comparison: ucx/dlist.c
ucx/dlist.c
- changeset 35
- fdabd1240b69
- parent 31
- 91ac86557290
- child 36
- a9d656e4f7ce
equal
deleted
inserted
replaced
| 34:0dcd2ca2a223 | 35:fdabd1240b69 |
|---|---|
| 110 } | 110 } |
| 111 | 111 |
| 112 return s; | 112 return s; |
| 113 } | 113 } |
| 114 | 114 |
| 115 int ucx_dlist_qsort_devide(UcxDlist** list, int l, int r, cmp_func f, void* d) { | |
| 116 int i = l; | |
| 117 int j = r - 1; | |
| 118 void *p = list[r]->data; | |
| 119 UcxDlist *b; | |
| 120 | |
| 121 do { | |
| 122 while (i < r && f(list[i]->data, p, d) <= 0) i++; | |
| 123 while (j > l && f(list[j]->data, p, d) >= 0) j--; | |
| 124 if (i < j) { | |
| 125 b = list[i]; | |
| 126 list[i] = list[j]; | |
| 127 list[j] = b; | |
| 128 } | |
| 129 } while (i < j); | |
| 130 | |
| 131 if (f(list[i]->data, p, d) > 0) { | |
| 132 b = list[r]; | |
| 133 list[r] = list[i]; | |
| 134 list[i] = b; | |
| 135 } | |
| 136 | |
| 137 return i; | |
| 138 } | |
| 139 | |
| 140 void ucx_dlist_qsort_sort(UcxDlist** list, int l, int r, cmp_func f, void* d) { | |
| 141 if (l < r) { | |
| 142 int m = ucx_dlist_qsort_devide(list, l, r, f, d); | |
| 143 ucx_dlist_qsort_sort(list, l, m-1, f, d); | |
| 144 ucx_dlist_qsort_sort(list, m+1, r, f, d); | |
| 145 } | |
| 146 } | |
| 147 | |
| 148 UcxDlist *ucx_dlist_qsort(UcxDlist *l, cmp_func fnc, void *data) { | |
| 149 if (l == NULL) { | |
| 150 return NULL; | |
| 151 } | |
| 152 size_t n = ucx_dlist_size(l); | |
| 153 if (n == 1) { | |
| 154 return l; | |
| 155 } | |
| 156 | |
| 157 UcxDlist *entries[n]; | |
| 158 entries[0] = l; | |
| 159 for (int i = 1 ; i < n ; i++) { | |
| 160 entries[i] = entries[i-1]->next; | |
| 161 } | |
| 162 | |
| 163 ucx_dlist_qsort_sort(entries, 0, n-1, fnc, data); | |
| 164 | |
| 165 entries[0]->prev = NULL; | |
| 166 for (int i = 0 ; i < n-1 ; i++) { | |
| 167 entries[i]->next = entries[i+1]; | |
| 168 entries[i+1]->prev = entries[i]; | |
| 169 } | |
| 170 entries[n-1]->next = NULL; | |
| 171 | |
| 172 return entries[0]; | |
| 173 } | |
| 174 | |
| 115 /* dlist specific functions */ | 175 /* dlist specific functions */ |
| 116 UcxDlist *ucx_dlist_first(UcxDlist *l) { | 176 UcxDlist *ucx_dlist_first(UcxDlist *l) { |
| 117 if (l == NULL) return NULL; | 177 if (l == NULL) return NULL; |
| 118 | 178 |
| 119 UcxDlist *e = l; | 179 UcxDlist *e = l; |
