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/*	CFBasicHash.h
25	Copyright (c) 2008-2013, Apple Inc. All rights reserved.
26*/
27
28#include <CoreFoundation/CFBase.h>
29#include <CoreFoundation/CFString.h>
30#include "CFInternal.h"
31
32CF_EXTERN_C_BEGIN
33
34struct __objcFastEnumerationStateEquivalent2 {
35    unsigned long state;
36    unsigned long *itemsPtr;
37    unsigned long *mutationsPtr;
38    unsigned long extra[5];
39};
40
41enum {
42    __kCFBasicHashLinearHashingValue = 1,
43    __kCFBasicHashDoubleHashingValue = 2,
44    __kCFBasicHashExponentialHashingValue = 3,
45};
46
47enum {
48    kCFBasicHashHasKeys = (1UL << 0),
49    kCFBasicHashHasCounts = (1UL << 1),
50    kCFBasicHashHasHashCache = (1UL << 2),
51
52    kCFBasicHashIntegerValues = (1UL << 6),
53    kCFBasicHashIntegerKeys = (1UL << 7),
54
55    kCFBasicHashStrongValues = (1UL << 8),
56    kCFBasicHashStrongKeys = (1UL << 9),
57
58    kCFBasicHashWeakValues = (1UL << 10),
59    kCFBasicHashWeakKeys = (1UL << 11),
60
61    kCFBasicHashIndirectKeys = (1UL << 12),
62
63    kCFBasicHashLinearHashing = (__kCFBasicHashLinearHashingValue << 13), // bits 13-14
64    kCFBasicHashDoubleHashing = (__kCFBasicHashDoubleHashingValue << 13),
65    kCFBasicHashExponentialHashing = (__kCFBasicHashExponentialHashingValue << 13),
66
67    kCFBasicHashAggressiveGrowth = (1UL << 15),
68};
69
70// Note that for a hash table without keys, the value is treated as the key,
71// and the value should be passed in as the key for operations which take a key.
72
73typedef struct {
74    CFIndex idx;
75    uintptr_t weak_key;
76    uintptr_t weak_value;
77    uintptr_t count;
78} CFBasicHashBucket;
79
80typedef struct __CFBasicHash *CFBasicHashRef;
81typedef const struct __CFBasicHash *CFConstBasicHashRef;
82
83// Bit 6 in the CF_INFO_BITS of the CFRuntimeBase inside the CFBasicHashRef is the "is immutable" bit
84CF_INLINE Boolean CFBasicHashIsMutable(CFConstBasicHashRef ht) {
85    return __CFBitfieldGetValue(((CFRuntimeBase *)ht)->_cfinfo[CF_INFO_BITS], 6, 6) ? false : true;
86}
87
88CF_INLINE void CFBasicHashMakeImmutable(CFBasicHashRef ht) {
89    __CFBitfieldSetValue(((CFRuntimeBase *)ht)->_cfinfo[CF_INFO_BITS], 6, 6, 1);
90}
91
92
93typedef struct __CFBasicHashCallbacks CFBasicHashCallbacks;
94
95struct __CFBasicHashCallbacks {
96    uintptr_t (*retainValue)(CFAllocatorRef alloc, uintptr_t stack_value);	// Return 2nd arg or new value
97    uintptr_t (*retainKey)(CFAllocatorRef alloc, uintptr_t stack_key);	// Return 2nd arg or new key
98    void (*releaseValue)(CFAllocatorRef alloc, uintptr_t stack_value);
99    void (*releaseKey)(CFAllocatorRef alloc, uintptr_t stack_key);
100    Boolean (*equateValues)(uintptr_t coll_value1, uintptr_t stack_value2); // 1st arg is in-collection value, 2nd arg is probe parameter OR in-collection value for a second collection
101    Boolean (*equateKeys)(uintptr_t coll_key1, uintptr_t stack_key2); // 1st arg is in-collection key, 2nd arg is probe parameter
102    CFHashCode (*hashKey)(uintptr_t stack_key);
103    uintptr_t (*getIndirectKey)(uintptr_t coll_value);	// Return key; 1st arg is in-collection value
104    CFStringRef (*copyValueDescription)(uintptr_t stack_value);
105    CFStringRef (*copyKeyDescription)(uintptr_t stack_key);
106};
107
108Boolean CFBasicHashHasStrongValues(CFConstBasicHashRef ht);
109Boolean CFBasicHashHasStrongKeys(CFConstBasicHashRef ht);
110
111CFOptionFlags CFBasicHashGetFlags(CFConstBasicHashRef ht);
112CFIndex CFBasicHashGetNumBuckets(CFConstBasicHashRef ht);
113CFIndex CFBasicHashGetCapacity(CFConstBasicHashRef ht);
114void CFBasicHashSetCapacity(CFBasicHashRef ht, CFIndex capacity);
115
116CFIndex CFBasicHashGetCount(CFConstBasicHashRef ht);
117CFBasicHashBucket CFBasicHashGetBucket(CFConstBasicHashRef ht, CFIndex idx);
118CFBasicHashBucket CFBasicHashFindBucket(CFConstBasicHashRef ht, uintptr_t stack_key);
119CFIndex CFBasicHashGetCountOfKey(CFConstBasicHashRef ht, uintptr_t stack_key);
120CFIndex CFBasicHashGetCountOfValue(CFConstBasicHashRef ht, uintptr_t stack_value);
121Boolean CFBasicHashesAreEqual(CFConstBasicHashRef ht1, CFConstBasicHashRef ht2);
122void CFBasicHashApply(CFConstBasicHashRef ht, Boolean (^block)(CFBasicHashBucket));
123void CFBasicHashApplyIndexed(CFConstBasicHashRef ht, CFRange range, Boolean (^block)(CFBasicHashBucket));
124void CFBasicHashGetElements(CFConstBasicHashRef ht, CFIndex bufferslen, uintptr_t *weak_values, uintptr_t *weak_keys);
125
126Boolean CFBasicHashAddValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value);
127void CFBasicHashReplaceValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value);
128void CFBasicHashSetValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value);
129CFIndex CFBasicHashRemoveValue(CFBasicHashRef ht, uintptr_t stack_key);
130CFIndex CFBasicHashRemoveValueAtIndex(CFBasicHashRef ht, CFIndex idx);
131void CFBasicHashRemoveAllValues(CFBasicHashRef ht);
132
133Boolean CFBasicHashAddIntValueAndInc(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t int_value);
134void CFBasicHashRemoveIntValueAndDec(CFBasicHashRef ht, uintptr_t int_value);
135
136size_t CFBasicHashGetSize(CFConstBasicHashRef ht, Boolean total);
137void CFBasicHashSuppressRC(CFBasicHashRef ht);
138void CFBasicHashUnsuppressRC(CFBasicHashRef ht);
139
140CFStringRef CFBasicHashCopyDescription(CFConstBasicHashRef ht, Boolean detailed, CFStringRef linePrefix, CFStringRef entryLinePrefix, Boolean describeElements);
141
142CFTypeID CFBasicHashGetTypeID(void);
143
144extern Boolean __CFBasicHashEqual(CFTypeRef cf1, CFTypeRef cf2);
145extern CFHashCode __CFBasicHashHash(CFTypeRef cf);
146extern CFStringRef __CFBasicHashCopyDescription(CFTypeRef cf);
147extern void __CFBasicHashDeallocate(CFTypeRef cf);
148extern unsigned long __CFBasicHashFastEnumeration(CFConstBasicHashRef ht, struct __objcFastEnumerationStateEquivalent2 *state, void *stackbuffer, unsigned long count);
149
150// creation functions create mutable CFBasicHashRefs
151CFBasicHashRef CFBasicHashCreate(CFAllocatorRef allocator, CFOptionFlags flags, const CFBasicHashCallbacks *cb);
152CFBasicHashRef CFBasicHashCreateCopy(CFAllocatorRef allocator, CFConstBasicHashRef ht);
153
154
155CF_EXTERN_C_END
156
157