ucx: src/list.c@871a8ffe6c9d

     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  */

    29 #include "ucx/list.h"

    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 }

    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 }

    49 int ucx_list_equals(const UcxList *l1, const UcxList *l2,

    50         cmp_func fnc, void* data) {

    51     if (l1 == l2) return 1;

    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     }

    63     return (l1 == NULL && l2 == NULL);

    64 }

    66 void ucx_list_free(UcxList *l) {

    67     ucx_list_free_a(ucx_default_allocator(), l);

    68 }

    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 }

    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 }

    87 UcxList *ucx_list_append(UcxList *l, void *data)  {

    88     return ucx_list_append_a(ucx_default_allocator(), l, data);

    89 }

    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     }

    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 }

   110 UcxList *ucx_list_prepend(UcxList *l, void *data) {

   111     return ucx_list_prepend_a(ucx_default_allocator(), l, data);

   112 }

   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);

   121     if (l) {

   122         nl->next = l;

   123         l->prev = nl;

   124     }

   125     return nl;

   126 }

   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 }

   141 UcxList *ucx_list_last(const UcxList *l) {

   142     if (l == NULL) return NULL;

   144     const UcxList *e = l;

   145     while (e->next != NULL) {

   146         e = e->next;

   147     }

   148     return (UcxList*)e;

   149 }

   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 }

   163 UcxList *ucx_list_get(const UcxList *l, size_t index) {

   164     if (l == NULL) return NULL;

   166     const UcxList *e = l;

   167     while (e->next && index > 0) {

   168         e = e->next;

   169         index--;

   170     }

   172     return (UcxList*)(index == 0 ? e : NULL);

   173 }

   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 }

   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 }

   198 size_t ucx_list_size(const UcxList *l) {

   199     if (l == NULL) return 0;

   201     const UcxList *e = l;

   202     size_t s = 1;

   203     while (e->next != NULL) {

   204         e = e->next;

   205         s++;

   206     }

   208     return s;

   209 }

   211 static UcxList *ucx_list_sort_merge(size_t length,

   212         UcxList* ls, UcxList* le, UcxList* re,

   213         cmp_func fnc, void* data) {

   215     UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length);

   216     UcxList *rc, *lc;

   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     }

   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;

   249     UcxList *ret = sorted[0];

   250     free(sorted);

   251     return ret;

   252 }

   254 UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) {

   255     if (l == NULL) {

   256         return NULL;

   257     }

   259     UcxList *lc;

   260     size_t ln = 1;

   262     UcxList *ls = l, *le, *re;

   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;

   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;

   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);

   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);

   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         }

   303         return l;

   304     }

   305 }

   307 UcxList *ucx_list_first(const UcxList *l) {

   308     if (!l) {

   309         return NULL;

   310     }

   312     const UcxList *e = l;

   313     while (e->prev) {

   314         e = e->prev;

   315     }

   316     return (UcxList *)e;

   317 }

   319 UcxList *ucx_list_remove(UcxList *l, UcxList *e) {

   320     return ucx_list_remove_a(ucx_default_allocator(), l, e);

   321 }

   323 UcxList *ucx_list_remove_a(UcxAllocator *alloc, UcxList *l, UcxList *e) {

   324     if (l == e) {

   325         l = e->next;

   326     }

   328     if (e->next) {

   329         e->next->prev = e->prev;

   330     }

   332     if (e->prev) {

   333         e->prev->next = e->next;

   334     }

   336     alfree(alloc, e);

   337     return l;

   338 }

   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) {

   347     UcxList *res = NULL;

   348     UcxList *cur = NULL;

   349     const UcxList *src = left;

   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);

   379     return res;

   380 }

   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 }

   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) {

   394     return ucx_list_setoperation_a(allocator, left, right,

   395             cmpfnc, cmpdata, cpfnc, cpdata, 0);

   396 }

   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 }

   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) {

   410     return ucx_list_setoperation_a(allocator, left, right,

   411             cmpfnc, cmpdata, cpfnc, cpdata, 1);

   412 }

   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 }

   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) {

   426     return ucx_list_setoperation_a(allocator, left, right,

   427             cmpfnc, cmpdata, cpfnc, cpdata, 2);

   428 }

Mercurial > hg > ucx / file revision

src/list.c@871a8ffe6c9d

src/list.c