![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to hash.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / GNUtools / cc / objc|
Return to hash.c CVS log | Up to [Apple XNU] / GNUtools / cc / objc |
1.1 root 1: /* Hash tables for Objective C internal structures
2: Copyright (C) 1993 Free Software Foundation, Inc.
3:
4: This file is part of GNU CC.
5:
6: GNU CC is free software; you can redistribute it and/or modify
7: it under the terms of the GNU General Public License as published by
8: the Free Software Foundation; either version 2, or (at your option)
9: any later version.
10:
11: GNU CC is distributed in the hope that it will be useful,
12: but WITHOUT ANY WARRANTY; without even the implied warranty of
13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14: GNU General Public License for more details.
15:
16: You should have received a copy of the GNU General Public License
17: along with GNU CC; see the file COPYING. If not, write to
18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
19:
20: /* As a special exception, if you link this library with files
21: compiled with GCC to produce an executable, this does not cause
22: the resulting executable to be covered by the GNU General Public License.
23: This exception does not however invalidate any other reasons why
24: the executable file might be covered by the GNU General Public License. */
25:
26: #include "assert.h"
27:
28: #include "objc/hash.h"
29: #include "objc/objc.h"
30:
31: #include "runtime.h" /* for DEBUG_PRINTF */
32:
33: /* These two macros determine when a hash table is full and
34: by how much it should be expanded respectively.
35:
36: These equations are percentages. */
37: #define FULLNESS(cache) \
38: ((((cache)->size * 75) / 100) <= (cache)->used)
39: #define EXPANSION(cache) \
40: ((cache)->size * 2)
41:
42: void *__objc_xcalloc (size_t, size_t);
43:
44: cache_ptr
45: hash_new (unsigned int size, hash_func_type hash_func,
46: compare_func_type compare_func)
47: {
48: cache_ptr cache;
49:
50: /* Pass me a value greater than 0 and a power of 2. */
51: assert (size);
52: assert (!(size & (size - 1)));
53:
54: /* Allocate the cache structure. calloc insures
55: its initialization for default values. */
56: cache = (cache_ptr) __objc_xcalloc (1, sizeof (struct cache));
57: assert (cache);
58:
59: /* Allocate the array of buckets for the cache.
60: calloc initializes all of the pointers to NULL. */
61: cache->node_table
62: = (node_ptr *) __objc_xcalloc (size, sizeof (node_ptr));
63: assert (cache->node_table);
64:
65: cache->size = size;
66:
67: /* This should work for all processor architectures? */
68: cache->mask = (size - 1);
69:
70: /* Store the hashing function so that codes can be computed. */
71: cache->hash_func = hash_func;
72:
73: /* Store the function that compares hash keys to
74: determine if they are equal. */
75: cache->compare_func = compare_func;
76:
77: return cache;
78: }
79:
80:
81: void
82: hash_delete (cache_ptr cache)
83: {
84: node_ptr node;
85:
86:
87: /* Purge all key/value pairs from the table. */
88: while ((node = hash_next (cache, NULL)))
89: hash_remove (cache, node->key);
90:
91: /* Release the array of nodes and the cache itself. */
92: free (cache->node_table);
93: free (cache);
94: }
95:
96:
97: void
98: hash_add (cache_ptr *cachep, const void *key, void *value)
99: {
100: size_t indx = (*(*cachep)->hash_func)(*cachep, key);
101: node_ptr node = (node_ptr) __objc_xcalloc (1, sizeof (struct cache_node));
102:
103:
104: assert (node);
105:
106: /* Initialize the new node. */
107: node->key = key;
108: node->value = value;
109: node->next = (*cachep)->node_table[indx];
110:
111: /* Debugging.
112: Check the list for another key. */
113: #ifdef DEBUG
114: { node_ptr node1 = (*cachep)->node_table[indx];
115:
116: while (node1) {
117:
118: assert (node1->key != key);
119: node1 = node1->next;
120: }
121: }
122: #endif
123:
124: /* Install the node as the first element on the list. */
125: (*cachep)->node_table[indx] = node;
126:
127: /* Bump the number of entries in the cache. */
128: ++(*cachep)->used;
129:
130: /* Check the hash table's fullness. We're going
131: to expand if it is above the fullness level. */
132: if (FULLNESS (*cachep)) {
133:
134: /* The hash table has reached its fullness level. Time to
135: expand it.
136:
137: I'm using a slow method here but is built on other
138: primitive functions thereby increasing its
139: correctness. */
140: node_ptr node1 = NULL;
141: cache_ptr new = hash_new (EXPANSION (*cachep),
142: (*cachep)->hash_func,
143: (*cachep)->compare_func);
144:
145: DEBUG_PRINTF ("Expanding cache %#x from %d to %d\n",
146: *cachep, (*cachep)->size, new->size);
147:
148: /* Copy the nodes from the first hash table to the new one. */
149: while ((node1 = hash_next (*cachep, node1)))
150: hash_add (&new, node1->key, node1->value);
151:
152: /* Trash the old cache. */
153: hash_delete (*cachep);
154:
155: /* Return a pointer to the new hash table. */
156: *cachep = new;
157: }
158: }
159:
160:
161: void
162: hash_remove (cache_ptr cache, const void *key)
163: {
164: size_t indx = (*cache->hash_func)(cache, key);
165: node_ptr node = cache->node_table[indx];
166:
167:
168: /* We assume there is an entry in the table. Error if it is not. */
169: assert (node);
170:
171: /* Special case. First element is the key/value pair to be removed. */
172: if ((*cache->compare_func)(node->key, key)) {
173: cache->node_table[indx] = node->next;
174: free (node);
175: } else {
176:
177: /* Otherwise, find the hash entry. */
178: node_ptr prev = node;
179: BOOL removed = NO;
180:
181: do {
182:
183: if ((*cache->compare_func)(node->key, key)) {
184: prev->next = node->next, removed = YES;
185: free (node);
186: } else
187: prev = node, node = node->next;
188: } while (!removed && node);
189: assert (removed);
190: }
191:
192: /* Decrement the number of entries in the hash table. */
193: --cache->used;
194: }
195:
196:
197: node_ptr
198: hash_next (cache_ptr cache, node_ptr node)
199: {
200: /* If the scan is being started then reset the last node
201: visitied pointer and bucket index. */
202: if (!node)
203: cache->last_bucket = 0;
204:
205: /* If there is a node visited last then check for another
206: entry in the same bucket; Otherwise step to the next bucket. */
207: if (node) {
208: if (node->next)
209: /* There is a node which follows the last node
210: returned. Step to that node and retun it. */
211: return node->next;
212: else
213: ++cache->last_bucket;
214: }
215:
216: /* If the list isn't exhausted then search the buckets for
217: other nodes. */
218: if (cache->last_bucket < cache->size) {
219: /* Scan the remainder of the buckets looking for an entry
220: at the head of the list. Return the first item found. */
221: while (cache->last_bucket < cache->size)
222: if (cache->node_table[cache->last_bucket])
223: return cache->node_table[cache->last_bucket];
224: else
225: ++cache->last_bucket;
226:
227: /* No further nodes were found in the hash table. */
228: return NULL;
229: } else
230: return NULL;
231: }
232:
233:
234: /* Given KEY, return corresponding value for it in CACHE.
235: Return NULL if the KEY is not recorded. */
236:
237: void *
238: hash_value_for_key (cache_ptr cache, const void *key)
239: {
240: node_ptr node = cache->node_table[(*cache->hash_func)(cache, key)];
241: void *retval = NULL;
242:
243: if (node)
244: do {
245: if ((*cache->compare_func)(node->key, key))
246: retval = node->value;
247: else
248: node = node->next;
249: } while (!retval && node);
250:
251: return retval;
252: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.