Qucs-core
0.0.19
|
00001 /* 00002 * hash.cpp - hash table functions 00003 * 00004 * Copyright (C) 2005, 2007 Stefan Jahn <stefan@lkcc.org> 00005 * 00006 * This is free software; you can redistribute it and/or modify 00007 * it under the terms of the GNU General Public License as published by 00008 * the Free Software Foundation; either version 2, or (at your option) 00009 * any later version. 00010 * 00011 * This software is distributed in the hope that it will be useful, 00012 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 * GNU General Public License for more details. 00015 * 00016 * You should have received a copy of the GNU General Public License 00017 * along with this package; see the file COPYING. If not, write to 00018 * the Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor, 00019 * Boston, MA 02110-1301, USA. 00020 * 00021 * $Id$ 00022 * 00023 */ 00024 00025 #if HAVE_CONFIG_H 00026 # include <config.h> 00027 #endif 00028 00029 #include <assert.h> 00030 #include <stdio.h> 00031 #include <stdlib.h> 00032 #include <string.h> 00033 00034 #include "hash.h" 00035 00036 using namespace qucs; 00037 00038 /* Calculate the hash code for a given string. This is the standard 00039 callback for any newly created hash table. */ 00040 static inline int hash_code (char * key) { 00041 int code = 0; 00042 char * p = key; 00043 while (*p) { code = (code << 1) ^ *p; p++; } 00044 return code; 00045 } 00046 00047 /* This is the default callback for any newly created hash for 00048 determining two keys being equal. Return zero if both strings are 00049 equal, otherwise non-zero. */ 00050 static inline int hash_key_equals (char * key1, char * key2) { 00051 char * p1, * p2; 00052 if (key1 == key2) return 0; 00053 p1 = key1; 00054 p2 = key2; 00055 while (*p1 && *p2) { 00056 if (*p1 != *p2) return -1; 00057 p1++; p2++; 00058 } 00059 if (!*p1 && !*p2) return 0; 00060 return -1; 00061 } 00062 00063 /* This is the default routine for determining the actual hash table 00064 key length of the given key. */ 00065 static inline unsigned hash_key_length (char * key) { 00066 unsigned len = 0; 00067 while (*key++) len++; 00068 len++; 00069 return len; 00070 } 00071 00072 // Constructor for the hash table. 00073 template <class type_t> 00074 qucs::hash<type_t>::hash (int size) { 00075 // set initial hash table size to a binary value 00076 int n; 00077 for (n = size, buckets = 1; n != 1; n >>= 1) 00078 buckets <<= 1; 00079 if (buckets < HASH_MIN_SIZE) 00080 buckets = HASH_MIN_SIZE; 00081 00082 // initialize default values 00083 fill = 0; 00084 keys = 0; 00085 code = hash_code; 00086 equals = hash_key_equals; 00087 keylen = hash_key_length; 00088 00089 // allocate space for the hash table buckets 00090 table = (hashbucket<type_t> **) 00091 calloc (buckets, sizeof (hashbucket<type_t> *)); 00092 } 00093 00094 // Destructor for the hash table. 00095 template <class type_t> 00096 qucs::hash<type_t>::~hash () { 00097 for (int n = 0; n < buckets; n++) { 00098 delete table[n]; 00099 } 00100 free (table); 00101 } 00102 00103 /* Clears the hash table. Afterwards it does not contain any key. 00104 The hash table is also shrunken to a minimal size. */ 00105 template <class type_t> 00106 void qucs::hash<type_t>::clear (void) { 00107 for (int n = 0; n < buckets; n++) { 00108 delete table[n]; 00109 } 00110 free (table); 00111 00112 // reinitialize the hash table 00113 buckets = HASH_MIN_SIZE; 00114 fill = 0; 00115 keys = 0; 00116 table = (hashbucket<type_t> **) 00117 calloc (buckets, sizeof (hashbucket<type_t> *)); 00118 } 00119 00120 // Returns number of items in the hash. 00121 template <class type_t> 00122 int qucs::hash<type_t>::count (void) { 00123 return keys; 00124 } 00125 00126 /* Rebuilds a hash table. Double (type is HASH_EXPAND) its size and 00127 expand the hash codes or half (type is HASH_SHRINK) its size and 00128 shrink the hash codes if these would be placed somewhere else. */ 00129 template <class type_t> 00130 void qucs::hash<type_t>::rehash (int type) { 00131 int n, e; 00132 hashbucket<type_t> * bucket, * next; 00133 00134 // Expand! 00135 if (type == HASH_EXPAND) { 00136 // Reallocate and initialize the hash table itself. 00137 buckets *= 2; 00138 table = (hashbucket<type_t> **) 00139 realloc (table, sizeof (hashbucket<type_t> *) * buckets); 00140 for (n = buckets / 2; n < buckets; n++) { table[n] = NULL; } 00141 00142 /* Go through all hash table entries and check if it is necessary 00143 to relocate them. */ 00144 for (n = 0; n < buckets / 2; n++){ 00145 bucket = table[n]; 00146 for (e = 0; bucket && e < bucket->size; e++) { 00147 int loc = HASH_LOCATION (bucket->entry[e]->code); 00148 if (n != loc) { 00149 /* copy this entry to the far entry */ 00150 if ((next = table[loc]) == NULL) { 00151 next = new hashbucket<type_t> (); 00152 table[loc] = next; 00153 } 00154 next->add (bucket->entry[e]); 00155 if (next->size == 1) fill++; 00156 /* delete this entry */ 00157 bucket->del (e); 00158 if (bucket->size == 0) fill--; 00159 e--; 00160 } 00161 } 00162 } 00163 } 00164 // Shrink! 00165 else if (type == HASH_SHRINK && buckets > HASH_MIN_SIZE) { 00166 buckets /= 2; 00167 for (n = buckets; n < buckets * 2; n++) { 00168 bucket = table[n]; 00169 if (bucket && bucket->size) { 00170 for (e = 0; e < bucket->size; e++) { 00171 int loc = HASH_LOCATION (bucket->entry[e]->code); 00172 if ((next = table[loc]) == NULL) { 00173 next = new hashbucket<type_t> (); 00174 } 00175 next->add (bucket->entry[e]); 00176 if (next->size == 1) fill++; 00177 } 00178 delete bucket; 00179 } 00180 fill--; 00181 } 00182 table = (hashbucket<type_t> **) 00183 realloc (table, sizeof (hashbucket<type_t> *) * buckets); 00184 } 00185 } 00186 00187 /* This function adds a new element consisting of key and value to an 00188 existing hash. If the hash is 75% filled it gets rehashed (size 00189 will be doubled). When the key already exists then the value just 00190 gets replaced dropping and returning the old value. */ 00191 template <class type_t> 00192 type_t * qucs::hash<type_t>::put (char * key, type_t * value) { 00193 int code = this->code (key); 00194 hashbucket<type_t> * bucket = table[HASH_LOCATION (code)]; 00195 00196 /* Check if the key is already stored. If so replace the value. */ 00197 if (bucket) { 00198 for (int e = 0; e < bucket->size; e++) { 00199 if (bucket->entry[e]->code == code) { 00200 if (equals (bucket->entry[e]->key, key) == 0) { 00201 type_t * old = bucket->entry[e]->value; 00202 bucket->entry[e]->value = value; 00203 return old; 00204 } 00205 } 00206 } 00207 } 00208 else { 00209 bucket = new hashbucket<type_t> (); 00210 table[HASH_LOCATION (code)] = bucket; 00211 } 00212 00213 /* Fill this entry. */ 00214 hashentry<type_t> * entry = new hashentry<type_t> (); 00215 entry->key = (char *) malloc (keylen (key)); 00216 memcpy (entry->key, key, keylen (key)); 00217 entry->value = value; 00218 entry->code = code; 00219 00220 bucket->add (entry); 00221 keys++; 00222 00223 /* 75% filled ? */ 00224 if (bucket->size == 1) { 00225 fill++; 00226 if (fill > HASH_EXPAND_LIMIT) { 00227 rehash (HASH_EXPAND); 00228 } 00229 } 00230 return NULL; 00231 } 00232 00233 /* Delete an existing hash entry accessed via a given key form the 00234 hash table. Return NULL if the key has not been found within the 00235 hash, otherwise the previous value. */ 00236 template <class type_t> 00237 type_t * qucs::hash<type_t>::del (char * key) { 00238 type_t * value; 00239 int code = this->code (key); 00240 hashbucket<type_t> * bucket = table[HASH_LOCATION (code)]; 00241 if (bucket) { 00242 for (int n = 0; n < bucket->size; n++) { 00243 if (bucket->entry[n]->code == code) { 00244 if (equals (bucket->entry[n]->key, key) == 0) { 00245 value = bucket->entry[n]->value; 00246 bucket->del (n); 00247 if (bucket->size == 0) { 00248 fill--; 00249 if (fill < HASH_SHRINK_LIMIT) { 00250 rehash (HASH_SHRINK); 00251 } 00252 } 00253 keys--; 00254 return value; 00255 } 00256 } 00257 } 00258 } 00259 return NULL; 00260 } 00261 00262 /* Hash table lookup. Find a value for a given key in the hash table. 00263 Return NULL if the key has not been found within the hash table. */ 00264 template <class type_t> 00265 type_t * qucs::hash<type_t>::get (char * key) { 00266 int code = this->code (key); 00267 hashbucket<type_t> * bucket = table[HASH_LOCATION (code)]; 00268 if (bucket) { 00269 for (int n = 0; n < bucket->size; n++) { 00270 if (bucket->entry[n]->code == code) 00271 if (equals (bucket->entry[n]->key, key) == 0) 00272 return bucket->entry[n]->value; 00273 } 00274 } 00275 return NULL; 00276 } 00277 00278 // Constructor for hash table iterator. 00279 template <class type_t> 00280 hashiterator<type_t>::hashiterator (hash<type_t> & h) { 00281 _hash = &h; 00282 _bucket = 0; 00283 _entry = 0; 00284 toLast (); 00285 toFirst (); 00286 } 00287 00288 // Default constructor for hash table iterator. 00289 template <class type_t> 00290 hashiterator<type_t>::hashiterator () { 00291 _hash = NULL; 00292 _bucket = 0; 00293 _entry = 0; 00294 _first = _last = _current = NULL; 00295 } 00296 00297 // Destructor for hash table iterator. 00298 template <class type_t> 00299 hashiterator<type_t>::~hashiterator () { 00300 } 00301 00302 // Returns number of items this iterator operates on. 00303 template <class type_t> 00304 int hashiterator<type_t>::count (void) { 00305 return _hash->keys; 00306 } 00307 00308 // Sets the current to the first item in the iterator list. 00309 template <class type_t> 00310 char * hashiterator<type_t>::toFirst (void) { 00311 for (int n = 0; n < _hash->buckets; n++) { 00312 hashbucket<type_t> * bucket = _hash->table[n]; 00313 if (bucket && bucket->size) { 00314 _bucket = n; 00315 _entry = 0; 00316 _current = _first = bucket->entry[_entry]; 00317 return _current->key; 00318 } 00319 } 00320 _current = _first = NULL; 00321 return NULL; 00322 } 00323 00324 // Sets the current to the last item in the iterator list. 00325 template <class type_t> 00326 char * hashiterator<type_t>::toLast (void) { 00327 for (int n = _hash->buckets - 1; n >= 0; n--) { 00328 hashbucket<type_t> * bucket = _hash->table[n]; 00329 if (bucket && bucket->size) { 00330 _bucket = n; 00331 _entry = bucket->size - 1; 00332 _current = _last = bucket->entry[_entry]; 00333 return _current->key; 00334 } 00335 } 00336 _current = _last = NULL; 00337 return NULL; 00338 } 00339 00340 // Makes the succeeding item current and returns the new current item. 00341 template <class type_t> 00342 char * hashiterator<type_t>::operator++ (void) { 00343 hashbucket<type_t> * bucket = _hash->table[_bucket]; 00344 if (bucket && _entry < bucket->size - 1) { 00345 _entry++; 00346 _current = bucket->entry[_entry]; 00347 return _current->key; 00348 } 00349 for (int n = _bucket + 1; n < _hash->buckets; n++) { 00350 bucket = _hash->table[n]; 00351 if (bucket && bucket->size) { 00352 _bucket = n; 00353 _entry = 0; 00354 _current = bucket->entry[_entry]; 00355 return _current->key; 00356 } 00357 } 00358 _current = NULL; 00359 return NULL; 00360 } 00361 00362 // Makes the preceding item current and returns the new current item. 00363 template <class type_t> 00364 char * hashiterator<type_t>::operator-- (void) { 00365 hashbucket<type_t> * bucket = _hash->table[_bucket]; 00366 if (bucket && _entry > 0) { 00367 _entry--; 00368 _current = bucket->entry[_entry]; 00369 return _current->key; 00370 } 00371 for (int n = _bucket - 1; n >= 0 ; n--) { 00372 bucket = _hash->table[n]; 00373 if (bucket && bucket->size) { 00374 _bucket = n; 00375 _entry = bucket->size - 1; 00376 _current = bucket->entry[_entry]; 00377 return _current->key; 00378 } 00379 } 00380 _current = NULL; 00381 return NULL; 00382 } 00383 00384 // Returns the current iterator item. 00385 template <class type_t> 00386 char * hashiterator<type_t>::current (void) { 00387 return _current ? _current->key : NULL; 00388 } 00389 00390 // Returns the current iterator items key. 00391 template <class type_t> 00392 char * hashiterator<type_t>::currentKey (void) { 00393 return current (); 00394 } 00395 00396 // Returns the current iterator items value. 00397 template <class type_t> 00398 type_t * hashiterator<type_t>::currentVal (void) { 00399 return _current ? _current->value : NULL; 00400 } 00401 00402 // Returns the first iterator item. 00403 template <class type_t> 00404 char * hashiterator<type_t>::first (void) { 00405 return _first ? _first->key : NULL; 00406 } 00407 00408 // Returns the last iterator item. 00409 template <class type_t> 00410 char * hashiterator<type_t>::last (void) { 00411 return _last ? _last->key : NULL; 00412 }