/ CFBasicHashFindBucket.m
CFBasicHashFindBucket.m
1 /* 2 * Copyright (c) 2015 Apple Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23 24 /* CFBasicHashFindBucket.m 25 Copyright (c) 2009-2014, Apple Inc. All rights reserved. 26 Responsibility: Christopher Kane 27 */ 28 29 30 #if !defined(FIND_BUCKET_NAME) || !defined(FIND_BUCKET_HASH_STYLE) || !defined(FIND_BUCKET_FOR_REHASH) || !defined(FIND_BUCKET_FOR_INDIRECT_KEY) 31 #error All of FIND_BUCKET_NAME, FIND_BUCKET_HASH_STYLE, FIND_BUCKET_FOR_REHASH, and FIND_BUCKET_FOR_INDIRECT_KEY must be defined before #including this file. 32 #endif 33 34 35 // During rehashing of a mutable CFBasicHash, we know that there are no 36 // deleted slots and the keys have already been uniqued. When rehashing, 37 // if key_hash is non-0, we use it as the hash code. 38 static 39 #if FIND_BUCKET_FOR_REHASH 40 CFIndex 41 #else 42 CFBasicHashBucket 43 #endif 44 FIND_BUCKET_NAME (CFConstBasicHashRef ht, uintptr_t stack_key 45 #if FIND_BUCKET_FOR_REHASH 46 , uintptr_t key_hash 47 #endif 48 ) { 49 uint8_t num_buckets_idx = ht->bits.num_buckets_idx; 50 uintptr_t num_buckets = __CFBasicHashTableSizes[num_buckets_idx]; 51 #if FIND_BUCKET_FOR_REHASH 52 CFHashCode hash_code = key_hash ? key_hash : __CFBasicHashHashKey(ht, stack_key); 53 #else 54 CFHashCode hash_code = __CFBasicHashHashKey(ht, stack_key); 55 #endif 56 57 #if FIND_BUCKET_HASH_STYLE == 1 // __kCFBasicHashLinearHashingValue 58 // Linear probing, with c = 1 59 // probe[0] = h1(k) 60 // probe[i] = (h1(k) + i * c) mod num_buckets, i = 1 .. num_buckets - 1 61 // h1(k) = k mod num_buckets 62 #if defined(__arm__) 63 uintptr_t h1 = __CFBasicHashFold(hash_code, num_buckets_idx); 64 #else 65 uintptr_t h1 = hash_code % num_buckets; 66 #endif 67 #elif FIND_BUCKET_HASH_STYLE == 2 // __kCFBasicHashDoubleHashingValue 68 // Double hashing 69 // probe[0] = h1(k) 70 // probe[i] = (h1(k) + i * h2(k)) mod num_buckets, i = 1 .. num_buckets - 1 71 // h1(k) = k mod num_buckets 72 // h2(k) = floor(k / num_buckets) mod num_buckets 73 #if defined(__arm__) 74 uintptr_t h1 = __CFBasicHashFold(hash_code, num_buckets_idx); 75 uintptr_t h2 = __CFBasicHashFold(hash_code / num_buckets, num_buckets_idx); 76 #else 77 uintptr_t h1 = hash_code % num_buckets; 78 uintptr_t h2 = (hash_code / num_buckets) % num_buckets; 79 #endif 80 if (0 == h2) h2 = num_buckets - 1; 81 #elif FIND_BUCKET_HASH_STYLE == 3 // __kCFBasicHashExponentialHashingValue 82 // Improved exponential hashing 83 // probe[0] = h1(k) 84 // probe[i] = (h1(k) + pr(k)^i * h2(k)) mod num_buckets, i = 1 .. num_buckets - 1 85 // h1(k) = k mod num_buckets 86 // h2(k) = floor(k / num_buckets) mod num_buckets 87 // note: h2(k) has the effect of rotating the sequence if it is constant 88 // note: pr(k) is any primitive root of num_buckets, varying this gives different sequences 89 #if defined(__arm__) 90 uintptr_t h1 = __CFBasicHashFold(hash_code, num_buckets_idx); 91 uintptr_t h2 = __CFBasicHashFold(hash_code / num_buckets, num_buckets_idx); 92 #else 93 uintptr_t h1 = hash_code % num_buckets; 94 uintptr_t h2 = (hash_code / num_buckets) % num_buckets; 95 #endif 96 if (0 == h2) h2 = num_buckets - 1; 97 uintptr_t pr = __CFBasicHashPrimitiveRoots[num_buckets_idx]; 98 #endif 99 100 COCOA_HASHTABLE_PROBING_START(ht, num_buckets); 101 CFBasicHashValue *keys = (ht->bits.keys_offset) ? __CFBasicHashGetKeys(ht) : __CFBasicHashGetValues(ht); 102 #if !FIND_BUCKET_FOR_REHASH 103 uintptr_t *hashes = (__CFBasicHashHasHashCache(ht)) ? __CFBasicHashGetHashes(ht) : NULL; 104 #endif 105 CFIndex deleted_idx = kCFNotFound; 106 uintptr_t probe = h1; 107 #if FIND_BUCKET_HASH_STYLE == 3 // __kCFBasicHashExponentialHashingValue 108 uintptr_t acc = pr; 109 #endif 110 for (CFIndex idx = 0; idx < num_buckets; idx++) { 111 uintptr_t curr_key = keys[probe].neutral; 112 if (curr_key == 0UL) { 113 COCOA_HASHTABLE_PROBE_EMPTY(ht, probe); 114 #if FIND_BUCKET_FOR_REHASH 115 CFIndex result = (kCFNotFound == deleted_idx) ? probe : deleted_idx; 116 #else 117 CFBasicHashBucket result; 118 result.idx = (kCFNotFound == deleted_idx) ? probe : deleted_idx; 119 result.count = 0; 120 #endif 121 COCOA_HASHTABLE_PROBING_END(ht, idx + 1); 122 return result; 123 #if !FIND_BUCKET_FOR_REHASH 124 } else if (curr_key == ~0UL) { 125 COCOA_HASHTABLE_PROBE_DELETED(ht, probe); 126 if (kCFNotFound == deleted_idx) { 127 deleted_idx = probe; 128 } 129 } else { 130 COCOA_HASHTABLE_PROBE_VALID(ht, probe); 131 if (__CFBasicHashSubABZero == curr_key) curr_key = 0UL; 132 if (__CFBasicHashSubABOne == curr_key) curr_key = ~0UL; 133 #if FIND_BUCKET_FOR_INDIRECT_KEY 134 // curr_key holds the value coming in here 135 curr_key = __CFBasicHashGetIndirectKey(ht, curr_key); 136 #endif 137 if (curr_key == stack_key || ((!hashes || hashes[probe] == hash_code) && __CFBasicHashTestEqualKey(ht, curr_key, stack_key))) { 138 COCOA_HASHTABLE_PROBING_END(ht, idx + 1); 139 #if FIND_BUCKET_FOR_REHASH 140 CFIndex result = probe; 141 #else 142 CFBasicHashBucket result; 143 result.idx = probe; 144 result.weak_value = __CFBasicHashGetValue(ht, probe); 145 result.weak_key = curr_key; 146 result.count = (ht->bits.counts_offset) ? __CFBasicHashGetSlotCount(ht, probe) : 1; 147 #endif 148 return result; 149 } 150 #endif 151 } 152 153 #if FIND_BUCKET_HASH_STYLE == 1 // __kCFBasicHashLinearHashingValue 154 probe += 1; 155 if (num_buckets <= probe) { 156 probe -= num_buckets; 157 } 158 #elif FIND_BUCKET_HASH_STYLE == 2 // __kCFBasicHashDoubleHashingValue 159 probe += h2; 160 if (num_buckets <= probe) { 161 probe -= num_buckets; 162 } 163 #elif FIND_BUCKET_HASH_STYLE == 3 // __kCFBasicHashExponentialHashingValue 164 probe = h1 + h2 * acc; 165 if (num_buckets <= probe) { 166 #if defined(__arm__) 167 probe = __CFBasicHashFold(probe, num_buckets_idx); 168 #else 169 probe = probe % num_buckets; 170 #endif 171 } 172 acc = acc * pr; 173 if (num_buckets <= acc) { 174 #if defined(__arm__) 175 acc = __CFBasicHashFold(acc, num_buckets_idx); 176 #else 177 acc = acc % num_buckets; 178 #endif 179 } 180 #endif 181 182 } 183 COCOA_HASHTABLE_PROBING_END(ht, num_buckets); 184 #if FIND_BUCKET_FOR_REHASH 185 CFIndex result = deleted_idx; 186 #else 187 CFBasicHashBucket result; 188 result.idx = deleted_idx; 189 result.count = 0; 190 #endif 191 return result; // all buckets full or deleted, return first deleted element which was found 192 } 193 194 #undef FIND_BUCKET_NAME 195 #undef FIND_BUCKET_HASH_STYLE 196 #undef FIND_BUCKET_FOR_REHASH 197 #undef FIND_BUCKET_FOR_INDIRECT_KEY 198