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