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. */
21 #ifndef _DBE_DEFAULTMAP_H
22 #define _DBE_DEFAULTMAP_H
28 template <typename Key_t
, typename Value_t
>
29 class DefaultMap
: public Map
<Key_t
, Value_t
>
36 void put (Key_t key
, Value_t val
);
37 Value_t
get (Key_t key
);
38 Value_t
get (Key_t key
, typename Map
<Key_t
, Value_t
>::Relation rel
);
39 Value_t
remove (Key_t
);
40 Vector
<Key_t
> *keySet ();
41 Vector
<Value_t
> *values ();
51 static const int CHUNK_SIZE
;
52 static const int HTABLE_SIZE
;
57 Vector
<Entry
*> *index
;
62 template <typename Key_t
, typename Value_t
>
63 const int DefaultMap
<Key_t
, Value_t
>::CHUNK_SIZE
= 16384;
64 template <typename Key_t
, typename Value_t
>
65 const int DefaultMap
<Key_t
, Value_t
>::HTABLE_SIZE
= 1024;
67 template <typename Key_t
, typename Value_t
>
68 DefaultMap
<Key_t
, Value_t
>::DefaultMap ()
73 index
= new Vector
<Entry
*>;
74 hashTable
= new Entry
*[HTABLE_SIZE
];
75 for (int i
= 0; i
< HTABLE_SIZE
; i
++)
79 template <typename Key_t
, typename Value_t
>
80 DefaultMap
<Key_t
, Value_t
>::~DefaultMap ()
82 for (int i
= 0; i
< nchunks
; i
++)
89 template <typename Key_t
, typename Value_t
>
91 DefaultMap
<Key_t
, Value_t
>::clear ()
95 for (int i
= 0; i
< HTABLE_SIZE
; i
++)
99 template <typename Key_t
>
103 unsigned h
= (unsigned) ((unsigned long) key
);
104 h
^= (h
>> 20) ^ (h
>> 12);
105 return (h
^ (h
>> 7) ^ (h
>> 4));
108 template <typename Key_t
, typename Value_t
>
110 DefaultMap
<Key_t
, Value_t
>::put (Key_t key
, Value_t val
)
112 unsigned idx
= hash (key
) % HTABLE_SIZE
;
113 Entry
*entry
= hashTable
[idx
];
114 if (entry
&& entry
->key
== key
)
120 int hi
= entries
- 1;
123 int md
= (lo
+ hi
) / 2;
124 entry
= index
->fetch (md
);
125 int cmp
= entry
->key
< key
? -1 : entry
->key
> key
? 1 : 0;
136 if (entries
>= nchunks
* CHUNK_SIZE
)
139 // Reallocate Entry chunk array
140 Entry
**new_chunks
= new Entry
*[nchunks
];
141 for (int i
= 0; i
< nchunks
- 1; i
++)
142 new_chunks
[i
] = chunks
[i
];
146 // Allocate new chunk for entries.
147 chunks
[nchunks
- 1] = new Entry
[CHUNK_SIZE
];
149 entry
= &chunks
[entries
/ CHUNK_SIZE
][entries
% CHUNK_SIZE
];
152 index
->insert (lo
, entry
);
153 hashTable
[idx
] = entry
;
157 template <typename Key_t
, typename Value_t
>
159 DefaultMap
<Key_t
, Value_t
>::get (Key_t key
)
161 unsigned idx
= hash (key
) % HTABLE_SIZE
;
162 Entry
*entry
= hashTable
[idx
];
163 if (entry
&& entry
->key
== key
)
167 int hi
= entries
- 1;
170 int md
= (lo
+ hi
) / 2;
171 entry
= index
->fetch (md
);
172 int cmp
= entry
->key
< key
? -1 : entry
->key
> key
? 1 : 0;
179 hashTable
[idx
] = entry
;
186 template <typename Key_t
, typename Value_t
>
188 DefaultMap
<Key_t
, Value_t
>::get (Key_t key
,
189 typename Map
<Key_t
, Value_t
>::Relation rel
)
191 if (rel
!= Map
<Key_t
, Value_t
>::REL_EQ
)
196 template <typename Key_t
, typename Value_t
>
198 DefaultMap
<Key_t
, Value_t
>::remove (Key_t
)
206 template <typename Key_t
, typename Value_t
>
208 DefaultMap
<Key_t
, Value_t
>::values ()
210 Vector
<Value_t
> *vals
= new Vector
<Value_t
>(entries
);
211 for (int i
= 0; i
< entries
; ++i
)
213 Entry
*entry
= index
->fetch (i
);
214 vals
->append (entry
->val
);
219 template <typename Key_t
, typename Value_t
>
221 DefaultMap
<Key_t
, Value_t
>::keySet ()
223 Vector
<Key_t
> *keys
= new Vector
<Key_t
>(entries
);
224 for (int i
= 0; i
< entries
; ++i
)
226 Entry
*entry
= index
->fetch (i
);
227 keys
->append (entry
->key
);