001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019 #include <sos/kmalloc.h>
020 #include <sos/klibc.h>
021 #include <sos/list.h>
022 #include <sos/assert.h>
023
024 #include "hash.h"
025
026 #define SOS_HASH_NAME_MAXLEN 32
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041 struct bucket
042 {
043 sos_count_t nb_elems;
044 struct sos_hash_linkage * list;
045 };
046
047
048
049
050
051 struct sos_hash_table
052 {
053 char name[SOS_HASH_NAME_MAXLEN];
054
055
056 sos_hash_func_t * key_hasher;
057
058
059 sos_hash_key_eq_func_t * key_iseq;
060
061
062 sos_uoffset_t offset_h_key;
063
064
065 sos_uoffset_t offset_h_linkage;
066
067
068 sos_count_t nbuckets;
069
070 struct bucket bucket[0];
071 };
072
073
074
075
076 #define h_linkage_of_elt(h,elt) \
077 ( (struct sos_hash_linkage*) \
078 ( ((unsigned long)(elt)) + (h)->offset_h_linkage) )
079
080
081
082
083 #define h_keyptr_of_elt(h,elt) \
084 ( (void*) \
085 ( ((unsigned long)(elt)) + (h)->offset_h_key) )
086
087
088
089
090 #define elt_for_h_linkage(h,linkage) \
091 ( (void*) \
092 ( ((unsigned long)(linkage)) - (h)->offset_h_linkage) )
093
094
095 struct sos_hash_table *
096 _sos_hash_create_FULL(const char *name,
097 sos_hash_func_t *key_hasher,
098 sos_hash_key_eq_func_t *key_iseq,
099 sos_count_t nbuckets,
100 sos_uoffset_t offset_h_key,
101 sos_uoffset_t offset_h_linkage)
102 {
103 struct sos_hash_table * h;
104 h = (struct sos_hash_table*)
105 sos_kmalloc(sizeof(struct sos_hash_table)
106 + nbuckets*sizeof(struct bucket), 0);
107
108 memset(h, 0x0,
109 sizeof(struct sos_hash_table) + nbuckets*sizeof(struct bucket));
110 h->key_hasher = key_hasher;
111 h->key_iseq = key_iseq;
112 h->offset_h_linkage = offset_h_linkage;
113 h->offset_h_key = offset_h_key;
114 h->nbuckets = nbuckets;
115 strzcpy(h->name, name, SOS_HASH_NAME_MAXLEN);
116
117 return h;
118 }
119
120
121 sos_ret_t sos_hash_dispose(struct sos_hash_table *h)
122 {
123 unsigned int i;
124 for (i = 0 ; i < h->nbuckets ; i++)
125 {
126 struct sos_hash_linkage * elt;
127
128 list_collapse_named(h->bucket[i].list, elt, h_prev, h_next)
129 {
130 elt->h_prev = elt->h_next = NULL;
131 }
132 }
133
134 return sos_kfree((sos_vaddr_t)h);
135 }
136
137
138 sos_ret_t sos_hash_insert(struct sos_hash_table *h,
139 void *elt_with_key)
140 {
141 struct sos_hash_linkage * h_elt;
142 sos_uoffset_t bucket;
143
144 h_elt = h_linkage_of_elt(h, elt_with_key);
145 if (h_elt->h_prev || h_elt->h_next)
146 return -SOS_EBUSY;
147
148 if (h->key_hasher)
149 bucket = h->key_hasher(h_keyptr_of_elt(h, elt_with_key)) % h->nbuckets;
150 else
151 {
152
153 unsigned long * keyval = h_keyptr_of_elt(h, elt_with_key);
154 bucket = *keyval % h->nbuckets;
155 }
156
157 list_add_head_named(h->bucket[bucket].list, h_elt, h_prev, h_next);
158 h->bucket[bucket].nb_elems ++;
159
160 return SOS_OK;
161 }
162
163
164 void * sos_hash_lookup(struct sos_hash_table *h,
165 const void * ptr_key)
166 {
167 struct sos_hash_linkage * h_elt;
168 sos_uoffset_t bucket;
169 int nb;
170
171 if (h->key_hasher)
172 bucket = h->key_hasher(ptr_key) % h->nbuckets;
173 else
174 {
175
176 const unsigned long * keyval = ptr_key;
177 bucket = *keyval % h->nbuckets;
178 }
179
180 list_foreach_forward_named(h->bucket[bucket].list, h_elt, nb, h_prev, h_next)
181 {
182 void * elt = elt_for_h_linkage(h, h_elt);
183 void * elt_ptr_key = h_keyptr_of_elt(h, elt);
184
185 if (ptr_key == elt_ptr_key)
186 return elt;
187
188 if (! h->key_iseq)
189 continue;
190
191 if (h->key_iseq(ptr_key, elt_ptr_key))
192 return elt;
193 }
194
195 return NULL;
196 }
197
198
199 sos_ret_t sos_hash_remove(struct sos_hash_table *h,
200 void * elt)
201 {
202 struct sos_hash_linkage * h_elt;
203 sos_uoffset_t bucket;
204
205 h_elt = h_linkage_of_elt(h, elt);
206 SOS_ASSERT_FATAL(h_elt->h_prev && h_elt->h_next);
207
208 if (h->key_hasher)
209 bucket = h->key_hasher(h_keyptr_of_elt(h, elt)) % h->nbuckets;
210 else
211 {
212 unsigned long * keyval = h_keyptr_of_elt(h, elt);
213 bucket = *keyval % h->nbuckets;
214 }
215
216 list_delete_named(h->bucket[bucket].list, h_elt, h_prev, h_next);
217 h->bucket[bucket].nb_elems --;
218
219 return SOS_OK;
220 }
221
222
223 unsigned long sos_hash_ui64(const void * ptr_key)
224 {
225 const sos_ui64_t * keyval = ptr_key;
226 return ((*keyval) * 302954987) & 0xffffffff;
227 }
228
229
230 sos_bool_t sos_hash_key_eq_ui64(const void * ptr_key1,
231 const void * ptr_key2)
232 {
233 const sos_ui64_t * keyval1 = ptr_key1;
234 const sos_ui64_t * keyval2 = ptr_key2;
235
236 return (*keyval1 == *keyval2);
237 }