comparison: ucx/list.c
ucx/list.c
- changeset 1
- 1bcaac272cdf
- child 5
- 88625853ae74
equal
deleted
inserted
replaced
| 0:0f94d369bb02 | 1:1bcaac272cdf |
|---|---|
| 1 #include "list.h" | |
| 2 | |
| 3 UcxList *restrict ucx_list_clone(UcxList *restrict l, | |
| 4 copy_func fnc, void *data) { | |
| 5 UcxList *ret = NULL; | |
| 6 while (l != NULL) { | |
| 7 if (fnc != NULL) { | |
| 8 ret = ucx_list_append(ret, fnc(l->data, data)); | |
| 9 } else { | |
| 10 ret = ucx_list_append(ret, l->data); | |
| 11 } | |
| 12 l = l->next; | |
| 13 } | |
| 14 return ret; | |
| 15 } | |
| 16 | |
| 17 int ucx_list_equals(const UcxList *l1, const UcxList *l2, | |
| 18 cmp_func fnc, void* data) { | |
| 19 if (l1 == l2) return 1; | |
| 20 | |
| 21 while (l1 != NULL && l2 != NULL) { | |
| 22 if (fnc == NULL) { | |
| 23 if (l1->data != l2->data) return 0; | |
| 24 } else { | |
| 25 if (fnc(l1->data, l2->data, data) != 0) return 0; | |
| 26 } | |
| 27 l1 = l1->next; | |
| 28 l2 = l2->next; | |
| 29 } | |
| 30 | |
| 31 return (l1 == NULL && l2 == NULL); | |
| 32 } | |
| 33 | |
| 34 void ucx_list_free(UcxList *l) { | |
| 35 UcxList *e = l, *f; | |
| 36 while (e != NULL) { | |
| 37 f = e; | |
| 38 e = e->next; | |
| 39 free(f); | |
| 40 } | |
| 41 } | |
| 42 | |
| 43 UcxList *ucx_list_append(UcxList *l, void *data) { | |
| 44 UcxList *nl = (UcxList*) malloc(sizeof(UcxList)); | |
| 45 if (nl == NULL) return NULL; | |
| 46 | |
| 47 nl->data = data; | |
| 48 nl->next = NULL; | |
| 49 if (l == NULL) { | |
| 50 return nl; | |
| 51 } else { | |
| 52 UcxList *t = ucx_list_last(l); | |
| 53 t->next = nl; | |
| 54 return l; | |
| 55 } | |
| 56 } | |
| 57 | |
| 58 UcxList *ucx_list_prepend(UcxList *l, void *data) { | |
| 59 UcxList *nl = ucx_list_append(NULL, data); | |
| 60 if (nl == NULL) return NULL; | |
| 61 | |
| 62 if (l != NULL) { | |
| 63 nl->next = l; | |
| 64 } | |
| 65 return nl; | |
| 66 } | |
| 67 | |
| 68 UcxList *ucx_list_concat(UcxList *restrict l1, UcxList *restrict l2) { | |
| 69 if (l1 == NULL) { | |
| 70 return l2; | |
| 71 } else { | |
| 72 UcxList *last = ucx_list_last(l1); | |
| 73 last->next = l2; | |
| 74 return l1; | |
| 75 } | |
| 76 } | |
| 77 | |
| 78 UcxList *ucx_list_last(const UcxList *l) { | |
| 79 if (l == NULL) return NULL; | |
| 80 | |
| 81 const UcxList *e = l; | |
| 82 while (e->next != NULL) { | |
| 83 e = e->next; | |
| 84 } | |
| 85 return (UcxList*)e; | |
| 86 } | |
| 87 | |
| 88 UcxList *ucx_list_get(const UcxList *l, int index) { | |
| 89 if (l == NULL) return NULL; | |
| 90 | |
| 91 const UcxList *e = l; | |
| 92 while (e->next != NULL && index > 0) { | |
| 93 e = e->next; | |
| 94 index--; | |
| 95 } | |
| 96 | |
| 97 return (UcxList*)(index == 0 ? e : NULL); | |
| 98 } | |
| 99 | |
| 100 size_t ucx_list_size(const UcxList *l) { | |
| 101 if (l == NULL) return 0; | |
| 102 | |
| 103 const UcxList *e = l; | |
| 104 size_t s = 1; | |
| 105 while (e->next != NULL) { | |
| 106 e = e->next; | |
| 107 s++; | |
| 108 } | |
| 109 | |
| 110 return s; | |
| 111 } | |
| 112 | |
| 113 UcxList *ucx_list_sort_merge(int length, | |
| 114 UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re, | |
| 115 cmp_func fnc, void* data) { | |
| 116 | |
| 117 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length); | |
| 118 UcxList *rc, *lc; | |
| 119 | |
| 120 lc = ls; rc = le; | |
| 121 int n = 0; | |
| 122 while (lc && lc != le && rc != re) { | |
| 123 if (fnc(lc->data, rc->data, data) <= 0) { | |
| 124 sorted[n] = lc; | |
| 125 lc = lc->next; | |
| 126 } else { | |
| 127 sorted[n] = rc; | |
| 128 rc = rc->next; | |
| 129 } | |
| 130 n++; | |
| 131 } | |
| 132 while (lc && lc != le) { | |
| 133 sorted[n] = lc; | |
| 134 lc = lc->next; | |
| 135 n++; | |
| 136 } | |
| 137 while (rc && rc != re) { | |
| 138 sorted[n] = rc; | |
| 139 rc = rc->next; | |
| 140 n++; | |
| 141 } | |
| 142 | |
| 143 // Update pointer | |
| 144 for (int i = 0 ; i < length-1 ; i++) { | |
| 145 sorted[i]->next = sorted[i+1]; | |
| 146 } | |
| 147 sorted[length-1]->next = NULL; | |
| 148 | |
| 149 UcxList *ret = sorted[0]; | |
| 150 free(sorted); | |
| 151 return ret; | |
| 152 } | |
| 153 | |
| 154 UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) { | |
| 155 if (l == NULL) { | |
| 156 return NULL; | |
| 157 } | |
| 158 | |
| 159 UcxList *lc; | |
| 160 int ln = 1; | |
| 161 | |
| 162 UcxList *restrict ls = l, *restrict le, *restrict re; | |
| 163 lc = ls; | |
| 164 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) { | |
| 165 lc = lc->next; | |
| 166 ln++; | |
| 167 } | |
| 168 le = lc->next; | |
| 169 | |
| 170 if (le == NULL) { | |
| 171 return l; // this list is already sorted :) | |
| 172 } else { | |
| 173 UcxList *rc; | |
| 174 int rn = 1; | |
| 175 rc = le; | |
| 176 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { | |
| 177 rc = rc->next; | |
| 178 rn++; | |
| 179 } | |
| 180 re = rc->next; | |
| 181 | |
| 182 // Something left? Sort it! | |
| 183 UcxList *remainder = re; | |
| 184 size_t remainder_length = ucx_list_size(remainder); | |
| 185 if (remainder != NULL) { | |
| 186 remainder = ucx_list_sort(remainder, fnc, data); | |
| 187 } | |
| 188 | |
| 189 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them | |
| 190 UcxList *sorted = ucx_list_sort_merge(ln+rn, | |
| 191 ls, le, re, | |
| 192 fnc, data); | |
| 193 | |
| 194 // merge sorted list with (also sorted) remainder | |
| 195 l = ucx_list_sort_merge(ln+rn+remainder_length, | |
| 196 sorted, remainder, NULL, fnc, data); | |
| 197 | |
| 198 return l; | |
| 199 } | |
| 200 } | |
| 201 | |
| 202 /* list specific functions */ | |
| 203 UcxList *ucx_list_remove(UcxList *l, UcxList *e) { | |
| 204 if (e == l) { | |
| 205 l = e->next; | |
| 206 free(e); | |
| 207 } else { | |
| 208 UcxList *f = l; | |
| 209 while (f->next != NULL && f->next != e) { | |
| 210 f = f->next; | |
| 211 } | |
| 212 /* perform remove if this element is found in this list */ | |
| 213 if (f->next == e) { | |
| 214 f->next = e->next; | |
| 215 free(e); | |
| 216 } | |
| 217 } | |
| 218 return l; | |
| 219 } |
