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