src/kv_list.c

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright 2025 Mike Becker, Olaf Wintermann All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   1. Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *
 *   2. Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * 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"

#include <string.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;
};

struct cx_kv_list_s {
    struct cx_linked_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;
    cx_destructor_func list_destr;
    cx_destructor_func2 list_destr2;
    void *list_destr_data;
    cx_destructor_func map_destr;
    cx_destructor_func2 map_destr2;
    void *map_destr_data;
};

static void cx_kv_list_destructor_wrapper_list(void *list_ptr, void *elem) {
    const cx_kv_list *kv_list = list_ptr;
    // list destructor is already called with proper deref of the elem
    if (kv_list->list_destr) {
        kv_list->list_destr(elem);
    }
    if (kv_list->list_destr2) {
        kv_list->list_destr2(kv_list->list_destr_data, elem);
    }
    if (kv_list->map_destr) {
        kv_list->map_destr(elem);
    }
    if (kv_list->map_destr2) {
        kv_list->map_destr2(kv_list->map_destr_data, elem);
    }
}

static void cx_kv_list_update_destructors(cx_kv_list *list) {
    // we copy the destructors to our custom fields and register
    // an own destructor function which invokes all these
    if (list->list.base.collection.simple_destructor != NULL) {
        list->list_destr = list->list.base.collection.simple_destructor;
        list->list.base.collection.simple_destructor = NULL;
    }
    if (list->list.base.collection.advanced_destructor != cx_kv_list_destructor_wrapper_list) {
        list->list_destr2 = list->list.base.collection.advanced_destructor;
        list->list_destr_data = list->list.base.collection.destructor_data;
        list->list.base.collection.advanced_destructor = cx_kv_list_destructor_wrapper_list;
        list->list.base.collection.destructor_data = list;
    }
    if (list->map->map_base.base.collection.simple_destructor != NULL) {
        list->map_destr = list->map->map_base.base.collection.simple_destructor;
        list->map->map_base.base.collection.simple_destructor = NULL;
    }
    if (list->map->map_base.base.collection.advanced_destructor != NULL) {
        list->map_destr2 = list->map->map_base.base.collection.advanced_destructor;
        list->map_destr_data = list->map->map_base.base.collection.destructor_data;
        list->map->map_base.base.collection.advanced_destructor = NULL;
        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);
}

