xref: /netbsd-src/external/gpl3/binutils.old/dist/gprofng/src/IntervalMap.h (revision c42dbd0ed2e61fe6eda8590caa852ccf34719964)
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