Mercurial > hg > ucx / changeset

     1.1 --- a/.hgignore	Sun Feb 07 18:08:21 2021 +0100
     1.2 +++ b/.hgignore	Sun Feb 07 19:42:12 2021 +0100
     1.3 @@ -1,32 +1,9 @@
     1.4  syntax:regexp
     1.5  ^nbproject/
     1.6  ^build/
     1.7 -^.settings/
     1.8 -^.project
     1.9 -^.cproject
    1.10 -^.autotools
    1.11  /core$
    1.12  DS_Store$
    1.13 -^docs/web/
    1.14 -^docs/man/
    1.15 -\.o$
    1.16 -\.lo$
    1.17 -\.la$
    1.18 -^autom4te\.cache/
    1.19 -^build-aux/
    1.20 -^m4/
    1.21 -^aclocal.m4$
    1.22 -^config\.
    1.23 -^configure$
    1.24 -^libtool$
    1.25 -^src/.*Makefile$
    1.26 -^test/.*Makefile$
    1.27 -^Makefile$
    1.28 -Makefile\.in$
    1.29 -/\.deps/
    1.30 -/\.libs/
    1.31  ^stamp-h
    1.32 -test/test_list.c
    1.33  /test-suite.log$
    1.34  ^ucx-.*\.tar.gz$
    1.35  ^.idea/

     2.1 --- a/src/CMakeLists.txt	Sun Feb 07 18:08:21 2021 +0100
     2.2 +++ b/src/CMakeLists.txt	Sun Feb 07 19:42:12 2021 +0100
     2.3 @@ -1,10 +1,12 @@
     2.4  set(sources
     2.5          allocator.c
     2.6          list.c
     2.7 +        linked_list.c
     2.8  )
     2.9  set(headers
    2.10          cx/allocator.h
    2.11          cx/list.h
    2.12 +        cx/linked_list.h
    2.13  )
    2.14  
    2.15  add_library(ucx SHARED ${sources})

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/src/cx/linked_list.h	Sun Feb 07 19:42:12 2021 +0100
     3.3 @@ -0,0 +1,42 @@
     3.4 +/*
     3.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     3.6 + *
     3.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
     3.8 + *
     3.9 + * Redistribution and use in source and binary forms, with or without
    3.10 + * modification, are permitted provided that the following conditions are met:
    3.11 + *
    3.12 + *   1. Redistributions of source code must retain the above copyright
    3.13 + *      notice, this list of conditions and the following disclaimer.
    3.14 + *
    3.15 + *   2. Redistributions in binary form must reproduce the above copyright
    3.16 + *      notice, this list of conditions and the following disclaimer in the
    3.17 + *      documentation and/or other materials provided with the distribution.
    3.18 + *
    3.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    3.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    3.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    3.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    3.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    3.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    3.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    3.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    3.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    3.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    3.29 + * POSSIBILITY OF SUCH DAMAGE.
    3.30 + */
    3.31 +
    3.32 +#ifndef UCX_LINKED_LIST_H
    3.33 +#define UCX_LINKED_LIST_H
    3.34 +
    3.35 +#include "list.h"
    3.36 +
    3.37 +void *cx_linked_list_last(void **begin, void **end, off_t loc_next);
    3.38 +
    3.39 +int cx_linked_list_add(void **begin, void **end, off_t loc_next, off_t loc_prev, void *newnode);
    3.40 +
    3.41 +CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator);
    3.42 +
    3.43 +extern cx_list_class cx_linked_list_class;
    3.44 +
    3.45 +#endif /* UCX_LINKED_LIST_H */

     4.1 --- a/src/cx/list.h	Sun Feb 07 18:08:21 2021 +0100
     4.2 +++ b/src/cx/list.h	Sun Feb 07 19:42:12 2021 +0100
     4.3 @@ -29,4 +29,50 @@
     4.4  #ifndef UCX_LIST_H
     4.5  #define UCX_LIST_H
     4.6  
     4.7 +#include <stdlib.h>
     4.8 +#include "allocator.h"
     4.9 +
    4.10 +typedef int(*CxListComparator)(void *left, void *right);
    4.11 +
    4.12 +typedef struct {
    4.13 +    CxAllocator allocator;
    4.14 +    CxListComparator cmpfunc;
    4.15 +    void *listdata;
    4.16 +} cx_list;
    4.17 +
    4.18 +typedef int (*cx_list_add)(cx_list *list, void *elem);
    4.19 +
    4.20 +typedef int (*cx_list_insert)(cx_list *list, size_t index, void *elem);
    4.21 +
    4.22 +typedef void *(*cx_list_remove)(cx_list *list, size_t index);
    4.23 +
    4.24 +typedef size_t (*cx_list_find)(cx_list *list, void *elem);
    4.25 +
    4.26 +typedef size_t (*cx_list_size)(cx_list *list);
    4.27 +
    4.28 +typedef struct {
    4.29 +    cx_list_add add;
    4.30 +    cx_list_insert insert;
    4.31 +    cx_list_remove remove;
    4.32 +    cx_list_find find;
    4.33 +    cx_list_size size;
    4.34 +} cx_list_class;
    4.35 +
    4.36 +struct cx_list_s {
    4.37 +    cx_list_class *cl;
    4.38 +    cx_list data;
    4.39 +};
    4.40 +
    4.41 +typedef struct cx_list_s *CxList;
    4.42 +
    4.43 +int cxListAdd(CxList list, void *elem);
    4.44 +
    4.45 +int cxListInsert(CxList list, size_t index, void *elem);
    4.46 +
    4.47 +void *cxListRemove(CxList list, size_t index);
    4.48 +
    4.49 +size_t cxListFind(CxList list, void *elem);
    4.50 +
    4.51 +size_t cxListSize(CxList list);
    4.52 +
    4.53  #endif /* UCX_LIST_H */

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/src/linked_list.c	Sun Feb 07 19:42:12 2021 +0100
     5.3 @@ -0,0 +1,162 @@
     5.4 +/*
     5.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     5.6 + *
     5.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
     5.8 + *
     5.9 + * Redistribution and use in source and binary forms, with or without
    5.10 + * modification, are permitted provided that the following conditions are met:
    5.11 + *
    5.12 + *   1. Redistributions of source code must retain the above copyright
    5.13 + *      notice, this list of conditions and the following disclaimer.
    5.14 + *
    5.15 + *   2. Redistributions in binary form must reproduce the above copyright
    5.16 + *      notice, this list of conditions and the following disclaimer in the
    5.17 + *      documentation and/or other materials provided with the distribution.
    5.18 + *
    5.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    5.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    5.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    5.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    5.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    5.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    5.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    5.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    5.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    5.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    5.29 + * POSSIBILITY OF SUCH DAMAGE.
    5.30 + */
    5.31 +
    5.32 +#include "cx/linked_list.h"
    5.33 +#include <stddef.h>
    5.34 +
    5.35 +/* LOW LEVEL LINKED LIST FUNCTIONS */
    5.36 +
    5.37 +#define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off))
    5.38 +
    5.39 +void *cx_linked_list_last(void **begin, void **end, off_t loc_next) {
    5.40 +    if (end != NULL) {
    5.41 +        return *end;
    5.42 +    } else {
    5.43 +        if (begin == NULL || *begin == NULL)
    5.44 +            return NULL;
    5.45 +
    5.46 +        void *cur = *begin;
    5.47 +        void *last;
    5.48 +        do {
    5.49 +            last = cur;
    5.50 +        } while ((cur = *CX_LL_PTR(cur, loc_next)) != NULL);
    5.51 +
    5.52 +        return last;
    5.53 +    }
    5.54 +}
    5.55 +
    5.56 +int cx_linked_list_add(void **begin, void **end, off_t loc_next, off_t loc_prev, void *newnode) {
    5.57 +    // TODO: how do we report error messages?
    5.58 +    if (loc_next < 0 || (begin == NULL && end == NULL)) {
    5.59 +        return 1;
    5.60 +    }
    5.61 +
    5.62 +    void *last = cx_linked_list_last(begin, end, loc_next);
    5.63 +    if (last == NULL) {
    5.64 +        if (begin == NULL) {
    5.65 +            return 1;
    5.66 +        } else {
    5.67 +            *begin = newnode;
    5.68 +            return 0;
    5.69 +        }
    5.70 +    }
    5.71 +
    5.72 +    void **next = CX_LL_PTR(last, loc_next);
    5.73 +    *next = newnode;
    5.74 +    if (loc_prev >= 0) {
    5.75 +        void **prev = CX_LL_PTR(newnode, loc_prev);
    5.76 +        *prev = last;
    5.77 +    }
    5.78 +
    5.79 +    return 0;
    5.80 +}
    5.81 +
    5.82 +/* HIGH LEVEL LINKED LIST IMPLEMENTATION */
    5.83 +
    5.84 +typedef struct cx_list_node_s cx_list_node;
    5.85 +
    5.86 +struct cx_list_node_s {
    5.87 +    cx_list_node *next;
    5.88 +    cx_list_node *prev;
    5.89 +    void *data;
    5.90 +};
    5.91 +
    5.92 +typedef struct {
    5.93 +    cx_list_node *begin;
    5.94 +    cx_list_node *end;
    5.95 +    size_t size;
    5.96 +} cx_linked_list;
    5.97 +
    5.98 +int cx_ll_add(cx_list *list, void *elem) {
    5.99 +    cx_linked_list *listdata = list->listdata;
   5.100 +    CxAllocator allocator = list->allocator;
   5.101 +
   5.102 +    struct cx_list_node_s *node = cxMalloc(allocator, sizeof(struct cx_list_node_s));
   5.103 +    if (node == NULL)
   5.104 +        return 1;
   5.105 +
   5.106 +    int ret = cx_linked_list_add(
   5.107 +            (void **) &listdata->begin,
   5.108 +            (void **) &listdata->end,
   5.109 +            offsetof(struct cx_list_node_s, next),
   5.110 +            offsetof(struct cx_list_node_s, prev),
   5.111 +            node
   5.112 +    );
   5.113 +    if (ret == 0) {
   5.114 +        listdata->size++;
   5.115 +        return 0;
   5.116 +    } else {
   5.117 +        return ret;
   5.118 +    }
   5.119 +}
   5.120 +
   5.121 +int cx_ll_insert(cx_list *list, size_t index, void *elem) {
   5.122 +    cx_linked_list *listdata = list->listdata;
   5.123 +    // TODO: implement using low level API
   5.124 +    return 1;
   5.125 +}
   5.126 +
   5.127 +void *cx_ll_remove(cx_list *list, size_t index) {
   5.128 +    cx_linked_list *listdata = list->listdata;
   5.129 +    // TODO: implement using low level API
   5.130 +    return NULL;
   5.131 +}
   5.132 +
   5.133 +size_t cx_ll_find(cx_list *list, void *elem) {
   5.134 +    cx_linked_list *listdata = list->listdata;
   5.135 +    // TODO: implement using low level API
   5.136 +    return 0;
   5.137 +}
   5.138 +
   5.139 +size_t cx_ll_size(cx_list *list) {
   5.140 +    cx_linked_list *listdata = list->listdata;
   5.141 +    return listdata->size;
   5.142 +}
   5.143 +
   5.144 +cx_list_class cx_linked_list_class = {
   5.145 +        cx_ll_add,
   5.146 +        cx_ll_insert,
   5.147 +        cx_ll_remove,
   5.148 +        cx_ll_find,
   5.149 +        cx_ll_size
   5.150 +};
   5.151 +
   5.152 +CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator) {
   5.153 +    CxList list = cxMalloc(allocator, sizeof(list));
   5.154 +    if (list == NULL)
   5.155 +        return NULL;
   5.156 +
   5.157 +    list->cl = &cx_linked_list_class;
   5.158 +    list->data.allocator = allocator;
   5.159 +    list->data.cmpfunc = comparator;
   5.160 +    list->data.listdata = cxCalloc(allocator, 1, sizeof(cx_linked_list));
   5.161 +    if (list->data.listdata == NULL) {
   5.162 +        cxFree(allocator, list);
   5.163 +        return NULL;
   5.164 +    }
   5.165 +}
   5.166 \ No newline at end of file

     6.1 --- a/src/list.c	Sun Feb 07 18:08:21 2021 +0100
     6.2 +++ b/src/list.c	Sun Feb 07 19:42:12 2021 +0100
     6.3 @@ -27,3 +27,23 @@
     6.4   */
     6.5  
     6.6  #include "cx/list.h"
     6.7 +
     6.8 +int cxListAdd(CxList list, void *elem) {
     6.9 +    return list->cl->add(&list->data, elem);
    6.10 +}
    6.11 +
    6.12 +int cxListInsert(CxList list, size_t index, void *elem) {
    6.13 +    return list->cl->insert(&list->data, index, elem);
    6.14 +}
    6.15 +
    6.16 +void *cxListRemove(CxList list, size_t index) {
    6.17 +    return list->cl->remove(&list->data, index);
    6.18 +}
    6.19 +
    6.20 +size_t cxListFind(CxList list, void *elem) {
    6.21 +    return list->cl->find(&list->data, elem);
    6.22 +}
    6.23 +
    6.24 +size_t cxListSize(CxList list) {
    6.25 +    return list->cl->size(&list->data);
    6.26 +}

     7.1 --- a/test/CMakeLists.txt	Sun Feb 07 18:08:21 2021 +0100
     7.2 +++ b/test/CMakeLists.txt	Sun Feb 07 19:42:12 2021 +0100
     7.3 @@ -9,7 +9,7 @@
     7.4      message(CHECK_PASS "found: compiling tests.")
     7.5      set(TESTS
     7.6              test_allocator
     7.7 -            test_list
     7.8 +            test_linked_list
     7.9      )
    7.10  
    7.11      foreach(test ${TESTS})

     8.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     8.2 +++ b/test/test_linked_list.c	Sun Feb 07 19:42:12 2021 +0100
     8.3 @@ -0,0 +1,35 @@
     8.4 +/*
     8.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     8.6 + *
     8.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
     8.8 + *
     8.9 + * Redistribution and use in source and binary forms, with or without
    8.10 + * modification, are permitted provided that the following conditions are met:
    8.11 + *
    8.12 + *   1. Redistributions of source code must retain the above copyright
    8.13 + *      notice, this list of conditions and the following disclaimer.
    8.14 + *
    8.15 + *   2. Redistributions in binary form must reproduce the above copyright
    8.16 + *      notice, this list of conditions and the following disclaimer in the
    8.17 + *      documentation and/or other materials provided with the distribution.
    8.18 + *
    8.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    8.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    8.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    8.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    8.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    8.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    8.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    8.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    8.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    8.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    8.29 + * POSSIBILITY OF SUCH DAMAGE.
    8.30 + */
    8.31 +
    8.32 +#include "cx/linked_list.h"
    8.33 +
    8.34 +#include <CUnit/Basic.h>
    8.35 +
    8.36 +int main() {
    8.37 +    return 0;
    8.38 +}

     9.1 --- a/test/test_list.c	Sun Feb 07 18:08:21 2021 +0100
     9.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     9.3 @@ -1,31 +0,0 @@
     9.4 -/*
     9.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     9.6 - *
     9.7 - * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
     9.8 - *
     9.9 - * Redistribution and use in source and binary forms, with or without
    9.10 - * modification, are permitted provided that the following conditions are met:
    9.11 - *
    9.12 - *   1. Redistributions of source code must retain the above copyright
    9.13 - *      notice, this list of conditions and the following disclaimer.
    9.14 - *
    9.15 - *   2. Redistributions in binary form must reproduce the above copyright
    9.16 - *      notice, this list of conditions and the following disclaimer in the
    9.17 - *      documentation and/or other materials provided with the distribution.
    9.18 - *
    9.19 - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    9.20 - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    9.21 - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    9.22 - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    9.23 - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    9.24 - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    9.25 - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    9.26 - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    9.27 - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    9.28 - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    9.29 - * POSSIBILITY OF SUCH DAMAGE.
    9.30 - */
    9.31 -
    9.32 -int main() {
    9.33 -    return 0;
    9.34 -}