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