source: trunk/third/gcc/libobjc/hash.c @ 21199

Revision 21199, 7.5 KB checked in by ghudson, 20 years ago (diff)
This commit was generated by cvs2svn to compensate for changes in r21198, which included commits to RCS files with non-trunk default branches.
RevLine 
[14547]1/* Hash tables for Objective C internal structures
2   Copyright (C) 1993, 1996, 1997 Free Software Foundation, Inc.
3
[21198]4This file is part of GCC.
[14547]5
[21198]6GCC is free software; you can redistribute it and/or modify
[14547]7it under the terms of the GNU General Public License as published by
8the Free Software Foundation; either version 2, or (at your option)
9any later version.
10
[21198]11GCC is distributed in the hope that it will be useful,
[14547]12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
[21198]17along with GCC; see the file COPYING.  If not, write to
[14547]18the Free Software Foundation, 59 Temple Place - Suite 330,
19Boston, MA 02111-1307, USA.  */
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
29#include "hash.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
42cache_ptr
43hash_new (unsigned int size, hash_func_type hash_func,
44          compare_func_type compare_func)
45{
46  cache_ptr cache;
47
48  /* Pass me a value greater than 0 and a power of 2.  */
49  assert (size);
[20088]50  assert (! (size & (size - 1)));
[14547]51
52  /* Allocate the cache structure.  calloc insures
53     its initialization for default values.  */
54  cache = (cache_ptr) objc_calloc (1, sizeof (struct cache));
55  assert (cache);
56
57  /* Allocate the array of buckets for the cache.
58     calloc initializes all of the pointers to NULL.  */
59  cache->node_table
60    = (node_ptr *) objc_calloc (size, sizeof (node_ptr));
61  assert (cache->node_table);
62
63  cache->size  = size;
64
65  /* This should work for all processor architectures? */
66  cache->mask = (size - 1);
67       
68  /* Store the hashing function so that codes can be computed.  */
69  cache->hash_func = hash_func;
70
71  /* Store the function that compares hash keys to
72     determine if they are equal.  */
73  cache->compare_func = compare_func;
74
75  return cache;
76}
77
78
79void
80hash_delete (cache_ptr cache)
81{
82  node_ptr node;
83  node_ptr next_node;
84  unsigned int i;
85
86  /* Purge all key/value pairs from the table.  */
87  /* Step through the nodes one by one and remove every node WITHOUT
88     using hash_next. this makes hash_delete much more efficient. */
89  for (i = 0;i < cache->size;i++) {
90    if ((node = cache->node_table[i])) {
91      /* an entry in the hash table has been found, now step through the
92         nodes next in the list and free them. */
93      while ((next_node = node->next)) {
94        hash_remove (cache,node->key);
95        node = next_node;
96      }
97
98      hash_remove (cache,node->key);
99    }
100  }
101
102  /* Release the array of nodes and the cache itself.  */
103  objc_free(cache->node_table);
104  objc_free(cache);
105}
106
107
108void
109hash_add (cache_ptr *cachep, const void *key, void *value)
110{
111  size_t indx = (*(*cachep)->hash_func)(*cachep, key);
112  node_ptr node = (node_ptr) objc_calloc (1, sizeof (struct cache_node));
113
114
115  assert (node);
116
117  /* Initialize the new node.  */
118  node->key    = key;
119  node->value  = value;
120  node->next  = (*cachep)->node_table[indx];
121
122  /* Debugging.
123     Check the list for another key.  */
124#ifdef DEBUG
125  { node_ptr node1 = (*cachep)->node_table[indx];
126
127    while (node1) {
128
129      assert (node1->key != key);
130      node1 = node1->next;
131    }
132  }
133#endif
134
135  /* Install the node as the first element on the list.  */
136  (*cachep)->node_table[indx] = node;
137
138  /* Bump the number of entries in the cache.  */
139  ++(*cachep)->used;
140
141  /* Check the hash table's fullness.   We're going
142     to expand if it is above the fullness level.  */
143  if (FULLNESS (*cachep)) {
144
145    /* The hash table has reached its fullness level.  Time to
146       expand it.
147
148       I'm using a slow method here but is built on other
149       primitive functions thereby increasing its
150       correctness.  */
151    node_ptr node1 = NULL;
152    cache_ptr new = hash_new (EXPANSION (*cachep),
153                              (*cachep)->hash_func,
154                              (*cachep)->compare_func);
155
156    DEBUG_PRINTF ("Expanding cache %#x from %d to %d\n",
157                  *cachep, (*cachep)->size, new->size);
158
159    /* Copy the nodes from the first hash table to the new one.  */
160    while ((node1 = hash_next (*cachep, node1)))
161      hash_add (&new, node1->key, node1->value);
162
163    /* Trash the old cache.  */
164    hash_delete (*cachep);
165
166    /* Return a pointer to the new hash table.  */
167    *cachep = new;
168  }
169}
170
171
172void
173hash_remove (cache_ptr cache, const void *key)
174{
175  size_t indx = (*cache->hash_func)(cache, key);
176  node_ptr node = cache->node_table[indx];
177
178
179  /* We assume there is an entry in the table.  Error if it is not.  */
180  assert (node);
181
182  /* Special case.  First element is the key/value pair to be removed.  */
183  if ((*cache->compare_func)(node->key, key)) {
184    cache->node_table[indx] = node->next;
185    objc_free(node);
186  } else {
187
188    /* Otherwise, find the hash entry.  */
189    node_ptr prev = node;
190    BOOL removed = NO;
191
192    do {
193
194      if ((*cache->compare_func)(node->key, key)) {
195        prev->next = node->next, removed = YES;
196        objc_free(node);
197      } else
198        prev = node, node = node->next;
[20088]199    } while (! removed && node);
[14547]200    assert (removed);
201  }
202
203  /* Decrement the number of entries in the hash table.  */
204  --cache->used;
205}
206
207
208node_ptr
209hash_next (cache_ptr cache, node_ptr node)
210{
211  /* If the scan is being started then reset the last node
212     visitied pointer and bucket index.  */
[20088]213  if (! node)
[14547]214    cache->last_bucket  = 0;
215
216  /* If there is a node visited last then check for another
217     entry in the same bucket;  Otherwise step to the next bucket.  */
218  if (node) {
219    if (node->next)
220      /* There is a node which follows the last node
221         returned.  Step to that node and retun it.  */
222      return node->next;
223    else
224      ++cache->last_bucket;
225  }
226
227  /* If the list isn't exhausted then search the buckets for
228     other nodes.  */
229  if (cache->last_bucket < cache->size) {
230    /*  Scan the remainder of the buckets looking for an entry
231        at the head of the list.  Return the first item found.  */
232    while (cache->last_bucket < cache->size)
233      if (cache->node_table[cache->last_bucket])
234        return cache->node_table[cache->last_bucket];
235      else
236        ++cache->last_bucket;
237
238    /* No further nodes were found in the hash table.  */
239    return NULL;
240  } else
241    return NULL;
242}
243
244
245/* Given KEY, return corresponding value for it in CACHE.
246   Return NULL if the KEY is not recorded.  */
247
248void *
249hash_value_for_key (cache_ptr cache, const void *key)
250{
251  node_ptr node = cache->node_table[(*cache->hash_func)(cache, key)];
252  void *retval = NULL;
253
254  if (node)
255    do {
256      if ((*cache->compare_func)(node->key, key)) {
257        retval = node->value;
258              break;
259      } else
260        node = node->next;
[20088]261    } while (! retval && node);
[14547]262
263  return retval;
264}
265
266/* Given KEY, return YES if it exists in the CACHE.
267   Return NO if it does not */
268
269BOOL
270hash_is_key_in_hash (cache_ptr cache, const void *key)
271{
272  node_ptr node = cache->node_table[(*cache->hash_func)(cache, key)];
273
274  if (node)
275    do {
276      if ((*cache->compare_func)(node->key, key))
277          return YES;
278      else
279        node = node->next;
280    } while (node);
281
282  return NO;
283}
Note: See TracBrowser for help on using the repository browser.