1/*
2 * Copyright (c) 2014 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-2013, 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.
38static
39#if FIND_BUCKET_FOR_REHASH
40CFIndex
41#else
42CFBasicHashBucket
43#endif
44FIND_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
199