[apple/cf.git] / CFBasicHash.h

/*
 * Copyright (c) 2010 Apple Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */

/*	CFBasicHash.h
	Copyright (c) 2008-2009, Apple Inc. All rights reserved.
*/

#include <CoreFoundation/CFBase.h>
#include <CoreFoundation/CFString.h>
#include "CFInternal.h"

CF_EXTERN_C_BEGIN

struct __objcFastEnumerationStateEquivalent2 {
    unsigned long state;
    unsigned long *itemsPtr;
    unsigned long *mutationsPtr;
    unsigned long extra[5];
};

enum {
    __kCFBasicHashLinearHashingValue = 1,
    __kCFBasicHashDoubleHashingValue = 2,
    __kCFBasicHashExponentialHashingValue = 3,
};

enum {
    kCFBasicHashHasValues2 = (1UL << 2),
    kCFBasicHashHasKeys = (1UL << 3),
    kCFBasicHashHasKeys2 = (1UL << 4),
    kCFBasicHashHasCounts = (1UL << 5),
    kCFBasicHashHasOrder = (1UL << 6),
    kCFBasicHashHasHashCache = (1UL << 7),

    kCFBasicHashStrongValues = (1UL << 9),
    kCFBasicHashStrongValues2 = (1UL << 10),
    kCFBasicHashStrongKeys = (1UL << 11),
    kCFBasicHashStrongKeys2 = (1UL << 12),

    kCFBasicHashLinearHashing = (__kCFBasicHashLinearHashingValue << 13), // bits 13-14
    kCFBasicHashDoubleHashing = (__kCFBasicHashDoubleHashingValue << 13),
    kCFBasicHashExponentialHashing = (__kCFBasicHashExponentialHashingValue << 13),

    kCFBasicHashAggressiveGrowth = (1UL << 15),
};

// Note that for a hash table without keys, the value is treated as the key,
// and the value should be passed in as the key for operations which take a key.

typedef struct {
    CFIndex idx;
    uintptr_t weak_key;
    uintptr_t weak_key2;
    uintptr_t weak_value;
    uintptr_t weak_value2;
    uintptr_t count;
    uintptr_t order;
} CFBasicHashBucket;

typedef struct __CFBasicHash *CFBasicHashRef;

// Bit 6 in the CF_INFO_BITS of the CFRuntimeBase inside the CFBasicHashRef is the "is immutable" bit
CF_INLINE Boolean CFBasicHashIsMutable(CFBasicHashRef ht) {
    return __CFBitfieldGetValue(((CFRuntimeBase *)ht)->_cfinfo[CF_INFO_BITS], 6, 6) ? false : true;
}
CF_INLINE void CFBasicHashMakeImmutable(CFBasicHashRef ht) {
    __CFBitfieldSetValue(((CFRuntimeBase *)ht)->_cfinfo[CF_INFO_BITS], 6, 6, 1);
}


typedef struct __CFBasicHashCallbacks CFBasicHashCallbacks;

typedef uintptr_t (*CFBasicHashCallbackType)(CFBasicHashRef ht, uint8_t op, uintptr_t a1, uintptr_t a2, const CFBasicHashCallbacks *cb);

enum {
    kCFBasicHashCallbackOpCopyCallbacks = 8,	// Return new value; REQUIRED
    kCFBasicHashCallbackOpFreeCallbacks = 9,	// Return 0; REQUIRED

    kCFBasicHashCallbackOpRetainValue = 10,	// Return first arg or new value; REQUIRED
    kCFBasicHashCallbackOpRetainValue2 = 11,	// Return first arg or new value
    kCFBasicHashCallbackOpRetainKey = 12,	// Return first arg or new key; REQUIRED
    kCFBasicHashCallbackOpRetainKey2 = 13,	// Return first arg or new key
    kCFBasicHashCallbackOpReleaseValue = 14,	// Return 0; REQUIRED
    kCFBasicHashCallbackOpReleaseValue2 = 15,	// Return 0
    kCFBasicHashCallbackOpReleaseKey = 16,	// Return 0; REQUIRED
    kCFBasicHashCallbackOpReleaseKey2 = 17,	// Return 0
    kCFBasicHashCallbackOpValueEqual = 18,	// Return 0 or 1; REQUIRED
    kCFBasicHashCallbackOpValue2Equal = 19,	// Return 0 or 1
    kCFBasicHashCallbackOpKeyEqual = 20,	// Return 0 or 1; REQUIRED
    kCFBasicHashCallbackOpKey2Equal = 21,	// Return 0 or 1
    kCFBasicHashCallbackOpHashKey = 22,		// Return hash code; REQUIRED
    kCFBasicHashCallbackOpHashKey2 = 23,	// Return hash code
    kCFBasicHashCallbackOpDescribeValue = 24,	// Return retained CFStringRef; REQUIRED
    kCFBasicHashCallbackOpDescribeValue2 = 25,	// Return retained CFStringRef
    kCFBasicHashCallbackOpDescribeKey = 26,	// Return retained CFStringRef; REQUIRED
    kCFBasicHashCallbackOpDescribeKey2 = 27,	// Return retained CFStringRef
};

