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