runtime/maptable.m

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