Mercurial > hg > ucx / changeset

     1.1 --- a/src/CMakeLists.txt	Tue Oct 05 16:33:11 2021 +0200
     1.2 +++ b/src/CMakeLists.txt	Wed Oct 06 14:10:19 2021 +0200
     1.3 @@ -1,6 +1,5 @@
     1.4  set(sources
     1.5          allocator.c
     1.6 -        list.c
     1.7          linked_list.c
     1.8          tree.c
     1.9  )

     2.1 --- a/src/cx/list.h	Tue Oct 05 16:33:11 2021 +0200
     2.2 +++ b/src/cx/list.h	Wed Oct 06 14:10:19 2021 +0200
     2.3 @@ -87,6 +87,11 @@
     2.4       * Member function for retrieving the last element.
     2.5       */
     2.6      void *(*last)(cx_list_s *list);
     2.7 +
     2.8 +    /**
     2.9 +     * Member function for sorting the list in place.
    2.10 +     */
    2.11 +    void (*sort)(cx_list_s *list);
    2.12  } cx_list_class;
    2.13  
    2.14  /**
    2.15 @@ -136,7 +141,9 @@
    2.16   * @param elem a pointer to the element to add
    2.17   * @return zero on success, non-zero on memory allocation failure
    2.18   */
    2.19 -int cxListAdd(CxList list, void *elem);
    2.20 +static inline int cxListAdd(CxList list, void *elem) {
    2.21 +    return list->cl->add(list, elem);
    2.22 +}
    2.23  
    2.24  /**
    2.25   * Inserts an item at the specified index.
    2.26 @@ -154,7 +161,9 @@
    2.27   * @return zero on success, non-zero on memory allocation failure
    2.28   * or when the index is out of bounds
    2.29   */
    2.30 -int cxListInsert(CxList list, size_t index, void *elem);
    2.31 +static inline int cxListInsert(CxList list, size_t index, void *elem) {
    2.32 +    return list->cl->insert(list, index, elem);
    2.33 +}
    2.34  
    2.35  /**
    2.36   * Removes the element at the specified index.
    2.37 @@ -162,7 +171,9 @@
    2.38   * @param index the index of the element
    2.39   * @return zero on success, non-zero if the index is out of bounds
    2.40   */
    2.41 -int cxListRemove(CxList list, size_t index);
    2.42 +static inline int cxListRemove(CxList list, size_t index) {
    2.43 +    return list->cl->remove(list, index);
    2.44 +}
    2.45  
    2.46  /**
    2.47   * Returns a pointer to the element at the specified index.
    2.48 @@ -171,7 +182,9 @@
    2.49   * @param index the index of the element
    2.50   * @return a pointer to the element or \c NULL if the index is out of bounds
    2.51   */
    2.52 -void *cxListAt(CxList list, size_t index);
    2.53 +static inline void *cxListAt(CxList list, size_t index) {
    2.54 +    return list->cl->at(list, index);
    2.55 +}
    2.56  
    2.57  /**
    2.58   * Returns the index of the first element that equals \p elem.
    2.59 @@ -182,7 +195,9 @@
    2.60   * @param elem the element to find
    2.61   * @return the index of the element or \c (size+1) if the element is not found
    2.62   */
    2.63 -size_t cxListFind(CxList list, void *elem);
    2.64 +static inline size_t cxListFind(CxList list, void *elem) {
    2.65 +    return list->cl->find(list, elem);
    2.66 +}
    2.67  
    2.68  /**
    2.69   * Returns a pointer to the last element of the list.
    2.70 @@ -194,7 +209,20 @@
    2.71   * @param list the list
    2.72   * @return a pointer to the last element or \c NULL if the list is empty
    2.73   */
    2.74 -void *cxListLast(CxList list);
    2.75 +static inline void *cxListLast(CxList list) {
    2.76 +    return list->cl->last(list);
    2.77 +}
    2.78 +
    2.79 +/**
    2.80 + * Sorts the list in place.
    2.81 + *
    2.82 + * \remark The underlying sort algorithm is implementation defined.
    2.83 + *
    2.84 + * @param list the list
    2.85 + */
    2.86 +static inline void cxListSort(CxList list) {
    2.87 +    list->cl->sort(list);
    2.88 +}
    2.89  
    2.90  #ifdef __cplusplus
    2.91  } /* extern "C" */

     3.1 --- a/src/linked_list.c	Tue Oct 05 16:33:11 2021 +0200
     3.2 +++ b/src/linked_list.c	Wed Oct 06 14:10:19 2021 +0200
     3.3 @@ -212,6 +212,7 @@
     3.4  
     3.5  #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
     3.6  #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
     3.7 +#define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
     3.8  
     3.9  typedef struct {
    3.10      cx_list_s base;
    3.11 @@ -380,13 +381,28 @@
    3.12      return last == NULL ? NULL : *(void **) last->payload;
    3.13  }
    3.14  
    3.15 +static void cx_ll_sort(cx_list_s *list) {
    3.16 +    cx_linked_list *ll = (cx_linked_list *) list;
    3.17 +    cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
    3.18 +                        CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
    3.19 +                        0, list->cmpfunc);
    3.20 +}
    3.21 +
    3.22 +static void cx_pll_sort(cx_list_s *list) {
    3.23 +    cx_linked_list *ll = (cx_linked_list *) list;
    3.24 +    cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
    3.25 +                        CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
    3.26 +                        1, list->cmpfunc);
    3.27 +}
    3.28 +
    3.29  static cx_list_class cx_linked_list_class = {
    3.30          cx_ll_add,
    3.31          cx_ll_insert,
    3.32          cx_ll_remove,
    3.33          cx_ll_at,
    3.34          cx_ll_find,
    3.35 -        cx_ll_last
    3.36 +        cx_ll_last,
    3.37 +        cx_ll_sort
    3.38  };
    3.39  
    3.40  static cx_list_class cx_pointer_linked_list_class = {
    3.41 @@ -395,7 +411,8 @@
    3.42          cx_ll_remove,
    3.43          cx_pll_at,
    3.44          cx_pll_find,
    3.45 -        cx_pll_last
    3.46 +        cx_pll_last,
    3.47 +        cx_pll_sort
    3.48  };
    3.49  
    3.50  CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {

     4.1 --- a/src/list.c	Tue Oct 05 16:33:11 2021 +0200
     4.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.3 @@ -1,53 +0,0 @@
     4.4 -/*
     4.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     4.6 - *
     4.7 - * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
     4.8 - *
     4.9 - * Redistribution and use in source and binary forms, with or without
    4.10 - * modification, are permitted provided that the following conditions are met:
    4.11 - *
    4.12 - *   1. Redistributions of source code must retain the above copyright
    4.13 - *      notice, this list of conditions and the following disclaimer.
    4.14 - *
    4.15 - *   2. Redistributions in binary form must reproduce the above copyright
    4.16 - *      notice, this list of conditions and the following disclaimer in the
    4.17 - *      documentation and/or other materials provided with the distribution.
    4.18 - *
    4.19 - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    4.20 - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    4.21 - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    4.22 - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    4.23 - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    4.24 - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    4.25 - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    4.26 - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    4.27 - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    4.28 - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    4.29 - * POSSIBILITY OF SUCH DAMAGE.
    4.30 - */
    4.31 -
    4.32 -#include "cx/list.h"
    4.33 -
    4.34 -int cxListAdd(CxList list, void *elem) {
    4.35 -    return list->cl->add(list, elem);
    4.36 -}
    4.37 -
    4.38 -int cxListInsert(CxList list, size_t index, void *elem) {
    4.39 -    return list->cl->insert(list, index, elem);
    4.40 -}
    4.41 -
    4.42 -int cxListRemove(CxList list, size_t index) {
    4.43 -    return list->cl->remove(list, index);
    4.44 -}
    4.45 -
    4.46 -void *cxListAt(CxList list, size_t index) {
    4.47 -    return list->cl->at(list, index);
    4.48 -}
    4.49 -
    4.50 -size_t cxListFind(CxList list, void *elem) {
    4.51 -    return list->cl->find(list, elem);
    4.52 -}
    4.53 -
    4.54 -void *cxListLast(CxList list) {
    4.55 -    return list->cl->last(list);
    4.56 -}

     5.1 --- a/test/test_list.c	Tue Oct 05 16:33:11 2021 +0200
     5.2 +++ b/test/test_list.c	Wed Oct 06 14:10:19 2021 +0200
     5.3 @@ -393,6 +393,42 @@
     5.4      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
     5.5  }
     5.6  
     5.7 +void test_hl_linked_list_sort(void) {
     5.8 +    int expected[] = {
     5.9 +            14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
    5.10 +            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
    5.11 +            1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
    5.12 +            2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
    5.13 +            3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
    5.14 +            4785, 4791, 4801, 4859, 4903, 4973
    5.15 +    };
    5.16 +    int scrambled[] = {
    5.17 +            759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
    5.18 +            2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
    5.19 +            2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
    5.20 +            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
    5.21 +            3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
    5.22 +            4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
    5.23 +    };
    5.24 +
    5.25 +    cxTestingAllocatorReset();
    5.26 +
    5.27 +    CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
    5.28 +
    5.29 +    for (int i = 0 ; i < 100 ; i++) {
    5.30 +        cxListAdd(list, &scrambled[i]);
    5.31 +    }
    5.32 +
    5.33 +    cxListSort(list);
    5.34 +
    5.35 +    for (int i = 0 ; i < 100 ; i++) {
    5.36 +        CU_ASSERT_EQUAL(*(int*)cxListAt(list, i), expected[i])
    5.37 +    }
    5.38 +
    5.39 +    cxLinkedListDestroy(list);
    5.40 +    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    5.41 +}
    5.42 +
    5.43  void test_hl_ptr_linked_list_create(void) {
    5.44      cxTestingAllocatorReset();
    5.45  
    5.46 @@ -558,6 +594,42 @@
    5.47      CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    5.48  }
    5.49  
    5.50 +void test_hl_ptr_linked_list_sort(void) {
    5.51 +    int expected[] = {
    5.52 +            14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
    5.53 +            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
    5.54 +            1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
    5.55 +            2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
    5.56 +            3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
    5.57 +            4785, 4791, 4801, 4859, 4903, 4973
    5.58 +    };
    5.59 +    int scrambled[] = {
    5.60 +            759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
    5.61 +            2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
    5.62 +            2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
    5.63 +            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
    5.64 +            3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
    5.65 +            4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
    5.66 +    };
    5.67 +
    5.68 +    cxTestingAllocatorReset();
    5.69 +
    5.70 +    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
    5.71 +
    5.72 +    for (int i = 0 ; i < 100 ; i++) {
    5.73 +        cxListAdd(list, &scrambled[i]);
    5.74 +    }
    5.75 +
    5.76 +    cxListSort(list);
    5.77 +
    5.78 +    for (int i = 0 ; i < 100 ; i++) {
    5.79 +        CU_ASSERT_EQUAL(*(int*)cxListAt(list, i), expected[i])
    5.80 +    }
    5.81 +
    5.82 +    cxLinkedListDestroy(list);
    5.83 +    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    5.84 +}
    5.85 +
    5.86  int main() {
    5.87      CU_pSuite suite = NULL;
    5.88  
    5.89 @@ -581,6 +653,7 @@
    5.90      cu_add_test(suite, test_hl_linked_list_insert);
    5.91      cu_add_test(suite, test_hl_linked_list_remove);
    5.92      cu_add_test(suite, test_hl_linked_list_find);
    5.93 +    cu_add_test(suite, test_hl_linked_list_sort);
    5.94  
    5.95      suite = CU_add_suite("high level pointer linked list", NULL, NULL);
    5.96  
    5.97 @@ -590,6 +663,7 @@
    5.98      cu_add_test(suite, test_hl_ptr_linked_list_insert);
    5.99      cu_add_test(suite, test_hl_ptr_linked_list_remove);
   5.100      cu_add_test(suite, test_hl_ptr_linked_list_find);
   5.101 +    cu_add_test(suite, test_hl_ptr_linked_list_sort);
   5.102  
   5.103      CU_basic_set_mode(UCX_CU_BRM);
   5.104