Branch data Line data Source code
1 : : /*
2 : : * hash.cpp - hash table functions
3 : : *
4 : : * Copyright (C) 2005, 2007 Stefan Jahn <stefan@lkcc.org>
5 : : *
6 : : * This 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 2, or (at your option)
9 : : * any later version.
10 : : *
11 : : * This software 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.
15 : : *
16 : : * You should have received a copy of the GNU General Public License
17 : : * along with this package; see the file COPYING. If not, write to
18 : : * the Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
19 : : * Boston, MA 02110-1301, USA.
20 : : *
21 : : * $Id$
22 : : *
23 : : */
24 : :
25 : : #if HAVE_CONFIG_H
26 : : # include <config.h>
27 : : #endif
28 : :
29 : : #include <assert.h>
30 : : #include <stdio.h>
31 : : #include <stdlib.h>
32 : : #include <string.h>
33 : :
34 : : #include "hash.h"
35 : :
36 : : using namespace qucs;
37 : :
38 : : /* Calculate the hash code for a given string. This is the standard
39 : : callback for any newly created hash table. */
40 : 34140 : static int hash_code (char * key) {
41 : 34140 : int code = 0;
42 : 34140 : char * p = key;
43 [ + + ]: 236086 : while (*p) { code = (code << 1) ^ *p; p++; }
44 : 34140 : return code;
45 : : }
46 : :
47 : : /* This is the default callback for any newly created hash for
48 : : determining two keys being equal. Return zero if both strings are
49 : : equal, otherwise non-zero. */
50 : 2628 : static int hash_key_equals (char * key1, char * key2) {
51 : : char * p1, * p2;
52 [ - + ]: 2628 : if (key1 == key2) return 0;
53 : 2628 : p1 = key1;
54 : 2628 : p2 = key2;
55 [ + + ][ + - ]: 8326 : while (*p1 && *p2) {
[ + + ]
56 [ + + ]: 6114 : if (*p1 != *p2) return -1;
57 : 5698 : p1++; p2++;
58 : : }
59 [ + - ][ + - ]: 2212 : if (!*p1 && !*p2) return 0;
60 : 2628 : return -1;
61 : : }
62 : :
63 : : /* This is the default routine for determining the actual hash table
64 : : key length of the given key. */
65 : 32656 : static unsigned hash_key_length (char * key) {
66 : 32656 : unsigned len = 0;
67 [ + + ]: 230672 : while (*key++) len++;
68 : 32656 : len++;
69 : 32656 : return len;
70 : : }
71 : :
72 : : // Constructor for the hash table.
73 : : template <class type_t>
74 : 107 : qucs::hash<type_t>::hash (int size) {
75 : : // set initial hash table size to a binary value
76 : : int n;
77 [ + + ]: 321 : for (n = size, buckets = 1; n != 1; n >>= 1)
78 : 214 : buckets <<= 1;
79 [ - + ]: 107 : if (buckets < HASH_MIN_SIZE)
80 : 0 : buckets = HASH_MIN_SIZE;
81 : :
82 : : // initialize default values
83 : 107 : fill = 0;
84 : 107 : keys = 0;
85 : 107 : code = hash_code;
86 : 107 : equals = hash_key_equals;
87 : 107 : keylen = hash_key_length;
88 : :
89 : : // allocate space for the hash table buckets
90 : 107 : table = (hashbucket<type_t> **)
91 : : calloc (buckets, sizeof (hashbucket<type_t> *));
92 : 107 : }
93 : :
94 : : // Destructor for the hash table.
95 : : template <class type_t>
96 : 107 : qucs::hash<type_t>::~hash () {
97 [ + + ]: 659 : for (int n = 0; n < buckets; n++) {
98 [ + + ][ + - ]: 552 : if (table[n]) delete table[n];
99 : : }
100 : 107 : free (table);
101 : 107 : }
102 : :
103 : : /* Clears the hash table. Afterwards it does not contain any key.
104 : : The hash table is also shrunken to a minimal size. */
105 : : template <class type_t>
106 : 103 : void qucs::hash<type_t>::clear (void) {
107 [ + + ]: 13287 : for (int n = 0; n < buckets; n++) {
108 [ + + ][ + - ]: 13184 : if (table[n]) delete table[n];
109 : : }
110 : 103 : free (table);
111 : :
112 : : // reinitialize the hash table
113 : 103 : buckets = HASH_MIN_SIZE;
114 : 103 : fill = 0;
115 : 103 : keys = 0;
116 : 103 : table = (hashbucket<type_t> **)
117 : : calloc (buckets, sizeof (hashbucket<type_t> *));
118 : 103 : }
119 : :
120 : : // Returns number of items in the hash.
121 : : template <class type_t>
122 : : int qucs::hash<type_t>::count (void) {
123 : : return keys;
124 : : }
125 : :
126 : : /* Rebuilds a hash table. Double (type is HASH_EXPAND) its size and
127 : : expand the hash codes or half (type is HASH_SHRINK) its size and
128 : : shrink the hash codes if these would be placed somewhere else. */
129 : : template <class type_t>
130 : 520 : void qucs::hash<type_t>::rehash (int type) {
131 : : int n, e;
132 : : hashbucket<type_t> * bucket, * next;
133 : :
134 : : // Expand!
135 [ + - ]: 520 : if (type == HASH_EXPAND) {
136 : : // Reallocate and initialize the hash table itself.
137 : 520 : buckets *= 2;
138 : 520 : table = (hashbucket<type_t> **)
139 : : realloc (table, sizeof (hashbucket<type_t> *) * buckets);
140 [ + + ]: 13416 : for (n = buckets / 2; n < buckets; n++) { table[n] = NULL; }
141 : :
142 : : /* Go through all hash table entries and check if it is necessary
143 : : to relocate them. */
144 [ + + ]: 13416 : for (n = 0; n < buckets / 2; n++){
145 : 12896 : bucket = table[n];
146 [ + + ][ + + ]: 35048 : for (e = 0; bucket && e < bucket->size; e++) {
[ + + ]
147 : 22152 : int loc = HASH_LOCATION (bucket->entry[e]->code);
148 [ + + ]: 22152 : if (n != loc) {
149 : : /* copy this entry to the far entry */
150 [ + + ]: 11336 : if ((next = table[loc]) == NULL) {
151 : 7384 : next = new hashbucket<type_t> ();
152 : 7384 : table[loc] = next;
153 : : }
154 : 11336 : next->add (bucket->entry[e]);
155 [ + + ]: 11336 : if (next->size == 1) fill++;
156 : : /* delete this entry */
157 : 11336 : bucket->del (e);
158 [ + + ]: 11336 : if (bucket->size == 0) fill--;
159 : 11336 : e--;
160 : : }
161 : : }
162 : : }
163 : : }
164 : : // Shrink!
165 [ # # ][ # # ]: 0 : else if (type == HASH_SHRINK && buckets > HASH_MIN_SIZE) {
166 : 0 : buckets /= 2;
167 [ # # ]: 0 : for (n = buckets; n < buckets * 2; n++) {
168 : 0 : bucket = table[n];
169 [ # # ][ # # ]: 0 : if (bucket && bucket->size) {
170 [ # # ]: 0 : for (e = 0; e < bucket->size; e++) {
171 : 0 : int loc = HASH_LOCATION (bucket->entry[e]->code);
172 [ # # ]: 0 : if ((next = table[loc]) == NULL) {
173 : 0 : next = new hashbucket<type_t> ();
174 : : }
175 : 0 : next->add (bucket->entry[e]);
176 [ # # ]: 0 : if (next->size == 1) fill++;
177 : : }
178 [ # # ]: 0 : delete bucket;
179 : : }
180 : 0 : fill--;
181 : : }
182 : 0 : table = (hashbucket<type_t> **)
183 : : realloc (table, sizeof (hashbucket<type_t> *) * buckets);
184 : : }
185 : 520 : }
186 : :
187 : : /* This function adds a new element consisting of key and value to an
188 : : existing hash. If the hash is 75% filled it gets rehashed (size
189 : : will be doubled). When the key already exists then the value just
190 : : gets replaced dropping and returning the old value. */
191 : : template <class type_t>
192 : 16328 : type_t * qucs::hash<type_t>::put (char * key, type_t * value) {
193 : 16328 : int code = this->code (key);
194 : 16328 : hashbucket<type_t> * bucket = table[HASH_LOCATION (code)];
195 : :
196 : : /* Check if the key is already stored. If so replace the value. */
197 [ + + ]: 16328 : if (bucket) {
198 [ + + ]: 35984 : for (int e = 0; e < bucket->size; e++) {
199 [ + + ]: 23192 : if (bucket->entry[e]->code == code) {
200 [ - + ]: 208 : if (equals (bucket->entry[e]->key, key) == 0) {
201 : 0 : type_t * old = bucket->entry[e]->value;
202 : 0 : bucket->entry[e]->value = value;
203 : 0 : return old;
204 : : }
205 : : }
206 : : }
207 : : }
208 : : else {
209 : 3536 : bucket = new hashbucket<type_t> ();
210 : 3536 : table[HASH_LOCATION (code)] = bucket;
211 : : }
212 : :
213 : : /* Fill this entry. */
214 : 16328 : hashentry<type_t> * entry = new hashentry<type_t> ();
215 : 16328 : entry->key = (char *) malloc (keylen (key));
216 : 16328 : memcpy (entry->key, key, keylen (key));
217 : 16328 : entry->value = value;
218 : 16328 : entry->code = code;
219 : :
220 : 16328 : bucket->add (entry);
221 : 16328 : keys++;
222 : :
223 : : /* 75% filled ? */
224 [ + + ]: 16328 : if (bucket->size == 1) {
225 : 4680 : fill++;
226 [ + + ]: 4680 : if (fill > HASH_EXPAND_LIMIT) {
227 : 520 : rehash (HASH_EXPAND);
228 : : }
229 : : }
230 : 16328 : return NULL;
231 : : }
232 : :
233 : : /* Delete an existing hash entry accessed via a given key form the
234 : : hash table. Return NULL if the key has not been found within the
235 : : hash, otherwise the previous value. */
236 : : template <class type_t>
237 : : type_t * qucs::hash<type_t>::del (char * key) {
238 : : type_t * value;
239 : : int code = this->code (key);
240 : : hashbucket<type_t> * bucket = table[HASH_LOCATION (code)];
241 : : if (bucket) {
242 : : for (int n = 0; n < bucket->size; n++) {
243 : : if (bucket->entry[n]->code == code) {
244 : : if (equals (bucket->entry[n]->key, key) == 0) {
245 : : value = bucket->entry[n]->value;
246 : : bucket->del (n);
247 : : if (bucket->size == 0) {
248 : : fill--;
249 : : if (fill < HASH_SHRINK_LIMIT) {
250 : : rehash (HASH_SHRINK);
251 : : }
252 : : }
253 : : keys--;
254 : : return value;
255 : : }
256 : : }
257 : : }
258 : : }
259 : : return NULL;
260 : : }
261 : :
262 : : /* Hash table lookup. Find a value for a given key in the hash table.
263 : : Return NULL if the key has not been found within the hash table. */
264 : : template <class type_t>
265 : 17812 : type_t * qucs::hash<type_t>::get (char * key) {
266 : 17812 : int code = this->code (key);
267 : 17812 : hashbucket<type_t> * bucket = table[HASH_LOCATION (code)];
268 [ + + ]: 17812 : if (bucket) {
269 [ + + ]: 38348 : for (int n = 0; n < bucket->size; n++) {
270 [ + + ]: 25972 : if (bucket->entry[n]->code == code)
271 [ + + ]: 2420 : if (equals (bucket->entry[n]->key, key) == 0)
272 : 2212 : return bucket->entry[n]->value;
273 : : }
274 : : }
275 : 17812 : return NULL;
276 : : }
277 : :
278 : : // Constructor for hash table iterator.
279 : : template <class type_t>
280 : 208 : hashiterator<type_t>::hashiterator (hash<type_t> & h) {
281 : 208 : _hash = &h;
282 : 208 : _bucket = 0;
283 : 208 : _entry = 0;
284 : 208 : toLast ();
285 : 208 : toFirst ();
286 : 208 : }
287 : :
288 : : // Default constructor for hash table iterator.
289 : : template <class type_t>
290 : 207 : hashiterator<type_t>::hashiterator () {
291 : 207 : _hash = NULL;
292 : 207 : _bucket = 0;
293 : 207 : _entry = 0;
294 : 207 : _first = _last = _current = NULL;
295 : 207 : }
296 : :
297 : : // Destructor for hash table iterator.
298 : : template <class type_t>
299 : 415 : hashiterator<type_t>::~hashiterator () {
300 : 415 : }
301 : :
302 : : // Returns number of items this iterator operates on.
303 : : template <class type_t>
304 : : int hashiterator<type_t>::count (void) {
305 : : return _hash->keys;
306 : : }
307 : :
308 : : // Sets the current to the first item in the iterator list.
309 : : template <class type_t>
310 : 208 : char * hashiterator<type_t>::toFirst (void) {
311 [ + - ]: 1040 : for (int n = 0; n < _hash->buckets; n++) {
312 : 1040 : hashbucket<type_t> * bucket = _hash->table[n];
313 [ + - ][ + + ]: 1040 : if (bucket && bucket->size) {
314 : 208 : _bucket = n;
315 : 208 : _entry = 0;
316 : 208 : _current = _first = bucket->entry[_entry];
317 : 208 : return _current->key;
318 : : }
319 : : }
320 : 0 : _current = _first = NULL;
321 : 208 : return NULL;
322 : : }
323 : :
324 : : // Sets the current to the last item in the iterator list.
325 : : template <class type_t>
326 : 208 : char * hashiterator<type_t>::toLast (void) {
327 [ + - ]: 208 : for (int n = _hash->buckets - 1; n >= 0; n--) {
328 : 208 : hashbucket<type_t> * bucket = _hash->table[n];
329 [ + - ][ + - ]: 208 : if (bucket && bucket->size) {
330 : 208 : _bucket = n;
331 : 208 : _entry = bucket->size - 1;
332 : 208 : _current = _last = bucket->entry[_entry];
333 : 208 : return _current->key;
334 : : }
335 : : }
336 : 0 : _current = _last = NULL;
337 : 208 : return NULL;
338 : : }
339 : :
340 : : // Makes the succeeding item current and returns the new current item.
341 : : template <class type_t>
342 : 32656 : char * hashiterator<type_t>::operator++ (void) {
343 : 32656 : hashbucket<type_t> * bucket = _hash->table[_bucket];
344 [ + - ][ + + ]: 32656 : if (bucket && _entry < bucket->size - 1) {
345 : 15184 : _entry++;
346 : 15184 : _current = bucket->entry[_entry];
347 : 15184 : return _current->key;
348 : : }
349 [ + + ]: 25792 : for (int n = _bucket + 1; n < _hash->buckets; n++) {
350 : 25584 : bucket = _hash->table[n];
351 [ + + ][ + + ]: 25584 : if (bucket && bucket->size) {
352 : 17264 : _bucket = n;
353 : 17264 : _entry = 0;
354 : 17264 : _current = bucket->entry[_entry];
355 : 17264 : return _current->key;
356 : : }
357 : : }
358 : 208 : _current = NULL;
359 : 32656 : return NULL;
360 : : }
361 : :
362 : : // Makes the preceding item current and returns the new current item.
363 : : template <class type_t>
364 : : char * hashiterator<type_t>::operator-- (void) {
365 : : hashbucket<type_t> * bucket = _hash->table[_bucket];
366 : : if (bucket && _entry > 0) {
367 : : _entry--;
368 : : _current = bucket->entry[_entry];
369 : : return _current->key;
370 : : }
371 : : for (int n = _bucket - 1; n >= 0 ; n--) {
372 : : bucket = _hash->table[n];
373 : : if (bucket && bucket->size) {
374 : : _bucket = n;
375 : : _entry = bucket->size - 1;
376 : : _current = bucket->entry[_entry];
377 : : return _current->key;
378 : : }
379 : : }
380 : : _current = NULL;
381 : : return NULL;
382 : : }
383 : :
384 : : // Returns the current iterator item.
385 : : template <class type_t>
386 : 32864 : char * hashiterator<type_t>::current (void) {
387 [ + + ]: 32864 : return _current ? _current->key : NULL;
388 : : }
389 : :
390 : : // Returns the current iterator items key.
391 : : template <class type_t>
392 : : char * hashiterator<type_t>::currentKey (void) {
393 : : return current ();
394 : : }
395 : :
396 : : // Returns the current iterator items value.
397 : : template <class type_t>
398 : 32656 : type_t * hashiterator<type_t>::currentVal (void) {
399 [ + - ]: 32656 : return _current ? _current->value : NULL;
400 : : }
401 : :
402 : : // Returns the first iterator item.
403 : : template <class type_t>
404 : : char * hashiterator<type_t>::first (void) {
405 : : return _first ? _first->key : NULL;
406 : : }
407 : :
408 : : // Returns the last iterator item.
409 : : template <class type_t>
410 : : char * hashiterator<type_t>::last (void) {
411 : : return _last ? _last->key : NULL;
412 : : }
|
