Branch data Line data Source code
1 : : /*
2 : : * hash.h - hash function interface
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$
22 : : *
23 : : */
24 : :
25 : : #ifndef __HASH_H__
26 : : #define __HASH_H__
27 : :
28 : : namespace qucs {
29 : :
30 : : /* Useful defines. */
31 : : #define HASH_SHRINK 4
32 : : #define HASH_EXPAND 8
33 : : #define HASH_MIN_SIZE 4
34 : : #define HASH_SHRINK_LIMIT (buckets >> 2)
35 : : #define HASH_EXPAND_LIMIT ((buckets >> 1) + (buckets >> 2))
36 : : #define HASH_LOCATION(code) ((code) & (buckets - 1))
37 : :
38 : : template <class type_t> class hashentry;
39 : : template <class type_t> class hashbucket;
40 : : template <class type_t> class hash;
41 : : template <class type_t> class hashiterator;
42 : :
43 : : /* This is the basic structure of a hash entry consisting of its key,
44 : : the actual value stored in the hash table and the hash code of the
45 : : key. */
46 : : template <class type_t>
47 : : class hashentry
48 : : {
49 : : friend class hashiterator<type_t>;
50 : : friend class hashbucket<type_t>;
51 : : friend class hash<type_t>;
52 : :
53 : : public:
54 : 16328 : hashentry () { // Constructor.
55 : 16328 : code = 0; key = NULL; value = NULL;
56 : 16328 : }
57 : 16328 : ~hashentry () { // Destructor.
58 [ + - ]: 16328 : if (key) free (key);
59 : 16328 : }
60 : :
61 : : private:
62 : : int code; // Hash code.
63 : : char * key; // Hash key.
64 : : type_t * value; // Hash value.
65 : : };
66 : :
67 : : /* The hash table consists of different hash buckets. This contains
68 : : the bucket's size and the entry array. */
69 : : template <class type_t>
70 : : class hashbucket
71 : : {
72 : : friend class hashiterator<type_t>;
73 : : friend class hash<type_t>;
74 : :
75 : : public:
76 : 10920 : hashbucket () { // Constructor.
77 : 10920 : capacity = size = 0;
78 : 10920 : entry = NULL;
79 : 10920 : }
80 : 10920 : ~hashbucket () { // Destructor.
81 [ + - ]: 10920 : if (entry) {
82 [ + - ][ + + ]: 27248 : for (int n = 0; n < size; n++) delete entry[n];
83 : 10920 : free (entry);
84 : : }
85 : 10920 : }
86 : :
87 : : public:
88 : : // Adds an entry to the bucket.
89 : 27664 : void add (hashentry<type_t> * e) {
90 [ + + ]: 27664 : if (capacity == 0) {
91 : 10920 : capacity = HASH_MIN_SIZE;
92 : 10920 : entry = (hashentry<type_t> **)
93 : : malloc (sizeof (hashentry<type_t> *) * capacity);
94 : : }
95 [ + + ]: 16744 : else if (size >= capacity) {
96 : 936 : capacity *= 2;
97 : 936 : entry = (hashentry<type_t> **)
98 : : realloc (entry, sizeof (hashentry<type_t> *) * capacity);
99 : : }
100 : 27664 : entry[size++] = e;
101 : 27664 : }
102 : : // Removes an entry from the bucket.
103 : 11336 : void del (int idx) {
104 : 11336 : size--;
105 [ + + ]: 11336 : if (idx != size) entry[idx] = entry[size];
106 : 11336 : }
107 : :
108 : : private:
109 : : int capacity; // The capacity of the bucket.
110 : : int size; // The current size.
111 : : hashentry<type_t> ** entry; // Hash entry table.
112 : : };
113 : :
114 : :
115 : : /* This structure keeps information of a specific hash table. */
116 : : template <class type_t>
117 : : class hash
118 : : {
119 : : friend class hashiterator<type_t>;
120 : :
121 : : public:
122 : : hash (int size = HASH_MIN_SIZE);
123 : : ~hash ();
124 : :
125 : : int count (void);
126 : : void clear (void);
127 : : void rehash (int);
128 : : type_t * put (char *, type_t *);
129 : : type_t * get (char *);
130 : : type_t * del (char *);
131 : :
132 : : private:
133 : : int buckets;
134 : : int fill;
135 : : int keys;
136 : : int (* equals) (char *, char *);
137 : : int (* code) (char *);
138 : : unsigned (* keylen) (char *);
139 : : hashbucket<type_t> ** table;
140 : : };
141 : :
142 : : /* Definition of the hash table iterator. */
143 : : template <class type_t>
144 : : class hashiterator
145 : : {
146 : : public:
147 : : hashiterator ();
148 : : hashiterator (hash<type_t> &);
149 : : ~hashiterator ();
150 : :
151 : : int count (void);
152 : : char * toFirst (void);
153 : : char * toLast (void);
154 : : char * operator++ (void);
155 : : char * operator-- (void);
156 : 32864 : char * operator * (void) { return current (); }
157 : : char * current (void);
158 : : char * currentKey (void);
159 : : type_t * currentVal (void);
160 : : char * first (void);
161 : : char * last (void);
162 : :
163 : : private:
164 : : hash<type_t> * _hash;
165 : : hashentry<type_t> * _first;
166 : : hashentry<type_t> * _last;
167 : : hashentry<type_t> * _current;
168 : : int _bucket;
169 : : int _entry;
170 : : };
171 : :
172 : : } /* namespace qucs */
173 : :
174 : : #include "hash.cpp"
175 : :
176 : : #endif /* __HASH_H__ */
|
