Mercurial > hg > ucx / file comparison

comparison: src/linked_list.c

src/linked_list.c

changeset 446
668757098b73
parent 441
7d5a06e32aa8
child 447
87b2cdd668ed
equal deleted inserted replaced
445:26ae21face39 446:668757098b73
34 34
35 #define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off)) 35 #define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off))
36 36
37 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) { 37 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
38 size_t i = start_index; 38 size_t i = start_index;
39 void* cur = start; 39 void *cur = start;
40 while (i != index && cur != NULL) { 40 while (i != index && cur != NULL) {
41 cur = *CX_LL_PTR(cur, loc_advance); 41 cur = *CX_LL_PTR(cur, loc_advance);
42 i < index ? i++ : i--; 42 i < index ? i++ : i--;
43 } 43 }
44 return cur; 44 return cur;
91 return 0; 91 return 0;
92 } 92 }
93 93
94 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ 94 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
95 95
96 struct cx_linked_list_node { 96 typedef struct {
97 void *prev; 97 void *prev;
98 void *next; 98 void *next;
99 char payload[]; 99 char payload[];
100 }; 100 } cx_linked_list_node;
101 101
102 #define CX_LL_LOC_PREV offsetof(struct cx_linked_list_node, prev) 102 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
103 #define CX_LL_LOC_NEXT offsetof(struct cx_linked_list_node, next) 103 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
104 104
105 typedef struct { 105 typedef struct {
106 cx_list_s base; 106 cx_list_s base;
107 void *begin; 107 cx_linked_list_node *begin;
108 void *end; 108 cx_linked_list_node *end;
109 ptrdiff_t loc_prev;
110 ptrdiff_t loc_next;
111 } cx_linked_list; 109 } cx_linked_list;
112 110
113 static int cx_ll_add(cx_list_s *list, void *elem) { 111 static int cx_ll_add(cx_list_s *list, void *elem) {
114 cx_linked_list *ll = (cx_linked_list *) list; 112 cx_linked_list *ll = (cx_linked_list *) list;
115 113
116 struct cx_linked_list_node *node = cxMalloc(list->allocator, 114 cx_linked_list_node *node = cxMalloc(list->allocator,
117 sizeof(struct cx_linked_list_node) + list->itemsize); 115 sizeof(cx_linked_list_node) + list->itemsize);
118 if (node == NULL) 116 if (node == NULL)
119 return 1; 117 return 1;
120 118
121 node->next = node->prev = NULL;
122 memcpy(node->payload, elem, list->itemsize); 119 memcpy(node->payload, elem, list->itemsize);
123 120 node->next = NULL;
124 int ret = cx_linked_list_add( 121
125 &ll->begin, &ll->end, 122 if (ll->begin == NULL) {
126 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, 123 ll->begin = ll->end = node;
127 node 124 } else {
128 ); 125 // per contract of this linked list we know that end must be non-null
129 if (ret == 0) { 126 ll->end->next = node;
130 list->size++; 127 ll->end = node;
131 return 0; 128 }
132 } else { 129 list->size++;
133 return ret; 130
134 } 131 return 0;
135 } 132 }
136 133
137 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) { 134 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
138 cx_linked_list *ll = (cx_linked_list *) list; 135 cx_linked_list *ll = (cx_linked_list *) list;
139 // TODO: implement using low level API 136 // TODO: implement using low level API
149 return 0; 146 return 0;
150 } 147 }
151 148
152 static void *cx_ll_at(cx_list_s *list, size_t index) { 149 static void *cx_ll_at(cx_list_s *list, size_t index) {
153 cx_linked_list *ll = (cx_linked_list *) list; 150 cx_linked_list *ll = (cx_linked_list *) list;
154 struct cx_linked_list_node *node; 151 cx_linked_list_node *node;
155 if (index >= list->size) { 152 if (index >= list->size) {
156 node = NULL; 153 node = NULL;
157 } else if (index > list->size / 2) { 154 } else if (index > list->size / 2) {
158 node = cx_linked_list_at(ll->end, list->size, CX_LL_LOC_PREV, index); 155 node = cx_linked_list_at(ll->end, list->size, CX_LL_LOC_PREV, index);
159 } else { 156 } else {
165 static size_t cx_ll_find(cx_list_s *list, void *elem) { 162 static size_t cx_ll_find(cx_list_s *list, void *elem) {
166 CxListComparator cmp = list->cmpfunc; 163 CxListComparator cmp = list->cmpfunc;
167 cx_linked_list *ll = (cx_linked_list *) list; 164 cx_linked_list *ll = (cx_linked_list *) list;
168 165
169 size_t index; 166 size_t index;
170 struct cx_linked_list_node* node = ll->begin; 167 cx_linked_list_node *node = ll->begin;
171 for (index = 0 ; index < list->size ; index++) { 168 for (index = 0; index < list->size; index++) {
172 void* current = node->payload; 169 void *current = node->payload;
173 if (cmp(current, elem) == 0) { 170 if (cmp(current, elem) == 0) {
174 return index; 171 return index;
175 } 172 }
176 node = node->next; 173 node = node->next;
177 } 174 }
178 return index; 175 return index;
179 } 176 }
180 177
181 static void *cx_ll_last(cx_list_s *list) { 178 static void *cx_ll_last(cx_list_s *list) {
182 cx_linked_list *ll = (cx_linked_list *) list; 179 cx_linked_list *ll = (cx_linked_list *) list;
183 struct cx_linked_list_node *last = cx_linked_list_last(NULL, &ll->end, CX_LL_LOC_NEXT); 180 cx_linked_list_node *last = cx_linked_list_last(NULL, (void **) &ll->end, CX_LL_LOC_NEXT);
184 return &last->payload; 181 return &last->payload;
185 } 182 }
186 183
187 cx_list_class cx_linked_list_class = { 184 cx_list_class cx_linked_list_class = {
188 cx_ll_add, 185 cx_ll_add,
192 cx_ll_find, 189 cx_ll_find,
193 cx_ll_last 190 cx_ll_last
194 }; 191 };
195 192
196 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) { 193 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
197 cx_linked_list* list = cxMalloc(allocator, sizeof(cx_linked_list)); 194 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
198 if (list == NULL) 195 if (list == NULL)
199 return NULL; 196 return NULL;
200 197
201 list->base.cl = &cx_linked_list_class; 198 list->base.cl = &cx_linked_list_class;
202 list->base.allocator = allocator; 199 list->base.allocator = allocator;
205 list->base.capacity = SIZE_MAX; 202 list->base.capacity = SIZE_MAX;
206 list->base.size = 0; 203 list->base.size = 0;
207 204
208 list->begin = NULL; 205 list->begin = NULL;
209 list->end = NULL; 206 list->end = NULL;
210 list->loc_prev = CX_LL_LOC_PREV;
211 list->loc_next = CX_LL_LOC_NEXT;
212 207
213 return (CxList) list; 208 return (CxList) list;
214 } 209 }
215 210
216 void cxLinkedListDestroy(CxList list) { 211 void cxLinkedListDestroy(CxList list) {
217 cx_linked_list* ll = (cx_linked_list*) list; 212 cx_linked_list *ll = (cx_linked_list *) list;
218 213
219 struct cx_linked_list_node* node = ll->begin; 214 cx_linked_list_node *node = ll->begin;
220 while (node) { 215 while (node) {
221 void* next = node->next; 216 void *next = node->next;
222 cxFree(list->allocator, node); 217 cxFree(list->allocator, node);
223 node = next; 218 node = next;
224 } 219 }
225 220
226 cxFree(list->allocator, list); 221 cxFree(list->allocator, list);
232 if (ll->begin == NULL) { 227 if (ll->begin == NULL) {
233 ll->base.size = 0; 228 ll->base.size = 0;
234 ll->end = NULL; 229 ll->end = NULL;
235 return 0; 230 return 0;
236 } else { 231 } else {
237 void *cur = ll->begin; 232 cx_linked_list_node *cur = ll->begin;
238 void *last; 233 cx_linked_list_node *last;
239 size_t size = 0; 234 size_t size = 0;
240 do { 235 do {
241 last = cur; 236 last = cur;
242 size++; 237 size++;
243 } while ((cur = *CX_LL_PTR(cur, ll->loc_next)) != NULL); 238 } while ((cur = cur->next) != NULL);
244 ll->end = last; 239 ll->end = last;
245 ll->base.size = size; 240 ll->base.size = size;
246 return size; 241 return size;
247 } 242 }
248 } 243 }

Mercurial Repository: ucx

mercurial