Mercurial > hg > toolkit / file comparison

comparison: ucx/map.c

ucx/map.c

changeset 157
0b33b9396851
parent 152
62921b370c60
child 162
18892c0a9adc
equal deleted inserted replaced
156:62f1a55535e7 157:0b33b9396851
1 /* 1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 * 3 *
4 * Copyright 2016 Olaf Wintermann. All rights reserved. 4 * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved.
5 * 5 *
6 * Redistribution and use in source and binary forms, with or without 6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met: 7 * modification, are permitted provided that the following conditions are met:
8 * 8 *
9 * 1. Redistributions of source code must retain the above copyright 9 * 1. Redistributions of source code must retain the above copyright
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 "ucx/map.h"
30
29 #include <stdlib.h> 31 #include <stdlib.h>
30 #include <string.h> 32 #include <string.h>
31
32 #include "map.h"
33 33
34 UcxMap *ucx_map_new(size_t size) { 34 UcxMap *ucx_map_new(size_t size) {
35 return ucx_map_new_a(NULL, size); 35 return ucx_map_new_a(NULL, size);
36 } 36 }
37 37
84 84
85 void ucx_map_free_content(UcxMap *map, ucx_destructor destr) { 85 void ucx_map_free_content(UcxMap *map, ucx_destructor destr) {
86 UcxMapIterator iter = ucx_map_iterator(map); 86 UcxMapIterator iter = ucx_map_iterator(map);
87 void *val; 87 void *val;
88 UCX_MAP_FOREACH(key, val, iter) { 88 UCX_MAP_FOREACH(key, val, iter) {
89 destr(val); 89 if (destr) {
90 destr(val);
91 } else {
92 alfree(map->allocator, val);
93 }
90 } 94 }
91 } 95 }
92 96
93 void ucx_map_clear(UcxMap *map) { 97 void ucx_map_clear(UcxMap *map) {
94 if (map->count == 0) { 98 if (map->count == 0) {
97 ucx_map_free_elmlist_contents(map); 101 ucx_map_free_elmlist_contents(map);
98 memset(map->map, 0, map->size*sizeof(UcxMapElement*)); 102 memset(map->map, 0, map->size*sizeof(UcxMapElement*));
99 map->count = 0; 103 map->count = 0;
100 } 104 }
101 105
102 int ucx_map_copy(UcxMap *restrict from, UcxMap *restrict to, 106 int ucx_map_copy(UcxMap *from, UcxMap *to, copy_func fnc, void *data) {
103 copy_func fnc, void *data) {
104 UcxMapIterator i = ucx_map_iterator(from); 107 UcxMapIterator i = ucx_map_iterator(from);
105 void *value; 108 void *value;
106 UCX_MAP_FOREACH(key, value, i) { 109 UCX_MAP_FOREACH(key, value, i) {
107 if (ucx_map_put(to, key, fnc ? fnc(value, data) : value)) { 110 if (ucx_map_put(to, key, fnc ? fnc(value, data) : value)) {
108 return 1; 111 return 1;
149 152
150 int ucx_map_put(UcxMap *map, UcxKey key, void *data) { 153 int ucx_map_put(UcxMap *map, UcxKey key, void *data) {
151 UcxAllocator *allocator = map->allocator; 154 UcxAllocator *allocator = map->allocator;
152 155
153 if (key.hash == 0) { 156 if (key.hash == 0) {
154 key.hash = ucx_hash((char*)key.data, key.len); 157 key.hash = ucx_hash((const char*)key.data, key.len);
155 } 158 }
156 159
157 size_t slot = key.hash%map->size; 160 struct UcxMapKey mapkey;
158 UcxMapElement *restrict elm = map->map[slot]; 161 mapkey.hash = key.hash;
159 UcxMapElement *restrict prev = NULL; 162
160 163 size_t slot = mapkey.hash%map->size;
161 while (elm && elm->key.hash < key.hash) { 164 UcxMapElement *elm = map->map[slot];
165 UcxMapElement *prev = NULL;
166
167 while (elm && elm->key.hash < mapkey.hash) {
162 prev = elm; 168 prev = elm;
163 elm = elm->next; 169 elm = elm->next;
164 } 170 }
165 171
166 if (!elm || elm->key.hash != key.hash) { 172 if (!elm || elm->key.hash != mapkey.hash) {
167 UcxMapElement *e = (UcxMapElement*)almalloc( 173 UcxMapElement *e = (UcxMapElement*)almalloc(
168 allocator, sizeof(UcxMapElement)); 174 allocator, sizeof(UcxMapElement));
169 if (!e) { 175 if (!e) {
170 return -1; 176 return -1;
171 } 177 }
183 void *kd = almalloc(allocator, key.len); 189 void *kd = almalloc(allocator, key.len);
184 if (!kd) { 190 if (!kd) {
185 return -1; 191 return -1;
186 } 192 }
187 memcpy(kd, key.data, key.len); 193 memcpy(kd, key.data, key.len);
188 key.data = kd; 194 mapkey.data = kd;
189 elm->key = key; 195 mapkey.len = key.len;
196 elm->key = mapkey;
190 map->count++; 197 map->count++;
191 } 198 }
192 elm->data = data; 199 elm->data = data;
193 200
194 return 0; 201 return 0;
195 } 202 }
196 203
197 void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, _Bool remove) { 204 static void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, int remove) {
198 if(key.hash == 0) { 205 if(key.hash == 0) {
199 key.hash = ucx_hash((char*)key.data, key.len); 206 key.hash = ucx_hash((const char*)key.data, key.len);
200 } 207 }
201 208
202 size_t slot = key.hash%map->size; 209 size_t slot = key.hash%map->size;
203 UcxMapElement *restrict elm = map->map[slot]; 210 UcxMapElement *elm = map->map[slot];
204 UcxMapElement *restrict pelm = NULL; 211 UcxMapElement *pelm = NULL;
205 while (elm && elm->key.hash <= key.hash) { 212 while (elm && elm->key.hash <= key.hash) {
206 if(elm->key.hash == key.hash) { 213 if(elm->key.hash == key.hash) {
207 int n = (key.len > elm->key.len) ? elm->key.len : key.len; 214 int n = (key.len > elm->key.len) ? elm->key.len : key.len;
208 if (memcmp(elm->key.data, key.data, n) == 0) { 215 if (memcmp(elm->key.data, key.data, n) == 0) {
209 void *data = elm->data; 216 void *data = elm->data;
234 241
235 void *ucx_map_remove(UcxMap *map, UcxKey key) { 242 void *ucx_map_remove(UcxMap *map, UcxKey key) {
236 return ucx_map_get_and_remove(map, key, 1); 243 return ucx_map_get_and_remove(map, key, 1);
237 } 244 }
238 245
239 UcxKey ucx_key(void *data, size_t len) { 246 UcxKey ucx_key(const void *data, size_t len) {
240 UcxKey key; 247 UcxKey key;
241 key.data = data; 248 key.data = data;
242 key.len = len; 249 key.len = len;
243 key.hash = ucx_hash((const char*) data, len); 250 key.hash = ucx_hash((const char*)data, len);
244 return key; 251 return key;
245 } 252 }
246 253
247 254
248 int ucx_hash(const char *data, size_t len) { 255 int ucx_hash(const char *data, size_t len) {
307 while (i->index < i->map->size) { 314 while (i->index < i->map->size) {
308 if (e) { 315 if (e) {
309 if (e->data) { 316 if (e->data) {
310 i->cur = e; 317 i->cur = e;
311 *elm = e->data; 318 *elm = e->data;
312 *key = e->key; 319 key->data = e->key.data;
320 key->hash = e->key.hash;
321 key->len = e->key.len;
313 return 1; 322 return 1;
314 } 323 }
315 324
316 e = e->next; 325 e = e->next;
317 } else { 326 } else {

Mercurial Repository: toolkit

mercurial