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