Mercurial > hg > ucx / file comparison

comparison: src/linked_list.c

src/linked_list.c

changeset 406
9cbea761fbf7
parent 404
86ebc3745e62
child 407
b447539ec255
equal deleted inserted replaced
405:44efaa54d63d 406:9cbea761fbf7
49 49
50 return last; 50 return last;
51 } 51 }
52 } 52 }
53 53
54 int cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *newnode) { 54 int cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
55 // TODO: how do we report error messages? 55 // TODO: how do we report error messages?
56 if (loc_next < 0 || (begin == NULL && end == NULL)) { 56 if (loc_next < 0 || (begin == NULL && end == NULL)) {
57 return 1; 57 return 1;
58 } 58 }
59 59
60 void *last = cx_linked_list_last(begin, end, loc_next); 60 void *last = cx_linked_list_last(begin, end, loc_next);
61 if (last == NULL) { 61 if (last == NULL) {
62 if (begin == NULL) { 62 if (begin == NULL) {
63 return 1; 63 return 1;
64 } else { 64 } else {
65 *begin = newnode; 65 *begin = new_node;
66 return 0; 66 return 0;
67 } 67 }
68 } 68 }
69 69
70 void **next = CX_LL_PTR(last, loc_next); 70 void **next = CX_LL_PTR(last, loc_next);
71 *next = newnode; 71 *next = new_node;
72 if (loc_prev >= 0) { 72 if (loc_prev >= 0) {
73 void **prev = CX_LL_PTR(newnode, loc_prev); 73 void **prev = CX_LL_PTR(new_node, loc_prev);
74 *prev = last; 74 *prev = last;
75 } 75 }
76 76
77 return 0; 77 return 0;
78 } 78 }
86 }; 86 };
87 87
88 typedef struct { 88 typedef struct {
89 void *begin; 89 void *begin;
90 void *end; 90 void *end;
91 ptrdiff_t loc_prev;
92 ptrdiff_t loc_next;
91 } cx_linked_list; 93 } cx_linked_list;
92 94
93 int cx_ll_add(cx_list *list, void *elem) { 95 int cx_ll_add(cx_list *list, void *elem) {
94 cx_linked_list *listdata = list->listdata; 96 cx_linked_list *listdata = (cx_linked_list *) list->listdata;
95 CxAllocator allocator = list->allocator; 97 CxAllocator allocator = list->allocator;
96 98
97 struct cx_linked_list_node *node = cxMalloc(allocator, 99 struct cx_linked_list_node *node = cxMalloc(allocator,
98 sizeof(struct cx_linked_list_node) + list->itemsize); 100 sizeof(struct cx_linked_list_node) + list->itemsize);
99 if (node == NULL) 101 if (node == NULL)
100 return 1; 102 return 1;
101 103
102 node->next = NULL; 104 node->next = NULL;
103 memcpy(&node->payload, elem, list->itemsize); 105 memcpy(node->payload, elem, list->itemsize);
104 106
105 int ret = cx_linked_list_add( 107 int ret = cx_linked_list_add(
106 &listdata->begin, 108 &listdata->begin,
107 &listdata->end, 109 &listdata->end,
108 offsetof(struct cx_linked_list_node, prev), 110 offsetof(struct cx_linked_list_node, prev),
116 return ret; 118 return ret;
117 } 119 }
118 } 120 }
119 121
120 int cx_ll_insert(cx_list *list, size_t index, void *elem) { 122 int cx_ll_insert(cx_list *list, size_t index, void *elem) {
121 cx_linked_list *listdata = list->listdata; 123 cx_linked_list *listdata = (cx_linked_list *) list->listdata;
122 // TODO: implement using low level API 124 // TODO: implement using low level API
123 return 1; 125 return 1;
124 } 126 }
125 127
126 void *cx_ll_remove(cx_list *list, size_t index) { 128 void *cx_ll_remove(cx_list *list, size_t index) {
127 cx_linked_list *listdata = list->listdata; 129 cx_linked_list *listdata = (cx_linked_list *) list->listdata;
128 // TODO: implement using low level API 130 // TODO: implement using low level API
129 return NULL; 131 return NULL;
130 } 132 }
131 133
132 size_t cx_ll_find(cx_list *list, void *elem) { 134 size_t cx_ll_find(cx_list *list, void *elem) {
133 cx_linked_list *listdata = list->listdata; 135 cx_linked_list *listdata = (cx_linked_list *) list->listdata;
134 // TODO: implement using low level API 136 // TODO: implement using low level API
135 return 0; 137 return 0;
136 } 138 }
137 139
138 void *cx_ll_last(cx_list *list) { 140 void *cx_ll_last(cx_list *list) {
139 cx_linked_list *ll = list->listdata; 141 cx_linked_list *listdata = (cx_linked_list *) list->listdata;
140 struct cx_linked_list_node *last = cx_linked_list_last( 142 struct cx_linked_list_node *last = cx_linked_list_last(
141 NULL, &ll->end, offsetof(struct cx_linked_list_node, next)); 143 NULL, &listdata->end, offsetof(struct cx_linked_list_node, next));
142 return &last->payload; 144 return &last->payload;
143 } 145 }
144 146
145 cx_list_class cx_linked_list_class = { 147 cx_list_class cx_linked_list_class = {
146 cx_ll_add, 148 cx_ll_add,
148 cx_ll_remove, 150 cx_ll_remove,
149 cx_ll_find, 151 cx_ll_find,
150 cx_ll_last 152 cx_ll_last
151 }; 153 };
152 154
153 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t itemsize) { 155 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
154 CxList list = cxMalloc(allocator, sizeof(list)); 156 CxLinkedListDesc desc;
157 desc.item_size = item_size;
158 desc.begin = desc.end = NULL;
159 desc.loc_prev = offsetof(struct cx_linked_list_node, prev);
160 desc.loc_next = offsetof(struct cx_linked_list_node, next);
161
162 return cxLinkedListWrap(allocator, comparator, desc);
163 }
164
165 CxList cxLinkedListWrap(CxAllocator allocator, CxListComparator comparator, CxLinkedListDesc desc) {
166 CxList list = cxMalloc(allocator, sizeof(list) + sizeof(cx_linked_list));
155 if (list == NULL) 167 if (list == NULL)
156 return NULL; 168 return NULL;
157 169
158 list->cl = &cx_linked_list_class; 170 list->cl = &cx_linked_list_class;
159 list->data.allocator = allocator; 171 list->data.allocator = allocator;
160 list->data.cmpfunc = comparator; 172 list->data.cmpfunc = comparator;
161 list->data.size = 0; 173 list->data.itemsize = desc.item_size;
162 list->data.itemsize = itemsize;
163 list->data.capacity = SIZE_MAX; 174 list->data.capacity = SIZE_MAX;
164 list->data.listdata = cxCalloc(allocator, 1, sizeof(cx_linked_list)); 175
165 if (list->data.listdata == NULL) { 176 cx_linked_list *ll = (cx_linked_list *) list->data.listdata;
166 cxFree(allocator, list); 177 ll->begin = desc.begin ? *desc.begin : NULL;
167 return NULL; 178 ll->end = desc.end ? *desc.end : NULL;
168 } 179 ll->loc_prev = desc.loc_prev;
169 } 180 ll->loc_next = desc.loc_next;
181 cxLinkedListRecalculateSize(list);
182
183 return list;
184 }
185
186 size_t cxLinkedListRecalculateSize(CxList list) {
187 cx_linked_list *ll = (cx_linked_list *) list->data.listdata;
188
189 if (ll->begin == NULL) {
190 list->data.size = 0;
191 return 0;
192 } else {
193 void *cur = ll->begin;
194 size_t size;
195 do {
196 size++;
197 } while ((cur = *CX_LL_PTR(cur, ll->loc_next)) != NULL);
198 list->data.size = size;
199 return size;
200 }
201 }

Mercurial Repository: ucx

mercurial