OSDN Git Service

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