runtime/hashtable2.m

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