runtime/maptable.m

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