1 /* Copyright (C) 2021 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
35 template <typename Key_t, typename Value_t>
36 class IntervalMap : public Map<Key_t, Value_t>
37 {
38 public:
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
47 private:
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
63 template <typename Key_t, typename Value_t>
64 const int IntervalMap<Key_t, Value_t>::CHUNK_SIZE = 16384;
65
66 template <typename Key_t, typename Value_t>
IntervalMap()67 IntervalMap<Key_t, Value_t>::IntervalMap ()
68 {
69 entries = 0;
70 nchunks = 0;
71 chunks = NULL;
72 index = new Vector<Entry*>;
73 }
74
75 template <typename Key_t, typename Value_t>
~IntervalMap()76 IntervalMap<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
84 template <typename Key_t, typename Value_t>
85 void
put(Key_t key,Value_t val)86 IntervalMap<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
126 template <typename Key_t, typename Value_t>
127 Value_t
get(Key_t key)128 IntervalMap<Key_t, Value_t>::get (Key_t key)
129 {
130 return get (key, Map<Key_t, Value_t>::REL_EQ);
131 }
132
133 template <typename Key_t, typename Value_t>
134 Value_t
get(Key_t key,typename Map<Key_t,Value_t>::Relation rel)135 IntervalMap<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
184 template <typename Key_t, typename Value_t>
185 Value_t
remove(Key_t)186 IntervalMap<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