comparison: ucx/list.c
ucx/list.c
- changeset 37
- ec296899d12f
- parent 36
- a9d656e4f7ce
- child 67
- 27e67e725d35
equal
deleted
inserted
replaced
| 36:a9d656e4f7ce | 37:ec296899d12f |
|---|---|
| 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) { | 111 UcxList *ucx_list_sort_merge(int length, |
| 112 int i = l; | 112 UcxList* ls, UcxList* rs, UcxList* le, UcxList* re, |
| 113 int j = r - 1; | 113 cmp_func fnc, void* data) { |
| 114 void *p = list[r]->data; | 114 UcxList *sorted[length]; |
| 115 UcxList *b; | 115 UcxList *rc, *lc; |
| 116 | 116 |
| 117 do { | 117 lc = ls; rc = rs; |
| 118 while (i < r && f(list[i]->data, p, d) <= 0) i++; | 118 int n = 0; |
| 119 while (j > l && f(list[j]->data, p, d) >= 0) j--; | 119 while (lc != le && rc != re) { |
| 120 if (i < j) { | 120 if (fnc(lc->data, rc->data, data) <= 0) { |
| 121 b = list[i]; | 121 sorted[n] = lc; |
| 122 list[i] = list[j]; | 122 lc = lc->next; |
| 123 list[j] = b; | 123 } else { |
| 124 } | 124 sorted[n] = rc; |
| 125 } while (i < j); | 125 rc = rc->next; |
| 126 | 126 } |
| 127 if (f(list[i]->data, p, d) > 0) { | 127 n++; |
| 128 b = list[r]; | 128 } |
| 129 list[r] = list[i]; | 129 while (lc != le) { |
| 130 list[i] = b; | 130 sorted[n] = lc; |
| 131 } | 131 lc = lc->next; |
| 132 | 132 n++; |
| 133 return i; | 133 } |
| 134 } | 134 while (rc != re) { |
| 135 | 135 sorted[n] = rc; |
| 136 void ucx_list_qsort_sort(UcxList** list, int l, int r, cmp_func f, void* d) { | 136 rc = rc->next; |
| 137 if (l < r) { | 137 n++; |
| 138 int m = ucx_list_qsort_devide(list, l, r, f, d); | 138 } |
| 139 ucx_list_qsort_sort(list, l, m-1, f, d); | 139 |
| 140 ucx_list_qsort_sort(list, m+1, r, f, d); | 140 // Update pointer |
| 141 } | 141 for (int i = 0 ; i < length-1 ; i++) { |
| 142 sorted[i]->next = sorted[i+1]; | |
| 143 } | |
| 144 sorted[length-1]->next = NULL; | |
| 145 | |
| 146 return sorted[0]; | |
| 142 } | 147 } |
| 143 | 148 |
| 144 UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) { | 149 UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) { |
| 145 if (l == NULL) { | 150 if (l == NULL) { |
| 146 return NULL; | 151 return NULL; |
| 147 } | 152 } |
| 148 size_t n = ucx_list_size(l); | 153 |
| 149 if (n == 1) { | 154 UcxList *lc; |
| 155 int ln = 1; | |
| 156 | |
| 157 UcxList *ls = l, *le; | |
| 158 lc = ls; | |
| 159 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) { | |
| 160 lc = lc->next; | |
| 161 ln++; | |
| 162 } | |
| 163 le = lc->next; | |
| 164 | |
| 165 UcxList *rs = le, *re; | |
| 166 if (rs == NULL) { | |
| 167 return l; // this list is already sorted :) | |
| 168 } else { | |
| 169 UcxList *rc; | |
| 170 int rn = 1; | |
| 171 rc = rs; | |
| 172 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { | |
| 173 rc = rc->next; | |
| 174 rn++; | |
| 175 } | |
| 176 re = rc->next; | |
| 177 | |
| 178 // Something left? Sort it! | |
| 179 UcxList *remainder = re; | |
| 180 size_t remainder_length = ucx_list_size(remainder); | |
| 181 if (remainder != NULL) { | |
| 182 remainder = ucx_list_sort(remainder, fnc, data); | |
| 183 } | |
| 184 | |
| 185 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them | |
| 186 UcxList *sorted = ucx_list_sort_merge(ln+rn, | |
| 187 ls, rs, le, re, | |
| 188 fnc, data); | |
| 189 | |
| 190 // merge sorted list with (also sorted) remainder | |
| 191 l = ucx_list_sort_merge(ln+rn+remainder_length, | |
| 192 sorted, remainder, NULL, NULL, | |
| 193 fnc, data); | |
| 194 | |
| 150 return l; | 195 return l; |
| 151 } | 196 } |
| 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 } | 197 } |
| 168 | 198 |
| 169 /* list specific functions */ | 199 /* list specific functions */ |
| 170 UcxList *ucx_list_remove(UcxList *l, UcxList *e) { | 200 UcxList *ucx_list_remove(UcxList *l, UcxList *e) { |
| 171 if (e == l) { | 201 if (e == l) { |
