Mercurial > hg > ucx / file comparison

comparison: src/linked_list.c

src/linked_list.c

changeset 480
e3be53a3354f
parent 478
599770bb6314
child 481
eef025d82a34
equal deleted inserted replaced
479:a29bdd703e02 480:e3be53a3354f
32 #include <assert.h> 32 #include <assert.h>
33 33
34 /* LOW LEVEL LINKED LIST FUNCTIONS */ 34 /* LOW LEVEL LINKED LIST FUNCTIONS */
35 35
36 #define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off)) 36 #define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off))
37 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
38 #define ll_next(node) CX_LL_PTR(node, loc_next)
39 #define ll_advance(node) CX_LL_PTR(node, loc_advance)
40 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
37 41
38 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) { 42 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
39 assert(start != NULL); 43 assert(start != NULL);
40 assert(loc_advance >= 0); 44 assert(loc_advance >= 0);
41 size_t i = start_index; 45 size_t i = start_index;
42 void *cur = start; 46 void *cur = start;
43 while (i != index && cur != NULL) { 47 while (i != index && cur != NULL) {
44 cur = CX_LL_PTR(cur, loc_advance); 48 cur = ll_advance(cur);
45 i < index ? i++ : i--; 49 i < index ? i++ : i--;
46 } 50 }
47 return cur; 51 return cur;
52 }
53
54 size_t cx_linked_list_find(void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, int follow_ptr,
55 CxListComparator cmp_func, void *elem) {
56 assert(start != NULL);
57 assert(loc_advance >= 0);
58 assert(loc_data >= 0);
59 assert(cmp_func);
60
61 void *node = start;
62 size_t index = 0;
63 do {
64 void *current = ll_data(node);
65 if (cmp_func(current, elem) == 0) {
66 return index;
67 }
68 node = ll_advance(node);
69 index++;
70 } while (node != NULL);
71 return index;
48 } 72 }
49 73
50 void *cx_linked_list_first(void *node, ptrdiff_t loc_prev) { 74 void *cx_linked_list_first(void *node, ptrdiff_t loc_prev) {
51 return cx_linked_list_last(node, loc_prev); 75 return cx_linked_list_last(node, loc_prev);
52 } 76 }
57 81
58 void *cur = node; 82 void *cur = node;
59 void *last; 83 void *last;
60 do { 84 do {
61 last = cur; 85 last = cur;
62 } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL); 86 } while ((cur = ll_next(cur)) != NULL);
63 87
64 return last; 88 return last;
65 } 89 }
66 90
67 void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node) { 91 void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node) {
70 assert(loc_next >= 0); 94 assert(loc_next >= 0);
71 if (begin == node) return NULL; 95 if (begin == node) return NULL;
72 void *cur = begin; 96 void *cur = begin;
73 void *next; 97 void *next;
74 while (1) { 98 while (1) {
75 next = CX_LL_PTR(cur, loc_next); 99 next = ll_next(cur);
76 if (next == node) return cur; 100 if (next == node) return cur;
77 cur = next; 101 cur = next;
78 } 102 }
79 } 103 }
80 104
81 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { 105 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
82 assert(new_node != NULL); 106 assert(new_node != NULL);
83 assert(loc_next >= 0); 107 assert(loc_next >= 0);
84 assert(CX_LL_PTR(new_node, loc_next) == NULL); 108 assert(ll_next(new_node) == NULL);
85 void *last; 109 void *last;
86 if (end == NULL) { 110 if (end == NULL) {
87 assert(begin != NULL); 111 assert(begin != NULL);
88 last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next); 112 last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next);
89 } else { 113 } else {
93 if (begin != NULL) { 117 if (begin != NULL) {
94 *begin = new_node; 118 *begin = new_node;
95 } 119 }
96 } else { 120 } else {
97 // if there is a last node, update its next pointer 121 // if there is a last node, update its next pointer
98 CX_LL_PTR(last, loc_next) = new_node; 122 ll_next(last) = new_node;
99 } 123 }
100 124
101 // if there is an end pointer, update it 125 // if there is an end pointer, update it
102 if (end != NULL) { 126 if (end != NULL) {
103 *end = new_node; 127 *end = new_node;
104 } 128 }
105 129
106 // if the nodes use a prev pointer, update it 130 // if the nodes use a prev pointer, update it
107 if (loc_prev >= 0) { 131 if (loc_prev >= 0) {
108 assert(CX_LL_PTR(new_node, loc_prev) == NULL); 132 assert(ll_prev(new_node) == NULL);
109 CX_LL_PTR(new_node, loc_prev) = last; 133 ll_prev(new_node) = last;
110 } 134 }
111 } 135 }
112 136
113 void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { 137 void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
114 assert(new_node != NULL); 138 assert(new_node != NULL);
115 assert(loc_next >= 0); 139 assert(loc_next >= 0);
116 assert(CX_LL_PTR(new_node, loc_next) == NULL); 140 assert(ll_next(new_node) == NULL);
117 void *first; 141 void *first;
118 if (begin == NULL) { 142 if (begin == NULL) {
119 assert(end != NULL); 143 assert(end != NULL);
120 assert(loc_prev >= 0); 144 assert(loc_prev >= 0);
121 first = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev); 145 first = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev);
125 if (first == NULL) { 149 if (first == NULL) {
126 if (end != NULL) { 150 if (end != NULL) {
127 *end = new_node; 151 *end = new_node;
128 } 152 }
129 } else { 153 } else {
130 CX_LL_PTR(new_node, loc_next) = first; 154 ll_next(new_node) = first;
131 if (loc_prev >= 0) { 155 if (loc_prev >= 0) {
132 CX_LL_PTR(first, loc_prev) = new_node; 156 ll_prev(first) = new_node;
133 } 157 }
134 } 158 }
135 159
136 if (begin != NULL) { 160 if (begin != NULL) {
137 assert(loc_prev < 0 || CX_LL_PTR(new_node, loc_prev) == NULL); 161 assert(loc_prev < 0 || ll_prev(new_node) == NULL);
138 *begin = new_node; 162 *begin = new_node;
139 } 163 }
140 } 164 }
141 165
142 void cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) { 166 void cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) {
143 assert(node != NULL); 167 assert(node != NULL);
144 assert(loc_next >= 0); 168 assert(loc_next >= 0);
145 assert(loc_prev >= 0 || begin != NULL); 169 assert(loc_prev >= 0 || begin != NULL);
146 170
147 // find adjacent nodes 171 // find adjacent nodes
148 void *next = CX_LL_PTR(node, loc_next); 172 void *next = ll_next(node);
149 void *prev; 173 void *prev;
150 if (loc_prev >= 0) { 174 if (loc_prev >= 0) {
151 prev = CX_LL_PTR(node, loc_prev); 175 prev = ll_prev(node);
152 } else { 176 } else {
153 prev = cx_linked_list_prev(*begin, loc_next, node); 177 prev = cx_linked_list_prev(*begin, loc_next, node);
154 } 178 }
155 179
156 // update next pointer of prev node, or set begin 180 // update next pointer of prev node, or set begin
157 if (prev == NULL) { 181 if (prev == NULL) {
158 if (begin != NULL) { 182 if (begin != NULL) {
159 *begin = next; 183 *begin = next;
160 } 184 }
161 } else { 185 } else {
162 CX_LL_PTR(prev, loc_next) = next; 186 ll_next(prev) = next;
163 } 187 }
164 188
165 // update prev pointer of next node, or set end 189 // update prev pointer of next node, or set end
166 if (next == NULL) { 190 if (next == NULL) {
167 if (end != NULL) { 191 if (end != NULL) {
168 *end = prev; 192 *end = prev;
169 } 193 }
170 } else if (loc_prev >= 0) { 194 } else if (loc_prev >= 0) {
171 CX_LL_PTR(next, loc_prev) = prev; 195 ll_prev(next) = prev;
172 } 196 }
173 } 197 }
174 198
175 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) { 199 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
176 assert(loc_next >= 0); 200 assert(loc_next >= 0);
177 size_t size = 0; 201 size_t size = 0;
178 while (node != NULL) { 202 while (node != NULL) {
179 node = CX_LL_PTR(node, loc_next); 203 node = ll_next(node);
180 size++; 204 size++;
181 } 205 }
182 return size; 206 return size;
183 } 207 }
184
185 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
186 #define ll_next(node) CX_LL_PTR(node, loc_next)
187 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
188 208
189 static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next, 209 static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,
190 ptrdiff_t loc_data, int follow_ptr, 210 ptrdiff_t loc_data, int follow_ptr,
191 size_t length, void *ls, void *le, void *re, 211 size_t length, void *ls, void *le, void *re,
192 CxListComparator cmp_func) { 212 CxListComparator cmp_func) {
288 } 308 }
289 if (end) *end = cx_linked_list_last(sorted, loc_next); 309 if (end) *end = cx_linked_list_last(sorted, loc_next);
290 } 310 }
291 } 311 }
292 312
293 #undef ll_next
294 #undef ll_data
295
296 void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) { 313 void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) {
297 assert(begin != NULL); 314 assert(begin != NULL);
298 assert(loc_next >= 0); 315 assert(loc_next >= 0);
299 316
300 // swap all links 317 // swap all links
301 void *prev = NULL; 318 void *prev = NULL;
302 void *cur = *begin; 319 void *cur = *begin;
303 while (cur != NULL) { 320 while (cur != NULL) {
304 void *next = CX_LL_PTR(cur, loc_next); 321 void *next = ll_next(cur);
305 322
306 CX_LL_PTR(cur, loc_next) = prev; 323 ll_next(cur) = prev;
307 if (loc_prev >= 0) { 324 if (loc_prev >= 0) {
308 CX_LL_PTR(cur, loc_prev) = next; 325 ll_prev(cur) = next;
309 } 326 }
310 327
311 prev = cur; 328 prev = cur;
312 cur = next; 329 cur = next;
313 } 330 }
444 cx_linked_list_node *node = cx_ll_node_at(ll, index); 461 cx_linked_list_node *node = cx_ll_node_at(ll, index);
445 return node == NULL ? NULL : *(void **) node->payload; 462 return node == NULL ? NULL : *(void **) node->payload;
446 } 463 }
447 464
448 static size_t cx_ll_find(cx_list_s *list, void *elem) { 465 static size_t cx_ll_find(cx_list_s *list, void *elem) {
449 CxListComparator cmp = list->cmpfunc; 466 return cx_linked_list_find(((cx_linked_list *) list)->begin,
450 cx_linked_list *ll = (cx_linked_list *) list; 467 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
451 468 0, list->cmpfunc, elem);
452 size_t index;
453 cx_linked_list_node *node = ll->begin;
454 for (index = 0; index < list->size; index++) {
455 void *current = node->payload;
456 if (cmp(current, elem) == 0) {
457 return index;
458 }
459 node = node->next;
460 }
461 return index;
462 } 469 }
463 470
464 static size_t cx_pll_find(cx_list_s *list, void *elem) { 471 static size_t cx_pll_find(cx_list_s *list, void *elem) {
465 CxListComparator cmp = list->cmpfunc; 472 return cx_linked_list_find(((cx_linked_list *) list)->begin,
466 cx_linked_list *ll = (cx_linked_list *) list; 473 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
467 474 1, list->cmpfunc, elem);
468 size_t index;
469 cx_linked_list_node *node = ll->begin;
470 for (index = 0; index < list->size; index++) {
471 void *current = *(void **) node->payload;
472 if (cmp(current, elem) == 0) {
473 return index;
474 }
475 node = node->next;
476 }
477 return index;
478 } 475 }
479 476
480 static void cx_ll_sort(cx_list_s *list) { 477 static void cx_ll_sort(cx_list_s *list) {
481 cx_linked_list *ll = (cx_linked_list *) list; 478 cx_linked_list *ll = (cx_linked_list *) list;
482 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, 479 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,

Mercurial Repository: ucx

mercurial