comparison: ucx/list.c
ucx/list.c
- changeset 121
- 311cac04d079
- parent 103
- 08018864fb91
equal
deleted
inserted
replaced
| 120:8170f658f017 | 121:311cac04d079 |
|---|---|
| 1 /* | |
| 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. | |
| 3 * | |
| 4 * Copyright 2013 Olaf Wintermann. All rights reserved. | |
| 5 * | |
| 6 * Redistribution and use in source and binary forms, with or without | |
| 7 * modification, are permitted provided that the following conditions are met: | |
| 8 * | |
| 9 * 1. Redistributions of source code must retain the above copyright | |
| 10 * notice, this list of conditions and the following disclaimer. | |
| 11 * | |
| 12 * 2. Redistributions in binary form must reproduce the above copyright | |
| 13 * notice, this list of conditions and the following disclaimer in the | |
| 14 * documentation and/or other materials provided with the distribution. | |
| 15 * | |
| 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | |
| 17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
| 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
| 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE | |
| 20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | |
| 21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | |
| 22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | |
| 23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | |
| 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
| 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | |
| 26 * POSSIBILITY OF SUCH DAMAGE. | |
| 27 */ | |
| 28 | |
| 29 #include "list.h" | |
| 30 | |
| 31 UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) { | |
| 32 UcxList *ret = NULL; | |
| 33 while (l != NULL) { | |
| 34 if (fnc != NULL) { | |
| 35 ret = ucx_list_append(ret, fnc(l->data, data)); | |
| 36 } else { | |
| 37 ret = ucx_list_append(ret, l->data); | |
| 38 } | |
| 39 l = l->next; | |
| 40 } | |
| 41 return ret; | |
| 42 } | |
| 43 | |
| 44 int ucx_list_equals(const UcxList *l1, const UcxList *l2, | |
| 45 cmp_func fnc, void* data) { | |
| 46 if (l1 == l2) return 1; | |
| 47 | |
| 48 while (l1 != NULL && l2 != NULL) { | |
| 49 if (fnc == NULL) { | |
| 50 if (l1->data != l2->data) return 0; | |
| 51 } else { | |
| 52 if (fnc(l1->data, l2->data, data) != 0) return 0; | |
| 53 } | |
| 54 l1 = l1->next; | |
| 55 l2 = l2->next; | |
| 56 } | |
| 57 | |
| 58 return (l1 == NULL && l2 == NULL); | |
| 59 } | |
| 60 | |
| 61 void ucx_list_free(UcxList *l) { | |
| 62 UcxList *e = l, *f; | |
| 63 while (e != NULL) { | |
| 64 f = e; | |
| 65 e = e->next; | |
| 66 free(f); | |
| 67 } | |
| 68 } | |
| 69 | |
| 70 UcxList *ucx_list_append(UcxList *l, void *data) { | |
| 71 UcxList *nl = (UcxList*) malloc(sizeof(UcxList)); | |
| 72 if (nl == NULL) return NULL; | |
| 73 | |
| 74 nl->data = data; | |
| 75 nl->next = NULL; | |
| 76 if (l == NULL) { | |
| 77 return nl; | |
| 78 } else { | |
| 79 UcxList *t = ucx_list_last(l); | |
| 80 t->next = nl; | |
| 81 return l; | |
| 82 } | |
| 83 } | |
| 84 | |
| 85 UcxList *ucx_list_prepend(UcxList *l, void *data) { | |
| 86 UcxList *nl = ucx_list_append(NULL, data); | |
| 87 if (nl == NULL) return NULL; | |
| 88 | |
| 89 if (l != NULL) { | |
| 90 nl->next = l; | |
| 91 } | |
| 92 return nl; | |
| 93 } | |
| 94 | |
| 95 UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) { | |
| 96 if (l1 == NULL) { | |
| 97 return l2; | |
| 98 } else { | |
| 99 UcxList *last = ucx_list_last(l1); | |
| 100 last->next = l2; | |
| 101 return l1; | |
| 102 } | |
| 103 } | |
| 104 | |
| 105 UcxList *ucx_list_last(const UcxList *l) { | |
| 106 if (l == NULL) return NULL; | |
| 107 | |
| 108 const UcxList *e = l; | |
| 109 while (e->next != NULL) { | |
| 110 e = e->next; | |
| 111 } | |
| 112 return (UcxList*)e; | |
| 113 } | |
| 114 | |
| 115 UcxList *ucx_list_get(const UcxList *l, int index) { | |
| 116 if (l == NULL) return NULL; | |
| 117 | |
| 118 const UcxList *e = l; | |
| 119 while (e->next != NULL && index > 0) { | |
| 120 e = e->next; | |
| 121 index--; | |
| 122 } | |
| 123 | |
| 124 return (UcxList*)(index == 0 ? e : NULL); | |
| 125 } | |
| 126 | |
| 127 int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) { | |
| 128 UCX_FOREACH(UcxList*, l, e) { | |
| 129 if (!fnc(elem, e->data, cmpdata)) { | |
| 130 return 1; | |
| 131 } | |
| 132 } | |
| 133 return 0; | |
| 134 } | |
| 135 | |
| 136 size_t ucx_list_size(const UcxList *l) { | |
| 137 if (l == NULL) return 0; | |
| 138 | |
| 139 const UcxList *e = l; | |
| 140 size_t s = 1; | |
| 141 while (e->next != NULL) { | |
| 142 e = e->next; | |
| 143 s++; | |
| 144 } | |
| 145 | |
| 146 return s; | |
| 147 } | |
| 148 | |
| 149 UcxList *ucx_list_sort_merge(int length, | |
| 150 UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re, | |
| 151 cmp_func fnc, void* data) { | |
| 152 | |
| 153 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length); | |
| 154 UcxList *rc, *lc; | |
| 155 | |
| 156 lc = ls; rc = le; | |
| 157 int n = 0; | |
| 158 while (lc && lc != le && rc != re) { | |
| 159 if (fnc(lc->data, rc->data, data) <= 0) { | |
| 160 sorted[n] = lc; | |
| 161 lc = lc->next; | |
| 162 } else { | |
| 163 sorted[n] = rc; | |
| 164 rc = rc->next; | |
| 165 } | |
| 166 n++; | |
| 167 } | |
| 168 while (lc && lc != le) { | |
| 169 sorted[n] = lc; | |
| 170 lc = lc->next; | |
| 171 n++; | |
| 172 } | |
| 173 while (rc && rc != re) { | |
| 174 sorted[n] = rc; | |
| 175 rc = rc->next; | |
| 176 n++; | |
| 177 } | |
| 178 | |
| 179 // Update pointer | |
| 180 for (int i = 0 ; i < length-1 ; i++) { | |
| 181 sorted[i]->next = sorted[i+1]; | |
| 182 } | |
| 183 sorted[length-1]->next = NULL; | |
| 184 | |
| 185 UcxList *ret = sorted[0]; | |
| 186 free(sorted); | |
| 187 return ret; | |
| 188 } | |
| 189 | |
| 190 UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) { | |
| 191 if (l == NULL) { | |
| 192 return NULL; | |
| 193 } | |
| 194 | |
| 195 UcxList *lc; | |
| 196 int ln = 1; | |
| 197 | |
| 198 UcxList *restrict ls = l, *restrict le, *restrict re; | |
| 199 lc = ls; | |
| 200 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) { | |
| 201 lc = lc->next; | |
| 202 ln++; | |
| 203 } | |
| 204 le = lc->next; | |
| 205 | |
| 206 if (le == NULL) { | |
| 207 return l; // this list is already sorted :) | |
| 208 } else { | |
| 209 UcxList *rc; | |
| 210 int rn = 1; | |
| 211 rc = le; | |
| 212 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { | |
| 213 rc = rc->next; | |
| 214 rn++; | |
| 215 } | |
| 216 re = rc->next; | |
| 217 | |
| 218 // Something left? Sort it! | |
| 219 UcxList *remainder = re; | |
| 220 size_t remainder_length = ucx_list_size(remainder); | |
| 221 if (remainder != NULL) { | |
| 222 remainder = ucx_list_sort(remainder, fnc, data); | |
| 223 } | |
| 224 | |
| 225 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them | |
| 226 UcxList *sorted = ucx_list_sort_merge(ln+rn, | |
| 227 ls, le, re, | |
| 228 fnc, data); | |
| 229 | |
| 230 // merge sorted list with (also sorted) remainder | |
| 231 l = ucx_list_sort_merge(ln+rn+remainder_length, | |
| 232 sorted, remainder, NULL, fnc, data); | |
| 233 | |
| 234 return l; | |
| 235 } | |
| 236 } | |
| 237 | |
| 238 /* list specific functions */ | |
| 239 UcxList *ucx_list_remove(UcxList *l, UcxList *e) { | |
| 240 if (e == l) { | |
| 241 l = e->next; | |
| 242 free(e); | |
| 243 } else { | |
| 244 UcxList *f = l; | |
| 245 while (f->next != NULL && f->next != e) { | |
| 246 f = f->next; | |
| 247 } | |
| 248 /* perform remove if this element is found in this list */ | |
| 249 if (f->next == e) { | |
| 250 f->next = e->next; | |
| 251 free(e); | |
| 252 } | |
| 253 } | |
| 254 return l; | |
| 255 } |