struct __CFBasicHashCallbacks {
    CFBasicHashCallbackType func; // must not be NULL
    uintptr_t context[0]; // variable size; any pointers in here must remain valid as long as the CFBasicHash
};

extern const CFBasicHashCallbacks CFBasicHashNullCallbacks;
extern const CFBasicHashCallbacks CFBasicHashStandardCallbacks;


CFOptionFlags CFBasicHashGetFlags(CFBasicHashRef ht);
CFIndex CFBasicHashGetNumBuckets(CFBasicHashRef ht);
CFIndex CFBasicHashGetCapacity(CFBasicHashRef ht);
void CFBasicHashSetCapacity(CFBasicHashRef ht, CFIndex capacity);

CFIndex CFBasicHashGetCount(CFBasicHashRef ht);
CFBasicHashBucket CFBasicHashGetBucket(CFBasicHashRef ht, CFIndex idx);
CFBasicHashBucket CFBasicHashFindBucket(CFBasicHashRef ht, uintptr_t stack_key);
CFIndex CFBasicHashGetCountOfKey(CFBasicHashRef ht, uintptr_t stack_key);
CFIndex CFBasicHashGetCountOfValue(CFBasicHashRef ht, uintptr_t stack_value);
Boolean CFBasicHashesAreEqual(CFBasicHashRef ht1, CFBasicHashRef ht2);
void CFBasicHashApply(CFBasicHashRef ht, Boolean (^block)(CFBasicHashBucket));
void CFBasicHashGetElements(CFBasicHashRef ht, CFIndex bufferslen, uintptr_t *weak_values, uintptr_t *weak_values2, uintptr_t *weak_keys, uintptr_t *weak_keys2);

void CFBasicHashAddValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value);
void CFBasicHashReplaceValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value);
void CFBasicHashSetValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value);
CFIndex CFBasicHashRemoveValue(CFBasicHashRef ht, uintptr_t stack_key);
void CFBasicHashRemoveAllValues(CFBasicHashRef ht);

size_t CFBasicHashGetSize(CFBasicHashRef ht, Boolean total);

CFStringRef CFBasicHashCopyDescription(CFBasicHashRef ht, Boolean detailed, CFStringRef linePrefix, CFStringRef entryLinePrefix, Boolean describeElements);

CFTypeID CFBasicHashGetTypeID(void);

extern Boolean __CFBasicHashEqual(CFTypeRef cf1, CFTypeRef cf2);
extern CFHashCode __CFBasicHashHash(CFTypeRef cf);
extern CFStringRef __CFBasicHashCopyDescription(CFTypeRef cf);
extern void __CFBasicHashDeallocate(CFTypeRef cf);
extern unsigned long __CFBasicHashFastEnumeration(CFBasicHashRef ht, struct __objcFastEnumerationStateEquivalent2 *state, void *stackbuffer, unsigned long count);

// creation functions create mutable CFBasicHashRefs
CFBasicHashRef CFBasicHashCreate(CFAllocatorRef allocator, CFOptionFlags flags, const CFBasicHashCallbacks *cb);
CFBasicHashRef CFBasicHashCreateCopy(CFAllocatorRef allocator, CFBasicHashRef ht);


CF_EXTERN_C_END
Commit	Line	Data
cf7d2af9	1	/*
e588f561	2	* Copyright (c) 2010 Apple Inc. All rights reserved.
cf7d2af9 A	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	*/
f64f9b69	23
cf7d2af9 A	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