dav: comparison ucx/kv

-:e77ccf1c4bb3
+:4d58cbcc9efa
 list->map->map_base.base.collection.destructor_data = NULL;
 }
 }
 static CxHashKey *cx_kv_list_loc_key(cx_kv_list *list, void *node_data) {
-return (CxHashKey*)((char*)node_data + list->list.base.collection.elem_size);
+return (CxHashKey*)((char*)node_data - list->list.loc_data + list->list.loc_extra);
 }
 static void cx_kvl_deallocate(struct cx_list_s *list) {
 cx_kv_list *kv_list = (cx_kv_list*)list;
 // patch the destructors
 // (the first to find the index, the second to get a pointer)
 if (list->collection.size == 0) return 0;
 size_t index;
 cx_linked_list *ll = &kv_list->list;
-char *node = cx_linked_list_find(
+char *node = cx_linked_list_find_c(
 ll->begin,
 ll->loc_next, ll->loc_data,
-list->collection.cmpfunc, elem,
+elem, &index,
-&index
+cx_list_compare_wrapper,
+list
 );
 if (node == NULL) {
 return list->collection.size;
 }
 if (remove) {
 return iter;
 }
 static void cx_kvl_map_deallocate(struct cx_map_s *map) {
 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
+cx_kv_list_update_destructors(kv_list);
 kv_list->map_methods->deallocate(map);
 kv_list->list_methods->deallocate(&kv_list->list.base);
 }
 static void cx_kvl_map_clear(struct cx_map_s *map) {
 cx_kv_list_update_destructors(kv_list);
 kv_list->list_methods->clear(&kv_list->list.base);
 kv_list->map_methods->clear(map);
 }
-static void *cx_kvl_map_put(CxMap *map, CxHashKey key, void *value) {
+static void *cx_kvl_map_get(const CxMap *map, CxHashKey key) {
-cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
-// if the hash has not yet been computed, do it now
-if (key.hash == 0) {
-cx_hash_murmur(&key);
-}
-// reserve memory in the map first
-void **map_data = kv_list->map_methods->put(map, key, NULL);
-if (map_data == NULL) return NULL; // LCOV_EXCL_LINE
-// insert the data into the list (which most likely destroys the sorted property)
-kv_list->list.base.collection.sorted = false;
-void *node_data = kv_list->list_methods->insert_element(
-&kv_list->list.base, kv_list->list.base.collection.size,
-kv_list->list.base.collection.store_pointer ? &value : value);
-if (node_data == NULL) { // LCOV_EXCL_START
-// non-destructively remove the key again
-kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &map_data);
-return NULL;
-} // LCOV_EXCL_STOP
-// write the node pointer to the map entry
-*map_data = node_data;
-// copy the key to the node data
-CxHashKey *key_ptr = cx_kv_list_loc_key(kv_list, node_data);
-*key_ptr = key;
-// we must return node_data here and not map_data,
-// because the node_data is the actual element of this collection
-return node_data;
-}
-void *cx_kvl_map_get(const CxMap *map, CxHashKey key) {
 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
 void *node_data = kv_list->map_methods->get(map, key);
 if (node_data == NULL) return NULL; // LCOV_EXCL_LINE
 // return the node data
 return kv_list->list.base.collection.store_pointer ? *(void**)node_data : node_data;
 }
-int cx_kvl_map_remove(CxMap *map, CxHashKey key, void *targetbuf) {
+static int cx_kvl_map_remove(CxMap *map, CxHashKey key, void *targetbuf) {
 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
 void *node_data;
 if (kv_list->map_methods->remove(map, key, &node_data)) {
 return 1;
 // deallocate the node
 cxFree(kv_list->list.base.collection.allocator, node_ptr);
 return 0;
+}
+static CxMapEntry cx_kvl_map_put(CxMap *map, CxHashKey key, void *value) {
+cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
+// if the hash has not yet been computed, do it now
+if (key.hash == 0) {
+cx_hash_murmur(&key);
+}
+// remove any existing element first
+cx_kvl_map_remove(map, key, NULL);
+// now reserve new memory in the map
+CxMapEntry map_entry = kv_list->map_methods->put(map, key, NULL);
+if (map_entry.key == NULL) return (CxMapEntry){NULL, NULL}; // LCOV_EXCL_LINE
+// insert the data into the list (which most likely destroys the sorted property)
+kv_list->list.base.collection.sorted = false;
+void *node_data = kv_list->list_methods->insert_element(
+&kv_list->list.base, kv_list->list.base.collection.size,
+kv_list->list.base.collection.store_pointer ? &value : value);
+if (node_data == NULL) { // LCOV_EXCL_START
+// non-destructively remove the key again
+void *dummy;
+kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &dummy);
+return (CxMapEntry){NULL, NULL};
+} // LCOV_EXCL_STOP
+// write the node pointer to the map entry
+*(void**)map_entry.value = node_data;
+// copy the key to the node data
+CxHashKey *key_ptr = cx_kv_list_loc_key(kv_list, node_data);
+*key_ptr = *map_entry.key;
+// we must return an entry that points to the node data!
+return (CxMapEntry ){key_ptr, node_data};
 }
 static void *cx_kvl_iter_current_entry(const void *it) {
 const CxMapIterator *iter = it;
 return (void*)&iter->entry;
 static bool cx_kvl_iter_valid(const void *it) {
 const CxMapIterator *iter = it;
 return iter->elem != NULL;
 }
-CxMapIterator cx_kvl_map_iterator(const CxMap *map, enum cx_map_iterator_type type) {
+static CxMapIterator cx_kvl_map_iterator(const CxMap *map, enum cx_map_iterator_type type) {
 CxMapIterator iter = {0};
 iter.type = type;
 iter.map = (CxMap*)map;
 // although we iterate over the list, we only report that many elements that have a key in the map
 }
 return iter;
 }
+static int cx_kvl_change_capacity(struct cx_list_s *list,
+cx_attr_unused size_t cap) {
+// since our backing list is a linked list, we don't need to do much here,
+// but rehashing the map is quite useful
+cx_kv_list *kv_list = (cx_kv_list*)list;
+cxMapRehash(&kv_list->map->map_base.base);
+return 0;
+}
 static cx_list_class cx_kv_list_class = {
 cx_kvl_deallocate,
 cx_kvl_insert_element,
 cx_kvl_insert_array,
 cx_kvl_insert_sorted,
 cx_kvl_at,
 cx_kvl_find_remove,
 cx_kvl_sort,
 NULL,
 cx_kvl_reverse,
+cx_kvl_change_capacity,
 cx_kvl_iterator,
 };
 static cx_map_class cx_kv_map_class = {
 cx_kvl_map_deallocate,
 cx_kvl_map_iterator,
 };
 CxList *cxKvListCreate(
 const CxAllocator *allocator,
-cx_compare_func comparator,
 size_t elem_size
 ) {
 if (allocator == NULL) {
 allocator = cxDefaultAllocator;
 }
 // create a normal linked list and a normal hash map, first
-CxList *list = cxLinkedListCreate(allocator, comparator, elem_size);
+CxList *list = cxLinkedListCreate(allocator, elem_size);
 if (list == NULL) return NULL; // LCOV_EXCL_LINE
 cx_linked_list *ll = (cx_linked_list*)list;
-ll->extra_data_len = sizeof(CxHashKey);
+cx_linked_list_extra_data(ll, sizeof(CxHashKey));
 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
 if (map == NULL) { // LCOV_EXCL_START
 cxListFree(list);
 return NULL;
 } // LCOV_EXCL_STOP
 kv_map->list = kv_list;
 // remember the base methods and override them
 kv_list->map_methods = map->cl;
 map->cl = &cx_kv_map_class;
-if (list->climpl == NULL) {
+kv_list->list_methods = list->cl;
-kv_list->list_methods = list->cl;
+list->cl = &cx_kv_list_class;
-list->cl = &cx_kv_list_class;
-} else {
-kv_list->list_methods = list->climpl;
-list->climpl = &cx_kv_list_class;
-}
 return list;
 }
 CxMap *cxKvListCreateAsMap(
 const CxAllocator *allocator,
-cx_compare_func comparator,
 size_t elem_size
 ) {
-CxList *list = cxKvListCreate(allocator, comparator, elem_size);
+CxList *list = cxKvListCreate(allocator, elem_size);
 return list == NULL ? NULL : cxKvListAsMap(list);
 }
 CxList *cxKvListAsList(CxMap *map) {
 return &((struct cx_kv_list_map_s*)map)->list->list.base;
 if (existing != NULL) {
 // the key is already assigned to another node, we disallow re-assignment
 return 1;
 }
-// add the key to the map;
+// add the key to the map
-if (NULL == kv_list->map_methods->put(&kv_list->map->map_base.base, key, node_data)) {
+const CxMapEntry entry = kv_list->map_methods->put(
-return 1; // LCOV_EXCL_LINE
+&kv_list->map->map_base.base, key, node_data);
-}
+if (entry.key == NULL) return 1; // LCOV_EXCL_LINE
 // write the key to the list's node
 CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
-*loc_key = key;
+*loc_key = *entry.key;
 return 0;
 }
 int cxKvListRemoveKey(CxList *list, size_t index) {
 list->collection.sorted = false;
 cx_kv_list *kv_list = (cx_kv_list*)list;
 // reserve memory in the map
-void **map_data = kv_list->map_methods->put(&kv_list->map->map_base.base, key, NULL);
+CxMapEntry map_entry = kv_list->map_methods->put(&kv_list->map->map_base.base, key, NULL);
-if (map_data == NULL) return 1; // LCOV_EXCL_LINE
+if (map_entry.key == NULL) return 1; // LCOV_EXCL_LINE
 // insert the node
 void *node_data = kv_list->list_methods->insert_element(&kv_list->list.base, index,
 kv_list->list.base.collection.store_pointer ? &value : value);
 if (node_data == NULL) { // LCOV_EXCL_START
 // non-destructively remove the key again
-kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &map_data);
+void *dummy;
+kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &dummy);
 return 1;
 } // LCOV_EXCL_STOP
-*map_data = node_data;
+*(void**)map_entry.value = node_data;
 // write the key to the node
 CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
-*loc_key = key;
+*loc_key = *map_entry.key;
 return 0;
 }

comparison: ucx/kv_list.c

ucx/kv_list.c

Mercurial > hg > dav / file comparison

comparison: ucx/kv_list.c

ucx/kv_list.c