# HG changeset patch # User Mike Becker # Date 1479478624 -3600 # Node ID 9f385abc72fb912466e51640742111e41a6576f6 # Parent 740fbd7bab717c9db8113320d55f11bca1a92dd0 adds ucx_list_append_once() and ucx_list_prepend_once() diff -r 740fbd7bab71 -r 9f385abc72fb Makefile --- a/Makefile Thu Oct 13 16:25:21 2016 +0200 +++ b/Makefile Fri Nov 18 15:17:04 2016 +0100 @@ -49,10 +49,10 @@ ucx-debug: FORCE cd ucx; $(MAKE) CONF=$(CONF) debug -test: ucx +test: ucx FORCE cd test; $(MAKE) CONF=$(CONF) -test-debug: ucx-debug +test-debug: ucx-debug FORCE cd test; $(MAKE) CONF=$(CONF) debug run: test diff -r 740fbd7bab71 -r 9f385abc72fb test/list_tests.c --- a/test/list_tests.c Thu Oct 13 16:25:21 2016 +0200 +++ b/test/list_tests.c Fri Nov 18 15:17:04 2016 +0100 @@ -68,6 +68,49 @@ ucx_list_free(list); } +UCX_TEST(test_ucx_list_append_once) { + UcxList *list, *first; + list = first = ucx_list_append_once(NULL, (void*)"Hello", ucx_strcmp, NULL); + UCX_TEST_BEGIN + + UCX_TEST_ASSERT(strncmp((const char*)list->data, "Hello", 5) == 0, + "failed"); + + list = ucx_list_append_once(list, (void*)"Hello", ucx_strcmp, NULL); + list = ucx_list_append_once(list, (void*)" World!", ucx_strcmp, NULL); + + UCX_TEST_ASSERT(list == first, "does not return first element"); + UCX_TEST_ASSERT(strncmp((const char*)list->next->data, " World!", 7) == 0, + "'Hello' was not inserted _once_"); + UCX_TEST_ASSERT(list->next->prev == list, "failed"); + UCX_TEST_ASSERT(list->next->next == NULL, "right not terminated"); + UCX_TEST_END + + ucx_list_free(list); +} + +UCX_TEST(test_ucx_list_prepend_once) { + UcxList *list, *last, *first; + list = last = ucx_list_prepend_once(NULL, (void*)" World!", + ucx_strcmp, NULL); + UCX_TEST_BEGIN + + list = ucx_list_prepend_once(list, (void*)"Hello", ucx_strcmp, NULL); + first = ucx_list_prepend_once(list, (void*)"Hello", ucx_strcmp, NULL); + + UCX_TEST_ASSERT(list == first, "'Hello' was not prepended _once_"); + UCX_TEST_ASSERT(first == last->prev, "does not return first element"); + 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, "right not terminated"); + UCX_TEST_ASSERT(list->prev == NULL, "left not terminated"); + + UCX_TEST_END + ucx_list_free(list); +} + UCX_TEST(test_ucx_list_equals) { const char *hello = "Hello"; const char *world = " World!"; diff -r 740fbd7bab71 -r 9f385abc72fb test/list_tests.h --- a/test/list_tests.h Thu Oct 13 16:25:21 2016 +0200 +++ b/test/list_tests.h Fri Nov 18 15:17:04 2016 +0100 @@ -45,6 +45,8 @@ UCX_TEST(test_ucx_list_append); UCX_TEST(test_ucx_list_prepend); +UCX_TEST(test_ucx_list_append_once); +UCX_TEST(test_ucx_list_prepend_once); UCX_TEST(test_ucx_list_equals); UCX_TEST(test_ucx_list_concat); UCX_TEST(test_ucx_list_size); diff -r 740fbd7bab71 -r 9f385abc72fb test/main.c --- a/test/main.c Thu Oct 13 16:25:21 2016 +0200 +++ b/test/main.c Fri Nov 18 15:17:04 2016 +0100 @@ -137,6 +137,8 @@ /* UcxList Tests */ ucx_test_register(suite, test_ucx_list_append); ucx_test_register(suite, test_ucx_list_prepend); + ucx_test_register(suite, test_ucx_list_append_once); + ucx_test_register(suite, test_ucx_list_prepend_once); ucx_test_register(suite, test_ucx_list_equals); ucx_test_register(suite, test_ucx_list_concat); ucx_test_register(suite, test_ucx_list_size); diff -r 740fbd7bab71 -r 9f385abc72fb ucx/list.c --- a/ucx/list.c Thu Oct 13 16:25:21 2016 +0200 +++ b/ucx/list.c Fri Nov 18 15:17:04 2016 +0100 @@ -106,6 +106,41 @@ } } +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(UcxList *l, void *data) { return ucx_list_prepend_a(ucx_default_allocator(), l, data); } @@ -124,6 +159,40 @@ return nl; } +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) { + + if (l) { + int found = 0; + UcxList *first; + { + UcxList *e = l; + while (e) { + found |= (cmpfnc(e->data, data, cmpdata) == 0); + first = e; + e = e->prev; + } + } + + if (found) { + return first; + } else { + UcxList *nl = ucx_list_append_a(alloc, NULL, data); + nl->next = first; + first->prev = nl; + return nl; + } + } else { + return ucx_list_append_a(alloc, NULL, data); + } +} + UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) { if (l1) { UcxList *last = ucx_list_last(l1); diff -r 740fbd7bab71 -r 9f385abc72fb ucx/list.h --- a/ucx/list.h Thu Oct 13 16:25:21 2016 +0200 +++ b/ucx/list.h Fri Nov 18 15:17:04 2016 +0100 @@ -211,6 +211,41 @@ UcxList *ucx_list_append_a(UcxAllocator *allocator, UcxList *list, void *data); /** + * Inserts an element at the end of the list, if it is not present in the list. + * + * + * @param list the list where to append the data, or NULL to + * create a new list + * @param data the data to insert + * @param cmpfnc the compare function + * @param cmpdata additional data for the compare function + * @return list, if it is not NULL or a pointer to + * the newly created list otherwise + * @see ucx_list_append() + */ +UcxList *ucx_list_append_once(UcxList *list, void *data, + cmp_func cmpfnc, void *cmpdata); + +/** + * Inserts an element at the end of the list, if it is not present in the list, + * using a UcxAllocator. + * + * See ucx_list_append() for details. + * + * @param allocator the allocator to use + * @param list the list where to append the data, or NULL to + * create a new list + * @param data the data to insert + * @param cmpfnc the compare function + * @param cmpdata additional data for the compare function + * @return list, if it is not NULL or a pointer to + * the newly created list otherwise + * @see ucx_list_append_a() + */ +UcxList *ucx_list_append_once_a(UcxAllocator *allocator, + UcxList *list, void *data, cmp_func cmpfnc, void *cmpdata); + +/** * Inserts an element at the beginning of the list. * * You should overwrite the old list pointer by calling @@ -241,6 +276,37 @@ UcxList *ucx_list_prepend_a(UcxAllocator *allocator, UcxList *list, void *data); /** + * Inserts an element at the beginning of the list, if it is not present + * in the list. + * + * @param list the list where to insert the data or NULL to create + * a new list + * @param data the data to insert + * @param cmpfnc the compare function + * @param cmpdata additional data for the compare function + * @return a pointer to the new list head + * @see ucx_list_prepend() + */ +UcxList *ucx_list_prepend_once(UcxList *list, void *data, + cmp_func cmpfnc, void *cmpdata); + +/** + * Inserts an element at the beginning of the list, if it is not present in + * the list, using a UcxAllocator. + * + * @param allocator the allocator to use + * @param list the list where to insert the data or NULL to create + * a new list + * @param data the data to insert + * @param cmpfnc the compare function + * @param cmpdata additional data for the compare function + * @return a pointer to the new list head + * @see ucx_list_prepend_a() + */ +UcxList *ucx_list_prepend_once_a(UcxAllocator *allocator, + UcxList *list, void *data, cmp_func cmpfnc, void *cmpdata); + +/** * Concatenates two lists. * * Either of the two arguments may be NULL. diff -r 740fbd7bab71 -r 9f385abc72fb ucx/ucx.h --- a/ucx/ucx.h Thu Oct 13 16:25:21 2016 +0200 +++ b/ucx/ucx.h Fri Nov 18 15:17:04 2016 +0100 @@ -40,7 +40,7 @@ #define UCX_VERSION_MAJOR 0 /** Minor UCX version as integer constant. */ -#define UCX_VERSION_MINOR 10 +#define UCX_VERSION_MINOR 11 #include