Qucs-core  0.0.19
hash.h
Go to the documentation of this file.
00001 /*
00002  * hash.h - hash function interface
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 #ifndef __HASH_H__
00026 #define __HASH_H__
00027 
00028 namespace qucs {
00029 
00030 /* Useful defines. */
00031 #define HASH_SHRINK         4
00032 #define HASH_EXPAND         8
00033 #define HASH_MIN_SIZE       4
00034 #define HASH_SHRINK_LIMIT   (buckets >> 2)
00035 #define HASH_EXPAND_LIMIT   ((buckets >> 1) + (buckets >> 2))
00036 #define HASH_LOCATION(code) ((code) & (buckets - 1))
00037 
00038 template <class type_t> class hashentry;
00039 template <class type_t> class hashbucket;
00040 template <class type_t> class hash;
00041 template <class type_t> class hashiterator;
00042 
00043 /* This is the basic structure of a hash entry consisting of its key,
00044    the actual value stored in the hash table and the hash code of the
00045    key. */
00046 template <class type_t>
00047 class hashentry
00048 {
00049   friend class hashiterator<type_t>;
00050   friend class hashbucket<type_t>;
00051   friend class hash<type_t>;
00052 
00053  public:
00054   hashentry () {  // Constructor.
00055     code = 0; key = NULL; value = NULL;
00056   }
00057   ~hashentry () { // Destructor.
00058     free (key);
00059   }
00060 
00061  private:
00062   int code;       // Hash code.
00063   char * key;     // Hash key.
00064   type_t * value; // Hash value.
00065 };
00066 
00067 /* The hash table consists of different hash buckets.  This contains
00068    the bucket's size and the entry array.  */
00069 template <class type_t>
00070 class hashbucket
00071 {
00072   friend class hashiterator<type_t>;
00073   friend class hash<type_t>;
00074 
00075  public:
00076   hashbucket () {  // Constructor.
00077     capacity = size = 0;
00078     entry = NULL;
00079   }
00080   ~hashbucket () { // Destructor.
00081     if (entry) {
00082       for (int n = 0; n < size; n++) delete entry[n];
00083       free (entry);
00084     }
00085   }
00086 
00087  public:
00088   // Adds an entry to the bucket.
00089   void add (hashentry<type_t> * e) {
00090     if (capacity == 0) {
00091       capacity = HASH_MIN_SIZE;
00092       entry = (hashentry<type_t> **)
00093         malloc (sizeof (hashentry<type_t> *) * capacity);
00094     }
00095     else if (size >= capacity) {
00096       capacity *= 2;
00097       entry = (hashentry<type_t> **)
00098         realloc (entry, sizeof (hashentry<type_t> *) * capacity);
00099     }
00100     entry[size++] = e;
00101   }
00102   // Removes an entry from the bucket.
00103   void del (int idx) {
00104     size--;
00105     if (idx != size) entry[idx] = entry[size];
00106   }
00107 
00108  private:
00109   int capacity;               // The capacity of the bucket.
00110   int size;                   // The current size.
00111   hashentry<type_t> ** entry; // Hash entry table.
00112 };
00113 
00114 
00115 /* This structure keeps information of a specific hash table.  */
00116 template <class type_t>
00117 class hash
00118 {
00119   friend class hashiterator<type_t>;
00120 
00121  public:
00122   hash (int size = HASH_MIN_SIZE);
00123   ~hash ();
00124 
00125   int  count (void);
00126   void clear (void);
00127   void rehash (int);
00128   type_t * put (char *, type_t *);
00129   type_t * get (char *);
00130   type_t * del (char *);
00131 
00132  private:
00133   int buckets;
00134   int fill;
00135   int keys;
00136   int (* equals) (char *, char *);
00137   int (* code) (char *);
00138   unsigned (* keylen) (char *);
00139   hashbucket<type_t> ** table;
00140 };
00141 
00142 /* Definition of the hash table iterator.  */
00143 template <class type_t>
00144 class hashiterator
00145 {
00146  public:
00147   hashiterator ();
00148   hashiterator (hash<type_t> &);
00149   ~hashiterator ();
00150 
00151   int count (void);
00152   char * toFirst (void);
00153   char * toLast (void);
00154   char * operator++ (void);
00155   char * operator-- (void);
00156   char * operator * (void) { return current (); }
00157   char * current (void);
00158   char * currentKey (void);
00159   type_t * currentVal (void);
00160   char * first (void);
00161   char * last (void);
00162 
00163  private:
00164   hash<type_t> * _hash;
00165   hashentry<type_t> * _first;
00166   hashentry<type_t> * _last;
00167   hashentry<type_t> * _current;
00168   int _bucket;
00169   int _entry;
00170 };
00171 
00172 } /* namespace qucs */
00173 
00174 #include "hash.cpp"
00175 
00176 #endif /* __HASH_H__ */