![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to HashTable.m CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple Darwin 0.x] / objc|
Return to HashTable.m CVS log | Up to [Apple Darwin 0.x] / objc |
1.1 root 1: /*
2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * "Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7: * Reserved. This file contains Original Code and/or Modifications of
8: * Original Code as defined in and that are subject to the Apple Public
9: * Source License Version 1.0 (the 'License'). You may not use this file
10: * except in compliance with the License. Please obtain a copy of the
11: * License at http://www.apple.com/publicsource and read it before using
12: * this file.
13: *
14: * The Original Code and all software distributed under the License are
15: * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19: * License for the specific language governing rights and limitations
20: * under the License."
21: *
22: * @APPLE_LICENSE_HEADER_END@
23: */
24: /*
25: HashTable.m
26: Copyright 1988, 1989 NeXT, Inc.
27: Written by Bertrand Serlet, Dec 88
28: Responsibility: Bertrand Serlet
29: */
30:
31: #ifdef SHLIB
32: #import "shlib.h"
33: #endif SHLIB
34:
35: #import <stdlib.h>
36: #import <stdio.h>
37: #import <string.h>
38: #import "HashTable.h"
39: #import "NXStringTable.h"
40: #import "objc-private.h"
41:
42: typedef struct {const void *key; void *value;} Pair;
43: typedef Pair *Pairs;
44: typedef struct {unsigned count; Pairs pairs;} Bucket;
45: typedef Bucket *Buckets;
46:
47: #define INITCAPA 1 /* _nbBuckets has to be a 2**N-1, and at least 1 */
48: #define PAIRSSIZE(count) ((count) * sizeof(Pair))
49: #define HASHSTR(str) (_objc_strhash (str))
50: #define HASHINT(x) ((((unsigned) x) >> 16) ^ ((unsigned) x))
51:
52: static unsigned log2 (unsigned x) { return (x<2) ? 0 : log2 (x>>1)+1; };
53:
54: static unsigned exp2m1 (unsigned x) { return (1 << x) - 1; };
55:
56: static unsigned hash (const char *keyDesc, const void *aKey, unsigned mod) {
57: switch (keyDesc[0]) {
58: case '@': return [(id) aKey hash] % mod;
59: case '%':
60: case '*': return aKey ? HASHSTR (aKey) % mod : 0;
61: default: return HASHINT (aKey) % mod;
62: };
63: };
64:
65: static unsigned isEqual (const char *keyDesc, const void *key1, const void *key2) {
66: if (key1 == key2) return YES;
67: switch (keyDesc[0]) {
68: case '@': return [(id) key1 isEqual: (id) key2];
69: case '%':
70: case '*':
71: if (! key1) return (strlen (key2) == 0);
72: if (! key2) return (strlen (key1) == 0);
73: if (((char *) key1)[0] != ((char *) key2)[0]) return NO;
74: return (strcmp (key1, key2) == 0);
75: default: return NO;
76: };
77: };
78:
79: static void freeObject (void *item) {
80: [(id) item free];
81: };
82:
83: static void noFree (void *item) {
84: };
85:
86: @implementation HashTable
87:
88: + initialize
89: {
90: [self setVersion: 1];
91: return self;
92: }
93:
94: - _initBare: (const char *) aKeyDesc : (const char *) aValueDesc : (unsigned) capacity
95: /* used for efficient implementation of rehashing: does create a semi ok table */
96: {
97: count = 0; _nbBuckets = capacity;
98: keyDesc = (aKeyDesc) ? aKeyDesc : "@";
99: valueDesc = (aValueDesc) ? aValueDesc : "@";
100: _buckets = nil;
101: return self;
102: }
103:
104: + _newBare: (const char *) aKeyDesc : (const char *) aValueDesc : (unsigned) capacity
105: /* used for efficient implementation of rehashing: does create a semi ok table */
106: {
107: return [[self allocFromZone: NXDefaultMallocZone()]
108: _initBare:aKeyDesc:aValueDesc:capacity];
109: }
110:
111: - initKeyDesc: (const char *) aKeyDesc valueDesc: (const char *) aValueDesc
112: {
113: return [self initKeyDesc: aKeyDesc valueDesc: aValueDesc capacity: INITCAPA];
114: }
115:
116: - initKeyDesc: (const char *) aKeyDesc
117: {
118: return [self initKeyDesc: aKeyDesc valueDesc: NULL];
119: }
120:
121: - init
122: {
123: return [self initKeyDesc: NULL];
124: }
125: - initKeyDesc: (const char *) aKeyDesc valueDesc: (const char *) aValueDesc capacity: (unsigned) aCapacity
126: {
127: [self _initBare: aKeyDesc: aValueDesc: exp2m1 (log2 (aCapacity)+1)];
128: _buckets = NXZoneCalloc ([self zone], _nbBuckets, sizeof(Bucket));
129: return self;
130: }
131:
132: + newKeyDesc: (const char *) aKeyDesc valueDesc: (const char *) aValueDesc capacity: (unsigned) aCapacity
133: {
134: return [[self allocFromZone: NXDefaultMallocZone()]
135: initKeyDesc:aKeyDesc valueDesc:aValueDesc capacity:aCapacity];
136: }
137:
138: + newKeyDesc: (const char *) aKeyDesc valueDesc: (const char *) aValueDesc
139: {
140: return [self newKeyDesc: aKeyDesc valueDesc: aValueDesc capacity: INITCAPA];
141: }
142:
143: + newKeyDesc: (const char *) aKeyDesc
144: {
145: return [self newKeyDesc: aKeyDesc valueDesc: NULL];
146: }
147:
148: + new
149: {
150: return [self newKeyDesc: NULL];
151: }
152:
153: - free {
154: [self freeKeys: noFree values: noFree];
155: free(_buckets);
156: return [super free];
157: }
158:
159: - freeObjects {
160: return [self
161: freeKeys: (keyDesc[0] == '@') ? freeObject : noFree
162: values: (valueDesc[0] == '@') ? freeObject : noFree
163: ];
164: }
165:
166: - freeKeys: (void (*) (void *)) keyFunc values: (void (*) (void *)) valueFunc {
167: unsigned i = _nbBuckets;
168: Buckets buckets = (Buckets) _buckets;
169: while (i--) {
170: if (buckets->count) {
171: unsigned j = buckets->count;
172: Pairs pairs = buckets->pairs;
173: while (j--) {
174: (*keyFunc) ((void *) pairs->key);
175: (*valueFunc) (pairs->value);
176: pairs++;
177: };
178: free(buckets->pairs);
179: buckets->count = 0;
180: buckets->pairs = (Pairs) nil;
181: };
182: buckets++;
183: };
184: count = 0;
185: return self;
186: };
187:
188: - empty
189: {
190: unsigned i = _nbBuckets;
191: Buckets buckets = (Buckets) _buckets;
192: while (i--) {
193: if (buckets->count) free(buckets->pairs);
194: buckets->count = 0;
195: buckets->pairs = NULL;
196: buckets++;
197: };
198: count = 0;
199: return self;
200: }
201:
202:
203: - copyFromZone:(NXZone *)zone
204: /* we enumerate the table instead of blind copy to create a hash table of the right size */
205: {
206: HashTable *new = [[[self class] allocFromZone: zone]
207: initKeyDesc: keyDesc
208: valueDesc: valueDesc
209: capacity: count];
210: NXHashState state = [self initState];
211: const void *key;
212: void *value;
213: while ([self nextState: &state key: &key value: &value])
214: [new insertKey: key value: value];
215: return new;
216: }
217:
218: - (unsigned) count
219: {
220: return count;
221: }
222:
223: - (BOOL) isKey: (const void *) aKey
224: {
225: Buckets buckets = (Buckets) _buckets;
226: unsigned index = hash (keyDesc, aKey, _nbBuckets);
227: Bucket bucket = buckets[index];
228: unsigned j = bucket.count;
229: Pairs pairs;
230: if (j == 0) return NO;
231: pairs = bucket.pairs;
232: while (j--) {
233: if (isEqual (keyDesc, aKey, pairs->key)) return YES;
234: pairs++;
235: };
236: return NO;
237: }
238:
239: - (void *) valueForKey: (const void *) aKey
240: {
241: Buckets buckets = (Buckets) _buckets;
242: unsigned index = hash (keyDesc, aKey, _nbBuckets);
243: Bucket bucket = buckets[index];
244: unsigned j = bucket.count;
245: Pairs pairs;
246: if (j == 0) return nil;
247: pairs = bucket.pairs;
248: while (j--) {
249: if (isEqual (keyDesc, aKey, pairs->key)) return pairs->value;
250: pairs++;
251: };
252: return nil;
253: }
254:
255: - (void *) _insertKeyNoRehash: (const void *) aKey value: (void *) aValue
256: {
257: Buckets buckets = (Buckets) _buckets;
258: unsigned index = hash (keyDesc, aKey, _nbBuckets);
259: Bucket bucket = buckets[index];
260: unsigned j = bucket.count;
261: Pairs pairs = bucket.pairs;
262: Pairs new;
263: while (j--) {
264: if (isEqual (keyDesc, aKey, pairs->key)) {
265: void *old = pairs->value;
266: pairs->key = aKey;
267: pairs->value = aValue;
268: return old;
269: };
270: pairs++;
271: };
272: /* we enlarge this bucket; this could be optimized by using realloc */
273: new = (Pairs) NXZoneMalloc ([self zone], PAIRSSIZE(bucket.count+1));
274: if (bucket.count) bcopy (bucket.pairs, new+1, PAIRSSIZE(bucket.count));
275: new->key = aKey; new->value = aValue;
276: if (bucket.count) free (bucket.pairs);
277: buckets[index].count++; buckets[index].pairs = new; count++;
278: return nil;
279: }
280:
281: - (void *) insertKey: (const void *) aKey value: (void *) aValue
282: {
283: void *result = [self _insertKeyNoRehash: aKey value: aValue];
284: if (result) return result; /* it was a replace */
285: if (count > _nbBuckets) {
286: /* Rehash: we create a pseudo table pointing really to the old guys,
287: extend self, copy the old pairs, and free the pseudo table */
288: HashTable * old = [[HashTable allocFromZone: [self zone]]
289: _initBare: keyDesc: valueDesc: _nbBuckets];
290: NXHashState state;
291: const void *key;
292: void *value;
293:
294: old->count = count; old->_buckets = _buckets;
295: _nbBuckets += _nbBuckets + 1;
296: count = 0;
297: _buckets = NXZoneCalloc ([self zone], _nbBuckets, sizeof(Bucket));
298: state = [old initState];
299: while ([old nextState: &state key: &key value: &value])
300: [self insertKey: key value: value];
301: #ifndef KERNEL
302: if (old->count != count)
303: _NXLogError("*** HashTable: count differs after rehashing; probably indicates a broken invariant: there are x and y such as isEqual(x, y) is TRUE but hash(x) != hash (y)\n");
304: #endif /* KERNEL */
305: [old free];
306: };
307: return nil;
308: }
309:
310: - (void *) removeKey: (const void *) aKey
311: {
312: Buckets buckets = (Buckets) _buckets;
313: unsigned index = hash (keyDesc, aKey, _nbBuckets);
314: Bucket bucket = buckets[index];
315: unsigned j = bucket.count;
316: Pairs pairs = bucket.pairs;
317: Pairs new;
318: while (j--) {
319: if (isEqual (keyDesc, aKey, pairs->key)) {
320: /* we shrink this bucket; this could be optimized by using realloc */
321: void *oldValue = pairs->value;
322: new = (bucket.count-1) ? (Pairs) NXZoneMalloc (
323: [self zone], PAIRSSIZE(bucket.count-1)) : 0;
324: if (bucket.count-1 != j)
325: bcopy (bucket.pairs, new, PAIRSSIZE(bucket.count-j-1));
326: if (j)
327: bcopy (bucket.pairs+bucket.count-j, new+bucket.count-j-1,PAIRSSIZE (j));
328: free (bucket.pairs);
329: count--; buckets[index].count--; buckets[index].pairs = new;
330: return oldValue;
331: };
332: pairs++;
333: };
334: return nil;
335: }
336:
337: - (NXHashState) initState {
338: NXHashState state;
339: state.i = _nbBuckets;
340: state.j = 0;
341: return state;
342: };
343:
344: - (BOOL) nextState: (NXHashState *) aState key: (const void **) aKey value: (void **) aValue
345: {
346: Buckets buckets = (Buckets) _buckets;
347: Pair pair;
348: while (aState->j == 0) {
349: if (aState->i == 0)
350: {
351: *aKey = NULL; *aValue = NULL;
352: return NO;
353: }
354: aState->i--; aState->j = buckets[aState->i].count;
355: }
356: aState->j--;
357: pair = buckets[aState->i].pairs[aState->j];
358: *aKey = pair.key; *aValue = pair.value;
359: return YES;
360: }
361:
362: #ifndef KERNEL
363: - write:(NXTypedStream *) stream
364: {
365: NXHashState state = [self initState];
366: const void *key;
367: void *value;
368: [super write: stream];
369: NXWriteTypes (stream, "i%%", &count, &keyDesc, &valueDesc);
370: while ([self nextState: &state key: &key value: &value]) {
371: NXWriteType (stream, keyDesc, &key);
372: NXWriteType (stream, valueDesc, &value);
373: };
374: return self;
375: }
376:
377: - read:(NXTypedStream *) stream
378: {
379: unsigned nb; /* we set count as 0 but read nb elements */
380: if (NXTypedStreamClassVersion (stream, "HashTable") == 0) {
381: NXReadTypes (stream, "i**", &nb, &keyDesc, &valueDesc);
382: } else {
383: [super read: stream];
384: NXReadTypes (stream, "i%%", &nb, &keyDesc, &valueDesc);
385: }
386: if (! keyDesc) exit (1);
387: if (! valueDesc) exit (2);
388: count = 0;
389: _nbBuckets = exp2m1 (log2 (nb)+1);
390: _buckets = NXZoneCalloc ([self zone], _nbBuckets, sizeof(Bucket));
391: while (nb--) {
392: const void *key;
393: void *value;
394: NXReadType (stream, keyDesc, &key);
395: NXReadType (stream, valueDesc, &value);
396: [self _insertKeyNoRehash: key value: value];
397: };
398: return self;
399: }
400: #else /* KERNEL */
401: - write:(NXTypedStream *) stream
402: {
403: return nil;
404: }
405: - read:(NXTypedStream *) stream
406: {
407: return nil;
408: }
409: #endif /* KERNEL */
410:
411: static void DebugPrint (NXStream *stream, const char *desc, const void *data) {
412: switch (desc[0]) {
413: case '@':
414: NXPrintf (stream, "%s[0x%x]", [(id) data name], (int) data);
415: return;
416: case 'i':
417: NXPrintf (stream, "%d[0x%x]", (int) data, (int) data);
418: return;
419: case '%':
420: case '*':
421: NXPrintf (stream, "\"%s\"", (char *) data);
422: return;
423: default:
424: NXPrintf (stream, "0x%x", (int) data);
425: return;
426: };
427: };
428:
429: - (void) printForDebugger:(NXStream *)stream
430: {
431: unsigned i = _nbBuckets;
432: Buckets buckets = (Buckets) _buckets;
433:
434: NXPrintf (stream, "Table [%s -> %s]: \tcount: %d\tcapacity: %d\n",
435: keyDesc, valueDesc, count, _nbBuckets);
436: while (i--) {
437: if (buckets->count) {
438: unsigned j = buckets->count;
439: Pairs pairs = buckets->pairs;
440:
441: NXPrintf (stream, "%d\t", j);
442: while (j--) {
443: DebugPrint (stream, keyDesc, pairs->key);
444: NXPrintf (stream, ": ");
445: DebugPrint (stream, valueDesc, pairs->value);
446: NXPrintf (stream, "\t");
447: pairs++;
448: };
449: NXPrintf (stream, "\n");
450: };
451: buckets++;
452: };
453: NXPrintf (stream, "\n");
454: NXFlush (stream);
455: }
456:
457: /* Obsolete (for binary compatibility only). */
458:
459: - _debugPrint: (NXStream *) stream
460: {
461: [self printForDebugger: stream];
462: return self;
463: }
464:
465: @end
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.