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