OSDN Git Service

* All .h files pushed down into the objc/ subdirectory.
[pf3gnuchains/gcc-fork.git] / libobjc / objc / hash.h
1 /* Hash tables for Objective C method dispatch.
2    Copyright (C) 1993, 1995, 1996 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, 59 Temple Place - Suite 330,
19 Boston, 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
28 #ifndef __hash_INCLUDE_GNU
29 #define __hash_INCLUDE_GNU
30
31 #include <stddef.h>
32 #include <objc/objc.h>
33
34 /*
35  * This data structure is used to hold items
36  *  stored in a hash table.  Each node holds 
37  *  a key/value pair.
38  *
39  * Items in the cache are really of type void *.
40  */
41 typedef struct cache_node
42 {
43   struct cache_node *next;      /* Pointer to next entry on the list.
44                                    NULL indicates end of list. */
45   const void *key;              /* Key used to locate the value.  Used
46                                    to locate value when more than one
47                                    key computes the same hash
48                                    value. */
49   void *value;                  /* Value stored for the key. */
50 } *node_ptr;
51
52
53 /*
54  * This data type is the function that computes a hash code given a key.
55  * Therefore, the key can be a pointer to anything and the function specific
56  * to the key type. 
57  *
58  * Unfortunately there is a mutual data structure reference problem with this
59  * typedef.  Therefore, to remove compiler warnings the functions passed to
60  * hash_new will have to be casted to this type. 
61  */
62 typedef unsigned int (*hash_func_type)(void *, const void *);
63
64 /*
65  * This data type is the function that compares two hash keys and returns an
66  * integer greater than, equal to, or less than 0, according as the first
67  * parameter is lexicographically greater than, equal to, or less than the
68  * second. 
69  */
70
71 typedef int (*compare_func_type)(const void *, const void *);
72
73
74 /*
75  * This data structure is the cache.
76  *
77  * It must be passed to all of the hashing routines
78  *   (except for new).
79  */
80 typedef struct cache
81 {
82   /* Variables used to implement the hash itself.  */
83   node_ptr *node_table; /* Pointer to an array of hash nodes.  */
84   /* Variables used to track the size of the hash table so to determine
85     when to resize it.  */
86   unsigned int size; /* Number of buckets allocated for the hash table
87                         (number of array entries allocated for
88                         "node_table").  Must be a power of two.  */
89   unsigned int used; /* Current number of entries in the hash table.  */
90   unsigned int mask; /* Precomputed mask.  */
91
92   /* Variables used to implement indexing through the hash table.  */
93
94   unsigned int last_bucket; /* Tracks which entry in the array where
95                                the last value was returned.  */
96   /* Function used to compute a hash code given a key. 
97      This function is specified when the hash table is created.  */
98   hash_func_type    hash_func;
99   /* Function used to compare two hash keys to see if they are equal.  */
100   compare_func_type compare_func;
101 } *cache_ptr;
102
103
104 /* Two important hash tables.  */
105 extern cache_ptr module_hash_table, class_hash_table;
106
107 /* Allocate and initialize a hash table.  */ 
108
109 cache_ptr hash_new (unsigned int size,
110                     hash_func_type hash_func,
111                     compare_func_type compare_func);
112                        
113 /* Deallocate all of the hash nodes and the cache itself.  */
114
115 void hash_delete (cache_ptr cache);
116
117 /* Add the key/value pair to the hash table.  If the
118    hash table reaches a level of fullness then it will be resized. 
119                                                    
120    assert if the key is already in the hash.  */
121
122 void hash_add (cache_ptr *cachep, const void *key, void *value);
123      
124 /* Remove the key/value pair from the hash table.  
125    assert if the key isn't in the table.  */
126
127 void hash_remove (cache_ptr cache, const void *key);
128
129 /* Used to index through the hash table.  Start with NULL
130    to get the first entry.
131                                                   
132    Successive calls pass the value returned previously.
133    ** Don't modify the hash during this operation *** 
134                                                   
135    Cache nodes are returned such that key or value can
136    be extracted.  */
137
138 node_ptr hash_next (cache_ptr cache, node_ptr node);
139
140 /* Used to return a value from a hash table using a given key.  */
141
142 void *hash_value_for_key (cache_ptr cache, const void *key);
143
144 /* Used to determine if the given key exists in the hash table */
145
146 BOOL hash_is_key_in_hash (cache_ptr cache, const void *key);
147
148 /************************************************
149
150         Useful hashing functions.  
151         
152         Declared inline for your pleasure.
153         
154 ************************************************/
155
156 /* Calculate a hash code by performing some 
157    manipulation of the key pointer.  (Use the lowest bits
158    except for those likely to be 0 due to alignment.)  */
159
160 static inline unsigned int
161 hash_ptr (cache_ptr cache, const void *key)
162 {
163   return ((size_t)key / sizeof (void *)) & cache->mask;
164 }
165
166
167 /* Calculate a hash code by iterating over a NULL 
168    terminate string.  */
169 static inline unsigned int 
170 hash_string (cache_ptr cache, const void *key)
171 {
172   unsigned int ret = 0;
173   unsigned int ctr = 0;
174         
175         
176   while (*(char*)key) {
177     ret ^= *(char*)key++ << ctr;
178     ctr = (ctr + 1) % sizeof (void *);
179   }
180
181   return ret & cache->mask;
182 }
183
184
185 /* Compare two pointers for equality.  */
186 static inline int 
187 compare_ptrs (const void *k1, const void *k2)
188 {
189   return !(k1 - k2);
190 }
191
192
193 /* Compare two strings.  */
194 static inline int 
195 compare_strings (const void *k1, const void *k2)
196 {
197   if (k1 == k2)
198     return 1;
199   else if (k1 == 0 || k2 == 0)
200     return 0;
201   else
202     return !strcmp (k1, k2);
203 }
204
205
206 #endif /* not __hash_INCLUDE_GNU */