CFBasicHash.h

   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
  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
  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
  73 typedef struct {
  74     CFIndex idx;
  75     uintptr_t weak_key;
  76     uintptr_t weak_value;
  77     uintptr_t count;
  78 } CFBasicHashBucket;
  79
  80 typedef struct __CFBasicHash *CFBasicHashRef;
  81 typedef const struct __CFBasicHash *CFConstBasicHashRef;
  82
  83 // Bit 6 in the CF_INFO_BITS of the CFRuntimeBase inside the CFBasicHashRef is the "is immutable" bit
  84 CF_INLINE Boolean CFBasicHashIsMutable(CFConstBasicHashRef ht) {
  85     return __CFBitfieldGetValue(((CFRuntimeBase *)ht)->_cfinfo[CF_INFO_BITS], 6, 6) ? false : true;
  86 }
  87
  88 CF_INLINE void CFBasicHashMakeImmutable(CFBasicHashRef ht) {
  89     __CFBitfieldSetValue(((CFRuntimeBase *)ht)->_cfinfo[CF_INFO_BITS], 6, 6, 1);
  90 }
  91
  92
  93 typedef struct __CFBasicHashCallbacks CFBasicHashCallbacks;
  94
  95 struct __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
 108 Boolean CFBasicHashHasStrongValues(CFConstBasicHashRef ht);
 109 Boolean CFBasicHashHasStrongKeys(CFConstBasicHashRef ht);
 110
 111 CFOptionFlags CFBasicHashGetFlags(CFConstBasicHashRef ht);
 112 CFIndex CFBasicHashGetNumBuckets(CFConstBasicHashRef ht);
 113 CFIndex CFBasicHashGetCapacity(CFConstBasicHashRef ht);
 114 void CFBasicHashSetCapacity(CFBasicHashRef ht, CFIndex capacity);
 115
 116 CFIndex CFBasicHashGetCount(CFConstBasicHashRef ht);
 117 CFBasicHashBucket CFBasicHashGetBucket(CFConstBasicHashRef ht, CFIndex idx);
 118 CFBasicHashBucket CFBasicHashFindBucket(CFConstBasicHashRef ht, uintptr_t stack_key);
 119 CFIndex CFBasicHashGetCountOfKey(CFConstBasicHashRef ht, uintptr_t stack_key);
 120 CFIndex CFBasicHashGetCountOfValue(CFConstBasicHashRef ht, uintptr_t stack_value);
 121 Boolean CFBasicHashesAreEqual(CFConstBasicHashRef ht1, CFConstBasicHashRef ht2);
 122 void CFBasicHashApply(CFConstBasicHashRef ht, Boolean (^block)(CFBasicHashBucket));
 123 void CFBasicHashApplyIndexed(CFConstBasicHashRef ht, CFRange range, Boolean (^block)(CFBasicHashBucket));
 124 void CFBasicHashGetElements(CFConstBasicHashRef ht, CFIndex bufferslen, uintptr_t *weak_values, uintptr_t *weak_keys);
 125
 126 Boolean CFBasicHashAddValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value);
 127 void CFBasicHashReplaceValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value);
 128 void CFBasicHashSetValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value);
 129 CFIndex CFBasicHashRemoveValue(CFBasicHashRef ht, uintptr_t stack_key);
 130 CFIndex CFBasicHashRemoveValueAtIndex(CFBasicHashRef ht, CFIndex idx);
 131 void CFBasicHashRemoveAllValues(CFBasicHashRef ht);
 132
 133 Boolean CFBasicHashAddIntValueAndInc(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t int_value);
 134 void CFBasicHashRemoveIntValueAndDec(CFBasicHashRef ht, uintptr_t int_value);
 135
 136 size_t CFBasicHashGetSize(CFConstBasicHashRef ht, Boolean total);
 137 void CFBasicHashSuppressRC(CFBasicHashRef ht);
 138 void CFBasicHashUnsuppressRC(CFBasicHashRef ht);
 139
 140 CFStringRef CFBasicHashCopyDescription(CFConstBasicHashRef ht, Boolean detailed, CFStringRef linePrefix, CFStringRef entryLinePrefix, Boolean describeElements);
 141
 142 CFTypeID CFBasicHashGetTypeID(void);
 143
 144 extern Boolean __CFBasicHashEqual(CFTypeRef cf1, CFTypeRef cf2);
 145 extern CFHashCode __CFBasicHashHash(CFTypeRef cf);
 146 extern CFStringRef __CFBasicHashCopyDescription(CFTypeRef cf);
 147 extern void __CFBasicHashDeallocate(CFTypeRef cf);
 148 extern unsigned long __CFBasicHashFastEnumeration(CFConstBasicHashRef ht, struct __objcFastEnumerationStateEquivalent2 *state, void *stackbuffer, unsigned long count);
 149
 150 // creation functions create mutable CFBasicHashRefs
 151 CFBasicHashRef CFBasicHashCreate(CFAllocatorRef allocator, CFOptionFlags flags, const CFBasicHashCallbacks *cb);
 152 CFBasicHashRef CFBasicHashCreateCopy(CFAllocatorRef allocator, CFConstBasicHashRef ht);
 153
 154
 155 CF_EXTERN_C_END
 156