Mercurial > hg > ucx / file revision

/*
 * 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.
 */
/**
 * @file kv_list.h
 * @brief Linked list implementation with key/value-lookup.
 * @author Mike Becker
 * @author Olaf Wintermann
 * @copyright 2-Clause BSD License
 */

#ifndef UCX_KV_LIST_H
#define UCX_KV_LIST_H

#include "common.h"
#include "list.h"
#include "map.h"

#ifdef __cplusplus
extern "C" {
#endif

/**
 * Allocates a linked list with a lookup-map for storing elements with @p elem_size bytes each.
 *
 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
 * copies of the added elements, and the compare function will be automatically set
 * to cx_cmp_ptr() if none is given.
 *
 * After creating the list, it can also be used as a map after converting the pointer
 * to a CxMap pointer with cxKvListAsMap().
 * When you want to use the list interface again, you can also convert the map pointer back
 * with cxKvListAsList().
 *
 * @param allocator the allocator for allocating the list nodes
 * (if @c NULL, the cxDefaultAllocator will be used)
 * @param comparator the comparator for the elements
 * (if @c NULL, and the list is not storing pointers, sort and find
 * functions will not work)
 * @param elem_size the size of each element in bytes
 * @return the created list
 * @see cxKvListAsMap()
 * @see cxKvListAsList()
 */
cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxListFree, 1)
CX_EXPORT CxList *cxKvListCreate(const CxAllocator *allocator,
        cx_compare_func comparator, size_t elem_size);

/**
 * Allocates a linked list with a lookup-map for storing elements with @p elem_size bytes each.
 *
 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
 * copies of the added elements, and the compare function will be automatically set
 * to cx_cmp_ptr() if none is given.
 *
 * This function creates the list with cxKvListCreate() and immediately applies
 * cxKvListAsMap(). If you want to use the returned object as a list, you can call
 * cxKvListAsList() later.
 *
 * @param allocator the allocator for allocating the list nodes
 * (if @c NULL, the cxDefaultAllocator will be used)
 * @param comparator the comparator for the elements
 * (if @c NULL, and the list is not storing pointers, sort and find
 * functions will not work)
 * @param elem_size the size of each element in bytes
 * @return the created list wrapped into the CxMap interface
 * @see cxKvListAsMap()
 * @see cxKvListAsList()
 */
cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxMapFree, 1)
CX_EXPORT CxMap *cxKvListCreateAsMap(const CxAllocator *allocator,
        cx_compare_func comparator, size_t elem_size);

/**
 * Allocates a linked list with a lookup-map for storing elements with @p elem_size bytes each.
 *
 * The list will use cxDefaultAllocator and no comparator function. If you want
 * to call functions that need a comparator, you must either set one immediately
 * after list creation or use cxKvListCreate().
 *
 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
 * copies of the added elements, and the compare function will be automatically set
 * to cx_cmp_ptr().
 *
 * After creating the list, it can also be used as a map after converting the pointer
 * to a CxMap pointer with cxKvListAsMap().
 * When you want to use the list interface again, you can also convert the map pointer back
 * with cxKvListAsList().
 *
 * @param elem_size (@c size_t) the size of each element in bytes
 * @return (@c CxList*) the created list
 * @see cxKvListAsMap()
 * @see cxKvListAsList()
 */
#define cxKvListCreateSimple(elem_size) cxKvListCreate(NULL, NULL, elem_size)

/**
 * Allocates a linked list with a lookup-map for storing elements with @p elem_size bytes each.
 *
 * The list will use cxDefaultAllocator and no comparator function. If you want
 * to call functions that need a comparator, you must either set one immediately
 * after list creation or use cxKvListCreate().
 *
 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
 * copies of the added elements, and the compare function will be automatically set
 * to cx_cmp_ptr().
 *
 * This macro behaves as if the list was created with cxKvListCreateSimple() and
 * immediately followed up by cxKvListAsMap().
 * If you want to use the returned object as a list, you can call cxKvListAsList() later.
 *
 * @param elem_size (@c size_t) the size of each element in bytes
 * @return (@c CxMap*) the created list wrapped into the CxMap interface
 * @see cxKvListAsMap()
 * @see cxKvListAsList()
 */
