ucx/list.c

   1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
   3  *
   4  * Copyright 2017 Mike Becker, 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 "ucx/list.h"
  30
  31 UcxList *ucx_list_clone(const UcxList *l, copy_func fnc, void *data) {
  32     return ucx_list_clone_a(ucx_default_allocator(), l, fnc, data);
  33 }
  34
  35 UcxList *ucx_list_clone_a(UcxAllocator *alloc, const UcxList *l,
  36         copy_func fnc, void *data) {
  37     UcxList *ret = NULL;
  38     while (l) {
  39         if (fnc) {
  40             ret = ucx_list_append_a(alloc, ret, fnc(l->data, data));
  41         } else {
  42             ret = ucx_list_append_a(alloc, ret, l->data);
  43         }
  44         l = l->next;
  45     }
  46     return ret;
  47 }
  48
  49 int ucx_list_equals(const UcxList *l1, const UcxList *l2,
  50         cmp_func fnc, void* data) {
  51     if (l1 == l2) return 1;
  52
  53     while (l1 != NULL && l2 != NULL) {
  54         if (fnc == NULL) {
  55             if (l1->data != l2->data) return 0;
  56         } else {
  57             if (fnc(l1->data, l2->data, data) != 0) return 0;
  58         }
  59         l1 = l1->next;
  60         l2 = l2->next;
  61     }
  62
  63     return (l1 == NULL && l2 == NULL);
  64 }
  65
  66 void ucx_list_free(UcxList *l) {
  67     ucx_list_free_a(ucx_default_allocator(), l);
  68 }
  69
  70 void ucx_list_free_a(UcxAllocator *alloc, UcxList *l) {
  71     UcxList *e = l, *f;
  72     while (e != NULL) {
  73         f = e;
  74         e = e->next;
  75         alfree(alloc, f);
  76     }
  77 }
  78
  79 void ucx_list_free_content(UcxList* list, ucx_destructor destr) {
  80     if (!destr) destr = free;
  81     while (list != NULL) {
  82         destr(list->data);
  83         list = list->next;
  84     }
  85 }
  86
  87 UcxList *ucx_list_append(UcxList *l, void *data)  {
  88     return ucx_list_append_a(ucx_default_allocator(), l, data);
  89 }
  90
  91 UcxList *ucx_list_append_a(UcxAllocator *alloc, UcxList *l, void *data)  {
  92     UcxList *nl = (UcxList*) almalloc(alloc, sizeof(UcxList));
  93     if (!nl) {
  94         return NULL;
  95     }
  96
  97     nl->data = data;
  98     nl->next = NULL;
  99     if (l) {
 100         UcxList *t = ucx_list_last(l);
 101         t->next = nl;
 102         nl->prev = t;
 103         return l;
 104     } else {
 105         nl->prev = NULL;
 106         return nl;
 107     }
 108 }
 109
 110 UcxList *ucx_list_prepend(UcxList *l, void *data) {
 111     return ucx_list_prepend_a(ucx_default_allocator(), l, data);
 112 }
 113
 114 UcxList *ucx_list_prepend_a(UcxAllocator *alloc, UcxList *l, void *data) {
 115     UcxList *nl = ucx_list_append_a(alloc, NULL, data);
 116     if (!nl) {
 117         return NULL;
 118     }
 119     l = ucx_list_first(l);
 120
 121     if (l) {
 122         nl->next = l;
 123         l->prev = nl;
 124     }
 125     return nl;
 126 }
 127
 128 UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) {
 129     if (l1) {
 130         UcxList *last = ucx_list_last(l1);
 131         last->next = l2;
 132         if (l2) {
 133             l2->prev = last;
 134         }
 135         return l1;
 136     } else {
 137         return l2;
 138     }
 139 }
 140
 141 UcxList *ucx_list_last(const UcxList *l) {
 142     if (l == NULL) return NULL;
 143
 144     const UcxList *e = l;
 145     while (e->next != NULL) {
 146         e = e->next;
 147     }
 148     return (UcxList*)e;
 149 }
 150
 151 ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem) {
 152     ssize_t index = 0;
 153     while (list) {
 154         if (list == elem) {
 155             return index;
 156         }
 157         list = list->next;
 158         index++;
 159     }
 160     return -1;
 161 }
 162
 163 UcxList *ucx_list_get(const UcxList *l, size_t index) {
 164     if (l == NULL) return NULL;
 165
 166     const UcxList *e = l;
 167     while (e->next && index > 0) {
 168         e = e->next;
 169         index--;
 170     }
 171
 172     return (UcxList*)(index == 0 ? e : NULL);
 173 }
 174
 175 ssize_t ucx_list_find(const UcxList *l, void *elem,
 176         cmp_func fnc, void *cmpdata) {
 177     ssize_t index = 0;
 178     UCX_FOREACH(e, l) {
 179         if (fnc) {
 180             if (fnc(elem, e->data, cmpdata) == 0) {
 181                 return index;
 182             }
 183         } else {
 184             if (elem == e->data) {
 185                 return index;
 186             }
 187         }
 188         index++;
 189     }
 190     return -1;
 191 }
 192
 193 int ucx_list_contains(const UcxList *l, void *elem,
 194         cmp_func fnc, void *cmpdata) {
 195     return ucx_list_find(l, elem, fnc, cmpdata) > -1;
 196 }
 197
 198 size_t ucx_list_size(const UcxList *l) {
 199     if (l == NULL) return 0;
 200
 201     const UcxList *e = l;
 202     size_t s = 1;
 203     while (e->next != NULL) {
 204         e = e->next;
 205         s++;
 206     }
 207
 208     return s;
 209 }
 210
 211 static UcxList *ucx_list_sort_merge(size_t length,
 212         UcxList* ls, UcxList* le, UcxList* re,
 213         cmp_func fnc, void* data) {
 214
 215     UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length);
 216     UcxList *rc, *lc;
 217
 218     lc = ls; rc = le;
 219     size_t n = 0;
 220     while (lc && lc != le && rc != re) {
 221         if (fnc(lc->data, rc->data, data) <= 0) {
 222             sorted[n] = lc;
 223             lc = lc->next;
 224         } else {
 225             sorted[n] = rc;
 226             rc = rc->next;
 227         }
 228         n++;
 229     }
 230     while (lc && lc != le) {
 231         sorted[n] = lc;
 232         lc = lc->next;
 233         n++;
 234     }
 235     while (rc && rc != re) {
 236         sorted[n] = rc;
 237         rc = rc->next;
 238         n++;
 239     }
 240
 241     // Update pointer
 242     sorted[0]->prev = NULL;
 243     for (int i = 0 ; i < length-1 ; i++) {
 244         sorted[i]->next = sorted[i+1];
 245         sorted[i+1]->prev = sorted[i];
 246     }
 247     sorted[length-1]->next = NULL;
 248
 249     UcxList *ret = sorted[0];
 250     free(sorted);
 251     return ret;
 252 }
 253
 254 UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) {
 255     if (l == NULL) {
 256         return NULL;
 257     }
 258
 259     UcxList *lc;
 260     size_t ln = 1;
 261
 262     UcxList *ls = l, *le, *re;
 263
 264     // check how many elements are already sorted
 265     lc = ls;
 266     while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
 267         lc = lc->next;
 268         ln++;
 269     }
 270     le = lc->next;
 271
 272     if (le == NULL) {
 273         return l; // this list is already sorted :)
 274     } else {
 275         UcxList *rc;
 276         size_t rn = 1;
 277         rc = le;
 278         // skip already sorted elements
 279         while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
 280             rc = rc->next;
 281             rn++;
 282         }
 283         re = rc->next;
 284
 285         // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
 286         UcxList *sorted = ucx_list_sort_merge(ln+rn,
 287                 ls, le, re,
 288                 fnc, data);
 289
 290         // Something left? Sort it!
 291         size_t remainder_length = ucx_list_size(re);
 292         if (remainder_length > 0) {
 293             UcxList *remainder = ucx_list_sort(re, fnc, data);
 294
 295             // merge sorted list with (also sorted) remainder
 296             l = ucx_list_sort_merge(ln+rn+remainder_length,
 297                     sorted, remainder, NULL, fnc, data);
 298         } else {
 299             // no remainder - we've got our sorted list
 300             l = sorted;
 301         }
 302
 303         return l;
 304     }
 305 }
 306
 307 UcxList *ucx_list_first(const UcxList *l) {
 308     if (!l) {
 309         return NULL;
 310     }
 311
 312     const UcxList *e = l;
 313     while (e->prev) {
 314         e = e->prev;
 315     }
 316     return (UcxList *)e;
 317 }
 318
 319 UcxList *ucx_list_remove(UcxList *l, UcxList *e) {
 320     return ucx_list_remove_a(ucx_default_allocator(), l, e);
 321 }
 322
 323 UcxList *ucx_list_remove_a(UcxAllocator *alloc, UcxList *l, UcxList *e) {
 324     if (l == e) {
 325         l = e->next;
 326     }
 327
 328     if (e->next) {
 329         e->next->prev = e->prev;
 330     }
 331
 332     if (e->prev) {
 333         e->prev->next = e->next;
 334     }
 335
 336     alfree(alloc, e);
 337     return l;
 338 }
 339
 340
 341 static UcxList* ucx_list_setoperation_a(UcxAllocator *allocator,
 342         UcxList const *left, UcxList const *right,
 343         cmp_func cmpfnc, void* cmpdata,
 344         copy_func cpfnc, void* cpdata,
 345         int op) {
 346
 347     UcxList *res = NULL;
 348     UcxList *cur = NULL;
 349     const UcxList *src = left;
 350
 351     do {
 352         UCX_FOREACH(node, src) {
 353             void* elem = node->data;
 354             if (
 355                 (op == 0 && !ucx_list_contains(res, elem, cmpfnc, cmpdata)) ||
 356                 (op == 1 && ucx_list_contains(right, elem, cmpfnc, cmpdata)) ||
 357                 (op == 2 && !ucx_list_contains(right, elem, cmpfnc, cmpdata))) {
 358                 UcxList *nl = almalloc(allocator, sizeof(UcxList));
 359                 nl->prev = cur;
 360                 nl->next = NULL;
 361                 if (cpfnc) {
 362                     nl->data = cpfnc(elem, cpdata);
 363                 } else {
 364                     nl->data = elem;
 365                 }
 366                 if (cur != NULL)
 367                     cur->next = nl;
 368                 cur = nl;
 369                 if (res == NULL)
 370                     res = cur;
 371             }
 372         }
 373         if (op == 0 && src == left)
 374             src = right;
 375         else
 376             src = NULL;
 377     } while (src != NULL);
 378
 379     return res;
 380 }
 381
 382 UcxList* ucx_list_union(UcxList const *left, UcxList const *right,
 383         cmp_func cmpfnc, void* cmpdata,
 384         copy_func cpfnc, void* cpdata) {
 385     return ucx_list_union_a(ucx_default_allocator(),
 386             left, right, cmpfnc, cmpdata, cpfnc, cpdata);
 387 }
 388
 389 UcxList* ucx_list_union_a(UcxAllocator *allocator,
 390         UcxList const *left, UcxList const *right,
 391         cmp_func cmpfnc, void* cmpdata,
 392         copy_func cpfnc, void* cpdata) {
 393
 394     return ucx_list_setoperation_a(allocator, left, right,
 395             cmpfnc, cmpdata, cpfnc, cpdata, 0);
 396 }
 397
 398 UcxList* ucx_list_intersection(UcxList const *left, UcxList const *right,
 399         cmp_func cmpfnc, void* cmpdata,
 400         copy_func cpfnc, void* cpdata) {
 401     return ucx_list_intersection_a(ucx_default_allocator(), left, right,
 402             cmpfnc, cmpdata, cpfnc, cpdata);
 403 }
 404
 405 UcxList* ucx_list_intersection_a(UcxAllocator *allocator,
 406         UcxList const *left, UcxList const *right,
 407         cmp_func cmpfnc, void* cmpdata,
 408         copy_func cpfnc, void* cpdata) {
 409
 410     return ucx_list_setoperation_a(allocator, left, right,
 411             cmpfnc, cmpdata, cpfnc, cpdata, 1);
 412 }
 413
 414 UcxList* ucx_list_difference(UcxList const *left, UcxList const *right,
 415         cmp_func cmpfnc, void* cmpdata,
 416         copy_func cpfnc, void* cpdata) {
 417     return ucx_list_difference_a(ucx_default_allocator(), left, right,
 418             cmpfnc, cmpdata, cpfnc, cpdata);
 419 }
 420
 421 UcxList* ucx_list_difference_a(UcxAllocator *allocator,
 422         UcxList const *left, UcxList const *right,
 423         cmp_func cmpfnc, void* cmpdata,
 424         copy_func cpfnc, void* cpdata) {
 425
 426     return ucx_list_setoperation_a(allocator, left, right,
 427             cmpfnc, cmpdata, cpfnc, cpdata, 2);
 428 }