runtime/hashtable2.mm

   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 #if !SUPPORT_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 /* Return interior pointer so a table of classes doesn't look like objects */
  61 #   define      ALLOCPAIRS(z,nb) (1+(const void **) calloc (nb+1, sizeof (void *)))
  62 #   define      FREEPAIRS(p) (free((void*)(-1+p)))
  63 #else
  64 #   define      DEFAULT_ZONE     malloc_default_zone()
  65 #   define      ZONE_FROM_PTR(p) malloc_zone_from_ptr(p)
  66 #   define      ALLOCTABLE(z)   ((NXHashTable *) malloc_zone_malloc ((malloc_zone_t *)z,sizeof (NXHashTable)))
  67 #   define      ALLOCBUCKETS(z,nb)((HashBucket *) malloc_zone_calloc ((malloc_zone_t *)z, nb, sizeof (HashBucket)))
  68 /* Return interior pointer so a table of classes doesn't look like objects */
  69 #   define      ALLOCPAIRS(z,nb) (1+(const void **) malloc_zone_calloc ((malloc_zone_t *)z, nb+1, sizeof (void *)))
  70 #   define      FREEPAIRS(p) (free((void*)(-1+p)))
  71 #endif
  72
  73 #if !SUPPORT_MOD
  74     /* nbBuckets must be a power of 2 */
  75 #   define BUCKETOF(table, data) (((HashBucket *)table->buckets)+((*table->prototype->hash)(table->info, data) & (table->nbBuckets-1)))
  76 #   define GOOD_CAPACITY(c) (c <= 1 ? 1 : 1 << (log2u (c-1)+1))
  77 #   define MORE_CAPACITY(b) (b*2)
  78 #else
  79     /* iff necessary this modulo can be optimized since the nbBuckets is of the form 2**n-1 */
  80 #   define      BUCKETOF(table, data) (((HashBucket *)table->buckets)+((*table->prototype->hash)(table->info, data) % table->nbBuckets))
  81     static unsigned exp2m1 (unsigned x) { return (1 << x) - 1; };
  82 #   define GOOD_CAPACITY(c) (exp2m1 (log2u (c)+1))
  83 #   define MORE_CAPACITY(b) (b*2+1)
  84 #endif
  85
  86 #define ISEQUAL(table, data1, data2) ((data1 == data2) || (*table->prototype->isEqual)(table->info, data1, data2))
  87         /* beware of double evaluation */
  88
  89 /*************************************************************************
  90  *
  91  *      Global data and bootstrap
  92  *
  93  *************************************************************************/
  94
  95 static int isEqualPrototype (const void *info, const void *data1, const void *data2) {
  96     NXHashTablePrototype        *proto1 = (NXHashTablePrototype *) data1;
  97     NXHashTablePrototype        *proto2 = (NXHashTablePrototype *) data2;
  98
  99     return (proto1->hash == proto2->hash) && (proto1->isEqual == proto2->isEqual) && (proto1->free == proto2->free) && (proto1->style == proto2->style);
 100     };
 101
 102 static uintptr_t hashPrototype (const void *info, const void *data) {
 103     NXHashTablePrototype        *proto = (NXHashTablePrototype *) data;
 104
 105     return NXPtrHash(info, (void*)proto->hash) ^ NXPtrHash(info, (void*)proto->isEqual) ^ NXPtrHash(info, (void*)proto->free) ^ (uintptr_t) proto->style;
 106     };
 107
 108 void NXNoEffectFree (const void *info, void *data) {};
 109
 110 static NXHashTablePrototype protoPrototype = {
 111     hashPrototype, isEqualPrototype, NXNoEffectFree, 0
 112     };
 113
 114 static NXHashTable *prototypes = NULL;
 115         /* table of all prototypes */
 116
 117 static void bootstrap (void) {
 118     free(malloc(8));
 119     prototypes = ALLOCTABLE (DEFAULT_ZONE);
 120     prototypes->prototype = &protoPrototype;
 121     prototypes->count = 1;
 122     prototypes->nbBuckets = 1; /* has to be 1 so that the right bucket is 0 */
 123     prototypes->buckets = ALLOCBUCKETS(DEFAULT_ZONE, 1);
 124     prototypes->info = NULL;
 125     ((HashBucket *) prototypes->buckets)[0].count = 1;
 126     ((HashBucket *) prototypes->buckets)[0].elements.one = &protoPrototype;
 127     };
 128
 129 int NXPtrIsEqual (const void *info, const void *data1, const void *data2) {
 130     return data1 == data2;
 131     };
 132
 133 /*************************************************************************
 134  *
 135  *      On z'y va
 136  *
 137  *************************************************************************/
 138
 139 NXHashTable *NXCreateHashTable (NXHashTablePrototype prototype, unsigned capacity, const void *info) {
 140     return NXCreateHashTableFromZone(prototype, capacity, info, DEFAULT_ZONE);
 141 }
 142
 143 NXHashTable *NXCreateHashTableFromZone (NXHashTablePrototype prototype, unsigned capacity, const void *info, void *z) {
 144     NXHashTable                 *table;
 145     NXHashTablePrototype        *proto;
 146
 147     table = ALLOCTABLE(z);
 148     if (! prototypes) bootstrap ();
 149     if (! prototype.hash) prototype.hash = NXPtrHash;
 150     if (! prototype.isEqual) prototype.isEqual = NXPtrIsEqual;
 151     if (! prototype.free) prototype.free = NXNoEffectFree;
 152     if (prototype.style) {
 153         _objc_inform ("*** NXCreateHashTable: invalid style\n");
 154         return NULL;
 155         };
 156     proto = (NXHashTablePrototype *)NXHashGet (prototypes, &prototype);
 157     if (! proto) {
 158         proto
 159             = (NXHashTablePrototype *) malloc(sizeof (NXHashTablePrototype));
 160         bcopy ((const char*)&prototype, (char*)proto, sizeof (NXHashTablePrototype));
 161         (void) NXHashInsert (prototypes, proto);
 162         proto = (NXHashTablePrototype *)NXHashGet (prototypes, &prototype);
 163         if (! proto) {
 164             _objc_inform ("*** NXCreateHashTable: bug\n");
 165             return NULL;
 166             };
 167         };
 168     table->prototype = proto; table->count = 0; table->info = info;
 169     table->nbBuckets = GOOD_CAPACITY(capacity);
 170     table->buckets = ALLOCBUCKETS(z, table->nbBuckets);
 171     return table;
 172     }
 173
 174 static void freeBucketPairs (void (*freeProc)(const void *info, void *data), HashBucket bucket, const void *info) {
 175     unsigned    j = bucket.count;
 176     const void  **pairs;
 177
 178     if (j == 1) {
 179         (*freeProc) (info, (void *) bucket.elements.one);
 180         return;
 181         };
 182     pairs = bucket.elements.many;
 183     while (j--) {
 184         (*freeProc) (info, (void *) *pairs);
 185         pairs ++;
 186         };
 187     FREEPAIRS (bucket.elements.many);
 188     };
 189
 190 static void freeBuckets (NXHashTable *table, int freeObjects) {
 191     unsigned            i = table->nbBuckets;
 192     HashBucket          *buckets = (HashBucket *) table->buckets;
 193
 194     while (i--) {
 195         if (buckets->count) {
 196             freeBucketPairs ((freeObjects) ? table->prototype->free : NXNoEffectFree, *buckets, table->info);
 197             buckets->count = 0;
 198             buckets->elements.one = NULL;
 199             };
 200         buckets++;
 201         };
 202     };
 203
 204 void NXFreeHashTable (NXHashTable *table) {
 205     freeBuckets (table, YES);
 206     free (table->buckets);
 207     free (table);
 208     };
 209
 210 void NXEmptyHashTable (NXHashTable *table) {
 211     freeBuckets (table, NO);
 212     table->count = 0;
 213     }
 214
 215 void NXResetHashTable (NXHashTable *table) {
 216     freeBuckets (table, YES);
 217     table->count = 0;
 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         *newt;
 235     NXHashState         state = NXInitHashState (table);
 236     void                *data;
 237     __unused void       *z = ZONE_FROM_PTR(table);
 238
 239     newt = ALLOCTABLE(z);
 240     newt->prototype = table->prototype; newt->count = 0;
 241     newt->info = table->info;
 242     newt->nbBuckets = table->nbBuckets;
 243     newt->buckets = ALLOCBUCKETS(z, newt->nbBuckets);
 244     while (NXNextHashState (table, &state, &data))
 245         NXHashInsert (newt, data);
 246     return newt;
 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 unsigned _NXHashCapacity (NXHashTable *table) {
 291     return table->nbBuckets;
 292     }
 293
 294 void _NXHashRehashToCapacity (NXHashTable *table, unsigned newCapacity) {
 295     /* Rehash: we create a pseudo table pointing really to the old guys,
 296     extend self, copy the old pairs, and free the pseudo table */
 297     NXHashTable *old;
 298     NXHashState state;
 299     void        *aux;
 300     __unused void *z = ZONE_FROM_PTR(table);
 301
 302     old = ALLOCTABLE(z);
 303     old->prototype = table->prototype; old->count = table->count;
 304     old->nbBuckets = table->nbBuckets; old->buckets = table->buckets;
 305     table->nbBuckets = newCapacity;
 306     table->count = 0; table->buckets = ALLOCBUCKETS(z, table->nbBuckets);
 307     state = NXInitHashState (old);
 308     while (NXNextHashState (old, &state, &aux))
 309         (void) NXHashInsert (table, aux);
 310     freeBuckets (old, NO);
 311     if (old->count != table->count)
 312         _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");
 313     free (old->buckets);
 314     free (old);
 315     }
 316
 317 static void _NXHashRehash (NXHashTable *table) {
 318     _NXHashRehashToCapacity (table, MORE_CAPACITY(table->nbBuckets));
 319     }
 320
 321 void *NXHashInsert (NXHashTable *table, const void *data) {
 322     HashBucket  *bucket = BUCKETOF(table, data);
 323     unsigned    j = bucket->count;
 324     const void  **pairs;
 325     const void  **newt;
 326     __unused void *z = ZONE_FROM_PTR(table);
 327
 328     if (! j) {
 329         bucket->count++; bucket->elements.one = data;
 330         table->count++;
 331         return NULL;
 332         };
 333     if (j == 1) {
 334         if (ISEQUAL(table, data, bucket->elements.one)) {
 335             const void  *old = bucket->elements.one;
 336             bucket->elements.one = data;
 337             return (void *) old;
 338             };
 339         newt = ALLOCPAIRS(z, 2);
 340         newt[1] = bucket->elements.one;
 341         *newt = data;
 342         bucket->count++; bucket->elements.many = newt;
 343         table->count++;
 344         if (table->count > table->nbBuckets) _NXHashRehash (table);
 345         return NULL;
 346         };
 347     pairs = bucket->elements.many;
 348     while (j--) {
 349         /* we don't cache isEqual because lists are short */
 350         if (ISEQUAL(table, data, *pairs)) {
 351             const void  *old = *pairs;
 352             *pairs = data;
 353             return (void *) old;
 354             };
 355         pairs ++;
 356         };
 357     /* we enlarge this bucket; and put new data in front */
 358     newt = ALLOCPAIRS(z, bucket->count+1);
 359     if (bucket->count) bcopy ((const char*)bucket->elements.many, (char*)(newt+1), bucket->count * PTRSIZE);
 360     *newt = data;
 361     FREEPAIRS (bucket->elements.many);
 362     bucket->count++; bucket->elements.many = newt;
 363     table->count++;
 364     if (table->count > table->nbBuckets) _NXHashRehash (table);
 365     return NULL;
 366     }
 367
 368 void *NXHashInsertIfAbsent (NXHashTable *table, const void *data) {
 369     HashBucket  *bucket = BUCKETOF(table, data);
 370     unsigned    j = bucket->count;
 371     const void  **pairs;
 372     const void  **newt;
 373     __unused void *z = ZONE_FROM_PTR(table);
 374
 375     if (! j) {
 376         bucket->count++; bucket->elements.one = data;
 377         table->count++;
 378         return (void *) data;
 379         };
 380     if (j == 1) {
 381         if (ISEQUAL(table, data, bucket->elements.one))
 382             return (void *) bucket->elements.one;
 383         newt = ALLOCPAIRS(z, 2);
 384         newt[1] = bucket->elements.one;
 385         *newt = data;
 386         bucket->count++; bucket->elements.many = newt;
 387         table->count++;
 388         if (table->count > table->nbBuckets) _NXHashRehash (table);
 389         return (void *) data;
 390         };
 391     pairs = bucket->elements.many;
 392     while (j--) {
 393         /* we don't cache isEqual because lists are short */
 394         if (ISEQUAL(table, data, *pairs))
 395             return (void *) *pairs;
 396         pairs ++;
 397         };
 398     /* we enlarge this bucket; and put new data in front */
 399     newt = ALLOCPAIRS(z, bucket->count+1);
 400     if (bucket->count) bcopy ((const char*)bucket->elements.many, (char*)(newt+1), bucket->count * PTRSIZE);
 401     *newt = data;
 402     FREEPAIRS (bucket->elements.many);
 403     bucket->count++; bucket->elements.many = newt;
 404     table->count++;
 405     if (table->count > table->nbBuckets) _NXHashRehash (table);
 406     return (void *) data;
 407     }
 408
 409 void *NXHashRemove (NXHashTable *table, const void *data) {
 410     HashBucket  *bucket = BUCKETOF(table, data);
 411     unsigned    j = bucket->count;
 412     const void  **pairs;
 413     const void  **newt;
 414     __unused void *z = ZONE_FROM_PTR(table);
 415
 416     if (! j) return NULL;
 417     if (j == 1) {
 418         if (! ISEQUAL(table, data, bucket->elements.one)) return NULL;
 419         data = bucket->elements.one;
 420         table->count--; bucket->count--; bucket->elements.one = NULL;
 421         return (void *) data;
 422         };
 423     pairs = bucket->elements.many;
 424     if (j == 2) {
 425         if (ISEQUAL(table, data, pairs[0])) {
 426             bucket->elements.one = pairs[1]; data = pairs[0];
 427             }
 428         else if (ISEQUAL(table, data, pairs[1])) {
 429             bucket->elements.one = pairs[0]; data = pairs[1];
 430             }
 431         else return NULL;
 432         FREEPAIRS (pairs);
 433         table->count--; bucket->count--;
 434         return (void *) data;
 435         };
 436     while (j--) {
 437         if (ISEQUAL(table, data, *pairs)) {
 438             data = *pairs;
 439             /* we shrink this bucket */
 440             newt = (bucket->count-1)
 441                 ? ALLOCPAIRS(z, bucket->count-1) : NULL;
 442             if (bucket->count-1 != j)
 443                     bcopy ((const char*)bucket->elements.many, (char*)newt, PTRSIZE*(bucket->count-j-1));
 444             if (j)
 445                     bcopy ((const char*)(bucket->elements.many + bucket->count-j), (char*)(newt+bucket->count-j-1), PTRSIZE*j);
 446             FREEPAIRS (bucket->elements.many);
 447             table->count--; bucket->count--; bucket->elements.many = newt;
 448             return (void *) data;
 449             };
 450         pairs ++;
 451         };
 452     return NULL;
 453     }
 454
 455 NXHashState NXInitHashState (NXHashTable *table) {
 456     NXHashState state;
 457
 458     state.i = table->nbBuckets;
 459     state.j = 0;
 460     return state;
 461     };
 462
 463 int NXNextHashState (NXHashTable *table, NXHashState *state, void **data) {
 464     HashBucket          *buckets = (HashBucket *) table->buckets;
 465
 466     while (state->j == 0) {
 467         if (state->i == 0) return NO;
 468         state->i--; state->j = buckets[state->i].count;
 469         }
 470     state->j--;
 471     buckets += state->i;
 472     *data = (void *) ((buckets->count == 1)
 473                 ? buckets->elements.one : buckets->elements.many[state->j]);
 474     return YES;
 475     };
 476
 477 /*************************************************************************
 478  *
 479  *      Conveniences
 480  *
 481  *************************************************************************/
 482
 483 uintptr_t NXPtrHash (const void *info, const void *data) {
 484     return (((uintptr_t) data) >> 16) ^ ((uintptr_t) data);
 485     };
 486
 487 uintptr_t NXStrHash (const void *info, const void *data) {
 488     register uintptr_t  hash = 0;
 489     register unsigned char      *s = (unsigned char *) data;
 490     /* unsigned to avoid a sign-extend */
 491     /* unroll the loop */
 492     if (s) for (; ; ) {
 493         if (*s == '\0') break;
 494         hash ^= (uintptr_t) *s++;
 495         if (*s == '\0') break;
 496         hash ^= (uintptr_t) *s++ << 8;
 497         if (*s == '\0') break;
 498         hash ^= (uintptr_t) *s++ << 16;
 499         if (*s == '\0') break;
 500         hash ^= (uintptr_t) *s++ << 24;
 501         }
 502     return hash;
 503     };
 504
 505 int NXStrIsEqual (const void *info, const void *data1, const void *data2) {
 506     if (data1 == data2) return YES;
 507     if (! data1) return ! strlen ((char *) data2);
 508     if (! data2) return ! strlen ((char *) data1);
 509     if (((char *) data1)[0] != ((char *) data2)[0]) return NO;
 510     return (strcmp ((char *) data1, (char *) data2)) ? NO : YES;
 511     };
 512
 513 void NXReallyFree (const void *info, void *data) {
 514     free (data);
 515     };
 516
 517 /* All the following functions are really private, made non-static only for the benefit of shlibs */
 518 static uintptr_t hashPtrStructKey (const void *info, const void *data) {
 519     return NXPtrHash(info, *((void **) data));
 520     };
 521
 522 static int isEqualPtrStructKey (const void *info, const void *data1, const void *data2) {
 523     return NXPtrIsEqual (info, *((void **) data1), *((void **) data2));
 524     };
 525
 526 static uintptr_t hashStrStructKey (const void *info, const void *data) {
 527     return NXStrHash(info, *((char **) data));
 528     };
 529
 530 static int isEqualStrStructKey (const void *info, const void *data1, const void *data2) {
 531     return NXStrIsEqual (info, *((char **) data1), *((char **) data2));
 532     };
 533
 534 const NXHashTablePrototype NXPtrPrototype = {
 535     NXPtrHash, NXPtrIsEqual, NXNoEffectFree, 0
 536     };
 537
 538 const NXHashTablePrototype NXStrPrototype = {
 539     NXStrHash, NXStrIsEqual, NXNoEffectFree, 0
 540     };
 541
 542 const NXHashTablePrototype NXPtrStructKeyPrototype = {
 543     hashPtrStructKey, isEqualPtrStructKey, NXReallyFree, 0
 544     };
 545
 546 const NXHashTablePrototype NXStrStructKeyPrototype = {
 547     hashStrStructKey, isEqualStrStructKey, NXReallyFree, 0
 548     };
 549
 550 /*************************************************************************
 551  *
 552  *      Unique strings
 553  *
 554  *************************************************************************/
 555
 556 #if !__OBJC2__  &&  !TARGET_OS_WIN32
 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 size_t   zSize = 0;
 568 static mutex_t          lock = MUTEX_INITIALIZER;
 569
 570 static const char *CopyIntoReadOnly (const char *str) {
 571     size_t      len = strlen (str) + 1;
 572     char        *result;
 573
 574     if (len > CHUNK_SIZE/2) {   /* dont let big strings waste space */
 575         result = (char *)malloc (len);
 576         bcopy (str, result, len);
 577         return result;
 578     }
 579
 580     mutex_lock (&lock);
 581     if (zSize < len) {
 582         zSize = CHUNK_SIZE *((len + CHUNK_SIZE - 1) / CHUNK_SIZE);
 583         /* not enough room, we try to allocate.  If no room left, too bad */
 584         z = (char *)malloc (zSize);
 585         };
 586
 587     result = z;
 588     bcopy (str, result, len);
 589     z += len;
 590     zSize -= len;
 591     mutex_unlock (&lock);
 592     return result;
 593     };
 594
 595 NXAtom NXUniqueString (const char *buffer) {
 596     const char  *previous;
 597
 598     if (! buffer) return buffer;
 599     accessUniqueString++;
 600     if (! uniqueStrings)
 601         uniqueStrings = NXCreateHashTable (NXStrPrototype, 0, NULL);
 602     previous = (const char *) NXHashGet (uniqueStrings, buffer);
 603     if (previous) return previous;
 604     previous = CopyIntoReadOnly (buffer);
 605     if (NXHashInsert (uniqueStrings, previous)) {
 606         _objc_inform ("*** NXUniqueString: invariant broken\n");
 607         return NULL;
 608         };
 609     return previous;
 610     };
 611
 612 NXAtom NXUniqueStringNoCopy (const char *string) {
 613     accessUniqueString++;
 614     if (! uniqueStrings)
 615         uniqueStrings = NXCreateHashTable (NXStrPrototype, 0, NULL);
 616     return (const char *) NXHashInsertIfAbsent (uniqueStrings, string);
 617     };
 618
 619 #define BUF_SIZE        256
 620
 621 NXAtom NXUniqueStringWithLength (const char *buffer, int length) {
 622     NXAtom      atom;
 623     char        *nullTermStr;
 624     char        stackBuf[BUF_SIZE];
 625
 626     if (length+1 > BUF_SIZE)
 627         nullTermStr = (char *)malloc (length+1);
 628     else
 629         nullTermStr = stackBuf;
 630     bcopy (buffer, nullTermStr, length);
 631     nullTermStr[length] = '\0';
 632     atom = NXUniqueString (nullTermStr);
 633     if (length+1 > BUF_SIZE)
 634         free (nullTermStr);
 635     return atom;
 636     };
 637
 638 char *NXCopyStringBufferFromZone (const char *str, void *zone) {
 639 #if !SUPPORT_ZONES
 640     return strdup(str);
 641 #else
 642     return strcpy ((char *) malloc_zone_malloc((malloc_zone_t *)zone, strlen (str) + 1), str);
 643 #endif
 644     };
 645
 646 char *NXCopyStringBuffer (const char *str) {
 647     return strdup(str);
 648     };
 649
 650 #endif