![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to maptable.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 maptable.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: /* maptable.m
25: Copyright 1990 NeXT, Inc.
26: Created by Bertrand Serlet, August 1990
27: */
28:
29: #ifdef SHLIB
30: #import "shlib.h"
31: #endif SHLIB
32:
33: #import "objc-private.h"
34: #import "maptable.h"
35:
36: #import <string.h>
37: #import <stdlib.h>
38: #import <stdio.h>
39: #import "Object.h"
40: #import "hashtable.h"
41:
42: /****** Macros and utilities ****************************/
43:
44: #if DEBUG
45: #define INLINE
46: #else
47: #define INLINE inline
48: #endif
49:
50: typedef struct _MapPair {
51: const void *key;
52: const void *value;
53: } MapPair;
54:
55: static unsigned log2(unsigned x) { return (x<2) ? 0 : log2(x>>1)+1; };
56:
57: static INLINE unsigned exp2m1(unsigned x) { return (1 << x) - 1; };
58:
59: /* iff necessary this modulo can be optimized since the nbBuckets is of the form 2**n-1 */
60: static INLINE unsigned bucketOf(NXMapTable *table, const void *key) {
61: unsigned hash = (table->prototype->hash)(table, key);
62: unsigned xored = (hash & 0xffff) ^ (hash >> 16);
63: return ((xored * 65521) + hash) % table->nbBuckets;
64: }
65:
66: static INLINE int isEqual(NXMapTable *table, const void *key1, const void *key2) {
67: return (key1 == key2) ? 1 : (table->prototype->isEqual)(table, key1, key2);
68: }
69:
70: static INLINE unsigned nextIndex(NXMapTable *table, unsigned index) {
71: return (index+1 >= table->nbBuckets) ? 0 : index+1;
72: }
73:
74: static INLINE void *allocBuckets(NXZone *zone, unsigned nb) {
75: MapPair *pairs = NXZoneMalloc(zone, (nb * sizeof(MapPair)));
76: MapPair *pair = pairs;
77: while (nb--) { pair->key = NX_MAPNOTAKEY; pair->value = NULL; pair++; }
78: return pairs;
79: }
80:
81: /***** Global data and bootstrap **********************/
82:
83: static unsigned hashPrototype(const void *info, const void *data) {
84: NXMapTablePrototype *proto = (NXMapTablePrototype *) data;
85: return NXPtrHash(info, proto->hash) ^ NXPtrHash(info, proto->isEqual) ^ NXPtrHash(info, proto->free) ^ (unsigned) proto->style;
86: }
87:
88: static int isEqualPrototype(const void *info, const void *data1, const void *data2) {
89: NXMapTablePrototype *proto1 = (NXMapTablePrototype *) data1;
90: NXMapTablePrototype *proto2 = (NXMapTablePrototype *) data2;
91: return (proto1->hash == proto2->hash) && (proto1->isEqual == proto2->isEqual) && (proto1->free == proto2->free) && (proto1->style == proto2->style);
92: }
93:
94: static NXHashTablePrototype protoPrototype = {
95: hashPrototype, isEqualPrototype, NXNoEffectFree, 0
96: };
97:
98: static NXHashTable *prototypes = NULL;
99: /* table of all prototypes */
100:
101: /**** Fundamentals Operations **************/
102:
103: NXMapTable *NXCreateMapTableFromZone(NXMapTablePrototype prototype, unsigned capacity, NXZone *zone) {
104: NXMapTable *table = NXZoneMalloc(zone, sizeof(NXMapTable));
105: NXMapTablePrototype *proto;
106: if (! prototypes) prototypes = NXCreateHashTable(protoPrototype, 0, NULL);
107: if (! prototype.hash || ! prototype.isEqual || ! prototype.free || prototype.style) {
108: _NXLogError("*** NXCreateMapTable: invalid creation parameters\n");
109: return NULL;
110: }
111: proto = NXHashGet(prototypes, &prototype);
112: if (! proto) {
113: proto = malloc(sizeof(NXMapTablePrototype));
114: *proto = prototype;
115: (void)NXHashInsert(prototypes, proto);
116: }
117: table->prototype = proto; table->count = 0;
118: table->nbBuckets = exp2m1(log2(capacity)+1);
119: table->buckets = allocBuckets(zone, table->nbBuckets);
120: return table;
121: }
122:
123: NXMapTable *NXCreateMapTable(NXMapTablePrototype prototype, unsigned capacity) {
124: return NXCreateMapTableFromZone(prototype, capacity, NXDefaultMallocZone());
125: }
126:
127: void NXFreeMapTable(NXMapTable *table) {
128: NXResetMapTable(table);
129: free(table->buckets);
130: free(table);
131: }
132:
133: void NXResetMapTable(NXMapTable *table) {
134: MapPair *pairs = table->buckets;
135: void (*freeProc)(struct _NXMapTable *, void *, void *) = table->prototype->free;
136: unsigned index = table->nbBuckets;
137: while (index--) {
138: if (pairs->key != NX_MAPNOTAKEY) {
139: freeProc(table, (void *)pairs->key, (void *)pairs->value);
140: pairs->key = NX_MAPNOTAKEY; pairs->value = NULL;
141: }
142: pairs++;
143: }
144: table->count = 0;
145: }
146:
147: BOOL NXCompareMapTables(NXMapTable *table1, NXMapTable *table2) {
148: if (table1 == table2) return YES;
149: if (table1->count != table2->count) return NO;
150: else {
151: void *key;
152: void *value;
153: NXMapState state = NXInitMapState(table1);
154: while (NXNextMapState(table1, &state, &key, &value)) {
155: if (NXMapMember(table2, key, &value) == NX_MAPNOTAKEY) return NO;
156: }
157: return YES;
158: }
159: }
160:
161: unsigned NXCountMapTable(NXMapTable *table) { return table->count; }
162:
163: static int mapSearch = 0;
164: static int mapSearchHit = 0;
165: static int mapSearchLoop = 0;
166:
167: static INLINE void *_NXMapMember(NXMapTable *table, const void *key, void **value) {
168: MapPair *pairs = table->buckets;
169: unsigned index = bucketOf(table, key);
170: MapPair *pair = pairs + index;
171: if (pair->key == NX_MAPNOTAKEY) return NX_MAPNOTAKEY;
172: mapSearch ++;
173: if (isEqual(table, pair->key, key)) {
174: *value = (void *)pair->value;
175: mapSearchHit ++;
176: return (void *)pair->key;
177: } else {
178: unsigned index2 = index;
179: while ((index2 = nextIndex(table, index2)) != index) {
180: mapSearchLoop ++;
181: pair = pairs + index2;
182: if (pair->key == NX_MAPNOTAKEY) return NX_MAPNOTAKEY;
183: if (isEqual(table, pair->key, key)) {
184: *value = (void *)pair->value;
185: return (void *)pair->key;
186: }
187: }
188: return NX_MAPNOTAKEY;
189: }
190: }
191:
192: void *NXMapMember(NXMapTable *table, const void *key, void **value) {
193: return _NXMapMember(table, key, value);
194: }
195:
196: void *NXMapGet(NXMapTable *table, const void *key) {
197: void *value;
198: return (_NXMapMember(table, key, &value) != NX_MAPNOTAKEY) ? value : NULL;
199: }
200:
201: static int mapRehash = 0;
202: static int mapRehashSum = 0;
203:
204: static void _NXMapRehash(NXMapTable *table) {
205: MapPair *pairs = table->buckets;
206: MapPair *pair = pairs;
207: unsigned index = table->nbBuckets;
208: unsigned oldCount = table->count;
209: table->nbBuckets += table->nbBuckets + 1; /* 2 times + 1 */
210: table->count = 0;
211: table->buckets = allocBuckets(NXZoneFromPtr(table), table->nbBuckets);
212: mapRehash ++;
213: mapRehashSum += table->count;
214: while (index--) {
215: if (pair->key != NX_MAPNOTAKEY) {
216: (void)NXMapInsert(table, pair->key, pair->value);
217: }
218: pair++;
219: }
220: if (oldCount != table->count)
221: _NXLogError("*** maptable: 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");
222: free(pairs);
223: }
224:
225: static int mapInsert = 0;
226: static int mapInsertHit = 0;
227: static int mapInsertLoop = 0;
228:
229: void *NXMapInsert(NXMapTable *table, const void *key, const void *value) {
230: MapPair *pairs = table->buckets;
231: unsigned index = bucketOf(table, key);
232: MapPair *pair = pairs + index;
233: if (key == NX_MAPNOTAKEY) {
234: _NXLogError("*** NXMapInsert: invalid key: -1\n");
235: return NULL;
236: }
237: mapInsert ++;
238: if (pair->key == NX_MAPNOTAKEY) {
239: mapInsertHit ++;
240: pair->key = key; pair->value = value;
241: table->count++;
242: return NULL;
243: }
244: if (isEqual(table, pair->key, key)) {
245: const void *old = pair->value;
246: mapInsertHit ++;
247: if (old != value) pair->value = value;/* avoid writing unless needed! */
248: return (void *)old;
249: } else if (table->count == table->nbBuckets) {
250: /* no room: rehash and retry */
251: _NXMapRehash(table);
252: return NXMapInsert(table, key, value);
253: } else {
254: unsigned index2 = index;
255: while ((index2 = nextIndex(table, index2)) != index) {
256: mapInsertLoop ++;
257: pair = pairs + index2;
258: if (pair->key == NX_MAPNOTAKEY) {
259: #if INSERT_TAIL
260: pair->key = key; pair->value = value;
261: #else
262: MapPair current = {key, value};
263: index2 = index;
264: while (current.key != NX_MAPNOTAKEY) {
265: MapPair temp;
266: pair = pairs + index2;
267: temp = *pair;
268: *pair = current;
269: current = temp;
270: index2 = nextIndex(table, index2);
271: }
272: #endif
273: table->count++;
274: if (table->count * 4 > table->nbBuckets * 3) _NXMapRehash(table);
275: return NULL;
276: }
277: if (isEqual(table, pair->key, key)) {
278: const void *old = pair->value;
279: if (old != value) pair->value = value;/* avoid writing unless needed! */
280: return (void *)old;
281: }
282: }
283: /* no room: can't happen! */
284: _NXLogError("**** NXMapInsert: bug\n");
285: return NULL;
286: }
287: }
288:
289: static int mapRemove = 0;
290:
291: void *NXMapRemove(NXMapTable *table, const void *key) {
292: MapPair *pairs = table->buckets;
293: unsigned index = bucketOf(table, key);
294: MapPair *pair = pairs + index;
295: unsigned chain = 1; /* number of non-nil pairs in a row */
296: int found = 0;
297: const void *old = NULL;
298: if (pair->key == NX_MAPNOTAKEY) return NULL;
299: mapRemove ++;
300: /* compute chain */
301: {
302: unsigned index2 = index;
303: if (isEqual(table, pair->key, key)) {found ++; old = pair->value; }
304: while ((index2 = nextIndex(table, index2)) != index) {
305: pair = pairs + index2;
306: if (pair->key == NX_MAPNOTAKEY) break;
307: if (isEqual(table, pair->key, key)) {found ++; old = pair->value; }
308: chain++;
309: }
310: }
311: if (! found) return NULL;
312: if (found != 1) _NXLogError("**** NXMapRemove: incorrect table\n");
313: /* remove then reinsert */
314: {
315: MapPair buffer[16];
316: MapPair *aux = (chain > 16) ? malloc(sizeof(MapPair)*(chain-1)) : buffer;
317: int auxnb = 0;
318: int nb = chain;
319: unsigned index2 = index;
320: while (nb--) {
321: pair = pairs + index2;
322: if (! isEqual(table, pair->key, key)) aux[auxnb++] = *pair;
323: pair->key = NX_MAPNOTAKEY; pair->value = NULL;
324: index2 = nextIndex(table, index2);
325: }
326: table->count -= chain;
327: if (auxnb != chain-1) _NXLogError("**** NXMapRemove: bug\n");
328: while (auxnb--) NXMapInsert(table, aux[auxnb].key, aux[auxnb].value);
329: if (chain > 16) free(aux);
330: }
331: return (void *)old;
332: }
333:
334: NXMapState NXInitMapState(NXMapTable *table) {
335: NXMapState state;
336: state.index = table->nbBuckets;
337: return state;
338: }
339:
340: int NXNextMapState(NXMapTable *table, NXMapState *state, const void **key, const void **value) {
341: MapPair *pairs = table->buckets;
342: while (state->index--) {
343: MapPair *pair = pairs + state->index;
344: if (pair->key != NX_MAPNOTAKEY) {
345: *key = pair->key; *value = pair->value;
346: return YES;
347: }
348: }
349: return NO;
350: }
351:
352: /**** Conveniences *************************************/
353:
354: unsigned _mapPtrHash(NXMapTable *table, const void *key) {
355: return (((unsigned) key) >> 16) ^ ((unsigned) key);
356: }
357:
358: unsigned _mapStrHash(NXMapTable *table, const void *key) {
359: unsigned hash = 0;
360: unsigned char *s = (unsigned char *)key;
361: /* unsigned to avoid a sign-extend */
362: /* unroll the loop */
363: if (s) for (; ; ) {
364: if (*s == '\0') break;
365: hash ^= *s++;
366: if (*s == '\0') break;
367: hash ^= *s++ << 8;
368: if (*s == '\0') break;
369: hash ^= *s++ << 16;
370: if (*s == '\0') break;
371: hash ^= *s++ << 24;
372: }
373: return hash;
374: }
375:
376: unsigned _mapObjectHash(NXMapTable *table, const void *key) {
377: return [(id)key hash];
378: }
379:
380: int _mapPtrIsEqual(NXMapTable *table, const void *key1, const void *key2) {
381: return key1 == key2;
382: }
383:
384: int _mapStrIsEqual(NXMapTable *table, const void *key1, const void *key2) {
385: if (key1 == key2) return YES;
386: if (! key1) return ! strlen ((char *) key2);
387: if (! key2) return ! strlen ((char *) key1);
388: if (((char *) key1)[0] != ((char *) key2)[0]) return NO;
389: return (strcmp((char *) key1, (char *) key2)) ? NO : YES;
390: }
391:
392: int _mapObjectIsEqual(NXMapTable *table, const void *key1, const void *key2) {
393: return [(id)key1 isEqual:(id)key2];
394: }
395:
396: void _mapNoFree(NXMapTable *table, void *key, void *value) {}
397:
398: void _mapObjectFree(NXMapTable *table, void *key, void *value) {
399: [(id)key free];
400: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.