Qucs-core
0.0.19
|
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__ */