Mercurial > hg > ucx / file comparison

comparison: src/kv_list.c

src/kv_list.c

changeset 1367
6b3d52dd176e
parent 1365
e4135791687e
equal deleted inserted replaced
1366:70ce877c838a 1367:6b3d52dd176e
38 struct cx_hash_map_s map_base; 38 struct cx_hash_map_s map_base;
39 /** Back-reference to the list. */ 39 /** Back-reference to the list. */
40 cx_kv_list *list; 40 cx_kv_list *list;
41 }; 41 };
42 42
43 /** The list aspect (must have the same layout as the normal linked list). */
44 struct cx_kv_list_list_s {
45 struct cx_list_s list_base;
46 void *begin;
47 void *end;
48 };
49
50 struct cx_kv_list_s { 43 struct cx_kv_list_s {
51 struct cx_kv_list_list_s list; 44 struct cx_linked_list_s list;
52 /** The lookup map - stores pointers to the nodes. */ 45 /** The lookup map - stores pointers to the nodes. */
53 struct cx_kv_list_map_s *map; 46 struct cx_kv_list_map_s *map;
54 const cx_list_class *list_methods; 47 const cx_list_class *list_methods;
55 const cx_map_class *map_methods; 48 const cx_map_class *map_methods;
56 cx_destructor_func list_destr; 49 cx_destructor_func list_destr;
80 73
81 static void cx_kv_list_destructor_wrapper_map(void *list_ptr, void *node_data) { 74 static void cx_kv_list_destructor_wrapper_map(void *list_ptr, void *node_data) {
82 const cx_kv_list *kv_list = list_ptr; 75 const cx_kv_list *kv_list = list_ptr;
83 // the elem called with a map destructor is a pointer to the node 76 // the elem called with a map destructor is a pointer to the node
84 // we need to deref the elem accordingly 77 // we need to deref the elem accordingly
85 void *elem = kv_list->list.list_base.collection.store_pointer ? *(void**)node_data : node_data; 78 void *elem = kv_list->list.base.collection.store_pointer ? *(void**)node_data : node_data;
86 if (kv_list->list_destr) { 79 if (kv_list->list_destr) {
87 kv_list->list_destr(elem); 80 kv_list->list_destr(elem);
88 } 81 }
89 if (kv_list->list_destr2) { 82 if (kv_list->list_destr2) {
90 kv_list->list_destr2(kv_list->list_destr_data, elem); 83 kv_list->list_destr2(kv_list->list_destr_data, elem);
98 } 91 }
99 92
100 static void cx_kv_list_update_destructors(cx_kv_list *list) { 93 static void cx_kv_list_update_destructors(cx_kv_list *list) {
101 // we copy the destructors to our custom fields and register 94 // we copy the destructors to our custom fields and register
102 // an own destructor function which invokes all these 95 // an own destructor function which invokes all these
103 if (list->list.list_base.collection.simple_destructor != NULL) { 96 if (list->list.base.collection.simple_destructor != NULL) {
104 list->list_destr = list->list.list_base.collection.simple_destructor; 97 list->list_destr = list->list.base.collection.simple_destructor;
105 list->list.list_base.collection.simple_destructor = NULL; 98 list->list.base.collection.simple_destructor = NULL;
106 } 99 }
107 if (list->list.list_base.collection.advanced_destructor != cx_kv_list_destructor_wrapper_list) { 100 if (list->list.base.collection.advanced_destructor != cx_kv_list_destructor_wrapper_list) {
108 list->list_destr2 = list->list.list_base.collection.advanced_destructor; 101 list->list_destr2 = list->list.base.collection.advanced_destructor;
109 list->list_destr_data = list->list.list_base.collection.destructor_data; 102 list->list_destr_data = list->list.base.collection.destructor_data;
110 list->list.list_base.collection.advanced_destructor = cx_kv_list_destructor_wrapper_list; 103 list->list.base.collection.advanced_destructor = cx_kv_list_destructor_wrapper_list;
111 list->list.list_base.collection.destructor_data = list; 104 list->list.base.collection.destructor_data = list;
112 } 105 }
113 if (list->map->map_base.base.collection.simple_destructor != NULL) { 106 if (list->map->map_base.base.collection.simple_destructor != NULL) {
114 list->map_destr = list->map->map_base.base.collection.simple_destructor; 107 list->map_destr = list->map->map_base.base.collection.simple_destructor;
115 list->map->map_base.base.collection.simple_destructor = NULL; 108 list->map->map_base.base.collection.simple_destructor = NULL;
116 } 109 }
124 117
125 static void cx_kvl_deallocate(struct cx_list_s *list) { 118 static void cx_kvl_deallocate(struct cx_list_s *list) {
126 cx_kv_list *kv_list = (cx_kv_list*)list; 119 cx_kv_list *kv_list = (cx_kv_list*)list;
127 // patch the destructors 120 // patch the destructors
128 cx_kv_list_update_destructors(kv_list); 121 cx_kv_list_update_destructors(kv_list);
129 // free the map first 122 // free the map first, but skip the destructors of the map
123 cxDefineAdvancedDestructor(&kv_list->map->map_base.base, NULL, NULL);
130 kv_list->map_methods->deallocate(&kv_list->map->map_base.base); 124 kv_list->map_methods->deallocate(&kv_list->map->map_base.base);
125 // then free the list, now the destructors may be called
131 kv_list->list_methods->deallocate(list); 126 kv_list->list_methods->deallocate(list);
132 } 127 }
133 128
134 static void *cx_kvl_insert_element( 129 static void *cx_kvl_insert_element(
135 struct cx_list_s *list, 130 struct cx_list_s *list,
194 cx_kv_list_update_destructors(kv_list); 189 cx_kv_list_update_destructors(kv_list);
195 cxDefineAdvancedDestructor(&kv_list->map->map_base.base, NULL, NULL); 190 cxDefineAdvancedDestructor(&kv_list->map->map_base.base, NULL, NULL);
196 // clear the list 191 // clear the list
197 kv_list->list_methods->clear(list); 192 kv_list->list_methods->clear(list);
198 // then clear the map 193 // then clear the map
199 cxMapClear(&kv_list->map->map_base.base); 194 kv_list->map_methods->clear(&kv_list->map->map_base.base);
200 } 195 }
201 196
202 static int cx_kvl_swap( 197 static int cx_kvl_swap(
203 struct cx_list_s *list, 198 struct cx_list_s *list,
204 size_t i, 199 size_t i,
248 } 243 }
249 244
250 static void cx_kvl_map_deallocate(struct cx_map_s *map) { 245 static void cx_kvl_map_deallocate(struct cx_map_s *map) {
251 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list; 246 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
252 kv_list->map_methods->deallocate(map); 247 kv_list->map_methods->deallocate(map);
253 kv_list->list_methods->deallocate(&kv_list->list.list_base); 248 kv_list->list_methods->deallocate(&kv_list->list.base);
254 } 249 }
255 250
256 static void cx_kvl_map_clear(struct cx_map_s *map) { 251 static void cx_kvl_map_clear(struct cx_map_s *map) {
257 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list; 252 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
258 cx_kv_list_update_destructors(kv_list); 253 cx_kv_list_update_destructors(kv_list);
261 } 256 }
262 257
263 static void *cx_kvl_map_put(CxMap *map, CxHashKey key, void *value) { 258 static void *cx_kvl_map_put(CxMap *map, CxHashKey key, void *value) {
264 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list; 259 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
265 // insert the data into the list first (assume that insertion destroys the sorted property) 260 // insert the data into the list first (assume that insertion destroys the sorted property)
266 kv_list->list.list_base.collection.sorted = false; 261 kv_list->list.base.collection.sorted = false;
267 // TODO: use the same trick as above to increase the element size temporarily to add the key to the data 262 // TODO: use the same trick as above to increase the element size temporarily to add the key to the data
268 void *node_data = kv_list->list_methods->insert_element( 263 void *node_data = kv_list->list_methods->insert_element(
269 &kv_list->list.list_base, kv_list->list.list_base.collection.size, value); 264 &kv_list->list.base, kv_list->list.base.collection.size, value);
270 if (node_data == NULL) return NULL; // LCOV_EXCL_LINE 265 if (node_data == NULL) return NULL; // LCOV_EXCL_LINE
271 // then insert the key into the map, referring to the node data 266 // then insert the key into the map, referring to the node data
272 // TODO: check if we still get a correct pointer when the list is storing pointers 267 // TODO: check if we still get a correct pointer when the list is storing pointers
273 return kv_list->map_methods->put(map, key, node_data); 268 return kv_list->map_methods->put(map, key, node_data);
274 } 269 }
292 287
293 // check if the outside caller want's us to return or to destroy the element 288 // check if the outside caller want's us to return or to destroy the element
294 if (targetbuf == NULL) { 289 if (targetbuf == NULL) {
295 // patch the destructors and invoke them through the wrapper 290 // patch the destructors and invoke them through the wrapper
296 cx_kv_list_update_destructors(kv_list); 291 cx_kv_list_update_destructors(kv_list);
297 cx_invoke_advanced_destructor(&kv_list->list.list_base, node_data); 292 cx_invoke_advanced_destructor(&kv_list->list.base, node_data);
298 } else { 293 } else {
299 // copy the element to the target buffer 294 // copy the element to the target buffer
300 memcpy(targetbuf, node_data, kv_list->list.list_base.collection.elem_size); 295 memcpy(targetbuf, node_data, kv_list->list.base.collection.elem_size);
301 } 296 }
302 297
303 // calculate the address of the node 298 // calculate the address of the node
304 void *node_ptr = (char*)node_data - 2*sizeof(void*); 299 void *node_ptr = (char*)node_data - kv_list->list.loc_data;
305 300
306 // unlink the node 301 // unlink the node
307 cx_linked_list_remove( 302 cx_linked_list_remove(
308 &kv_list->list.begin, 303 &kv_list->list.begin,
309 &kv_list->list.end, 304 &kv_list->list.end,
310 0, 305 kv_list->list.loc_prev,
311 sizeof(void*), 306 kv_list->list.loc_next,
312 node_ptr 307 node_ptr
313 ); 308 );
314 309
315 // decrement the list's size 310 // decrement the list's size
316 kv_list->list.list_base.collection.size--; 311 kv_list->list.base.collection.size--;
317 312
318 // deallocate the node 313 // deallocate the node
319 cxFree(kv_list->list.list_base.collection.allocator, node_ptr); 314 cxFree(kv_list->list.base.collection.allocator, node_ptr);
320 315
321 return 0; 316 return 0;
322 } 317 }
323 318
324 CxMapIterator cx_kvl_map_iterator(const CxMap *map, enum cx_map_iterator_type type) { 319 CxMapIterator cx_kvl_map_iterator(const CxMap *map, enum cx_map_iterator_type type) {
362 } 357 }
363 358
364 // create a normal linked list and a normal hash map, first 359 // create a normal linked list and a normal hash map, first
365 CxList *list = cxLinkedListCreate(allocator, comparator, elem_size); 360 CxList *list = cxLinkedListCreate(allocator, comparator, elem_size);
366 if (list == NULL) return NULL; // LCOV_EXCL_LINE 361 if (list == NULL) return NULL; // LCOV_EXCL_LINE
362 cx_linked_list *ll = (cx_linked_list*)list;
363 ll->extra_data_len = sizeof(CxHashKey);
367 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0); 364 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
368 if (map == NULL) { // LCOV_EXCL_START 365 if (map == NULL) { // LCOV_EXCL_START
369 cxListFree(list); 366 cxListFree(list);
370 return NULL; 367 return NULL;
371 } // LCOV_EXCL_STOP 368 } // LCOV_EXCL_STOP
419 CxList *list = cxKvListCreate(allocator, comparator, elem_size); 416 CxList *list = cxKvListCreate(allocator, comparator, elem_size);
420 return list == NULL ? NULL : cxKvListAsMap(list); 417 return list == NULL ? NULL : cxKvListAsMap(list);
421 } 418 }
422 419
423 CxList *cxKvListAsList(CxMap *map) { 420 CxList *cxKvListAsList(CxMap *map) {
424 return &((struct cx_kv_list_map_s*)map)->list->list.list_base; 421 return &((struct cx_kv_list_map_s*)map)->list->list.base;
425 } 422 }
426 423
427 CxMap *cxKvListAsMap(CxList *list) { 424 CxMap *cxKvListAsMap(CxList *list) {
428 return &((cx_kv_list*)list)->map->map_base.base; 425 return &((cx_kv_list*)list)->map->map_base.base;
429 } 426 }
430 427
431 int cx_kv_list_set_key(CxList *list, size_t index, CxHashKey key) { 428 int cx_kv_list_set_key(CxList *list, size_t index, CxHashKey key) {
432 return -1; 429 cx_kv_list *kv_list = (cx_kv_list*)list;
430 char *node_data = kv_list->list_methods->at(list, index);
431 char *loc_key = node_data + list->collection.elem_size;
432 memcpy(loc_key, &key, sizeof(key));
433
434 // TODO: what happens when we are _replacing_ an existing key?
435 kv_list->map_methods->put(&kv_list->map->map_base.base, key, node_data);
436 // TODO: what happens if the map cocks up and returns NULL?
437
438 return 0;
433 } 439 }
434 440
435 int cx_kv_list_remove_key(CxList *list, size_t index, CxHashKey key) { 441 int cx_kv_list_remove_key(CxList *list, size_t index, CxHashKey key) {
436 return -1; 442 return -1;
437 } 443 }

Mercurial Repository: ucx

mercurial