Mercurial > hg > ucx / changeset

--- a/.hgignore	Sun Feb 07 18:08:21 2021 +0100
+++ b/.hgignore	Sun Feb 07 19:42:12 2021 +0100
@@ -1,32 +1,9 @@
 syntax:regexp
 ^nbproject/
 ^build/
-^.settings/
-^.project
-^.cproject
-^.autotools
 /core$
 DS_Store$
-^docs/web/
-^docs/man/
-\.o$
-\.lo$
-\.la$
-^autom4te\.cache/
-^build-aux/
-^m4/
-^aclocal.m4$
-^config\.
-^configure$
-^libtool$
-^src/.*Makefile$
-^test/.*Makefile$
-^Makefile$
-Makefile\.in$
-/\.deps/
-/\.libs/
 ^stamp-h
-test/test_list.c
 /test-suite.log$
 ^ucx-.*\.tar.gz$
 ^.idea/

--- a/src/CMakeLists.txt	Sun Feb 07 18:08:21 2021 +0100
+++ b/src/CMakeLists.txt	Sun Feb 07 19:42:12 2021 +0100
@@ -1,10 +1,12 @@
 set(sources
         allocator.c
         list.c
+        linked_list.c
 )
 set(headers
         cx/allocator.h
         cx/list.h
+        cx/linked_list.h
 )
 
 add_library(ucx SHARED ${sources})

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/cx/linked_list.h	Sun Feb 07 19:42:12 2021 +0100
@@ -0,0 +1,42 @@
+/*
+ * 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.
+ */
+
+#ifndef UCX_LINKED_LIST_H
+#define UCX_LINKED_LIST_H
+
+#include "list.h"
+
+void *cx_linked_list_last(void **begin, void **end, off_t loc_next);
+
+int cx_linked_list_add(void **begin, void **end, off_t loc_next, off_t loc_prev, void *newnode);
+
+CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator);
+
+extern cx_list_class cx_linked_list_class;
+
+#endif /* UCX_LINKED_LIST_H */

--- a/src/cx/list.h	Sun Feb 07 18:08:21 2021 +0100
+++ b/src/cx/list.h	Sun Feb 07 19:42:12 2021 +0100
@@ -29,4 +29,50 @@
 #ifndef UCX_LIST_H
 #define UCX_LIST_H
 
