My Project  0.0.16
QUCS Mapping
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
hash.cpp
Go to the documentation of this file.
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: hash.cpp 1825 2011-03-11 20:42:14Z ela $
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 static int hash_code (char * key) {
41  int code = 0;
42  char * p = key;
43  while (*p) { code = (code << 1) ^ *p; p++; }
44  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 static int hash_key_equals (char * key1, char * key2) {
51  char * p1, * p2;
52  if (key1 == key2) return 0;
53  p1 = key1;
54  p2 = key2;
55  while (*p1 && *p2) {
56  if (*p1 != *p2) return -1;
57  p1++; p2++;
58  }
59  if (!*p1 && !*p2) return 0;
60  return -1;
61 }
62 
63 /* This is the default routine for determining the actual hash table
64  key length of the given key. */
65 static unsigned hash_key_length (char * key) {
66  unsigned len = 0;
67  while (*key++) len++;
68  len++;
69  return len;
70 }
71 
72 // Constructor for the hash table.
73 template <class type_t>
74 hash<type_t>::hash (int size) {
75  // set initial hash table size to a binary value
76  int n;
77  for (n = size, buckets = 1; n != 1; n >>= 1)
78  buckets <<= 1;
79  if (buckets < HASH_MIN_SIZE)
80  buckets = HASH_MIN_SIZE;
81 
82  // initialize default values
83  fill = 0;
84  keys = 0;
85  code = hash_code;
86  equals = hash_key_equals;
87  keylen = hash_key_length;
88 
89  // allocate space for the hash table buckets
90  table = (hashbucket<type_t> **)
91  calloc (buckets, sizeof (hashbucket<type_t> *));
92 }
93 
94 // Destructor for the hash table.
95 template <class type_t>
97  for (int n = 0; n < buckets; n++) {
98  if (table[n]) delete table[n];
99  }
100  free (table);
101 }
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 void hash<type_t>::clear (void) {
107  for (int n = 0; n < buckets; n++) {
108  if (table[n]) delete table[n];
109  }
110  free (table);
111 
112  // reinitialize the hash table
113  buckets = HASH_MIN_SIZE;
114  fill = 0;
115  keys = 0;
116  table = (hashbucket<type_t> **)
117  calloc (buckets, sizeof (hashbucket<type_t> *));
118 }
119 
120 // Returns number of items in the hash.
121 template <class type_t>
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 void hash<type_t>::rehash (int type) {
131  int n, e;
132  hashbucket<type_t> * bucket, * next;
133 
134  // Expand!
135  if (type == HASH_EXPAND) {
136  // Reallocate and initialize the hash table itself.
137  buckets *= 2;
138  table = (hashbucket<type_t> **)
139  realloc (table, sizeof (hashbucket<type_t> *) * buckets);
140  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  for (n = 0; n < buckets / 2; n++){
145  bucket = table[n];
146  for (e = 0; bucket && e < bucket->size; e++) {
147  int loc = HASH_LOCATION (bucket->entry[e]->code);
148  if (n != loc) {
149  /* copy this entry to the far entry */
150  if ((next = table[loc]) == NULL) {
151  next = new hashbucket<type_t> ();
152  table[loc] = next;
153  }
154  next->add (bucket->entry[e]);
155  if (next->size == 1) fill++;
156  /* delete this entry */
157  bucket->del (e);
158  if (bucket->size == 0) fill--;
159  e--;
160  }
161  }
162  }
163  }
164  // Shrink!
165  else if (type == HASH_SHRINK && buckets > HASH_MIN_SIZE) {
166  buckets /= 2;
167  for (n = buckets; n < buckets * 2; n++) {
168  bucket = table[n];
169  if (bucket && bucket->size) {
170  for (e = 0; e < bucket->size; e++) {
171  int loc = HASH_LOCATION (bucket->entry[e]->code);
172  if ((next = table[loc]) == NULL) {
173  next = new hashbucket<type_t> ();
174  }
175  next->add (bucket->entry[e]);
176  if (next->size == 1) fill++;
177  }
178  delete bucket;
179  }
180  fill--;
181  }
182  table = (hashbucket<type_t> **)
183  realloc (table, sizeof (hashbucket<type_t> *) * buckets);
184  }
185 }
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 type_t * hash<type_t>::put (char * key, type_t * value) {
193  int code = this->code (key);
194  hashbucket<type_t> * bucket = table[HASH_LOCATION (code)];
195 
196  /* Check if the key is already stored. If so replace the value. */
197  if (bucket) {
198  for (int e = 0; e < bucket->size; e++) {
199  if (bucket->entry[e]->code == code) {
200  if (equals (bucket->entry[e]->key, key) == 0) {
201  type_t * old = bucket->entry[e]->value;
202  bucket->entry[e]->value = value;
203  return old;
204  }
205  }
206  }
207  }
208  else {
209  bucket = new hashbucket<type_t> ();
210  table[HASH_LOCATION (code)] = bucket;
211  }
212 
213  /* Fill this entry. */
214  hashentry<type_t> * entry = new hashentry<type_t> ();
215  entry->key = (char *) malloc (keylen (key));
216  memcpy (entry->key, key, keylen (key));
217  entry->value = value;
218  entry->code = code;
219 
220  bucket->add (entry);
221  keys++;
222 
223  /* 75% filled ? */
224  if (bucket->size == 1) {
225  fill++;
226  if (fill > HASH_EXPAND_LIMIT) {
227  rehash (HASH_EXPAND);
228  }
229  }
230  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 * 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 type_t * hash<type_t>::get (char * key) {
266  int code = this->code (key);
267  hashbucket<type_t> * bucket = table[HASH_LOCATION (code)];
268  if (bucket) {
269  for (int n = 0; n < bucket->size; n++) {
270  if (bucket->entry[n]->code == code)
271  if (equals (bucket->entry[n]->key, key) == 0)
272  return bucket->entry[n]->value;
273  }
274  }
275  return NULL;
276 }
277 
278 // Constructor for hash table iterator.
279 template <class type_t>
281  _hash = &h;
282  _bucket = 0;
283  _entry = 0;
284  toLast ();
285  toFirst ();
286 }
287 
288 // Default constructor for hash table iterator.
289 template <class type_t>
291  _hash = NULL;
292  _bucket = 0;
293  _entry = 0;
294  _first = _last = _current = NULL;
295 }
296 
297 // Destructor for hash table iterator.
298 template <class type_t>
300 }
301 
302 // Returns number of items this iterator operates on.
303 template <class type_t>
305  return _hash->keys;
306 }
307 
308 // Sets the current to the first item in the iterator list.
309 template <class type_t>
311  for (int n = 0; n < _hash->buckets; n++) {
312  hashbucket<type_t> * bucket = _hash->table[n];
313  if (bucket && bucket->size) {
314  _bucket = n;
315  _entry = 0;
316  _current = _first = bucket->entry[_entry];
317  return _current->key;
318  }
319  }
320  _current = _first = NULL;
321  return NULL;
322 }
323 
324 // Sets the current to the last item in the iterator list.
325 template <class type_t>
327  for (int n = _hash->buckets - 1; n >= 0; n--) {
328  hashbucket<type_t> * bucket = _hash->table[n];
329  if (bucket && bucket->size) {
330  _bucket = n;
331  _entry = bucket->size - 1;
332  _current = _last = bucket->entry[_entry];
333  return _current->key;
334  }
335  }
336  _current = _last = NULL;
337  return NULL;
338 }
339 
340 // Makes the succeeding item current and returns the new current item.
341 template <class type_t>
343  hashbucket<type_t> * bucket = _hash->table[_bucket];
344  if (bucket && _entry < bucket->size - 1) {
345  _entry++;
346  _current = bucket->entry[_entry];
347  return _current->key;
348  }
349  for (int n = _bucket + 1; n < _hash->buckets; n++) {
350  bucket = _hash->table[n];
351  if (bucket && bucket->size) {
352  _bucket = n;
353  _entry = 0;
354  _current = bucket->entry[_entry];
355  return _current->key;
356  }
357  }
358  _current = NULL;
359  return NULL;
360 }
361 
362 // Makes the preceding item current and returns the new current item.
363 template <class type_t>
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>
387  return _current ? _current->key : NULL;
388 }
389 
390 // Returns the current iterator items key.
391 template <class type_t>
393  return current ();
394 }
395 
396 // Returns the current iterator items value.
397 template <class type_t>
399  return _current ? _current->value : NULL;
400 }
401 
402 // Returns the first iterator item.
403 template <class type_t>
405  return _first ? _first->key : NULL;
406 }
407 
408 // Returns the last iterator item.
409 template <class type_t>
411  return _last ? _last->key : NULL;
412 }