2 * Copyright (c) 1999-2003, 2005-2007 Apple Inc. All Rights Reserved.
4 * @APPLE_LICENSE_HEADER_START@
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
21 * @APPLE_LICENSE_HEADER_END@
24 Copyright 1990-1996 NeXT Software, Inc.
25 Created by Bertrand Serlet, August 1990
33 #include "objc-private.h"
35 #include "hashtable2.h"
38 /****** Macros and utilities ****************************/
46 typedef struct _MapPair {
51 static INLINE unsigned xorHash(unsigned hash) {
52 unsigned xored = (hash & 0xffff) ^ (hash >> 16);
53 return ((xored * 65521) + hash);
56 static INLINE unsigned bucketOf(NXMapTable *table, const void *key) {
57 unsigned hash = (table->prototype->hash)(table, key);
58 return hash & table->nbBucketsMinusOne;
61 static INLINE int isEqual(NXMapTable *table, const void *key1, const void *key2) {
62 return (key1 == key2) ? 1 : (table->prototype->isEqual)(table, key1, key2);
65 static INLINE unsigned nextIndex(NXMapTable *table, unsigned index) {
66 return (index + 1) & table->nbBucketsMinusOne;
69 static INLINE void *allocBuckets(void *z, unsigned nb) {
70 MapPair *pairs = 1+(MapPair *)malloc_zone_malloc((malloc_zone_t *)z, ((nb+1) * sizeof(MapPair)));
71 MapPair *pair = pairs;
72 while (nb--) { pair->key = NX_MAPNOTAKEY; pair->value = NULL; pair++; }
76 static INLINE void freeBuckets(void *p) {
77 free(-1+(MapPair *)p);
80 /***** Global data and bootstrap **********************/
82 static int isEqualPrototype (const void *info, const void *data1, const void *data2) {
83 NXHashTablePrototype *proto1 = (NXHashTablePrototype *) data1;
84 NXHashTablePrototype *proto2 = (NXHashTablePrototype *) data2;
86 return (proto1->hash == proto2->hash) && (proto1->isEqual == proto2->isEqual) && (proto1->free == proto2->free) && (proto1->style == proto2->style);
89 static uintptr_t hashPrototype (const void *info, const void *data) {
90 NXHashTablePrototype *proto = (NXHashTablePrototype *) data;
92 return NXPtrHash(info, (void*)proto->hash) ^ NXPtrHash(info, (void*)proto->isEqual) ^ NXPtrHash(info, (void*)proto->free) ^ (uintptr_t) proto->style;
95 static NXHashTablePrototype protoPrototype = {
96 hashPrototype, isEqualPrototype, NXNoEffectFree, 0
99 static NXHashTable *prototypes = NULL;
100 /* table of all prototypes */
102 /**** Fundamentals Operations **************/
104 NXMapTable *NXCreateMapTableFromZone(NXMapTablePrototype prototype, unsigned capacity, void *z) {
105 NXMapTable *table = (NXMapTable *)malloc_zone_malloc((malloc_zone_t *)z, sizeof(NXMapTable));
106 NXMapTablePrototype *proto;
107 if (! prototypes) prototypes = NXCreateHashTable(protoPrototype, 0, NULL);
108 if (! prototype.hash || ! prototype.isEqual || ! prototype.free || prototype.style) {
109 _objc_inform("*** NXCreateMapTable: invalid creation parameters\n");
112 proto = (NXMapTablePrototype *)NXHashGet(prototypes, &prototype);
114 proto = (NXMapTablePrototype *)malloc(sizeof(NXMapTablePrototype));
116 (void)NXHashInsert(prototypes, proto);
118 table->prototype = proto; table->count = 0;
119 table->nbBucketsMinusOne = exp2u(log2u(capacity)+1) - 1;
120 table->buckets = allocBuckets(z, table->nbBucketsMinusOne + 1);
124 NXMapTable *NXCreateMapTable(NXMapTablePrototype prototype, unsigned capacity) {
125 return NXCreateMapTableFromZone(prototype, capacity, malloc_default_zone());
128 void NXFreeMapTable(NXMapTable *table) {
129 NXResetMapTable(table);
130 freeBuckets(table->buckets);
134 void NXResetMapTable(NXMapTable *table) {
135 MapPair *pairs = (MapPair *)table->buckets;
136 void (*freeProc)(struct _NXMapTable *, void *, void *) = table->prototype->free;
137 unsigned index = table->nbBucketsMinusOne + 1;
139 if (pairs->key != NX_MAPNOTAKEY) {
140 freeProc(table, (void *)pairs->key, (void *)pairs->value);
141 pairs->key = NX_MAPNOTAKEY; pairs->value = NULL;
148 BOOL NXCompareMapTables(NXMapTable *table1, NXMapTable *table2) {
149 if (table1 == table2) return YES;
150 if (table1->count != table2->count) return NO;
154 NXMapState state = NXInitMapState(table1);
155 while (NXNextMapState(table1, &state, &key, &value)) {
156 if (NXMapMember(table2, key, (void**)&value) == NX_MAPNOTAKEY) return NO;
162 unsigned NXCountMapTable(NXMapTable *table) { return table->count; }
164 static INLINE void *_NXMapMember(NXMapTable *table, const void *key, void **value) {
165 MapPair *pairs = (MapPair *)table->buckets;
166 unsigned index = bucketOf(table, key);
167 MapPair *pair = pairs + index;
168 if (pair->key == NX_MAPNOTAKEY) return NX_MAPNOTAKEY;
169 if (isEqual(table, pair->key, key)) {
170 *value = (void *)pair->value;
171 return (void *)pair->key;
173 unsigned index2 = index;
174 while ((index2 = nextIndex(table, index2)) != index) {
175 pair = pairs + index2;
176 if (pair->key == NX_MAPNOTAKEY) return NX_MAPNOTAKEY;
177 if (isEqual(table, pair->key, key)) {
178 *value = (void *)pair->value;
179 return (void *)pair->key;
182 return NX_MAPNOTAKEY;
186 void *NXMapMember(NXMapTable *table, const void *key, void **value) {
187 return _NXMapMember(table, key, value);
190 void *NXMapGet(NXMapTable *table, const void *key) {
192 return (_NXMapMember(table, key, &value) != NX_MAPNOTAKEY) ? value : NULL;
195 static void _NXMapRehash(NXMapTable *table) {
196 MapPair *pairs = (MapPair *)table->buckets;
197 MapPair *pair = pairs;
198 unsigned numBuckets = table->nbBucketsMinusOne + 1;
199 unsigned index = numBuckets;
200 unsigned oldCount = table->count;
202 table->nbBucketsMinusOne = 2 * numBuckets - 1;
204 table->buckets = allocBuckets(malloc_zone_from_ptr(table), table->nbBucketsMinusOne + 1);
206 if (pair->key != NX_MAPNOTAKEY) {
207 (void)NXMapInsert(table, pair->key, pair->value);
211 if (oldCount != table->count)
212 _objc_inform("*** 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");
216 void *NXMapInsert(NXMapTable *table, const void *key, const void *value) {
217 MapPair *pairs = (MapPair *)table->buckets;
218 unsigned index = bucketOf(table, key);
219 MapPair *pair = pairs + index;
220 if (key == NX_MAPNOTAKEY) {
221 _objc_inform("*** NXMapInsert: invalid key: -1\n");
225 unsigned numBuckets = table->nbBucketsMinusOne + 1;
227 if (pair->key == NX_MAPNOTAKEY) {
228 pair->key = key; pair->value = value;
230 if (table->count * 4 > numBuckets * 3) _NXMapRehash(table);
234 if (isEqual(table, pair->key, key)) {
235 const void *old = pair->value;
236 if (old != value) pair->value = value;/* avoid writing unless needed! */
238 } else if (table->count == numBuckets) {
239 /* no room: rehash and retry */
241 return NXMapInsert(table, key, value);
243 unsigned index2 = index;
244 while ((index2 = nextIndex(table, index2)) != index) {
245 pair = pairs + index2;
246 if (pair->key == NX_MAPNOTAKEY) {
247 pair->key = key; pair->value = value;
249 if (table->count * 4 > numBuckets * 3) _NXMapRehash(table);
252 if (isEqual(table, pair->key, key)) {
253 const void *old = pair->value;
254 if (old != value) pair->value = value;/* avoid writing unless needed! */
258 /* no room: can't happen! */
259 _objc_inform("**** NXMapInsert: bug\n");
264 static int mapRemove = 0;
266 void *NXMapRemove(NXMapTable *table, const void *key) {
267 MapPair *pairs = (MapPair *)table->buckets;
268 unsigned index = bucketOf(table, key);
269 MapPair *pair = pairs + index;
270 unsigned chain = 1; /* number of non-nil pairs in a row */
272 const void *old = NULL;
273 if (pair->key == NX_MAPNOTAKEY) return NULL;
277 unsigned index2 = index;
278 if (isEqual(table, pair->key, key)) {found ++; old = pair->value; }
279 while ((index2 = nextIndex(table, index2)) != index) {
280 pair = pairs + index2;
281 if (pair->key == NX_MAPNOTAKEY) break;
282 if (isEqual(table, pair->key, key)) {found ++; old = pair->value; }
286 if (! found) return NULL;
287 if (found != 1) _objc_inform("**** NXMapRemove: incorrect table\n");
288 /* remove then reinsert */
291 MapPair *aux = (chain > 16) ? (MapPair *)malloc(sizeof(MapPair)*(chain-1)) : buffer;
294 unsigned index2 = index;
296 pair = pairs + index2;
297 if (! isEqual(table, pair->key, key)) aux[auxnb++] = *pair;
298 pair->key = NX_MAPNOTAKEY; pair->value = NULL;
299 index2 = nextIndex(table, index2);
301 table->count -= chain;
302 if (auxnb != chain-1) _objc_inform("**** NXMapRemove: bug\n");
303 while (auxnb--) NXMapInsert(table, aux[auxnb].key, aux[auxnb].value);
304 if (chain > 16) free(aux);
309 NXMapState NXInitMapState(NXMapTable *table) {
311 state.index = table->nbBucketsMinusOne + 1;
315 int NXNextMapState(NXMapTable *table, NXMapState *state, const void **key, const void **value) {
316 MapPair *pairs = (MapPair *)table->buckets;
317 while (state->index--) {
318 MapPair *pair = pairs + state->index;
319 if (pair->key != NX_MAPNOTAKEY) {
320 *key = pair->key; *value = pair->value;
328 /***********************************************************************
329 * NXMapKeyCopyingInsert
330 * Like NXMapInsert, but strdups the key if necessary.
331 * Used to prevent stale pointers when bundles are unloaded.
332 **********************************************************************/
333 void *NXMapKeyCopyingInsert(NXMapTable *table, const void *key, const void *value)
336 void *realValue = NULL;
338 if ((realKey = NXMapMember(table, key, &realValue)) != NX_MAPNOTAKEY) {
339 // key DOES exist in table - use table's key for insertion
341 // key DOES NOT exist in table - copy the new key before insertion
342 realKey = (void *)strdup((char *)key);
344 return NXMapInsert(table, realKey, value);
348 /***********************************************************************
349 * NXMapKeyFreeingRemove
350 * Like NXMapRemove, but frees the existing key if necessary.
351 * Used to prevent stale pointers when bundles are unloaded.
352 **********************************************************************/
353 void *NXMapKeyFreeingRemove(NXMapTable *table, const void *key)
356 void *realValue = NULL;
358 if ((realKey = NXMapMember(table, key, &realValue)) != NX_MAPNOTAKEY) {
359 // key DOES exist in table - remove pair and free key
360 realValue = NXMapRemove(table, realKey);
361 free(realKey); // the key from the table, not necessarily the one given
364 // key DOES NOT exist in table - nothing to do
370 /**** Conveniences *************************************/
372 static unsigned _mapPtrHash(NXMapTable *table, const void *key) {
374 return (unsigned)(((uintptr_t)key) >> 3);
376 return ((uintptr_t)key) >> 2;
380 static unsigned _mapStrHash(NXMapTable *table, const void *key) {
382 unsigned char *s = (unsigned char *)key;
383 /* unsigned to avoid a sign-extend */
384 /* unroll the loop */
386 if (*s == '\0') break;
388 if (*s == '\0') break;
390 if (*s == '\0') break;
392 if (*s == '\0') break;
395 return xorHash(hash);
398 static int _mapPtrIsEqual(NXMapTable *table, const void *key1, const void *key2) {
402 static int _mapStrIsEqual(NXMapTable *table, const void *key1, const void *key2) {
403 if (key1 == key2) return YES;
404 if (! key1) return ! strlen ((char *) key2);
405 if (! key2) return ! strlen ((char *) key1);
406 if (((char *) key1)[0] != ((char *) key2)[0]) return NO;
407 return (strcmp((char *) key1, (char *) key2)) ? NO : YES;
410 static void _mapNoFree(NXMapTable *table, void *key, void *value) {}
412 const NXMapTablePrototype NXPtrValueMapPrototype = {
413 _mapPtrHash, _mapPtrIsEqual, _mapNoFree, 0
416 const NXMapTablePrototype NXStrValueMapPrototype = {
417 _mapStrHash, _mapStrIsEqual, _mapNoFree, 0
421 #if !__OBJC2__ && !TARGET_OS_WIN32
423 /* This only works with class Object, which is unavailable. */
425 /* Method prototypes */
426 @interface DoesNotExist
430 - (const char *)UTF8String;
431 - (unsigned long)hash;
432 - (BOOL)isEqual:(id)object;
436 static unsigned _mapObjectHash(NXMapTable *table, const void *key) {
437 return [(id)key hash];
440 static int _mapObjectIsEqual(NXMapTable *table, const void *key1, const void *key2) {
441 return [(id)key1 isEqual:(id)key2];
444 static void _mapObjectFree(NXMapTable *table, void *key, void *value) {
448 const NXMapTablePrototype NXObjectMapPrototype = {
449 _mapObjectHash, _mapObjectIsEqual, _mapObjectFree, 0