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