1 /* Hash tables for Objective C internal structures
2 Copyright (C) 1993, 1996, 1997 Free Software Foundation, Inc.
4 This file is part of GNU CC.
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)
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.
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, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
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. */
29 #include "runtime.h" /* for DEBUG_PRINTF */
32 /* These two macros determine when a hash table is full and
33 by how much it should be expanded respectively.
35 These equations are percentages. */
36 #define FULLNESS(cache) ((((cache)->size * 75) / 100) <= (cache)->used)
37 #define EXPANSION(cache) ((cache)->size * 2)
39 cache_ptr hash_new (unsigned int size, char hashType)
43 /* Pass me a value greater than 0 and a power of 2. */
45 assert (!(size & (size - 1)));
47 /* Allocate the cache structure. calloc insures
48 its initialization for default values. */
49 cache = (cache_ptr)OBJC_CALLOC_UNCOLLECTABLE(sizeof (struct cache));
52 /* Allocate the array of buckets for the cache.
53 calloc initializes all of the pointers to NULL. */
55 (node_ptr *)OBJC_CALLOC_UNCOLLECTABLE(size * sizeof (node_ptr));
57 assert (cache->node_table);
61 /* This should work for all processor architectures? */
62 cache->mask = (size - 1);
64 cache->hashType = hashType;
71 hash_add (cache_ptr *cachep, const void *key, void *value)
73 size_t indx = objc_call_hash(*cachep, key);
74 //hh: size_t indx = (*(*cachep)->hash_func)(*cachep, key);
77 node = (node_ptr)OBJC_CALLOC_UNCOLLECTABLE(sizeof (struct cache_node));
80 /* Initialize the new node. */
83 node->next = (*cachep)->node_table[indx];
86 Check the list for another key. */
88 { node_ptr node1 = (*cachep)->node_table[indx];
92 assert (node1->key != key);
98 /* Install the node as the first element on the list. */
99 (*cachep)->node_table[indx] = node;
101 /* Bump the number of entries in the cache. */
104 /* Check the hash table's fullness. We're going
105 to expand if it is above the fullness level. */
106 if (FULLNESS (*cachep)) {
108 /* The hash table has reached its fullness level. Time to
111 I'm using a slow method here but is built on other
112 primitive functions thereby increasing its
114 node_ptr node1 = NULL;
115 cache_ptr new = hash_new (EXPANSION (*cachep), (*cachep)->hashType);
117 DEBUG_PRINTF ("Expanding cache 0x%08X from %d to %d\n",
118 (size_t)*cachep, (*cachep)->size, new->size);
120 /* Copy the nodes from the first hash table to the new one. */
121 while ((node1 = hash_next (*cachep, node1)))
122 hash_add (&new, node1->key, node1->value);
124 /* Trash the old cache. */
125 hash_delete (*cachep);
127 /* Return a pointer to the new hash table. */