Debian Codegraph @

xo/lhash.cxx

raw
1 /* lhash.cxx
2 $Id: lhash.cxx,v 1.4 1997/10/18 04:57:35 elf Exp $
3
4 written by Marc Singer
5 15 October 1997
6
7 This file is part of the project XO. See the file README for
8 more information.
9
10 Copyright (C) 1997 Marc Singer
11
12 This program is free software; you can redistribute it and/or
13 modify it under the terms of the GNU General Public License as
14 published by the Free Software Foundation; either version 2 of the
15 License, or (at your option) any later version.
16
17 This program is distributed in the hope that it will be useful, but
18 WITHOUT ANY WARRANTY; without even the implied warranty of
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20 General Public License for more details.
21
22 You should have received a copy of the GNU General Public License
23 in a file called COPYING along with this program; if not, write to
24 the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA
25 02139, USA.
26
27 */
28
29 /* ----- Includes */
30
31 #include "standard.h"
32
33 #include <ctype.h>
34
35 #include "lhash.h"
36
37 /* ----- Class Globals/Statics */
38
39 /* ----- Methods */
40
41
42 bool LHashBucket::add (HashKey key, const void* pv)
43 {
44 int i = _find (key);
45
46 // -- Add new entry
47 if (i == -1)
48 return m_pArrayKey->add (&key)
49 && m_pArrayItem->add (pv);
50
51 // -- Replace old entry
52 void* pvItem = m_pArrayItem->reference (i);
53 if (pvItem)
54 memcpy (pvItem, pv, m_cbEach);
55 return pvItem != NULL;
56 } /* LHashBucket::add */
57
58
59 /* LHashBucket::_find
60
61 performs the internal lookup within a bucket. We do a simple
62 linear search of the items in the list. The return value is the
63 index of the item or -1 if the key cannot be found.
64
65 */
66
67 int LHashBucket::_find (HashKey key)
68 {
69 if (!is_init ())
70 return -1;
71
72 int i = 0;
73 for (HashKey* pKey = NULL;
74 pKey = (HashKey*) m_pArrayKey->enumerate ((void*) pKey); ++i)
75 if (*pKey == key)
76 return i;
77 return -1;
78 } /* LHashBucket::_find */
79
80 bool LHashBucket::find (HashKey key, void* pv)
81 {
82 int i = _find (key);
83 if (i == -1)
84 return false;
85 return m_pArrayItem->get (i, pv);
86 } /* LHashBucket::find */
87
88
89 void* LHashBucket::find (HashKey key)
90 {
91 int i = _find (key);
92 if (i == -1)
93 return NULL;
94 return m_pArrayItem->reference (i);
95 } /* LHashBucket::find */
96
97
98 void LHashBucket::init (int cbEach)
99 {
100 release_all ();
101 m_cbEach = cbEach;
102 m_pArrayItem = new LArray (cbEach);
103 m_pArrayKey = new LArray (sizeof (HashKey));
104 } /* LHashBucket::init */
105
106 void LHashBucket::release_all (void)
107 {
108 if (m_pArrayKey)
109 delete m_pArrayKey;
110 m_pArrayKey = NULL;
111 if (m_pArrayItem)
112 delete m_pArrayItem;
113 m_pArrayItem = NULL;
114 m_cbEach = 0;
115 } /* LHashBucket::release_all */
116
117 bool LHashBucket::remove (HashKey key)
118 {
119 int i = _find (key);
120
121 if (i == -1)
122 return false;
123
124 m_pArrayKey->remove (i);
125 m_pArrayItem->remove (i);
126 return true;
127 } /* LHashBucket::remove */
128
129
130 void LHashBucket::zero (void)
131 {
132 memset (this, 0, sizeof (*this));
133 } /* LHashBucket::zero */
134
135
136 bool LHashTable::add (HashKey key, const void* pv)
137 {
138 LHashBucket* pBucket
139 = (LHashBucket*) m_pArrayBucket->reference (bucket_of (key));
140 if (!pBucket)
141 return false;
142 if (!pBucket->is_init ())
143 pBucket->init (m_cbEach);
144 return pBucket->add (key, pv);
145 } /* LHashTable::add */
146
147
148 /* LHashTable::enumerate_reverse
149
150 enumerates all keys in the hash table. It is called _reverse
151 because it uses to the same technique as LArray::enumerate_reverse
152 that guarantees that deleted items during the enumeration will not
153 affect the completeness of the coverage.
154
155 The unsigned32 index controls the enumeration. For the first call,
156 pass index as zero. On subsequent calls, pass the index as
157 returned from the previous call. The return value is zero when
158 enumeration is complete.
159
160 */
161
162 unsigned32 LHashTable::enumerate_reverse (unsigned32 index, HashKey* pKey,
163 const void** ppv)
164 {
165 LHashBucket* pBucket;
166 unsigned iBucket = HIWORD (index);
167 unsigned long iKey = LOWORD (index) - 1;
168
169 // -- Initial case
170 if (index == 0) {
171 iBucket = m_cBuckets;
172 iKey = 0;
173 } /* if */
174
175 // -- Iteration across bucket boundary
176 if (!iKey) {
177 while (iBucket--) {
178 pBucket = (LHashBucket*) m_pArrayBucket->reference (iBucket);
179 if (!pBucket || !pBucket->is_init ())
180 continue;
181 iKey = pBucket->get_count ();
182 break;
183 } /* while */
184 if (!iKey)
185 return 0;
186 } /* if */
187
188 --iKey;
189 pBucket = (LHashBucket*) m_pArrayBucket->at (iBucket);
190
191 if (pKey)
192 *pKey = pBucket->get_key (iKey);
193 if (ppv)
194 *ppv = pBucket->reference_item (iKey);
195
196 return MAKELONG (iKey + 1, iBucket);
197 } /* LHashTable::enumerate_reverse */
198
199
200 void* LHashTable::find (HashKey key)
201 {
202 LHashBucket* pBucket
203 = (LHashBucket*) m_pArrayBucket->reference (bucket_of (key));
204 return pBucket ? pBucket->find (key) : NULL;
205 } /* LHashTable::find */
206
207
208 bool LHashTable::find (HashKey key, void* pv)
209 {
210 LHashBucket* pBucket
211 = (LHashBucket*) m_pArrayBucket->reference (bucket_of (key));
212 return pBucket ? pBucket->find (key, pv) : false;
213 } /* LHashTable::find */
214
215
216 void LHashTable::init (int cbEach, int cBuckets)
217 {
218 release_all ();
219 m_cbEach = cbEach;
220 m_cBuckets = cBuckets;
221 if (!cBuckets)
222 return;
223 m_pArrayBucket = new LArray (sizeof (LHashBucket));
224 m_pArrayBucket->alloc_to (cBuckets);
225 }
226
227 HashKey LHashTable::make_string_key (const char* sz)
228 {
229 return LHashTable::make_string_key (sz, strlen (sz));
230 }
231
232
233 HashKey LHashTable::make_string_key (const char* sz, int cch)
234 {
235 unsigned long l = 0;
236
237 while (cch--) {
238 l = (l << 4) + (unsigned char)*(sz++);
239 unsigned long m = l & 0xf0000000;
240 if (m) {
241 l = l ^ (m >> 24);
242 l = l ^ m;
243 }
244 }
245 return l;
246 }
247
248
249 HashKey LHashTable::make_case_string_key (const char* sz)
250 {
251 return LHashTable::make_case_string_key (sz, strlen (sz));
252 }
253
254
255 HashKey LHashTable::make_case_string_key (const char* sz, int cch)
256 {
257 unsigned long l = 0;
258
259 while (cch--) {
260 l = (l << 4) + tolower (*(sz++));
261 unsigned long m = l & 0xf0000000;
262 if (m) {
263 l = l ^ (m >> 24);
264 l = l ^ m;
265 }
266 }
267 return l;
268 }
269
270
271 void LHashTable::release_all (void)
272 {
273 if (m_pArrayBucket) {
274 for (LHashBucket* pBucket = NULL;
275 pBucket = (LHashBucket*) m_pArrayBucket
276 ->enumerate ((void*) pBucket); )
277 pBucket->release_all ();
278 delete m_pArrayBucket;
279 m_pArrayBucket = NULL;
280 } /* if */
281 } /* LHashTable::release_all */
282
283
284 bool LHashTable::remove (HashKey key)
285 {
286 LHashBucket* pBucket
287 = (LHashBucket*) m_pArrayBucket->reference (bucket_of (key));
288 return pBucket ? pBucket->remove (key) : false;
289 } /* LHashTable::remove */
290
291
292 void LHashTable::zero (void)
293 {
294 memset (this, 0, sizeof (*this));
295 } /* LHashTable::zero */