Mon, 14 May 2018 18:12:14 +0200
renames ucx_strcmp() to ucx_cmp_str()
/* * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. * * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. */ #include "ucx/list.h" UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) { return ucx_list_clone_a(ucx_default_allocator(), l, fnc, data); } UcxList *ucx_list_clone_a(UcxAllocator *alloc, UcxList *l, copy_func fnc, void *data) { UcxList *ret = NULL; while (l) { if (fnc) { ret = ucx_list_append_a(alloc, ret, fnc(l->data, data)); } else { ret = ucx_list_append_a(alloc, ret, l->data); } l = l->next; } return ret; } int ucx_list_equals(const UcxList *l1, const UcxList *l2, cmp_func fnc, void* data) { if (l1 == l2) return 1; while (l1 != NULL && l2 != NULL) { if (fnc == NULL) { if (l1->data != l2->data) return 0; } else { if (fnc(l1->data, l2->data, data) != 0) return 0; } l1 = l1->next; l2 = l2->next; } return (l1 == NULL && l2 == NULL); } void ucx_list_free(UcxList *l) { ucx_list_free_a(ucx_default_allocator(), l); } void ucx_list_free_a(UcxAllocator *alloc, UcxList *l) { UcxList *e = l, *f; while (e != NULL) { f = e; e = e->next; alfree(alloc, f); } } void ucx_list_free_content(UcxList* list, ucx_destructor destr) { if (!destr) destr = free; while (list != NULL) { destr(list->data); list = list->next; } } UcxList *ucx_list_append(UcxList *l, void *data) { return ucx_list_append_a(ucx_default_allocator(), l, data); } UcxList *ucx_list_append_a(UcxAllocator *alloc, UcxList *l, void *data) { UcxList *nl = (UcxList*) almalloc(alloc, sizeof(UcxList)); if (!nl) { return NULL; } nl->data = data; nl->next = NULL; if (l) { UcxList *t = ucx_list_last(l); t->next = nl; nl->prev = t; return l; } else { nl->prev = NULL; return nl; } } UcxList *ucx_list_append_once(UcxList *l, void *data, cmp_func cmpfnc, void *cmpdata) { return ucx_list_append_once_a(ucx_default_allocator(), l, data, cmpfnc, cmpdata); } UcxList *ucx_list_append_once_a(UcxAllocator *alloc, UcxList *l, void *data, cmp_func cmpfnc, void *cmpdata) { UcxList *last = NULL; { UcxList *e = l; while (e) { if (cmpfnc(e->data, data, cmpdata) == 0) { return l; } last = e; e = e->next; } } UcxList *nl = ucx_list_append_a(alloc, NULL, data); if (!nl) { return NULL; } if (last == NULL) { return nl; } else { nl->prev = last; last->next = nl; return l; } } UcxList *ucx_list_prepend_once(UcxList *l, void *data, cmp_func cmpfnc, void *cmpdata) { return ucx_list_prepend_once_a(ucx_default_allocator(), l, data, cmpfnc, cmpdata); } UcxList *ucx_list_prepend_once_a(UcxAllocator *alloc, UcxList *l, void *data, cmp_func cmpfnc, void *cmpdata) { UcxList* first = ucx_list_first(l); { UcxList *e = first; while (e) { if (cmpfnc(e->data, data, cmpdata) == 0) { return l; } e = e->next; } } UcxList *nl = ucx_list_append_a(alloc, NULL, data); if (!nl) { return NULL; } if (first) { nl->next = first; first->prev = nl; } return nl; } UcxList *ucx_list_prepend(UcxList *l, void *data) { return ucx_list_prepend_a(ucx_default_allocator(), l, data); } UcxList *ucx_list_prepend_a(UcxAllocator *alloc, UcxList *l, void *data) { UcxList *nl = ucx_list_append_a(alloc, NULL, data); if (!nl) { return NULL; } l = ucx_list_first(l); if (l) { nl->next = l; l->prev = nl; } return nl; } UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) { if (l1) { UcxList *last = ucx_list_last(l1); last->next = l2; if (l2) { l2->prev = last; } return l1; } else { return l2; } } UcxList *ucx_list_last(const UcxList *l) { if (l == NULL) return NULL; const UcxList *e = l; while (e->next != NULL) { e = e->next; } return (UcxList*)e; } ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem) { ssize_t index = 0; while (list) { if (list == elem) { return index; } list = list->next; index++; } return -1; } UcxList *ucx_list_get(const UcxList *l, size_t index) { if (l == NULL) return NULL; const UcxList *e = l; while (e->next && index > 0) { e = e->next; index--; } return (UcxList*)(index == 0 ? e : NULL); } ssize_t ucx_list_find(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) { ssize_t index = 0; UCX_FOREACH(e, l) { if (fnc) { if (fnc(elem, e->data, cmpdata) == 0) { return index; } } else { if (elem == e->data) { return index; } } index++; } return -1; } int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) { return ucx_list_find(l, elem, fnc, cmpdata) > -1; } size_t ucx_list_size(const UcxList *l) { if (l == NULL) return 0; const UcxList *e = l; size_t s = 1; while (e->next != NULL) { e = e->next; s++; } return s; } static UcxList *ucx_list_sort_merge(int length, UcxList* ls, UcxList* le, UcxList* re, cmp_func fnc, void* data) { UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length); UcxList *rc, *lc; lc = ls; rc = le; int n = 0; while (lc && lc != le && rc != re) { if (fnc(lc->data, rc->data, data) <= 0) { sorted[n] = lc; lc = lc->next; } else { sorted[n] = rc; rc = rc->next; } n++; } while (lc && lc != le) { sorted[n] = lc; lc = lc->next; n++; } while (rc && rc != re) { sorted[n] = rc; rc = rc->next; n++; } // Update pointer sorted[0]->prev = NULL; for (int i = 0 ; i < length-1 ; i++) { sorted[i]->next = sorted[i+1]; sorted[i+1]->prev = sorted[i]; } sorted[length-1]->next = NULL; UcxList *ret = sorted[0]; free(sorted); return ret; } UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) { if (l == NULL) { return NULL; } UcxList *lc; int ln = 1; UcxList *ls = l, *le, *re; // check how many elements are already sorted lc = ls; while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) { lc = lc->next; ln++; } le = lc->next; if (le == NULL) { return l; // this list is already sorted :) } else { UcxList *rc; int rn = 1; rc = le; // skip already sorted elements while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { rc = rc->next; rn++; } re = rc->next; // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them UcxList *sorted = ucx_list_sort_merge(ln+rn, ls, le, re, fnc, data); // Something left? Sort it! size_t remainder_length = ucx_list_size(re); if (remainder_length > 0) { UcxList *remainder = ucx_list_sort(re, fnc, data); // merge sorted list with (also sorted) remainder l = ucx_list_sort_merge(ln+rn+remainder_length, sorted, remainder, NULL, fnc, data); } else { // no remainder - we've got our sorted list l = sorted; } return l; } } UcxList *ucx_list_first(const UcxList *l) { if (!l) { return NULL; } const UcxList *e = l; while (e->prev) { e = e->prev; } return (UcxList *)e; } UcxList *ucx_list_remove(UcxList *l, UcxList *e) { return ucx_list_remove_a(ucx_default_allocator(), l, e); } UcxList *ucx_list_remove_a(UcxAllocator *alloc, UcxList *l, UcxList *e) { if (l == e) { l = e->next; } if (e->next) { e->next->prev = e->prev; } if (e->prev) { e->prev->next = e->next; } alfree(alloc, e); return l; }