Sun, 26 Sep 2021 13:06:48 +0200
remove public visibility of default allocator class
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
1 | /* |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
3 | * |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
4 | * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
5 | * |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
6 | * Redistribution and use in source and binary forms, with or without |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
7 | * modification, are permitted provided that the following conditions are met: |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
8 | * |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
9 | * 1. Redistributions of source code must retain the above copyright |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
10 | * notice, this list of conditions and the following disclaimer. |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
11 | * |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
12 | * 2. Redistributions in binary form must reproduce the above copyright |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
13 | * notice, this list of conditions and the following disclaimer in the |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
14 | * documentation and/or other materials provided with the distribution. |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
15 | * |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
26 | * POSSIBILITY OF SUCH DAMAGE. |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
27 | */ |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
28 | |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
29 | #include "cx/linked_list.h" |
401
e6a8f7fb0c45
copy list items when they are added to the list
Mike Becker <universe@uap-core.de>
parents:
400
diff
changeset
|
30 | #include <stdint.h> |
e6a8f7fb0c45
copy list items when they are added to the list
Mike Becker <universe@uap-core.de>
parents:
400
diff
changeset
|
31 | #include <string.h> |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
32 | |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
33 | /* LOW LEVEL LINKED LIST FUNCTIONS */ |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
34 | |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
35 | #define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off)) |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
36 | |
400
8cd274352419
changes off_t to ptrdiff_t
Mike Becker <universe@uap-core.de>
parents:
399
diff
changeset
|
37 | void *cx_linked_list_last(void **begin, void **end, ptrdiff_t loc_next) { |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
38 | if (end != NULL) { |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
39 | return *end; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
40 | } else { |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
41 | if (begin == NULL || *begin == NULL) |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
42 | return NULL; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
43 | |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
44 | void *cur = *begin; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
45 | void *last; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
46 | do { |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
47 | last = cur; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
48 | } while ((cur = *CX_LL_PTR(cur, loc_next)) != NULL); |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
49 | |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
50 | return last; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
51 | } |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
52 | } |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
53 | |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
54 | int cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
55 | void *last = cx_linked_list_last(begin, end, loc_next); |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
56 | if (last == NULL) { |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
57 | if (begin == NULL) { |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
58 | return 1; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
59 | } else { |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
60 | *begin = new_node; |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
61 | return 0; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
62 | } |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
63 | } |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
64 | |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
65 | void **next = CX_LL_PTR(last, loc_next); |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
66 | *next = new_node; |
408
dfdd571550f8
fixes cx_linked_list_add not recalculating end
Mike Becker <universe@uap-core.de>
parents:
407
diff
changeset
|
67 | if (end != NULL) { |
dfdd571550f8
fixes cx_linked_list_add not recalculating end
Mike Becker <universe@uap-core.de>
parents:
407
diff
changeset
|
68 | *end = cx_linked_list_last(&new_node, NULL, loc_next); |
dfdd571550f8
fixes cx_linked_list_add not recalculating end
Mike Becker <universe@uap-core.de>
parents:
407
diff
changeset
|
69 | } |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
70 | if (loc_prev >= 0) { |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
71 | void **prev = CX_LL_PTR(new_node, loc_prev); |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
72 | *prev = last; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
73 | } |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
74 | |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
75 | return 0; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
76 | } |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
77 | |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
78 | /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
79 | |
402
a34b93911956
use named fields to access node memory
Mike Becker <universe@uap-core.de>
parents:
401
diff
changeset
|
80 | struct cx_linked_list_node { |
a34b93911956
use named fields to access node memory
Mike Becker <universe@uap-core.de>
parents:
401
diff
changeset
|
81 | void *prev; |
a34b93911956
use named fields to access node memory
Mike Becker <universe@uap-core.de>
parents:
401
diff
changeset
|
82 | void *next; |
403
8fa43b732980
use C99 flexible array to mark the node's payload
Mike Becker <universe@uap-core.de>
parents:
402
diff
changeset
|
83 | char payload[]; |
402
a34b93911956
use named fields to access node memory
Mike Becker <universe@uap-core.de>
parents:
401
diff
changeset
|
84 | }; |
a34b93911956
use named fields to access node memory
Mike Becker <universe@uap-core.de>
parents:
401
diff
changeset
|
85 | |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
86 | typedef struct { |
401
e6a8f7fb0c45
copy list items when they are added to the list
Mike Becker <universe@uap-core.de>
parents:
400
diff
changeset
|
87 | void *begin; |
e6a8f7fb0c45
copy list items when they are added to the list
Mike Becker <universe@uap-core.de>
parents:
400
diff
changeset
|
88 | void *end; |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
89 | ptrdiff_t loc_prev; |
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
90 | ptrdiff_t loc_next; |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
91 | } cx_linked_list; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
92 | |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
93 | int cx_ll_add(cx_list *list, void *elem) { |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
94 | cx_linked_list *listdata = (cx_linked_list *) list->listdata; |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
95 | CxAllocator allocator = list->allocator; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
96 | |
402
a34b93911956
use named fields to access node memory
Mike Becker <universe@uap-core.de>
parents:
401
diff
changeset
|
97 | struct cx_linked_list_node *node = cxMalloc(allocator, |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
98 | sizeof(struct cx_linked_list_node) + list->itemsize); |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
99 | if (node == NULL) |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
100 | return 1; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
101 | |
402
a34b93911956
use named fields to access node memory
Mike Becker <universe@uap-core.de>
parents:
401
diff
changeset
|
102 | node->next = NULL; |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
103 | memcpy(node->payload, elem, list->itemsize); |
399
8902fcd1e057
adds missing assignments for new list node
Mike Becker <universe@uap-core.de>
parents:
398
diff
changeset
|
104 | |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
105 | int ret = cx_linked_list_add( |
401
e6a8f7fb0c45
copy list items when they are added to the list
Mike Becker <universe@uap-core.de>
parents:
400
diff
changeset
|
106 | &listdata->begin, |
e6a8f7fb0c45
copy list items when they are added to the list
Mike Becker <universe@uap-core.de>
parents:
400
diff
changeset
|
107 | &listdata->end, |
402
a34b93911956
use named fields to access node memory
Mike Becker <universe@uap-core.de>
parents:
401
diff
changeset
|
108 | offsetof(struct cx_linked_list_node, prev), |
a34b93911956
use named fields to access node memory
Mike Becker <universe@uap-core.de>
parents:
401
diff
changeset
|
109 | offsetof(struct cx_linked_list_node, next), |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
110 | node |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
111 | ); |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
112 | if (ret == 0) { |
401
e6a8f7fb0c45
copy list items when they are added to the list
Mike Becker <universe@uap-core.de>
parents:
400
diff
changeset
|
113 | list->size++; |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
114 | return 0; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
115 | } else { |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
116 | return ret; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
117 | } |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
118 | } |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
119 | |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
120 | int cx_ll_insert(cx_list *list, size_t index, void *elem) { |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
121 | cx_linked_list *listdata = (cx_linked_list *) list->listdata; |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
122 | // TODO: implement using low level API |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
123 | return 1; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
124 | } |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
125 | |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
126 | void *cx_ll_remove(cx_list *list, size_t index) { |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
127 | cx_linked_list *listdata = (cx_linked_list *) list->listdata; |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
128 | // TODO: implement using low level API |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
129 | return NULL; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
130 | } |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
131 | |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
132 | size_t cx_ll_find(cx_list *list, void *elem) { |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
133 | cx_linked_list *listdata = (cx_linked_list *) list->listdata; |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
134 | // TODO: implement using low level API |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
135 | return 0; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
136 | } |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
137 | |
404 | 138 | void *cx_ll_last(cx_list *list) { |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
139 | cx_linked_list *listdata = (cx_linked_list *) list->listdata; |
404 | 140 | struct cx_linked_list_node *last = cx_linked_list_last( |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
141 | NULL, &listdata->end, offsetof(struct cx_linked_list_node, next)); |
404 | 142 | return &last->payload; |
143 | } | |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
144 | |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
145 | cx_list_class cx_linked_list_class = { |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
146 | cx_ll_add, |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
147 | cx_ll_insert, |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
148 | cx_ll_remove, |
404 | 149 | cx_ll_find, |
150 | cx_ll_last | |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
151 | }; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
152 | |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
153 | CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) { |
412
af766caea48d
removes stupid high level wrapper for linked lists + adds test for cxLinkedListCreate
Mike Becker <universe@uap-core.de>
parents:
409
diff
changeset
|
154 | CxList list = cxMalloc(allocator, sizeof(cx_list_s) + sizeof(cx_linked_list)); |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
155 | if (list == NULL) |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
156 | return NULL; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
157 | |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
158 | list->cl = &cx_linked_list_class; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
159 | list->data.allocator = allocator; |
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
160 | list->data.cmpfunc = comparator; |
412
af766caea48d
removes stupid high level wrapper for linked lists + adds test for cxLinkedListCreate
Mike Becker <universe@uap-core.de>
parents:
409
diff
changeset
|
161 | list->data.itemsize = item_size; |
401
e6a8f7fb0c45
copy list items when they are added to the list
Mike Becker <universe@uap-core.de>
parents:
400
diff
changeset
|
162 | list->data.capacity = SIZE_MAX; |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
163 | |
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
164 | cx_linked_list *ll = (cx_linked_list *) list->data.listdata; |
412
af766caea48d
removes stupid high level wrapper for linked lists + adds test for cxLinkedListCreate
Mike Becker <universe@uap-core.de>
parents:
409
diff
changeset
|
165 | ll->begin = NULL; |
af766caea48d
removes stupid high level wrapper for linked lists + adds test for cxLinkedListCreate
Mike Becker <universe@uap-core.de>
parents:
409
diff
changeset
|
166 | ll->loc_prev = offsetof(struct cx_linked_list_node, prev); |
af766caea48d
removes stupid high level wrapper for linked lists + adds test for cxLinkedListCreate
Mike Becker <universe@uap-core.de>
parents:
409
diff
changeset
|
167 | ll->loc_next = offsetof(struct cx_linked_list_node, next); |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
168 | cxLinkedListRecalculateSize(list); |
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
169 | |
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
170 | return list; |
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
171 | } |
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
172 | |
409
5d167af0eadb
adds cxLinkedListDestroy prototype
Mike Becker <universe@uap-core.de>
parents:
408
diff
changeset
|
173 | void cxLinkedListDestroy(CxList list) { |
5d167af0eadb
adds cxLinkedListDestroy prototype
Mike Becker <universe@uap-core.de>
parents:
408
diff
changeset
|
174 | |
5d167af0eadb
adds cxLinkedListDestroy prototype
Mike Becker <universe@uap-core.de>
parents:
408
diff
changeset
|
175 | } |
5d167af0eadb
adds cxLinkedListDestroy prototype
Mike Becker <universe@uap-core.de>
parents:
408
diff
changeset
|
176 | |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
177 | size_t cxLinkedListRecalculateSize(CxList list) { |
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
178 | cx_linked_list *ll = (cx_linked_list *) list->data.listdata; |
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
179 | |
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
180 | if (ll->begin == NULL) { |
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
181 | list->data.size = 0; |
407
b447539ec255
simplifies linked list descriptor
Mike Becker <universe@uap-core.de>
parents:
406
diff
changeset
|
182 | ll->end = NULL; |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
183 | return 0; |
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
184 | } else { |
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
185 | void *cur = ll->begin; |
407
b447539ec255
simplifies linked list descriptor
Mike Becker <universe@uap-core.de>
parents:
406
diff
changeset
|
186 | void *last; |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
187 | size_t size; |
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
188 | do { |
407
b447539ec255
simplifies linked list descriptor
Mike Becker <universe@uap-core.de>
parents:
406
diff
changeset
|
189 | last = cur; |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
190 | size++; |
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
191 | } while ((cur = *CX_LL_PTR(cur, ll->loc_next)) != NULL); |
407
b447539ec255
simplifies linked list descriptor
Mike Becker <universe@uap-core.de>
parents:
406
diff
changeset
|
192 | ll->end = last; |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
193 | list->data.size = size; |
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
194 | return size; |
398
8d506ed6c1c0
adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
195 | } |
406
9cbea761fbf7
adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents:
404
diff
changeset
|
196 | } |