1.1 --- a/src/hash_map.c Thu May 19 14:30:20 2022 +0200
1.2 +++ b/src/hash_map.c Sat May 21 11:22:47 2022 +0200
1.3 @@ -175,6 +175,25 @@
1.4 return 0;
1.5 }
1.6
1.7 +static void cx_hash_map_unlink(
1.8 + struct cx_hash_map_s *hash_map,
1.9 + size_t slot,
1.10 + struct cx_hash_map_element_s *prev,
1.11 + struct cx_hash_map_element_s *elm
1.12 +) {
1.13 + // unlink
1.14 + if (prev == NULL) {
1.15 + hash_map->buckets[slot] = elm->next;
1.16 + } else {
1.17 + prev->next = elm->next;
1.18 + }
1.19 + // free element
1.20 + cxFree(hash_map->base.allocator, elm->key.data);
1.21 + cxFree(hash_map->base.allocator, elm);
1.22 + // decrease size
1.23 + hash_map->base.size--;
1.24 +}
1.25 +
1.26 /**
1.27 * Helper function to avoid code duplication.
1.28 *
1.29 @@ -200,17 +219,7 @@
1.30 if (memcmp(elm->key.data, key.data, key.len) == 0) {
1.31 void *data = elm->data;
1.32 if (remove) {
1.33 - // unlink
1.34 - if (prev) {
1.35 - prev->next = elm->next;
1.36 - } else {
1.37 - hash_map->buckets[slot] = elm->next;
1.38 - }
1.39 - // free element
1.40 - cxFree(map->allocator, elm->key.data);
1.41 - cxFree(map->allocator, elm);
1.42 - // decrease size
1.43 - map->size--;
1.44 + cx_hash_map_unlink(hash_map, slot, prev, elm);
1.45 }
1.46 return data;
1.47 }
1.48 @@ -237,21 +246,120 @@
1.49 return cx_hash_map_get_remove(map, key, true);
1.50 }
1.51
1.52 -static CxIterator cx_hash_map_iterator(CxMap const *map) {
1.53 +static void *cx_hash_map_iter_current_entry(CxIterator const *iter) {
1.54 + // struct has to have a compatible signature
1.55 + struct cx_map_entry_s *entry = (struct cx_map_entry_s *) &(iter->kv_data);
1.56 + return entry;
1.57 +}
1.58 +
1.59 +static void *cx_hash_map_iter_current_key(CxIterator const *iter) {
1.60 + struct cx_hash_map_element_s *elm = iter->elem_handle;
1.61 + return &elm->key;
1.62 +}
1.63 +
1.64 +static void *cx_hash_map_iter_current_value(CxIterator const *iter) {
1.65 + struct cx_hash_map_element_s *elm = iter->elem_handle;
1.66 + // TODO: return a pointer to data if this map is storing copies
1.67 + return elm->data;
1.68 +}
1.69 +
1.70 +static bool cx_hash_map_iter_valid(CxIterator const *iter) {
1.71 + return iter->elem_handle != NULL;
1.72 +}
1.73 +
1.74 +static void cx_hash_map_iter_next(CxIterator *iter) {
1.75 + struct cx_hash_map_s *map = iter->src_handle;
1.76 + struct cx_hash_map_element_s *elm = iter->elem_handle;
1.77 +
1.78 + // remove current element, if asked
1.79 + if (iter->remove) {
1.80 + // clear the flag
1.81 + iter->remove = false;
1.82 +
1.83 + // determine the next element
1.84 + struct cx_hash_map_element_s *next = elm->next;
1.85 +
1.86 + // search the previous element
1.87 + struct cx_hash_map_element_s *prev = NULL;
1.88 + if (map->buckets[iter->slot] != elm) {
1.89 + prev = map->buckets[iter->slot];
1.90 + while (prev->next != elm) {
1.91 + prev = prev->next;
1.92 + }
1.93 + }
1.94 +
1.95 + // unlink
1.96 + cx_hash_map_unlink(map, iter->slot, prev, elm);
1.97 +
1.98 + // advance
1.99 + elm = next;
1.100 + } else {
1.101 + // just advance
1.102 + elm = elm->next;
1.103 + }
1.104 +
1.105 + // do we leave the bucket?
1.106 + if (elm == NULL) {
1.107 + // search the next bucket
1.108 + for (; elm == NULL && iter->slot < map->bucket_count; iter->slot++) {
1.109 + elm = map->buckets[iter->slot];
1.110 + }
1.111 + }
1.112 +
1.113 + // advance the index in any case
1.114 + iter->index++;
1.115 +
1.116 + // fill the struct with the current element
1.117 + iter->elem_handle = elm;
1.118 + if (elm == NULL) {
1.119 + iter->kv_data.key = NULL;
1.120 + iter->kv_data.value = NULL;
1.121 + } else {
1.122 + iter->kv_data.key = &elm->key;
1.123 + // TODO: pointer to data if this map is storing copies
1.124 + iter->kv_data.value = elm->data;
1.125 + }
1.126 +}
1.127 +
1.128 +static CxIterator cx_hash_map_iterator(CxMap *map) {
1.129 CxIterator iter;
1.130 - // TODO: initialize iter
1.131 +
1.132 + iter.src_handle = map;
1.133 + iter.valid = cx_hash_map_iter_valid;
1.134 + iter.next = cx_hash_map_iter_next;
1.135 + iter.current = cx_hash_map_iter_current_entry;
1.136 +
1.137 + iter.slot = 0;
1.138 + iter.index = 0;
1.139 + iter.remove = false;
1.140 +
1.141 + if (map->size > 0) {
1.142 + struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
1.143 + struct cx_hash_map_element_s *elem = NULL;
1.144 + for (; elem == NULL; iter.slot++) {
1.145 + elem = hash_map->buckets[iter.slot];
1.146 + }
1.147 + iter.elem_handle = elem;
1.148 + iter.kv_data.key = NULL;
1.149 + iter.kv_data.value = NULL;
1.150 + } else {
1.151 + iter.elem_handle = NULL;
1.152 + iter.kv_data.key = NULL;
1.153 + iter.kv_data.value = NULL;
1.154 + }
1.155 +
1.156 return iter;
1.157 }
1.158
1.159 -static CxIterator cx_hash_map_iterator_keys(CxMap const *map) {
1.160 - CxIterator iter;
1.161 - // TODO: initialize iter
1.162 +static CxIterator cx_hash_map_iterator_keys(CxMap *map) {
1.163 + CxIterator iter = cx_hash_map_iterator(map);
1.164 + iter.current = cx_hash_map_iter_current_key;
1.165 return iter;
1.166 }
1.167
1.168 -static CxIterator cx_hash_map_iterator_values(CxMap const *map) {
1.169 - CxIterator iter;
1.170 - // TODO: initialize iter
1.171 +static CxIterator cx_hash_map_iterator_values(CxMap *map) {
1.172 + CxIterator iter = cx_hash_map_iterator(map);
1.173 + iter.current = cx_hash_map_iter_current_value;
1.174 return iter;
1.175 }
1.176