+#include <stdlib.h>
+#include "allocator.h"
+
+typedef int(*CxListComparator)(void *left, void *right);
+
+typedef struct {
+    CxAllocator allocator;
+    CxListComparator cmpfunc;
+    void *listdata;
+} cx_list;
+
+typedef int (*cx_list_add)(cx_list *list, void *elem);
+
+typedef int (*cx_list_insert)(cx_list *list, size_t index, void *elem);
+
+typedef void *(*cx_list_remove)(cx_list *list, size_t index);
+
+typedef size_t (*cx_list_find)(cx_list *list, void *elem);
+
+typedef size_t (*cx_list_size)(cx_list *list);
+
+typedef struct {
+    cx_list_add add;
+    cx_list_insert insert;
+    cx_list_remove remove;
+    cx_list_find find;
+    cx_list_size size;
+} cx_list_class;
+
+struct cx_list_s {
+    cx_list_class *cl;
+    cx_list data;
+};
+
+typedef struct cx_list_s *CxList;
+
+int cxListAdd(CxList list, void *elem);
+
+int cxListInsert(CxList list, size_t index, void *elem);
+
+void *cxListRemove(CxList list, size_t index);
+
+size_t cxListFind(CxList list, void *elem);
+
+size_t cxListSize(CxList list);
+
 #endif /* UCX_LIST_H */

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/linked_list.c	Sun Feb 07 19:42:12 2021 +0100
@@ -0,0 +1,162 @@
+/*
+ * 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/linked_list.h"
+#include <stddef.h>
+
+/* LOW LEVEL LINKED LIST FUNCTIONS */
+
+#define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off))
+
+void *cx_linked_list_last(void **begin, void **end, off_t loc_next) {
+    if (end != NULL) {
+        return *end;
+    } else {
+        if (begin == NULL || *begin == NULL)
+            return NULL;
+
+        void *cur = *begin;
+        void *last;
+        do {
+            last = cur;
+        } while ((cur = *CX_LL_PTR(cur, loc_next)) != NULL);
+
+        return last;
+    }
+}
+
+int cx_linked_list_add(void **begin, void **end, off_t loc_next, off_t loc_prev, void *newnode) {
+    // TODO: how do we report error messages?
+    if (loc_next < 0 || (begin == NULL && end == NULL)) {
+        return 1;
+    }
+
+    void *last = cx_linked_list_last(begin, end, loc_next);
+    if (last == NULL) {
+        if (begin == NULL) {
+            return 1;
+        } else {
+            *begin = newnode;
+            return 0;
+        }
+    }
+
+    void **next = CX_LL_PTR(last, loc_next);
+    *next = newnode;
+    if (loc_prev >= 0) {
+        void **prev = CX_LL_PTR(newnode, loc_prev);
+        *prev = last;
+    }
+
+    return 0;
+}
+
+/* HIGH LEVEL LINKED LIST IMPLEMENTATION */
+
+typedef struct cx_list_node_s cx_list_node;
+
+struct cx_list_node_s {
+    cx_list_node *next;
+    cx_list_node *prev;
+    void *data;
+};
+
+typedef struct {
+    cx_list_node *begin;
+    cx_list_node *end;
+    size_t size;
+} cx_linked_list;
+
+int cx_ll_add(cx_list *list, void *elem) {
+    cx_linked_list *listdata = list->listdata;
+    CxAllocator allocator = list->allocator;
+
+    struct cx_list_node_s *node = cxMalloc(allocator, sizeof(struct cx_list_node_s));
+    if (node == NULL)
+        return 1;
+
+    int ret = cx_linked_list_add(
+            (void **) &listdata->begin,
+            (void **) &listdata->end,
+            offsetof(struct cx_list_node_s, next),
+            offsetof(struct cx_list_node_s, prev),
+            node
+    );
+    if (ret == 0) {
+        listdata->size++;
+        return 0;
+    } else {
+        return ret;
+    }
+}
+
+int cx_ll_insert(cx_list *list, size_t index, void *elem) {
+    cx_linked_list *listdata = list->listdata;
+    // TODO: implement using low level API
+    return 1;
+}
+
+void *cx_ll_remove(cx_list *list, size_t index) {
+    cx_linked_list *listdata = list->listdata;
+    // TODO: implement using low level API
+    return NULL;
+}
+
+size_t cx_ll_find(cx_list *list, void *elem) {
+    cx_linked_list *listdata = list->listdata;
+    // TODO: implement using low level API
+    return 0;
+}
+
+size_t cx_ll_size(cx_list *list) {
+    cx_linked_list *listdata = list->listdata;
+    return listdata->size;
+}
+
+cx_list_class cx_linked_list_class = {
+        cx_ll_add,
+        cx_ll_insert,
+        cx_ll_remove,
+        cx_ll_find,
+        cx_ll_size
+};
+
+CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator) {
+    CxList list = cxMalloc(allocator, sizeof(list));
+    if (list == NULL)
+        return NULL;
+
+    list->cl = &cx_linked_list_class;
+    list->data.allocator = allocator;
+    list->data.cmpfunc = comparator;
+    list->data.listdata = cxCalloc(allocator, 1, sizeof(cx_linked_list));
+    if (list->data.listdata == NULL) {
+        cxFree(allocator, list);
+        return NULL;
+    }
+}
\ No newline at end of file

--- a/src/list.c	Sun Feb 07 18:08:21 2021 +0100
+++ b/src/list.c	Sun Feb 07 19:42:12 2021 +0100
@@ -27,3 +27,23 @@
  */
 
 #include "cx/list.h"
+
+int cxListAdd(CxList list, void *elem) {
+    return list->cl->add(&list->data, elem);
+}
+
+int cxListInsert(CxList list, size_t index, void *elem) {
+    return list->cl->insert(&list->data, index, elem);
+}
+
+void *cxListRemove(CxList list, size_t index) {
+    return list->cl->remove(&list->data, index);
+}
+
+size_t cxListFind(CxList list, void *elem) {
+    return list->cl->find(&list->data, elem);
+}
+
+size_t cxListSize(CxList list) {
+    return list->cl->size(&list->data);
+}

--- a/test/CMakeLists.txt	Sun Feb 07 18:08:21 2021 +0100
+++ b/test/CMakeLists.txt	Sun Feb 07 19:42:12 2021 +0100
@@ -9,7 +9,7 @@
     message(CHECK_PASS "found: compiling tests.")
     set(TESTS
             test_allocator
-            test_list
+            test_linked_list
     )
 
     foreach(test ${TESTS})

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/test_linked_list.c	Sun Feb 07 19:42:12 2021 +0100
@@ -0,0 +1,35 @@
+/*
+ * 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/linked_list.h"
+
+#include <CUnit/Basic.h>
+
+int main() {
+    return 0;
+}

--- a/test/test_list.c	Sun Feb 07 18:08:21 2021 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,31 +0,0 @@
-/*
- * 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.
- */
-
-int main() {
-    return 0;
-}