runtime/maptable.m

   1 /*
   2  * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Portions Copyright (c) 1999 Apple Computer, Inc.  All Rights
   7  * Reserved.  This file contains Original Code and/or Modifications of
   8  * Original Code as defined in and that are subject to the Apple Public
   9  * Source License Version 1.1 (the "License").  You may not use this file
  10  * except in compliance with the License.  Please obtain a copy of the
  11  * License at http://www.apple.com/publicsource and read it before using
  12  * this file.
  13  *
  14  * The Original Code and all software distributed under the License are
  15  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  16  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  17  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE OR NON- INFRINGEMENT.  Please see the
  19  * License for the specific language governing rights and limitations
  20  * under the License.
  21  *
  22  * @APPLE_LICENSE_HEADER_END@
  23  */
  24 /*      maptable.m
  25         Copyright 1990-1996 NeXT Software, Inc.
  26         Created by Bertrand Serlet, August 1990
  27  */
  28
  29
  30 #import "objc-private.h"
  31 #import "maptable.h"
  32
  33 #import <string.h>
  34 #import <stdlib.h>
  35 #import <stdio.h>
  36 #import <objc/Object.h>
  37 #import <objc/hashtable2.h>
  38
  39
  40 /******         Macros and utilities    ****************************/
  41
  42 #if defined(DEBUG)
  43     #define INLINE
  44 #else
  45     #define INLINE inline
  46 #endif
  47
  48 typedef struct _MapPair {
  49     const void  *key;
  50     const void  *value;
  51 } MapPair;
  52
  53 static unsigned log2(unsigned x) { return (x<2) ? 0 : log2(x>>1)+1; };
  54
  55 static INLINE unsigned exp2m1(unsigned x) { return (1 << x) - 1; };
  56
  57 /* iff necessary this modulo can be optimized since the nbBuckets is of the form 2**n-1 */
  58 static INLINE unsigned bucketOf(NXMapTable *table, const void *key) {
  59     unsigned    hash = (table->prototype->hash)(table, key);
  60     unsigned    xored = (hash & 0xffff) ^ (hash >> 16);
  61     return ((xored * 65521) + hash) % table->nbBuckets;
  62 }
  63
  64 static INLINE int isEqual(NXMapTable *table, const void *key1, const void *key2) {
  65     return (key1 == key2) ? 1 : (table->prototype->isEqual)(table, key1, key2);
  66 }
  67
  68 static INLINE unsigned nextIndex(NXMapTable *table, unsigned index) {
  69     return (index+1 >= table->nbBuckets) ? 0 : index+1;
  70 }
  71
  72 static INLINE void *allocBuckets(void *z, unsigned nb) {
  73     MapPair     *pairs = malloc_zone_malloc(z, (nb * sizeof(MapPair)));
  74     MapPair     *pair = pairs;
  75     while (nb--) { pair->key = NX_MAPNOTAKEY; pair->value = NULL; pair++; }
  76     return pairs;
  77 }
  78
  79 /*****          Global data and bootstrap       **********************/
  80
  81 static int isEqualPrototype (const void *info, const void *data1, const void *data2) {
  82     NXHashTablePrototype        *proto1 = (NXHashTablePrototype *) data1;
  83     NXHashTablePrototype        *proto2 = (NXHashTablePrototype *) data2;
  84
  85     return (proto1->hash == proto2->hash) && (proto1->isEqual == proto2->isEqual) && (proto1->free == proto2->free) && (proto1->style == proto2->style);
  86     };
  87
  88 static uarith_t hashPrototype (const void *info, const void *data) {
  89     NXHashTablePrototype        *proto = (NXHashTablePrototype *) data;
  90
  91     return NXPtrHash(info, proto->hash) ^ NXPtrHash(info, proto->isEqual) ^ NXPtrHash(info, proto->free) ^ (uarith_t) proto->style;
  92     };
  93
  94 static NXHashTablePrototype protoPrototype = {
  95     hashPrototype, isEqualPrototype, NXNoEffectFree, 0
  96 };
  97
  98 static NXHashTable *prototypes = NULL;
  99         /* table of all prototypes */
 100
 101 /****           Fundamentals Operations                 **************/
 102
 103 NXMapTable *NXCreateMapTableFromZone(NXMapTablePrototype prototype, unsigned capacity, void *z) {
 104     NXMapTable                  *table = malloc_zone_malloc(z, sizeof(NXMapTable));
 105     NXMapTablePrototype         *proto;
 106     if (! prototypes) prototypes = NXCreateHashTable(protoPrototype, 0, NULL);
 107     if (! prototype.hash || ! prototype.isEqual || ! prototype.free || prototype.style) {
 108         _objc_syslog("*** NXCreateMapTable: invalid creation parameters\n");
 109         return NULL;
 110     }
 111     proto = NXHashGet(prototypes, &prototype);
 112     if (! proto) {
 113         proto = malloc(sizeof(NXMapTablePrototype));
 114         *proto = prototype;
 115         (void)NXHashInsert(prototypes, proto);
 116     }
 117     table->prototype = proto; table->count = 0;
 118     table->nbBuckets = exp2m1(log2(capacity)+1);
 119     table->buckets = allocBuckets(z, table->nbBuckets);
 120     return table;
 121 }
 122
 123 NXMapTable *NXCreateMapTable(NXMapTablePrototype prototype, unsigned capacity) {
 124     return NXCreateMapTableFromZone(prototype, capacity, malloc_default_zone());
 125 }
 126
 127 void NXFreeMapTable(NXMapTable *table) {
 128     NXResetMapTable(table);
 129     free(table->buckets);
 130     free(table);
 131 }
 132
 133 void NXResetMapTable(NXMapTable *table) {
 134     MapPair     *pairs = table->buckets;
 135     void        (*freeProc)(struct _NXMapTable *, void *, void *) = table->prototype->free;
 136     unsigned    index = table->nbBuckets;
 137     while (index--) {
 138         if (pairs->key != NX_MAPNOTAKEY) {
 139             freeProc(table, (void *)pairs->key, (void *)pairs->value);
 140             pairs->key = NX_MAPNOTAKEY; pairs->value = NULL;
 141         }
 142         pairs++;
 143     }
 144     table->count = 0;
 145 }
 146
 147 BOOL NXCompareMapTables(NXMapTable *table1, NXMapTable *table2) {
 148     if (table1 == table2) return YES;
 149     if (table1->count != table2->count) return NO;
 150     else {
 151         const void *key;
 152         const void *value;
 153         NXMapState      state = NXInitMapState(table1);
 154         while (NXNextMapState(table1, &state, &key, &value)) {
 155             if (NXMapMember(table2, key, (void**)&value) == NX_MAPNOTAKEY) return NO;
 156         }
 157         return YES;
 158     }
 159 }
 160
 161 unsigned NXCountMapTable(NXMapTable *table) { return table->count; }
 162
 163 static int mapSearch = 0;
 164 static int mapSearchHit = 0;
 165 static int mapSearchLoop = 0;
 166
 167 static INLINE void *_NXMapMember(NXMapTable *table, const void *key, void **value) {
 168     MapPair     *pairs = table->buckets;
 169     unsigned    index = bucketOf(table, key);
 170     MapPair     *pair = pairs + index;
 171     if (pair->key == NX_MAPNOTAKEY) return NX_MAPNOTAKEY;
 172     mapSearch ++;
 173     if (isEqual(table, pair->key, key)) {
 174         *value = (void *)pair->value;
 175         mapSearchHit ++;
 176         return (void *)pair->key;
 177     } else {
 178         unsigned        index2 = index;
 179         while ((index2 = nextIndex(table, index2)) != index) {
 180             mapSearchLoop ++;
 181             pair = pairs + index2;
 182             if (pair->key == NX_MAPNOTAKEY) return NX_MAPNOTAKEY;
 183             if (isEqual(table, pair->key, key)) {
 184                 *value = (void *)pair->value;
 185                 return (void *)pair->key;
 186             }
 187         }
 188         return NX_MAPNOTAKEY;
 189     }
 190 }
 191
 192 void *NXMapMember(NXMapTable *table, const void *key, void **value) {
 193     return _NXMapMember(table, key, value);
 194 }
 195
 196 void *NXMapGet(NXMapTable *table, const void *key) {
 197     void        *value;
 198     return (_NXMapMember(table, key, &value) != NX_MAPNOTAKEY) ? value : NULL;
 199 }
 200
 201 static int mapRehash = 0;
 202 static int mapRehashSum = 0;
 203
 204 static void _NXMapRehash(NXMapTable *table) {
 205     MapPair     *pairs = table->buckets;
 206     MapPair     *pair = pairs;
 207     unsigned    index = table->nbBuckets;
 208     unsigned    oldCount = table->count;
 209     table->nbBuckets += table->nbBuckets + 1; /* 2 times + 1 */
 210     table->count = 0;
 211     table->buckets = allocBuckets(malloc_zone_from_ptr(table), table->nbBuckets);
 212     mapRehash ++;
 213     mapRehashSum += table->count;
 214     while (index--) {
 215         if (pair->key != NX_MAPNOTAKEY) {
 216             (void)NXMapInsert(table, pair->key, pair->value);
 217         }
 218         pair++;
 219     }
 220     if (oldCount != table->count)
 221         _objc_syslog("*** 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");
 222     free(pairs);
 223 }
 224
 225 static int mapInsert = 0;
 226 static int mapInsertHit = 0;
 227 static int mapInsertLoop = 0;
 228
 229 void *NXMapInsert(NXMapTable *table, const void *key, const void *value) {
 230     MapPair     *pairs = table->buckets;
 231     unsigned    index = bucketOf(table, key);
 232     MapPair     *pair = pairs + index;
 233     if (key == NX_MAPNOTAKEY) {
 234         _objc_syslog("*** NXMapInsert: invalid key: -1\n");
 235         return NULL;
 236     }
 237     mapInsert ++;
 238     if (pair->key == NX_MAPNOTAKEY) {
 239         mapInsertHit ++;
 240         pair->key = key; pair->value = value;
 241         table->count++;
 242         return NULL;
 243     }
 244     if (isEqual(table, pair->key, key)) {
 245         const void      *old = pair->value;
 246         mapInsertHit ++;
 247         if (old != value) pair->value = value;/* avoid writing unless needed! */
 248         return (void *)old;
 249     } else if (table->count == table->nbBuckets) {
 250         /* no room: rehash and retry */
 251         _NXMapRehash(table);
 252         return NXMapInsert(table, key, value);
 253     } else {
 254         unsigned        index2 = index;
 255         while ((index2 = nextIndex(table, index2)) != index) {
 256             mapInsertLoop ++;
 257             pair = pairs + index2;
 258             if (pair->key == NX_MAPNOTAKEY) {
 259     #if INSERT_TAIL
 260               pair->key = key; pair->value = value;
 261     #else
 262               MapPair         current = {key, value};
 263               index2 = index;
 264               while (current.key != NX_MAPNOTAKEY) {
 265                   MapPair             temp;
 266                   pair = pairs + index2;
 267                   temp = *pair;
 268                   *pair = current;
 269                   current = temp;
 270                   index2 = nextIndex(table, index2);
 271               }
 272     #endif
 273                 table->count++;
 274                 if (table->count * 4 > table->nbBuckets * 3) _NXMapRehash(table);
 275                 return NULL;
 276             }
 277             if (isEqual(table, pair->key, key)) {
 278                 const void      *old = pair->value;
 279                 if (old != value) pair->value = value;/* avoid writing unless needed! */
 280                 return (void *)old;
 281             }
 282         }
 283         /* no room: can't happen! */
 284         _objc_syslog("**** NXMapInsert: bug\n");
 285         return NULL;
 286     }
 287 }
 288
 289 static int mapRemove = 0;
 290
 291 void *NXMapRemove(NXMapTable *table, const void *key) {
 292     MapPair     *pairs = table->buckets;
 293     unsigned    index = bucketOf(table, key);
 294     MapPair     *pair = pairs + index;
 295     unsigned    chain = 1; /* number of non-nil pairs in a row */
 296     int         found = 0;
 297     const void  *old = NULL;
 298     if (pair->key == NX_MAPNOTAKEY) return NULL;
 299     mapRemove ++;
 300     /* compute chain */
 301     {
 302         unsigned        index2 = index;
 303         if (isEqual(table, pair->key, key)) {found ++; old = pair->value; }
 304         while ((index2 = nextIndex(table, index2)) != index) {
 305             pair = pairs + index2;
 306             if (pair->key == NX_MAPNOTAKEY) break;
 307             if (isEqual(table, pair->key, key)) {found ++; old = pair->value; }
 308             chain++;
 309         }
 310     }
 311     if (! found) return NULL;
 312     if (found != 1) _objc_syslog("**** NXMapRemove: incorrect table\n");
 313     /* remove then reinsert */
 314     {
 315         MapPair buffer[16];
 316         MapPair *aux = (chain > 16) ? malloc(sizeof(MapPair)*(chain-1)) : buffer;
 317         int     auxnb = 0;
 318         int     nb = chain;
 319         unsigned        index2 = index;
 320         while (nb--) {
 321             pair = pairs + index2;
 322             if (! isEqual(table, pair->key, key)) aux[auxnb++] = *pair;
 323             pair->key = NX_MAPNOTAKEY; pair->value = NULL;
 324             index2 = nextIndex(table, index2);
 325         }
 326         table->count -= chain;
 327         if (auxnb != chain-1) _objc_syslog("**** NXMapRemove: bug\n");
 328         while (auxnb--) NXMapInsert(table, aux[auxnb].key, aux[auxnb].value);
 329         if (chain > 16) free(aux);
 330     }
 331     return (void *)old;
 332 }
 333
 334 NXMapState NXInitMapState(NXMapTable *table) {
 335     NXMapState  state;
 336     state.index = table->nbBuckets;
 337     return state;
 338 }
 339
 340 int NXNextMapState(NXMapTable *table, NXMapState *state, const void **key, const void **value) {
 341     MapPair     *pairs = table->buckets;
 342     while (state->index--) {
 343         MapPair *pair = pairs + state->index;
 344         if (pair->key != NX_MAPNOTAKEY) {
 345             *key = pair->key; *value = pair->value;
 346             return YES;
 347         }
 348     }
 349     return NO;
 350 }
 351
 352 /****           Conveniences            *************************************/
 353
 354 static unsigned _mapPtrHash(NXMapTable *table, const void *key) {
 355     return (((uarith_t) key) >> ARITH_SHIFT) ^ ((uarith_t) key);
 356 }
 357
 358 static unsigned _mapStrHash(NXMapTable *table, const void *key) {
 359     unsigned            hash = 0;
 360     unsigned char       *s = (unsigned char *)key;
 361     /* unsigned to avoid a sign-extend */
 362     /* unroll the loop */
 363     if (s) for (; ; ) {
 364         if (*s == '\0') break;
 365         hash ^= *s++;
 366         if (*s == '\0') break;
 367         hash ^= *s++ << 8;
 368         if (*s == '\0') break;
 369         hash ^= *s++ << 16;
 370         if (*s == '\0') break;
 371         hash ^= *s++ << 24;
 372     }
 373     return hash;
 374 }
 375
 376 static unsigned _mapObjectHash(NXMapTable *table, const void *key) {
 377     return [(id)key hash];
 378 }
 379
 380 static int _mapPtrIsEqual(NXMapTable *table, const void *key1, const void *key2) {
 381     return key1 == key2;
 382 }
 383
 384 static int _mapStrIsEqual(NXMapTable *table, const void *key1, const void *key2) {
 385     if (key1 == key2) return YES;
 386     if (! key1) return ! strlen ((char *) key2);
 387     if (! key2) return ! strlen ((char *) key1);
 388     if (((char *) key1)[0] != ((char *) key2)[0]) return NO;
 389     return (strcmp((char *) key1, (char *) key2)) ? NO : YES;
 390 }
 391
 392 static int _mapObjectIsEqual(NXMapTable *table, const void *key1, const void *key2) {
 393     return [(id)key1 isEqual:(id)key2];
 394 }
 395
 396 static void _mapNoFree(NXMapTable *table, void *key, void *value) {}
 397
 398 static void _mapObjectFree(NXMapTable *table, void *key, void *value) {
 399     [(id)key free];
 400 }
 401
 402 const NXMapTablePrototype NXPtrValueMapPrototype = {
 403     _mapPtrHash, _mapPtrIsEqual, _mapNoFree, 0
 404 };
 405
 406 const NXMapTablePrototype NXStrValueMapPrototype = {
 407     _mapStrHash, _mapStrIsEqual, _mapNoFree, 0
 408 };
 409
 410 const NXMapTablePrototype NXObjectMapPrototype = {
 411     _mapObjectHash, _mapObjectIsEqual, _mapObjectFree, 0
 412 };
 413