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 } |