comparison: src/hash_map.c
src/hash_map.c
- changeset 550
- 89b2a83728b1
- parent 549
- d7f0b5a9a985
- child 551
- 2946e13c89a4
equal
deleted
inserted
replaced
| 549:d7f0b5a9a985 | 550:89b2a83728b1 |
|---|---|
| 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| 26 * POSSIBILITY OF SUCH DAMAGE. | 26 * POSSIBILITY OF SUCH DAMAGE. |
| 27 */ | 27 */ |
| 28 | 28 |
| 29 #include <errno.h> | |
| 29 #include <string.h> | 30 #include <string.h> |
| 30 #include "cx/hash_map.h" | 31 #include "cx/hash_map.h" |
| 32 #include "cx/utils.h" | |
| 31 | 33 |
| 32 /** | 34 /** |
| 33 * Computes a murmur hash-2. | 35 * Computes a murmur hash-2. |
| 34 * | 36 * |
| 35 * @param data the data to hash | 37 * @param data the data to hash |
| 81 h ^= h >> 15; | 83 h ^= h >> 15; |
| 82 | 84 |
| 83 return h; | 85 return h; |
| 84 } | 86 } |
| 85 | 87 |
| 88 static void cx_hash_map_clear(struct cx_map_s *map) { | |
| 89 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; | |
| 90 cx_for_n(i, hash_map->bucket_count) { | |
| 91 struct cx_hash_map_element_s *elem = hash_map->buckets[i]; | |
| 92 if (elem != NULL) { | |
| 93 do { | |
| 94 struct cx_hash_map_element_s *next = elem->next; | |
| 95 // free the key data | |
| 96 cxFree(map->allocator, elem->key.data); | |
| 97 // free the node | |
| 98 cxFree(map->allocator, elem); | |
| 99 // proceed | |
| 100 elem = next; | |
| 101 } while (elem != NULL); | |
| 102 | |
| 103 // do not leave a dangling pointer | |
| 104 hash_map->buckets[i] = NULL; | |
| 105 } | |
| 106 } | |
| 107 map->size = 0; | |
| 108 } | |
| 109 | |
| 110 static void cx_hash_map_destructor(struct cx_map_s *map) { | |
| 111 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; | |
| 112 | |
| 113 // free the buckets | |
| 114 cx_hash_map_clear(map); | |
| 115 cxFree(map->allocator, hash_map->buckets); | |
| 116 | |
| 117 // free the map structure | |
| 118 cxFree(map->allocator, map); | |
| 119 } | |
| 120 | |
| 121 static int cx_hash_map_put( | |
| 122 CxMap *map, | |
| 123 CxDataPtr key, | |
| 124 void *value | |
| 125 ) { | |
| 126 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; | |
| 127 CxAllocator *allocator = map->allocator; | |
| 128 | |
| 129 unsigned hash = cx_hash_map_murmur(key.data, key.len); | |
| 130 | |
| 131 size_t slot = hash % hash_map->bucket_count; | |
| 132 struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; | |
| 133 struct cx_hash_map_element_s *prev = NULL; | |
| 134 | |
| 135 while (elm != NULL && elm->key.hash < hash) { | |
| 136 prev = elm; | |
| 137 elm = elm->next; | |
| 138 } | |
| 139 | |
| 140 if (elm == NULL || elm->key.hash != hash) { | |
| 141 struct cx_hash_map_element_s *e = cxMalloc(allocator, sizeof(struct cx_hash_map_element_s)); | |
| 142 if (e == NULL) { | |
| 143 return -1; | |
| 144 } | |
| 145 | |
| 146 // write the value | |
| 147 // TODO: depending on future map features, we may want to copy here | |
| 148 e->data = value; | |
| 149 | |
| 150 // copy the key | |
| 151 void *kd = cxMalloc(allocator, key.len); | |
| 152 if (kd == NULL) { | |
| 153 return -1; | |
| 154 } | |
| 155 memcpy(kd, key.data, key.len); | |
| 156 e->key.data = kd; | |
| 157 e->key.len = key.len; | |
| 158 e->key.hash = hash; | |
| 159 | |
| 160 // insert the element into the linked list | |
| 161 if (prev == NULL) { | |
| 162 hash_map->buckets[slot] = e; | |
| 163 } else { | |
| 164 prev->next = e; | |
| 165 } | |
| 166 e->next = elm; | |
| 167 | |
| 168 // increase the size | |
| 169 map->size++; | |
| 170 } else { | |
| 171 // (elem != NULL && elem->key.hash == hash) - overwrite value of existing element | |
| 172 elm->data = value; | |
| 173 } | |
| 174 | |
| 175 return 0; | |
| 176 } | |
| 86 | 177 |
| 87 /** | 178 /** |
| 88 * Creates a hash map key based on the given data. | 179 * Helper function to avoid code duplication. |
| 89 * | 180 * |
| 90 * This function implicitly computes the hash. | 181 * @param map the map |
| 91 * | 182 * @param key the key to look up |
| 92 * @attention The data will be copied to the key structure. | 183 * @param remove flag indicating whether the looked up entry shall be removed |
| 93 * | 184 * @return the value corresponding to the key or \c NULL |
| 94 * @param data the data for the key | |
| 95 * @return the computed key | |
| 96 */ | 185 */ |
| 97 static struct cx_hash_map_key_s cx_hash_map_key(CxDataPtr data) { | 186 static void *cx_hash_map_get_remove( |
| 98 unsigned char *target = malloc(data.len); | 187 CxMap *map, |
| 99 memcpy(target, data.data, data.len); | 188 CxDataPtr key, |
| 100 struct cx_hash_map_key_s key; | 189 bool remove |
| 101 key.data.data = target; | 190 ) { |
| 102 key.data.len = data.len; | 191 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; |
| 103 key.hash = cx_hash_map_murmur(target, data.len); | 192 |
| 104 return key; | 193 unsigned hash = cx_hash_map_murmur(key.data, key.len); |
| 105 } | 194 |
| 195 size_t slot = hash % hash_map->bucket_count; | |
| 196 struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; | |
| 197 struct cx_hash_map_element_s *prev = NULL; | |
| 198 while (elm && elm->key.hash <= hash) { | |
| 199 if (elm->key.hash == hash && elm->key.len == key.len) { | |
| 200 if (memcmp(elm->key.data, key.data, key.len) == 0) { | |
| 201 void *data = elm->data; | |
| 202 if (remove) { | |
| 203 // unlink | |
| 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 } | |
| 215 return data; | |
| 216 } | |
| 217 } | |
| 218 prev = elm; | |
| 219 elm = prev->next; | |
| 220 } | |
| 221 | |
| 222 return NULL; | |
| 223 } | |
| 224 | |
| 225 static void *cx_hash_map_get( | |
| 226 CxMap const *map, | |
| 227 CxDataPtr key | |
| 228 ) { | |
| 229 // we can safely cast, because we know when remove=false, the map stays untouched | |
| 230 return cx_hash_map_get_remove((CxMap *) map, key, false); | |
| 231 } | |
| 232 | |
| 233 static void *cx_hash_map_remove( | |
| 234 CxMap *map, | |
| 235 CxDataPtr key | |
| 236 ) { | |
| 237 return cx_hash_map_get_remove(map, key, true); | |
| 238 } | |
| 239 | |
| 240 static CxIterator cx_hash_map_iterator(CxMap const *map) { | |
| 241 CxIterator iter; | |
| 242 // TODO: initialize iter | |
| 243 return iter; | |
| 244 } | |
| 245 | |
| 246 static CxIterator cx_hash_map_iterator_keys(CxMap const *map) { | |
| 247 CxIterator iter; | |
| 248 // TODO: initialize iter | |
| 249 return iter; | |
| 250 } | |
| 251 | |
| 252 static CxIterator cx_hash_map_iterator_values(CxMap const *map) { | |
| 253 CxIterator iter; | |
| 254 // TODO: initialize iter | |
| 255 return iter; | |
| 256 } | |
| 257 | |
| 258 static cx_map_class cx_hash_map_class = { | |
| 259 cx_hash_map_destructor, | |
| 260 cx_hash_map_clear, | |
| 261 cx_hash_map_put, | |
| 262 cx_hash_map_get, | |
| 263 cx_hash_map_remove, | |
| 264 cx_hash_map_iterator, | |
| 265 cx_hash_map_iterator_keys, | |
| 266 cx_hash_map_iterator_values, | |
| 267 }; | |
| 268 | |
| 269 CxMap *cxHashMapCreate( | |
| 270 CxAllocator *allocator, | |
| 271 size_t buckets | |
| 272 ) { | |
| 273 if (buckets == 0) { | |
| 274 // implementation defined default | |
| 275 buckets = 16; | |
| 276 } | |
| 277 | |
| 278 struct cx_hash_map_s *map = cxMalloc(allocator, sizeof(struct cx_hash_map_s)); | |
| 279 if (map == NULL) return NULL; | |
| 280 | |
| 281 // initialize hash map members | |
| 282 map->bucket_count = buckets; | |
| 283 map->buckets = cxCalloc(allocator, buckets, sizeof(struct cx_hash_map_element_s *)); | |
| 284 if (map->buckets == NULL) { | |
| 285 cxFree(allocator, map); | |
| 286 return NULL; | |
| 287 } | |
| 288 | |
| 289 // initialize base members | |
| 290 map->base.cl = &cx_hash_map_class; | |
| 291 map->base.allocator = allocator; | |
| 292 map->base.size = 0; | |
| 293 | |
| 294 return (CxMap *) map; | |
| 295 } |
