CFBasicHash.h

   1 /*
   2  * Copyright (c) 2009 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-2009, 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     kCFBasicHashHasValues2 = (1UL << 2),
  49     kCFBasicHashHasKeys = (1UL << 3),
  50     kCFBasicHashHasKeys2 = (1UL << 4),
  51     kCFBasicHashHasCounts = (1UL << 5),
  52     kCFBasicHashHasOrder = (1UL << 6),
  53     kCFBasicHashHasHashCache = (1UL << 7),
  54
  55     kCFBasicHashStrongValues = (1UL << 9),
  56     kCFBasicHashStrongValues2 = (1UL << 10),
  57     kCFBasicHashStrongKeys = (1UL << 11),
  58     kCFBasicHashStrongKeys2 = (1UL << 12),
  59
  60     kCFBasicHashLinearHashing = (__kCFBasicHashLinearHashingValue << 13), // bits 13-14
  61     kCFBasicHashDoubleHashing = (__kCFBasicHashDoubleHashingValue << 13),
  62     kCFBasicHashExponentialHashing = (__kCFBasicHashExponentialHashingValue << 13),
  63
  64     kCFBasicHashAggressiveGrowth = (1UL << 15),
  65 };
  66
  67 // Note that for a hash table without keys, the value is treated as the key,
  68 // and the value should be passed in as the key for operations which take a key.
  69
  70 typedef struct {
  71     CFIndex idx;
  72     uintptr_t weak_key;
  73     uintptr_t weak_key2;
  74     uintptr_t weak_value;
  75     uintptr_t weak_value2;
  76     uintptr_t count;
  77     uintptr_t order;
  78 } CFBasicHashBucket;
  79
  80 typedef struct __CFBasicHash *CFBasicHashRef;
  81
  82 // Bit 6 in the CF_INFO_BITS of the CFRuntimeBase inside the CFBasicHashRef is the "is immutable" bit
  83 CF_INLINE Boolean CFBasicHashIsMutable(CFBasicHashRef ht) {
  84     return __CFBitfieldGetValue(((CFRuntimeBase *)ht)->_cfinfo[CF_INFO_BITS], 6, 6) ? false : true;
  85 }
  86 CF_INLINE void CFBasicHashMakeImmutable(CFBasicHashRef ht) {
  87     __CFBitfieldSetValue(((CFRuntimeBase *)ht)->_cfinfo[CF_INFO_BITS], 6, 6, 1);
  88 }
  89
  90
  91 typedef struct __CFBasicHashCallbacks CFBasicHashCallbacks;
  92
  93 typedef uintptr_t (*CFBasicHashCallbackType)(CFBasicHashRef ht, uint8_t op, uintptr_t a1, uintptr_t a2, const CFBasicHashCallbacks *cb);
  94
  95 enum {
  96     kCFBasicHashCallbackOpCopyCallbacks = 8,    // Return new value; REQUIRED
  97     kCFBasicHashCallbackOpFreeCallbacks = 9,    // Return 0; REQUIRED
  98
  99     kCFBasicHashCallbackOpRetainValue = 10,     // Return first arg or new value; REQUIRED
 100     kCFBasicHashCallbackOpRetainValue2 = 11,    // Return first arg or new value
 101     kCFBasicHashCallbackOpRetainKey = 12,       // Return first arg or new key; REQUIRED
 102     kCFBasicHashCallbackOpRetainKey2 = 13,      // Return first arg or new key
 103     kCFBasicHashCallbackOpReleaseValue = 14,    // Return 0; REQUIRED
 104     kCFBasicHashCallbackOpReleaseValue2 = 15,   // Return 0
 105     kCFBasicHashCallbackOpReleaseKey = 16,      // Return 0; REQUIRED
 106     kCFBasicHashCallbackOpReleaseKey2 = 17,     // Return 0
 107     kCFBasicHashCallbackOpValueEqual = 18,      // Return 0 or 1; REQUIRED
 108     kCFBasicHashCallbackOpValue2Equal = 19,     // Return 0 or 1
 109     kCFBasicHashCallbackOpKeyEqual = 20,        // Return 0 or 1; REQUIRED
 110     kCFBasicHashCallbackOpKey2Equal = 21,       // Return 0 or 1
 111     kCFBasicHashCallbackOpHashKey = 22,         // Return hash code; REQUIRED
 112     kCFBasicHashCallbackOpHashKey2 = 23,        // Return hash code
 113     kCFBasicHashCallbackOpDescribeValue = 24,   // Return retained CFStringRef; REQUIRED
 114     kCFBasicHashCallbackOpDescribeValue2 = 25,  // Return retained CFStringRef
 115     kCFBasicHashCallbackOpDescribeKey = 26,     // Return retained CFStringRef; REQUIRED
 116     kCFBasicHashCallbackOpDescribeKey2 = 27,    // Return retained CFStringRef
 117 };
 118
 119 struct __CFBasicHashCallbacks {
 120     CFBasicHashCallbackType func; // must not be NULL
 121     uintptr_t context[0]; // variable size; any pointers in here must remain valid as long as the CFBasicHash
 122 };
 123
 124 extern const CFBasicHashCallbacks CFBasicHashNullCallbacks;
 125 extern const CFBasicHashCallbacks CFBasicHashStandardCallbacks;
 126
 127
 128 CFOptionFlags CFBasicHashGetFlags(CFBasicHashRef ht);
 129 CFIndex CFBasicHashGetNumBuckets(CFBasicHashRef ht);
 130 CFIndex CFBasicHashGetCapacity(CFBasicHashRef ht);
 131 void CFBasicHashSetCapacity(CFBasicHashRef ht, CFIndex capacity);
 132
 133 CFIndex CFBasicHashGetCount(CFBasicHashRef ht);
 134 CFBasicHashBucket CFBasicHashGetBucket(CFBasicHashRef ht, CFIndex idx);
 135 CFBasicHashBucket CFBasicHashFindBucket(CFBasicHashRef ht, uintptr_t stack_key);
 136 CFIndex CFBasicHashGetCountOfKey(CFBasicHashRef ht, uintptr_t stack_key);
 137 CFIndex CFBasicHashGetCountOfValue(CFBasicHashRef ht, uintptr_t stack_value);
 138 Boolean CFBasicHashesAreEqual(CFBasicHashRef ht1, CFBasicHashRef ht2);
 139 void CFBasicHashApply(CFBasicHashRef ht, Boolean (^block)(CFBasicHashBucket));
 140 void CFBasicHashGetElements(CFBasicHashRef ht, CFIndex bufferslen, uintptr_t *weak_values, uintptr_t *weak_values2, uintptr_t *weak_keys, uintptr_t *weak_keys2);
 141
 142 void CFBasicHashAddValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value);
 143 void CFBasicHashReplaceValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value);
 144 void CFBasicHashSetValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value);
 145 CFIndex CFBasicHashRemoveValue(CFBasicHashRef ht, uintptr_t stack_key);
 146 void CFBasicHashRemoveAllValues(CFBasicHashRef ht);
 147
 148 size_t CFBasicHashGetSize(CFBasicHashRef ht, Boolean total);
 149
 150 CFStringRef CFBasicHashCopyDescription(CFBasicHashRef ht, Boolean detailed, CFStringRef linePrefix, CFStringRef entryLinePrefix, Boolean describeElements);
 151
 152 CFTypeID CFBasicHashGetTypeID(void);
 153
 154 extern Boolean __CFBasicHashEqual(CFTypeRef cf1, CFTypeRef cf2);
 155 extern CFHashCode __CFBasicHashHash(CFTypeRef cf);
 156 extern CFStringRef __CFBasicHashCopyDescription(CFTypeRef cf);
 157 extern void __CFBasicHashDeallocate(CFTypeRef cf);
 158 extern unsigned long __CFBasicHashFastEnumeration(CFBasicHashRef ht, struct __objcFastEnumerationStateEquivalent2 *state, void *stackbuffer, unsigned long count);
 159
 160 // creation functions create mutable CFBasicHashRefs
 161 CFBasicHashRef CFBasicHashCreate(CFAllocatorRef allocator, CFOptionFlags flags, const CFBasicHashCallbacks *cb);
 162 CFBasicHashRef CFBasicHashCreateCopy(CFAllocatorRef allocator, CFBasicHashRef ht);
 163
 164
 165 CF_EXTERN_C_END
 166