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