Mercurial > hg > ucx / file comparison

comparison: ucx/dlist.c

ucx/dlist.c

changeset 67
27e67e725d35
parent 37
ec296899d12f
child 69
fb59270b1de3
equal deleted inserted replaced
66:fcfe8c5e9fe1 67:27e67e725d35
1 #include "dlist.h" 1 #include "dlist.h"
2 2
3 UcxDlist *ucx_dlist_clone(UcxDlist *l, copy_func fnc, void *data) { 3 UcxDlist *restrict ucx_dlist_clone(UcxDlist *restrict l,
4 copy_func fnc, void *data) {
4 UcxDlist *ret = NULL; 5 UcxDlist *ret = NULL;
5 while (l != NULL) { 6 while (l != NULL) {
6 if (fnc != NULL) { 7 if (fnc != NULL) {
7 ret = ucx_dlist_append(ret, fnc(l->data, data)); 8 ret = ucx_dlist_append(ret, fnc(l->data, data));
8 } else { 9 } else {
11 l = l->next; 12 l = l->next;
12 } 13 }
13 return ret; 14 return ret;
14 } 15 }
15 16
16 int ucx_dlist_equals(UcxDlist *l1, UcxDlist *l2, cmp_func fnc, void* data) { 17 int ucx_dlist_equals(const UcxDlist *l1, const UcxDlist *l2,
18 cmp_func fnc, void* data) {
17 if (l1 == l2) return 1; 19 if (l1 == l2) return 1;
18 20
19 while (l1 != NULL && l2 != NULL) { 21 while (l1 != NULL && l2 != NULL) {
20 if (fnc == NULL) { 22 if (fnc == NULL) {
21 if (l1->data != l2->data) return 0; 23 if (l1->data != l2->data) return 0;
64 l->prev = nl; 66 l->prev = nl;
65 } 67 }
66 return nl; 68 return nl;
67 } 69 }
68 70
69 UcxDlist *ucx_dlist_concat(UcxDlist *l1, UcxDlist *l2) { 71 UcxDlist *ucx_dlist_concat(UcxDlist *restrict l1, UcxDlist *restrict l2) {
70 if (l1 == NULL) { 72 if (l1 == NULL) {
71 return l2; 73 return l2;
72 } else { 74 } else {
73 UcxDlist *last = ucx_dlist_last(l1); 75 UcxDlist *last = ucx_dlist_last(l1);
74 last->next = l2; 76 last->next = l2;
75 l2->prev = last; 77 l2->prev = last;
76 return l1; 78 return l1;
77 } 79 }
78 } 80 }
79 81
80 UcxDlist *ucx_dlist_last(UcxDlist *l) { 82 UcxDlist *ucx_dlist_last(const UcxDlist *l) {
81 if (l == NULL) return NULL; 83 if (l == NULL) return NULL;
82 84
83 UcxDlist *e = l; 85 const UcxDlist *e = l;
84 while (e->next != NULL) { 86 while (e->next != NULL) {
85 e = e->next; 87 e = e->next;
86 } 88 }
87 return e; 89 return (UcxDlist*)e;
88 } 90 }
89 91
90 UcxDlist *ucx_dlist_get(UcxDlist *l, int index) { 92 UcxDlist *ucx_dlist_get(const UcxDlist *l, int index) {
91 if (l == NULL) return NULL; 93 if (l == NULL) return NULL;
92 94
93 UcxDlist *e = l; 95 const UcxDlist *e = l;
94 while (e->next != NULL && index > 0) { 96 while (e->next != NULL && index > 0) {
95 e = e->next; 97 e = e->next;
96 index--; 98 index--;
97 } 99 }
98 100
99 return index == 0 ? e : NULL; 101 return (UcxDlist*)(index == 0 ? e : NULL);
100 } 102 }
101 103
102 size_t ucx_dlist_size(UcxDlist *l) { 104 size_t ucx_dlist_size(const UcxDlist *l) {
103 if (l == NULL) return 0; 105 if (l == NULL) return 0;
104 106
105 UcxDlist *e = l; 107 const UcxDlist *e = l;
106 size_t s = 1; 108 size_t s = 1;
107 while (e->next != NULL) { 109 while (e->next != NULL) {
108 e = e->next; 110 e = e->next;
109 s++; 111 s++;
110 } 112 }
111 113
112 return s; 114 return s;
113 } 115 }
114 116
115 UcxDlist *ucx_dlist_sort_merge(int length, 117 UcxDlist *ucx_dlist_sort_merge(int length,
116 UcxDlist* ls, UcxDlist* rs, UcxDlist* le, UcxDlist* re, 118 UcxDlist* restrict ls, UcxDlist* restrict le, UcxDlist* restrict re,
117 cmp_func fnc, void* data) { 119 cmp_func fnc, void* data) {
118 UcxDlist *sorted[length]; 120 UcxDlist *sorted[length];
119 UcxDlist *rc, *lc; 121 UcxDlist *rc, *lc;
120 122
121 lc = ls; rc = rs; 123 lc = ls; rc = le;
122 int n = 0; 124 int n = 0;
123 while (lc != le && rc != re) { 125 while (lc && lc != le && rc != re) {
124 if (fnc(lc->data, rc->data, data) <= 0) { 126 if (fnc(lc->data, rc->data, data) <= 0) {
125 sorted[n] = lc; 127 sorted[n] = lc;
126 lc = lc->next; 128 lc = lc->next;
127 } else { 129 } else {
128 sorted[n] = rc; 130 sorted[n] = rc;
129 rc = rc->next; 131 rc = rc->next;
130 } 132 }
131 n++; 133 n++;
132 } 134 }
133 while (lc != le) { 135 while (lc && lc != le) {
134 sorted[n] = lc; 136 sorted[n] = lc;
135 lc = lc->next; 137 lc = lc->next;
136 n++; 138 n++;
137 } 139 }
138 while (rc != re) { 140 while (rc && rc != re) {
139 sorted[n] = rc; 141 sorted[n] = rc;
140 rc = rc->next; 142 rc = rc->next;
141 n++; 143 n++;
142 } 144 }
143 145
158 } 160 }
159 161
160 UcxDlist *lc; 162 UcxDlist *lc;
161 int ln = 1; 163 int ln = 1;
162 164
163 UcxDlist *ls = l, *le; 165 UcxDlist *restrict ls = l, *restrict le, *restrict re;
164 lc = ls; 166 lc = ls;
165 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) { 167 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
166 lc = lc->next; 168 lc = lc->next;
167 ln++; 169 ln++;
168 } 170 }
169 le = lc->next; 171 le = lc->next;
170 172
171 UcxDlist *rs = le, *re; 173 if (le == NULL) {
172 if (rs == NULL) {
173 return l; // this list is already sorted :) 174 return l; // this list is already sorted :)
174 } else { 175 } else {
175 UcxDlist *rc; 176 UcxDlist *rc;
176 int rn = 1; 177 int rn = 1;
177 rc = rs; 178 rc = le;
178 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { 179 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
179 rc = rc->next; 180 rc = rc->next;
180 rn++; 181 rn++;
181 } 182 }
182 re = rc->next; 183 re = rc->next;
188 remainder = ucx_dlist_sort(remainder, fnc, data); 189 remainder = ucx_dlist_sort(remainder, fnc, data);
189 } 190 }
190 191
191 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them 192 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
192 UcxDlist *sorted = ucx_dlist_sort_merge(ln+rn, 193 UcxDlist *sorted = ucx_dlist_sort_merge(ln+rn,
193 ls, rs, le, re, 194 ls, le, re,
194 fnc, data); 195 fnc, data);
195 196
196 // merge sorted list with (also sorted) remainder 197 // merge sorted list with (also sorted) remainder
197 l = ucx_dlist_sort_merge(ln+rn+remainder_length, 198 l = ucx_dlist_sort_merge(ln+rn+remainder_length,
198 sorted, remainder, NULL, NULL, 199 sorted, remainder, NULL, fnc, data);
199 fnc, data);
200 200
201 return l; 201 return l;
202 } 202 }
203 } 203 }
204 204
205 /* dlist specific functions */ 205 /* dlist specific functions */
206 UcxDlist *ucx_dlist_first(UcxDlist *l) { 206 UcxDlist *ucx_dlist_first(const UcxDlist *l) {
207 if (l == NULL) return NULL; 207 if (l == NULL) return NULL;
208 208
209 UcxDlist *e = l; 209 const UcxDlist *e = l;
210 while (e->prev != NULL) { 210 while (e->prev != NULL) {
211 e = e->prev; 211 e = e->prev;
212 } 212 }
213 return e; 213 return (UcxDlist *)e;
214 } 214 }
215 215
216 UcxDlist *ucx_dlist_remove(UcxDlist *l, UcxDlist *e) { 216 UcxDlist *ucx_dlist_remove(UcxDlist *l, UcxDlist *e) {
217 if (e->prev == NULL) { 217 if (e->prev == NULL) {
218 if(e->next != NULL) { 218 if(e->next != NULL) {

Mercurial Repository: ucx

mercurial