comparison: ucx/list.c
ucx/list.c
- changeset 35
- fdabd1240b69
- parent 31
- 91ac86557290
- child 36
- a9d656e4f7ce
equal
deleted
inserted
replaced
| 34:0dcd2ca2a223 | 35:fdabd1240b69 |
|---|---|
| 106 } | 106 } |
| 107 | 107 |
| 108 return s; | 108 return s; |
| 109 } | 109 } |
| 110 | 110 |
| 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; | |
| 116 | |
| 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); | |
| 126 | |
| 127 if (f(list[i]->data, p, d) > 0) { | |
| 128 b = list[r]; | |
| 129 list[r] = list[i]; | |
| 130 list[i] = b; | |
| 131 } | |
| 132 | |
| 133 return i; | |
| 134 } | |
| 135 | |
| 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 } | |
| 143 | |
| 144 UcxList *ucx_list_qsort(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 } | |
| 152 | |
| 153 UcxList *entries[n]; | |
| 154 entries[0] = l; | |
| 155 for (int i = 1 ; i < n ; i++) { | |
| 156 entries[i] = entries[i-1]->next; | |
| 157 } | |
| 158 | |
| 159 ucx_list_qsort_sort(entries, 0, n-1, fnc, data); | |
| 160 | |
| 161 for (int i = 0 ; i < n-1 ; i++) { | |
| 162 entries[i]->next = entries[i+1]; | |
| 163 } | |
| 164 entries[n-1]->next = NULL; | |
| 165 | |
| 166 return entries[0]; | |
| 167 } | |
| 168 | |
| 111 /* list specific functions */ | 169 /* list specific functions */ |
| 112 UcxList *ucx_list_remove(UcxList *l, UcxList *e) { | 170 UcxList *ucx_list_remove(UcxList *l, UcxList *e) { |
| 113 if (e == l) { | 171 if (e == l) { |
| 114 l = e->next; | 172 l = e->next; |
| 115 free(e); | 173 free(e); |
