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