#define cxKvListCreateAsMapSimple(elem_size) cxKvListCreateAsMap(NULL, NULL, elem_size)

/**
 * Converts a map pointer belonging to a key-value-List back to the original list pointer.
 *
 * @param map a map pointer that was returned by a call to cxKvListAsMap()
 * @return the original list pointer
 */
cx_attr_nodiscard cx_attr_nonnull cx_attr_returns_nonnull
CX_EXPORT CxList *cxKvListAsList(CxMap *map);

/**
 * Converts a map pointer belonging to a key-value-List back to the original list pointer.
 *
 * @param list a list created by cxKvListCreate() or cxKvListCreateSimple()
 * @return a map pointer that lets you use the list as if it was a map
 */
cx_attr_nodiscard cx_attr_nonnull cx_attr_returns_nonnull
CX_EXPORT CxMap *cxKvListAsMap(CxList *list);

/**
 * Sets or updates the key of a list item.
 *
 * This is, for example, useful when you have inserted an element using the CxList interface,
 * and now you want to associate this element with a key.
 *
 * @param list the list
 * @param index the index of the element in the list
 * @param key the key
 * @retval zero success
 * @retval non-zero memory allocation failure or the index is out of bounds
 * @see cxKvListSetKey()
 */
cx_attr_nonnull
CX_EXPORT int cx_kv_list_set_key(CxList *list, size_t index, CxHashKey key);

/**
 * Inserts an item into the list at the specified index and associates it with the specified key.
 *
 * @param list the list
 * @param index the index the inserted element shall have
 * @param key the key
 * @param value the value
 * @retval zero success
 * @retval non-zero memory allocation failure or the index is out of bounds
 * @see cxKvListInsert()
 */
cx_attr_nonnull
CX_EXPORT int cx_kv_list_insert(CxList *list, size_t index, CxHashKey key, void *value);

/**
 * Sets or updates the key of a list item.
 *
 * This is, for example, useful when you have inserted an element using the CxList interface,
 * and now you want to associate this element with a key.
 *
 * @param list (@c CxList*) the list
 * @param index (@c size_t) the index of the element in the list
 * @param key (any supported key type) the key
 * @retval zero success
 * @retval non-zero memory allocation failure or the index is out of bounds
 * @see CX_HASH_KEY()
 */
#define cxKvListSetKey(list, index, key) cx_kv_list_set_key(list, index, CX_HASH_KEY(key))

/**
 * Inserts an item into the list at the specified index and associates it with the specified key.
 *
 * @param list (@c CxList*) the list
 * @param index (@c size_t) the index the inserted element shall have
 * @param key (any supported key type) the key
 * @param value (@c void*) the value
 * @retval zero success
 * @retval non-zero memory allocation failure or the index is out of bounds
 * @see CX_HASH_KEY()
 */
#define cxKvListInsert(list, index, key, value) cx_kv_list_insert(list, index, CX_HASH_KEY(key), value)


/**
 * Removes the key of a list item.
 *
 * This can be useful if you want to explicitly remove an item from the lookup map.
 *
 * If no key is associated with the item, nothing happens, and this function returns zero.
 *
 * @param list the list
 * @param index the index of the element in the list
 * @retval zero success
 * @retval non-zero the index is out of bounds
 */
cx_attr_nonnull
CX_EXPORT int cxKvListRemoveKey(CxList *list, size_t index);

/**
 * Returns the key of a list item.
 *
 * @param list the list
 * @param index the index of the element in the list
 * @return a pointer to the key or @c NULL when the index is out of bounds or the item does not have a key
 */
cx_attr_nonnull
CX_EXPORT const CxHashKey *cxKvListGetKey(CxList *list, size_t index);

/**
 * Adds an item into the list and associates it with the specified key.
 *
 * @param list (@c CxList*) the list
 * @param key (@c CxHashKey, @c char*, @c cxstring, or @c cxmutstr) the key
 * @param value (@c void*) the value
 * @retval zero success
 * @retval non-zero memory allocation failure
 */
#define cxKvListAdd(list, key, value) cxKvListInsert(list, (list)->collection.size, key, value)

#ifdef __cplusplus
} // extern "C"
#endif

#endif // UCX_KV_LIST_H