1 /* Copyright (C) 2021-2024 Free Software Foundation, Inc.
4 This file is part of GNU Binutils.
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)
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.
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. */
22 * Interval Map implementation.
24 * Interval Map makes the following assumptions:
25 * - if duplicate keys, the last one will be stored
28 #ifndef _DBE_INTERVALMAP_H
29 #define _DBE_INTERVALMAP_H
35 template <typename Key_t
, typename Value_t
>
36 class IntervalMap
: public Map
<Key_t
, Value_t
>
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
);
55 static const int CHUNK_SIZE
;
60 Vector
<Entry
*> *index
;
63 template <typename Key_t
, typename Value_t
>
64 const int IntervalMap
<Key_t
, Value_t
>::CHUNK_SIZE
= 16384;
66 template <typename Key_t
, typename Value_t
>
67 IntervalMap
<Key_t
, Value_t
>::IntervalMap ()
72 index
= new Vector
<Entry
*>;
75 template <typename Key_t
, typename Value_t
>
76 IntervalMap
<Key_t
, Value_t
>::~IntervalMap ()
78 for (int i
= 0; i
< nchunks
; i
++)
84 template <typename Key_t
, typename Value_t
>
86 IntervalMap
<Key_t
, Value_t
>::put (Key_t key
, Value_t val
)
92 int md
= (lo
+ hi
) / 2;
93 Entry
*entry
= index
->fetch (md
);
94 int cmp
= entry
->key
< key
? -1 : entry
->key
> key
? 1 : 0;
106 if (entries
>= nchunks
* CHUNK_SIZE
)
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
];
116 // Allocate new chunk for entries.
117 chunks
[nchunks
- 1] = new Entry
[CHUNK_SIZE
];
119 Entry
*entry
= &chunks
[entries
/ CHUNK_SIZE
][entries
% CHUNK_SIZE
];
122 index
->insert (lo
, entry
);
126 template <typename Key_t
, typename Value_t
>
128 IntervalMap
<Key_t
, Value_t
>::get (Key_t key
)
130 return get (key
, Map
<Key_t
, Value_t
>::REL_EQ
);
133 template <typename Key_t
, typename Value_t
>
135 IntervalMap
<Key_t
, Value_t
>::get (Key_t key
, typename Map
<Key_t
, Value_t
>::Relation rel
)
138 int hi
= entries
- 1;
141 int md
= (lo
+ hi
) / 2;
142 Entry
*entry
= index
->fetch (md
);
143 int cmp
= entry
->key
< key
? -1 : entry
->key
> key
? 1 : 0;
146 case Map
<Key_t
, Value_t
>::REL_LT
:
152 case Map
<Key_t
, Value_t
>::REL_GT
:
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
:
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
:
184 template <typename Key_t
, typename Value_t
>
186 IntervalMap
<Key_t
, Value_t
>::remove (Key_t
)