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