# HG changeset patch # User Mike Becker # Date 1374486819 -7200 # Node ID 540d99722f1f1aac6ab3f4e5f8daecc17f3dcc6e # Parent 311cac04d079c9d3dc956e158f9cae8c01e68d64 removal of single linked list implemenation - step 2: renamed UcxDlist to UcxList (new single implementation) diff -r 311cac04d079 -r 540d99722f1f test/Makefile --- a/test/Makefile Mon Jul 22 11:39:06 2013 +0200 +++ b/test/Makefile Mon Jul 22 11:53:39 2013 +0200 @@ -29,7 +29,7 @@ include ../$(CONF).mk SRC = main.c -SRC += dlist_tests.c +SRC += list_tests.c SRC += mpool_tests.c SRC += map_tests.c SRC += prop_tests.c diff -r 311cac04d079 -r 540d99722f1f test/dlist_tests.c --- a/test/dlist_tests.c Mon Jul 22 11:39:06 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,247 +0,0 @@ -/* - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Copyright 2013 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 "dlist_tests.h" -#include "ucx/utils.h" - -UCX_TEST_IMPLEMENT(test_ucx_dlist_append) { - UcxDlist *list = ucx_dlist_append(NULL, (void*)"Hello"); - UCX_TEST_BEGIN - - UCX_TEST_ASSERT(strncmp((const char*)list->data, "Hello", 5) == 0, - "failed"); - - list = ucx_dlist_append(list, (void*)" World!"); - - UCX_TEST_ASSERT(strncmp((const char*)list->next->data, " World!", 7) == 0, - "failed"); - UCX_TEST_ASSERT(list->next->next == NULL, "failed"); - UCX_TEST_END - - ucx_dlist_free(list); -} - -UCX_TEST_IMPLEMENT(test_ucx_dlist_prepend) { - UcxDlist *list = ucx_dlist_prepend(NULL, (void*)" World!"); - UCX_TEST_BEGIN - - list = ucx_dlist_prepend(list, (void*)"Hello"); - - UCX_TEST_ASSERT(strncmp((const char*)list->data, "Hello", 5) == 0, - "failed"); - UCX_TEST_ASSERT(strncmp((const char*)list->next->data, " World!", 7) == 0, - "failed"); - UCX_TEST_ASSERT(list->next->next == NULL, "failed"); - - UCX_TEST_END - ucx_dlist_free(list); -} - -UCX_TEST_IMPLEMENT(test_ucx_dlist_equals) { - UcxDlist *list = ucx_dlist_append(NULL, (void*)"Hello"); - list = ucx_dlist_append(list, (void*)" World!"); - UcxDlist *list2 = ucx_dlist_prepend(NULL, (void*)" World!"); - list2 = ucx_dlist_prepend(list2, (void*)"Hello"); - UcxDlist *list3 = ucx_dlist_prepend(NULL, (void*)" Welt!"); - list3 = ucx_dlist_prepend(list3, (void*)"Hallo"); - UCX_TEST_BEGIN - - UCX_TEST_ASSERT(ucx_dlist_equals(list, list2, ucx_strcmp, NULL), "failed"); - UCX_TEST_ASSERT(!ucx_dlist_equals(list, list3, ucx_strcmp, NULL), "failed"); - - UCX_TEST_END - ucx_dlist_free(list3); - ucx_dlist_free(list2); - ucx_dlist_free(list); -} - -UCX_TEST_IMPLEMENT(test_ucx_dlist_concat) { - UcxDlist *list = ucx_dlist_append(NULL, (void*)"Hello"); - UcxDlist *list2 = ucx_dlist_prepend(NULL, (void*)" World!"); - UCX_TEST_BEGIN - - list = ucx_dlist_concat(list, list2); - - UCX_TEST_ASSERT(strncmp((const char*)list->data, "Hello", 5) == 0, - "failed"); - UCX_TEST_ASSERT(strncmp((const char*)list->next->data, " World!", 7) == 0, - "failed"); - UCX_TEST_ASSERT(list->next->next == NULL, "failed"); - - UCX_TEST_END - ucx_dlist_free(list); -} - -UCX_TEST_IMPLEMENT(test_ucx_dlist_size) { - UcxDlist *list = ucx_dlist_append(NULL, (void*)"This "); - UCX_TEST_BEGIN - list = ucx_dlist_append(list, (void*)"list "); - list = ucx_dlist_append(list, (void*)"has "); - list = ucx_dlist_append(list, (void*)"size "); - list = ucx_dlist_append(list, (void*)"5!"); - - UCX_TEST_ASSERT(ucx_dlist_size(list) == 5, "failed"); - - UCX_TEST_END - ucx_dlist_free(list); -} - -UCX_TEST_IMPLEMENT(test_ucx_dlist_first) { - UcxDlist *list = ucx_dlist_append(NULL, (void*)"Find "); - UCX_TEST_BEGIN - list = ucx_dlist_append(list, (void*)"the "); - list = ucx_dlist_append(list, (void*)"first!"); - - const char* first = (const char*) (ucx_dlist_first(list)->data); - - UCX_TEST_ASSERT(strncmp(first, "Find ", 5) == 0, "failed"); - - UCX_TEST_END - ucx_dlist_free(list); -} - -UCX_TEST_IMPLEMENT(test_ucx_dlist_last) { - UcxDlist *list = ucx_dlist_append(NULL, (void*)"Find "); - UCX_TEST_BEGIN - list = ucx_dlist_append(list, (void*)"the "); - list = ucx_dlist_append(list, (void*)"last!"); - - const char* last = (const char*) (ucx_dlist_last(list)->data); - - UCX_TEST_ASSERT(strncmp(last, "last!", 5) == 0, "failed"); - - UCX_TEST_END - ucx_dlist_free(list); -} - -UCX_TEST_IMPLEMENT(test_ucx_dlist_get) { - UcxDlist *list = ucx_dlist_append(NULL, (void*)"Find "); - UCX_TEST_BEGIN - list = ucx_dlist_append(list, (void*)"the "); - list = ucx_dlist_append(list, (void*)"mid!"); - - const char* mid = (const char*) (ucx_dlist_get(list, 1)->data); - - UCX_TEST_ASSERT(strncmp(mid, "the ", 4) == 0, "failed"); - - UCX_TEST_END - ucx_dlist_free(list); -} - -UCX_TEST_IMPLEMENT(test_ucx_dlist_contains) { - UcxDlist *l = ucx_dlist_append(NULL, (void*)"Contains "); - UCX_TEST_BEGIN - l = ucx_dlist_append(l, (void*)"a "); - l = ucx_dlist_append(l, (void*)"string!"); - - UCX_TEST_ASSERT(ucx_dlist_contains(l,(void*)"a ",ucx_strcmp,NULL),"failed"); - UCX_TEST_ASSERT(!ucx_dlist_contains(l,(void*)"a",ucx_strcmp,NULL),"failed"); - - UCX_TEST_END - ucx_dlist_free(l); -} - -UCX_TEST_IMPLEMENT(test_ucx_dlist_remove) { - UcxDlist *list = ucx_dlist_append(NULL, (void*)"Hello"); - UCX_TEST_BEGIN - list = ucx_dlist_append(list, (void*)" fucking"); - list = ucx_dlist_append(list, (void*)" World!"); - - list = ucx_dlist_remove(list, ucx_dlist_get(list, 1)); - - UCX_TEST_ASSERT(strncmp((const char*)list->data, "Hello", 5) == 0, - "failed"); - UCX_TEST_ASSERT(strncmp((const char*)list->next->data, " World!", 7) == 0, - "failed"); - UCX_TEST_ASSERT(list->next->next == NULL, "failed"); - - UCX_TEST_END - ucx_dlist_free(list); -} - -UCX_TEST_IMPLEMENT(test_ucx_dlist_clone) { - - char *hello = (char*)malloc(6); - char *world = (char*)malloc(8); - - memcpy(hello, "Hello", 6); - memcpy(world, " World!", 8); - - UcxDlist *list = ucx_dlist_append(NULL, hello); - list = ucx_dlist_append(list, world); - - UcxDlist *copy = ucx_dlist_clone(list, ucx_strcpy, NULL); - UCX_TEST_BEGIN - - UCX_TEST_ASSERT(ucx_dlist_equals(list, copy, ucx_strcmp, NULL), "failed"); - UCX_TEST_ASSERT(hello != copy->data, "first element is no copy"); - UCX_TEST_ASSERT(world != copy->next->data, "second element is no copy"); - - UCX_TEST_END - free(copy->next->data); - free(copy->data); - - free(world); - free(hello); - ucx_dlist_free(list); - ucx_dlist_free(copy); -} - -UCX_TEST_IMPLEMENT(test_ucx_dlist_sort) { - UcxDlist *list = ucx_dlist_append(NULL, (void*)"this"); - list = ucx_dlist_append(list, (void*)"is"); - list = ucx_dlist_append(list, (void*)"a"); - list = ucx_dlist_append(list, (void*)"test"); - list = ucx_dlist_append(list, (void*)"for"); - list = ucx_dlist_append(list, (void*)"partial"); - list = ucx_dlist_append(list, (void*)"correctness"); - - UcxDlist *expected = ucx_dlist_append(NULL, (void*)"a"); - expected = ucx_dlist_append(expected, (void*)"correctness"); - expected = ucx_dlist_append(expected, (void*)"for"); - expected = ucx_dlist_append(expected, (void*)"is"); - expected = ucx_dlist_append(expected, (void*)"partial"); - expected = ucx_dlist_append(expected, (void*)"test"); - expected = ucx_dlist_append(expected, (void*)"this"); - - list = ucx_dlist_sort(list, ucx_strcmp, NULL); - - UCX_TEST_BEGIN - UCX_TEST_ASSERT( - ucx_dlist_equals(list, expected, ucx_strcmp, NULL), "failed"); - UcxDlist *l = list; - UCX_TEST_ASSERT(l->prev == NULL, "prev field of first entry is not null"); - while (l->next != NULL) { - UCX_TEST_ASSERT(l->next->prev == l, "prev pointer corrupted"); - l = l->next; - } - UCX_TEST_END - - ucx_dlist_free(expected); - ucx_dlist_free(list); -} diff -r 311cac04d079 -r 540d99722f1f test/dlist_tests.h --- a/test/dlist_tests.h Mon Jul 22 11:39:06 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,64 +0,0 @@ -/* - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Copyright 2013 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. - */ - -#ifndef DLIST_TESTS_H -#define DLIST_TESTS_H - -#include "main.h" - -#include "ucx/dlist.h" -#include "ucx/test.h" - -#ifdef __cplusplus -extern "C" { -#endif - -/* - * Assumed to be correct: - * ucx_dlist_free - */ - -UCX_TEST_DECLARE(test_ucx_dlist_append); -UCX_TEST_DECLARE(test_ucx_dlist_prepend); -UCX_TEST_DECLARE(test_ucx_dlist_equals); -UCX_TEST_DECLARE(test_ucx_dlist_concat); -UCX_TEST_DECLARE(test_ucx_dlist_size); -UCX_TEST_DECLARE(test_ucx_dlist_first); -UCX_TEST_DECLARE(test_ucx_dlist_last); -UCX_TEST_DECLARE(test_ucx_dlist_get); -UCX_TEST_DECLARE(test_ucx_dlist_contains); -UCX_TEST_DECLARE(test_ucx_dlist_remove); -UCX_TEST_DECLARE(test_ucx_dlist_clone); -UCX_TEST_DECLARE(test_ucx_dlist_sort); - -#ifdef __cplusplus -} -#endif - -#endif /* DLIST_TESTS_H */ - diff -r 311cac04d079 -r 540d99722f1f test/list_tests.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/list_tests.c Mon Jul 22 11:53:39 2013 +0200 @@ -0,0 +1,247 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2013 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 "list_tests.h" +#include "ucx/utils.h" + +UCX_TEST_IMPLEMENT(test_ucx_list_append) { + UcxList *list = ucx_list_append(NULL, (void*)"Hello"); + UCX_TEST_BEGIN + + UCX_TEST_ASSERT(strncmp((const char*)list->data, "Hello", 5) == 0, + "failed"); + + list = ucx_list_append(list, (void*)" World!"); + + UCX_TEST_ASSERT(strncmp((const char*)list->next->data, " World!", 7) == 0, + "failed"); + UCX_TEST_ASSERT(list->next->next == NULL, "failed"); + UCX_TEST_END + + ucx_list_free(list); +} + +UCX_TEST_IMPLEMENT(test_ucx_list_prepend) { + UcxList *list = ucx_list_prepend(NULL, (void*)" World!"); + UCX_TEST_BEGIN + + list = ucx_list_prepend(list, (void*)"Hello"); + + UCX_TEST_ASSERT(strncmp((const char*)list->data, "Hello", 5) == 0, + "failed"); + UCX_TEST_ASSERT(strncmp((const char*)list->next->data, " World!", 7) == 0, + "failed"); + UCX_TEST_ASSERT(list->next->next == NULL, "failed"); + + UCX_TEST_END + ucx_list_free(list); +} + +UCX_TEST_IMPLEMENT(test_ucx_list_equals) { + UcxList *list = ucx_list_append(NULL, (void*)"Hello"); + list = ucx_list_append(list, (void*)" World!"); + UcxList *list2 = ucx_list_prepend(NULL, (void*)" World!"); + list2 = ucx_list_prepend(list2, (void*)"Hello"); + UcxList *list3 = ucx_list_prepend(NULL, (void*)" Welt!"); + list3 = ucx_list_prepend(list3, (void*)"Hallo"); + UCX_TEST_BEGIN + + UCX_TEST_ASSERT(ucx_list_equals(list, list2, ucx_strcmp, NULL), "failed"); + UCX_TEST_ASSERT(!ucx_list_equals(list, list3, ucx_strcmp, NULL), "failed"); + + UCX_TEST_END + ucx_list_free(list3); + ucx_list_free(list2); + ucx_list_free(list); +} + +UCX_TEST_IMPLEMENT(test_ucx_list_concat) { + UcxList *list = ucx_list_append(NULL, (void*)"Hello"); + UcxList *list2 = ucx_list_prepend(NULL, (void*)" World!"); + UCX_TEST_BEGIN + + list = ucx_list_concat(list, list2); + + UCX_TEST_ASSERT(strncmp((const char*)list->data, "Hello", 5) == 0, + "failed"); + UCX_TEST_ASSERT(strncmp((const char*)list->next->data, " World!", 7) == 0, + "failed"); + UCX_TEST_ASSERT(list->next->next == NULL, "failed"); + + UCX_TEST_END + ucx_list_free(list); +} + +UCX_TEST_IMPLEMENT(test_ucx_list_size) { + UcxList *list = ucx_list_append(NULL, (void*)"This "); + UCX_TEST_BEGIN + list = ucx_list_append(list, (void*)"list "); + list = ucx_list_append(list, (void*)"has "); + list = ucx_list_append(list, (void*)"size "); + list = ucx_list_append(list, (void*)"5!"); + + UCX_TEST_ASSERT(ucx_list_size(list) == 5, "failed"); + + UCX_TEST_END + ucx_list_free(list); +} + +UCX_TEST_IMPLEMENT(test_ucx_list_first) { + UcxList *list = ucx_list_append(NULL, (void*)"Find "); + UCX_TEST_BEGIN + list = ucx_list_append(list, (void*)"the "); + list = ucx_list_append(list, (void*)"first!"); + + const char* first = (const char*) (ucx_list_first(list)->data); + + UCX_TEST_ASSERT(strncmp(first, "Find ", 5) == 0, "failed"); + + UCX_TEST_END + ucx_list_free(list); +} + +UCX_TEST_IMPLEMENT(test_ucx_list_last) { + UcxList *list = ucx_list_append(NULL, (void*)"Find "); + UCX_TEST_BEGIN + list = ucx_list_append(list, (void*)"the "); + list = ucx_list_append(list, (void*)"last!"); + + const char* last = (const char*) (ucx_list_last(list)->data); + + UCX_TEST_ASSERT(strncmp(last, "last!", 5) == 0, "failed"); + + UCX_TEST_END + ucx_list_free(list); +} + +UCX_TEST_IMPLEMENT(test_ucx_list_get) { + UcxList *list = ucx_list_append(NULL, (void*)"Find "); + UCX_TEST_BEGIN + list = ucx_list_append(list, (void*)"the "); + list = ucx_list_append(list, (void*)"mid!"); + + const char* mid = (const char*) (ucx_list_get(list, 1)->data); + + UCX_TEST_ASSERT(strncmp(mid, "the ", 4) == 0, "failed"); + + UCX_TEST_END + ucx_list_free(list); +} + +UCX_TEST_IMPLEMENT(test_ucx_list_contains) { + UcxList *l = ucx_list_append(NULL, (void*)"Contains "); + UCX_TEST_BEGIN + l = ucx_list_append(l, (void*)"a "); + l = ucx_list_append(l, (void*)"string!"); + + UCX_TEST_ASSERT(ucx_list_contains(l,(void*)"a ",ucx_strcmp,NULL),"failed"); + UCX_TEST_ASSERT(!ucx_list_contains(l,(void*)"a",ucx_strcmp,NULL),"failed"); + + UCX_TEST_END + ucx_list_free(l); +} + +UCX_TEST_IMPLEMENT(test_ucx_list_remove) { + UcxList *list = ucx_list_append(NULL, (void*)"Hello"); + UCX_TEST_BEGIN + list = ucx_list_append(list, (void*)" fucking"); + list = ucx_list_append(list, (void*)" World!"); + + list = ucx_list_remove(list, ucx_list_get(list, 1)); + + UCX_TEST_ASSERT(strncmp((const char*)list->data, "Hello", 5) == 0, + "failed"); + UCX_TEST_ASSERT(strncmp((const char*)list->next->data, " World!", 7) == 0, + "failed"); + UCX_TEST_ASSERT(list->next->next == NULL, "failed"); + + UCX_TEST_END + ucx_list_free(list); +} + +UCX_TEST_IMPLEMENT(test_ucx_list_clone) { + + char *hello = (char*)malloc(6); + char *world = (char*)malloc(8); + + memcpy(hello, "Hello", 6); + memcpy(world, " World!", 8); + + UcxList *list = ucx_list_append(NULL, hello); + list = ucx_list_append(list, world); + + UcxList *copy = ucx_list_clone(list, ucx_strcpy, NULL); + UCX_TEST_BEGIN + + UCX_TEST_ASSERT(ucx_list_equals(list, copy, ucx_strcmp, NULL), "failed"); + UCX_TEST_ASSERT(hello != copy->data, "first element is no copy"); + UCX_TEST_ASSERT(world != copy->next->data, "second element is no copy"); + + UCX_TEST_END + free(copy->next->data); + free(copy->data); + + free(world); + free(hello); + ucx_list_free(list); + ucx_list_free(copy); +} + +UCX_TEST_IMPLEMENT(test_ucx_list_sort) { + UcxList *list = ucx_list_append(NULL, (void*)"this"); + list = ucx_list_append(list, (void*)"is"); + list = ucx_list_append(list, (void*)"a"); + list = ucx_list_append(list, (void*)"test"); + list = ucx_list_append(list, (void*)"for"); + list = ucx_list_append(list, (void*)"partial"); + list = ucx_list_append(list, (void*)"correctness"); + + UcxList *expected = ucx_list_append(NULL, (void*)"a"); + expected = ucx_list_append(expected, (void*)"correctness"); + expected = ucx_list_append(expected, (void*)"for"); + expected = ucx_list_append(expected, (void*)"is"); + expected = ucx_list_append(expected, (void*)"partial"); + expected = ucx_list_append(expected, (void*)"test"); + expected = ucx_list_append(expected, (void*)"this"); + + list = ucx_list_sort(list, ucx_strcmp, NULL); + + UCX_TEST_BEGIN + UCX_TEST_ASSERT( + ucx_list_equals(list, expected, ucx_strcmp, NULL), "failed"); + UcxList *l = list; + UCX_TEST_ASSERT(l->prev == NULL, "prev field of first entry is not null"); + while (l->next != NULL) { + UCX_TEST_ASSERT(l->next->prev == l, "prev pointer corrupted"); + l = l->next; + } + UCX_TEST_END + + ucx_list_free(expected); + ucx_list_free(list); +} diff -r 311cac04d079 -r 540d99722f1f test/list_tests.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/list_tests.h Mon Jul 22 11:53:39 2013 +0200 @@ -0,0 +1,64 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2013 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. + */ + +#ifndef LIST_TESTS_H +#define LIST_TESTS_H + +#include "main.h" + +#include "ucx/list.h" +#include "ucx/test.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* + * Assumed to be correct: + * ucx_list_free + */ + +UCX_TEST_DECLARE(test_ucx_list_append); +UCX_TEST_DECLARE(test_ucx_list_prepend); +UCX_TEST_DECLARE(test_ucx_list_equals); +UCX_TEST_DECLARE(test_ucx_list_concat); +UCX_TEST_DECLARE(test_ucx_list_size); +UCX_TEST_DECLARE(test_ucx_list_first); +UCX_TEST_DECLARE(test_ucx_list_last); +UCX_TEST_DECLARE(test_ucx_list_get); +UCX_TEST_DECLARE(test_ucx_list_contains); +UCX_TEST_DECLARE(test_ucx_list_remove); +UCX_TEST_DECLARE(test_ucx_list_clone); +UCX_TEST_DECLARE(test_ucx_list_sort); + +#ifdef __cplusplus +} +#endif + +#endif /* LIST_TESTS_H */ + diff -r 311cac04d079 -r 540d99722f1f test/main.c --- a/test/main.c Mon Jul 22 11:39:06 2013 +0200 +++ b/test/main.c Mon Jul 22 11:53:39 2013 +0200 @@ -34,7 +34,7 @@ #include "main.h" #include "logging_tests.h" -#include "dlist_tests.h" +#include "list_tests.h" #include "string_tests.h" #include "mpool_tests.h" #include "map_tests.h" @@ -121,18 +121,18 @@ ucx_test_register(suite, test_ucx_logger_log); /* UcxDlist Tests */ - ucx_test_register(suite, test_ucx_dlist_append); - ucx_test_register(suite, test_ucx_dlist_prepend); - ucx_test_register(suite, test_ucx_dlist_equals); - ucx_test_register(suite, test_ucx_dlist_concat); - ucx_test_register(suite, test_ucx_dlist_size); - ucx_test_register(suite, test_ucx_dlist_first); - ucx_test_register(suite, test_ucx_dlist_last); - ucx_test_register(suite, test_ucx_dlist_get); - ucx_test_register(suite, test_ucx_dlist_contains); - ucx_test_register(suite, test_ucx_dlist_remove); - ucx_test_register(suite, test_ucx_dlist_clone); - ucx_test_register(suite, test_ucx_dlist_sort); + ucx_test_register(suite, test_ucx_list_append); + ucx_test_register(suite, test_ucx_list_prepend); + ucx_test_register(suite, test_ucx_list_equals); + ucx_test_register(suite, test_ucx_list_concat); + ucx_test_register(suite, test_ucx_list_size); + ucx_test_register(suite, test_ucx_list_first); + ucx_test_register(suite, test_ucx_list_last); + ucx_test_register(suite, test_ucx_list_get); + ucx_test_register(suite, test_ucx_list_contains); + ucx_test_register(suite, test_ucx_list_remove); + ucx_test_register(suite, test_ucx_list_clone); + ucx_test_register(suite, test_ucx_list_sort); /* UcxMemPool Tests */ ucx_test_register(suite, test_ucx_mempool_new); diff -r 311cac04d079 -r 540d99722f1f ucx/Makefile --- a/ucx/Makefile Mon Jul 22 11:39:06 2013 +0200 +++ b/ucx/Makefile Mon Jul 22 11:53:39 2013 +0200 @@ -30,7 +30,7 @@ # list of source files SRC = utils.c -SRC += dlist.c +SRC += list.c SRC += map.c SRC += properties.c SRC += mempool.c diff -r 311cac04d079 -r 540d99722f1f ucx/dlist.c --- a/ucx/dlist.c Mon Jul 22 11:39:06 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,270 +0,0 @@ -/* - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Copyright 2013 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 "dlist.h" - -UcxDlist *ucx_dlist_clone(UcxDlist *l, copy_func fnc, void *data) { - UcxDlist *ret = NULL; - while (l != NULL) { - if (fnc != NULL) { - ret = ucx_dlist_append(ret, fnc(l->data, data)); - } else { - ret = ucx_dlist_append(ret, l->data); - } - l = l->next; - } - return ret; -} - -int ucx_dlist_equals(const UcxDlist *l1, const UcxDlist *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_dlist_free(UcxDlist *l) { - UcxDlist *e = l, *f; - while (e != NULL) { - f = e; - e = e->next; - free(f); - } -} - -UcxDlist *ucx_dlist_append(UcxDlist *l, void *data) { - UcxDlist *nl = (UcxDlist*) malloc(sizeof(UcxDlist)); - if (nl == NULL) return NULL; - - nl->data = data; - nl->next = NULL; - if (l == NULL) { - nl->prev = NULL; - return nl; - } else { - UcxDlist *t = ucx_dlist_last(l); - t->next = nl; - nl->prev = t; - return l; - } -} - -UcxDlist *ucx_dlist_prepend(UcxDlist *l, void *data) { - UcxDlist *nl = ucx_dlist_append(NULL, data); - if (nl == NULL) return NULL; - - if (l != NULL) { - nl->next = l; - l->prev = nl; - } - return nl; -} - -UcxDlist *ucx_dlist_concat(UcxDlist *l1, UcxDlist *l2) { - if (l1 == NULL) { - return l2; - } else { - UcxDlist *last = ucx_dlist_last(l1); - last->next = l2; - l2->prev = last; - return l1; - } -} - -UcxDlist *ucx_dlist_last(const UcxDlist *l) { - if (l == NULL) return NULL; - - const UcxDlist *e = l; - while (e->next != NULL) { - e = e->next; - } - return (UcxDlist*)e; -} - -UcxDlist *ucx_dlist_get(const UcxDlist *l, int index) { - if (l == NULL) return NULL; - - const UcxDlist *e = l; - while (e->next != NULL && index > 0) { - e = e->next; - index--; - } - - return (UcxDlist*)(index == 0 ? e : NULL); -} - -int ucx_dlist_contains(UcxDlist *l, void *elem, cmp_func fnc, void *cmpdata) { - UCX_FOREACH(l, e) { - if (!fnc(elem, e->data, cmpdata)) { - return 1; - } - } - return 0; -} - -size_t ucx_dlist_size(const UcxDlist *l) { - if (l == NULL) return 0; - - const UcxDlist *e = l; - size_t s = 1; - while (e->next != NULL) { - e = e->next; - s++; - } - - return s; -} - -UcxDlist *ucx_dlist_sort_merge(int length, - UcxDlist* restrict ls, UcxDlist* restrict le, UcxDlist* restrict re, - cmp_func fnc, void* data) { - - UcxDlist** sorted = (UcxDlist**) malloc(sizeof(UcxDlist*)*length); - UcxDlist *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; - - UcxDlist *ret = sorted[0]; - free(sorted); - return ret; -} - -UcxDlist *ucx_dlist_sort(UcxDlist *l, cmp_func fnc, void *data) { - if (l == NULL) { - return NULL; - } - - UcxDlist *lc; - int ln = 1; - - UcxDlist *restrict ls = l, *restrict le, *restrict re; - 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 { - UcxDlist *rc; - int rn = 1; - rc = le; - while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { - rc = rc->next; - rn++; - } - re = rc->next; - - // Something left? Sort it! - UcxDlist *remainder = re; - size_t remainder_length = ucx_dlist_size(remainder); - if (remainder != NULL) { - remainder = ucx_dlist_sort(remainder, fnc, data); - } - - // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them - UcxDlist *sorted = ucx_dlist_sort_merge(ln+rn, - ls, le, re, - fnc, data); - - // merge sorted list with (also sorted) remainder - l = ucx_dlist_sort_merge(ln+rn+remainder_length, - sorted, remainder, NULL, fnc, data); - - return l; - } -} - -/* dlist specific functions */ -UcxDlist *ucx_dlist_first(const UcxDlist *l) { - if (l == NULL) return NULL; - - const UcxDlist *e = l; - while (e->prev != NULL) { - e = e->prev; - } - return (UcxDlist *)e; -} - -UcxDlist *ucx_dlist_remove(UcxDlist *l, UcxDlist *e) { - if (e->prev == NULL) { - if(e->next != NULL) { - e->next->prev = NULL; - l = e->next; - } else { - l = NULL; - } - - } else { - e->prev->next = e->next; - e->next->prev = e->prev; - } - free(e); - return l; -} diff -r 311cac04d079 -r 540d99722f1f ucx/dlist.h --- a/ucx/dlist.h Mon Jul 22 11:39:06 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,86 +0,0 @@ -/* - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Copyright 2013 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. - */ - -#ifndef UCX_DLIST_H -#define UCX_DLIST_H - -#include "ucx.h" -#include - -#ifdef __cplusplus -extern "C" { -#endif - -/** - * Loop statement for UCX lists. - * - * The first argument is a pointer to the list. In most cases this will be the - * pointer to the first element of the list, but it may also be an arbitrary - * element of the list. The iteration will then start with that element. - * - * The second argument is the name of the iteration variable. The scope of - * this variable is limited to the UCX_FOREACH statement. - * - * @param list The first element of the list - * @param elem The variable name of the element - */ -#define UCX_FOREACH(list,elem) \ - for (UcxDlist* elem = list ; elem != NULL ; elem = elem->next) - -typedef struct UcxDlist UcxDlist; -struct UcxDlist { - void *data; - UcxDlist *next; - UcxDlist *prev; -}; - -UcxDlist *ucx_dlist_clone(UcxDlist *l, copy_func fnc, void* data); -int ucx_dlist_equals(const UcxDlist *l1, const UcxDlist *l2, - cmp_func fnc, void* data); - -void ucx_dlist_free(UcxDlist *l); -UcxDlist *ucx_dlist_append(UcxDlist *l, void *data); -UcxDlist *ucx_dlist_prepend(UcxDlist *l, void *data); -UcxDlist *ucx_dlist_concat(UcxDlist *l1, UcxDlist *l2); -UcxDlist *ucx_dlist_last(const UcxDlist *l); -UcxDlist *ucx_dlist_get(const UcxDlist *l, int index); -size_t ucx_dlist_size(const UcxDlist *l); -int ucx_dlist_contains(UcxDlist *l, void *elem, cmp_func fnc, void *cmpdata); - -UcxDlist *ucx_dlist_sort(UcxDlist *l, cmp_func fnc, void *data); - -/* dlist specific functions */ -UcxDlist *ucx_dlist_first(const UcxDlist *l); -UcxDlist *ucx_dlist_remove(UcxDlist *l, UcxDlist *e); - -#ifdef __cplusplus -} -#endif - -#endif /* UCX_DLIST_H */ - diff -r 311cac04d079 -r 540d99722f1f ucx/list.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ucx/list.c Mon Jul 22 11:53:39 2013 +0200 @@ -0,0 +1,269 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2013 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 "list.h" + +UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) { + UcxList *ret = NULL; + while (l != NULL) { + if (fnc != NULL) { + ret = ucx_list_append(ret, fnc(l->data, data)); + } else { + ret = ucx_list_append(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) { + UcxList *e = l, *f; + while (e != NULL) { + f = e; + e = e->next; + free(f); + } +} + +UcxList *ucx_list_append(UcxList *l, void *data) { + UcxList *nl = (UcxList*) malloc(sizeof(UcxList)); + if (nl == NULL) return NULL; + + nl->data = data; + nl->next = NULL; + if (l == NULL) { + nl->prev = NULL; + return nl; + } else { + UcxList *t = ucx_list_last(l); + t->next = nl; + nl->prev = t; + return l; + } +} + +UcxList *ucx_list_prepend(UcxList *l, void *data) { + UcxList *nl = ucx_list_append(NULL, data); + if (nl == NULL) return NULL; + + if (l != NULL) { + nl->next = l; + l->prev = nl; + } + return nl; +} + +UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) { + if (l1 == NULL) { + return l2; + } else { + UcxList *last = ucx_list_last(l1); + last->next = l2; + l2->prev = last; + return l1; + } +} + +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; +} + +UcxList *ucx_list_get(const UcxList *l, int index) { + if (l == NULL) return NULL; + + const UcxList *e = l; + while (e->next != NULL && index > 0) { + e = e->next; + index--; + } + + return (UcxList*)(index == 0 ? e : NULL); +} + +int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) { + UCX_FOREACH(e, l) { + if (!fnc(elem, e->data, cmpdata)) { + return 1; + } + } + return 0; +} + +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; +} + +UcxList *ucx_list_sort_merge(int length, + UcxList* restrict ls, UcxList* restrict le, UcxList* restrict 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 *restrict ls = l, *restrict le, *restrict re; + 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; + while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { + rc = rc->next; + rn++; + } + re = rc->next; + + // Something left? Sort it! + UcxList *remainder = re; + size_t remainder_length = ucx_list_size(remainder); + if (remainder != NULL) { + remainder = ucx_list_sort(remainder, fnc, data); + } + + // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them + UcxList *sorted = ucx_list_sort_merge(ln+rn, + ls, le, re, + fnc, data); + + // merge sorted list with (also sorted) remainder + l = ucx_list_sort_merge(ln+rn+remainder_length, + sorted, remainder, NULL, fnc, data); + + return l; + } +} + +UcxList *ucx_list_first(const UcxList *l) { + if (l == NULL) return NULL; + + const UcxList *e = l; + while (e->prev != NULL) { + e = e->prev; + } + return (UcxList *)e; +} + +UcxList *ucx_list_remove(UcxList *l, UcxList *e) { + if (e->prev == NULL) { + if(e->next != NULL) { + e->next->prev = NULL; + l = e->next; + } else { + l = NULL; + } + + } else { + e->prev->next = e->next; + e->next->prev = e->prev; + } + free(e); + return l; +} diff -r 311cac04d079 -r 540d99722f1f ucx/list.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ucx/list.h Mon Jul 22 11:53:39 2013 +0200 @@ -0,0 +1,85 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2013 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. + */ + +#ifndef UCX_LIST_H +#define UCX_LIST_H + +#include "ucx.h" +#include + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * Loop statement for UCX lists. + * + * The first argument is a pointer to the list. In most cases this will be the + * pointer to the first element of the list, but it may also be an arbitrary + * element of the list. The iteration will then start with that element. + * + * The second argument is the name of the iteration variable. The scope of + * this variable is limited to the UCX_FOREACH statement. + * + * @param list The first element of the list + * @param elem The variable name of the element + */ +#define UCX_FOREACH(elem,list) \ + for (UcxList* elem = list ; elem != NULL ; elem = elem->next) + +typedef struct UcxList UcxList; +struct UcxList { + void *data; + UcxList *next; + UcxList *prev; +}; + +UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void* data); +int ucx_list_equals(const UcxList *l1, const UcxList *l2, + cmp_func fnc, void* data); + +void ucx_list_free(UcxList *l); +UcxList *ucx_list_append(UcxList *l, void *data); +UcxList *ucx_list_prepend(UcxList *l, void *data); +UcxList *ucx_list_concat(UcxList *l1, UcxList *l2); +UcxList *ucx_list_last(const UcxList *l); +UcxList *ucx_list_get(const UcxList *l, int index); +size_t ucx_list_size(const UcxList *l); +int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata); + +UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data); + +UcxList *ucx_list_first(const UcxList *l); +UcxList *ucx_list_remove(UcxList *l, UcxList *e); + +#ifdef __cplusplus +} +#endif + +#endif /* UCX_LIST_H */ +