Return to HashTable.m CVS log

Up to [Apple Darwin 0.x] / objc

Annotation of objc/HashTable.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: /*
        !            25:        HashTable.m
        !            26:        Copyright 1988, 1989 NeXT, Inc.
        !            27:        Written by Bertrand Serlet, Dec 88
        !            28:        Responsibility: Bertrand Serlet
        !            29: */
        !            30: 
        !            31: #ifdef SHLIB
        !            32: #import "shlib.h"
        !            33: #endif SHLIB
        !            34: 
        !            35: #import <stdlib.h>
        !            36: #import <stdio.h>
        !            37: #import <string.h>
        !            38: #import "HashTable.h"
        !            39: #import "NXStringTable.h"
        !            40: #import "objc-private.h"
        !            41: 
        !            42: typedef struct {const void *key; void *value;} Pair;
        !            43: typedef        Pair    *Pairs;
        !            44: typedef struct {unsigned count; Pairs pairs;} Bucket;
        !            45: typedef        Bucket  *Buckets;
        !            46: 
        !            47: #define INITCAPA       1       /* _nbBuckets has to be a 2**N-1, and at least 1 */
        !            48: #define PAIRSSIZE(count) ((count) * sizeof(Pair))
        !            49: #define HASHSTR(str) (_objc_strhash (str))
        !            50: #define HASHINT(x) ((((unsigned) x) >> 16) ^ ((unsigned) x))
        !            51: 
        !            52: static unsigned log2 (unsigned x) { return (x<2) ? 0 : log2 (x>>1)+1; };
        !            53: 
        !            54: static unsigned exp2m1 (unsigned x) { return (1 << x) - 1; };
        !            55: 
        !            56: static unsigned hash (const char *keyDesc, const void *aKey, unsigned mod) {
        !            57:     switch (keyDesc[0]) {
        !            58:        case '@': return [(id) aKey hash] % mod;
        !            59:        case '%':
        !            60:        case '*': return aKey ? HASHSTR (aKey) % mod : 0;
        !            61:        default: return HASHINT (aKey) % mod;
        !            62:        };
        !            63:     };  
        !            64:     
        !            65: static unsigned isEqual (const char *keyDesc, const void *key1, const void *key2) {
        !            66:     if (key1 == key2) return YES;
        !            67:     switch (keyDesc[0]) {
        !            68:        case '@': return [(id) key1 isEqual: (id) key2];
        !            69:        case '%':
        !            70:        case '*':
        !            71:                if (! key1) return (strlen (key2) == 0);
        !            72:                if (! key2) return (strlen (key1) == 0);
        !            73:                if (((char *) key1)[0] != ((char *) key2)[0]) return NO;
        !            74:                return (strcmp (key1, key2) == 0);
        !            75:        default: return NO;
        !            76:        };
        !            77:     };
        !            78:     
        !            79: static void freeObject (void *item) {
        !            80:     [(id) item free];
        !            81:     };
        !            82:     
        !            83: static void noFree (void *item) {
        !            84:     };
        !            85:     
        !            86: @implementation  HashTable
        !            87: 
        !            88: + initialize
        !            89: {
        !            90:     [self setVersion: 1];
        !            91:     return self;
        !            92: }
        !            93: 
        !            94: - _initBare: (const char *) aKeyDesc : (const char *) aValueDesc : (unsigned) capacity
        !            95: /* used for efficient implementation of rehashing: does create a semi ok table */
        !            96: {
        !            97:     count = 0; _nbBuckets = capacity;
        !            98:     keyDesc = (aKeyDesc) ? aKeyDesc : "@"; 
        !            99:     valueDesc = (aValueDesc) ? aValueDesc : "@";
        !           100:     _buckets = nil;
        !           101:     return self;
        !           102: }
        !           103: 
        !           104: + _newBare: (const char *) aKeyDesc : (const char *) aValueDesc : (unsigned) capacity
        !           105: /* used for efficient implementation of rehashing: does create a semi ok table */
        !           106: {
        !           107:     return [[self allocFromZone: NXDefaultMallocZone()] 
        !           108:                _initBare:aKeyDesc:aValueDesc:capacity];
        !           109: }
        !           110: 
        !           111: - initKeyDesc: (const char *) aKeyDesc valueDesc: (const char *) aValueDesc
        !           112: {
        !           113:     return [self initKeyDesc: aKeyDesc valueDesc: aValueDesc capacity: INITCAPA];
        !           114: }
        !           115: 
        !           116: - initKeyDesc: (const char *) aKeyDesc
        !           117: {
        !           118:     return [self initKeyDesc: aKeyDesc valueDesc: NULL];
        !           119: }
        !           120: 
        !           121: - init
        !           122: {
        !           123:     return [self initKeyDesc: NULL];
        !           124: }
        !           125: - initKeyDesc: (const char *) aKeyDesc valueDesc: (const char *) aValueDesc capacity: (unsigned) aCapacity
        !           126: {
        !           127:     [self _initBare: aKeyDesc: aValueDesc: exp2m1 (log2 (aCapacity)+1)];
        !           128:     _buckets = NXZoneCalloc ([self zone], _nbBuckets, sizeof(Bucket));
        !           129:     return self;
        !           130: }
        !           131: 
        !           132: + newKeyDesc: (const char *) aKeyDesc valueDesc: (const char *) aValueDesc capacity: (unsigned) aCapacity
        !           133: {
        !           134:     return [[self allocFromZone: NXDefaultMallocZone()]
        !           135:        initKeyDesc:aKeyDesc valueDesc:aValueDesc capacity:aCapacity];
        !           136: }
        !           137: 
        !           138: + newKeyDesc: (const char *) aKeyDesc valueDesc: (const char *) aValueDesc
        !           139: {
        !           140:     return [self newKeyDesc: aKeyDesc valueDesc: aValueDesc capacity: INITCAPA];
        !           141: }
        !           142: 
        !           143: + newKeyDesc: (const char *) aKeyDesc
        !           144: {
        !           145:     return [self newKeyDesc: aKeyDesc valueDesc: NULL];
        !           146: }
        !           147: 
        !           148: + new
        !           149: {
        !           150:     return [self newKeyDesc: NULL];
        !           151: }
        !           152: 
        !           153: - free {
        !           154:     [self freeKeys: noFree values: noFree];
        !           155:     free(_buckets);
        !           156:     return [super free];
        !           157:     }
        !           158: 
        !           159: - freeObjects {
        !           160:     return [self 
        !           161:        freeKeys: (keyDesc[0] == '@') ? freeObject : noFree 
        !           162:        values: (valueDesc[0] == '@') ? freeObject : noFree 
        !           163:        ];
        !           164:     }
        !           165: 
        !           166: - freeKeys: (void (*) (void *)) keyFunc values: (void (*) (void *)) valueFunc {
        !           167:     unsigned   i = _nbBuckets;
        !           168:     Buckets    buckets = (Buckets) _buckets;
        !           169:     while (i--) {
        !           170:        if (buckets->count) {
        !           171:            unsigned    j = buckets->count;
        !           172:            Pairs       pairs = buckets->pairs;
        !           173:            while (j--) {
        !           174:                (*keyFunc) ((void *) pairs->key);
        !           175:                (*valueFunc) (pairs->value);
        !           176:                pairs++;
        !           177:                };
        !           178:            free(buckets->pairs);
        !           179:            buckets->count = 0;
        !           180:            buckets->pairs = (Pairs) nil;
        !           181:            };
        !           182:        buckets++;
        !           183:        };
        !           184:     count = 0;
        !           185:     return self;
        !           186:     };
        !           187:     
        !           188: - empty
        !           189: {
        !           190:     unsigned   i = _nbBuckets;
        !           191:     Buckets    buckets = (Buckets) _buckets;
        !           192:     while (i--) {
        !           193:        if (buckets->count) free(buckets->pairs);
        !           194:        buckets->count = 0;
        !           195:        buckets->pairs = NULL;
        !           196:        buckets++;
        !           197:        };
        !           198:     count = 0;
        !           199:     return self;
        !           200: }
        !           201: 
        !           202: 
        !           203: - copyFromZone:(NXZone *)zone
        !           204: /* we enumerate the table instead of blind copy to create a hash table of the right size */
        !           205: {
        !           206:     HashTable  *new = [[[self class] allocFromZone: zone] 
        !           207:                                           initKeyDesc: keyDesc
        !           208:                                                                            valueDesc: valueDesc
        !           209:                                                                             capacity: count];
        !           210:     NXHashState        state = [self initState];
        !           211:     const void *key;
        !           212:     void       *value;
        !           213:     while ([self nextState: &state key: &key value: &value])
        !           214:        [new insertKey: key value: value];
        !           215:     return new;
        !           216: }
        !           217: 
        !           218: - (unsigned) count
        !           219: {
        !           220:     return count;
        !           221: }
        !           222: 
        !           223: - (BOOL) isKey: (const void *) aKey
        !           224: {
        !           225:     Buckets    buckets = (Buckets) _buckets;
        !           226:     unsigned   index = hash (keyDesc, aKey, _nbBuckets);
        !           227:     Bucket     bucket = buckets[index];
        !           228:     unsigned   j = bucket.count;
        !           229:     Pairs      pairs;
        !           230:     if (j == 0) return NO;
        !           231:     pairs = bucket.pairs;
        !           232:     while (j--) {
        !           233:        if (isEqual (keyDesc, aKey, pairs->key)) return YES; 
        !           234:        pairs++;
        !           235:        };
        !           236:     return NO;
        !           237: }
        !           238: 
        !           239: - (void *) valueForKey: (const void *) aKey
        !           240: {
        !           241:     Buckets    buckets = (Buckets) _buckets;
        !           242:     unsigned   index = hash (keyDesc, aKey, _nbBuckets);
        !           243:     Bucket     bucket = buckets[index];
        !           244:     unsigned   j = bucket.count;
        !           245:     Pairs      pairs;
        !           246:     if (j == 0) return nil;
        !           247:     pairs = bucket.pairs;
        !           248:     while (j--) {
        !           249:        if (isEqual (keyDesc, aKey, pairs->key)) return pairs->value; 
        !           250:        pairs++;
        !           251:        };
        !           252:     return nil;
        !           253: }
        !           254: 
        !           255: - (void *) _insertKeyNoRehash: (const void *) aKey value: (void *) aValue
        !           256: {
        !           257:     Buckets    buckets = (Buckets) _buckets;
        !           258:     unsigned   index = hash (keyDesc, aKey, _nbBuckets);
        !           259:     Bucket     bucket = buckets[index];
        !           260:     unsigned   j = bucket.count;
        !           261:     Pairs      pairs = bucket.pairs;
        !           262:     Pairs      new;
        !           263:     while (j--) {
        !           264:        if (isEqual (keyDesc, aKey, pairs->key)) {
        !           265:                void    *old = pairs->value;
        !           266:                pairs->key = aKey;
        !           267:                pairs->value = aValue;
        !           268:                return old;
        !           269:                };
        !           270:        pairs++;
        !           271:        };
        !           272:     /* we enlarge this bucket; this could be optimized by using realloc */
        !           273:     new = (Pairs) NXZoneMalloc ([self zone], PAIRSSIZE(bucket.count+1));
        !           274:     if (bucket.count) bcopy (bucket.pairs, new+1, PAIRSSIZE(bucket.count));
        !           275:     new->key = aKey; new->value = aValue;
        !           276:     if (bucket.count) free (bucket.pairs);
        !           277:     buckets[index].count++; buckets[index].pairs = new; count++; 
        !           278:     return nil;
        !           279: }
        !           280: 
        !           281: - (void *) insertKey: (const void *) aKey value: (void *) aValue
        !           282: {
        !           283:     void       *result = [self _insertKeyNoRehash: aKey value: aValue];
        !           284:     if (result) return result; /* it was a replace */
        !           285:     if (count > _nbBuckets) {
        !           286:        /* Rehash: we create a pseudo table pointing really to the old guys,
        !           287:        extend self, copy the old pairs, and free the pseudo table */
        !           288:        HashTable       * old = [[HashTable allocFromZone: [self zone]]
        !           289:                             _initBare: keyDesc: valueDesc: _nbBuckets];
        !           290:         NXHashState    state;
        !           291:         const void     *key;
        !           292:        void            *value;
        !           293:        
        !           294:        old->count = count; old->_buckets = _buckets;
        !           295:        _nbBuckets += _nbBuckets + 1;
        !           296:        count = 0;
        !           297:        _buckets = NXZoneCalloc ([self zone], _nbBuckets, sizeof(Bucket));
        !           298:        state = [old initState];
        !           299:        while ([old nextState: &state key: &key value: &value])
        !           300:            [self insertKey: key value: value];
        !           301: #ifndef        KERNEL
        !           302:        if (old->count != count)
        !           303:            _NXLogError("*** HashTable: 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");
        !           304: #endif /* KERNEL */
        !           305:        [old free];
        !           306:        };
        !           307:     return nil;
        !           308: }
        !           309: 
        !           310: - (void *) removeKey: (const void *) aKey
        !           311: {
        !           312:     Buckets    buckets = (Buckets) _buckets;
        !           313:     unsigned   index = hash (keyDesc, aKey, _nbBuckets);
        !           314:     Bucket     bucket = buckets[index];
        !           315:     unsigned   j = bucket.count;
        !           316:     Pairs      pairs = bucket.pairs;
        !           317:     Pairs      new;
        !           318:     while (j--) {
        !           319:        if (isEqual (keyDesc, aKey, pairs->key)) {
        !           320:                /* we shrink this bucket; this could be optimized by using realloc */
        !           321:                void    *oldValue = pairs->value;
        !           322:                new = (bucket.count-1) ? (Pairs) NXZoneMalloc (
        !           323:                    [self zone], PAIRSSIZE(bucket.count-1)) : 0;
        !           324:                if (bucket.count-1 != j)
        !           325:                        bcopy (bucket.pairs, new, PAIRSSIZE(bucket.count-j-1));
        !           326:                if (j)
        !           327:                        bcopy (bucket.pairs+bucket.count-j, new+bucket.count-j-1,PAIRSSIZE (j));
        !           328:                free (bucket.pairs); 
        !           329:                count--; buckets[index].count--; buckets[index].pairs = new;
        !           330:                return oldValue;
        !           331:                };
        !           332:        pairs++;
        !           333:        };
        !           334:     return nil;
        !           335: }
        !           336: 
        !           337: - (NXHashState) initState {
        !           338:     NXHashState        state;
        !           339:     state.i = _nbBuckets;
        !           340:     state.j = 0;
        !           341:     return state;
        !           342:     };
        !           343:     
        !           344: - (BOOL) nextState: (NXHashState *) aState key: (const void **) aKey value: (void **) aValue
        !           345: {
        !           346:     Buckets    buckets = (Buckets) _buckets;
        !           347:     Pair       pair;
        !           348:     while (aState->j == 0) {
        !           349:        if (aState->i == 0)
        !           350:          {
        !           351:            *aKey = NULL; *aValue = NULL;
        !           352:            return NO;
        !           353:          }
        !           354:        aState->i--; aState->j = buckets[aState->i].count;
        !           355:        }
        !           356:     aState->j--;
        !           357:     pair = buckets[aState->i].pairs[aState->j];
        !           358:     *aKey = pair.key; *aValue = pair.value;
        !           359:     return YES;
        !           360: }
        !           361: 
        !           362: #ifndef        KERNEL
        !           363: - write:(NXTypedStream *) stream
        !           364: {
        !           365:     NXHashState                state = [self initState];
        !           366:     const void *key;
        !           367:     void       *value;
        !           368:     [super write: stream];
        !           369:     NXWriteTypes (stream, "i%%", &count, &keyDesc, &valueDesc);
        !           370:     while ([self nextState: &state key: &key value: &value]) {
        !           371:        NXWriteType (stream, keyDesc, &key);
        !           372:        NXWriteType (stream, valueDesc, &value);
        !           373:        };
        !           374:     return self;
        !           375:     }
        !           376: 
        !           377: - read:(NXTypedStream *) stream
        !           378: {
        !           379:     unsigned   nb; /* we set count as 0 but read nb elements */
        !           380:     if (NXTypedStreamClassVersion (stream, "HashTable") == 0) {
        !           381:         NXReadTypes (stream, "i**", &nb, &keyDesc, &valueDesc);
        !           382:     } else {
        !           383:        [super read: stream];
        !           384:         NXReadTypes (stream, "i%%", &nb, &keyDesc, &valueDesc);
        !           385:     }
        !           386:     if (! keyDesc) exit (1);
        !           387:     if (! valueDesc) exit (2);
        !           388:     count = 0;
        !           389:     _nbBuckets = exp2m1 (log2 (nb)+1);
        !           390:     _buckets = NXZoneCalloc ([self zone], _nbBuckets, sizeof(Bucket));
        !           391:     while (nb--) {
        !           392:        const void      *key;
        !           393:        void    *value;
        !           394:        NXReadType (stream, keyDesc, &key);
        !           395:        NXReadType (stream, valueDesc, &value);
        !           396:        [self _insertKeyNoRehash: key value: value];
        !           397:         };
        !           398:     return self;
        !           399:     }
        !           400: #else  /* KERNEL */
        !           401: - write:(NXTypedStream *) stream
        !           402: {
        !           403:     return nil;
        !           404: }
        !           405: - read:(NXTypedStream *) stream
        !           406: {
        !           407:     return nil;
        !           408: }
        !           409: #endif /* KERNEL */
        !           410: 
        !           411: static void DebugPrint (NXStream *stream, const char *desc, const void *data) {
        !           412:     switch (desc[0]) {
        !           413:        case '@': 
        !           414:            NXPrintf (stream, "%s[0x%x]", [(id) data name], (int) data);
        !           415:            return;
        !           416:        case 'i':
        !           417:            NXPrintf (stream, "%d[0x%x]", (int) data, (int) data);
        !           418:            return;
        !           419:        case '%':
        !           420:        case '*': 
        !           421:            NXPrintf (stream, "\"%s\"", (char *) data);
        !           422:            return;
        !           423:        default: 
        !           424:            NXPrintf (stream, "0x%x", (int) data);
        !           425:            return;
        !           426:        };
        !           427:     };  
        !           428: 
        !           429: - (void) printForDebugger:(NXStream *)stream
        !           430: {
        !           431:     unsigned   i = _nbBuckets;
        !           432:     Buckets    buckets = (Buckets) _buckets;
        !           433: 
        !           434:     NXPrintf (stream, "Table [%s -> %s]: \tcount: %d\tcapacity: %d\n", 
        !           435:        keyDesc, valueDesc, count, _nbBuckets);
        !           436:     while (i--) {
        !           437:        if (buckets->count) {
        !           438:            unsigned    j = buckets->count;
        !           439:            Pairs       pairs = buckets->pairs;
        !           440: 
        !           441:            NXPrintf (stream, "%d\t", j);
        !           442:            while (j--) {
        !           443:                DebugPrint (stream, keyDesc, pairs->key);
        !           444:                NXPrintf (stream, ": ");
        !           445:                DebugPrint (stream, valueDesc, pairs->value);
        !           446:                NXPrintf (stream, "\t");
        !           447:                pairs++;
        !           448:                };
        !           449:            NXPrintf (stream, "\n");
        !           450:            };
        !           451:        buckets++;
        !           452:        };
        !           453:     NXPrintf (stream, "\n");
        !           454:     NXFlush (stream);
        !           455: }
        !           456: 
        !           457: /* Obsolete (for binary compatibility only). */
        !           458: 
        !           459: - _debugPrint: (NXStream *) stream
        !           460: {
        !           461:   [self printForDebugger: stream];
        !           462:   return self;
        !           463: }
        !           464: 
        !           465: @end

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