Mercurial > hg > webserver / changeset

--- a/src/server/test/main.c	Sun Nov 20 11:39:46 2022 +0100
+++ b/src/server/test/main.c	Sun Nov 20 12:19:09 2022 +0100
@@ -79,7 +79,6 @@
     ucx_test_register(suite, test_util_uri_escape_kanji);
     
     // object tests
-    /*
     ucx_test_register(suite, test_expr_parse_expr_value);
     ucx_test_register(suite, test_expr_parse_expr_neg_value);
     ucx_test_register(suite, test_expr_parse_expr_value_str);
@@ -91,8 +90,7 @@
     ucx_test_register(suite, test_expr_parse_expr_compare2value_expr);
     ucx_test_register(suite, test_expr_parse_expr_compare2expr_value);
     ucx_test_register(suite, test_expr_parse_expr_bracket);
-    */
-    //ucx_test_register(suite, test_expr_parse_expr_func_arg0);
+    ucx_test_register(suite, test_expr_parse_expr_func_arg0);
     ucx_test_register(suite, test_expr_parse_expr_func_arg1);
     ucx_test_register(suite, test_expr_parse_expr_func_arg3);
     ucx_test_register(suite, test_expr_parse_expr_func_expr1);

--- a/src/ucx/Makefile	Sun Nov 20 11:39:46 2022 +0100
+++ b/src/ucx/Makefile	Sun Nov 20 12:19:09 2022 +0100
@@ -37,6 +37,7 @@
 SRC += hash_key.c
 SRC += hash_map.c
 SRC += linked_list.c
