Mercurial > hg > ucx / changeset

     1.1 --- a/test/Makefile	Fri Jun 01 12:35:30 2012 +0200
     1.2 +++ b/test/Makefile	Wed Aug 15 19:32:29 2012 +0200
     1.3 @@ -37,6 +37,8 @@
     1.4  ../build/test1: $(OBJ)
     1.5  	$(LD) $(LDFLAGS) -o ../build/test$(APP_EXT) $(OBJ) ../build/libucx.a
     1.6  
     1.7 -../build/%.$(OBJ_EXT): %.c
     1.8 +../build/%.$(OBJ_EXT): %.c ../build
     1.9  	$(CC) $(CFLAGS) -I../ -o $@ -c $<
    1.10  
    1.11 +../build:
    1.12 +	mkdir -p build

     2.1 --- a/test/dlist_tests.c	Fri Jun 01 12:35:30 2012 +0200
     2.2 +++ b/test/dlist_tests.c	Wed Aug 15 19:32:29 2012 +0200
     2.3 @@ -165,3 +165,37 @@
     2.4      ucx_dlist_free(list);
     2.5      ucx_dlist_free(copy);
     2.6  }
     2.7 +
     2.8 +UCX_TEST_IMPLEMENT(test_ucx_dlist_qsort) {
     2.9 +    UcxDlist *list = ucx_dlist_append(NULL, "this");
    2.10 +    list = ucx_dlist_append(list, "is");
    2.11 +    list = ucx_dlist_append(list, "a");
    2.12 +    list = ucx_dlist_append(list, "test");
    2.13 +    list = ucx_dlist_append(list, "for");
    2.14 +    list = ucx_dlist_append(list, "partial");
    2.15 +    list = ucx_dlist_append(list, "correctness");
    2.16 +
    2.17 +    UcxDlist *expected = ucx_dlist_append(NULL, "a");
    2.18 +    expected = ucx_dlist_append(expected, "correctness");
    2.19 +    expected = ucx_dlist_append(expected, "for");
    2.20 +    expected = ucx_dlist_append(expected, "is");
    2.21 +    expected = ucx_dlist_append(expected, "partial");
    2.22 +    expected = ucx_dlist_append(expected, "test");
    2.23 +    expected = ucx_dlist_append(expected, "this");
    2.24 +
    2.25 +    list = ucx_dlist_qsort(list, cmp_string, NULL);
    2.26 +
    2.27 +    UCX_TEST_BEGIN
    2.28 +    UCX_TEST_ASSERT(
    2.29 +            ucx_dlist_equals(list, expected, cmp_string, NULL), "failed");
    2.30 +    UcxDlist *l = list;
    2.31 +    UCX_TEST_ASSERT(l->prev == NULL, "prev field of first entry is not null");
    2.32 +    while (l->next != NULL) {
    2.33 +        UCX_TEST_ASSERT(l->next->prev == l, "prev pointer corrupted");
    2.34 +        l = l->next;
    2.35 +    }
    2.36 +    UCX_TEST_END
    2.37 +
    2.38 +    ucx_dlist_free(expected);
    2.39 +    ucx_dlist_free(list);
    2.40 +}

     3.1 --- a/test/dlist_tests.h	Fri Jun 01 12:35:30 2012 +0200
     3.2 +++ b/test/dlist_tests.h	Wed Aug 15 19:32:29 2012 +0200
     3.3 @@ -32,6 +32,7 @@
     3.4  UCX_TEST_DECLARE(test_ucx_dlist_get)
     3.5  UCX_TEST_DECLARE(test_ucx_dlist_remove)
     3.6  UCX_TEST_DECLARE(test_ucx_dlist_clone)
     3.7 +UCX_TEST_DECLARE(test_ucx_dlist_qsort)
     3.8  
     3.9  #ifdef	__cplusplus
    3.10  }

     4.1 --- a/test/list_tests.c	Fri Jun 01 12:35:30 2012 +0200
     4.2 +++ b/test/list_tests.c	Wed Aug 15 19:32:29 2012 +0200
     4.3 @@ -153,3 +153,31 @@
     4.4      ucx_list_free(list);
     4.5      ucx_list_free(copy);
     4.6  }
     4.7 +
     4.8 +UCX_TEST_IMPLEMENT(test_ucx_list_qsort) {
     4.9 +    UcxList *list = ucx_list_append(NULL, "this");
    4.10 +    list = ucx_list_append(list, "is");
    4.11 +    list = ucx_list_append(list, "a");
    4.12 +    list = ucx_list_append(list, "test");
    4.13 +    list = ucx_list_append(list, "for");
    4.14 +    list = ucx_list_append(list, "partial");
    4.15 +    list = ucx_list_append(list, "correctness");
    4.16 +
    4.17 +    UcxList *expected = ucx_list_append(NULL, "a");
    4.18 +    expected = ucx_list_append(expected, "correctness");
    4.19 +    expected = ucx_list_append(expected, "for");
    4.20 +    expected = ucx_list_append(expected, "is");
    4.21 +    expected = ucx_list_append(expected, "partial");
    4.22 +    expected = ucx_list_append(expected, "test");
    4.23 +    expected = ucx_list_append(expected, "this");
    4.24 +
    4.25 +    list = ucx_list_qsort(list, cmp_string, NULL);
    4.26 +
    4.27 +    UCX_TEST_BEGIN
    4.28 +    UCX_TEST_ASSERT(
    4.29 +            ucx_list_equals(list, expected, cmp_string, NULL), "failed");
    4.30 +    UCX_TEST_END
    4.31 +
    4.32 +    ucx_list_free(expected);
    4.33 +    ucx_list_free(list);
    4.34 +}

     5.1 --- a/test/list_tests.h	Fri Jun 01 12:35:30 2012 +0200
     5.2 +++ b/test/list_tests.h	Wed Aug 15 19:32:29 2012 +0200
     5.3 @@ -31,6 +31,7 @@
     5.4  UCX_TEST_DECLARE(test_ucx_list_get)
     5.5  UCX_TEST_DECLARE(test_ucx_list_remove)
     5.6  UCX_TEST_DECLARE(test_ucx_list_clone)
     5.7 +UCX_TEST_DECLARE(test_ucx_list_qsort)
     5.8  
     5.9  #ifdef	__cplusplus
    5.10  }

     6.1 --- a/test/main.c	Fri Jun 01 12:35:30 2012 +0200
     6.2 +++ b/test/main.c	Wed Aug 15 19:32:29 2012 +0200
     6.3 @@ -116,6 +116,7 @@
     6.4          ucx_test_register(suite, test_ucx_list_get);
     6.5          ucx_test_register(suite, test_ucx_list_remove);
     6.6          ucx_test_register(suite, test_ucx_list_clone);
     6.7 +        ucx_test_register(suite, test_ucx_list_qsort);
     6.8          
     6.9          /* UcxDlist Tests */
    6.10          ucx_test_register(suite, test_ucx_dlist_append);
    6.11 @@ -128,6 +129,7 @@
    6.12          ucx_test_register(suite, test_ucx_dlist_get);
    6.13          ucx_test_register(suite, test_ucx_dlist_remove);
    6.14          ucx_test_register(suite, test_ucx_dlist_clone);
    6.15 +        ucx_test_register(suite, test_ucx_dlist_qsort);
    6.16  
    6.17          /* UcxMemPool Tests */
    6.18          ucx_test_register(suite, test_ucx_mempool_new);

     7.1 --- a/ucx/Makefile	Fri Jun 01 12:35:30 2012 +0200
     7.2 +++ b/ucx/Makefile	Wed Aug 15 19:32:29 2012 +0200
     7.3 @@ -38,6 +38,8 @@
     7.4  libucx: $(OBJ)
     7.5  	$(AR) $(ARFLAGS) ../build/libucx.$(LIB_EXT) $(OBJ)
     7.6  
     7.7 -../build/%.$(OBJ_EXT): %.c
     7.8 +../build/%.$(OBJ_EXT): %.c ../build
     7.9  	$(CC) $(CFLAGS) -c $< -o $@
    7.10  
    7.11 +../build:
    7.12 +	mkdir -p ../build

     8.1 --- a/ucx/dlist.c	Fri Jun 01 12:35:30 2012 +0200
     8.2 +++ b/ucx/dlist.c	Wed Aug 15 19:32:29 2012 +0200
     8.3 @@ -112,6 +112,66 @@
     8.4      return s;
     8.5  }
     8.6  
     8.7 +int ucx_dlist_qsort_devide(UcxDlist** list, int l, int r, cmp_func f, void* d) {
     8.8 +    int i = l;
     8.9 +    int j = r - 1;
    8.10 +    void *p = list[r]->data;
    8.11 +    UcxDlist *b;
    8.12 +
    8.13 +    do {
    8.14 +        while (i < r && f(list[i]->data, p, d) <= 0) i++;
    8.15 +        while (j > l && f(list[j]->data, p, d) >= 0) j--;
    8.16 +        if (i < j) {
    8.17 +            b = list[i];
    8.18 +            list[i] = list[j];
    8.19 +            list[j] = b;
    8.20 +        }
    8.21 +    } while (i < j);
    8.22 +
    8.23 +    if (f(list[i]->data, p, d) > 0) {
    8.24 +        b = list[r];
    8.25 +        list[r] = list[i];
    8.26 +        list[i] = b;
    8.27 +    }
    8.28 +
    8.29 +    return i;
    8.30 +}
    8.31 +
    8.32 +void ucx_dlist_qsort_sort(UcxDlist** list, int l, int r, cmp_func f, void* d) {
    8.33 +    if (l < r) {
    8.34 +        int m = ucx_dlist_qsort_devide(list, l, r, f, d);
    8.35 +        ucx_dlist_qsort_sort(list, l, m-1, f, d);
    8.36 +        ucx_dlist_qsort_sort(list, m+1, r, f, d);
    8.37 +    }
    8.38 +}
    8.39 +
    8.40 +UcxDlist *ucx_dlist_qsort(UcxDlist *l, cmp_func fnc, void *data) {
    8.41 +    if (l == NULL) {
    8.42 +        return NULL;
    8.43 +    }
    8.44 +    size_t n = ucx_dlist_size(l);
    8.45 +    if (n == 1) {
    8.46 +        return l;
    8.47 +    }
    8.48 +
    8.49 +    UcxDlist *entries[n];
    8.50 +    entries[0] = l;
    8.51 +    for (int i = 1 ; i < n ; i++) {
    8.52 +      entries[i] = entries[i-1]->next;
    8.53 +    }
    8.54 +
    8.55 +    ucx_dlist_qsort_sort(entries, 0, n-1, fnc, data);
    8.56 +
    8.57 +    entries[0]->prev = NULL;
    8.58 +    for (int i = 0 ; i < n-1 ; i++) {
    8.59 +      entries[i]->next = entries[i+1];
    8.60 +      entries[i+1]->prev = entries[i];
    8.61 +    }
    8.62 +    entries[n-1]->next = NULL;
    8.63 +
    8.64 +    return entries[0];
    8.65 +}
    8.66 +
    8.67  /* dlist specific functions */
    8.68  UcxDlist *ucx_dlist_first(UcxDlist *l) {
    8.69      if (l == NULL) return NULL;

     9.1 --- a/ucx/dlist.h	Fri Jun 01 12:35:30 2012 +0200
     9.2 +++ b/ucx/dlist.h	Wed Aug 15 19:32:29 2012 +0200
     9.3 @@ -30,6 +30,8 @@
     9.4  UcxDlist *ucx_dlist_get(UcxDlist *l, int index);
     9.5  size_t ucx_dlist_size(UcxDlist *l);
     9.6  
     9.7 +UcxDlist *ucx_dlist_qsort(UcxDlist *l, cmp_func fnc, void *data);
     9.8 +
     9.9  /* dlist specific functions */
    9.10  UcxDlist *ucx_dlist_first(UcxDlist *l);
    9.11  UcxDlist *ucx_dlist_remove(UcxDlist *l, UcxDlist *e);

    10.1 --- a/ucx/list.c	Fri Jun 01 12:35:30 2012 +0200
    10.2 +++ b/ucx/list.c	Wed Aug 15 19:32:29 2012 +0200
    10.3 @@ -108,6 +108,64 @@
    10.4      return s;
    10.5  }
    10.6  
    10.7 +int ucx_list_qsort_devide(UcxList** list, int l, int r, cmp_func f, void* d) {
    10.8 +    int i = l;
    10.9 +    int j = r - 1;
   10.10 +    void *p = list[r]->data;
   10.11 +    UcxList *b;
   10.12 +
   10.13 +    do {
   10.14 +        while (i < r && f(list[i]->data, p, d) <= 0) i++;
   10.15 +        while (j > l && f(list[j]->data, p, d) >= 0) j--;
   10.16 +        if (i < j) {
   10.17 +            b = list[i];
   10.18 +            list[i] = list[j];
   10.19 +            list[j] = b;
   10.20 +        }
   10.21 +    } while (i < j);
   10.22 +
   10.23 +    if (f(list[i]->data, p, d) > 0) {
   10.24 +        b = list[r];
   10.25 +        list[r] = list[i];
   10.26 +        list[i] = b;
   10.27 +    }
   10.28 +
   10.29 +    return i;
   10.30 +}
   10.31 +
   10.32 +void ucx_list_qsort_sort(UcxList** list, int l, int r, cmp_func f, void* d) {
   10.33 +    if (l < r) {
   10.34 +        int m = ucx_list_qsort_devide(list, l, r, f, d);
   10.35 +        ucx_list_qsort_sort(list, l, m-1, f, d);
   10.36 +        ucx_list_qsort_sort(list, m+1, r, f, d);
   10.37 +    }
   10.38 +}
   10.39 +
   10.40 +UcxList *ucx_list_qsort(UcxList *l, cmp_func fnc, void *data) {
   10.41 +    if (l == NULL) {
   10.42 +        return NULL;
   10.43 +    }
   10.44 +    size_t n = ucx_list_size(l);
   10.45 +    if (n == 1) {
   10.46 +        return l;
   10.47 +    }
   10.48 +
   10.49 +    UcxList *entries[n];
   10.50 +    entries[0] = l;
   10.51 +    for (int i = 1 ; i < n ; i++) {
   10.52 +      entries[i] = entries[i-1]->next;
   10.53 +    }
   10.54 +
   10.55 +    ucx_list_qsort_sort(entries, 0, n-1, fnc, data);
   10.56 +
   10.57 +    for (int i = 0 ; i < n-1 ; i++) {
   10.58 +      entries[i]->next = entries[i+1];
   10.59 +    }
   10.60 +    entries[n-1]->next = NULL;
   10.61 +
   10.62 +    return entries[0];
   10.63 +}
   10.64 +
   10.65  /* list specific functions */
   10.66  UcxList *ucx_list_remove(UcxList *l, UcxList *e) {
   10.67      if (e == l) {

    11.1 --- a/ucx/list.h	Fri Jun 01 12:35:30 2012 +0200
    11.2 +++ b/ucx/list.h	Wed Aug 15 19:32:29 2012 +0200
    11.3 @@ -29,6 +29,8 @@
    11.4  UcxList *ucx_list_get(UcxList *l, int index);
    11.5  size_t ucx_list_size(UcxList *l);
    11.6  
    11.7 +UcxList *ucx_list_qsort(UcxList *l, cmp_func fnc, void *data);
    11.8 +
    11.9  /* list specific functions */
   11.10  UcxList *ucx_list_remove(UcxList *l, UcxList *e);
   11.11