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