1/* 2 * Copyright (c) 1999-2003, 2006-2007 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/* maptable.h 24 Scalable hash table of mappings. 25 Bertrand, August 1990 26 Copyright 1990-1996 NeXT Software, Inc. 27*/ 28 29#ifndef _OBJC_MAPTABLE_H_ 30#define _OBJC_MAPTABLE_H_ 31 32#ifndef _OBJC_PRIVATE_H_ 33# define OBJC_MAP_AVAILABILITY __OSX_AVAILABLE_BUT_DEPRECATED(__MAC_10_0,__MAC_10_1, __IPHONE_NA,__IPHONE_NA); 34#else 35# define OBJC_MAP_AVAILABILITY 36#endif 37 38#include <objc/objc.h> 39 40__BEGIN_DECLS 41 42/*************** Definitions ***************/ 43 44 /* This module allows hashing of arbitrary associations [key -> value]. Keys and values must be pointers or integers, and client is responsible for allocating/deallocating this data. A deallocation call-back is provided. 45 NX_MAPNOTAKEY (-1) is used internally as a marker, and therefore keys must always be different from -1. 46 As well-behaved scalable data structures, hash tables double in size when they start becoming full, thus guaranteeing both average constant time access and linear size. */ 47 48typedef struct _NXMapTable { 49 /* private data structure; may change */ 50 const struct _NXMapTablePrototype *prototype; 51 unsigned count; 52 unsigned nbBucketsMinusOne; 53 void *buckets; 54} NXMapTable OBJC_MAP_AVAILABILITY; 55 56typedef struct _NXMapTablePrototype { 57 unsigned (*hash)(NXMapTable *, const void *key); 58 int (*isEqual)(NXMapTable *, const void *key1, const void *key2); 59 void (*free)(NXMapTable *, void *key, void *value); 60 int style; /* reserved for future expansion; currently 0 */ 61} NXMapTablePrototype OBJC_MAP_AVAILABILITY; 62 63 /* invariants assumed by the implementation: 64 A - key != -1 65 B - key1 == key2 => hash(key1) == hash(key2) 66 when key varies over time, hash(key) must remain invariant 67 e.g. if string key, the string must not be changed 68 C - isEqual(key1, key2) => key1 == key2 69 */ 70 71#define NX_MAPNOTAKEY ((void *)(-1)) 72 73/*************** Functions ***************/ 74 75OBJC_EXPORT NXMapTable *NXCreateMapTableFromZone(NXMapTablePrototype prototype, unsigned capacity, void *z) OBJC_MAP_AVAILABILITY; 76OBJC_EXPORT NXMapTable *NXCreateMapTable(NXMapTablePrototype prototype, unsigned capacity) OBJC_MAP_AVAILABILITY; 77 /* capacity is only a hint; 0 creates a small table */ 78 79OBJC_EXPORT void NXFreeMapTable(NXMapTable *table) OBJC_MAP_AVAILABILITY; 80 /* call free for each pair, and recovers table */ 81 82OBJC_EXPORT void NXResetMapTable(NXMapTable *table) OBJC_MAP_AVAILABILITY; 83 /* free each pair; keep current capacity */ 84 85OBJC_EXPORT BOOL NXCompareMapTables(NXMapTable *table1, NXMapTable *table2) OBJC_MAP_AVAILABILITY; 86 /* Returns YES if the two sets are equal (each member of table1 in table2, and table have same size) */ 87 88OBJC_EXPORT unsigned NXCountMapTable(NXMapTable *table) OBJC_MAP_AVAILABILITY; 89 /* current number of data in table */ 90 91OBJC_EXPORT void *NXMapMember(NXMapTable *table, const void *key, void **value) OBJC_MAP_AVAILABILITY; 92 /* return original table key or NX_MAPNOTAKEY. If key is found, value is set */ 93 94OBJC_EXPORT void *NXMapGet(NXMapTable *table, const void *key) OBJC_MAP_AVAILABILITY; 95 /* return original corresponding value or NULL. When NULL need be stored as value, NXMapMember can be used to test for presence */ 96 97OBJC_EXPORT void *NXMapInsert(NXMapTable *table, const void *key, const void *value) OBJC_MAP_AVAILABILITY; 98 /* override preexisting pair; Return previous value or NULL. */ 99 100OBJC_EXPORT void *NXMapRemove(NXMapTable *table, const void *key) OBJC_MAP_AVAILABILITY; 101 /* previous value or NULL is returned */ 102 103/* Iteration over all elements of a table consists in setting up an iteration state and then to progress until all entries have been visited. An example of use for counting elements in a table is: 104 unsigned count = 0; 105 const MyKey *key; 106 const MyValue *value; 107 NXMapState state = NXInitMapState(table); 108 while(NXNextMapState(table, &state, &key, &value)) { 109 count++; 110 } 111*/ 112 113typedef struct {int index;} NXMapState OBJC_MAP_AVAILABILITY; 114 /* callers should not rely on actual contents of the struct */ 115 116OBJC_EXPORT NXMapState NXInitMapState(NXMapTable *table) OBJC_MAP_AVAILABILITY; 117 118OBJC_EXPORT int NXNextMapState(NXMapTable *table, NXMapState *state, const void **key, const void **value) OBJC_MAP_AVAILABILITY; 119 /* returns 0 when all elements have been visited */ 120 121/*************** Conveniences ***************/ 122 123OBJC_EXPORT const NXMapTablePrototype NXPtrValueMapPrototype OBJC_MAP_AVAILABILITY; 124 /* hashing is pointer/integer hashing; 125 isEqual is identity; 126 free is no-op. */ 127OBJC_EXPORT const NXMapTablePrototype NXStrValueMapPrototype OBJC_MAP_AVAILABILITY; 128 /* hashing is string hashing; 129 isEqual is strcmp; 130 free is no-op. */ 131OBJC_EXPORT const NXMapTablePrototype NXObjectMapPrototype OBJC2_UNAVAILABLE; 132 /* for objects; uses methods: hash, isEqual:, free, all for key. */ 133 134__END_DECLS 135 136#endif /* _OBJC_MAPTABLE_H_ */ 137