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