1  /*
  2   * Copyright (c) 2015 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-2014, 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