]>
Commit | Line | Data |
---|---|---|
fd67aa11 | 1 | /* Copyright (C) 2021-2024 Free Software Foundation, Inc. |
bb368aad VM |
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> | |
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> | |
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 | |
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 | |
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 | |
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 | |
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 |