Qucs-core  0.0.19
hash.cpp
Go to the documentation of this file.
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 }