ucx: ucx/list.c@a9d656e4f7ce

changed API of sort algorithms (no further hint for the algorithms used in preparation for the upcomming change from qsort to natural merge sort)

     1 #include "list.h"

     3 UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) {

     4     UcxList *ret = NULL;

     5     while (l != NULL) {

     6         if (fnc != NULL) {

     7             ret = ucx_list_append(ret, fnc(l->data, data));

     8         } else {

     9             ret = ucx_list_append(ret, l->data);

    10         }

    11         l = l->next;

    12     }

    13     return ret;

    14 }

    16 int ucx_list_equals(UcxList *l1, UcxList *l2, cmp_func fnc, void* data) {

    17     if (l1 == l2) return 1;

    19     while (l1 != NULL && l2 != NULL) {

    20         if (fnc == NULL) {

    21             if (l1->data != l2->data) return 0;

    22         } else {

    23             if (fnc(l1->data, l2->data, data) != 0) return 0;

    24         }

    25         l1 = l1->next;

    26         l2 = l2->next;

    27     }

    29     return (l1 == NULL && l2 == NULL);

    30 }

    32 void ucx_list_free(UcxList *l) {

    33     UcxList *e = l, *f;

    34     while (e != NULL) {

    35         f = e;

    36         e = e->next;

    37         free(f);

    38     }

    39 }

    41 UcxList *ucx_list_append(UcxList *l, void *data)  {

    42     UcxList *nl = (UcxList*) malloc(sizeof(UcxList));

    43     if (nl == NULL) return NULL;

    45     nl->data = data;

    46     nl->next = NULL;

    47     if (l == NULL) {

    48         return nl;

    49     } else {

    50         UcxList *t = ucx_list_last(l);

    51         t->next = nl;

    52         return l;

    53     }

    54 }

    56 UcxList *ucx_list_prepend(UcxList *l, void *data) {

    57     UcxList *nl = ucx_list_append(NULL, data);

    58     if (nl == NULL) return NULL;

    60     if (l != NULL) {

    61         nl->next = l;

    62     }

    63     return nl;

    64 }

    66 UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) {

    67     if (l1 == NULL) {

    68         return l2;

    69     } else {

    70         UcxList *last = ucx_list_last(l1);

    71         last->next = l2;

    72         return l1;

    73     }

    74 }

    76 UcxList *ucx_list_last(UcxList *l) {

    77     if (l == NULL) return NULL;

    79     UcxList *e = l;

    80     while (e->next != NULL) {

    81         e = e->next;

    82     }

    83     return e;

    84 }

    86 UcxList *ucx_list_get(UcxList *l, int index) {

    87     if (l == NULL) return NULL;

    89     UcxList *e = l;

    90     while (e->next != NULL && index > 0) {

    91         e = e->next;

    92         index--;

    93     }

    95     return index == 0 ? e : NULL;

    96 }

    98 size_t ucx_list_size(UcxList *l) {

    99     if (l == NULL) return 0;

   101     UcxList *e = l;

   102     size_t s = 1;

   103     while (e->next != NULL) {

   104         e = e->next;

   105         s++;

   106     }

   108     return s;

   109 }

   111 int ucx_list_qsort_devide(UcxList** list, int l, int r, cmp_func f, void* d) {

   112     int i = l;

   113     int j = r - 1;

   114     void *p = list[r]->data;

   115     UcxList *b;

   117     do {

   118         while (i < r && f(list[i]->data, p, d) <= 0) i++;

   119         while (j > l && f(list[j]->data, p, d) >= 0) j--;

   120         if (i < j) {

   121             b = list[i];

   122             list[i] = list[j];

   123             list[j] = b;

   124         }

   125     } while (i < j);

   127     if (f(list[i]->data, p, d) > 0) {

   128         b = list[r];

   129         list[r] = list[i];

   130         list[i] = b;

   131     }

   133     return i;

   134 }

   136 void ucx_list_qsort_sort(UcxList** list, int l, int r, cmp_func f, void* d) {

   137     if (l < r) {

   138         int m = ucx_list_qsort_devide(list, l, r, f, d);

   139         ucx_list_qsort_sort(list, l, m-1, f, d);

   140         ucx_list_qsort_sort(list, m+1, r, f, d);

   141     }

   142 }

   144 UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) {

   145     if (l == NULL) {

   146         return NULL;

   147     }

   148     size_t n = ucx_list_size(l);

   149     if (n == 1) {

   150         return l;

   151     }

   153     UcxList *entries[n];

   154     entries[0] = l;

   155     for (int i = 1 ; i < n ; i++) {

   156       entries[i] = entries[i-1]->next;

   157     }

   159     ucx_list_qsort_sort(entries, 0, n-1, fnc, data);

   161     for (int i = 0 ; i < n-1 ; i++) {

   162       entries[i]->next = entries[i+1];

   163     }

   164     entries[n-1]->next = NULL;

   166     return entries[0];

   167 }

   169 /* list specific functions */

   170 UcxList *ucx_list_remove(UcxList *l, UcxList *e) {

   171     if (e == l) {

   172         l = e->next;

   173         free(e);

   174     } else {

   175         UcxList *f = l;

   176         while (f->next != NULL && f->next != e) {

   177             f = f->next;

   178         }

   179         /* perform remove if this element is found in this list */

   180         if (f->next == e) {

   181             f->next = e->next;

   182             free(e);

   183         }

   184     }

   185     return l;

   186 }

Mercurial > hg > ucx / file revision