OSDN Git Service

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