ucx: ucx/list.c@1e51558b9d09

     1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.

     3  *

     4  * Copyright 2015 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 "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 UcxList *ucx_list_append(UcxList *l, void *data)  {

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

    81 }

    83 UcxList *ucx_list_append_a(UcxAllocator *alloc, UcxList *l, void *data)  {

    84     UcxList *nl = (UcxList*) almalloc(alloc, sizeof(UcxList));

    85     if (!nl) {

    86         return NULL;

    87     }

    89     nl->data = data;

    90     nl->next = NULL;

    91     if (l) {

    92         UcxList *t = ucx_list_last(l);

    93         t->next = nl;

    94         nl->prev = t;

    95         return l;

    96     } else {

    97         nl->prev = NULL;

    98         return nl;

    99     }

   100 }

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

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

   104 }

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

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

   108     if (!nl) {

   109         return NULL;

   110     }

   111     l = ucx_list_first(l);

   113     if (l) {

   114         nl->next = l;

   115         l->prev = nl;

   116     }

   117     return nl;

   118 }

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

   121     if (l1) {

   122         UcxList *last = ucx_list_last(l1);

   123         last->next = l2;

   124         if (l2) {

   125             l2->prev = last;

   126         }

   127         return l1;

   128     } else {

   129         return l2;

   130     }

   131 }

   133 UcxList *ucx_list_last(const UcxList *l) {

   134     if (l == NULL) return NULL;

   136     const UcxList *e = l;

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

   138         e = e->next;

   139     }

   140     return (UcxList*)e;

   141 }

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

   144     ssize_t index = 0;

   145     while (list) {

   146         if (list == elem) {

   147             return index;

   148         }

   149         list = list->next;

   150         index++;

   151     }

   152     return -1;

   153 }

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

   156     if (l == NULL) return NULL;

   158     const UcxList *e = l;

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

   160         e = e->next;

   161         index--;

   162     }

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

   165 }

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

   168     ssize_t index = 0;

   169     UCX_FOREACH(e, l) {

   170         if (fnc) {

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

   172                 return index;

   173             }

   174         } else {

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

   176                 return index;

   177             }

   178         }

   179         index++;

   180     }

   181     return -1;

   182 }

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

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

   186 }

   188 size_t ucx_list_size(const UcxList *l) {

   189     if (l == NULL) return 0;

   191     const UcxList *e = l;

   192     size_t s = 1;

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

   194         e = e->next;

   195         s++;

   196     }

   198     return s;

   199 }

   201 static UcxList *ucx_list_sort_merge(int length,

   202         UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re,

   203         cmp_func fnc, void* data) {

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

   206     UcxList *rc, *lc;

   208     lc = ls; rc = le;

   209     int n = 0;

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

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

   212             sorted[n] = lc;

   213             lc = lc->next;

   214         } else {

   215             sorted[n] = rc;

   216             rc = rc->next;

   217         }

   218         n++;

   219     }

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

   221         sorted[n] = lc;

   222         lc = lc->next;

   223         n++;

   224     }

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

   226         sorted[n] = rc;

   227         rc = rc->next;

   228         n++;

   229     }

   231     // Update pointer

   232     sorted[0]->prev = NULL;

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

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

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

   236     }

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

   239     UcxList *ret = sorted[0];

   240     free(sorted);

   241     return ret;

   242 }

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

   245     if (l == NULL) {

   246         return NULL;

   247     }

   249     UcxList *lc;

   250     int ln = 1;

   252     UcxList *restrict ls = l, *restrict le, *restrict re;

   254     // check how many elements are already sorted

   255     lc = ls;

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

   257         lc = lc->next;

   258         ln++;

   259     }

   260     le = lc->next;

   262     if (le == NULL) {

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

   264     } else {

   265         UcxList *rc;

   266         int rn = 1;

   267         rc = le;

   268         // skip already sorted elements

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

   270             rc = rc->next;

   271             rn++;

   272         }

   273         re = rc->next;

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

   276         UcxList *sorted = ucx_list_sort_merge(ln+rn,

   277                 ls, le, re,

   278                 fnc, data);

   280         // Something left? Sort it!

   281         size_t remainder_length = ucx_list_size(re);

   282         if (remainder_length > 0) {

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

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

   286             l = ucx_list_sort_merge(ln+rn+remainder_length,

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

   288         } else {

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

   290             l = sorted;

   291         }

   293         return l;

   294     }

   295 }

   297 UcxList *ucx_list_first(const UcxList *l) {

   298     if (!l) {

   299         return NULL;

   300     }

   302     const UcxList *e = l;

   303     while (e->prev) {

   304         e = e->prev;

   305     }

   306     return (UcxList *)e;

   307 }

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

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

   311 }

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

   314     if (l == e) {

   315         l = e->next;

   316     }

   318     if (e->next) {

   319         e->next->prev = e->prev;

   320     }

   322     if (e->prev) {

   323         e->prev->next = e->next;

   324     }

   326     alfree(alloc, e);

   327     return l;

   328 }

Mercurial > hg > ucx / file revision

ucx/list.c@1e51558b9d09

ucx/list.c