Mercurial > hg > dav / file comparison

comparison: ucx/hash_map.c

ucx/hash_map.c

changeset 888
af685cc9d623
parent 854
1c8401ece69e
equal deleted inserted replaced
877:b60487c3ec36 888:af685cc9d623
76 76
77 // free the map structure 77 // free the map structure
78 cxFree(map->collection.allocator, map); 78 cxFree(map->collection.allocator, map);
79 } 79 }
80 80
81 static int cx_hash_map_put( 81 static void *cx_hash_map_put(
82 CxMap *map, 82 CxMap *map,
83 CxHashKey key, 83 CxHashKey key,
84 void *value 84 void *value
85 ) { 85 ) {
86 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; 86 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
87 const CxAllocator *allocator = map->collection.allocator; 87 const CxAllocator *allocator = map->collection.allocator;
88 88
89 unsigned hash = key.hash; 89 uint64_t hash = key.hash;
90 if (hash == 0) { 90 if (hash == 0) {
91 cx_hash_murmur(&key); 91 cx_hash_murmur(&key);
92 hash = key.hash; 92 hash = key.hash;
93 } 93 }
94 94
99 while (elm != NULL && elm->key.hash < hash) { 99 while (elm != NULL && elm->key.hash < hash) {
100 prev = elm; 100 prev = elm;
101 elm = elm->next; 101 elm = elm->next;
102 } 102 }
103 103
104 if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len && 104 if (elm != NULL && cx_hash_key_cmp(&elm->key, &key) == 0) {
105 memcmp(elm->key.data, key.data, key.len) == 0) {
106 // overwrite existing element, but call destructors first 105 // overwrite existing element, but call destructors first
107 cx_invoke_destructor(map, elm->data); 106 cx_invoke_destructor(map, elm->data);
108 if (map->collection.store_pointer) { 107 if (value == NULL) {
108 memset(elm->data, 0, map->collection.elem_size);
109 } else if (map->collection.store_pointer) {
109 memcpy(elm->data, &value, sizeof(void *)); 110 memcpy(elm->data, &value, sizeof(void *));
110 } else { 111 } else {
111 memcpy(elm->data, value, map->collection.elem_size); 112 memcpy(elm->data, value, map->collection.elem_size);
112 } 113 }
113 } else { 114 } else {
114 // allocate new element 115 // allocate new element
115 struct cx_hash_map_element_s *e = cxMalloc( 116 struct cx_hash_map_element_s *e = cxMalloc(
116 allocator, 117 allocator,
117 sizeof(struct cx_hash_map_element_s) + map->collection.elem_size 118 sizeof(struct cx_hash_map_element_s) + map->collection.elem_size
118 ); 119 );
119 if (e == NULL) return -1; 120 if (e == NULL) return NULL;
120 121
121 // write the value 122 // write the value
122 if (map->collection.store_pointer) { 123 if (value == NULL) {
124 memset(e->data, 0, map->collection.elem_size);
125 } else if (map->collection.store_pointer) {
123 memcpy(e->data, &value, sizeof(void *)); 126 memcpy(e->data, &value, sizeof(void *));
124 } else { 127 } else {
125 memcpy(e->data, value, map->collection.elem_size); 128 memcpy(e->data, value, map->collection.elem_size);
126 } 129 }
127 130
128 // copy the key 131 // copy the key
129 void *kd = cxMalloc(allocator, key.len); 132 void *kd = cxMalloc(allocator, key.len);
130 if (kd == NULL) return -1; 133 if (kd == NULL) {
134 cxFree(allocator, e);
135 return NULL;
136 }
131 memcpy(kd, key.data, key.len); 137 memcpy(kd, key.data, key.len);
132 e->key.data = kd; 138 e->key.data = kd;
133 e->key.len = key.len; 139 e->key.len = key.len;
134 e->key.hash = hash; 140 e->key.hash = hash;
135 141
138 hash_map->buckets[slot] = e; 144 hash_map->buckets[slot] = e;
139 } else { 145 } else {
140 prev->next = e; 146 prev->next = e;
141 } 147 }
142 e->next = elm; 148 e->next = elm;
149 elm = e;
143 150
144 // increase the size 151 // increase the size
145 map->collection.size++; 152 map->collection.size++;
146 } 153 }
147 154
148 return 0; 155 // return pointer to the element
156 return elm->data;
149 } 157 }
150 158
151 static void cx_hash_map_unlink( 159 static void cx_hash_map_unlink(
152 struct cx_hash_map_s *hash_map, 160 struct cx_hash_map_s *hash_map,
153 size_t slot, 161 size_t slot,
193 void *targetbuf, 201 void *targetbuf,
194 bool remove 202 bool remove
195 ) { 203 ) {
196 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; 204 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
197 205
198 unsigned hash = key.hash; 206 uint64_t hash = key.hash;
199 if (hash == 0) { 207 if (hash == 0) {
200 cx_hash_murmur(&key); 208 cx_hash_murmur(&key);
201 hash = key.hash; 209 hash = key.hash;
202 } 210 }
203 211
204 size_t slot = hash % hash_map->bucket_count; 212 size_t slot = hash % hash_map->bucket_count;
205 struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; 213 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
206 struct cx_hash_map_element_s *prev = NULL; 214 struct cx_hash_map_element_s *prev = NULL;
207 while (elm && elm->key.hash <= hash) { 215 while (elm && elm->key.hash <= hash) {
208 if (elm->key.hash == hash && elm->key.len == key.len) { 216 if (cx_hash_key_cmp(&elm->key, &key) == 0) {
209 if (memcmp(elm->key.data, key.data, key.len) == 0) { 217 if (remove) {
210 if (remove) { 218 if (targetbuf == NULL) {
211 if (targetbuf == NULL) { 219 cx_invoke_destructor(map, elm->data);
212 cx_invoke_destructor(map, elm->data);
213 } else {
214 memcpy(targetbuf, elm->data, map->collection.elem_size);
215 }
216 cx_hash_map_unlink(hash_map, slot, prev, elm);
217 } else { 220 } else {
218 assert(targetbuf != NULL); 221 memcpy(targetbuf, elm->data, map->collection.elem_size);
219 void *data = NULL;
220 if (map->collection.store_pointer) {
221 data = *(void **) elm->data;
222 } else {
223 data = elm->data;
224 }
225 memcpy(targetbuf, &data, sizeof(void *));
226 } 222 }
227 return 0; 223 cx_hash_map_unlink(hash_map, slot, prev, elm);
224 } else {
225 assert(targetbuf != NULL);
226 void *data = NULL;
227 if (map->collection.store_pointer) {
228 data = *(void **) elm->data;
229 } else {
230 data = elm->data;
231 }
232 memcpy(targetbuf, &data, sizeof(void *));
228 } 233 }
234 return 0;
229 } 235 }
230 prev = elm; 236 prev = elm;
231 elm = prev->next; 237 elm = prev->next;
232 } 238 }
233 239
258 return (void*) &iter->entry; 264 return (void*) &iter->entry;
259 } 265 }
260 266
261 static void *cx_hash_map_iter_current_key(const void *it) { 267 static void *cx_hash_map_iter_current_key(const void *it) {
262 const CxMapIterator *iter = it; 268 const CxMapIterator *iter = it;
263 struct cx_hash_map_element_s *elm = iter->elem; 269 return (void*) iter->entry.key;
264 return &elm->key;
265 } 270 }
266 271
267 static void *cx_hash_map_iter_current_value(const void *it) { 272 static void *cx_hash_map_iter_current_value(const void *it) {
268 const CxMapIterator *iter = it; 273 const CxMapIterator *iter = it;
269 const CxMap *map = iter->map.c; 274 return iter->entry.value;
270 struct cx_hash_map_element_s *elm = iter->elem;
271 if (map->collection.store_pointer) {
272 return *(void **) elm->data;
273 } else {
274 return elm->data;
275 }
276 } 275 }
277 276
278 static bool cx_hash_map_iter_valid(const void *it) { 277 static bool cx_hash_map_iter_valid(const void *it) {
279 const CxMapIterator *iter = it; 278 const CxMapIterator *iter = it;
280 return iter->elem != NULL; 279 return iter->elem != NULL;
281 } 280 }
282 281
283 static void cx_hash_map_iter_next(void *it) { 282 static void cx_hash_map_iter_next(void *it) {
284 CxMapIterator *iter = it; 283 CxMapIterator *iter = it;
285 CxMap *map = iter->map.m; 284 CxMap *map = iter->map;
286 struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map; 285 struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map;
287 struct cx_hash_map_element_s *elm = iter->elem; 286 struct cx_hash_map_element_s *elm = iter->elem;
288 287
289 // remove current element, if asked 288 // remove current element, if asked
290 if (iter->base.remove) { 289 if (iter->base.remove) {
307 // destroy 306 // destroy
308 cx_invoke_destructor(map, elm->data); 307 cx_invoke_destructor(map, elm->data);
309 308
310 // unlink 309 // unlink
311 cx_hash_map_unlink(hmap, iter->slot, prev, elm); 310 cx_hash_map_unlink(hmap, iter->slot, prev, elm);
311 iter->elem_count--;
312 312
313 // advance 313 // advance
314 elm = next; 314 elm = next;
315 } else { 315 } else {
316 // just advance 316 // just advance
327 // copy data to a location where the iterator can point to 327 // copy data to a location where the iterator can point to
328 // we need to do it here, because the iterator function call 328 // we need to do it here, because the iterator function call
329 // must not modify the iterator (the parameter is const) 329 // must not modify the iterator (the parameter is const)
330 if (elm != NULL) { 330 if (elm != NULL) {
331 iter->entry.key = &elm->key; 331 iter->entry.key = &elm->key;
332 if (iter->map.c->collection.store_pointer) { 332 if (map->collection.store_pointer) {
333 iter->entry.value = *(void **) elm->data; 333 iter->entry.value = *(void **) elm->data;
334 } else { 334 } else {
335 iter->entry.value = elm->data; 335 iter->entry.value = elm->data;
336 } 336 }
337 } 337 }
341 const CxMap *map, 341 const CxMap *map,
342 enum cx_map_iterator_type type 342 enum cx_map_iterator_type type
343 ) { 343 ) {
344 CxMapIterator iter; 344 CxMapIterator iter;
345 345
346 iter.map.c = map; 346 iter.map = (CxMap*) map;
347 iter.elem_count = map->collection.size; 347 iter.elem_count = map->collection.size;
348 348
349 switch (type) { 349 switch (type) {
350 case CX_MAP_ITERATOR_PAIRS: 350 case CX_MAP_ITERATOR_PAIRS:
351 iter.elem_size = sizeof(CxMapEntry); 351 iter.elem_size = sizeof(CxMapEntry);
364 } 364 }
365 365
366 iter.base.valid = cx_hash_map_iter_valid; 366 iter.base.valid = cx_hash_map_iter_valid;
367 iter.base.next = cx_hash_map_iter_next; 367 iter.base.next = cx_hash_map_iter_next;
368 iter.base.remove = false; 368 iter.base.remove = false;
369 iter.base.mutating = false; 369 iter.base.allow_remove = true;
370 370
371 iter.slot = 0; 371 iter.slot = 0;
372 iter.index = 0; 372 iter.index = 0;
373 373
374 if (map->collection.size > 0) { 374 if (map->collection.size > 0) {

Mercurial Repository: dav

mercurial