1 /**************************************************************************\
2 * Copyright (c) Kongsberg Oil & Gas Technologies AS
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met:
8 *
9 * Redistributions of source code must retain the above copyright notice,
10 * this list of conditions and the following disclaimer.
11 *
12 * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * Neither the name of the copyright holder nor the names of its
17 * contributors may be used to endorse or promote products derived from
18 * this software without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 \**************************************************************************/
32
33 /* OBSOLETE: the C data abstraction for a hash has been moved into
34 dict.c and renamed to cc_dict. This code is present here just to be
35 backwards API and ABI compatible on the Coin 2.x releases. */
36
37 /* ********************************************************************** */
38
39 #define COIN_ALLOW_CC_HASH /* Hack to get around include protection
40 for obsoleted ADT. */
41
42 /*! \file hash.h */
43 #include <Inventor/C/base/hash.h>
44
45 #include <cassert>
46 #include <cstdio>
47 #include <cstring>
48
49 #include <Inventor/C/tidbits.h>
50 #include <Inventor/C/errors/debugerror.h>
51
52 #include "base/hashp.h"
53 #include "tidbitsp.h"
54 #include "coindefs.h"
55
56 #ifndef COIN_WORKAROUND_NO_USING_STD_FUNCS
57 using std::memset;
58 #endif // !COIN_WORKAROUND_NO_USING_STD_FUNCS
59
60 #undef COIN_ALLOW_CC_HASH
61
62 /* ********************************************************************** */
63
64 /*!
65 \typedef uintptr_t cc_hash_key;
66
67 The type definition used locally for a hash key.
68 */
69
70 /*
71 \struct cc_hash hash.h Inventor/C/base/hash.h
72
73 Note that the cc_hash structure has been obsolete and should no longer be
74 used. It is maintained purely for backwards compatability.
75
76 cc_dict is now the preferred structure.
77 */
78
79 /*!
80 \typedef struct cc_hash cc_hash;
81
82 The type definition for the cc_hash structure.
83 */
84
85 /*!
86 \typedef cc_hash_key cc_hash_func(const cc_hash_key key)
87
88 A type definition for cc_hash_func function pointers.
89 */
90
91 /*!
92 \typedef void cc_hash_apply_func(cc_hash_key key, void * val, void * closure)
93
94 A type definition for cc_hash_apply_func function pointers.
95 */
96
97 /* ********************************************************************** */
98 /* private functions */
99
100 extern "C" {
101
102 /*!
103 Private default function - actually does nothing.
104 */
105
106 static cc_hash_key
hash_default_hashfunc(const cc_hash_key key)107 hash_default_hashfunc(const cc_hash_key key)
108 {
109 return key;
110 }
111
112 } // extern "C"
113
114 /*!
115 Private function that returns the index for a given key.
116 */
117
118 static unsigned int
hash_get_index(cc_hash * ht,cc_hash_key key)119 hash_get_index(cc_hash * ht, cc_hash_key key)
120 {
121 assert(ht != NULL);
122 key = ht->hashfunc(key);
123 return key % ht->size;
124 }
125
126 /*!
127 Private function to resize the hash table.
128 */
129
130 static void
hash_resize(cc_hash * ht,unsigned int newsize)131 hash_resize(cc_hash * ht, unsigned int newsize)
132 {
133 cc_hash_entry ** oldbuckets = ht->buckets;
134 unsigned int oldsize = ht->size, i;
135 cc_hash_entry * prev;
136
137 /* Never shrink the table */
138 if (ht->size >= newsize)
139 return;
140
141 ht->size = newsize;
142 ht->elements = 0;
143 ht->threshold = (unsigned int) (newsize * ht->loadfactor);
144 ht->buckets = (cc_hash_entry **) calloc(newsize, sizeof(cc_hash_entry*));
145
146 /* Transfer all mappings */
147 for (i = 0; i < oldsize; i++) {
148 cc_hash_entry * he = oldbuckets[i];
149 while (he) {
150 cc_hash_put(ht, he->key, he->val);
151 prev = he;
152 he = he->next;
153 cc_memalloc_deallocate(ht->memalloc, (void*) prev);
154 }
155 }
156 free(oldbuckets);
157 }
158
159 /* ********************************************************************** */
160 /* public api */
161
162 /*!
163 Construct a hash table.
164
165 \a size is the initial bucket size. The caller need not attempt to
166 find a good (prime number) value for this argument to ensure good
167 hashing. That will be taken care of internally.
168
169 \a loadfactor is the percentage the table should be filled before
170 resizing, and should be a number from 0 to 1. It is of course
171 possible to specify a number bigger than 1, but then there will be
172 greater chance of having many elements on the same bucket (linear
173 search for an element). If you supply a number <= 0 for loadfactor,
174 the default value 0.75 will be used.
175 */
176 cc_hash *
cc_hash_construct(unsigned int size,float loadfactor)177 cc_hash_construct(unsigned int size, float loadfactor)
178 {
179 unsigned int s;
180 cc_hash * ht = (cc_hash *) malloc(sizeof(cc_hash));
181
182 /* size should be a prime number */
183 s = (unsigned int) coin_geq_prime_number(size);
184 if (loadfactor <= 0.0f) loadfactor = 0.75f;
185
186 ht->size = s;
187 ht->elements = 0;
188 ht->threshold = (unsigned int) (s * loadfactor);
189 ht->loadfactor = loadfactor;
190 ht->buckets = (cc_hash_entry **) calloc(s, sizeof(cc_hash_entry*));
191 ht->hashfunc = hash_default_hashfunc;
192 /* we use a memory allocator to avoid an operating system malloc
193 every time a new entry is needed */
194 ht->memalloc = cc_memalloc_construct(sizeof(cc_hash_entry));
195 return ht;
196 }
197
198 /*!
199 Destruct the hash table \a ht.
200 */
201 void
cc_hash_destruct(cc_hash * ht)202 cc_hash_destruct(cc_hash * ht)
203 {
204 cc_hash_clear(ht);
205 cc_memalloc_destruct(ht->memalloc);
206 free(ht->buckets);
207 free(ht);
208 }
209
210 /*!
211 Clear/remove all elements in the hash table \a ht.
212 */
213 void
cc_hash_clear(cc_hash * ht)214 cc_hash_clear(cc_hash * ht)
215 {
216 // cc_memalloc_clear() will free memory used by internal
217 // structures. To avoid continuous memory allocation/deallocation
218 // that could be bad for performance (cc_hash is used in
219 // SoSensorManager) we manually free all entries from cc_memalloc
220 // instead.
221 #if 0 // disabled
222 cc_memalloc_clear(ht->memalloc); /* free all memory used by all entries */
223 #else // new version that will not trigger any malloc()/free() calls
224 unsigned int i;
225 cc_hash_entry * entry;
226 cc_hash_entry * next;
227 for (i = 0; i < ht->size; i++) {
228 entry = ht->buckets[i];
229 while (entry) {
230 next = entry->next;
231 cc_memalloc_deallocate(ht->memalloc, (void*) entry);
232 entry = next;
233 }
234 }
235 #endif // new version
236
237 // all memory has been freed. Just clear buckets
238 memset(ht->buckets, 0, ht->size * sizeof(cc_hash_entry*));
239 ht->elements = 0;
240 }
241
242 /*!
243
244 Insert a new element in the hash table \a ht. \a key is the key used
245 to identify the element, while \a val is the element value. If \a
246 key is already used by another element, the element value will be
247 overwritten, and \e FALSE is returned. Otherwise a new element is
248 created and \e TRUE is returned.
249
250 */
251 SbBool
cc_hash_put(cc_hash * ht,cc_hash_key key,void * val)252 cc_hash_put(cc_hash * ht, cc_hash_key key, void * val)
253 {
254 unsigned int i = hash_get_index(ht, key);
255 cc_hash_entry * he = ht->buckets[i];
256
257 while (he) {
258 if (he->key == key) {
259 /* Replace the old value */
260 he->val = val;
261 return FALSE;
262 }
263 he = he->next;
264 }
265
266 /* Key not already in the hash table; insert a new
267 * entry as the first element in the bucket
268 */
269 he = (cc_hash_entry *) cc_memalloc_allocate(ht->memalloc);
270 he->key = key;
271 he->val = val;
272 he->next = ht->buckets[i];
273 ht->buckets[i] = he;
274
275 if (ht->elements++ >= ht->threshold) {
276 hash_resize(ht, (unsigned int) coin_geq_prime_number(ht->size + 1));
277 }
278 return TRUE;
279 }
280
281 /*!
282
283 Find the element with key value \a key. If found, the value is written to
284 \a val, and TRUE is returned. Otherwise FALSE is returned and \a val
285 is not changed.
286
287 */
288 SbBool
cc_hash_get(cc_hash * ht,cc_hash_key key,void ** val)289 cc_hash_get(cc_hash * ht, cc_hash_key key, void ** val)
290 {
291 cc_hash_entry * he;
292 unsigned int i = hash_get_index(ht, key);
293 he = ht->buckets[i];
294 while (he) {
295 if (he->key == key) {
296 *val = he->val;
297 return TRUE;
298 }
299 he = he->next;
300 }
301 return FALSE;
302 }
303
304 /*!
305 Attempt to remove the element with key value \a key. Returns
306 TRUE if found, FALSE otherwise.
307 */
308 SbBool
cc_hash_remove(cc_hash * ht,cc_hash_key key)309 cc_hash_remove(cc_hash * ht, cc_hash_key key)
310 {
311 cc_hash_entry * he, *next, * prev;
312 unsigned int i = hash_get_index(ht, key);
313
314 he = ht->buckets[i];
315 prev = NULL;
316 while (he) {
317 next = he->next;
318 if (he->key == key) {
319 ht->elements--;
320 if (prev == NULL) {
321 ht->buckets[i] = next;
322 }
323 else {
324 prev->next = next;
325 }
326 cc_memalloc_deallocate(ht->memalloc, (void*) he);
327 return TRUE;
328 }
329 prev = he;
330 he = next;
331 }
332 return FALSE;
333 }
334
335 /*!
336 Return the number of elements in the hash table.
337 */
338 unsigned int
cc_hash_get_num_elements(cc_hash * ht)339 cc_hash_get_num_elements(cc_hash * ht)
340 {
341 return ht->elements;
342 }
343
344 /*!
345 Set the hash func that is used to map key values into
346 a bucket index.
347 */
348 void
cc_hash_set_hash_func(cc_hash * ht,cc_hash_func * func)349 cc_hash_set_hash_func(cc_hash * ht, cc_hash_func * func)
350 {
351 ht->hashfunc = func;
352 }
353
354 /*!
355 Call \a func for for each element in the hash table.
356 */
357 void
cc_hash_apply(cc_hash * ht,cc_hash_apply_func * func,void * closure)358 cc_hash_apply(cc_hash * ht, cc_hash_apply_func * func, void * closure)
359 {
360 unsigned int i;
361 cc_hash_entry * elem;
362 for (i = 0; i < ht->size; i++) {
363 elem = ht->buckets[i];
364 while (elem) {
365 func(elem->key, elem->val, closure);
366 elem = elem->next;
367 }
368 }
369 }
370
371 /*!
372 For debugging only. Prints information about hash with
373 cc_debugerror.
374 */
375 void
cc_hash_print_stat(cc_hash * ht)376 cc_hash_print_stat(cc_hash * ht)
377 {
378 unsigned int i, used_buckets = 0, max_chain_l = 0;
379 for (i = 0; i < ht->size; i++) {
380 if (ht->buckets[i]) {
381 unsigned int chain_l = 0;
382 cc_hash_entry * he = ht->buckets[i];
383 used_buckets++;
384 while (he) {
385 chain_l++;
386 he = he->next;
387 }
388 if (chain_l > max_chain_l) max_chain_l = chain_l;
389 }
390 }
391 cc_debugerror_postinfo("cc_hash_print_stat",
392 "Used buckets %u of %u (%u elements), "
393 "avg chain length: %.2f, max chain length: %u\n",
394 used_buckets, ht->size, ht->elements,
395 (float)ht->elements / used_buckets, max_chain_l);
396 }
397