CFBasicHash.m

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