+SRC += array_list.c
 SRC += list.c
 SRC += string.c
 SRC += tree.c

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/ucx/array_list.c	Sun Nov 20 12:19:09 2022 +0100
@@ -0,0 +1,342 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
+ *
+ * Copyright 2021 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/array_list.h"
+#include <assert.h>
+#include <string.h>
+#include <stdint.h>
+
+/* LOW LEVEL ARRAY LIST FUNCTIONS */
+
+enum cx_array_copy_result cx_array_copy(
+        void **target,
+        size_t *size,
+        size_t *capacity,
+        size_t index,
+        void const *src,
+        size_t elem_size,
+        size_t elem_count,
+        struct cx_array_reallocator_s *reallocator
+) {
+    /* assert pointers */
+    assert(target != NULL);
+    assert(size != NULL);
+    assert(src != NULL);
+
+    /* determine capacity */
+    size_t cap = capacity == NULL ? *size : *capacity;
+
+    /* check if resize is required */
+    size_t newsize = index + elem_count;
+    bool needrealloc = newsize > cap;
+
+    /* reallocate if possible */
+    if (needrealloc) {
+        /* a reallocator and a capacity variable must be available */
+        if (reallocator == NULL || capacity == NULL) {
+            return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED;
+        }
+
+        /* check, if we need to repair the src pointer */
+        uintptr_t targetaddr = (uintptr_t) *target;
+        uintptr_t srcaddr = (uintptr_t) src;
+        bool repairsrc = targetaddr <= srcaddr
+                         && srcaddr < targetaddr + cap * elem_size;
+
+        /* increase capacity linearly */
+        cap += 16;
+
+        /* perform reallocation */
+        void *newmem = reallocator->realloc(
+                *target, cap, elem_size, reallocator
+        );
+        if (newmem == NULL) {
+            return CX_ARRAY_COPY_REALLOC_FAILED;
+        }
+
+        /* repair src pointer, if necessary */
+        if (repairsrc) {
+            src = ((char *) newmem) + (srcaddr - targetaddr);
+        }
+
+        /* store new pointer and capacity */
+        *target = newmem;
+        *capacity = cap;
+    }
+
+    /* determine target pointer */
+    char *start = *target;
+    start += index * elem_size;
+
+    /* copy elements and set new size */
+    memmove(start, src, elem_count * elem_size);
+    *size = newsize;
+
+    /* return successfully */
+    return CX_ARRAY_COPY_SUCCESS;
+}
+
+/* HIGH LEVEL ARRAY LIST FUNCTIONS */
+
+typedef struct {
+    struct cx_list_s base;
+    void *data;
+    struct cx_array_reallocator_s reallocator;
+} cx_array_list;
+
+static void *cx_arl_realloc(
+        void *array,
+        size_t capacity,
+        size_t elem_size,
+        struct cx_array_reallocator_s *alloc
+) {
+    /* retrieve the pointer to the list allocator */
+    CxAllocator const *al = alloc->ptr1;
+
+    /* use the list allocator to reallocate the memory */
+    return cxRealloc(al, array, capacity * elem_size);
+}
+
+static void cx_arl_destructor(struct cx_list_s *list) {
+    cx_array_list *arl = (cx_array_list *) list;
+    cxFree(list->allocator, arl->data);
+}
+
+static int cx_arl_add(
+        struct cx_list_s *list,
+        void const *elem
+) {
+    cx_array_list *arl = (cx_array_list *) list;
+    return cx_array_copy(
+            &arl->data,
+            &list->size,
+            &list->capacity,
+            list->size,
+            elem,
+            list->itemsize,
+            1,
+            &arl->reallocator
+    );
+}
+
+static int cx_arl_insert(
+        struct cx_list_s *list,
+        size_t index,
+        void const *elem
+) {
+    if (index > list->size) {
+        return 1;
+    } else if (index == list->size) {
+        return cx_arl_add(list, elem);
+    } else {
+        cx_array_list *arl = (cx_array_list *) list;
+
+        /* move elements starting at index to the right */
+        if (cx_array_copy(
+                &arl->data,
+                &list->size,
+                &list->capacity,
+                index + 1,
+                ((char *) arl->data) + index * list->itemsize,
+                list->itemsize,
+                list->size - index,
+                &arl->reallocator
+        )) {
+            return 1;
+        }
+
+        /* place the element */
+        memcpy(((char *) arl->data) + index * list->itemsize,
+               elem, list->itemsize);
+
+        return 0;
+    }
+}
+
+static int cx_arl_insert_iter(
+        struct cx_iterator_s *iter,
+        void const *elem,
+        int prepend
+) {
+    return 1;
+}
+
+static int cx_arl_remove(
+        struct cx_list_s *list,
+        size_t index
+) {
+    /* out-of-bounds check */
+    if (index >= list->size) {
+        return 1;
+    }
+
+    cx_array_list *arl = (cx_array_list *) list;
+
+    /* just move the elements starting at index to the left */
+    int result = cx_array_copy(
+            &arl->data,
+            &list->size,
+            &list->capacity,
+            index,
+            ((char *) arl->data) + (index + 1) * list->itemsize,
+            list->itemsize,
+            list->size - index,
+            &arl->reallocator
+    );
+    if (result == 0) {
+        /* decrease the size */
+        list->size--;
+    }
+    return result;
+}
+
+static void *cx_arl_at(
+        struct cx_list_s const *list,
+        size_t index
+) {
+    if (index < list->size) {
+        cx_array_list const *arl = (cx_array_list const *) list;
+        char *space = arl->data;
+        return space + index * list->itemsize;
+    } else {
+        return NULL;
+    }
+}
+
+static size_t cx_arl_find(
+        struct cx_list_s const *list,
+        void const *elem
+) {
+    char *cur = ((cx_array_list const *) list)->data;
+
+    for (size_t i = 0; i < list->size; i++) {
+        if (0 == list->cmpfunc(elem, cur)) {
+            return i;
+        }
+        cur += list->itemsize;
+    }
+
+    return list->size;
+}
+
+static void cx_arl_sort(struct cx_list_s *list) {
+    qsort(((cx_array_list *) list)->data,
+          list->size,
+          list->itemsize,
+          list->cmpfunc
+    );
+}
+
+static int cx_arl_compare(
+        struct cx_list_s const *list,
+        struct cx_list_s const *other
+) {
+
+}
+
+static void cx_arl_reverse(struct cx_list_s *list) {
+
+}
+
+static bool cx_arl_iter_valid(struct cx_iterator_s const *iter) {
+    struct cx_list_s const *list = iter->src_handle;
+    return iter->index < list->size;
+}
+
+static void *cx_arl_iter_current(struct cx_iterator_s const *iter) {
+    return iter->elem_handle;
+}
+
+static void cx_arl_iter_next(struct cx_iterator_s *iter) {
+    if (iter->remove) {
+        iter->remove = false;
+        cx_arl_remove(iter->src_handle, iter->index);
+    } else {
+        iter->index++;
+        iter->elem_handle = cx_arl_at(iter->src_handle, iter->index);
+    }
+}
+
+static struct cx_iterator_s cx_arl_iterator(
+        struct cx_list_s *list,
+        size_t index
+) {
+    struct cx_iterator_s iter;
+
+    iter.index = index;
+    iter.src_handle = list;
+    iter.elem_handle = cx_arl_at(list, index);
+    iter.valid = cx_arl_iter_valid;
+    iter.current = cx_arl_iter_current;
+    iter.next = cx_arl_iter_next;
+    iter.remove = false;
+
+    return iter;
+}
+
+static cx_list_class cx_array_list_class = {
+        cx_arl_destructor,
+        cx_arl_add,
+        cx_arl_insert,
+        cx_arl_insert_iter,
+        cx_arl_remove,
+        cx_arl_at,
+        cx_arl_find,
+        cx_arl_sort,
+        cx_arl_compare,
+        cx_arl_reverse,
+        cx_arl_iterator,
+};
+
+CxList *cxArrayListCreate(
+        CxAllocator const *allocator,
+        CxListComparator comparator,
+        size_t item_size,
+        size_t initial_capacity
+) {
+    cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
+    if (list == NULL) return NULL;
+
+    list->data = cxCalloc(allocator, initial_capacity, item_size);
+    if (list->data == NULL) {
+        cxFree(allocator, list);
+        return NULL;
+    }
+
+    list->base.cl = &cx_array_list_class;
+    list->base.allocator = allocator;
+    list->base.cmpfunc = comparator;
+    list->base.itemsize = item_size;
+    list->base.capacity = initial_capacity;
+
+    /* configure the reallocator */
+    list->reallocator.realloc = cx_arl_realloc;
+    list->reallocator.ptr1 = (void *) allocator;
+
+    return (CxList *) list;
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/ucx/cx/array_list.h	Sun Nov 20 12:19:09 2022 +0100
@@ -0,0 +1,156 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
+ *
+ * Copyright 2021 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 array_list.h
+ * \brief Array list implementation.
+ * \details Also provides several low-level functions for custom array list implementations.
+ * \author Mike Becker
+ * \author Olaf Wintermann
+ * \version 3.0
+ * \copyright 2-Clause BSD License
+ */
+
+
+#ifndef UCX_ARRAY_LIST_H
+#define UCX_ARRAY_LIST_H
+
+#include "list.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * Defines a reallocation mechanism for arrays.
+ */
+struct cx_array_reallocator_s {
+    /**
+     * Re-allocates space for the given array.
+     *
+     * Implementations are not required to free the original array.
+     * This allows re-allocation of static memory by allocating heap memory
+     * and copying the array contents. The information in \p data can keep
+     * track of the state of the memory or other additional allocator info.
+     *
+     * @param array the array to reallocate
+     * @param capacity the new capacity (number of elements)
+     * @param elem_size the size of each element
+     * @param alloc a reference to this allocator
+     * @return a pointer to the reallocated memory or \c NULL on failure
+     */
+    void *(*realloc)(
+            void *array,
+            size_t capacity,
+            size_t elem_size,
+            struct cx_array_reallocator_s *alloc
+    );
+
+    /**
+     * Custom data pointer.
+     */
+    void *ptr1;
+    /**
+     * Custom data pointer.
+     */
+    void *ptr2;
+    /**
+     * Custom data integer.
+     */
+    size_t int1;
+    /**
+     * Custom data integer.
+     */
+    size_t int2;
+};
+
+/**
+ * Return codes for cx_array_copy().
+ */
+enum cx_array_copy_result {
+    CX_ARRAY_COPY_SUCCESS,
+    CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED,
+    CX_ARRAY_COPY_REALLOC_FAILED,
+};
+
+/**
+ * Copies elements from one array to another.
+ *
+ * The elements are copied to the \p target array at the specified \p index,
+ * overwriting possible elements. The index must be in range of the current
+ * array \p size. If the number of elements added would extend the array's size,
+ * and \p capacity is not \c NULL, the remaining capacity is used.
+ *
+ * If the capacity is insufficient to hold the new data, a reallocation
+ * attempt is made, unless the allocator is set to \c NULL, in which case
+ * this function ultimately returns a failure.
+ *
+ * @param target the target array
+ * @param size a pointer to the size of the target array
+ * @param capacity a pointer to the target array's capacity -
+ * \c NULL if only the size shall be used to bound the array
+ * @param index the index where the copied elements shall be placed
+ * @param src the source array
+ * @param elem_size the size of one element
+ * @param elem_count the number of elements to copy
+ * @param reallocator the array re-allocator to use, or \c NULL
+ * if re-allocation shall not happen
+ * @return zero on success, non-zero error code on failure
+ */
+enum cx_array_copy_result cx_array_copy(
+        void **target,
+        size_t *size,
+        size_t *capacity,
+        size_t index,
+        void const *src,
+        size_t elem_size,
+        size_t elem_count,
+        struct cx_array_reallocator_s *reallocator
+) __attribute__((__nonnull__(1, 2, 5)));
+
+/**
+ * Allocates an array list for storing elements with \p item_size bytes each.
+ *
+ * @param allocator the allocator for allocating the list memory
+ * @param comparator the comparator for the elements
+ * @param item_size the size of each element in bytes
+ * @param initial_capacity the initial number of elements the array can store
+ * @return the created list
+ */
+CxList *cxArrayListCreate(
+        CxAllocator const *allocator,
+        CxListComparator comparator,
+        size_t item_size,
+        size_t initial_capacity
+) __attribute__((__nonnull__));
+
+
+#ifdef __cplusplus
+} /* extern "C" */
+#endif
+
+#endif /* UCX_ARRAY_LIST_H */