ucx: comparison src/kv

-:b1696d0d598b
+:189756516eaa
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */
 #include "cx/kv_list.h"
+#include "cx/hash_map.h"
+#include "cx/linked_list.h"
+typedef struct cx_kv_list_s cx_kv_list;
+struct cx_kv_list_map_s {
+struct cx_hash_map_s map_base;
+/** Back-reference to the list. */
+cx_kv_list *list;
+};
+/** The list aspect (must have the same layout as the normal linked list). */
+struct cx_kv_list_list_s {
+struct cx_list_s list_base;
+void *begin;
+void *end;
+};
+struct cx_kv_list_s {
+struct cx_kv_list_list_s list;
+/** The lookup map - stores pointers to the nodes. */
+struct cx_kv_list_map_s *map;
+const cx_list_class *list_methods;
+const cx_map_class *map_methods;
+};
+static void cx_kvl_deallocate(struct cx_list_s *list) {
+cx_kv_list *kv_list = (cx_kv_list*)list;
+// free the map first
+kv_list->map_methods->deallocate(&kv_list->map->map_base.base);
+kv_list->list_methods->deallocate(list);
+}
+static void *cx_kvl_insert_element(
+struct cx_list_s *list,
+size_t index,
+const void *data
+) {
+cx_kv_list *kv_list = (cx_kv_list*)list;
+// TODO: trick the base method by adding the required space for the key to the elem_size
+return kv_list->list_methods->insert_element(list, index, data);
+}
+static size_t cx_kvl_insert_array(
+struct cx_list_s *list,
+size_t index,
+const void *data,
+size_t n
+) {
+cx_kv_list *kv_list = (cx_kv_list*)list;
+// TODO: trick the base method by adding the required space for the key to the elem_size
+return kv_list->list_methods->insert_array(list, index, data, n);
+}
+static size_t cx_kvl_insert_sorted(
+struct cx_list_s *list,
+const void *sorted_data,
+size_t n
+) {
+cx_kv_list *kv_list = (cx_kv_list*)list;
+// TODO: trick the base method by adding the required space for the key to the elem_size
+return kv_list->list_methods->insert_sorted(list, sorted_data, n);
+}
+static int cx_kvl_insert_iter(
+struct cx_iterator_s *iter,
+const void *elem,
+int prepend
+) {
+cx_kv_list *kv_list = (cx_kv_list*)iter->src_handle.m;
+// TODO: trick the base method by adding the required space for the key to the elem_size
+return kv_list->list_methods->insert_iter(iter, elem, prepend);
+}
+static size_t cx_kvl_remove(
+struct cx_list_s *list,
+size_t index,
+size_t num,
+void *targetbuf
+) {
+cx_kv_list *kv_list = (cx_kv_list*)list;
+// TODO: always use the target buffer to get the element first,
+//       then obtain the key, remove it from the map,
+//       and finally call any destructors manually
+return kv_list->list_methods->remove(list, index, num, targetbuf);
+}
+static void cx_kvl_clear(struct cx_list_s *list) {
+cx_kv_list *kv_list = (cx_kv_list*)list;
+kv_list->list_methods->clear(list);
+// also clear all lookup entries
+cxMapClear(&kv_list->map->map_base.base);
+}
+static int cx_kvl_swap(
+struct cx_list_s *list,
+size_t i,
+size_t j
+) {
+cx_kv_list *kv_list = (cx_kv_list*)list;
+return kv_list->list_methods->swap(list, i, j);
+}
+static void *cx_kvl_at(
+const struct cx_list_s *list,
+size_t index
+) {
+const cx_kv_list *kv_list = (const cx_kv_list*)list;
+return kv_list->list_methods->at(list, index);
+}
+static size_t cx_kvl_find_remove(
+struct cx_list_s *list,
+const void *elem,
+bool remove
+) {
+cx_kv_list *kv_list = (cx_kv_list*)list;
+// TODO: implement removal of the key in the map
+return kv_list->list_methods->find_remove(list, elem, remove);
+}
+static void cx_kvl_sort(struct cx_list_s *list) {
+cx_kv_list *kv_list = (cx_kv_list*)list;
+kv_list->list_methods->sort(list);
+}
+static int cx_kvl_compare(
+const struct cx_list_s *list,
+const struct cx_list_s *other
+) {
+// TODO: make it so that comparison with normal linked lists is also optimized
+const cx_kv_list *kv_list = (const cx_kv_list*)list;
+return kv_list->list_methods->compare(list, other);
+}
+static void cx_kvl_reverse(struct cx_list_s *list) {
+cx_kv_list *kv_list = (cx_kv_list*)list;
+kv_list->list_methods->reverse(list);
+}
+static struct cx_iterator_s cx_kvl_iterator(
+const struct cx_list_s *list,
+size_t index,
+bool backward
+) {
+const cx_kv_list *kv_list = (const cx_kv_list*)list;
+// TODO: cannot really forward, because mutating iterators must be able to remove the element
+return kv_list->list_methods->iterator(list, index, backward);
+}
+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_insert_iter,
+cx_kvl_remove,
+cx_kvl_clear,
+cx_kvl_swap,
+cx_kvl_at,
+cx_kvl_find_remove,
+cx_kvl_sort,
+cx_kvl_compare,
+cx_kvl_reverse,
+cx_kvl_iterator,
+};
 CxList *cxKvListCreate(
 const CxAllocator *allocator,
 cx_compare_func comparator,
 size_t elem_size
 ) {
-return NULL;
+if (allocator == NULL) {
+allocator = cxDefaultAllocator;
+}
+// create a normal linked list and a normal hash map, first
+CxList *list = cxLinkedListCreate(allocator, comparator, elem_size);
+if (list == NULL) return NULL; // LCOV_EXCL_LINE
+CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
+if (map == NULL) { // LCOV_EXCL_START
+cxListFree(list);
+return NULL;
+} // LCOV_EXCL_STOP
+// reallocate the map to add memory for the list back-reference
+struct cx_kv_list_map_s *kv_map = cxRealloc(allocator, map, sizeof(struct cx_kv_list_map_s));
+// reallocate the list to add memory for storing the metadata
+cx_kv_list *kv_list = cxRealloc(allocator, list, sizeof(cx_kv_list));
+// if any of the reallocations failed, we bail out
+if (kv_map != NULL && kv_list != NULL) {
+map = (CxMap*) kv_map;
+list = (CxList*) kv_list;
+} else { // LCOV_EXCL_START
+cxListFree(list);
+cxMapFree(map);
+return NULL;
+} // LCOV_EXCL_STOP
+// combine the list and the map aspect
+kv_list->map = kv_map;
+kv_map->list = kv_list;
+// remember the base methods and override them
+kv_list->list_methods = list->cl;
+kv_list->map_methods = map->cl;
+list->cl = &cx_kv_list_class;
+// TODO: override all map members
+//       and remember to set the sorted flag of the list to false in the put/emplace methods!
+return list;
 }
 CxMap *cxKvListCreateAsMap(
 const CxAllocator *allocator,
 cx_compare_func comparator,
 CxList *list = cxKvListCreate(allocator, comparator, elem_size);
 return list == NULL ? NULL : cxKvListAsMap(list);
 }
 CxList *cxKvListAsList(CxMap *map) {
-return NULL;
+return &((struct cx_kv_list_map_s*)map)->list->list.list_base;
 }
 CxMap *cxKvListAsMap(CxList *list) {
-return NULL;
+return &((cx_kv_list*)list)->map->map_base.base;
 }
 int cx_kv_list_set_key(CxList *list, size_t index, CxHashKey key) {
 return -1;
 }

comparison: src/kv_list.c

src/kv_list.c

Mercurial > hg > ucx / file comparison

comparison: src/kv_list.c

src/kv_list.c