comparison: src/hash_map.c
src/hash_map.c
- changeset 630
- ac5e7f789048
- parent 575
- b05935945637
- child 658
- 56c62780582e
equal
deleted
inserted
replaced
| 629:6c81ee4f11ad | 630:ac5e7f789048 |
|---|---|
| 199 CxHashKey key | 199 CxHashKey key |
| 200 ) { | 200 ) { |
| 201 return cx_hash_map_get_remove(map, key, true); | 201 return cx_hash_map_get_remove(map, key, true); |
| 202 } | 202 } |
| 203 | 203 |
| 204 static void *cx_hash_map_iter_current_entry(CxIterator const *iter) { | 204 static void *cx_hash_map_iter_current_entry(void const *it) { |
| 205 struct cx_iterator_s const *iter = it; | |
| 205 // struct has to have a compatible signature | 206 // struct has to have a compatible signature |
| 206 return (struct cx_map_entry_s *) &(iter->kv_data); | 207 return (struct cx_map_entry_s *) &(iter->kv_data); |
| 207 } | 208 } |
| 208 | 209 |
| 209 static void *cx_hash_map_iter_current_key(CxIterator const *iter) { | 210 static void *cx_hash_map_iter_current_key(void const *it) { |
| 211 struct cx_iterator_s const *iter = it; | |
| 210 struct cx_hash_map_element_s *elm = iter->elem_handle; | 212 struct cx_hash_map_element_s *elm = iter->elem_handle; |
| 211 return &elm->key; | 213 return &elm->key; |
| 212 } | 214 } |
| 213 | 215 |
| 214 static void *cx_hash_map_iter_current_value(CxIterator const *iter) { | 216 static void *cx_hash_map_iter_current_value(void const *it) { |
| 217 struct cx_iterator_s const *iter = it; | |
| 215 struct cx_hash_map_element_s *elm = iter->elem_handle; | 218 struct cx_hash_map_element_s *elm = iter->elem_handle; |
| 216 // TODO: return a pointer to data if this map is storing copies | 219 // TODO: return a pointer to data if this map is storing copies |
| 217 return elm->data; | 220 return elm->data; |
| 218 } | 221 } |
| 219 | 222 |
| 220 static bool cx_hash_map_iter_valid(CxIterator const *iter) { | 223 static bool cx_hash_map_iter_valid(void const *it) { |
| 224 struct cx_iterator_s const *iter = it; | |
| 221 return iter->elem_handle != NULL; | 225 return iter->elem_handle != NULL; |
| 222 } | 226 } |
| 223 | 227 |
| 224 static void cx_hash_map_iter_next(CxIterator *iter) { | 228 static void cx_hash_map_iter_next(void *it) { |
| 225 struct cx_hash_map_s *map = iter->src_handle; | 229 struct cx_iterator_s *iter = it; |
| 226 struct cx_hash_map_element_s *elm = iter->elem_handle; | 230 struct cx_hash_map_element_s *elm = iter->elem_handle; |
| 227 | 231 |
| 228 // remove current element, if asked | 232 // remove current element, if asked |
| 229 if (iter->remove) { | 233 if (iter->base.remove) { |
| 234 // obtain mutable pointer to the map | |
| 235 struct cx_mut_iterator_s *miter = it; | |
| 236 struct cx_hash_map_s *map = miter->src_handle; | |
| 237 | |
| 230 // clear the flag | 238 // clear the flag |
| 231 iter->remove = false; | 239 iter->base.remove = false; |
| 232 | 240 |
| 233 // determine the next element | 241 // determine the next element |
| 234 struct cx_hash_map_element_s *next = elm->next; | 242 struct cx_hash_map_element_s *next = elm->next; |
| 235 | 243 |
| 236 // search the previous element | 244 // search the previous element |
| 252 elm = elm->next; | 260 elm = elm->next; |
| 253 iter->index++; | 261 iter->index++; |
| 254 } | 262 } |
| 255 | 263 |
| 256 // search the next bucket, if required | 264 // search the next bucket, if required |
| 265 struct cx_hash_map_s const *map = iter->src_handle; | |
| 257 while (elm == NULL && ++iter->slot < map->bucket_count) { | 266 while (elm == NULL && ++iter->slot < map->bucket_count) { |
| 258 elm = map->buckets[iter->slot]; | 267 elm = map->buckets[iter->slot]; |
| 259 } | 268 } |
| 260 | 269 |
| 261 // fill the struct with the next element | 270 // fill the struct with the next element |
| 268 // TODO: pointer to data if this map is storing copies | 277 // TODO: pointer to data if this map is storing copies |
| 269 iter->kv_data.value = elm->data; | 278 iter->kv_data.value = elm->data; |
| 270 } | 279 } |
| 271 } | 280 } |
| 272 | 281 |
| 273 static CxIterator cx_hash_map_iterator(CxMap *map) { | 282 static bool cx_hash_map_iter_flag_rm(void *it) { |
| 283 struct cx_iterator_base_s *iter = it; | |
| 284 if (iter->mutating) { | |
| 285 iter->remove = true; | |
| 286 return true; | |
| 287 } else { | |
| 288 return false; | |
| 289 } | |
| 290 } | |
| 291 | |
| 292 static CxIterator cx_hash_map_iterator(CxMap const *map) { | |
| 274 CxIterator iter; | 293 CxIterator iter; |
| 275 | 294 |
| 276 iter.src_handle = map; | 295 iter.src_handle = map; |
| 277 iter.valid = cx_hash_map_iter_valid; | 296 iter.base.valid = cx_hash_map_iter_valid; |
| 278 iter.next = cx_hash_map_iter_next; | 297 iter.base.next = cx_hash_map_iter_next; |
| 279 iter.current = cx_hash_map_iter_current_entry; | 298 iter.base.current = cx_hash_map_iter_current_entry; |
| 299 iter.base.flag_removal = cx_hash_map_iter_flag_rm; | |
| 300 iter.base.remove = false; | |
| 301 iter.base.mutating = false; | |
| 280 | 302 |
| 281 iter.slot = 0; | 303 iter.slot = 0; |
| 282 iter.index = 0; | 304 iter.index = 0; |
| 283 iter.remove = false; | |
| 284 | 305 |
| 285 if (map->size > 0) { | 306 if (map->size > 0) { |
| 286 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; | 307 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; |
| 287 struct cx_hash_map_element_s *elm = hash_map->buckets[0]; | 308 struct cx_hash_map_element_s *elm = hash_map->buckets[0]; |
| 288 for (; elm == NULL; iter.slot++) { | 309 for (; elm == NULL; iter.slot++) { |
| 299 } | 320 } |
| 300 | 321 |
| 301 return iter; | 322 return iter; |
| 302 } | 323 } |
| 303 | 324 |
| 304 static CxIterator cx_hash_map_iterator_keys(CxMap *map) { | 325 static CxIterator cx_hash_map_iterator_keys(CxMap const *map) { |
| 305 CxIterator iter = cx_hash_map_iterator(map); | 326 CxIterator iter = cx_hash_map_iterator(map); |
| 306 iter.current = cx_hash_map_iter_current_key; | 327 iter.base.current = cx_hash_map_iter_current_key; |
| 307 return iter; | 328 return iter; |
| 308 } | 329 } |
| 309 | 330 |
| 310 static CxIterator cx_hash_map_iterator_values(CxMap *map) { | 331 static CxIterator cx_hash_map_iterator_values(CxMap const *map) { |
| 311 CxIterator iter = cx_hash_map_iterator(map); | 332 CxIterator iter = cx_hash_map_iterator(map); |
| 312 iter.current = cx_hash_map_iter_current_value; | 333 iter.base.current = cx_hash_map_iter_current_value; |
| 334 return iter; | |
| 335 } | |
| 336 | |
| 337 static CxMutIterator cx_hash_map_mut_iterator(CxMap *map) { | |
| 338 CxIterator it = cx_hash_map_iterator(map); | |
| 339 it.base.mutating = true; | |
| 340 | |
| 341 // we know the iterators share the same memory layout | |
| 342 CxMutIterator iter; | |
| 343 memcpy(&iter, &it, sizeof(CxMutIterator)); | |
| 344 return iter; | |
| 345 } | |
| 346 | |
| 347 static CxMutIterator cx_hash_map_mut_iterator_keys(CxMap *map) { | |
| 348 CxMutIterator iter = cx_hash_map_mut_iterator(map); | |
| 349 iter.base.current = cx_hash_map_iter_current_key; | |
| 350 return iter; | |
| 351 } | |
| 352 | |
| 353 static CxMutIterator cx_hash_map_mut_iterator_values(CxMap *map) { | |
| 354 CxMutIterator iter = cx_hash_map_mut_iterator(map); | |
| 355 iter.base.current = cx_hash_map_iter_current_value; | |
| 313 return iter; | 356 return iter; |
| 314 } | 357 } |
| 315 | 358 |
| 316 static cx_map_class cx_hash_map_class = { | 359 static cx_map_class cx_hash_map_class = { |
| 317 cx_hash_map_destructor, | 360 cx_hash_map_destructor, |
| 320 cx_hash_map_get, | 363 cx_hash_map_get, |
| 321 cx_hash_map_remove, | 364 cx_hash_map_remove, |
| 322 cx_hash_map_iterator, | 365 cx_hash_map_iterator, |
| 323 cx_hash_map_iterator_keys, | 366 cx_hash_map_iterator_keys, |
| 324 cx_hash_map_iterator_values, | 367 cx_hash_map_iterator_values, |
| 368 cx_hash_map_mut_iterator, | |
| 369 cx_hash_map_mut_iterator_keys, | |
| 370 cx_hash_map_mut_iterator_values, | |
| 325 }; | 371 }; |
| 326 | 372 |
| 327 CxMap *cxHashMapCreate( | 373 CxMap *cxHashMapCreate( |
| 328 CxAllocator *allocator, | 374 CxAllocator *allocator, |
| 329 size_t buckets | 375 size_t buckets |
