Mercurial > hg > ucx / changeset

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

--- a/test/dlist_tests.c	Fri Jun 01 12:35:30 2012 +0200
+++ b/test/dlist_tests.c	Wed Aug 15 19:32:29 2012 +0200
@@ -165,3 +165,37 @@
     ucx_dlist_free(list);
     ucx_dlist_free(copy);
 }
+
+UCX_TEST_IMPLEMENT(test_ucx_dlist_qsort) {
+    UcxDlist *list = ucx_dlist_append(NULL, "this");
+    list = ucx_dlist_append(list, "is");
+    list = ucx_dlist_append(list, "a");
+    list = ucx_dlist_append(list, "test");
+    list = ucx_dlist_append(list, "for");
+    list = ucx_dlist_append(list, "partial");
+    list = ucx_dlist_append(list, "correctness");
+
+    UcxDlist *expected = ucx_dlist_append(NULL, "a");
+    expected = ucx_dlist_append(expected, "correctness");
+    expected = ucx_dlist_append(expected, "for");
+    expected = ucx_dlist_append(expected, "is");
+    expected = ucx_dlist_append(expected, "partial");
+    expected = ucx_dlist_append(expected, "test");
+    expected = ucx_dlist_append(expected, "this");
+
+    list = ucx_dlist_qsort(list, cmp_string, NULL);
+
+    UCX_TEST_BEGIN
+    UCX_TEST_ASSERT(
+            ucx_dlist_equals(list, expected, cmp_string, 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);
+}

--- a/test/dlist_tests.h	Fri Jun 01 12:35:30 2012 +0200
+++ b/test/dlist_tests.h	Wed Aug 15 19:32:29 2012 +0200
@@ -32,6 +32,7 @@
 UCX_TEST_DECLARE(test_ucx_dlist_get)
 UCX_TEST_DECLARE(test_ucx_dlist_remove)
 UCX_TEST_DECLARE(test_ucx_dlist_clone)
+UCX_TEST_DECLARE(test_ucx_dlist_qsort)
 
 #ifdef	__cplusplus
 }

--- a/test/list_tests.c	Fri Jun 01 12:35:30 2012 +0200
+++ b/test/list_tests.c	Wed Aug 15 19:32:29 2012 +0200
@@ -153,3 +153,31 @@
     ucx_list_free(list);
     ucx_list_free(copy);
 }
+
+UCX_TEST_IMPLEMENT(test_ucx_list_qsort) {
+    UcxList *list = ucx_list_append(NULL, "this");
+    list = ucx_list_append(list, "is");
+    list = ucx_list_append(list, "a");
+    list = ucx_list_append(list, "test");
+    list = ucx_list_append(list, "for");
+    list = ucx_list_append(list, "partial");
+    list = ucx_list_append(list, "correctness");
+
+    UcxList *expected = ucx_list_append(NULL, "a");
+    expected = ucx_list_append(expected, "correctness");
+    expected = ucx_list_append(expected, "for");
+    expected = ucx_list_append(expected, "is");
+    expected = ucx_list_append(expected, "partial");
+    expected = ucx_list_append(expected, "test");
+    expected = ucx_list_append(expected, "this");
+
+    list = ucx_list_qsort(list, cmp_string, NULL);
+
+    UCX_TEST_BEGIN
+    UCX_TEST_ASSERT(
+            ucx_list_equals(list, expected, cmp_string, NULL), "failed");
+    UCX_TEST_END
+
+    ucx_list_free(expected);
+    ucx_list_free(list);
+}

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

--- a/test/main.c	Fri Jun 01 12:35:30 2012 +0200
+++ b/test/main.c	Wed Aug 15 19:32:29 2012 +0200
@@ -116,6 +116,7 @@
         ucx_test_register(suite, test_ucx_list_get);
         ucx_test_register(suite, test_ucx_list_remove);
         ucx_test_register(suite, test_ucx_list_clone);
+        ucx_test_register(suite, test_ucx_list_qsort);
         
         /* UcxDlist Tests */
         ucx_test_register(suite, test_ucx_dlist_append);
@@ -128,6 +129,7 @@
         ucx_test_register(suite, test_ucx_dlist_get);
         ucx_test_register(suite, test_ucx_dlist_remove);
         ucx_test_register(suite, test_ucx_dlist_clone);
+        ucx_test_register(suite, test_ucx_dlist_qsort);
 
         /* UcxMemPool Tests */
         ucx_test_register(suite, test_ucx_mempool_new);

--- a/ucx/Makefile	Fri Jun 01 12:35:30 2012 +0200
+++ b/ucx/Makefile	Wed Aug 15 19:32:29 2012 +0200
@@ -38,6 +38,8 @@
 libucx: $(OBJ)
 	$(AR) $(ARFLAGS) ../build/libucx.$(LIB_EXT) $(OBJ)
 
