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