CFBasicHash.m

   1 /*
   2  * Copyright (c) 2010 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 /*      CFBasicHash.m
  25         Copyright (c) 2008-2009, Apple Inc. All rights reserved.
  26         Responsibility: Christopher Kane
  27 */
  28
  29 #import "CFBasicHash.h"
  30 #import <CoreFoundation/CFRuntime.h>
  31 #import <CoreFoundation/CFSet.h>
  32 #import <Block.h>
  33 #import <objc/objc.h>
  34 #import <math.h>
  35
  36 #if DEPLOYMENT_TARGET_WINDOWS
  37 #define __SetLastAllocationEventName(A, B) do { } while (0)
  38 #else
  39 #define __SetLastAllocationEventName(A, B) do { if (__CFOASafe && (A)) __CFSetLastAllocationEventName(A, B); } while (0)
  40 #endif
  41
  42 #define GCRETAIN(A, B) kCFTypeSetCallBacks.retain(A, B)
  43 #define GCRELEASE(A, B) kCFTypeSetCallBacks.release(A, B)
  44
  45 #define __AssignWithWriteBarrier(location, value) objc_assign_strongCast((id)value, (id *)location)
  46
  47 #define ENABLE_DTRACE_PROBES 0
  48 #define ENABLE_MEMORY_COUNTERS 0
  49
  50
  51 /*
  52 // dtrace -h -s foo.d
  53 // Note: output then changed by putting do/while around macro bodies and adding a cast of the arguments
  54
  55 provider Cocoa_HashTable {
  56         probe hash_key(unsigned long table, unsigned long key, unsigned long hash);
  57         probe test_equal(unsigned long table, unsigned long key1, unsigned long key2);
  58         probe probing_start(unsigned long table, unsigned long num_buckets);
  59         probe probe_empty(unsigned long table, unsigned long idx);
  60         probe probe_deleted(unsigned long table, unsigned long idx);
  61         probe probe_valid(unsigned long table, unsigned long idx);
  62         probe probing_end(unsigned long table, unsigned long num_probes);
  63         probe rehash_start(unsigned long table, unsigned long num_buckets, unsigned long total_size);
  64         probe rehash_end(unsigned long table, unsigned long num_buckets, unsigned long total_size);
  65 };
  66
  67 #pragma D attributes Unstable/Unstable/Common provider Cocoa_HashTable provider
  68 #pragma D attributes Private/Private/Unknown provider Cocoa_HashTable module
  69 #pragma D attributes Private/Private/Unknown provider Cocoa_HashTable function
  70 #pragma D attributes Unstable/Unstable/Common provider Cocoa_HashTable name
  71 #pragma D attributes Unstable/Unstable/Common provider Cocoa_HashTable args
  72 */
  73
  74 #if ENABLE_DTRACE_PROBES
  75
  76 #define COCOA_HASHTABLE_STABILITY "___dtrace_stability$Cocoa_HashTable$v1$4_4_5_1_1_0_1_1_0_4_4_5_4_4_5"
  77
  78 #define COCOA_HASHTABLE_TYPEDEFS "___dtrace_typedefs$Cocoa_HashTable$v2"
  79
  80 #define COCOA_HASHTABLE_REHASH_END(arg0, arg1, arg2) \
  81 do { \
  82         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
  83         __dtrace_probe$Cocoa_HashTable$rehash_end$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1), (unsigned long)(arg2)); \
  84         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
  85 } while (0)
  86 #define COCOA_HASHTABLE_REHASH_END_ENABLED() \
  87         __dtrace_isenabled$Cocoa_HashTable$rehash_end$v1()
  88 #define COCOA_HASHTABLE_REHASH_START(arg0, arg1, arg2) \
  89 do { \
  90         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
  91         __dtrace_probe$Cocoa_HashTable$rehash_start$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1), (unsigned long)(arg2)); \
  92         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
  93 } while (0)
  94 #define COCOA_HASHTABLE_REHASH_START_ENABLED() \
  95         __dtrace_isenabled$Cocoa_HashTable$rehash_start$v1()
  96 #define COCOA_HASHTABLE_HASH_KEY(arg0, arg1, arg2) \
  97 do { \
  98         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
  99         __dtrace_probe$Cocoa_HashTable$hash_key$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1), (unsigned long)(arg2)); \
 100         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
 101 } while (0)
 102 #define COCOA_HASHTABLE_HASH_KEY_ENABLED() \
 103         __dtrace_isenabled$Cocoa_HashTable$hash_key$v1()
 104 #define COCOA_HASHTABLE_PROBE_DELETED(arg0, arg1) \
 105 do { \
 106         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
 107         __dtrace_probe$Cocoa_HashTable$probe_deleted$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1)); \
 108         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
 109 } while (0)
 110 #define COCOA_HASHTABLE_PROBE_DELETED_ENABLED() \
 111         __dtrace_isenabled$Cocoa_HashTable$probe_deleted$v1()
 112 #define COCOA_HASHTABLE_PROBE_EMPTY(arg0, arg1) \
 113 do { \
 114         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
 115         __dtrace_probe$Cocoa_HashTable$probe_empty$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1)); \
 116         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
 117 } while (0)
 118 #define COCOA_HASHTABLE_PROBE_EMPTY_ENABLED() \
 119         __dtrace_isenabled$Cocoa_HashTable$probe_empty$v1()
 120 #define COCOA_HASHTABLE_PROBE_VALID(arg0, arg1) \
 121 do { \
 122         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
 123         __dtrace_probe$Cocoa_HashTable$probe_valid$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1)); \
 124         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
 125 } while (0)
 126 #define COCOA_HASHTABLE_PROBE_VALID_ENABLED() \
 127         __dtrace_isenabled$Cocoa_HashTable$probe_valid$v1()
 128 #define COCOA_HASHTABLE_PROBING_END(arg0, arg1) \
 129 do { \
 130         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
 131         __dtrace_probe$Cocoa_HashTable$probing_end$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1)); \
 132         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
 133 } while (0)
 134 #define COCOA_HASHTABLE_PROBING_END_ENABLED() \
 135         __dtrace_isenabled$Cocoa_HashTable$probing_end$v1()
 136 #define COCOA_HASHTABLE_PROBING_START(arg0, arg1) \
 137 do { \
 138         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
 139         __dtrace_probe$Cocoa_HashTable$probing_start$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1)); \
 140         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
 141 } while (0)
 142 #define COCOA_HASHTABLE_PROBING_START_ENABLED() \
 143         __dtrace_isenabled$Cocoa_HashTable$probing_start$v1()
 144 #define COCOA_HASHTABLE_TEST_EQUAL(arg0, arg1, arg2) \
 145 do { \
 146         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
 147         __dtrace_probe$Cocoa_HashTable$test_equal$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1), (unsigned long)(arg2)); \
 148         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
 149 } while (0)
 150 #define COCOA_HASHTABLE_TEST_EQUAL_ENABLED() \
 151         __dtrace_isenabled$Cocoa_HashTable$test_equal$v1()
 152
 153 extern void __dtrace_probe$Cocoa_HashTable$rehash_end$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long, unsigned long);
 154 extern int __dtrace_isenabled$Cocoa_HashTable$rehash_end$v1(void);
 155 extern void __dtrace_probe$Cocoa_HashTable$rehash_start$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long, unsigned long);
 156 extern int __dtrace_isenabled$Cocoa_HashTable$rehash_start$v1(void);
 157 extern void __dtrace_probe$Cocoa_HashTable$hash_key$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long, unsigned long);
 158 extern int __dtrace_isenabled$Cocoa_HashTable$hash_key$v1(void);
 159 extern void __dtrace_probe$Cocoa_HashTable$probe_deleted$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long);
 160 extern int __dtrace_isenabled$Cocoa_HashTable$probe_deleted$v1(void);
 161 extern void __dtrace_probe$Cocoa_HashTable$probe_empty$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long);
 162 extern int __dtrace_isenabled$Cocoa_HashTable$probe_empty$v1(void);
 163 extern void __dtrace_probe$Cocoa_HashTable$probe_valid$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long);
 164 extern int __dtrace_isenabled$Cocoa_HashTable$probe_valid$v1(void);
 165 extern void __dtrace_probe$Cocoa_HashTable$probing_end$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long);
 166 extern int __dtrace_isenabled$Cocoa_HashTable$probing_end$v1(void);
 167 extern void __dtrace_probe$Cocoa_HashTable$probing_start$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long);
 168 extern int __dtrace_isenabled$Cocoa_HashTable$probing_start$v1(void);
 169 extern void __dtrace_probe$Cocoa_HashTable$test_equal$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long, unsigned long);
 170 extern int __dtrace_isenabled$Cocoa_HashTable$test_equal$v1(void);
 171
 172 #else
 173
 174 #define COCOA_HASHTABLE_REHASH_END(arg0, arg1, arg2) do {} while (0)
 175 #define COCOA_HASHTABLE_REHASH_END_ENABLED() 0
 176 #define COCOA_HASHTABLE_REHASH_START(arg0, arg1, arg2) do {} while (0)
 177 #define COCOA_HASHTABLE_REHASH_START_ENABLED() 0
 178 #define COCOA_HASHTABLE_HASH_KEY(arg0, arg1, arg2) do {} while (0)
 179 #define COCOA_HASHTABLE_HASH_KEY_ENABLED() 0
 180 #define COCOA_HASHTABLE_PROBE_DELETED(arg0, arg1) do {} while (0)
 181 #define COCOA_HASHTABLE_PROBE_DELETED_ENABLED() 0
 182 #define COCOA_HASHTABLE_PROBE_EMPTY(arg0, arg1) do {} while (0)
 183 #define COCOA_HASHTABLE_PROBE_EMPTY_ENABLED() 0
 184 #define COCOA_HASHTABLE_PROBE_VALID(arg0, arg1) do {} while (0)
 185 #define COCOA_HASHTABLE_PROBE_VALID_ENABLED() 0
 186 #define COCOA_HASHTABLE_PROBING_END(arg0, arg1) do {} while (0)
 187 #define COCOA_HASHTABLE_PROBING_END_ENABLED() 0
 188 #define COCOA_HASHTABLE_PROBING_START(arg0, arg1) do {} while (0)
 189 #define COCOA_HASHTABLE_PROBING_START_ENABLED() 0
 190 #define COCOA_HASHTABLE_TEST_EQUAL(arg0, arg1, arg2) do {} while (0)
 191 #define COCOA_HASHTABLE_TEST_EQUAL_ENABLED() 0
 192
 193 #endif
 194
 195
 196 #if !defined(__LP64__)
 197 #define __LP64__ 0
 198 #endif
 199
 200 enum {
 201 #if __LP64__
 202     __CFBasicHashMarkerShift = 40 // 64 - 24
 203 #else
 204     __CFBasicHashMarkerShift = 8  // 32 - 24
 205 #endif
 206 };
 207
 208 typedef union {
 209     uintptr_t weak;
 210     id strong;
 211 } CFBasicHashValue;
 212
 213 struct __CFBasicHash {
 214     CFRuntimeBase base;
 215     struct { // 128 bits
 216         uint64_t hash_style:2;
 217         uint64_t values2_offset:1;
 218         uint64_t keys_offset:2;
 219         uint64_t keys2_offset:2;
 220         uint64_t counts_offset:3;
 221         uint64_t orders_offset:3;
 222         uint64_t hashes_offset:3;
 223         uint64_t num_buckets_idx:6; /* index to number of buckets */
 224         uint64_t used_buckets:42;   /* number of used buckets */
 225         uint64_t __0:2;
 226         uint64_t finalized:1;
 227         uint64_t fast_grow:1;
 228         uint64_t strong_values:1;
 229         uint64_t strong_values2:1;
 230         uint64_t strong_keys:1;
 231         uint64_t strong_keys2:1;
 232         uint64_t marker:24;
 233         uint64_t deleted:16;
 234         uint64_t mutations:16;
 235     } bits;
 236     __strong const CFBasicHashCallbacks *callbacks;
 237     void *pointers[1];
 238 };
 239
 240 CF_INLINE CFBasicHashValue *__CFBasicHashGetValues(CFBasicHashRef ht) {
 241     return (CFBasicHashValue *)ht->pointers[0];
 242 }
 243
 244 CF_INLINE void __CFBasicHashSetValues(CFBasicHashRef ht, CFBasicHashValue *ptr) {
 245     __AssignWithWriteBarrier(&ht->pointers[0], ptr);
 246 }
 247
 248 CF_INLINE CFBasicHashValue *__CFBasicHashGetValues2(CFBasicHashRef ht) {
 249     if (0 == ht->bits.values2_offset) HALT;
 250     return (CFBasicHashValue *)ht->pointers[ht->bits.values2_offset];
 251 }
 252
 253 CF_INLINE void __CFBasicHashSetValues2(CFBasicHashRef ht, CFBasicHashValue *ptr) {
 254     if (0 == ht->bits.values2_offset) HALT;
 255     __AssignWithWriteBarrier(&ht->pointers[ht->bits.values2_offset], ptr);
 256 }
 257
 258 CF_INLINE CFBasicHashValue *__CFBasicHashGetKeys(CFBasicHashRef ht) {
 259     if (0 == ht->bits.keys_offset) HALT;
 260     return (CFBasicHashValue *)ht->pointers[ht->bits.keys_offset];
 261 }
 262
 263 CF_INLINE void __CFBasicHashSetKeys(CFBasicHashRef ht, CFBasicHashValue *ptr) {
 264     if (0 == ht->bits.keys_offset) HALT;
 265     __AssignWithWriteBarrier(&ht->pointers[ht->bits.keys_offset], ptr);
 266 }
 267
 268 CF_INLINE CFBasicHashValue *__CFBasicHashGetKeys2(CFBasicHashRef ht) {
 269     if (0 == ht->bits.keys2_offset) HALT;
 270     return (CFBasicHashValue *)ht->pointers[ht->bits.keys2_offset];
 271 }
 272
 273 CF_INLINE void __CFBasicHashSetKeys2(CFBasicHashRef ht, CFBasicHashValue *ptr) {
 274     if (0 == ht->bits.keys2_offset) HALT;
 275     __AssignWithWriteBarrier(&ht->pointers[ht->bits.keys2_offset], ptr);
 276 }
 277
 278 CF_INLINE uintptr_t *__CFBasicHashGetCounts(CFBasicHashRef ht) {
 279     if (0 == ht->bits.counts_offset) HALT;
 280     return (uintptr_t *)ht->pointers[ht->bits.counts_offset];
 281 }
 282
 283 CF_INLINE void __CFBasicHashSetCounts(CFBasicHashRef ht, uintptr_t *ptr) {
 284     if (0 == ht->bits.counts_offset) HALT;
 285     __AssignWithWriteBarrier(&ht->pointers[ht->bits.counts_offset], ptr);
 286 }
 287
 288 CF_INLINE uintptr_t *__CFBasicHashGetOrders(CFBasicHashRef ht) {
 289     if (0 == ht->bits.orders_offset) HALT;
 290     return (uintptr_t *)ht->pointers[ht->bits.orders_offset];
 291 }
 292
 293 CF_INLINE void __CFBasicHashSetOrders(CFBasicHashRef ht, uintptr_t *ptr) {
 294     if (0 == ht->bits.orders_offset) HALT;
 295     __AssignWithWriteBarrier(&ht->pointers[ht->bits.orders_offset], ptr);
 296 }
 297
 298 CF_INLINE uintptr_t *__CFBasicHashGetHashes(CFBasicHashRef ht) {
 299     if (0 == ht->bits.hashes_offset) HALT;
 300     return (uintptr_t *)ht->pointers[ht->bits.hashes_offset];
 301 }
 302
 303 CF_INLINE void __CFBasicHashSetHashes(CFBasicHashRef ht, uintptr_t *ptr) {
 304     if (0 == ht->bits.hashes_offset) HALT;
 305     __AssignWithWriteBarrier(&ht->pointers[ht->bits.hashes_offset], ptr);
 306 }
 307
 308 static uintptr_t __CFBasicHashNullCallback(CFBasicHashRef ht, uint8_t op, uintptr_t a1, uintptr_t a2, const CFBasicHashCallbacks *cb) {
 309     switch (op) {
 310     case kCFBasicHashCallbackOpCopyCallbacks: return (uintptr_t)&CFBasicHashNullCallbacks;
 311     case kCFBasicHashCallbackOpFreeCallbacks: return 0;
 312     case kCFBasicHashCallbackOpRetainValue:
 313     case kCFBasicHashCallbackOpRetainValue2:
 314     case kCFBasicHashCallbackOpRetainKey:
 315     case kCFBasicHashCallbackOpRetainKey2:   return a1;
 316     case kCFBasicHashCallbackOpReleaseValue:
 317     case kCFBasicHashCallbackOpReleaseValue2:
 318     case kCFBasicHashCallbackOpReleaseKey:
 319     case kCFBasicHashCallbackOpReleaseKey2:  return 0;
 320     case kCFBasicHashCallbackOpValueEqual:
 321     case kCFBasicHashCallbackOpValue2Equal:
 322     case kCFBasicHashCallbackOpKeyEqual:
 323     case kCFBasicHashCallbackOpKey2Equal:    return a1 == a2;
 324     case kCFBasicHashCallbackOpHashKey:
 325     case kCFBasicHashCallbackOpHashKey2:     return a1;
 326     case kCFBasicHashCallbackOpDescribeValue:
 327     case kCFBasicHashCallbackOpDescribeValue2:
 328     case kCFBasicHashCallbackOpDescribeKey:
 329     case kCFBasicHashCallbackOpDescribeKey2: return (uintptr_t)CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<%p>"), (void *)a1);
 330     }
 331     return 0;
 332 }
 333
 334 static uintptr_t __CFBasicHashStandardCallback(CFBasicHashRef ht, uint8_t op, uintptr_t a1, uintptr_t a2, const CFBasicHashCallbacks *cb) {
 335     switch (op) {
 336     case kCFBasicHashCallbackOpCopyCallbacks: return (uintptr_t)&CFBasicHashStandardCallbacks;
 337     case kCFBasicHashCallbackOpFreeCallbacks: return 0;
 338     case kCFBasicHashCallbackOpRetainValue:   return (ht->bits.strong_values) ? (uintptr_t)GCRETAIN(kCFAllocatorSystemDefault, (CFTypeRef)a1) : (uintptr_t)CFRetain((CFTypeRef)a1);
 339     case kCFBasicHashCallbackOpRetainValue2:  return (ht->bits.strong_values2) ? (uintptr_t)GCRETAIN(kCFAllocatorSystemDefault, (CFTypeRef)a1) : (uintptr_t)CFRetain((CFTypeRef)a1);
 340     case kCFBasicHashCallbackOpRetainKey:     return (ht->bits.strong_keys) ? (uintptr_t)GCRETAIN(kCFAllocatorSystemDefault, (CFTypeRef)a1) : (uintptr_t)CFRetain((CFTypeRef)a1);
 341     case kCFBasicHashCallbackOpRetainKey2:    return (ht->bits.strong_keys2) ? (uintptr_t)GCRETAIN(kCFAllocatorSystemDefault, (CFTypeRef)a1) : (uintptr_t)CFRetain((CFTypeRef)a1);
 342     case kCFBasicHashCallbackOpReleaseValue:  if (ht->bits.strong_values) GCRELEASE(kCFAllocatorSystemDefault, (CFTypeRef)a1); else CFRelease((CFTypeRef)a1); return 0;
 343     case kCFBasicHashCallbackOpReleaseValue2: if (ht->bits.strong_values2) GCRELEASE(kCFAllocatorSystemDefault, (CFTypeRef)a1); else CFRelease((CFTypeRef)a1); return 0;
 344     case kCFBasicHashCallbackOpReleaseKey:    if (ht->bits.strong_keys) GCRELEASE(kCFAllocatorSystemDefault, (CFTypeRef)a1); else CFRelease((CFTypeRef)a1); return 0;
 345     case kCFBasicHashCallbackOpReleaseKey2:   if (ht->bits.strong_keys2) GCRELEASE(kCFAllocatorSystemDefault, (CFTypeRef)a1); else CFRelease((CFTypeRef)a1); return 0;
 346     case kCFBasicHashCallbackOpValueEqual:
 347     case kCFBasicHashCallbackOpValue2Equal:
 348     case kCFBasicHashCallbackOpKeyEqual:
 349     case kCFBasicHashCallbackOpKey2Equal:     return CFEqual((CFTypeRef)a1, (CFTypeRef)a2);
 350     case kCFBasicHashCallbackOpHashKey:
 351     case kCFBasicHashCallbackOpHashKey2:      return (uintptr_t)CFHash((CFTypeRef)a1);
 352     case kCFBasicHashCallbackOpDescribeValue:
 353     case kCFBasicHashCallbackOpDescribeValue2:
 354     case kCFBasicHashCallbackOpDescribeKey:
 355     case kCFBasicHashCallbackOpDescribeKey2:  return (uintptr_t)CFCopyDescription((CFTypeRef)a1);
 356     }
 357     return 0;
 358 }
 359
 360 __private_extern__ const CFBasicHashCallbacks CFBasicHashNullCallbacks = {__CFBasicHashNullCallback};
 361 __private_extern__ const CFBasicHashCallbacks CFBasicHashStandardCallbacks = {__CFBasicHashStandardCallback};
 362
 363 CF_INLINE uintptr_t __CFBasicHashImportValue(CFBasicHashRef ht, uintptr_t stack_value) {
 364     return ht->callbacks->func(ht, kCFBasicHashCallbackOpRetainValue, stack_value, 0, ht->callbacks);
 365 }
 366
 367 CF_INLINE uintptr_t __CFBasicHashImportValue2(CFBasicHashRef ht, uintptr_t stack_value) {
 368     return ht->callbacks->func(ht, kCFBasicHashCallbackOpRetainValue2, stack_value, 0, ht->callbacks);
 369 }
 370
 371 CF_INLINE uintptr_t __CFBasicHashImportKey(CFBasicHashRef ht, uintptr_t stack_key) {
 372     return ht->callbacks->func(ht, kCFBasicHashCallbackOpRetainKey, stack_key, 0, ht->callbacks);
 373 }
 374
 375 CF_INLINE uintptr_t __CFBasicHashImportKey2(CFBasicHashRef ht, uintptr_t stack_key) {
 376     return ht->callbacks->func(ht, kCFBasicHashCallbackOpRetainKey2, stack_key, 0, ht->callbacks);
 377 }
 378
 379 CF_INLINE void __CFBasicHashEjectValue(CFBasicHashRef ht, uintptr_t stack_value) {
 380     ht->callbacks->func(ht, kCFBasicHashCallbackOpReleaseValue, stack_value, 0, ht->callbacks);
 381 }
 382
 383 CF_INLINE void __CFBasicHashEjectValue2(CFBasicHashRef ht, uintptr_t stack_value) {
 384     ht->callbacks->func(ht, kCFBasicHashCallbackOpReleaseValue2, stack_value, 0, ht->callbacks);
 385 }
 386
 387 CF_INLINE void __CFBasicHashEjectKey(CFBasicHashRef ht, uintptr_t stack_key) {
 388     ht->callbacks->func(ht, kCFBasicHashCallbackOpReleaseKey, stack_key, 0, ht->callbacks);
 389 }
 390
 391 CF_INLINE void __CFBasicHashEjectKey2(CFBasicHashRef ht, uintptr_t stack_key) {
 392     ht->callbacks->func(ht, kCFBasicHashCallbackOpReleaseKey2, stack_key, 0, ht->callbacks);
 393 }
 394
 395 CF_INLINE Boolean __CFBasicHashTestEqualValue(CFBasicHashRef ht, uintptr_t stack_value_a, uintptr_t stack_value_b) {
 396     return (Boolean)ht->callbacks->func(ht, kCFBasicHashCallbackOpValueEqual, stack_value_a, stack_value_b, ht->callbacks);
 397 }
 398
 399 CF_INLINE Boolean __CFBasicHashTestEqualValue2(CFBasicHashRef ht, uintptr_t stack_value_a, uintptr_t stack_value_b) {
 400     return (Boolean)ht->callbacks->func(ht, kCFBasicHashCallbackOpValue2Equal, stack_value_a, stack_value_b, ht->callbacks);
 401 }
 402
 403 CF_INLINE Boolean __CFBasicHashTestEqualKey(CFBasicHashRef ht, uintptr_t stack_key_a, uintptr_t stack_key_b) {
 404     COCOA_HASHTABLE_TEST_EQUAL(ht, stack_key_a, stack_key_b);
 405     return (Boolean)ht->callbacks->func(ht, kCFBasicHashCallbackOpKeyEqual, stack_key_a, stack_key_b, ht->callbacks);
 406 }
 407
 408 CF_INLINE Boolean __CFBasicHashTestEqualKey2(CFBasicHashRef ht, uintptr_t stack_key_a, uintptr_t stack_key_b) {
 409     COCOA_HASHTABLE_TEST_EQUAL(ht, stack_key_a, stack_key_b);
 410     return (Boolean)ht->callbacks->func(ht, kCFBasicHashCallbackOpKey2Equal, stack_key_a, stack_key_b, ht->callbacks);
 411 }
 412
 413 CF_INLINE CFHashCode __CFBasicHashHashKey(CFBasicHashRef ht, uintptr_t stack_key) {
 414     CFHashCode hash_code = (CFHashCode)ht->callbacks->func(ht, kCFBasicHashCallbackOpHashKey, stack_key, 0, ht->callbacks);
 415     COCOA_HASHTABLE_HASH_KEY(ht, stack_key, hash_code);
 416     return hash_code;
 417 }
 418
 419 CF_INLINE CFHashCode __CFBasicHashHashKey2(CFBasicHashRef ht, uintptr_t stack_key) {
 420     CFHashCode hash_code = (CFHashCode)ht->callbacks->func(ht, kCFBasicHashCallbackOpHashKey2, stack_key, 0, ht->callbacks);
 421     COCOA_HASHTABLE_HASH_KEY(ht, stack_key, hash_code);
 422     return hash_code;
 423 }
 424
 425 CF_INLINE void *__CFBasicHashAllocateMemory(CFBasicHashRef ht, CFIndex count, CFIndex elem_size, Boolean strong) {
 426     CFAllocatorRef allocator = CFGetAllocator(ht);
 427     void *new_mem = NULL;
 428     if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 429         new_mem = auto_zone_allocate_object(auto_zone(), count * elem_size, strong ? AUTO_MEMORY_SCANNED : AUTO_UNSCANNED, false, false);
 430     } else {
 431         new_mem = CFAllocatorAllocate(allocator, count * elem_size, 0);
 432     }
 433     if (!new_mem) HALT;
 434     return new_mem;
 435 }
 436
 437
 438 // Prime numbers. Values above 100 have been adjusted up so that the
 439 // malloced block size will be just below a multiple of 512; values
 440 // above 1200 have been adjusted up to just below a multiple of 4096.
 441 static const uintptr_t __CFBasicHashTableSizes[64] = {
 442     0, 3, 7, 13, 23, 41, 71, 127, 191, 251, 383, 631, 1087, 1723,
 443     2803, 4523, 7351, 11959, 19447, 31231, 50683, 81919, 132607,
 444     214519, 346607, 561109, 907759, 1468927, 2376191, 3845119,
 445     6221311, 10066421, 16287743, 26354171, 42641881, 68996069,
 446     111638519, 180634607, 292272623, 472907251,
 447 #if __LP64__
 448     765180413UL, 1238087663UL, 2003267557UL, 3241355263UL, 5244622819UL,
 449     8485977589UL, 13730600407UL, 22216578047UL, 35947178479UL,
 450     58163756537UL, 94110934997UL, 152274691561UL, 246385626107UL,
 451     398660317687UL, 645045943807UL, 1043706260983UL, 1688752204787UL,
 452     2732458465769UL, 4421210670577UL, 7153669136377UL,
 453     11574879807461UL, 18728548943849UL, 30303428750843UL
 454 #endif
 455 };
 456
 457 // Primitive roots for the primes above
 458 static const uintptr_t __CFBasicHashPrimitiveRoots[64] = {
 459     0, 2, 3, 2, 5, 6, 7, 3, 19, 6, 5, 3, 3, 3,
 460     2, 5, 6, 3, 3, 6, 2, 3, 3,
 461     3, 5, 10, 3, 3, 22, 3,
 462     3, 3, 5, 2, 22, 2,
 463     11, 5, 5, 2,
 464 #if __LP64__
 465     3, 10, 2, 3, 10,
 466     2, 3, 5, 3,
 467     3, 2, 7, 2,
 468     3, 3, 3, 2,
 469     3, 5, 5,
 470     2, 3, 2
 471 #endif
 472 };
 473
 474 /* Primitive roots under 100 for the primes above
 475 3: 2
 476 7: 3 5
 477 13: 2 6 7 11
 478 23: 5 7 10 11 14 15 17 19 20 21
 479 41: 6 7 11 12 13 15 17 19 22 24 26 28 29 30 34 35
 480 71: 7 11 13 21 22 28 31 33 35 42 44 47 52 53 55 56 59 61 62 63 65 67 68 69
 481 127: 3 6 7 12 14 23 29 39 43 45 46 48 53 55 56 57 58 65 67 78 83 85 86 91 92 93 96 97
 482 191: 19 21 22 28 29 33 35 42 44 47 53 56 57 58 61 62 63 71 73 74 76 83 87 88 89 91 93 94 95 99
 483 251: 6 11 14 18 19 24 26 29 30 33 34 37 42 43 44 46 53 54 55 56 57 59 61 62 70 71 72 76 77 78 82 87 90 95 96 97 98 99
 484 383: 5 10 11 13 15 20 22 26 30 33 35 37 39 40 41 44 45 47 52 53 59 60 61 66 70 74 77 78 79 80 82 83 85 88 89 90 91 94 95 97 99
 485 631: 3 7 12 13 14 15 19 26 51 53 54 56 59 60 61 63 65 70 75 76 87 93 95 96 99
 486 1087: 3 10 12 13 14 20 22 24 28 29 31 38 44 45 46 51 52 53 54 58 59 61 62 63 67 74 75 76 80 89 90 92 94 96 97 99
 487 1723: 3 12 17 18 29 30 38 45 46 48 55 63 74 75 77 78 82 83 86 88 94 95
 488 2803: 2 11 12 18 20 21 29 30 32 34 35 38 41 46 48 50 52 56 66 67 74 78 79 80 83 84 86 91 93 94 98 99
 489 4523: 5 6 7 15 18 20 22 24 26 31 34 41 45 54 55 57 60 65 66 70 72 74 76 77 83 85 88 93 94 96 98
 490 7351: 6 7 12 15 17 22 28 31 35 38 44 52 54 55 56 60 65 69 71 75 96
 491 11959: 3 6 12 24 29 33 37 39 41 47 48 51 53 57 58 59 66 67 69 73 74 75 78 82 94 96
 492 19447: 3 5 6 7 10 12 14 20 23 24 28 29 37 39 45 46 47 51 55 56 58 65 71 73 74 75 78 79 80 82 83 90 91 92 94 96
 493 31231: 6 7 24 29 30 33 41 43 48 52 53 54 56 57 59 60 62 65 69 70 73 75 77 83 86
 494 50683: 2 3 12 14 17 18 20 32 33 35 39 41 45 50 55 56 57 58 61 62 65 68 69 71 72 74 75 80 84 86 88 93 95
 495 81919: 3 12 23 24 26 30 33 43 52 53 54 57 59 60 65 66 75 84 86 87 91 92 93 96 97
 496 132607: 3 5 6 17 19 20 21 23 24 26 29 33 34 35 38 40 42 45 48 52 54 61 62 67 71 73 75 79 82 86 89 90 92
 497 214519: 3 7 12 15 19 24 26 28 30 33 35 38 41 52 54 56 61 65 69 70 73 77 86 87 89 93 96 97
 498 346607: 5 10 14 15 17 19 20 21 28 30 34 38 40 41 42 45 51 55 56 57 59 60 63 65 67 68 76 77 80 82 84 89 90 91 97
 499 561109: 10 11 18 21 26 30 33 35 38 40 41 43 46 47 50 51 53 61 62 72 73 74 84 85 91 96
 500 907759: 3 6 12 13 17 24 26 33 34 41 47 48 52 57 61 66 68 71 75 79 82 87 89 93 94
 501 1468927: 3 5 6 11 20 21 22 23 24 26 35 40 42 45 48 51 52 54 58 71 73 75 77 79 86 88 90 92 93 94 95
 502 2376191: 22 29 31 33 37 43 44 47 55 58 59 62 66 77 86 87 88 93 99
 503 3845119: 3 11 12 13 15 23 24 30 37 42 43 44 51 52 53 54 55 57 65 73 84 86 87 88 89 92 94 96 97
 504 6221311: 3 12 13 15 21 24 30 31 33 46 54 57 61 66 67 74 82 84 87 89 91 92 96
 505 10066421: 3 10 11 12 17 18 19 21 23 27 39 40 41 48 50 56 58 60 61 66 68 71 72 73 74 75 76 77 83 85 86 87 92 94 95 97
 506 16287743: 5 10 15 20 30 31 35 40 43 45 47 53 55 59 60 61 62 65 70 73 79 80 85 86 89 90 93 94 95
 507 26354171: 2 6 7 8 10 17 18 21 22 23 24 26 30 35 38 40 50 51 53 59 62 63 66 67 68 69 71 72 74 77 78 83 84 85 87 88 90 91 96 98
 508 42641881: 22 31 38 44 46 57 59 62 67 69 73 76 77 83 92 99
 509 68996069: 2 3 8 10 11 12 14 15 17 18 21 26 27 32 37 38 40 43 44 46 47 48 50 53 55 56 58 60 61 62 66 67 68 69 70 72 75 77 82 84 85 87 89 90 93 98 99
 510 111638519: 11 13 17 22 26 29 33 34 39 41 44 51 52 53 55 58 59 61 65 66 67 68 71 77 78 79 82 83 85 87 88 91 97 99
 511 180634607: 5 10 15 19 20 23 30 31 35 37 38 40 43 45 46 47 55 57 60 62 65 69 70 74 76 79 80 85 86 89 90 92 93 94
 512 292272623: 5 10 11 13 15 20 22 23 26 30 31 33 35 39 40 44 45 46 47 52 59 60 61 62 66 67 69 70 71 77 78 79 80 83 85 88 90 91 92 93 94 95 97 99
 513 472907251: 2 10 12 14 17 18 29 31 37 46 50 60 61 65 68 70 78 82 84 85 90 91 94 98
 514 765180413: 3 5 11 12 14 18 20 21 23 26 27 29 30 34 35 38 39 44 45 47 48 50 51 56 57 59 62 66 67 71 72 73 74 75 77 80 82 84 85 86 89 92 93 95 97 98 99
 515 1238087663: 10 13 14 15 20 21 23 28 38 40 41 42 43 45 46 52 55 56 57 60 63 67 69 71 76 78 80 82 84 85 86 89 90 92
 516 2003267557: 2 13 14 18 20 22 23 24 31 32 34 37 38 41 43 47 50 54 59 60 67 69 79 80 85 87 91 93 96
 517 3241355263: 3 6 10 11 20 21 22 24 34 42 43 45 46 48 54 57 61 65 68 70 71 75 77 78 80 83 86 87 88 92 93 94
 518 5244622819: 10 15 17 23 29 31 35 38 40 50 57 60 65 67 68 71 73 74 75 79 90 92 94
 519 8485977589: 2 6 10 17 18 19 22 28 30 31 32 35 37 40 47 51 52 54 57 58 59 61 65 66 76 77 79 84 85 86 88 90 93 96 98
 520 13730600407: 3 5 10 12 19 24 33 35 40 42 43 45 46 51 54 55 65 73 75 76 78 80 82 84 87 89 92 93 94 96
 521 22216578047: 5 10 11 15 17 20 22 30 33 34 35 40 44 45 51 59 60 61 65 66 68 70 73 77 79 80 88 90 95 99
 522 35947178479: 3 12 14 15 22 24 29 30 38 41 44 51 54 55 56 58 63 69 70 73 76 78 89 91 95 96 97 99
 523 58163756537: 3 5 6 7 10 11 12 14 17 20 22 23 24 27 28 31 39 40 43 44 45 46 47 48 53 54 56 57 59 61 62 63 65 68 71 73 75 78 79 80 86 87 88 89 90 91 92 94 95 96 97 99
 524 94110934997: 2 3 5 8 11 12 14 18 19 20 21 23 26 27 29 30 32 34 35 39 41 43 44 48 51 56 59 62 66 67 71 72 74 75 76 77 79 80 84 85 92 93 94 98 99
 525 152274691561: 7 17 26 35 37 39 41 42 43 53 56 62 63 65 67 74 82 84 85 89 93 94
 526 246385626107UL: 2 5 6 8 11 14 15 18 20 23 24 26 29 31 32 33 34 35 37 38 42 43 44 45 50 54 56 60 61 65 67 69 71 72 77 78 80 82 83 85 87 89 92 93 94 95 96 98 99
 527 398660317687UL: 3 5 6 7 11 13 20 24 26 28 40 44 45 48 54 56 59 63 69 75 79 85 88 89 90 93 95 99
 528 645045943807UL: 3 5 10 12 21 22 23 24 26 35 37 40 41 44 45 47 51 52 53 59 70 75 79 85 87 92 93 95 96 97 99
 529 1043706260983UL: 3 7 11 24 28 29 (<= 32)
 530 1688752204787UL: 2 5 6 7 8 13 18 20 21 22 23 24 28 32 (<= 32)
 531 2732458465769UL: 3 6 11 12 13 15 17 19 21 22 23 24 26 27 30 31 (<= 32)
 532 4421210670577UL: 5 (<= 9)
 533
 534 */
 535
 536 static const uintptr_t __CFBasicHashTableCapacities[64] = {
 537     0, 3, 6, 11, 19, 32, 52, 85, 118, 155, 237, 390, 672, 1065,
 538     1732, 2795, 4543, 7391, 12019, 19302, 31324, 50629, 81956,
 539     132580, 214215, 346784, 561026, 907847, 1468567, 2376414,
 540     3844982, 6221390, 10066379, 16287773, 26354132, 42641916,
 541     68996399, 111638327, 180634415, 292272755,
 542 #if __LP64__
 543     472907503UL, 765180257UL, 1238087439UL, 2003267722UL, 3241355160UL,
 544     5244622578UL, 8485977737UL, 13730600347UL, 22216578100UL,
 545     35947178453UL, 58163756541UL, 94110935011UL, 152274691274UL,
 546     246385626296UL, 398660317578UL, 645045943559UL, 1043706261135UL,
 547     1688752204693UL, 2732458465840UL, 4421210670552UL,
 548     7153669136706UL, 11574879807265UL, 18728548943682UL
 549 #endif
 550 };
 551
 552 // to expose the load factor, expose this function to customization
 553 CF_INLINE CFIndex __CFBasicHashGetCapacityForNumBuckets(CFBasicHashRef ht, CFIndex num_buckets_idx) {
 554     return __CFBasicHashTableCapacities[num_buckets_idx];
 555 #if 0
 556     CFIndex num_buckets = __CFBasicHashTableSizes[num_buckets_idx];
 557     if (num_buckets_idx < 8) {
 558         double dep = 0.0545665730357293074; // (1 - (sqrt(5) - 1) / 2) / 7
 559         double factor = 1.0 - (num_buckets_idx - 1) * dep;
 560         return (CFIndex)floor(num_buckets * factor + 0.375); // 0.375 is intentional
 561     }
 562     double factor = 0.6180339887498948482; // (sqrt(5) - 1) / 2
 563     return (CFIndex)floor(num_buckets * factor + 0.5);
 564 #endif
 565 }
 566
 567 CF_INLINE CFIndex __CFBasicHashGetNumBucketsIndexForCapacity(CFBasicHashRef ht, CFIndex capacity) {
 568     for (CFIndex idx = 0; idx < 64; idx++) {
 569         if (capacity <= __CFBasicHashGetCapacityForNumBuckets(ht, idx)) return idx;
 570     }
 571     HALT;
 572     return 0;
 573 }
 574
 575 __private_extern__ CFIndex CFBasicHashGetNumBuckets(CFBasicHashRef ht) {
 576     return __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 577 }
 578
 579 __private_extern__ CFIndex CFBasicHashGetCapacity(CFBasicHashRef ht) {
 580     return __CFBasicHashGetCapacityForNumBuckets(ht, ht->bits.num_buckets_idx);
 581 }
 582
 583 // In returned struct, .count is zero if the bucket is empty or deleted,
 584 // and the .weak_key field indicates which. .idx is either the index of
 585 // the found bucket or the index of the bucket which should be filled by
 586 // an add operation. For a set or multiset, the .weak_key and .weak_value
 587 // are the same.
 588 __private_extern__ CFBasicHashBucket CFBasicHashGetBucket(CFBasicHashRef ht, CFIndex idx) {
 589     uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
 590     CFBasicHashBucket result;
 591     result.idx = idx;
 592     result.weak_value = __CFBasicHashGetValues(ht)[idx].weak;
 593     result.weak_value2 = (0 != ht->bits.values2_offset) ? __CFBasicHashGetValues2(ht)[idx].weak : 0;
 594     result.weak_key = (0 != ht->bits.keys_offset) ? __CFBasicHashGetKeys(ht)[idx].weak : result.weak_value;
 595     result.weak_key2 = (0 != ht->bits.keys2_offset) ? __CFBasicHashGetKeys2(ht)[idx].weak : 0;
 596     result.count = (0 != ht->bits.counts_offset) ? __CFBasicHashGetCounts(ht)[idx] : ((result.weak_key == empty || result.weak_key == deleted) ? 0 : 1);
 597     result.order = (0 != ht->bits.orders_offset) ? __CFBasicHashGetOrders(ht)[idx] : 0;
 598     return result;
 599 }
 600
 601 // During rehashing of a mutable CFBasicHash, we know that there are no
 602 // deleted slots and the keys have already been uniqued. When rehashing,
 603 // if key_hash is non-0, we use it as the hash code.
 604 static CFBasicHashBucket ___CFBasicHashFindBucket1(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t key_hash, Boolean rehashing) {
 605     CFHashCode hash_code = key_hash ? key_hash : __CFBasicHashHashKey(ht, stack_key);
 606     uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
 607     CFBasicHashValue *keys = (0 != ht->bits.keys_offset) ? __CFBasicHashGetKeys(ht) : __CFBasicHashGetValues(ht);
 608     uintptr_t *hashes = (0 != ht->bits.hashes_offset) ? __CFBasicHashGetHashes(ht) : NULL;
 609     uintptr_t num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 610     CFBasicHashBucket result = {kCFNotFound, deleted, 0, deleted, 0, 0, 0};
 611
 612     uintptr_t h1 = 0;
 613         // Linear probing, with c = 1
 614         // probe[0] = h1(k)
 615         // probe[i] = (h1(k) + i * c) mod num_buckets, i = 1 .. num_buckets - 1
 616         // h1(k) = k mod num_buckets
 617         h1 = hash_code % num_buckets;
 618
 619     COCOA_HASHTABLE_PROBING_START(ht, num_buckets);
 620     uintptr_t probe = h1;
 621     for (CFIndex idx = 0; idx < num_buckets; idx++) {
 622         uintptr_t stack_curr = keys[probe].weak;
 623         if (stack_curr == empty) {
 624             COCOA_HASHTABLE_PROBE_EMPTY(ht, probe);
 625             if (kCFNotFound == result.idx) {
 626                 result.idx = probe;
 627                 result.weak_value = empty;
 628                 result.weak_key = empty;
 629             }
 630             COCOA_HASHTABLE_PROBING_END(ht, idx + 1);
 631             return result;
 632         } else if (__builtin_expect(!rehashing, 0)) {
 633             if (stack_curr == deleted) {
 634                 COCOA_HASHTABLE_PROBE_DELETED(ht, probe);
 635                 if (kCFNotFound == result.idx) {
 636                     result.idx = probe;
 637                 }
 638             } else {
 639                 COCOA_HASHTABLE_PROBE_VALID(ht, probe);
 640                 if (stack_curr == stack_key || ((!hashes || hashes[probe] == hash_code) && __CFBasicHashTestEqualKey(ht, stack_curr, stack_key))) {
 641                     COCOA_HASHTABLE_PROBING_END(ht, idx + 1);
 642                     result.idx = probe;
 643                     result.weak_value = (0 != ht->bits.keys_offset) ? __CFBasicHashGetValues(ht)[probe].weak : stack_curr;
 644                     result.weak_value2 = (0 != ht->bits.values2_offset) ? __CFBasicHashGetValues2(ht)[probe].weak : 0;
 645                     result.weak_key = stack_curr;
 646                     result.weak_key2 = (0 != ht->bits.keys2_offset) ? __CFBasicHashGetKeys2(ht)[probe].weak : 0;
 647                     result.count = (0 != ht->bits.counts_offset) ? __CFBasicHashGetCounts(ht)[probe] : 1;
 648                     result.order = (0 != ht->bits.orders_offset) ? __CFBasicHashGetOrders(ht)[probe] : 1;
 649                     return result;
 650                 }
 651             }
 652         }
 653         // Linear probing, with c = 1
 654             probe += 1;
 655             if (__builtin_expect(num_buckets <= probe, 0)) {
 656                 probe -= num_buckets;
 657             }
 658     }
 659     COCOA_HASHTABLE_PROBING_END(ht, num_buckets);
 660     return result; // all buckets full or deleted, return first deleted element which was found
 661 }
 662
 663 static CFBasicHashBucket ___CFBasicHashFindBucket2(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t key_hash, Boolean rehashing) {
 664     CFHashCode hash_code = key_hash ? key_hash : __CFBasicHashHashKey(ht, stack_key);
 665     uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
 666     CFBasicHashValue *keys = (0 != ht->bits.keys_offset) ? __CFBasicHashGetKeys(ht) : __CFBasicHashGetValues(ht);
 667     uintptr_t *hashes = (0 != ht->bits.hashes_offset) ? __CFBasicHashGetHashes(ht) : NULL;
 668     uintptr_t num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 669     CFBasicHashBucket result = {kCFNotFound, deleted, 0, deleted, 0, 0, 0};
 670
 671     uintptr_t h1 = 0, h2 = 0;
 672         // Double hashing
 673         // probe[0] = h1(k)
 674         // probe[i] = (h1(k) + i * h2(k)) mod num_buckets, i = 1 .. num_buckets - 1
 675         // h1(k) = k mod num_buckets
 676         // h2(k) = floor(k / num_buckets) mod num_buckets
 677         h1 = hash_code % num_buckets;
 678         h2 = (hash_code / num_buckets) % num_buckets;
 679         if (0 == h2) h2 = num_buckets - 1;
 680
 681     COCOA_HASHTABLE_PROBING_START(ht, num_buckets);
 682     uintptr_t probe = h1;
 683     for (CFIndex idx = 0; idx < num_buckets; idx++) {
 684         uintptr_t stack_curr = keys[probe].weak;
 685         if (stack_curr == empty) {
 686             COCOA_HASHTABLE_PROBE_EMPTY(ht, probe);
 687             if (kCFNotFound == result.idx) {
 688                 result.idx = probe;
 689                 result.weak_value = empty;
 690                 result.weak_key = empty;
 691             }
 692             COCOA_HASHTABLE_PROBING_END(ht, idx + 1);
 693             return result;
 694         } else if (__builtin_expect(!rehashing, 0)) {
 695             if (stack_curr == deleted) {
 696                 COCOA_HASHTABLE_PROBE_DELETED(ht, probe);
 697                 if (kCFNotFound == result.idx) {
 698                     result.idx = probe;
 699                 }
 700             } else {
 701                 COCOA_HASHTABLE_PROBE_VALID(ht, probe);
 702                 if (stack_curr == stack_key || ((!hashes || hashes[probe] == hash_code) && __CFBasicHashTestEqualKey(ht, stack_curr, stack_key))) {
 703                     COCOA_HASHTABLE_PROBING_END(ht, idx + 1);
 704                     result.idx = probe;
 705                     result.weak_value = (0 != ht->bits.keys_offset) ? __CFBasicHashGetValues(ht)[probe].weak : stack_curr;
 706                     result.weak_value2 = (0 != ht->bits.values2_offset) ? __CFBasicHashGetValues2(ht)[probe].weak : 0;
 707                     result.weak_key = stack_curr;
 708                     result.weak_key2 = (0 != ht->bits.keys2_offset) ? __CFBasicHashGetKeys2(ht)[probe].weak : 0;
 709                     result.count = (0 != ht->bits.counts_offset) ? __CFBasicHashGetCounts(ht)[probe] : 1;
 710                     result.order = (0 != ht->bits.orders_offset) ? __CFBasicHashGetOrders(ht)[probe] : 1;
 711                     return result;
 712                 }
 713             }
 714         }
 715         // Double hashing
 716             probe += h2;
 717             if (__builtin_expect(num_buckets <= probe, 1)) {
 718                 probe -= num_buckets;
 719             }
 720     }
 721     COCOA_HASHTABLE_PROBING_END(ht, num_buckets);
 722     return result; // all buckets full or deleted, return first deleted element which was found
 723 }
 724
 725 static CFBasicHashBucket ___CFBasicHashFindBucket3(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t key_hash, Boolean rehashing) {
 726     CFHashCode hash_code = key_hash ? key_hash : __CFBasicHashHashKey(ht, stack_key);
 727     uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
 728     CFBasicHashValue *keys = (0 != ht->bits.keys_offset) ? __CFBasicHashGetKeys(ht) : __CFBasicHashGetValues(ht);
 729     uintptr_t *hashes = (0 != ht->bits.hashes_offset) ? __CFBasicHashGetHashes(ht) : NULL;
 730     uintptr_t num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 731     CFBasicHashBucket result = {kCFNotFound, deleted, 0, deleted, 0, 0, 0};
 732
 733     uintptr_t h1 = 0, h2 = 0, pr = 0;
 734         // Improved exponential hashing
 735         // probe[0] = h1(k)
 736         // probe[i] = (h1(k) + pr(k)^i * h2(k)) mod num_buckets, i = 1 .. num_buckets - 1
 737         // h1(k) = k mod num_buckets
 738         // h2(k) = floor(k / num_buckets) mod num_buckets
 739         // note: h2(k) has the effect of rotating the sequence if it is constant
 740         // note: pr(k) is any primitive root of num_buckets, varying this gives different sequences
 741         h1 = hash_code % num_buckets;
 742         h2 = (hash_code / num_buckets) % num_buckets;
 743         if (0 == h2) h2 = num_buckets - 1;
 744         pr = __CFBasicHashPrimitiveRoots[ht->bits.num_buckets_idx];
 745
 746     COCOA_HASHTABLE_PROBING_START(ht, num_buckets);
 747     uintptr_t probe = h1, acc = pr;
 748     for (CFIndex idx = 0; idx < num_buckets; idx++) {
 749         uintptr_t stack_curr = keys[probe].weak;
 750         if (stack_curr == empty) {
 751             COCOA_HASHTABLE_PROBE_EMPTY(ht, probe);
 752             if (kCFNotFound == result.idx) {
 753                 result.idx = probe;
 754                 result.weak_value = empty;
 755                 result.weak_key = empty;
 756             }
 757             COCOA_HASHTABLE_PROBING_END(ht, idx + 1);
 758             return result;
 759         } else if (__builtin_expect(!rehashing, 0)) {
 760             if (stack_curr == deleted) {
 761                 COCOA_HASHTABLE_PROBE_DELETED(ht, probe);
 762                 if (kCFNotFound == result.idx) {
 763                     result.idx = probe;
 764                 }
 765             } else {
 766                 COCOA_HASHTABLE_PROBE_VALID(ht, probe);
 767                 if (stack_curr == stack_key || ((!hashes || hashes[probe] == hash_code) && __CFBasicHashTestEqualKey(ht, stack_curr, stack_key))) {
 768                     COCOA_HASHTABLE_PROBING_END(ht, idx + 1);
 769                     result.idx = probe;
 770                     result.weak_value = (0 != ht->bits.keys_offset) ? __CFBasicHashGetValues(ht)[probe].weak : stack_curr;
 771                     result.weak_value2 = (0 != ht->bits.values2_offset) ? __CFBasicHashGetValues2(ht)[probe].weak : 0;
 772                     result.weak_key = stack_curr;
 773                     result.weak_key2 = (0 != ht->bits.keys2_offset) ? __CFBasicHashGetKeys2(ht)[probe].weak : 0;
 774                     result.count = (0 != ht->bits.counts_offset) ? __CFBasicHashGetCounts(ht)[probe] : 1;
 775                     result.order = (0 != ht->bits.orders_offset) ? __CFBasicHashGetOrders(ht)[probe] : 1;
 776                     return result;
 777                 }
 778             }
 779         }
 780         // Improved exponential hashing
 781             probe = h1 + h2 * acc;
 782             if (__builtin_expect(num_buckets <= probe, 1)) {
 783                 probe = probe % num_buckets;
 784             }
 785             acc = acc * pr;
 786             if (__builtin_expect(num_buckets <= acc, 1)) {
 787                 acc = acc % num_buckets;
 788             }
 789     }
 790     COCOA_HASHTABLE_PROBING_END(ht, num_buckets);
 791     return result; // all buckets full or deleted, return first deleted element which was found
 792 }
 793
 794 CF_INLINE CFBasicHashBucket ___CFBasicHashFindBucket(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t key_hash, Boolean rehashing) {
 795     switch (ht->bits.hash_style) {
 796     case __kCFBasicHashLinearHashingValue:
 797         return ___CFBasicHashFindBucket1(ht, stack_key, 0, rehashing);
 798     case __kCFBasicHashDoubleHashingValue:
 799         return ___CFBasicHashFindBucket2(ht, stack_key, 0, rehashing);
 800     case __kCFBasicHashExponentialHashingValue:
 801         return ___CFBasicHashFindBucket3(ht, stack_key, 0, rehashing);
 802     }
 803     HALT;
 804     CFBasicHashBucket result = {kCFNotFound, 0, 0, 0};
 805     return result;
 806 }
 807
 808 CF_INLINE CFBasicHashBucket __CFBasicHashFindBucket(CFBasicHashRef ht, uintptr_t stack_key) {
 809     if (0 == ht->bits.num_buckets_idx) {
 810         uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift);
 811         CFBasicHashBucket result = {kCFNotFound, empty, empty, 0};
 812         return result;
 813     }
 814     return ___CFBasicHashFindBucket(ht, stack_key, 0, false);
 815 }
 816
 817 __private_extern__ CFBasicHashBucket CFBasicHashFindBucket(CFBasicHashRef ht, uintptr_t stack_key) {
 818     return __CFBasicHashFindBucket(ht, stack_key);
 819 }
 820
 821 __private_extern__ CFOptionFlags CFBasicHashGetFlags(CFBasicHashRef ht) {
 822     CFOptionFlags flags = (ht->bits.hash_style << 13);
 823     if (ht->bits.strong_values) flags |= kCFBasicHashStrongValues;
 824     if (ht->bits.strong_values2) flags |= kCFBasicHashStrongValues2;
 825     if (ht->bits.strong_keys) flags |= kCFBasicHashStrongKeys;
 826     if (ht->bits.strong_keys2) flags |= kCFBasicHashStrongKeys2;
 827     if (ht->bits.fast_grow) flags |= kCFBasicHashAggressiveGrowth;
 828     if (ht->bits.values2_offset) flags |= kCFBasicHashHasValues2;
 829     if (ht->bits.keys_offset) flags |= kCFBasicHashHasKeys;
 830     if (ht->bits.keys2_offset) flags |= kCFBasicHashHasKeys2;
 831     if (ht->bits.counts_offset) flags |= kCFBasicHashHasCounts;
 832     if (ht->bits.orders_offset) flags |= kCFBasicHashHasOrder;
 833     if (ht->bits.hashes_offset) flags |= kCFBasicHashHasHashCache;
 834     return flags;
 835 }
 836
 837 __private_extern__ CFIndex CFBasicHashGetCount(CFBasicHashRef ht) {
 838     if (0 != ht->bits.counts_offset) {
 839         CFIndex total = 0L;
 840         CFIndex cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 841         uintptr_t *counts = __CFBasicHashGetCounts(ht);
 842         for (CFIndex idx = 0; idx < cnt; idx++) {
 843             total += counts[idx];
 844         }
 845         return total;
 846     }
 847     return (CFIndex)ht->bits.used_buckets;
 848 }
 849
 850 __private_extern__ CFIndex CFBasicHashGetCountOfKey(CFBasicHashRef ht, uintptr_t stack_key) {
 851     if (0L == ht->bits.used_buckets) {
 852         return 0L;
 853     }
 854     return __CFBasicHashFindBucket(ht, stack_key).count;
 855 }
 856
 857 __private_extern__ CFIndex CFBasicHashGetCountOfValue(CFBasicHashRef ht, uintptr_t stack_value) {
 858     if (0L == ht->bits.used_buckets) {
 859         return 0L;
 860     }
 861     if (!(0 != ht->bits.keys_offset)) {
 862         return __CFBasicHashFindBucket(ht, stack_value).count;
 863     }
 864     __block CFIndex total = 0L;
 865     CFBasicHashApply(ht, ^(CFBasicHashBucket bkt) {
 866             if ((stack_value == bkt.weak_value) || __CFBasicHashTestEqualValue(ht, bkt.weak_value, stack_value)) total += bkt.count;
 867             return (Boolean)true;
 868         });
 869     return total;
 870 }
 871
 872 __private_extern__ Boolean CFBasicHashesAreEqual(CFBasicHashRef ht1, CFBasicHashRef ht2) {
 873     CFIndex cnt1 = CFBasicHashGetCount(ht1);
 874     if (cnt1 != CFBasicHashGetCount(ht2)) return false;
 875     if (0 == cnt1) return true;
 876     __block Boolean equal = true;
 877     CFBasicHashApply(ht1, ^(CFBasicHashBucket bkt1) {
 878             CFBasicHashBucket bkt2 = __CFBasicHashFindBucket(ht2, bkt1.weak_key);
 879             if (bkt1.count != bkt2.count) {
 880                 equal = false;
 881                 return (Boolean)false;
 882             }
 883             if ((0 != ht1->bits.keys_offset) && (bkt1.weak_value != bkt2.weak_value) && !__CFBasicHashTestEqualValue(ht1, bkt1.weak_value, bkt2.weak_value)) {
 884                 equal = false;
 885                 return (Boolean)false;
 886             }
 887             return (Boolean)true;
 888         });
 889     return equal;
 890 }
 891
 892 __private_extern__ void CFBasicHashApply(CFBasicHashRef ht, Boolean (^block)(CFBasicHashBucket)) {
 893     CFIndex used = (CFIndex)ht->bits.used_buckets, cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 894     for (CFIndex idx = 0; 0 < used && idx < cnt; idx++) {
 895         CFBasicHashBucket bkt = CFBasicHashGetBucket(ht, idx);
 896         if (0 < bkt.count) {
 897             if (!block(bkt)) {
 898                 return;
 899             }
 900             used--;
 901         }
 902     }
 903 }
 904
 905 __private_extern__ void CFBasicHashGetElements(CFBasicHashRef ht, CFIndex bufferslen, uintptr_t *weak_values, uintptr_t *weak_values2, uintptr_t *weak_keys, uintptr_t *weak_keys2) {
 906     CFIndex used = (CFIndex)ht->bits.used_buckets, cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 907     uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
 908     CFBasicHashValue *values = __CFBasicHashGetValues(ht);
 909     CFBasicHashValue *values2 = (0 != ht->bits.values2_offset) ? __CFBasicHashGetValues2(ht) : NULL;
 910     CFBasicHashValue *keys = (0 != ht->bits.keys_offset) ? __CFBasicHashGetKeys(ht) : NULL;
 911     CFBasicHashValue *keys2 = (0 != ht->bits.keys2_offset) ? __CFBasicHashGetKeys2(ht) : NULL;
 912     uintptr_t *counts = (0 != ht->bits.counts_offset) ? __CFBasicHashGetCounts(ht) : NULL;
 913     CFIndex offset = 0;
 914     for (CFIndex idx = 0; 0 < used && idx < cnt && offset < bufferslen; idx++) {
 915         uintptr_t weak_key = keys ? keys[idx].weak : values[idx].weak;
 916         uintptr_t count = counts ? counts[idx] : ((weak_key == empty || weak_key == deleted) ? 0 : 1);
 917         if (0 < count) {
 918             used--;
 919             for (CFIndex cnt = count; cnt-- && offset < bufferslen;) {
 920                 if (weak_values) { weak_values[offset] = values[idx].weak; }
 921                 if (weak_values2) { weak_values2[offset] = values2 ? values2[idx].weak : 0; }
 922                 if (weak_keys) { weak_keys[offset] = weak_key; }
 923                 if (weak_keys2) { weak_keys2[offset] = keys2 ? keys2[idx].weak : 0; }
 924                 offset++;
 925             }
 926         }
 927     }
 928 }
 929
 930 __private_extern__ unsigned long __CFBasicHashFastEnumeration(CFBasicHashRef ht, struct __objcFastEnumerationStateEquivalent2 *state, void *stackbuffer, unsigned long count) {
 931     /* copy as many as count items over */
 932     if (0 == state->state) {        /* first time */
 933         state->mutationsPtr = (unsigned long *)&ht->bits + (__LP64__ ? 1 : 3);
 934     }
 935     state->itemsPtr = (unsigned long *)stackbuffer;
 936     CFIndex cntx = 0;
 937     CFIndex used = (CFIndex)ht->bits.used_buckets, cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 938     for (CFIndex idx = (CFIndex)state->state; 0 < used && idx < cnt && cntx < (CFIndex)count; idx++) {
 939         CFBasicHashBucket bkt = CFBasicHashGetBucket(ht, idx);
 940         if (0 < bkt.count) {
 941             state->itemsPtr[cntx++] = (unsigned long)bkt.weak_key;
 942             used--;
 943         }
 944         state->state++;
 945     }
 946     return cntx;
 947 }
 948
 949 #if ENABLE_MEMORY_COUNTERS
 950 static volatile int64_t __CFBasicHashTotalCount = 0ULL;
 951 static volatile int64_t __CFBasicHashTotalSize = 0ULL;
 952 static volatile int64_t __CFBasicHashPeakCount = 0ULL;
 953 static volatile int64_t __CFBasicHashPeakSize = 0ULL;
 954 static volatile int32_t __CFBasicHashSizes[64] = {0};
 955 #endif
 956
 957 static void __CFBasicHashDrain(CFBasicHashRef ht, Boolean forFinalization) {
 958 #if ENABLE_MEMORY_COUNTERS
 959     OSAtomicAdd64Barrier(-1 * (int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
 960 #endif
 961
 962     uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
 963     CFIndex old_num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 964
 965     CFAllocatorRef allocator = CFGetAllocator(ht);
 966     Boolean nullify = (!forFinalization || !CF_IS_COLLECTABLE_ALLOCATOR(allocator));
 967
 968     CFBasicHashValue *old_values = NULL, *old_values2 = NULL, *old_keys = NULL, *old_keys2 = NULL;
 969     uintptr_t *old_counts = NULL, *old_orders = NULL, *old_hashes = NULL;
 970
 971     old_values = __CFBasicHashGetValues(ht);
 972     if (nullify) __CFBasicHashSetValues(ht, NULL);
 973     if (0 != ht->bits.values2_offset) {
 974         old_values2 = __CFBasicHashGetValues2(ht);
 975         if (nullify) __CFBasicHashSetValues2(ht, NULL);
 976     }
 977     if (0 != ht->bits.keys_offset) {
 978         old_keys = __CFBasicHashGetKeys(ht);
 979         if (nullify) __CFBasicHashSetKeys(ht, NULL);
 980     }
 981     if (0 != ht->bits.keys2_offset) {
 982         old_keys2 = __CFBasicHashGetKeys2(ht);
 983         if (nullify) __CFBasicHashSetKeys2(ht, NULL);
 984     }
 985     if (0 != ht->bits.counts_offset) {
 986         old_counts = __CFBasicHashGetCounts(ht);
 987         if (nullify) __CFBasicHashSetCounts(ht, NULL);
 988     }
 989     if (0 != ht->bits.orders_offset) {
 990         old_orders = __CFBasicHashGetOrders(ht);
 991         if (nullify) __CFBasicHashSetOrders(ht, NULL);
 992     }
 993     if (0 != ht->bits.hashes_offset) {
 994         old_hashes = __CFBasicHashGetHashes(ht);
 995         if (nullify) __CFBasicHashSetHashes(ht, NULL);
 996     }
 997
 998     if (nullify) {
 999         ht->bits.mutations++;
1000         ht->bits.num_buckets_idx = 0;
1001         ht->bits.used_buckets = 0;
1002         ht->bits.marker = 0;
1003         ht->bits.deleted = 0;
1004     }
1005
1006     if (ht->callbacks != &CFBasicHashNullCallbacks) {
1007         CFBasicHashValue *keys = old_keys ? old_keys : old_values;
1008         for (CFIndex idx = 0; idx < old_num_buckets; idx++) {
1009             uintptr_t stack_key = keys[idx].weak;
1010             if (stack_key != empty && stack_key != deleted) {
1011                 __CFBasicHashEjectValue(ht, old_values[idx].weak);
1012                 if (old_values2) {
1013                     __CFBasicHashEjectValue2(ht, old_values2[idx].weak);
1014                 }
1015                 if (old_keys) {
1016                     __CFBasicHashEjectKey(ht, old_keys[idx].weak);
1017                 }
1018                 if (old_keys2) {
1019                     __CFBasicHashEjectKey2(ht, old_keys2[idx].weak);
1020                 }
1021             }
1022         }
1023     }
1024
1025     if (forFinalization) {
1026         ht->callbacks->func(ht, kCFBasicHashCallbackOpFreeCallbacks, (uintptr_t)allocator, 0, ht->callbacks);
1027     }
1028
1029     if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
1030         CFAllocatorDeallocate(allocator, old_values);
1031         CFAllocatorDeallocate(allocator, old_values2);
1032         CFAllocatorDeallocate(allocator, old_keys);
1033         CFAllocatorDeallocate(allocator, old_keys2);
1034         CFAllocatorDeallocate(allocator, old_counts);
1035         CFAllocatorDeallocate(allocator, old_orders);
1036         CFAllocatorDeallocate(allocator, old_hashes);
1037     }
1038
1039 #if ENABLE_MEMORY_COUNTERS
1040     int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
1041     while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize));
1042 #endif
1043 }
1044
1045 static void __CFBasicHashRehash(CFBasicHashRef ht, CFIndex newItemCount) {
1046 #if ENABLE_MEMORY_COUNTERS
1047     OSAtomicAdd64Barrier(-1 * (int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
1048     OSAtomicAdd32Barrier(-1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1049 #endif
1050
1051     if (COCOA_HASHTABLE_REHASH_START_ENABLED()) COCOA_HASHTABLE_REHASH_START(ht, CFBasicHashGetNumBuckets(ht), CFBasicHashGetSize(ht, true));
1052
1053     CFIndex new_num_buckets_idx = ht->bits.num_buckets_idx;
1054     if (0 != newItemCount) {
1055         if (newItemCount < 0) newItemCount = 0;
1056         CFIndex new_capacity_req = ht->bits.used_buckets + newItemCount;
1057         new_num_buckets_idx = __CFBasicHashGetNumBucketsIndexForCapacity(ht, new_capacity_req);
1058         if (1 == newItemCount && ht->bits.fast_grow) {
1059             new_num_buckets_idx++;
1060         }
1061     }
1062
1063     CFIndex new_num_buckets = __CFBasicHashTableSizes[new_num_buckets_idx];
1064     CFIndex old_num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1065
1066     CFBasicHashValue *new_values = NULL, *new_values2 = NULL, *new_keys = NULL, *new_keys2 = NULL;
1067     uintptr_t *new_counts = NULL, *new_orders = NULL, *new_hashes = NULL;
1068
1069     if (0 < new_num_buckets) {
1070         new_values = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), ht->bits.strong_values);
1071         __SetLastAllocationEventName(new_values, "CFBasicHash (value-store)");
1072         if (0 != ht->bits.values2_offset) {
1073             new_values2 = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), ht->bits.strong_values2);
1074             __SetLastAllocationEventName(new_values2, "CFBasicHash (value2-store)");
1075         }
1076         if (0 != ht->bits.keys_offset) {
1077             new_keys = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), ht->bits.strong_keys);
1078             __SetLastAllocationEventName(new_keys, "CFBasicHash (key-store)");
1079         }
1080         if (0 != ht->bits.keys2_offset) {
1081             new_keys2 = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), ht->bits.strong_keys2);
1082             __SetLastAllocationEventName(new_keys2, "CFBasicHash (key2-store)");
1083         }
1084         if (0 != ht->bits.counts_offset) {
1085             new_counts = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(uintptr_t), false);
1086             __SetLastAllocationEventName(new_counts, "CFBasicHash (count-store)");
1087             memset(new_counts, 0, new_num_buckets * sizeof(uintptr_t));
1088         }
1089         if (0 != ht->bits.orders_offset) {
1090             new_orders = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(uintptr_t), false);
1091             __SetLastAllocationEventName(new_orders, "CFBasicHash (order-store)");
1092             memset(new_orders, 0, new_num_buckets * sizeof(uintptr_t));
1093         }
1094         if (0 != ht->bits.hashes_offset) {
1095             new_hashes = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(uintptr_t), false);
1096             __SetLastAllocationEventName(new_hashes, "CFBasicHash (hash-store)");
1097             memset(new_hashes, 0, new_num_buckets * sizeof(uintptr_t));
1098         }
1099     }
1100
1101     uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
1102     // if we knew the allocations were coming from already-cleared memory, and the marker was still 0, we could skip all this next stuff
1103     for (CFIndex idx = 0; idx < new_num_buckets; idx++) {
1104         if (ht->bits.strong_values) new_values[idx].strong = (id)empty; else new_values[idx].weak = empty;
1105         if (new_values2) {
1106             if (ht->bits.strong_values2) new_values2[idx].strong = (id)empty; else new_values2[idx].weak = empty;
1107         }
1108         if (new_keys) {
1109             if (ht->bits.strong_keys) new_keys[idx].strong = (id)empty; else new_keys[idx].weak = empty;
1110         }
1111         if (new_keys2) {
1112             if (ht->bits.strong_keys2) new_keys2[idx].strong = (id)empty; else new_keys2[idx].weak = empty;
1113         }
1114     }
1115
1116     ht->bits.num_buckets_idx = new_num_buckets_idx;
1117     ht->bits.deleted = 0;
1118
1119     CFBasicHashValue *old_values = NULL, *old_values2 = NULL, *old_keys = NULL, *old_keys2 = NULL;
1120     uintptr_t *old_counts = NULL, *old_orders = NULL, *old_hashes = NULL;
1121
1122     old_values = __CFBasicHashGetValues(ht);
1123     __CFBasicHashSetValues(ht, new_values);
1124     if (0 != ht->bits.values2_offset) {
1125         old_values2 = __CFBasicHashGetValues2(ht);
1126         __CFBasicHashSetValues2(ht, new_values2);
1127     }
1128     if (0 != ht->bits.keys_offset) {
1129         old_keys = __CFBasicHashGetKeys(ht);
1130         __CFBasicHashSetKeys(ht, new_keys);
1131     }
1132     if (0 != ht->bits.keys2_offset) {
1133         old_keys2 = __CFBasicHashGetKeys2(ht);
1134         __CFBasicHashSetKeys2(ht, new_keys2);
1135     }
1136     if (0 != ht->bits.counts_offset) {
1137         old_counts = __CFBasicHashGetCounts(ht);
1138         __CFBasicHashSetCounts(ht, new_counts);
1139     }
1140     if (0 != ht->bits.orders_offset) {
1141         old_orders = __CFBasicHashGetOrders(ht);
1142         __CFBasicHashSetOrders(ht, new_orders);
1143     }
1144     if (0 != ht->bits.hashes_offset) {
1145         old_hashes = __CFBasicHashGetHashes(ht);
1146         __CFBasicHashSetHashes(ht, new_hashes);
1147     }
1148
1149     if (0 < old_num_buckets) {
1150         CFBasicHashValue *keys = old_keys ? old_keys : old_values;
1151         for (CFIndex idx = 0; idx < old_num_buckets; idx++) {
1152             uintptr_t stack_key = keys[idx].weak;
1153             if (stack_key != empty && stack_key != deleted) {
1154                 CFBasicHashBucket bkt = ___CFBasicHashFindBucket(ht, stack_key, old_hashes ? old_hashes[idx] : 0, true);
1155                 uintptr_t stack_value = old_values[idx].weak;
1156                 if (ht->bits.strong_values) new_values[bkt.idx].strong = (id)stack_value; else new_values[bkt.idx].weak = stack_value;
1157                 if (old_values2) {
1158                     if (ht->bits.strong_values2) new_values2[bkt.idx].strong = (id)old_values2[idx].weak; else new_values2[bkt.idx].weak = old_values2[idx].weak;
1159                 }
1160                 if (old_keys) {
1161                     if (ht->bits.strong_keys) new_keys[bkt.idx].strong = (id)stack_key; else new_keys[bkt.idx].weak = stack_key;
1162                 }
1163                 if (old_keys2) {
1164                     if (ht->bits.strong_keys2) new_keys2[bkt.idx].strong = (id)old_keys2[idx].weak; else new_keys2[bkt.idx].weak = old_keys2[idx].weak;
1165                 }
1166                 if (old_counts) {
1167                     new_counts[bkt.idx] = old_counts[idx];
1168                 }
1169                 if (old_orders) {
1170                     new_orders[bkt.idx] = old_orders[idx];
1171                 }
1172                 if (old_hashes) {
1173                     new_hashes[bkt.idx] = old_hashes[idx];
1174                 }
1175             }
1176         }
1177     }
1178
1179     CFAllocatorRef allocator = CFGetAllocator(ht);
1180     if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
1181         CFAllocatorDeallocate(allocator, old_values);
1182         CFAllocatorDeallocate(allocator, old_values2);
1183         CFAllocatorDeallocate(allocator, old_keys);
1184         CFAllocatorDeallocate(allocator, old_keys2);
1185         CFAllocatorDeallocate(allocator, old_counts);
1186         CFAllocatorDeallocate(allocator, old_orders);
1187         CFAllocatorDeallocate(allocator, old_hashes);
1188     }
1189
1190     if (COCOA_HASHTABLE_REHASH_END_ENABLED()) COCOA_HASHTABLE_REHASH_END(ht, CFBasicHashGetNumBuckets(ht), CFBasicHashGetSize(ht, true));
1191
1192 #if ENABLE_MEMORY_COUNTERS
1193     int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), &__CFBasicHashTotalSize);
1194     while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize));
1195     OSAtomicAdd32Barrier(1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1196 #endif
1197 }
1198
1199 __private_extern__ void CFBasicHashSetCapacity(CFBasicHashRef ht, CFIndex capacity) {
1200     if (!CFBasicHashIsMutable(ht)) HALT;
1201     if (ht->bits.used_buckets < capacity) {
1202         ht->bits.mutations++;
1203         __CFBasicHashRehash(ht, capacity - ht->bits.used_buckets);
1204     }
1205 }
1206
1207 static void __CFBasicHashFindNewMarker(CFBasicHashRef ht, uintptr_t stack_key) {
1208     uintptr_t marker = ht->bits.marker;
1209     uintptr_t empty = (marker << __CFBasicHashMarkerShift), deleted = ~empty;
1210     CFBasicHashValue *keys = (0 != ht->bits.keys_offset) ? __CFBasicHashGetKeys(ht) : __CFBasicHashGetValues(ht);
1211     Boolean strong = (0 != ht->bits.keys_offset) ? ht->bits.strong_keys : ht->bits.strong_values;
1212     CFIndex cnt = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1213     if (0 == marker) marker = 4096;
1214
1215     again:;
1216     marker++;
1217     if ((1UL << 26) <= marker) HALT;
1218     uintptr_t new_empty = (marker << __CFBasicHashMarkerShift), new_deleted = ~new_empty;
1219     if (stack_key == new_empty || stack_key == new_deleted) {
1220         goto again;
1221     }
1222     for (CFIndex idx = 0; idx < cnt; idx++) {
1223         uintptr_t stack_curr = strong ? (uintptr_t)keys[idx].strong : keys[idx].weak;
1224         if (stack_curr == new_empty || stack_curr == new_deleted) {
1225             goto again;
1226         }
1227     }
1228     for (CFIndex idx = 0; idx < cnt; idx++) {
1229         uintptr_t stack_curr = strong ? (uintptr_t)keys[idx].strong : keys[idx].weak;
1230         if (stack_curr == empty) {
1231             if (strong) keys[idx].strong = (id)new_empty; else keys[idx].weak = new_empty;
1232         } else if (stack_curr == deleted) {
1233             if (strong) keys[idx].strong = (id)new_deleted; else keys[idx].weak = new_deleted;
1234         }
1235     }
1236     ht->bits.marker = marker;
1237 }
1238
1239 static void __CFBasicHashAddValue(CFBasicHashRef ht, CFBasicHashBucket bkt, uintptr_t stack_key, uintptr_t stack_key2, uintptr_t stack_value, uintptr_t stack_value2) {
1240     ht->bits.mutations++;
1241     stack_value = __CFBasicHashImportValue(ht, stack_value);
1242     if (0 != ht->bits.keys_offset) {
1243         stack_key = __CFBasicHashImportKey(ht, stack_key);
1244     } else {
1245         stack_key = stack_value;
1246     }
1247     if (0 != ht->bits.values2_offset) {
1248         stack_value2 = __CFBasicHashImportValue2(ht, stack_value2);
1249     }
1250     if (0 != ht->bits.keys2_offset) {
1251         stack_key2 = __CFBasicHashImportKey2(ht, stack_key2);
1252     }
1253     if (CFBasicHashGetCapacity(ht) < ht->bits.used_buckets + 1) {
1254         __CFBasicHashRehash(ht, 1);
1255         bkt = ___CFBasicHashFindBucket(ht, stack_key, 0, true);
1256     }
1257     uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
1258     if (bkt.weak_key == deleted) {
1259         ht->bits.deleted--;
1260     }
1261     if (stack_key == empty || stack_key == deleted) {
1262         __CFBasicHashFindNewMarker(ht, stack_key);
1263     }
1264     CFBasicHashValue *value = &(__CFBasicHashGetValues(ht)[bkt.idx]);
1265     if (ht->bits.strong_values) value->strong = (id)stack_value; else value->weak = stack_value;
1266     if (0 != ht->bits.values2_offset) {
1267         CFBasicHashValue *value2 = &(__CFBasicHashGetValues2(ht)[bkt.idx]);
1268         if (ht->bits.strong_values2) value2->strong = (id)stack_value2; else value2->weak = stack_value2;
1269     }
1270     if (0 != ht->bits.keys_offset) {
1271         CFBasicHashValue *key = &(__CFBasicHashGetKeys(ht)[bkt.idx]);
1272         if (ht->bits.strong_keys) key->strong = (id)stack_key; else key->weak = stack_key;
1273     }
1274     if (0 != ht->bits.keys2_offset) {
1275         CFBasicHashValue *key2 = &(__CFBasicHashGetKeys2(ht)[bkt.idx]);
1276         if (ht->bits.strong_keys2) key2->strong = (id)stack_key2; else key2->weak = stack_key2;
1277     }
1278     if (0 != ht->bits.counts_offset) {
1279         __CFBasicHashGetCounts(ht)[bkt.idx] = 1;
1280     }
1281     if (0 != ht->bits.orders_offset) {
1282         __CFBasicHashGetOrders(ht)[bkt.idx] = 0;
1283     }
1284     if (ht->bits.hashes_offset) {
1285         __CFBasicHashGetHashes(ht)[bkt.idx] = __CFBasicHashHashKey(ht, stack_key);
1286     }
1287     ht->bits.used_buckets++;
1288 }
1289
1290 static void __CFBasicHashReplaceValue(CFBasicHashRef ht, CFBasicHashBucket bkt, uintptr_t stack_key, uintptr_t stack_key2, uintptr_t stack_value, uintptr_t stack_value2) {
1291     ht->bits.mutations++;
1292     stack_value = __CFBasicHashImportValue(ht, stack_value);
1293     if (0 != ht->bits.keys_offset) {
1294         stack_key = __CFBasicHashImportKey(ht, stack_key);
1295     } else {
1296         stack_key = stack_value;
1297     }
1298     if (0 != ht->bits.values2_offset) {
1299         stack_value2 = __CFBasicHashImportValue2(ht, stack_value2);
1300     }
1301     if (0 != ht->bits.keys2_offset) {
1302         stack_key2 = __CFBasicHashImportKey2(ht, stack_key2);
1303     }
1304     uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
1305     if (stack_key == empty || stack_key == deleted) {
1306         __CFBasicHashFindNewMarker(ht, stack_key);
1307     }
1308     CFBasicHashValue *value = &(__CFBasicHashGetValues(ht)[bkt.idx]);
1309     uintptr_t old_value = value->weak;
1310     if (ht->bits.strong_values) value->strong = (id)stack_value; else value->weak = stack_value;
1311     __CFBasicHashEjectValue(ht, old_value);
1312     if (0 != ht->bits.values2_offset) {
1313         CFBasicHashValue *value2 = &(__CFBasicHashGetValues2(ht)[bkt.idx]);
1314         uintptr_t old_value2 = value2->weak;
1315         if (ht->bits.strong_values2) value2->strong = (id)stack_value2; else value2->weak = stack_value2;
1316         __CFBasicHashEjectValue2(ht, old_value2);
1317     }
1318     if (0 != ht->bits.keys_offset) {
1319         CFBasicHashValue *key = &(__CFBasicHashGetKeys(ht)[bkt.idx]);
1320         uintptr_t old_key = key->weak;
1321         if (ht->bits.strong_keys) key->strong = (id)stack_key; else key->weak = stack_key;
1322         __CFBasicHashEjectKey(ht, old_key);
1323     }
1324     if (0 != ht->bits.keys2_offset) {
1325         CFBasicHashValue *key2 = &(__CFBasicHashGetKeys2(ht)[bkt.idx]);
1326         uintptr_t old_key2 = key2->weak;
1327         if (ht->bits.strong_keys2) key2->strong = (id)stack_key2; else key2->weak = stack_key2;
1328         __CFBasicHashEjectKey2(ht, old_key2);
1329     }
1330 }
1331
1332 static void __CFBasicHashRemoveValue(CFBasicHashRef ht, CFBasicHashBucket bkt, uintptr_t stack_key, uintptr_t stack_key2) {
1333     ht->bits.mutations++;
1334     uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
1335     CFBasicHashValue *value = &(__CFBasicHashGetValues(ht)[bkt.idx]);
1336     uintptr_t old_value = value->weak;
1337     if (ht->bits.strong_values) value->strong = (id)deleted; else value->weak = deleted;
1338     __CFBasicHashEjectValue(ht, old_value);
1339     if (0 != ht->bits.values2_offset) {
1340         CFBasicHashValue *value2 = &(__CFBasicHashGetValues2(ht)[bkt.idx]);
1341         uintptr_t old_value2 = value2->weak;
1342         if (ht->bits.strong_values2) value2->strong = (id)deleted; else value2->weak = deleted;
1343         __CFBasicHashEjectValue2(ht, old_value2);
1344     }
1345     if (0 != ht->bits.keys_offset) {
1346         CFBasicHashValue *key = &(__CFBasicHashGetKeys(ht)[bkt.idx]);
1347         uintptr_t old_key = key->weak;
1348         if (ht->bits.strong_keys) key->strong = (id)deleted; else key->weak = deleted;
1349         __CFBasicHashEjectKey(ht, old_key);
1350     }
1351     if (0 != ht->bits.keys2_offset) {
1352         CFBasicHashValue *key2 = &(__CFBasicHashGetKeys2(ht)[bkt.idx]);
1353         uintptr_t old_key2 = key2->weak;
1354         if (ht->bits.strong_keys2) key2->strong = (id)deleted; else key2->weak = deleted;
1355         __CFBasicHashEjectKey2(ht, old_key2);
1356     }
1357     if (0 != ht->bits.counts_offset) {
1358         __CFBasicHashGetCounts(ht)[bkt.idx] = 0;
1359     }
1360     if (0 != ht->bits.orders_offset) {
1361         __CFBasicHashGetOrders(ht)[bkt.idx] = 0;
1362     }
1363     if (ht->bits.hashes_offset) {
1364         __CFBasicHashGetHashes(ht)[bkt.idx] = 0;
1365     }
1366     ht->bits.used_buckets--;
1367     ht->bits.deleted++;
1368     Boolean do_shrink = false;
1369     if (ht->bits.fast_grow) { // == slow shrink
1370         do_shrink = (5 < ht->bits.num_buckets_idx && ht->bits.used_buckets < __CFBasicHashGetCapacityForNumBuckets(ht, ht->bits.num_buckets_idx - 5));
1371     } else {
1372         do_shrink = (2 < ht->bits.num_buckets_idx && ht->bits.used_buckets < __CFBasicHashGetCapacityForNumBuckets(ht, ht->bits.num_buckets_idx - 2));
1373     }
1374     if (do_shrink) {
1375         __CFBasicHashRehash(ht, -1);
1376         return;
1377     }
1378     do_shrink = (0 == ht->bits.deleted); // .deleted roll-over
1379     CFIndex num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1380     do_shrink = do_shrink || ((20 <= num_buckets) && (num_buckets / 4 <= ht->bits.deleted));
1381     if (do_shrink) {
1382         __CFBasicHashRehash(ht, 0);
1383     }
1384 }
1385
1386 __private_extern__ void CFBasicHashAddValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value) {
1387     if (!CFBasicHashIsMutable(ht)) HALT;
1388     CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
1389     if (0 < bkt.count) {
1390         ht->bits.mutations++;
1391         if (0 != ht->bits.counts_offset) {
1392             __CFBasicHashGetCounts(ht)[bkt.idx]++;
1393         }
1394     } else {
1395         __CFBasicHashAddValue(ht, bkt, stack_key, 0, stack_value, 0);
1396     }
1397 }
1398
1399 __private_extern__ void CFBasicHashReplaceValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value) {
1400     if (!CFBasicHashIsMutable(ht)) HALT;
1401     CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
1402     if (0 < bkt.count) {
1403         __CFBasicHashReplaceValue(ht, bkt, stack_key, 0, stack_value, 0);
1404     }
1405 }
1406
1407 __private_extern__ void CFBasicHashSetValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value) {
1408     if (!CFBasicHashIsMutable(ht)) HALT;
1409     CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
1410     if (0 < bkt.count) {
1411         __CFBasicHashReplaceValue(ht, bkt, stack_key, 0, stack_value, 0);
1412     } else {
1413         __CFBasicHashAddValue(ht, bkt, stack_key, 0, stack_value, 0);
1414     }
1415 }
1416
1417 __private_extern__ CFIndex CFBasicHashRemoveValue(CFBasicHashRef ht, uintptr_t stack_key) {
1418     if (!CFBasicHashIsMutable(ht)) HALT;
1419     CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
1420     if (1 < bkt.count) {
1421         ht->bits.mutations++;
1422         if (0 != ht->bits.counts_offset) {
1423             __CFBasicHashGetCounts(ht)[bkt.idx]--;
1424         }
1425     } else if (0 < bkt.count) {
1426         __CFBasicHashRemoveValue(ht, bkt, stack_key, 0);
1427     }
1428     return bkt.count;
1429 }
1430
1431 __private_extern__ void CFBasicHashRemoveAllValues(CFBasicHashRef ht) {
1432     if (!CFBasicHashIsMutable(ht)) HALT;
1433     if (0 == ht->bits.num_buckets_idx) return;
1434     __CFBasicHashDrain(ht, false);
1435 }
1436
1437 __private_extern__ size_t CFBasicHashGetSize(CFBasicHashRef ht, Boolean total) {
1438     size_t size = sizeof(struct __CFBasicHash);
1439     if (0 != ht->bits.values2_offset) size += sizeof(CFBasicHashValue *);
1440     if (0 != ht->bits.keys_offset) size += sizeof(CFBasicHashValue *);
1441     if (0 != ht->bits.keys2_offset) size += sizeof(CFBasicHashValue *);
1442     if (0 != ht->bits.counts_offset) size += sizeof(uintptr_t *);
1443     if (0 != ht->bits.orders_offset) size += sizeof(uintptr_t *);
1444     if (0 != ht->bits.hashes_offset) size += sizeof(uintptr_t *);
1445     if (total) {
1446         CFIndex num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1447         if (0 < num_buckets) {
1448             size += malloc_size(__CFBasicHashGetValues(ht));
1449             if (0 != ht->bits.values2_offset) size += malloc_size(__CFBasicHashGetValues2(ht));
1450             if (0 != ht->bits.keys_offset) size += malloc_size(__CFBasicHashGetKeys(ht));
1451             if (0 != ht->bits.keys2_offset) size += malloc_size(__CFBasicHashGetKeys2(ht));
1452             if (0 != ht->bits.counts_offset) size += malloc_size(__CFBasicHashGetCounts(ht));
1453             if (0 != ht->bits.orders_offset) size += malloc_size(__CFBasicHashGetOrders(ht));
1454             if (0 != ht->bits.hashes_offset) size += malloc_size(__CFBasicHashGetHashes(ht));
1455             size += malloc_size((void *)ht->callbacks);
1456         }
1457     }
1458     return size;
1459 }
1460
1461 __private_extern__ CFStringRef CFBasicHashCopyDescription(CFBasicHashRef ht, Boolean detailed, CFStringRef prefix, CFStringRef entryPrefix, Boolean describeElements) {
1462     CFMutableStringRef result = CFStringCreateMutable(kCFAllocatorSystemDefault, 0);
1463     CFStringAppendFormat(result, NULL, CFSTR("%@{type = %s %s%s, count = %ld,\n"), prefix, (CFBasicHashIsMutable(ht) ? "mutable" : "immutable"), ((0 != ht->bits.counts_offset) ? "multi" : ""), ((0 != ht->bits.keys_offset) ? "dict" : "set"), CFBasicHashGetCount(ht));
1464     if (detailed) {
1465         const char *cb_type = "custom";
1466         if (&CFBasicHashNullCallbacks == ht->callbacks) {
1467             cb_type = "null";
1468         } else if (&CFBasicHashStandardCallbacks == ht->callbacks) {
1469             cb_type = "standard";
1470         }
1471         CFStringAppendFormat(result, NULL, CFSTR("%@hash cache = %s, strong values = %s, strong keys = %s, cb = %s,\n"), prefix, ((0 != ht->bits.hashes_offset) ? "yes" : "no"), (ht->bits.strong_values ? "yes" : "no"), (ht->bits.strong_keys ? "yes" : "no"), cb_type);
1472         CFStringAppendFormat(result, NULL, CFSTR("%@num bucket index = %d, num buckets = %ld, capacity = %ld, num buckets used = %ld,\n"), prefix, ht->bits.num_buckets_idx, CFBasicHashGetNumBuckets(ht), CFBasicHashGetCapacity(ht), ht->bits.used_buckets);
1473         uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
1474         CFStringAppendFormat(result, NULL, CFSTR("%@empty marker = 0x%lx, deleted marker = 0x%lx, finalized = %s,\n"), prefix, empty, deleted, (ht->bits.finalized ? "yes" : "no"));
1475         CFStringAppendFormat(result, NULL, CFSTR("%@num mutations = %ld, num deleted = %ld, size = %ld, total size = %ld,\n"), prefix, ht->bits.mutations, ht->bits.deleted, CFBasicHashGetSize(ht, false), CFBasicHashGetSize(ht, true));
1476         CFStringAppendFormat(result, NULL, CFSTR("%@values ptr = %p, keys ptr = %p, counts ptr = %p, hashes ptr = %p,\n"), prefix, __CFBasicHashGetValues(ht), ((0 != ht->bits.keys_offset) ? __CFBasicHashGetKeys(ht) : NULL), ((0 != ht->bits.counts_offset) ? __CFBasicHashGetCounts(ht) : NULL), ((0 != ht->bits.hashes_offset) ? __CFBasicHashGetHashes(ht) : NULL));
1477     }
1478     CFStringAppendFormat(result, NULL, CFSTR("%@entries =>\n"), prefix);
1479     CFBasicHashApply(ht, ^(CFBasicHashBucket bkt) {
1480             CFStringRef vDesc = NULL, kDesc = NULL;
1481             CFBasicHashCallbackType cb = ht->callbacks->func;
1482             if (!describeElements) cb = __CFBasicHashNullCallback;
1483             vDesc = (CFStringRef)cb(ht, kCFBasicHashCallbackOpDescribeValue, bkt.weak_value, 0, ht->callbacks);
1484             if (0 != ht->bits.keys_offset) {
1485                 kDesc = (CFStringRef)cb(ht, kCFBasicHashCallbackOpDescribeKey, bkt.weak_key, 0, ht->callbacks);
1486             }
1487             if ((0 != ht->bits.keys_offset) && (0 != ht->bits.counts_offset)) {
1488                 CFStringAppendFormat(result, NULL, CFSTR("%@%ld : %@ = %@ (%ld)\n"), entryPrefix, bkt.idx, kDesc, vDesc, bkt.count);
1489             } else if (0 != ht->bits.keys_offset) {
1490                 CFStringAppendFormat(result, NULL, CFSTR("%@%ld : %@ = %@\n"), entryPrefix, bkt.idx, kDesc, vDesc);
1491             } else if (0 != ht->bits.counts_offset) {
1492                 CFStringAppendFormat(result, NULL, CFSTR("%@%ld : %@ (%ld)\n"), entryPrefix, bkt.idx, vDesc, bkt.count);
1493             } else {
1494                 CFStringAppendFormat(result, NULL, CFSTR("%@%ld : %@\n"), entryPrefix, bkt.idx, vDesc);
1495             }
1496             if (kDesc) CFRelease(kDesc);
1497             if (vDesc) CFRelease(vDesc);
1498             return (Boolean)true;
1499         });
1500     CFStringAppendFormat(result, NULL, CFSTR("%@}\n"), prefix);
1501     return result;
1502 }
1503
1504 __private_extern__ void CFBasicHashShow(CFBasicHashRef ht) {
1505     CFStringRef str = CFBasicHashCopyDescription(ht, true, CFSTR(""), CFSTR("\t"), false);
1506     CFShow(str);
1507     CFRelease(str);
1508 }
1509
1510 __private_extern__ Boolean __CFBasicHashEqual(CFTypeRef cf1, CFTypeRef cf2) {
1511     CFBasicHashRef ht1 = (CFBasicHashRef)cf1;
1512     CFBasicHashRef ht2 = (CFBasicHashRef)cf2;
1513 //#warning this used to require that the key and value equal callbacks were pointer identical
1514     return CFBasicHashesAreEqual(ht1, ht2);
1515 }
1516
1517 __private_extern__ CFHashCode __CFBasicHashHash(CFTypeRef cf) {
1518     CFBasicHashRef ht = (CFBasicHashRef)cf;
1519     return CFBasicHashGetCount(ht);
1520 }
1521
1522 __private_extern__ CFStringRef __CFBasicHashCopyDescription(CFTypeRef cf) {
1523     CFBasicHashRef ht = (CFBasicHashRef)cf;
1524     CFStringRef desc = CFBasicHashCopyDescription(ht, false, CFSTR(""), CFSTR("\t"), true);
1525     CFStringRef result = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<CFBasicHash %p [%p]>%@"), cf, CFGetAllocator(cf), desc);
1526     CFRelease(desc);
1527     return result;
1528 }
1529
1530 __private_extern__ void __CFBasicHashDeallocate(CFTypeRef cf) {
1531     CFBasicHashRef ht = (CFBasicHashRef)cf;
1532     if (ht->bits.finalized) HALT;
1533     ht->bits.finalized = 1;
1534     __CFBasicHashDrain(ht, true);
1535 #if ENABLE_MEMORY_COUNTERS
1536     OSAtomicAdd64Barrier(-1, &__CFBasicHashTotalCount);
1537     OSAtomicAdd32Barrier(-1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1538 #endif
1539 }
1540
1541 static CFTypeID __kCFBasicHashTypeID = _kCFRuntimeNotATypeID;
1542
1543 static const CFRuntimeClass __CFBasicHashClass = {
1544     _kCFRuntimeScannedObject,
1545     "CFBasicHash",
1546     NULL,        // init
1547     NULL,        // copy
1548     __CFBasicHashDeallocate,
1549     __CFBasicHashEqual,
1550     __CFBasicHashHash,
1551     NULL,        //
1552     __CFBasicHashCopyDescription
1553 };
1554
1555 __private_extern__ CFTypeID CFBasicHashGetTypeID(void) {
1556     if (_kCFRuntimeNotATypeID == __kCFBasicHashTypeID) __kCFBasicHashTypeID = _CFRuntimeRegisterClass(&__CFBasicHashClass);
1557     return __kCFBasicHashTypeID;
1558 }
1559
1560 CFBasicHashRef CFBasicHashCreate(CFAllocatorRef allocator, CFOptionFlags flags, const CFBasicHashCallbacks *cb) {
1561     size_t size = sizeof(struct __CFBasicHash) - sizeof(CFRuntimeBase);
1562     if (flags & kCFBasicHashHasValues2) size += sizeof(CFBasicHashValue *); // values2
1563     if (flags & kCFBasicHashHasKeys) size += sizeof(CFBasicHashValue *); // keys
1564     if (flags & kCFBasicHashHasKeys2) size += sizeof(CFBasicHashValue *); // keys2
1565     if (flags & kCFBasicHashHasCounts) size += sizeof(uintptr_t *); // counts
1566     if (flags & kCFBasicHashHasOrder) size += sizeof(uintptr_t *); // order
1567     if (flags & kCFBasicHashHasHashCache) size += sizeof(uintptr_t *); // hashes
1568     CFBasicHashRef ht = (CFBasicHashRef)_CFRuntimeCreateInstance(allocator, CFBasicHashGetTypeID(), size, NULL);
1569     if (NULL == ht) HALT;
1570
1571     ht->bits.finalized = 0;
1572     ht->bits.strong_values = (flags & kCFBasicHashStrongValues) ? 1 : 0;
1573     ht->bits.strong_values2 = 0;
1574     ht->bits.strong_keys = (flags & kCFBasicHashStrongKeys) ? 1 : 0;
1575     ht->bits.strong_keys2 = 0;
1576     ht->bits.hash_style = (flags >> 13) & 0x3;
1577     ht->bits.fast_grow = (flags & kCFBasicHashAggressiveGrowth) ? 1 : 0;
1578     ht->bits.__0 = 0;
1579     ht->bits.num_buckets_idx = 0;
1580     ht->bits.used_buckets = 0;
1581     ht->bits.marker = 0;
1582     ht->bits.deleted = 0;
1583     ht->bits.mutations = 1;
1584
1585     uint64_t offset = 1;
1586     ht->bits.values2_offset = 0;
1587     ht->bits.keys_offset = (flags & kCFBasicHashHasKeys) ? offset++ : 0;
1588     ht->bits.keys2_offset = 0;
1589     ht->bits.counts_offset = (flags & kCFBasicHashHasCounts) ? offset++ : 0;
1590     ht->bits.orders_offset = 0;
1591     ht->bits.hashes_offset = (flags & kCFBasicHashHasHashCache) ? offset++ : 0;
1592
1593     __AssignWithWriteBarrier(&ht->callbacks, cb);
1594     for (CFIndex idx = 0; idx < offset; idx++) {
1595         ht->pointers[idx] = NULL;
1596     }
1597
1598 #if ENABLE_MEMORY_COUNTERS
1599     int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
1600     while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize));
1601     int64_t count_now = OSAtomicAdd64Barrier(1, & __CFBasicHashTotalCount);
1602     while (__CFBasicHashPeakCount < count_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakCount, count_now, & __CFBasicHashPeakCount));
1603     OSAtomicAdd32Barrier(1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1604 #endif
1605
1606     return ht;
1607 }
1608
1609 CFBasicHashRef CFBasicHashCreateCopy(CFAllocatorRef allocator, CFBasicHashRef src_ht) {
1610     size_t size = CFBasicHashGetSize(src_ht, false) - sizeof(CFRuntimeBase);
1611     CFBasicHashRef ht = (CFBasicHashRef)_CFRuntimeCreateInstance(allocator, CFBasicHashGetTypeID(), size, NULL);
1612     if (NULL == ht) HALT;
1613
1614     memmove((uint8_t *)ht + sizeof(CFRuntimeBase), (uint8_t *)src_ht + sizeof(CFRuntimeBase), sizeof(ht->bits));
1615     if (kCFUseCollectableAllocator && !CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
1616         ht->bits.strong_values = 0;
1617         ht->bits.strong_values2 = 0;
1618         ht->bits.strong_keys = 0;
1619         ht->bits.strong_keys2 = 0;
1620     }
1621     ht->bits.finalized = 0;
1622     ht->bits.mutations = 1;
1623     __AssignWithWriteBarrier(&ht->callbacks, src_ht->callbacks->func(ht, kCFBasicHashCallbackOpCopyCallbacks, (uintptr_t)allocator, 0, src_ht->callbacks));
1624     if (NULL == ht->callbacks) HALT;
1625
1626     CFIndex new_num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1627     if (0 == new_num_buckets) {
1628 #if ENABLE_MEMORY_COUNTERS
1629         int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
1630         while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize));
1631         int64_t count_now = OSAtomicAdd64Barrier(1, & __CFBasicHashTotalCount);
1632         while (__CFBasicHashPeakCount < count_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakCount, count_now, & __CFBasicHashPeakCount));
1633         OSAtomicAdd32Barrier(1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1634 #endif
1635         return ht;
1636     }
1637
1638     CFBasicHashValue *new_values = NULL, *new_values2 = NULL, *new_keys = NULL, *new_keys2 = NULL;
1639     uintptr_t *new_counts = NULL, *new_orders = NULL, *new_hashes = NULL;
1640
1641     if (0 < new_num_buckets) {
1642         new_values = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), ht->bits.strong_values);
1643         __SetLastAllocationEventName(new_values, "CFBasicHash (value-store)");
1644         if (0 != ht->bits.values2_offset) {
1645             new_values2 = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), ht->bits.strong_values2);
1646             __SetLastAllocationEventName(new_values2, "CFBasicHash (value2-store)");
1647         }
1648         if (0 != ht->bits.keys_offset) {
1649             new_keys = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), ht->bits.strong_keys);
1650             __SetLastAllocationEventName(new_keys, "CFBasicHash (key-store)");
1651         }
1652         if (0 != ht->bits.keys2_offset) {
1653             new_keys2 = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), ht->bits.strong_keys2);
1654             __SetLastAllocationEventName(new_keys2, "CFBasicHash (key2-store)");
1655         }
1656         if (0 != ht->bits.counts_offset) {
1657             new_counts = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(uintptr_t), false);
1658             __SetLastAllocationEventName(new_counts, "CFBasicHash (count-store)");
1659         }
1660         if (0 != ht->bits.orders_offset) {
1661             new_orders = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(uintptr_t), false);
1662             __SetLastAllocationEventName(new_orders, "CFBasicHash (order-store)");
1663         }
1664         if (0 != ht->bits.hashes_offset) {
1665             new_hashes = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(uintptr_t), false);
1666             __SetLastAllocationEventName(new_hashes, "CFBasicHash (hash-store)");
1667         }
1668     }
1669
1670     uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
1671     CFBasicHashValue *old_values = NULL, *old_values2 = NULL, *old_keys = NULL, *old_keys2 = NULL;
1672     uintptr_t *old_counts = NULL, *old_orders = NULL, *old_hashes = NULL;
1673     old_values = __CFBasicHashGetValues(src_ht);
1674     if (0 != src_ht->bits.values2_offset) {
1675         old_values2 = __CFBasicHashGetValues2(src_ht);
1676     }
1677     if (0 != src_ht->bits.keys_offset) {
1678         old_keys = __CFBasicHashGetKeys(src_ht);
1679     }
1680     if (0 != src_ht->bits.keys2_offset) {
1681         old_keys2 = __CFBasicHashGetKeys2(src_ht);
1682     }
1683     if (0 != src_ht->bits.counts_offset) {
1684         old_counts = __CFBasicHashGetCounts(src_ht);
1685     }
1686     if (0 != src_ht->bits.orders_offset) {
1687         old_orders = __CFBasicHashGetOrders(src_ht);
1688     }
1689     if (0 != src_ht->bits.hashes_offset) {
1690         old_hashes = __CFBasicHashGetHashes(src_ht);
1691     }
1692
1693     CFBasicHashValue *keys = old_keys ? old_keys : old_values;
1694     for (CFIndex idx = 0; idx < new_num_buckets; idx++) {
1695         uintptr_t stack_key = keys[idx].weak;
1696         if (stack_key != empty && stack_key != deleted) {
1697             uintptr_t stack_value = __CFBasicHashImportValue(ht, old_values[idx].weak);
1698             if (ht->bits.strong_values) new_values[idx].strong = (id)stack_value; else new_values[idx].weak = stack_value;
1699             if (new_values2) {
1700                 uintptr_t stack_value2 = __CFBasicHashImportValue2(ht, old_values2[idx].weak);
1701                 if (ht->bits.strong_values2) new_values2[idx].strong = (id)stack_value2; else new_values2[idx].weak = stack_value2;
1702             }
1703             if (new_keys) {
1704                 uintptr_t stack_key = __CFBasicHashImportKey(ht, old_keys[idx].weak);
1705                 if (ht->bits.strong_keys) new_keys[idx].strong = (id)stack_key; else new_keys[idx].weak = stack_key;
1706             }
1707             if (new_keys2) {
1708                 uintptr_t stack_key2 = __CFBasicHashImportKey2(ht, old_keys2[idx].weak);
1709                 if (ht->bits.strong_keys2) new_keys2[idx].strong = (id)stack_key2; else new_keys2[idx].weak = stack_key2;
1710             }
1711         } else {
1712             if (ht->bits.strong_values) new_values[idx].strong = (id)stack_key; else new_values[idx].weak = stack_key;
1713             if (new_values2) {
1714                 if (ht->bits.strong_values2) new_values2[idx].strong = (id)stack_key; else new_values2[idx].weak = stack_key;
1715             }
1716             if (new_keys) {
1717                 if (ht->bits.strong_keys) new_keys[idx].strong = (id)stack_key; else new_keys[idx].weak = stack_key;
1718             }
1719             if (new_keys2) {
1720                 if (ht->bits.strong_keys2) new_keys2[idx].strong = (id)stack_key; else new_keys2[idx].weak = stack_key;
1721             }
1722         }
1723     }
1724     if (new_counts) memmove(new_counts, old_counts, new_num_buckets * sizeof(uintptr_t));
1725     if (new_orders) memmove(new_orders, old_orders, new_num_buckets * sizeof(uintptr_t));
1726     if (new_hashes) memmove(new_hashes, old_hashes, new_num_buckets * sizeof(uintptr_t));
1727
1728     __CFBasicHashSetValues(ht, new_values);
1729     if (new_values2) {
1730         __CFBasicHashSetValues2(ht, new_values2);
1731     }
1732     if (new_keys) {
1733         __CFBasicHashSetKeys(ht, new_keys);
1734     }
1735     if (new_keys2) {
1736         __CFBasicHashSetKeys2(ht, new_keys2);
1737     }
1738     if (new_counts) {
1739         __CFBasicHashSetCounts(ht, new_counts);
1740     }
1741     if (new_orders) {
1742         __CFBasicHashSetOrders(ht, new_orders);
1743     }
1744     if (new_hashes) {
1745         __CFBasicHashSetHashes(ht, new_hashes);
1746     }
1747
1748 #if ENABLE_MEMORY_COUNTERS
1749     int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
1750     while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize));
1751     int64_t count_now = OSAtomicAdd64Barrier(1, & __CFBasicHashTotalCount);
1752     while (__CFBasicHashPeakCount < count_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakCount, count_now, & __CFBasicHashPeakCount));
1753     OSAtomicAdd32Barrier(1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1754 #endif
1755
1756     return ht;
1757 }
1758
1759 void _CFbhx588461(CFBasicHashRef ht, Boolean growth) {
1760     if (!CFBasicHashIsMutable(ht)) HALT;
1761     if (ht->bits.finalized) HALT;
1762     ht->bits.fast_grow = growth ? 1 : 0;
1763 }
1764