1/* Copyright (C) 2021-2024 Free Software Foundation, Inc.
2   Contributed by Oracle.
3
4   This file is part of GNU Binutils.
5
6   This program is free software; you can redistribute it and/or modify
7   it under the terms of the GNU General Public License as published by
8   the Free Software Foundation; either version 3, or (at your option)
9   any later version.
10
11   This program is distributed in the hope that it will be useful,
12   but WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   GNU General Public License for more details.
15
16   You should have received a copy of the GNU General Public License
17   along with this program; if not, write to the Free Software
18   Foundation, 51 Franklin Street - Fifth Floor, Boston,
19   MA 02110-1301, USA.  */
20
21/*
22 *  Interval Map implementation.
23 *
24 *    Interval Map makes the following assumptions:
25 *    - if duplicate keys, the last one will be stored
26 *    - <TBC>
27 */
28#ifndef _DBE_INTERVALMAP_H
29#define _DBE_INTERVALMAP_H
30
31#include <assert.h>
32#include <vec.h>
33#include <Map.h>
34
35template <typename Key_t, typename Value_t>
36class IntervalMap : public Map<Key_t, Value_t>
37{
38public:
39
40  IntervalMap ();
41  ~IntervalMap ();
42  void put (Key_t key, Value_t val);
43  Value_t get (Key_t key);
44  Value_t get (Key_t key, typename Map<Key_t, Value_t>::Relation rel);
45  Value_t remove (Key_t key);
46
47private:
48
49  struct Entry
50  {
51    Key_t key;
52    Value_t val;
53  };
54
55  static const int CHUNK_SIZE;
56
57  int entries;
58  int nchunks;
59  Entry **chunks;
60  Vector<Entry*> *index;
61};
62
63template <typename Key_t, typename Value_t>
64const int IntervalMap<Key_t, Value_t>::CHUNK_SIZE = 16384;
65
66template <typename Key_t, typename Value_t>
67IntervalMap<Key_t, Value_t>::IntervalMap ()
68{
69  entries = 0;
70  nchunks = 0;
71  chunks = NULL;
72  index = new Vector<Entry*>;
73}
74
75template <typename Key_t, typename Value_t>
76IntervalMap<Key_t, Value_t>::~IntervalMap ()
77{
78  for (int i = 0; i < nchunks; i++)
79    delete[] chunks[i];
80  delete[] chunks;
81  delete index;
82}
83
84template <typename Key_t, typename Value_t>
85void
86IntervalMap<Key_t, Value_t>::put (Key_t key, Value_t val)
87{
88  int lo = 0;
89  int hi = entries - 1;
90  while (lo <= hi)
91    {
92      int md = (lo + hi) / 2;
93      Entry *entry = index->fetch (md);
94      int cmp = entry->key < key ? -1 : entry->key > key ? 1 : 0;
95      if (cmp < 0)
96	lo = md + 1;
97      else if (cmp > 0)
98	hi = md - 1;
99      else
100	{
101	  entry->val = val;
102	  return;
103	}
104    }
105
106  if (entries >= nchunks * CHUNK_SIZE)
107    {
108      nchunks++;
109      // Reallocate Entry chunk array
110      Entry **new_chunks = new Entry*[nchunks];
111      for (int i = 0; i < nchunks - 1; i++)
112	new_chunks[i] = chunks[i];
113      delete chunks;
114      chunks = new_chunks;
115
116      // Allocate new chunk for entries.
117      chunks[nchunks - 1] = new Entry[CHUNK_SIZE];
118    }
119  Entry *entry = &chunks[entries / CHUNK_SIZE][entries % CHUNK_SIZE];
120  entry->key = key;
121  entry->val = val;
122  index->insert (lo, entry);
123  entries++;
124}
125
126template <typename Key_t, typename Value_t>
127Value_t
128IntervalMap<Key_t, Value_t>::get (Key_t key)
129{
130  return get (key, Map<Key_t, Value_t>::REL_EQ);
131}
132
133template <typename Key_t, typename Value_t>
134Value_t
135IntervalMap<Key_t, Value_t>::get (Key_t key, typename Map<Key_t, Value_t>::Relation rel)
136{
137  int lo = 0;
138  int hi = entries - 1;
139  while (lo <= hi)
140    {
141      int md = (lo + hi) / 2;
142      Entry *entry = index->fetch (md);
143      int cmp = entry->key < key ? -1 : entry->key > key ? 1 : 0;
144      switch (rel)
145	{
146	case Map<Key_t, Value_t>::REL_LT:
147	  if (cmp < 0)
148	    lo = md + 1;
149	  else
150	    hi = md - 1;
151	  break;
152	case Map<Key_t, Value_t>::REL_GT:
153	  if (cmp <= 0)
154	    lo = md + 1;
155	  else
156	    hi = md - 1;
157	  break;
158	case Map<Key_t, Value_t>::REL_LE:
159	case Map<Key_t, Value_t>::REL_GE:
160	case Map<Key_t, Value_t>::REL_EQ:
161	  if (cmp < 0)
162	    lo = md + 1;
163	  else if (cmp > 0)
164	    hi = md - 1;
165	  else
166	    return entry->val;
167	  break;
168	}
169    }
170  switch (rel)
171    {
172    case Map<Key_t, Value_t>::REL_LT:
173    case Map<Key_t, Value_t>::REL_LE:
174      return hi >= 0 ? index->fetch (hi)->val : (Value_t) 0;
175    case Map<Key_t, Value_t>::REL_GT:
176    case Map<Key_t, Value_t>::REL_GE:
177      return lo < entries ? index->fetch (lo)->val : (Value_t) 0;
178    case Map<Key_t, Value_t>::REL_EQ:
179      break;
180    }
181  return (Value_t) 0;
182}
183
184template <typename Key_t, typename Value_t>
185Value_t
186IntervalMap<Key_t, Value_t>::remove (Key_t)
187{
188  // Not implemented
189  if (1)
190    assert (0);
191  return (Value_t) 0;
192}
193
194#endif
195