]> git.saurik.com Git - apple/objc4.git/blob - runtime/maptable.mm
objc4-532.2.tar.gz
[apple/objc4.git] / runtime / maptable.mm
1 /*
2 * Copyright (c) 1999-2003, 2005-2007 Apple Inc. All Rights Reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
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
11 * file.
12 *
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.
20 *
21 * @APPLE_LICENSE_HEADER_END@
22 */
23 /* maptable.m
24 Copyright 1990-1996 NeXT Software, Inc.
25 Created by Bertrand Serlet, August 1990
26 */
27
28
29 #include <string.h>
30 #include <stdlib.h>
31 #include <stdio.h>
32
33 #include "objc-private.h"
34 #include "maptable.h"
35 #include "hashtable2.h"
36
37
38 /****** Macros and utilities ****************************/
39
40 #if defined(DEBUG)
41 #define INLINE
42 #else
43 #define INLINE inline
44 #endif
45
46 typedef struct _MapPair {
47 const void *key;
48 const void *value;
49 } MapPair;
50
51 static unsigned log2u(unsigned x) { return (x<2) ? 0 : log2u(x>>1)+1; };
52
53 static INLINE unsigned exp2u(unsigned x) { return (1 << x); };
54
55 static INLINE unsigned xorHash(unsigned hash) {
56 unsigned xored = (hash & 0xffff) ^ (hash >> 16);
57 return ((xored * 65521) + hash);
58 }
59
60 static INLINE unsigned bucketOf(NXMapTable *table, const void *key) {
61 unsigned hash = (table->prototype->hash)(table, key);
62 return hash & table->nbBucketsMinusOne;
63 }
64
65 static INLINE int isEqual(NXMapTable *table, const void *key1, const void *key2) {
66 return (key1 == key2) ? 1 : (table->prototype->isEqual)(table, key1, key2);
67 }
68
69 static INLINE unsigned nextIndex(NXMapTable *table, unsigned index) {
70 return (index + 1) & table->nbBucketsMinusOne;
71 }
72
73 static INLINE void *allocBuckets(void *z, unsigned nb) {
74 MapPair *pairs = 1+(MapPair *)malloc_zone_malloc((malloc_zone_t *)z, ((nb+1) * sizeof(MapPair)));
75 MapPair *pair = pairs;
76 while (nb--) { pair->key = NX_MAPNOTAKEY; pair->value = NULL; pair++; }
77 return pairs;
78 }
79
80 static INLINE void freeBuckets(void *p) {
81 free(-1+(MapPair *)p);
82 }
83
84 /***** Global data and bootstrap **********************/
85
86 static int isEqualPrototype (const void *info, const void *data1, const void *data2) {
87 NXHashTablePrototype *proto1 = (NXHashTablePrototype *) data1;
88 NXHashTablePrototype *proto2 = (NXHashTablePrototype *) data2;
89
90 return (proto1->hash == proto2->hash) && (proto1->isEqual == proto2->isEqual) && (proto1->free == proto2->free) && (proto1->style == proto2->style);
91 };
92
93 static uintptr_t hashPrototype (const void *info, const void *data) {
94 NXHashTablePrototype *proto = (NXHashTablePrototype *) data;
95
96 return NXPtrHash(info, (void*)proto->hash) ^ NXPtrHash(info, (void*)proto->isEqual) ^ NXPtrHash(info, (void*)proto->free) ^ (uintptr_t) proto->style;
97 };
98
99 static NXHashTablePrototype protoPrototype = {
100 hashPrototype, isEqualPrototype, NXNoEffectFree, 0
101 };
102
103 static NXHashTable *prototypes = NULL;
104 /* table of all prototypes */
105
106 /**** Fundamentals Operations **************/
107
108 NXMapTable *NXCreateMapTableFromZone(NXMapTablePrototype prototype, unsigned capacity, void *z) {
109 NXMapTable *table = (NXMapTable *)malloc_zone_malloc((malloc_zone_t *)z, sizeof(NXMapTable));
110 NXMapTablePrototype *proto;
111 if (! prototypes) prototypes = NXCreateHashTable(protoPrototype, 0, NULL);
112 if (! prototype.hash || ! prototype.isEqual || ! prototype.free || prototype.style) {
113 _objc_inform("*** NXCreateMapTable: invalid creation parameters\n");
114 return NULL;
115 }
116 proto = (NXMapTablePrototype *)NXHashGet(prototypes, &prototype);
117 if (! proto) {
118 proto = (NXMapTablePrototype *)malloc(sizeof(NXMapTablePrototype));
119 *proto = prototype;
120 (void)NXHashInsert(prototypes, proto);
121 }
122 table->prototype = proto; table->count = 0;
123 table->nbBucketsMinusOne = exp2u(log2u(capacity)+1) - 1;
124 table->buckets = allocBuckets(z, table->nbBucketsMinusOne + 1);
125 return table;
126 }
127
128 NXMapTable *NXCreateMapTable(NXMapTablePrototype prototype, unsigned capacity) {
129 return NXCreateMapTableFromZone(prototype, capacity, malloc_default_zone());
130 }
131
132 void NXFreeMapTable(NXMapTable *table) {
133 NXResetMapTable(table);
134 freeBuckets(table->buckets);
135 free(table);
136 }
137
138 void NXResetMapTable(NXMapTable *table) {
139 MapPair *pairs = (MapPair *)table->buckets;
140 void (*freeProc)(struct _NXMapTable *, void *, void *) = table->prototype->free;
141 unsigned index = table->nbBucketsMinusOne + 1;
142 while (index--) {
143 if (pairs->key != NX_MAPNOTAKEY) {
144 freeProc(table, (void *)pairs->key, (void *)pairs->value);
145 pairs->key = NX_MAPNOTAKEY; pairs->value = NULL;
146 }
147 pairs++;
148 }
149 table->count = 0;
150 }
151
152 BOOL NXCompareMapTables(NXMapTable *table1, NXMapTable *table2) {
153 if (table1 == table2) return YES;
154 if (table1->count != table2->count) return NO;
155 else {
156 const void *key;
157 const void *value;
158 NXMapState state = NXInitMapState(table1);
159 while (NXNextMapState(table1, &state, &key, &value)) {
160 if (NXMapMember(table2, key, (void**)&value) == NX_MAPNOTAKEY) return NO;
161 }
162 return YES;
163 }
164 }
165
166 unsigned NXCountMapTable(NXMapTable *table) { return table->count; }
167
168 static INLINE void *_NXMapMember(NXMapTable *table, const void *key, void **value) {
169 MapPair *pairs = (MapPair *)table->buckets;
170 unsigned index = bucketOf(table, key);
171 MapPair *pair = pairs + index;
172 if (pair->key == NX_MAPNOTAKEY) return NX_MAPNOTAKEY;
173 if (isEqual(table, pair->key, key)) {
174 *value = (void *)pair->value;
175 return (void *)pair->key;
176 } else {
177 unsigned index2 = index;
178 while ((index2 = nextIndex(table, index2)) != index) {
179 pair = pairs + index2;
180 if (pair->key == NX_MAPNOTAKEY) return NX_MAPNOTAKEY;
181 if (isEqual(table, pair->key, key)) {
182 *value = (void *)pair->value;
183 return (void *)pair->key;
184 }
185 }
186 return NX_MAPNOTAKEY;
187 }
188 }
189
190 void *NXMapMember(NXMapTable *table, const void *key, void **value) {
191 return _NXMapMember(table, key, value);
192 }
193
194 void *NXMapGet(NXMapTable *table, const void *key) {
195 void *value;
196 return (_NXMapMember(table, key, &value) != NX_MAPNOTAKEY) ? value : NULL;
197 }
198
199 static void _NXMapRehash(NXMapTable *table) {
200 MapPair *pairs = (MapPair *)table->buckets;
201 MapPair *pair = pairs;
202 unsigned numBuckets = table->nbBucketsMinusOne + 1;
203 unsigned index = numBuckets;
204 unsigned oldCount = table->count;
205
206 table->nbBucketsMinusOne = 2 * numBuckets - 1;
207 table->count = 0;
208 table->buckets = allocBuckets(malloc_zone_from_ptr(table), table->nbBucketsMinusOne + 1);
209 while (index--) {
210 if (pair->key != NX_MAPNOTAKEY) {
211 (void)NXMapInsert(table, pair->key, pair->value);
212 }
213 pair++;
214 }
215 if (oldCount != table->count)
216 _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");
217 freeBuckets(pairs);
218 }
219
220 void *NXMapInsert(NXMapTable *table, const void *key, const void *value) {
221 MapPair *pairs = (MapPair *)table->buckets;
222 unsigned index = bucketOf(table, key);
223 MapPair *pair = pairs + index;
224 if (key == NX_MAPNOTAKEY) {
225 _objc_inform("*** NXMapInsert: invalid key: -1\n");
226 return NULL;
227 }
228
229 unsigned numBuckets = table->nbBucketsMinusOne + 1;
230
231 if (pair->key == NX_MAPNOTAKEY) {
232 pair->key = key; pair->value = value;
233 table->count++;
234 if (table->count * 4 > numBuckets * 3) _NXMapRehash(table);
235 return NULL;
236 }
237
238 if (isEqual(table, pair->key, key)) {
239 const void *old = pair->value;
240 if (old != value) pair->value = value;/* avoid writing unless needed! */
241 return (void *)old;
242 } else if (table->count == numBuckets) {
243 /* no room: rehash and retry */
244 _NXMapRehash(table);
245 return NXMapInsert(table, key, value);
246 } else {
247 unsigned index2 = index;
248 while ((index2 = nextIndex(table, index2)) != index) {
249 pair = pairs + index2;
250 if (pair->key == NX_MAPNOTAKEY) {
251 pair->key = key; pair->value = value;
252 table->count++;
253 if (table->count * 4 > numBuckets * 3) _NXMapRehash(table);
254 return NULL;
255 }
256 if (isEqual(table, pair->key, key)) {
257 const void *old = pair->value;
258 if (old != value) pair->value = value;/* avoid writing unless needed! */
259 return (void *)old;
260 }
261 }
262 /* no room: can't happen! */
263 _objc_inform("**** NXMapInsert: bug\n");
264 return NULL;
265 }
266 }
267
268 static int mapRemove = 0;
269
270 void *NXMapRemove(NXMapTable *table, const void *key) {
271 MapPair *pairs = (MapPair *)table->buckets;
272 unsigned index = bucketOf(table, key);
273 MapPair *pair = pairs + index;
274 unsigned chain = 1; /* number of non-nil pairs in a row */
275 int found = 0;
276 const void *old = NULL;
277 if (pair->key == NX_MAPNOTAKEY) return NULL;
278 mapRemove ++;
279 /* compute chain */
280 {
281 unsigned index2 = index;
282 if (isEqual(table, pair->key, key)) {found ++; old = pair->value; }
283 while ((index2 = nextIndex(table, index2)) != index) {
284 pair = pairs + index2;
285 if (pair->key == NX_MAPNOTAKEY) break;
286 if (isEqual(table, pair->key, key)) {found ++; old = pair->value; }
287 chain++;
288 }
289 }
290 if (! found) return NULL;
291 if (found != 1) _objc_inform("**** NXMapRemove: incorrect table\n");
292 /* remove then reinsert */
293 {
294 MapPair buffer[16];
295 MapPair *aux = (chain > 16) ? (MapPair *)malloc(sizeof(MapPair)*(chain-1)) : buffer;
296 unsigned auxnb = 0;
297 int nb = chain;
298 unsigned index2 = index;
299 while (nb--) {
300 pair = pairs + index2;
301 if (! isEqual(table, pair->key, key)) aux[auxnb++] = *pair;
302 pair->key = NX_MAPNOTAKEY; pair->value = NULL;
303 index2 = nextIndex(table, index2);
304 }
305 table->count -= chain;
306 if (auxnb != chain-1) _objc_inform("**** NXMapRemove: bug\n");
307 while (auxnb--) NXMapInsert(table, aux[auxnb].key, aux[auxnb].value);
308 if (chain > 16) free(aux);
309 }
310 return (void *)old;
311 }
312
313 NXMapState NXInitMapState(NXMapTable *table) {
314 NXMapState state;
315 state.index = table->nbBucketsMinusOne + 1;
316 return state;
317 }
318
319 int NXNextMapState(NXMapTable *table, NXMapState *state, const void **key, const void **value) {
320 MapPair *pairs = (MapPair *)table->buckets;
321 while (state->index--) {
322 MapPair *pair = pairs + state->index;
323 if (pair->key != NX_MAPNOTAKEY) {
324 *key = pair->key; *value = pair->value;
325 return YES;
326 }
327 }
328 return NO;
329 }
330
331
332 /***********************************************************************
333 * NXMapKeyCopyingInsert
334 * Like NXMapInsert, but strdups the key if necessary.
335 * Used to prevent stale pointers when bundles are unloaded.
336 **********************************************************************/
337 void *NXMapKeyCopyingInsert(NXMapTable *table, const void *key, const void *value)
338 {
339 void *realKey;
340 void *realValue = NULL;
341
342 if ((realKey = NXMapMember(table, key, &realValue)) != NX_MAPNOTAKEY) {
343 // key DOES exist in table - use table's key for insertion
344 } else {
345 // key DOES NOT exist in table - copy the new key before insertion
346 realKey = (void *)_strdup_internal((char *)key);
347 }
348 return NXMapInsert(table, realKey, value);
349 }
350
351
352 /***********************************************************************
353 * NXMapKeyFreeingRemove
354 * Like NXMapRemove, but frees the existing key if necessary.
355 * Used to prevent stale pointers when bundles are unloaded.
356 **********************************************************************/
357 void *NXMapKeyFreeingRemove(NXMapTable *table, const void *key)
358 {
359 void *realKey;
360 void *realValue = NULL;
361
362 if ((realKey = NXMapMember(table, key, &realValue)) != NX_MAPNOTAKEY) {
363 // key DOES exist in table - remove pair and free key
364 realValue = NXMapRemove(table, realKey);
365 _free_internal(realKey); // the key from the table, not necessarily the one given
366 return realValue;
367 } else {
368 // key DOES NOT exist in table - nothing to do
369 return NULL;
370 }
371 }
372
373
374 /**** Conveniences *************************************/
375
376 static unsigned _mapPtrHash(NXMapTable *table, const void *key) {
377 #ifdef __LP64__
378 return ((uintptr_t)key) >> 3;
379 #else
380 return ((uintptr_t)key) >> 2;
381 #endif
382 }
383
384 static unsigned _mapStrHash(NXMapTable *table, const void *key) {
385 unsigned hash = 0;
386 unsigned char *s = (unsigned char *)key;
387 /* unsigned to avoid a sign-extend */
388 /* unroll the loop */
389 if (s) for (; ; ) {
390 if (*s == '\0') break;
391 hash ^= *s++;
392 if (*s == '\0') break;
393 hash ^= *s++ << 8;
394 if (*s == '\0') break;
395 hash ^= *s++ << 16;
396 if (*s == '\0') break;
397 hash ^= *s++ << 24;
398 }
399 return xorHash(hash);
400 }
401
402 static int _mapPtrIsEqual(NXMapTable *table, const void *key1, const void *key2) {
403 return key1 == key2;
404 }
405
406 static int _mapStrIsEqual(NXMapTable *table, const void *key1, const void *key2) {
407 if (key1 == key2) return YES;
408 if (! key1) return ! strlen ((char *) key2);
409 if (! key2) return ! strlen ((char *) key1);
410 if (((char *) key1)[0] != ((char *) key2)[0]) return NO;
411 return (strcmp((char *) key1, (char *) key2)) ? NO : YES;
412 }
413
414 static void _mapNoFree(NXMapTable *table, void *key, void *value) {}
415
416 const NXMapTablePrototype NXPtrValueMapPrototype = {
417 _mapPtrHash, _mapPtrIsEqual, _mapNoFree, 0
418 };
419
420 const NXMapTablePrototype NXStrValueMapPrototype = {
421 _mapStrHash, _mapStrIsEqual, _mapNoFree, 0
422 };
423
424
425 #if !__OBJC2__ && !TARGET_OS_WIN32
426
427 /* This only works with class Object, which is unavailable. */
428
429 /* Method prototypes */
430 @interface DoesNotExist
431 + (id)class;
432 + (id)initialize;
433 - (id)description;
434 - (const char *)UTF8String;
435 - (unsigned long)hash;
436 - (BOOL)isEqual:(id)object;
437 - (void)free;
438 @end
439
440 static unsigned _mapObjectHash(NXMapTable *table, const void *key) {
441 return [(id)key hash];
442 }
443
444 static int _mapObjectIsEqual(NXMapTable *table, const void *key1, const void *key2) {
445 return [(id)key1 isEqual:(id)key2];
446 }
447
448 static void _mapObjectFree(NXMapTable *table, void *key, void *value) {
449 [(id)key free];
450 }
451
452 const NXMapTablePrototype NXObjectMapPrototype = {
453 _mapObjectHash, _mapObjectIsEqual, _mapObjectFree, 0
454 };
455
456 #endif