# HG changeset patch # User Mike Becker # Date 1612723332 -3600 # Node ID 8d506ed6c1c03b64e7aa816af6a8918d5b9cc996 # Parent cfc1193b1e65932c53258aac663e3f0fbc0a800b adds first draft for linked list implementation diff -r cfc1193b1e65 -r 8d506ed6c1c0 .hgignore --- 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/ diff -r cfc1193b1e65 -r 8d506ed6c1c0 src/CMakeLists.txt --- 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}) diff -r cfc1193b1e65 -r 8d506ed6c1c0 src/cx/linked_list.h --- /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 */ diff -r cfc1193b1e65 -r 8d506ed6c1c0 src/cx/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 +#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 */ diff -r cfc1193b1e65 -r 8d506ed6c1c0 src/linked_list.c --- /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 + +/* 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 diff -r cfc1193b1e65 -r 8d506ed6c1c0 src/list.c --- 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); +} diff -r cfc1193b1e65 -r 8d506ed6c1c0 test/CMakeLists.txt --- 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}) diff -r cfc1193b1e65 -r 8d506ed6c1c0 test/test_linked_list.c --- /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 + +int main() { + return 0; +} diff -r cfc1193b1e65 -r 8d506ed6c1c0 test/test_list.c --- 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; -}