CFBasicHash.h

   1 /*
   2  * Copyright (c) 2012 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-2011, Apple Inc. All rights reserved.
  26 */
  27
  28 #include <CoreFoundation/CFBase.h>
  29 #include <CoreFoundation/CFString.h>
  30 #include "CFInternal.h"
  31
  32 CF_EXTERN_C_BEGIN
  33
  34 struct __objcFastEnumerationStateEquivalent2 {
  35     unsigned long state;
  36     unsigned long *itemsPtr;
  37     unsigned long *mutationsPtr;
  38     unsigned long extra[5];
  39 };
  40
  41 enum {
  42     __kCFBasicHashLinearHashingValue = 1,
  43     __kCFBasicHashDoubleHashingValue = 2,
  44     __kCFBasicHashExponentialHashingValue = 3,
  45 };
  46
  47 enum {
  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     kCFBasicHashCompactableValues = (1UL << 16),
  70     kCFBasicHashCompactableKeys = (1UL << 17),
  71 };
  72
  73 // Note that for a hash table without keys, the value is treated as the key,
  74 // and the value should be passed in as the key for operations which take a key.
  75
  76 typedef struct {
  77     CFIndex idx;
  78     uintptr_t weak_key;
  79     uintptr_t weak_value;
  80     uintptr_t count;
  81 } CFBasicHashBucket;
  82
  83 typedef struct __CFBasicHash *CFBasicHashRef;
  84 typedef const struct __CFBasicHash *CFConstBasicHashRef;
  85
  86 // Bit 6 in the CF_INFO_BITS of the CFRuntimeBase inside the CFBasicHashRef is the "is immutable" bit
  87 CF_INLINE Boolean CFBasicHashIsMutable(CFConstBasicHashRef ht) {
  88     return __CFBitfieldGetValue(((CFRuntimeBase *)ht)->_cfinfo[CF_INFO_BITS], 6, 6) ? false : true;
  89 }
  90
  91 CF_INLINE void CFBasicHashMakeImmutable(CFBasicHashRef ht) {
  92     __CFBitfieldSetValue(((CFRuntimeBase *)ht)->_cfinfo[CF_INFO_BITS], 6, 6, 1);
  93 }
  94
  95
  96 typedef struct __CFBasicHashCallbacks CFBasicHashCallbacks;
  97
  98 struct __CFBasicHashCallbacks {
  99     CFBasicHashCallbacks *(*copyCallbacks)(CFConstBasicHashRef ht, CFAllocatorRef allocator, CFBasicHashCallbacks *cb); // Return new value
 100     void (*freeCallbacks)(CFConstBasicHashRef ht, CFAllocatorRef allocator, CFBasicHashCallbacks *cb);
 101     uintptr_t (*retainValue)(CFConstBasicHashRef ht, uintptr_t stack_value);    // Return 2nd arg or new value
 102     uintptr_t (*retainKey)(CFConstBasicHashRef ht, uintptr_t stack_key);        // Return 2nd arg or new key
 103     void (*releaseValue)(CFConstBasicHashRef ht, uintptr_t stack_value);
 104     void (*releaseKey)(CFConstBasicHashRef ht, uintptr_t stack_key);
 105     Boolean (*equateValues)(CFConstBasicHashRef ht, uintptr_t coll_value1, uintptr_t stack_value2); // 2nd arg is in-collection value, 3rd arg is probe parameter OR in-collection value for a second collection
 106     Boolean (*equateKeys)(CFConstBasicHashRef ht, uintptr_t coll_key1, uintptr_t stack_key2); // 2nd arg is in-collection key, 3rd arg is probe parameter
 107     uintptr_t (*hashKey)(CFConstBasicHashRef ht, uintptr_t stack_key);
 108     uintptr_t (*getIndirectKey)(CFConstBasicHashRef ht, uintptr_t coll_value);  // Return key; 2nd arg is in-collection value
 109     CFStringRef (*copyValueDescription)(CFConstBasicHashRef ht, uintptr_t stack_value);
 110     CFStringRef (*copyKeyDescription)(CFConstBasicHashRef ht, uintptr_t stack_key);
 111     uintptr_t context[0]; // variable size; any pointers in here must remain valid as long as the CFBasicHash
 112 };
 113
 114 Boolean CFBasicHashHasStrongValues(CFConstBasicHashRef ht);
 115 Boolean CFBasicHashHasStrongKeys(CFConstBasicHashRef ht);
 116
 117 uint16_t CFBasicHashGetSpecialBits(CFConstBasicHashRef ht);
 118 uint16_t CFBasicHashSetSpecialBits(CFBasicHashRef ht, uint16_t bits);
 119
 120 CFOptionFlags CFBasicHashGetFlags(CFConstBasicHashRef ht);
 121 CFIndex CFBasicHashGetNumBuckets(CFConstBasicHashRef ht);
 122 CFIndex CFBasicHashGetCapacity(CFConstBasicHashRef ht);
 123 void CFBasicHashSetCapacity(CFBasicHashRef ht, CFIndex capacity);
 124
 125 const CFBasicHashCallbacks *CFBasicHashGetCallbacks(CFConstBasicHashRef ht);
 126 CFIndex CFBasicHashGetCount(CFConstBasicHashRef ht);
 127 CFBasicHashBucket CFBasicHashGetBucket(CFConstBasicHashRef ht, CFIndex idx);
 128 CFBasicHashBucket CFBasicHashFindBucket(CFConstBasicHashRef ht, uintptr_t stack_key);
 129 CFIndex CFBasicHashGetCountOfKey(CFConstBasicHashRef ht, uintptr_t stack_key);
 130 CFIndex CFBasicHashGetCountOfValue(CFConstBasicHashRef ht, uintptr_t stack_value);
 131 Boolean CFBasicHashesAreEqual(CFConstBasicHashRef ht1, CFConstBasicHashRef ht2);
 132 void CFBasicHashApply(CFConstBasicHashRef ht, Boolean (^block)(CFBasicHashBucket));
 133 void CFBasicHashApplyIndexed(CFConstBasicHashRef ht, CFRange range, Boolean (^block)(CFBasicHashBucket));
 134 void CFBasicHashGetElements(CFConstBasicHashRef ht, CFIndex bufferslen, uintptr_t *weak_values, uintptr_t *weak_keys);
 135
 136 Boolean CFBasicHashAddValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value);
 137 void CFBasicHashReplaceValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value);
 138 void CFBasicHashSetValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value);
 139 CFIndex CFBasicHashRemoveValue(CFBasicHashRef ht, uintptr_t stack_key);
 140 CFIndex CFBasicHashRemoveValueAtIndex(CFBasicHashRef ht, CFIndex idx);
 141 void CFBasicHashRemoveAllValues(CFBasicHashRef ht);
 142
 143 Boolean CFBasicHashAddIntValueAndInc(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t int_value);
 144 void CFBasicHashRemoveIntValueAndDec(CFBasicHashRef ht, uintptr_t int_value);
 145
 146 size_t CFBasicHashGetSize(CFConstBasicHashRef ht, Boolean total);
 147
 148 CFStringRef CFBasicHashCopyDescription(CFConstBasicHashRef ht, Boolean detailed, CFStringRef linePrefix, CFStringRef entryLinePrefix, Boolean describeElements);
 149
 150 CFTypeID CFBasicHashGetTypeID(void);
 151
 152 extern Boolean __CFBasicHashEqual(CFTypeRef cf1, CFTypeRef cf2);
 153 extern CFHashCode __CFBasicHashHash(CFTypeRef cf);
 154 extern CFStringRef __CFBasicHashCopyDescription(CFTypeRef cf);
 155 extern void __CFBasicHashDeallocate(CFTypeRef cf);
 156 extern unsigned long __CFBasicHashFastEnumeration(CFConstBasicHashRef ht, struct __objcFastEnumerationStateEquivalent2 *state, void *stackbuffer, unsigned long count);
 157
 158 // creation functions create mutable CFBasicHashRefs
 159 CFBasicHashRef CFBasicHashCreate(CFAllocatorRef allocator, CFOptionFlags flags, const CFBasicHashCallbacks *cb);
 160 CFBasicHashRef CFBasicHashCreateCopy(CFAllocatorRef allocator, CFConstBasicHashRef ht);
 161 void __CFBasicHashSetCallbacks(CFBasicHashRef ht, const CFBasicHashCallbacks *cb);
 162
 163
 164 CF_EXTERN_C_END
 165