![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to maptable.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple Darwin 0.x] / objc|
Return to maptable.h CVS log | Up to [Apple Darwin 0.x] / objc |
1.1 root 1: /*
2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * "Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7: * Reserved. This file contains Original Code and/or Modifications of
8: * Original Code as defined in and that are subject to the Apple Public
9: * Source License Version 1.0 (the 'License'). You may not use this file
10: * except in compliance with the License. Please obtain a copy of the
11: * License at http://www.apple.com/publicsource and read it before using
12: * this file.
13: *
14: * The Original Code and all software distributed under the License are
15: * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19: * License for the specific language governing rights and limitations
20: * under the License."
21: *
22: * @APPLE_LICENSE_HEADER_END@
23: */
24: /* maptable.h
25: Scalable hash table of mappings.
26: Bertrand, August 1990
27: Copyright 1990 NeXT, Inc.
28: */
29:
30: #ifndef _OBJC_MAPTABLE_H_
31: #define _OBJC_MAPTABLE_H_
32:
33: #import "objc.h"
34: #import <objc/zone.h>
35:
36: /*************** Definitions ***************/
37:
38: /* 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.
39: NX_MAPNOTAKEY (-1) is used internally as a marker, and therefore keys must always be different from -1.
40: 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. */
41:
42: typedef struct _NXMapTable {
43: /* private data structure; may change */
44: const struct _NXMapTablePrototype *prototype;
45: unsigned count;
46: unsigned nbBuckets;
47: void *buckets;
48: } NXMapTable;
49:
50: typedef struct _NXMapTablePrototype {
51: unsigned (*hash)(NXMapTable *, const void *key);
52: int (*isEqual)(NXMapTable *, const void *key1, const void *key2);
53: void (*free)(NXMapTable *, void *key, void *value);
54: int style; /* reserved for future expansion; currently 0 */
55: } NXMapTablePrototype;
56:
57: /* invariants assumed by the implementation:
58: A - key != -1
59: B - key1 == key2 => hash(key1) == hash(key2)
60: when key varies over time, hash(key) must remain invariant
61: e.g. if string key, the string must not be changed
62: C - isEqual(key1, key2) => key1 == key2
63: */
64:
65: #define NX_MAPNOTAKEY ((void *)(-1))
66:
67: /*************** Functions ***************/
68:
69: extern NXMapTable *NXCreateMapTableFromZone(NXMapTablePrototype prototype, unsigned capacity, NXZone *zone);
70: extern NXMapTable *NXCreateMapTable(NXMapTablePrototype prototype, unsigned capacity);
71: /* capacity is only a hint; 0 creates a small table */
72:
73: extern void NXFreeMapTable(NXMapTable *table);
74: /* call free for each pair, and recovers table */
75:
76: extern void NXResetMapTable(NXMapTable *table);
77: /* free each pair; keep current capacity */
78:
79: extern BOOL NXCompareMapTables(NXMapTable *table1, NXMapTable *table2);
80: /* Returns YES if the two sets are equal (each member of table1 in table2, and table have same size) */
81:
82: extern unsigned NXCountMapTable(NXMapTable *table);
83: /* current number of data in table */
84:
85: extern void *NXMapMember(NXMapTable *table, const void *key, void **value);
86: /* return original table key or NX_MAPNOTAKEY. If key is found, value is set */
87:
88: extern void *NXMapGet(NXMapTable *table, const void *key);
89: /* return original corresponding value or NULL. When NULL need be stored as value, NXMapMember can be used to test for presence */
90:
91: extern void *NXMapInsert(NXMapTable *table, const void *key, const void *value);
92: /* override preexisting pair; Return previous value or NULL. */
93:
94: extern void *NXMapRemove(NXMapTable *table, const void *key);
95: /* previous value or NULL is returned */
96:
97: /* 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:
98: unsigned count = 0;
99: const MyKey *key;
100: const MyValue *value;
101: NXMapState state = NXInitMapState(table);
102: while(NXNextMapState(table, &state, &key, &value)) {
103: count++;
104: }
105: */
106:
107: typedef struct {int index;} NXMapState;
108: /* callers should not rely on actual contents of the struct */
109:
110: extern NXMapState NXInitMapState(NXMapTable *table);
111:
112: extern int NXNextMapState(NXMapTable *table, NXMapState *state, const void **key, const void **value);
113: /* returns 0 when all elements have been visited */
114:
115: /*************** Conveniences ***************/
116:
117: extern const NXMapTablePrototype NXPtrValueMapPrototype;
118: /* hashing is pointer/integer hashing;
119: isEqual is identity;
120: free is no-op. */
121: extern const NXMapTablePrototype NXStrValueMapPrototype;
122: /* hashing is string hashing;
123: isEqual is strcmp;
124: free is no-op. */
125: extern const NXMapTablePrototype NXObjectMapPrototype;
126: /* for objects; uses methods: hash, isEqual:, free, all for key. */
127:
128: #endif /* _OBJC_MAPTABLE_H_ */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.