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 1989 NeXT, Inc.
        !            27:        Created by Bertrand Serlet, Feb 89
        !            28:  */
        !            29: 
        !            30: #ifdef SHLIB
        !            31: #import "shlib.h"
        !            32: #endif SHLIB
        !            33: 
        !            34: #import "hashtable.h"
        !            35: #import "objc-private.h"
        !            36: 
        !            37: #ifdef KERNEL
        !            38: 
        !            39: #else /* KERNEL */
        !            40: 
        !            41: #import <mach/mach.h>
        !            42: #import <mach/cthreads.h>
        !            43: 
        !            44: #endif /* KERNEL */
        !            45: 
        !            46: /* In order to improve efficiency, buckets contain a pointer to an array or directly the data when the array size is 1 */
        !            47: typedef union {
        !            48:     const void *one;
        !            49:     const void **many;
        !            50:     } oneOrMany;
        !            51:     /* an optimization consists of storing directly data when count = 1 */
        !            52:     
        !            53: typedef struct {
        !            54:     unsigned   count; 
        !            55:     oneOrMany  elements;
        !            56:     } HashBucket;
        !            57:     /* private data structure; may change */
        !            58:     
        !            59: /*************************************************************************
        !            60:  *
        !            61:  *     Macros and utilities
        !            62:  *     
        !            63:  *************************************************************************/
        !            64: 
        !            65: static unsigned log2 (unsigned x) { return (x<2) ? 0 : log2 (x>>1)+1; };
        !            66: 
        !            67: static unsigned exp2m1 (unsigned x) { return (1 << x) - 1; };
        !            68: 
        !            69: #define        PTRSIZE         sizeof(void *)
        !            70: 
        !            71: #define        ALLOCTABLE(z)   ((NXHashTable *) NXZoneMalloc (z,sizeof (NXHashTable)))
        !            72: #define        ALLOCBUCKETS(z,nb)((HashBucket *) NXZoneCalloc (z, nb, sizeof (HashBucket)))
        !            73: #define        ALLOCPAIRS(z,nb) ((const void **) NXZoneCalloc (z, nb, sizeof (void *)))
        !            74: 
        !            75: /* iff necessary this modulo can be optimized since the nbBuckets is of the form 2**n-1 */
        !            76: #define        BUCKETOF(table, data) (((HashBucket *)table->buckets)+((*table->prototype->hash)(table->info, data) % table->nbBuckets))
        !            77: 
        !            78: #define ISEQUAL(table, data1, data2) ((data1 == data2) || (*table->prototype->isEqual)(table->info, data1, data2))
        !            79:        /* beware of double evaluation */
        !            80:        
        !            81: /*************************************************************************
        !            82:  *
        !            83:  *     Global data and bootstrap
        !            84:  *     
        !            85:  *************************************************************************/
        !            86:  
        !            87: static unsigned hashPrototype (const void *info, const void *data) {
        !            88:     NXHashTablePrototype       *proto = (NXHashTablePrototype *) data;
        !            89:     
        !            90:     return NXPtrHash(info, proto->hash) ^ NXPtrHash(info, proto->isEqual) ^ NXPtrHash(info, proto->free) ^ (unsigned) proto->style;
        !            91:     };
        !            92: 
        !            93: static int isEqualPrototype (const void *info, const void *data1, const void *data2) {
        !            94:     NXHashTablePrototype       *proto1 = (NXHashTablePrototype *) data1;
        !            95:     NXHashTablePrototype       *proto2 = (NXHashTablePrototype *) data2;
        !            96:     
        !            97:     return (proto1->hash == proto2->hash) && (proto1->isEqual == proto2->isEqual) && (proto1->free == proto2->free) && (proto1->style == proto2->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: static void bootstrap (void) {
        !           108:     free(malloc(8));
        !           109:     prototypes = ALLOCTABLE (NXDefaultMallocZone());
        !           110:     prototypes->prototype = &protoPrototype; 
        !           111:     prototypes->count = 1;
        !           112:     prototypes->nbBuckets = 1; /* has to be 1 so that the right bucket is 0 */
        !           113:     prototypes->buckets = ALLOCBUCKETS(NXDefaultMallocZone(),  1);
        !           114:     prototypes->info = NULL;
        !           115:     ((HashBucket *) prototypes->buckets)[0].count = 1;
        !           116:     ((HashBucket *) prototypes->buckets)[0].elements.one = &protoPrototype;
        !           117:     };
        !           118: 
        !           119: /*************************************************************************
        !           120:  *
        !           121:  *     On z'y va
        !           122:  *     
        !           123:  *************************************************************************/
        !           124: 
        !           125: NXHashTable *NXCreateHashTable (NXHashTablePrototype prototype, unsigned capacity, const void *info) {
        !           126:     return NXCreateHashTableFromZone(prototype, capacity, info, NXDefaultMallocZone());
        !           127: }
        !           128: 
        !           129: NXHashTable *NXCreateHashTableFromZone (NXHashTablePrototype prototype, unsigned capacity, const void *info, NXZone *zone) {
        !           130:     NXHashTable                        *table;
        !           131:     NXHashTablePrototype       *proto;
        !           132:     
        !           133:     table = ALLOCTABLE(zone);
        !           134:     if (! prototypes) bootstrap ();
        !           135:     if (! prototype.hash) prototype.hash = NXPtrHash;
        !           136:     if (! prototype.isEqual) prototype.isEqual = NXPtrIsEqual;
        !           137:     if (! prototype.free) prototype.free = NXNoEffectFree;
        !           138:     if (prototype.style) {
        !           139:        _NXLogError ("*** NXCreateHashTable: invalid style\n");
        !           140:        return NULL;
        !           141:        };
        !           142:     proto = NXHashGet (prototypes, &prototype); 
        !           143:     if (! proto) {
        !           144:        proto
        !           145:        = (NXHashTablePrototype *) NXZoneMalloc (NXDefaultMallocZone(),
        !           146:                                                 sizeof (NXHashTablePrototype));
        !           147:        bcopy (&prototype, proto, sizeof (NXHashTablePrototype));
        !           148:        (void) NXHashInsert (prototypes, proto);
        !           149:        proto = NXHashGet (prototypes, &prototype);
        !           150:        if (! proto) {
        !           151:            _NXLogError ("*** NXCreateHashTable: bug\n");
        !           152:            return NULL;
        !           153:            };
        !           154:        };
        !           155:     table->prototype = proto; table->count = 0; table->info = info;
        !           156:     table->nbBuckets = exp2m1 (log2 (capacity)+1);
        !           157:     table->buckets = ALLOCBUCKETS(zone, table->nbBuckets);
        !           158:     return table;
        !           159:     }
        !           160: 
        !           161: static void freeBucketPairs (void (*freeProc)(const void *info, void *data), HashBucket bucket, const void *info) {
        !           162:     unsigned   j = bucket.count;
        !           163:     const void **pairs;
        !           164:     
        !           165:     if (j == 1) {
        !           166:        (*freeProc) (info, (void *) bucket.elements.one);
        !           167:        return;
        !           168:        };
        !           169:     pairs = bucket.elements.many;
        !           170:     while (j--) {
        !           171:        (*freeProc) (info, (void *) *pairs);
        !           172:        pairs ++;
        !           173:        };
        !           174:     free (bucket.elements.many);
        !           175:     };
        !           176:     
        !           177: static void freeBuckets (NXHashTable *table, int freeObjects) {
        !           178:     unsigned           i = table->nbBuckets;
        !           179:     HashBucket         *buckets = (HashBucket *) table->buckets;
        !           180:     
        !           181:     while (i--) {
        !           182:        if (buckets->count) {
        !           183:            freeBucketPairs ((freeObjects) ? table->prototype->free : NXNoEffectFree, *buckets, table->info);
        !           184:            buckets->count = 0;
        !           185:            buckets->elements.one = NULL;
        !           186:            };
        !           187:        buckets++;
        !           188:        };
        !           189:     };
        !           190:     
        !           191: void NXFreeHashTable (NXHashTable *table) {
        !           192:     freeBuckets (table, YES);
        !           193:     free (table->buckets);
        !           194:     free (table);
        !           195:     };
        !           196:     
        !           197: void NXEmptyHashTable (NXHashTable *table) {
        !           198:     freeBuckets (table, NO);
        !           199:     table->count = 0;
        !           200:     }
        !           201: 
        !           202: void NXResetHashTable (NXHashTable *table) {
        !           203:     freeBuckets (table, YES);
        !           204:     table->count = 0;
        !           205: }
        !           206: 
        !           207: BOOL NXIsEqualHashTable (NXHashTable *table1, NXHashTable *table2) {
        !           208:     if (table1 == table2) return YES;
        !           209:     if (NXCountHashTable (table1) != NXCountHashTable (table2)) return NO;
        !           210:     else {
        !           211:        void            *data;
        !           212:        NXHashState     state = NXInitHashState (table1);
        !           213:        while (NXNextHashState (table1, &state, &data)) {
        !           214:            if (! NXHashMember (table2, data)) return NO;
        !           215:        }
        !           216:        return YES;
        !           217:     }
        !           218: }
        !           219: 
        !           220: BOOL NXCompareHashTables (NXHashTable *table1, NXHashTable *table2) {
        !           221:     if (table1 == table2) return YES;
        !           222:     if (NXCountHashTable (table1) != NXCountHashTable (table2)) return NO;
        !           223:     else {
        !           224:        void            *data;
        !           225:        NXHashState     state = NXInitHashState (table1);
        !           226:        while (NXNextHashState (table1, &state, &data)) {
        !           227:            if (! NXHashMember (table2, data)) return NO;
        !           228:        }
        !           229:        return YES;
        !           230:     }
        !           231: }
        !           232: 
        !           233: NXHashTable *NXCopyHashTable (NXHashTable *table) {
        !           234:     NXHashTable                *new;
        !           235:     NXHashState                state = NXInitHashState (table);
        !           236:     void               *data;
        !           237:     NXZone             *zone = NXZoneFromPtr(table);
        !           238:     
        !           239:     new = ALLOCTABLE(zone);
        !           240:     new->prototype = table->prototype; new->count = 0;
        !           241:     new->info = table->info;
        !           242:     new->nbBuckets = table->nbBuckets;
        !           243:     new->buckets = ALLOCBUCKETS(zone, new->nbBuckets);
        !           244:     while (NXNextHashState (table, &state, &data))
        !           245:        (void) NXHashInsert (new, data);
        !           246:     return new;
        !           247:     }
        !           248: 
        !           249: unsigned NXCountHashTable (NXHashTable *table) {
        !           250:     return table->count;
        !           251:     }
        !           252: 
        !           253: int NXHashMember (NXHashTable *table, const void *data) {
        !           254:     HashBucket *bucket = BUCKETOF(table, data);
        !           255:     unsigned   j = bucket->count;
        !           256:     const void **pairs;
        !           257:     
        !           258:     if (! j) return 0;
        !           259:     if (j == 1) {
        !           260:        return ISEQUAL(table, data, bucket->elements.one);
        !           261:        };
        !           262:     pairs = bucket->elements.many;
        !           263:     while (j--) {
        !           264:        /* we don't cache isEqual because lists are short */
        !           265:        if (ISEQUAL(table, data, *pairs)) return 1; 
        !           266:        pairs ++;
        !           267:        };
        !           268:     return 0;
        !           269:     }
        !           270: 
        !           271: void *NXHashGet (NXHashTable *table, const void *data) {
        !           272:     HashBucket *bucket = BUCKETOF(table, data);
        !           273:     unsigned   j = bucket->count;
        !           274:     const void **pairs;
        !           275:     
        !           276:     if (! j) return NULL;
        !           277:     if (j == 1) {
        !           278:        return ISEQUAL(table, data, bucket->elements.one)
        !           279:            ? (void *) bucket->elements.one : NULL; 
        !           280:        };
        !           281:     pairs = bucket->elements.many;
        !           282:     while (j--) {
        !           283:        /* we don't cache isEqual because lists are short */
        !           284:        if (ISEQUAL(table, data, *pairs)) return (void *) *pairs; 
        !           285:        pairs ++;
        !           286:        };
        !           287:     return NULL;
        !           288:     }
        !           289: 
        !           290: static void _NXHashRehash (NXHashTable *table) {
        !           291:     /* Rehash: we create a pseudo table pointing really to the old guys,
        !           292:     extend self, copy the old pairs, and free the pseudo table */
        !           293:     NXHashTable        *old;
        !           294:     NXHashState        state;
        !           295:     void       *aux;
        !           296:     NXZone     *zone = NXZoneFromPtr(table);
        !           297:     
        !           298:     old = ALLOCTABLE(zone);
        !           299:     old->prototype = table->prototype; old->count = table->count; 
        !           300:     old->nbBuckets = table->nbBuckets; old->buckets = table->buckets;
        !           301:     table->nbBuckets += table->nbBuckets + 1; /* 2 times + 1 */
        !           302:     table->count = 0; table->buckets = ALLOCBUCKETS(zone, table->nbBuckets);
        !           303:     state = NXInitHashState (old);
        !           304:     while (NXNextHashState (old, &state, &aux))
        !           305:        (void) NXHashInsert (table, aux);
        !           306:     freeBuckets (old, NO);
        !           307:     if (old->count != table->count)
        !           308:        _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");
        !           309:     free (old->buckets); 
        !           310:     free (old);
        !           311:     };
        !           312: 
        !           313: void *NXHashInsert (NXHashTable *table, const void *data) {
        !           314:     HashBucket *bucket = BUCKETOF(table, data);
        !           315:     unsigned   j = bucket->count;
        !           316:     const void **pairs;
        !           317:     const void **new;
        !           318:     NXZone     *zone = NXZoneFromPtr(table);
        !           319:     
        !           320:     if (! j) {
        !           321:        bucket->count++; bucket->elements.one = data; 
        !           322:        table->count++; 
        !           323:        return NULL;
        !           324:        };
        !           325:     if (j == 1) {
        !           326:        if (ISEQUAL(table, data, bucket->elements.one)) {
        !           327:            const void  *old = bucket->elements.one;
        !           328:            bucket->elements.one = data;
        !           329:            return (void *) old;
        !           330:            };
        !           331:        new = ALLOCPAIRS(zone, 2);
        !           332:        new[1] = bucket->elements.one;
        !           333:        *new = data;
        !           334:        bucket->count++; bucket->elements.many = new; 
        !           335:        table->count++; 
        !           336:        if (table->count > table->nbBuckets) _NXHashRehash (table);
        !           337:        return NULL;
        !           338:        };
        !           339:     pairs = bucket->elements.many;
        !           340:     while (j--) {
        !           341:        /* we don't cache isEqual because lists are short */
        !           342:        if (ISEQUAL(table, data, *pairs)) {
        !           343:            const void  *old = *pairs;
        !           344:            *pairs = data;
        !           345:            return (void *) old;
        !           346:            };
        !           347:        pairs ++;
        !           348:        };
        !           349:     /* we enlarge this bucket; and put new data in front */
        !           350:     new = ALLOCPAIRS(zone, bucket->count+1);
        !           351:     if (bucket->count) bcopy (bucket->elements.many, new+1, bucket->count * PTRSIZE);
        !           352:     *new = data;
        !           353:     free (bucket->elements.many);
        !           354:     bucket->count++; bucket->elements.many = new; 
        !           355:     table->count++; 
        !           356:     if (table->count > table->nbBuckets) _NXHashRehash (table);
        !           357:     return NULL;
        !           358:     }
        !           359: 
        !           360: void *NXHashInsertIfAbsent (NXHashTable *table, const void *data) {
        !           361:     HashBucket *bucket = BUCKETOF(table, data);
        !           362:     unsigned   j = bucket->count;
        !           363:     const void **pairs;
        !           364:     const void **new;
        !           365:     NXZone     *zone = NXZoneFromPtr(table);
        !           366:     
        !           367:     if (! j) {
        !           368:        bucket->count++; bucket->elements.one = data; 
        !           369:        table->count++; 
        !           370:        return (void *) data;
        !           371:        };
        !           372:     if (j == 1) {
        !           373:        if (ISEQUAL(table, data, bucket->elements.one))
        !           374:            return (void *) bucket->elements.one;
        !           375:        new = ALLOCPAIRS(zone, 2);
        !           376:        new[1] = bucket->elements.one;
        !           377:        *new = data;
        !           378:        bucket->count++; bucket->elements.many = new; 
        !           379:        table->count++; 
        !           380:        if (table->count > table->nbBuckets) _NXHashRehash (table);
        !           381:        return (void *) data;
        !           382:        };
        !           383:     pairs = bucket->elements.many;
        !           384:     while (j--) {
        !           385:        /* we don't cache isEqual because lists are short */
        !           386:        if (ISEQUAL(table, data, *pairs))
        !           387:            return (void *) *pairs;
        !           388:        pairs ++;
        !           389:        };
        !           390:     /* we enlarge this bucket; and put new data in front */
        !           391:     new = ALLOCPAIRS(zone, bucket->count+1);
        !           392:     if (bucket->count) bcopy (bucket->elements.many, new+1, bucket->count * PTRSIZE);
        !           393:     *new = data;
        !           394:     free (bucket->elements.many);
        !           395:     bucket->count++; bucket->elements.many = new; 
        !           396:     table->count++; 
        !           397:     if (table->count > table->nbBuckets) _NXHashRehash (table);
        !           398:     return (void *) data;
        !           399:     }
        !           400: 
        !           401: void *NXHashRemove (NXHashTable *table, const void *data) {
        !           402:     HashBucket *bucket = BUCKETOF(table, data);
        !           403:     unsigned   j = bucket->count;
        !           404:     const void **pairs;
        !           405:     const void **new;
        !           406:     NXZone     *zone = NXZoneFromPtr(table);
        !           407:     
        !           408:     if (! j) return NULL;
        !           409:     if (j == 1) {
        !           410:        if (! ISEQUAL(table, data, bucket->elements.one)) return NULL;
        !           411:        data = bucket->elements.one;
        !           412:        table->count--; bucket->count--; bucket->elements.one = NULL;
        !           413:        return (void *) data;
        !           414:        };
        !           415:     pairs = bucket->elements.many;
        !           416:     if (j == 2) {
        !           417:        if (ISEQUAL(table, data, pairs[0])) {
        !           418:            bucket->elements.one = pairs[1]; data = pairs[0];
        !           419:            }
        !           420:        else if (ISEQUAL(table, data, pairs[1])) {
        !           421:            bucket->elements.one = pairs[0]; data = pairs[1];
        !           422:            }
        !           423:        else return NULL;
        !           424:        free (pairs);
        !           425:        table->count--; bucket->count--;
        !           426:        return (void *) data;
        !           427:        };
        !           428:     while (j--) {
        !           429:        if (ISEQUAL(table, data, *pairs)) {
        !           430:            data = *pairs;
        !           431:            /* we shrink this bucket */
        !           432:            new = (bucket->count-1) 
        !           433:                ? ALLOCPAIRS(zone, bucket->count-1) : NULL;
        !           434:            if (bucket->count-1 != j)
        !           435:                    bcopy (bucket->elements.many, new, PTRSIZE*(bucket->count-j-1));
        !           436:            if (j)
        !           437:                    bcopy (bucket->elements.many + bucket->count-j, new+bucket->count-j-1, PTRSIZE*j);
        !           438:            free (bucket->elements.many);
        !           439:            table->count--; bucket->count--; bucket->elements.many = new;
        !           440:            return (void *) data;
        !           441:            };
        !           442:        pairs ++;
        !           443:        };
        !           444:     return NULL;
        !           445:     }
        !           446: 
        !           447: NXHashState NXInitHashState (NXHashTable *table) {
        !           448:     NXHashState        state;
        !           449:     
        !           450:     state.i = table->nbBuckets;
        !           451:     state.j = 0;
        !           452:     return state;
        !           453:     };
        !           454:     
        !           455: int NXNextHashState (NXHashTable *table, NXHashState *state, void **data) {
        !           456:     HashBucket         *buckets = (HashBucket *) table->buckets;
        !           457:     
        !           458:     while (state->j == 0) {
        !           459:        if (state->i == 0) return NO;
        !           460:        state->i--; state->j = buckets[state->i].count;
        !           461:        }
        !           462:     state->j--;
        !           463:     buckets += state->i;
        !           464:     *data = (void *) ((buckets->count == 1) 
        !           465:                ? buckets->elements.one : buckets->elements.many[state->j]);
        !           466:     return YES;
        !           467:     };
        !           468: 
        !           469: /*************************************************************************
        !           470:  *
        !           471:  *     Conveniences
        !           472:  *     
        !           473:  *************************************************************************/
        !           474: 
        !           475: unsigned NXPtrHash (const void *info, const void *data) {
        !           476:     return (((unsigned) data) >> 16) ^ ((unsigned) data);
        !           477:     };
        !           478:     
        !           479: unsigned NXStrHash (const void *info, const void *data) {
        !           480:     register unsigned          hash = 0;
        !           481:     register unsigned char     *s = (unsigned char *) data;
        !           482:     /* unsigned to avoid a sign-extend */
        !           483:     /* unroll the loop */
        !           484:     if (s) for (; ; ) { 
        !           485:        if (*s == '\0') break;
        !           486:        hash ^= *s++;
        !           487:        if (*s == '\0') break;
        !           488:        hash ^= *s++ << 8;
        !           489:        if (*s == '\0') break;
        !           490:        hash ^= *s++ << 16;
        !           491:        if (*s == '\0') break;
        !           492:        hash ^= *s++ << 24;
        !           493:        }
        !           494:     return hash;
        !           495:     };
        !           496:     
        !           497: int NXPtrIsEqual (const void *info, const void *data1, const void *data2) {
        !           498:     return data1 == data2;
        !           499:     };
        !           500: 
        !           501: int NXStrIsEqual (const void *info, const void *data1, const void *data2) {
        !           502:     if (data1 == data2) return YES;
        !           503:     if (! data1) return ! strlen ((char *) data2);
        !           504:     if (! data2) return ! strlen ((char *) data1);
        !           505:     if (((char *) data1)[0] != ((char *) data2)[0]) return NO;
        !           506:     return (strcmp ((char *) data1, (char *) data2)) ? NO : YES;
        !           507:     };
        !           508:     
        !           509: void NXNoEffectFree (const void *info, void *data) {};
        !           510: 
        !           511: void NXReallyFree (const void *info, void *data) {
        !           512:     free (data);
        !           513:     };
        !           514: 
        !           515: /* All the following functions are really private, made non-static only for the benefit of shlibs */
        !           516: unsigned hashPtrStructKey (const void *info, const void *data) {
        !           517:     return NXPtrHash(info, *((void **) data));
        !           518:     };
        !           519: int isEqualPtrStructKey (const void *info, const void *data1, const void *data2) {
        !           520:     return NXPtrIsEqual (info, *((void **) data1), *((void **) data2));
        !           521:     };
        !           522: unsigned hashStrStructKey (const void *info, const void *data) {
        !           523:     return NXStrHash(info, *((char **) data));
        !           524:     };
        !           525: int isEqualStrStructKey (const void *info, const void *data1, const void *data2) {
        !           526:     return NXStrIsEqual (info, *((char **) data1), *((char **) data2));
        !           527:     };
        !           528: 
        !           529: 
        !           530: /*************************************************************************
        !           531:  *
        !           532:  *     Unique strings
        !           533:  *     
        !           534:  *************************************************************************/
        !           535: 
        !           536: /* the implementation could be made faster at the expense of memory if the size of the strings were kept around */
        !           537: static NXHashTable *uniqueStrings = NULL;
        !           538: 
        !           539: /* this is based on most apps using a few K of strings, and an average string size of 15 using sqrt(2*dataAlloced*perChunkOverhead) */
        !           540: #define CHUNK_SIZE     360
        !           541: 
        !           542: static int accessUniqueString = 0;
        !           543: 
        !           544: static char            *zone = NULL;
        !           545: static vm_size_t       zoneSize = 0;
        !           546: static mutex_t         lock = NULL;
        !           547: 
        !           548: static const char *CopyIntoReadOnly (const char *str) {
        !           549:     unsigned int       len = strlen (str) + 1;
        !           550:     char       *new;
        !           551:     
        !           552:     if (len > CHUNK_SIZE/2) {  /* dont let big strings waste space */
        !           553: #ifdef KERNEL
        !           554:        new = kalloc (len);
        !           555: #else /* KERNEL */
        !           556:        new = malloc (len);
        !           557: #endif /* KERNEL */
        !           558:        bcopy (str, new, len);
        !           559:        return new;
        !           560:     }
        !           561: 
        !           562:     if (! lock) {
        !           563:        lock = mutex_alloc ();
        !           564:        mutex_init (lock);
        !           565:        };
        !           566: 
        !           567:     mutex_lock (lock);
        !           568:     if (zoneSize < len) {
        !           569:        zoneSize = CHUNK_SIZE *((len + CHUNK_SIZE - 1) / CHUNK_SIZE);
        !           570:        /* not enough room, we try to allocate.  If no room left, too bad */
        !           571: #ifdef KERNEL
        !           572:        zone = kalloc (zoneSize);
        !           573: #else /* KERNEL */
        !           574:        zone = malloc (zoneSize);
        !           575: #endif /* KERNEL */
        !           576:        };
        !           577:     
        !           578:     new = zone;
        !           579:     bcopy (str, new, len);
        !           580:     zone += len;
        !           581:     zoneSize -= len;
        !           582:     mutex_unlock (lock);
        !           583:     return new;
        !           584:     };
        !           585:     
        !           586: NXAtom NXUniqueString (const char *buffer) {
        !           587:     const char *previous;
        !           588:     
        !           589:     if (! buffer) return buffer;
        !           590:     accessUniqueString++;
        !           591:     if (! uniqueStrings)
        !           592:        uniqueStrings = NXCreateHashTable (NXStrPrototype, 0, NULL);
        !           593:     previous = (const char *) NXHashGet (uniqueStrings, buffer);
        !           594:     if (previous) return previous;
        !           595:     previous = CopyIntoReadOnly (buffer);
        !           596:     if (NXHashInsert (uniqueStrings, previous)) {
        !           597:        _NXLogError ("*** NXUniqueString: invariant broken\n");
        !           598:        return NULL;
        !           599:        };
        !           600:     return previous;
        !           601:     };
        !           602: 
        !           603: NXAtom NXUniqueStringNoCopy (const char *string) {
        !           604:     accessUniqueString++;
        !           605:     if (! uniqueStrings)
        !           606:        uniqueStrings = NXCreateHashTable (NXStrPrototype, 0, NULL);
        !           607:     return (const char *) NXHashInsertIfAbsent (uniqueStrings, string);
        !           608:     };
        !           609: 
        !           610: #define BUF_SIZE       256
        !           611: 
        !           612: NXAtom NXUniqueStringWithLength (const char *buffer, int length) {
        !           613:     NXAtom     atom;
        !           614:     char       *nullTermStr;
        !           615:     char       stackBuf[BUF_SIZE];
        !           616: 
        !           617:     if (length+1 > BUF_SIZE)
        !           618:        nullTermStr = malloc (length+1);
        !           619:     else
        !           620:        nullTermStr = stackBuf;
        !           621:     bcopy (buffer, nullTermStr, length);
        !           622:     nullTermStr[length] = '\0';
        !           623:     atom = NXUniqueString (nullTermStr);
        !           624:     if (length+1 > BUF_SIZE)
        !           625:        free (nullTermStr);
        !           626:     return atom;
        !           627:     };
        !           628: 
        !           629: char *NXCopyStringBufferFromZone (const char *str, NXZone *zone) {
        !           630:     return strcpy ((char *) NXZoneMalloc (zone, strlen (str) + 1), str);
        !           631:     };
        !           632:     
        !           633: char *NXCopyStringBuffer (const char *str) {
        !           634:     return NXCopyStringBufferFromZone(str, NXDefaultMallocZone());
        !           635:     };
        !           636:     
        !           637: #if 0  /* Never used! */
        !           638: static void uniqueStringsStatistics (void) {
        !           639:     unsigned   i = uniqueStrings->nbBuckets;
        !           640:     HashBucket *buckets = (HashBucket *) uniqueStrings->buckets;
        !           641:     
        !           642:     printf ("Size: %d\tcount: %d\taccesses: %d\n", i, uniqueStrings->count, accessUniqueString);
        !           643:     while (i--) {
        !           644:        if (buckets->count) {
        !           645:            if (buckets->count == 1)
        !           646:                printf ("1\t%s\n", (char *) buckets->elements.one);
        !           647:            else {
        !           648:                int     j = buckets->count;
        !           649:                char    **pairs = (char **) buckets->elements.many;
        !           650:                printf ("%d\t", buckets->count);
        !           651:                while (j--) printf ("%s ", *(pairs++));
        !           652:                printf ("\n");
        !           653:                };
        !           654:            };
        !           655:        buckets++;
        !           656:        };
        !           657:     };
        !           658: #endif

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