static void cx_kvl_deallocate(struct cx_list_s *list) {
    cx_kv_list *kv_list = (cx_kv_list*)list;
    // patch the destructors
    cx_kv_list_update_destructors(kv_list);
    kv_list->map_methods->deallocate(&kv_list->map->map_base.base);
    // then free the list, now the destructors may be called
    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;
    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;
    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;
    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 = iter->src_handle.m;
    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;
    // patch the destructors
    // we also have to do that when targetbuf is NULL,
    // because we do not want wrong destructors to be called when we remove keys from the map
    cx_kv_list_update_destructors(kv_list);
    // iterate through the elements first and remove their keys from the map
    CxIterator iter = kv_list->list_methods->iterator(list, index, false);
    for (size_t i = 0; i < num && cxIteratorValid(iter); i++) {
        void *node_data = cxIteratorCurrent(iter);
        CxHashKey *key = cx_kv_list_loc_key(kv_list, node_data);
        // when the hash is zero, there is no key assigned to that element
        if (key->hash != 0) {
            kv_list->map_methods->remove(&kv_list->map->map_base.base, *key, NULL);
        }
        cxIteratorNext(iter);
    }
    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;
    // patch the destructors
    cx_kv_list_update_destructors(kv_list);
    // clear the list
    kv_list->list_methods->clear(list);
    // then clear the map
    kv_list->map_methods->clear(&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;
    cx_kv_list_update_destructors(kv_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 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 void cx_kvl_map_deallocate(struct cx_map_s *map) {
    cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->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 *kv_list = ((struct cx_kv_list_map_s*)map)->list;
    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) {
    cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
    // insert the data into the list first (assume that insertion 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) return NULL; // LCOV_EXCL_LINE
    // if the hash has not yet been computed, do it now
    if (key.hash == 0) {
        cx_hash_murmur(&key);
    }
    // copy the key to the node data
    CxHashKey *key_ptr = cx_kv_list_loc_key(kv_list, node_data);
    *key_ptr = key;
    // then insert the key into the map, referring to the node data
    return kv_list->map_methods->put(map, key, 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) {
    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;
    }
    // we cannot just call a list method (because we don't have the index)
    // and tbh. we also don't want to (because it's not performant when we
    // can have the node ptr directly instead)
    // therefore, we re-implement the logic ourselves

    // check if the outside caller want's us to return or to destroy the element
    if (targetbuf == NULL) {
        // patch the destructors and invoke them through the wrapper
        cx_kv_list_update_destructors(kv_list);
        cx_invoke_advanced_destructor(&kv_list->list.base, node_data);
    } else {
        // copy the element to the target buffer
        memcpy(targetbuf, node_data, kv_list->list.base.collection.elem_size);
    }

    // calculate the address of the node
    void *node_ptr = (char*)node_data - kv_list->list.loc_data;

    // unlink the node
    cx_linked_list_remove(
        &kv_list->list.begin,
        &kv_list->list.end,
        kv_list->list.loc_prev,
        kv_list->list.loc_next,
        node_ptr
    );

    // decrement the list's size
    kv_list->list.base.collection.size--;

    // deallocate the node
    cxFree(kv_list->list.base.collection.allocator, node_ptr);

    return 0;
}

CxMapIterator cx_kvl_map_iterator(const CxMap *map, enum cx_map_iterator_type type) {
    cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
    return kv_list->map_methods->iterator(map, type);
}

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,
    NULL,
    cx_kvl_reverse,
    cx_kvl_iterator,
};

static cx_map_class cx_kv_map_class = {
    cx_kvl_map_deallocate,
    cx_kvl_map_clear,
    cx_kvl_map_put,
    cx_kvl_map_get,
    cx_kvl_map_remove,
    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);
    if (list == NULL) return NULL; // LCOV_EXCL_LINE
    cx_linked_list *ll = (cx_linked_list*)list;
    ll->extra_data_len = sizeof(CxHashKey);
    CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
    if (map == NULL) { // LCOV_EXCL_START
        cxListFree(list);
        return NULL;
    } // LCOV_EXCL_STOP

    // patch the kv-list class with the compare function of the linked list
    // this allows cxListCompare() to optimize comparisons between linked lists and kv-list
    cx_kv_list_class.compare = list->cl->compare;

    // 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(struct cx_kv_list_s));

    // 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

    // zero the custom destructor information
    memset((char*)kv_list + offsetof(cx_kv_list, list_destr), 0, sizeof(void*)*6);

    // 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->map_methods = map->cl;
    map->cl = &cx_kv_map_class;
    if (list->climpl == NULL) {
        kv_list->list_methods = list->cl;
        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);
    return list == NULL ? NULL : cxKvListAsMap(list);
}

CxList *cxKvListAsList(CxMap *map) {
    return &((struct cx_kv_list_map_s*)map)->list->list.base;
}

CxMap *cxKvListAsMap(CxList *list) {
    return &((cx_kv_list*)list)->map->map_base.base;
}

int cx_kv_list_set_key(CxList *list, size_t index, CxHashKey key) {
    cx_kv_list *kv_list = (cx_kv_list*)list;
    void *node_data = kv_list->list_methods->at(list, index);
    if (node_data == NULL) {
        return 1;
    }
    // if the hash has not yet been computed, do it now
    if (key.hash == 0) {
        cx_hash_murmur(&key);
    }
    CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
    *loc_key = key;

    // TODO: what happens when we are _replacing_ an existing key?
    kv_list->map_methods->put(&kv_list->map->map_base.base, key, node_data);
    // TODO: what happens if the map cocks up and returns NULL?

    return 0;
}

int cx_kv_list_remove_key(CxList *list, size_t index, CxHashKey key) {
    return -1;
}

int cx_kv_list_insert(CxList *list, size_t index, CxHashKey key, void *value) {
    return -1;
}