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