runtime/hashtable2.m

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