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