ucx: src/list.c@9af21a50b516

     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(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, 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_append_once(UcxList *l, void *data,

   111         cmp_func cmpfnc, void *cmpdata) {

   112     return ucx_list_append_once_a(ucx_default_allocator(), l,

   113             data, cmpfnc, cmpdata);

   114 }

   116 UcxList *ucx_list_append_once_a(UcxAllocator *alloc, UcxList *l, void *data,

   117         cmp_func cmpfnc, void *cmpdata) {

   119     UcxList *last = NULL;

   120     {

   121         UcxList *e = l;

   122         while (e) {

   123             if (cmpfnc(e->data, data, cmpdata) == 0) {

   124                 return l;

   125             }

   126             last = e;

   127             e = e->next;

   128         }

   129     }

   131     UcxList *nl = ucx_list_append_a(alloc, NULL, data);

   132     if (!nl) {

   133         return NULL;

   134     }

   136     if (last == NULL) {

   137         return nl;

   138     } else {

   139         nl->prev = last;

   140         last->next = nl;

   141         return l;

   142     }

   143 }

   145 UcxList *ucx_list_prepend_once(UcxList *l, void *data,

   146         cmp_func cmpfnc, void *cmpdata) {

   147     return ucx_list_prepend_once_a(ucx_default_allocator(), l,

   148             data, cmpfnc, cmpdata);

   149 }

   151 UcxList *ucx_list_prepend_once_a(UcxAllocator *alloc, UcxList *l, void *data,

   152         cmp_func cmpfnc, void *cmpdata) {

   154     UcxList* first = ucx_list_first(l);

   155     {

   156         UcxList *e = first;

   157         while (e) {

   158             if (cmpfnc(e->data, data, cmpdata) == 0) {

   159                 return l;

   160             }

   161             e = e->next;

   162         }

   163     }

   165     UcxList *nl = ucx_list_append_a(alloc, NULL, data);

   166     if (!nl) {

   167         return NULL;

   168     }

   170     if (first) {

   171         nl->next = first;

   172         first->prev = nl;

   173     }

   175     return nl;

   176 }

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

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

   180 }

   182 UcxList *ucx_list_prepend_a(UcxAllocator *alloc, UcxList *l, void *data) {

   183     UcxList *nl = ucx_list_append_a(alloc, NULL, data);

   184     if (!nl) {

   185         return NULL;

   186     }

   187     l = ucx_list_first(l);

   189     if (l) {

   190         nl->next = l;

   191         l->prev = nl;

   192     }

   193     return nl;

   194 }

   196 UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) {

   197     if (l1) {

   198         UcxList *last = ucx_list_last(l1);

   199         last->next = l2;

   200         if (l2) {

   201             l2->prev = last;

   202         }

   203         return l1;

   204     } else {

   205         return l2;

   206     }

   207 }

   209 UcxList *ucx_list_last(const UcxList *l) {

   210     if (l == NULL) return NULL;

   212     const UcxList *e = l;

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

   214         e = e->next;

   215     }

   216     return (UcxList*)e;

   217 }

   219 ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem) {

   220     ssize_t index = 0;

   221     while (list) {

   222         if (list == elem) {

   223             return index;

   224         }

   225         list = list->next;

   226         index++;

   227     }

   228     return -1;

   229 }

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

   232     if (l == NULL) return NULL;

   234     const UcxList *e = l;

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

   236         e = e->next;

   237         index--;

   238     }

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

   241 }

   243 ssize_t ucx_list_find(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) {

   244     ssize_t index = 0;

   245     UCX_FOREACH(e, l) {

   246         if (fnc) {

   247             if (fnc(elem, e->data, cmpdata) == 0) {

   248                 return index;

   249             }

   250         } else {

   251             if (elem == e->data) {

   252                 return index;

   253             }

   254         }

   255         index++;

   256     }

   257     return -1;

   258 }

   260 int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) {

   261     return ucx_list_find(l, elem, fnc, cmpdata) > -1;

   262 }

   264 size_t ucx_list_size(const UcxList *l) {

   265     if (l == NULL) return 0;

   267     const UcxList *e = l;

   268     size_t s = 1;

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

   270         e = e->next;

   271         s++;

   272     }

   274     return s;

   275 }

   277 static UcxList *ucx_list_sort_merge(int length,

   278         UcxList* ls, UcxList* le, UcxList* re,

   279         cmp_func fnc, void* data) {

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

   282     UcxList *rc, *lc;

   284     lc = ls; rc = le;

   285     int n = 0;

   286     while (lc && lc != le && rc != re) {

   287         if (fnc(lc->data, rc->data, data) <= 0) {

   288             sorted[n] = lc;

   289             lc = lc->next;

   290         } else {

   291             sorted[n] = rc;

   292             rc = rc->next;

   293         }

   294         n++;

   295     }

   296     while (lc && lc != le) {

   297         sorted[n] = lc;

   298         lc = lc->next;

   299         n++;

   300     }

   301     while (rc && rc != re) {

   302         sorted[n] = rc;

   303         rc = rc->next;

   304         n++;

   305     }

   307     // Update pointer

   308     sorted[0]->prev = NULL;

   309     for (int i = 0 ; i < length-1 ; i++) {

   310         sorted[i]->next = sorted[i+1];

   311         sorted[i+1]->prev = sorted[i];

   312     }

   313     sorted[length-1]->next = NULL;

   315     UcxList *ret = sorted[0];

   316     free(sorted);

   317     return ret;

   318 }

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

   321     if (l == NULL) {

   322         return NULL;

   323     }

   325     UcxList *lc;

   326     int ln = 1;

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

   330     // check how many elements are already sorted

   331     lc = ls;

   332     while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {

   333         lc = lc->next;

   334         ln++;

   335     }

   336     le = lc->next;

   338     if (le == NULL) {

   339         return l; // this list is already sorted :)

   340     } else {

   341         UcxList *rc;

   342         int rn = 1;

   343         rc = le;

   344         // skip already sorted elements

   345         while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {

   346             rc = rc->next;

   347             rn++;

   348         }

   349         re = rc->next;

   351         // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them

   352         UcxList *sorted = ucx_list_sort_merge(ln+rn,

   353                 ls, le, re,

   354                 fnc, data);

   356         // Something left? Sort it!

   357         size_t remainder_length = ucx_list_size(re);

   358         if (remainder_length > 0) {

   359             UcxList *remainder = ucx_list_sort(re, fnc, data);

   361             // merge sorted list with (also sorted) remainder

   362             l = ucx_list_sort_merge(ln+rn+remainder_length,

   363                     sorted, remainder, NULL, fnc, data);

   364         } else {

   365             // no remainder - we've got our sorted list

   366             l = sorted;

   367         }

   369         return l;

   370     }

   371 }

   373 UcxList *ucx_list_first(const UcxList *l) {

   374     if (!l) {

   375         return NULL;

   376     }

   378     const UcxList *e = l;

   379     while (e->prev) {

   380         e = e->prev;

   381     }

   382     return (UcxList *)e;

   383 }

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

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

   387 }

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

   390     if (l == e) {

   391         l = e->next;

   392     }

   394     if (e->next) {

   395         e->next->prev = e->prev;

   396     }

   398     if (e->prev) {

   399         e->prev->next = e->next;

   400     }

   402     alfree(alloc, e);

   403     return l;

   404 }

Mercurial > hg > ucx / file revision

src/list.c@9af21a50b516

src/list.c