Mercurial > hg > ucx / file comparison

comparison: ucx/list.c

ucx/list.c

changeset 67
27e67e725d35
parent 37
ec296899d12f
child 69
fb59270b1de3
equal deleted inserted replaced
66:fcfe8c5e9fe1 67:27e67e725d35
1 #include "list.h" 1 #include "list.h"
2 2
3 UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) { 3 UcxList *restrict ucx_list_clone(UcxList *restrict l,
4 copy_func fnc, void *data) {
4 UcxList *ret = NULL; 5 UcxList *ret = NULL;
5 while (l != NULL) { 6 while (l != NULL) {
6 if (fnc != NULL) { 7 if (fnc != NULL) {
7 ret = ucx_list_append(ret, fnc(l->data, data)); 8 ret = ucx_list_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_list_equals(UcxList *l1, UcxList *l2, cmp_func fnc, void* data) { 17 int ucx_list_equals(const UcxList *l1, const UcxList *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;
61 nl->next = l; 63 nl->next = l;
62 } 64 }
63 return nl; 65 return nl;
64 } 66 }
65 67
66 UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) { 68 UcxList *ucx_list_concat(UcxList *restrict l1, UcxList *restrict l2) {
67 if (l1 == NULL) { 69 if (l1 == NULL) {
68 return l2; 70 return l2;
69 } else { 71 } else {
70 UcxList *last = ucx_list_last(l1); 72 UcxList *last = ucx_list_last(l1);
71 last->next = l2; 73 last->next = l2;
72 return l1; 74 return l1;
73 } 75 }
74 } 76 }
75 77
76 UcxList *ucx_list_last(UcxList *l) { 78 UcxList *ucx_list_last(const UcxList *l) {
77 if (l == NULL) return NULL; 79 if (l == NULL) return NULL;
78 80
79 UcxList *e = l; 81 const UcxList *e = l;
80 while (e->next != NULL) { 82 while (e->next != NULL) {
81 e = e->next; 83 e = e->next;
82 } 84 }
83 return e; 85 return (UcxList*)e;
84 } 86 }
85 87
86 UcxList *ucx_list_get(UcxList *l, int index) { 88 UcxList *ucx_list_get(const UcxList *l, int index) {
87 if (l == NULL) return NULL; 89 if (l == NULL) return NULL;
88 90
89 UcxList *e = l; 91 const UcxList *e = l;
90 while (e->next != NULL && index > 0) { 92 while (e->next != NULL && index > 0) {
91 e = e->next; 93 e = e->next;
92 index--; 94 index--;
93 } 95 }
94 96
95 return index == 0 ? e : NULL; 97 return (UcxList*)(index == 0 ? e : NULL);
96 } 98 }
97 99
98 size_t ucx_list_size(UcxList *l) { 100 size_t ucx_list_size(const UcxList *l) {
99 if (l == NULL) return 0; 101 if (l == NULL) return 0;
100 102
101 UcxList *e = l; 103 const UcxList *e = l;
102 size_t s = 1; 104 size_t s = 1;
103 while (e->next != NULL) { 105 while (e->next != NULL) {
104 e = e->next; 106 e = e->next;
105 s++; 107 s++;
106 } 108 }
107 109
108 return s; 110 return s;
109 } 111 }
110 112
111 UcxList *ucx_list_sort_merge(int length, 113 UcxList *ucx_list_sort_merge(int length,
112 UcxList* ls, UcxList* rs, UcxList* le, UcxList* re, 114 UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re,
113 cmp_func fnc, void* data) { 115 cmp_func fnc, void* data) {
114 UcxList *sorted[length]; 116 UcxList *sorted[length];
115 UcxList *rc, *lc; 117 UcxList *rc, *lc;
116 118
117 lc = ls; rc = rs; 119 lc = ls; rc = le;
118 int n = 0; 120 int n = 0;
119 while (lc != le && rc != re) { 121 while (lc && lc != le && rc != re) {
120 if (fnc(lc->data, rc->data, data) <= 0) { 122 if (fnc(lc->data, rc->data, data) <= 0) {
121 sorted[n] = lc; 123 sorted[n] = lc;
122 lc = lc->next; 124 lc = lc->next;
123 } else { 125 } else {
124 sorted[n] = rc; 126 sorted[n] = rc;
125 rc = rc->next; 127 rc = rc->next;
126 } 128 }
127 n++; 129 n++;
128 } 130 }
129 while (lc != le) { 131 while (lc && lc != le) {
130 sorted[n] = lc; 132 sorted[n] = lc;
131 lc = lc->next; 133 lc = lc->next;
132 n++; 134 n++;
133 } 135 }
134 while (rc != re) { 136 while (rc && rc != re) {
135 sorted[n] = rc; 137 sorted[n] = rc;
136 rc = rc->next; 138 rc = rc->next;
137 n++; 139 n++;
138 } 140 }
139 141
152 } 154 }
153 155
154 UcxList *lc; 156 UcxList *lc;
155 int ln = 1; 157 int ln = 1;
156 158
157 UcxList *ls = l, *le; 159 UcxList *restrict ls = l, *restrict le, *restrict re;
158 lc = ls; 160 lc = ls;
159 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) { 161 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
160 lc = lc->next; 162 lc = lc->next;
161 ln++; 163 ln++;
162 } 164 }
163 le = lc->next; 165 le = lc->next;
164 166
165 UcxList *rs = le, *re; 167 if (le == NULL) {
166 if (rs == NULL) {
167 return l; // this list is already sorted :) 168 return l; // this list is already sorted :)
168 } else { 169 } else {
169 UcxList *rc; 170 UcxList *rc;
170 int rn = 1; 171 int rn = 1;
171 rc = rs; 172 rc = le;
172 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { 173 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
173 rc = rc->next; 174 rc = rc->next;
174 rn++; 175 rn++;
175 } 176 }
176 re = rc->next; 177 re = rc->next;
182 remainder = ucx_list_sort(remainder, fnc, data); 183 remainder = ucx_list_sort(remainder, fnc, data);
183 } 184 }
184 185
185 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them 186 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
186 UcxList *sorted = ucx_list_sort_merge(ln+rn, 187 UcxList *sorted = ucx_list_sort_merge(ln+rn,
187 ls, rs, le, re, 188 ls, le, re,
188 fnc, data); 189 fnc, data);
189 190
190 // merge sorted list with (also sorted) remainder 191 // merge sorted list with (also sorted) remainder
191 l = ucx_list_sort_merge(ln+rn+remainder_length, 192 l = ucx_list_sort_merge(ln+rn+remainder_length,
192 sorted, remainder, NULL, NULL, 193 sorted, remainder, NULL, fnc, data);
193 fnc, data);
194 194
195 return l; 195 return l;
196 } 196 }
197 } 197 }
198 198

Mercurial Repository: ucx

mercurial