-../build/%.$(OBJ_EXT): %.c
+../build/%.$(OBJ_EXT): %.c ../build
 	$(CC) $(CFLAGS) -c $< -o $@
 
+../build:
+	mkdir -p ../build

--- a/ucx/dlist.c	Fri Jun 01 12:35:30 2012 +0200
+++ b/ucx/dlist.c	Wed Aug 15 19:32:29 2012 +0200
@@ -112,6 +112,66 @@
     return s;
 }
 
+int ucx_dlist_qsort_devide(UcxDlist** list, int l, int r, cmp_func f, void* d) {
+    int i = l;
+    int j = r - 1;
+    void *p = list[r]->data;
+    UcxDlist *b;
+
+    do {
+        while (i < r && f(list[i]->data, p, d) <= 0) i++;
+        while (j > l && f(list[j]->data, p, d) >= 0) j--;
+        if (i < j) {
+            b = list[i];
+            list[i] = list[j];
+            list[j] = b;
+        }
+    } while (i < j);
+
+    if (f(list[i]->data, p, d) > 0) {
+        b = list[r];
+        list[r] = list[i];
+        list[i] = b;
+    }
+
+    return i;
+}
+
+void ucx_dlist_qsort_sort(UcxDlist** list, int l, int r, cmp_func f, void* d) {
+    if (l < r) {
+        int m = ucx_dlist_qsort_devide(list, l, r, f, d);
+        ucx_dlist_qsort_sort(list, l, m-1, f, d);
+        ucx_dlist_qsort_sort(list, m+1, r, f, d);
+    }
+}
+
+UcxDlist *ucx_dlist_qsort(UcxDlist *l, cmp_func fnc, void *data) {
+    if (l == NULL) {
+        return NULL;
+    }
+    size_t n = ucx_dlist_size(l);
+    if (n == 1) {
+        return l;
+    }
+
+    UcxDlist *entries[n];
+    entries[0] = l;
+    for (int i = 1 ; i < n ; i++) {
+      entries[i] = entries[i-1]->next;
+    }
+
+    ucx_dlist_qsort_sort(entries, 0, n-1, fnc, data);
+
+    entries[0]->prev = NULL;
+    for (int i = 0 ; i < n-1 ; i++) {
+      entries[i]->next = entries[i+1];
+      entries[i+1]->prev = entries[i];
+    }
+    entries[n-1]->next = NULL;
+
+    return entries[0];
+}
+
 /* dlist specific functions */
 UcxDlist *ucx_dlist_first(UcxDlist *l) {
     if (l == NULL) return NULL;

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

--- a/ucx/list.c	Fri Jun 01 12:35:30 2012 +0200
+++ b/ucx/list.c	Wed Aug 15 19:32:29 2012 +0200
@@ -108,6 +108,64 @@
     return s;
 }
 
+int ucx_list_qsort_devide(UcxList** list, int l, int r, cmp_func f, void* d) {
+    int i = l;
+    int j = r - 1;
+    void *p = list[r]->data;
+    UcxList *b;
+
+    do {
+        while (i < r && f(list[i]->data, p, d) <= 0) i++;
+        while (j > l && f(list[j]->data, p, d) >= 0) j--;
+        if (i < j) {
+            b = list[i];
+            list[i] = list[j];
+            list[j] = b;
+        }
+    } while (i < j);
+
+    if (f(list[i]->data, p, d) > 0) {
+        b = list[r];
+        list[r] = list[i];
+        list[i] = b;
+    }
+
+    return i;
+}
+
+void ucx_list_qsort_sort(UcxList** list, int l, int r, cmp_func f, void* d) {
+    if (l < r) {
+        int m = ucx_list_qsort_devide(list, l, r, f, d);
+        ucx_list_qsort_sort(list, l, m-1, f, d);
+        ucx_list_qsort_sort(list, m+1, r, f, d);
+    }
+}
+
+UcxList *ucx_list_qsort(UcxList *l, cmp_func fnc, void *data) {
+    if (l == NULL) {
+        return NULL;
+    }
+    size_t n = ucx_list_size(l);
+    if (n == 1) {
+        return l;
+    }
+
+    UcxList *entries[n];
+    entries[0] = l;
+    for (int i = 1 ; i < n ; i++) {
+      entries[i] = entries[i-1]->next;
+    }
+
+    ucx_list_qsort_sort(entries, 0, n-1, fnc, data);
+
+    for (int i = 0 ; i < n-1 ; i++) {
+      entries[i]->next = entries[i+1];
+    }
+    entries[n-1]->next = NULL;
+
+    return entries[0];
+}
+
 /* list specific functions */
 UcxList *ucx_list_remove(UcxList *l, UcxList *e) {
     if (e == l) {

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