Return to maptable.m CVS log

Up to [Apple Darwin 0.x] / objc

Annotation of objc/maptable.m, revision 1.1

1.1     ! root        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.0 (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 NeXT, Inc.
        !            26:        Created by Bertrand Serlet, August 1990
        !            27:  */
        !            28: 
        !            29: #ifdef SHLIB
        !            30: #import "shlib.h"
        !            31: #endif SHLIB
        !            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 "Object.h"
        !            40: #import "hashtable.h"
        !            41: 
        !            42: /******                Macros and utilities    ****************************/
        !            43: 
        !            44: #if DEBUG
        !            45: #define INLINE 
        !            46: #else
        !            47: #define INLINE inline
        !            48: #endif
        !            49: 
        !            50: typedef struct _MapPair {
        !            51:     const void *key;
        !            52:     const void *value;
        !            53: } MapPair;
        !            54: 
        !            55: static unsigned log2(unsigned x) { return (x<2) ? 0 : log2(x>>1)+1; };
        !            56: 
        !            57: static INLINE unsigned exp2m1(unsigned x) { return (1 << x) - 1; };
        !            58: 
        !            59: /* iff necessary this modulo can be optimized since the nbBuckets is of the form 2**n-1 */
        !            60: static INLINE unsigned bucketOf(NXMapTable *table, const void *key) {
        !            61:     unsigned   hash = (table->prototype->hash)(table, key);
        !            62:     unsigned   xored = (hash & 0xffff) ^ (hash >> 16);
        !            63:     return ((xored * 65521) + hash) % table->nbBuckets;
        !            64: }
        !            65: 
        !            66: static INLINE int isEqual(NXMapTable *table, const void *key1, const void *key2) {
        !            67:     return (key1 == key2) ? 1 : (table->prototype->isEqual)(table, key1, key2);
        !            68: }
        !            69: 
        !            70: static INLINE unsigned nextIndex(NXMapTable *table, unsigned index) {
        !            71:     return (index+1 >= table->nbBuckets) ? 0 : index+1;
        !            72: }
        !            73: 
        !            74: static INLINE void *allocBuckets(NXZone *zone, unsigned nb) {
        !            75:     MapPair    *pairs = NXZoneMalloc(zone, (nb * sizeof(MapPair)));
        !            76:     MapPair    *pair = pairs;
        !            77:     while (nb--) { pair->key = NX_MAPNOTAKEY; pair->value = NULL; pair++; }
        !            78:     return pairs;
        !            79: }
        !            80: 
        !            81: /*****         Global data and bootstrap       **********************/
        !            82: 
        !            83: static unsigned hashPrototype(const void *info, const void *data) {
        !            84:     NXMapTablePrototype        *proto = (NXMapTablePrototype *) data;
        !            85:     return NXPtrHash(info, proto->hash) ^ NXPtrHash(info, proto->isEqual) ^ NXPtrHash(info, proto->free) ^ (unsigned) proto->style;
        !            86: }
        !            87: 
        !            88: static int isEqualPrototype(const void *info, const void *data1, const void *data2) {
        !            89:     NXMapTablePrototype        *proto1 = (NXMapTablePrototype *) data1;
        !            90:     NXMapTablePrototype        *proto2 = (NXMapTablePrototype *) data2;
        !            91:     return (proto1->hash == proto2->hash) && (proto1->isEqual == proto2->isEqual) && (proto1->free == proto2->free) && (proto1->style == proto2->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, NXZone *zone) {
        !           104:     NXMapTable                 *table = NXZoneMalloc(zone, sizeof(NXMapTable));
        !           105:     NXMapTablePrototype                *proto;
        !           106:     if (! prototypes) prototypes = NXCreateHashTable(protoPrototype, 0, NULL);
        !           107:     if (! prototype.hash || ! prototype.isEqual || ! prototype.free || prototype.style) {
        !           108:        _NXLogError("*** 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(zone, table->nbBuckets);
        !           120:     return table;
        !           121: }
        !           122: 
        !           123: NXMapTable *NXCreateMapTable(NXMapTablePrototype prototype, unsigned capacity) {
        !           124:     return NXCreateMapTableFromZone(prototype, capacity, NXDefaultMallocZone());
        !           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:        void            *key;
        !           152:        void            *value;
        !           153:        NXMapState      state = NXInitMapState(table1);
        !           154:        while (NXNextMapState(table1, &state, &key, &value)) {
        !           155:            if (NXMapMember(table2, key, &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(NXZoneFromPtr(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:        _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");
        !           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:        _NXLogError("*** 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:        _NXLogError("**** 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) _NXLogError("**** 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) _NXLogError("**** 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: unsigned _mapPtrHash(NXMapTable *table, const void *key) {
        !           355:     return (((unsigned) key) >> 16) ^ ((unsigned) key);
        !           356: }
        !           357:     
        !           358: 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: unsigned _mapObjectHash(NXMapTable *table, const void *key) {
        !           377:     return [(id)key hash];
        !           378: }
        !           379:     
        !           380: int _mapPtrIsEqual(NXMapTable *table, const void *key1, const void *key2) {
        !           381:     return key1 == key2;
        !           382: }
        !           383: 
        !           384: 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: int _mapObjectIsEqual(NXMapTable *table, const void *key1, const void *key2) {
        !           393:     return [(id)key1 isEqual:(id)key2];
        !           394: }
        !           395:     
        !           396: void _mapNoFree(NXMapTable *table, void *key, void *value) {}
        !           397: 
        !           398: void _mapObjectFree(NXMapTable *table, void *key, void *value) {
        !           399:     [(id)key free];
        !           400: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.