comparison: src/hash_map.c
src/hash_map.c
- changeset 551
- 2946e13c89a4
- parent 550
- 89b2a83728b1
- child 554
- fd3d843b839d
equal
deleted
inserted
replaced
| 550:89b2a83728b1 | 551:2946e13c89a4 |
|---|---|
| 173 } | 173 } |
| 174 | 174 |
| 175 return 0; | 175 return 0; |
| 176 } | 176 } |
| 177 | 177 |
| 178 static void cx_hash_map_unlink( | |
| 179 struct cx_hash_map_s *hash_map, | |
| 180 size_t slot, | |
| 181 struct cx_hash_map_element_s *prev, | |
| 182 struct cx_hash_map_element_s *elm | |
| 183 ) { | |
| 184 // unlink | |
| 185 if (prev == NULL) { | |
| 186 hash_map->buckets[slot] = elm->next; | |
| 187 } else { | |
| 188 prev->next = elm->next; | |
| 189 } | |
| 190 // free element | |
| 191 cxFree(hash_map->base.allocator, elm->key.data); | |
| 192 cxFree(hash_map->base.allocator, elm); | |
| 193 // decrease size | |
| 194 hash_map->base.size--; | |
| 195 } | |
| 196 | |
| 178 /** | 197 /** |
| 179 * Helper function to avoid code duplication. | 198 * Helper function to avoid code duplication. |
| 180 * | 199 * |
| 181 * @param map the map | 200 * @param map the map |
| 182 * @param key the key to look up | 201 * @param key the key to look up |
| 198 while (elm && elm->key.hash <= hash) { | 217 while (elm && elm->key.hash <= hash) { |
| 199 if (elm->key.hash == hash && elm->key.len == key.len) { | 218 if (elm->key.hash == hash && elm->key.len == key.len) { |
| 200 if (memcmp(elm->key.data, key.data, key.len) == 0) { | 219 if (memcmp(elm->key.data, key.data, key.len) == 0) { |
| 201 void *data = elm->data; | 220 void *data = elm->data; |
| 202 if (remove) { | 221 if (remove) { |
| 203 // unlink | 222 cx_hash_map_unlink(hash_map, slot, prev, elm); |
| 204 if (prev) { | |
| 205 prev->next = elm->next; | |
| 206 } else { | |
| 207 hash_map->buckets[slot] = elm->next; | |
| 208 } | |
| 209 // free element | |
| 210 cxFree(map->allocator, elm->key.data); | |
| 211 cxFree(map->allocator, elm); | |
| 212 // decrease size | |
| 213 map->size--; | |
| 214 } | 223 } |
| 215 return data; | 224 return data; |
| 216 } | 225 } |
| 217 } | 226 } |
| 218 prev = elm; | 227 prev = elm; |
| 235 CxDataPtr key | 244 CxDataPtr key |
| 236 ) { | 245 ) { |
| 237 return cx_hash_map_get_remove(map, key, true); | 246 return cx_hash_map_get_remove(map, key, true); |
| 238 } | 247 } |
| 239 | 248 |
| 240 static CxIterator cx_hash_map_iterator(CxMap const *map) { | 249 static void *cx_hash_map_iter_current_entry(CxIterator const *iter) { |
| 250 // struct has to have a compatible signature | |
| 251 struct cx_map_entry_s *entry = (struct cx_map_entry_s *) &(iter->kv_data); | |
| 252 return entry; | |
| 253 } | |
| 254 | |
| 255 static void *cx_hash_map_iter_current_key(CxIterator const *iter) { | |
| 256 struct cx_hash_map_element_s *elm = iter->elem_handle; | |
| 257 return &elm->key; | |
| 258 } | |
| 259 | |
| 260 static void *cx_hash_map_iter_current_value(CxIterator const *iter) { | |
| 261 struct cx_hash_map_element_s *elm = iter->elem_handle; | |
| 262 // TODO: return a pointer to data if this map is storing copies | |
| 263 return elm->data; | |
| 264 } | |
| 265 | |
| 266 static bool cx_hash_map_iter_valid(CxIterator const *iter) { | |
| 267 return iter->elem_handle != NULL; | |
| 268 } | |
| 269 | |
| 270 static void cx_hash_map_iter_next(CxIterator *iter) { | |
| 271 struct cx_hash_map_s *map = iter->src_handle; | |
| 272 struct cx_hash_map_element_s *elm = iter->elem_handle; | |
| 273 | |
| 274 // remove current element, if asked | |
| 275 if (iter->remove) { | |
| 276 // clear the flag | |
| 277 iter->remove = false; | |
| 278 | |
| 279 // determine the next element | |
| 280 struct cx_hash_map_element_s *next = elm->next; | |
| 281 | |
| 282 // search the previous element | |
| 283 struct cx_hash_map_element_s *prev = NULL; | |
| 284 if (map->buckets[iter->slot] != elm) { | |
| 285 prev = map->buckets[iter->slot]; | |
| 286 while (prev->next != elm) { | |
| 287 prev = prev->next; | |
| 288 } | |
| 289 } | |
| 290 | |
| 291 // unlink | |
| 292 cx_hash_map_unlink(map, iter->slot, prev, elm); | |
| 293 | |
| 294 // advance | |
| 295 elm = next; | |
| 296 } else { | |
| 297 // just advance | |
| 298 elm = elm->next; | |
| 299 } | |
| 300 | |
| 301 // do we leave the bucket? | |
| 302 if (elm == NULL) { | |
| 303 // search the next bucket | |
| 304 for (; elm == NULL && iter->slot < map->bucket_count; iter->slot++) { | |
| 305 elm = map->buckets[iter->slot]; | |
| 306 } | |
| 307 } | |
| 308 | |
| 309 // advance the index in any case | |
| 310 iter->index++; | |
| 311 | |
| 312 // fill the struct with the current element | |
| 313 iter->elem_handle = elm; | |
| 314 if (elm == NULL) { | |
| 315 iter->kv_data.key = NULL; | |
| 316 iter->kv_data.value = NULL; | |
| 317 } else { | |
| 318 iter->kv_data.key = &elm->key; | |
| 319 // TODO: pointer to data if this map is storing copies | |
| 320 iter->kv_data.value = elm->data; | |
| 321 } | |
| 322 } | |
| 323 | |
| 324 static CxIterator cx_hash_map_iterator(CxMap *map) { | |
| 241 CxIterator iter; | 325 CxIterator iter; |
| 242 // TODO: initialize iter | 326 |
| 327 iter.src_handle = map; | |
| 328 iter.valid = cx_hash_map_iter_valid; | |
| 329 iter.next = cx_hash_map_iter_next; | |
| 330 iter.current = cx_hash_map_iter_current_entry; | |
| 331 | |
| 332 iter.slot = 0; | |
| 333 iter.index = 0; | |
| 334 iter.remove = false; | |
| 335 | |
| 336 if (map->size > 0) { | |
| 337 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; | |
| 338 struct cx_hash_map_element_s *elem = NULL; | |
| 339 for (; elem == NULL; iter.slot++) { | |
| 340 elem = hash_map->buckets[iter.slot]; | |
| 341 } | |
| 342 iter.elem_handle = elem; | |
| 343 iter.kv_data.key = NULL; | |
| 344 iter.kv_data.value = NULL; | |
| 345 } else { | |
| 346 iter.elem_handle = NULL; | |
| 347 iter.kv_data.key = NULL; | |
| 348 iter.kv_data.value = NULL; | |
| 349 } | |
| 350 | |
| 243 return iter; | 351 return iter; |
| 244 } | 352 } |
| 245 | 353 |
| 246 static CxIterator cx_hash_map_iterator_keys(CxMap const *map) { | 354 static CxIterator cx_hash_map_iterator_keys(CxMap *map) { |
| 247 CxIterator iter; | 355 CxIterator iter = cx_hash_map_iterator(map); |
| 248 // TODO: initialize iter | 356 iter.current = cx_hash_map_iter_current_key; |
| 249 return iter; | 357 return iter; |
| 250 } | 358 } |
| 251 | 359 |
| 252 static CxIterator cx_hash_map_iterator_values(CxMap const *map) { | 360 static CxIterator cx_hash_map_iterator_values(CxMap *map) { |
| 253 CxIterator iter; | 361 CxIterator iter = cx_hash_map_iterator(map); |
| 254 // TODO: initialize iter | 362 iter.current = cx_hash_map_iter_current_value; |
| 255 return iter; | 363 return iter; |
| 256 } | 364 } |
| 257 | 365 |
| 258 static cx_map_class cx_hash_map_class = { | 366 static cx_map_class cx_hash_map_class = { |
| 259 cx_hash_map_destructor, | 367 cx_hash_map_destructor, |
