comparison: src/server/ucx/dlist.c
src/server/ucx/dlist.c
- changeset 36
- 450d2d5f4735
- parent 30
- 27c7511c0e34
- child 71
- 069c152f6272
equal
deleted
inserted
replaced
| 35:4417619a9bbd | 36:450d2d5f4735 |
|---|---|
| 110 } | 110 } |
| 111 | 111 |
| 112 return s; | 112 return s; |
| 113 } | 113 } |
| 114 | 114 |
| 115 UcxDlist *ucx_dlist_sort_merge(int length, | |
| 116 UcxDlist* ls, UcxDlist* rs, UcxDlist* le, UcxDlist* re, | |
| 117 cmp_func fnc, void* data) { | |
| 118 UcxDlist *sorted[length]; | |
| 119 UcxDlist *rc, *lc; | |
| 120 | |
| 121 lc = ls; rc = rs; | |
| 122 int n = 0; | |
| 123 while (lc != le && rc != re) { | |
| 124 if (fnc(lc->data, rc->data, data) <= 0) { | |
| 125 sorted[n] = lc; | |
| 126 lc = lc->next; | |
| 127 } else { | |
| 128 sorted[n] = rc; | |
| 129 rc = rc->next; | |
| 130 } | |
| 131 n++; | |
| 132 } | |
| 133 while (lc != le) { | |
| 134 sorted[n] = lc; | |
| 135 lc = lc->next; | |
| 136 n++; | |
| 137 } | |
| 138 while (rc != re) { | |
| 139 sorted[n] = rc; | |
| 140 rc = rc->next; | |
| 141 n++; | |
| 142 } | |
| 143 | |
| 144 // Update pointer | |
| 145 sorted[0]->prev = NULL; | |
| 146 for (int i = 0 ; i < length-1 ; i++) { | |
| 147 sorted[i]->next = sorted[i+1]; | |
| 148 sorted[i+1]->prev = sorted[i]; | |
| 149 } | |
| 150 sorted[length-1]->next = NULL; | |
| 151 | |
| 152 return sorted[0]; | |
| 153 } | |
| 154 | |
| 155 UcxDlist *ucx_dlist_sort(UcxDlist *l, cmp_func fnc, void *data) { | |
| 156 if (l == NULL) { | |
| 157 return NULL; | |
| 158 } | |
| 159 | |
| 160 UcxDlist *lc; | |
| 161 int ln = 1; | |
| 162 | |
| 163 UcxDlist *ls = l, *le; | |
| 164 lc = ls; | |
| 165 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) { | |
| 166 lc = lc->next; | |
| 167 ln++; | |
| 168 } | |
| 169 le = lc->next; | |
| 170 | |
| 171 UcxDlist *rs = le, *re; | |
| 172 if (rs == NULL) { | |
| 173 return l; // this list is already sorted :) | |
| 174 } else { | |
| 175 UcxDlist *rc; | |
| 176 int rn = 1; | |
| 177 rc = rs; | |
| 178 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { | |
| 179 rc = rc->next; | |
| 180 rn++; | |
| 181 } | |
| 182 re = rc->next; | |
| 183 | |
| 184 // Something left? Sort it! | |
| 185 UcxDlist *remainder = re; | |
| 186 size_t remainder_length = ucx_dlist_size(remainder); | |
| 187 if (remainder != NULL) { | |
| 188 remainder = ucx_dlist_sort(remainder, fnc, data); | |
| 189 } | |
| 190 | |
| 191 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them | |
| 192 UcxDlist *sorted = ucx_dlist_sort_merge(ln+rn, | |
| 193 ls, rs, le, re, | |
| 194 fnc, data); | |
| 195 | |
| 196 // merge sorted list with (also sorted) remainder | |
| 197 l = ucx_dlist_sort_merge(ln+rn+remainder_length, | |
| 198 sorted, remainder, NULL, NULL, | |
| 199 fnc, data); | |
| 200 | |
| 201 return l; | |
| 202 } | |
| 203 } | |
| 204 | |
| 115 /* dlist specific functions */ | 205 /* dlist specific functions */ |
| 116 UcxDlist *ucx_dlist_first(UcxDlist *l) { | 206 UcxDlist *ucx_dlist_first(UcxDlist *l) { |
| 117 if (l == NULL) return NULL; | 207 if (l == NULL) return NULL; |
| 118 | 208 |
| 119 UcxDlist *e = l; | 209 UcxDlist *e = l; |
