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