comparison: src/server/ucx/list.c
src/server/ucx/list.c
- changeset 36
- 450d2d5f4735
- parent 23
- a2c8fc23c90e
- child 71
- 069c152f6272
equal
deleted
inserted
replaced
| 35:4417619a9bbd | 36:450d2d5f4735 |
|---|---|
| 23 if (fnc(l1->data, l2->data, data) != 0) return 0; | 23 if (fnc(l1->data, l2->data, data) != 0) return 0; |
| 24 } | 24 } |
| 25 l1 = l1->next; | 25 l1 = l1->next; |
| 26 l2 = l2->next; | 26 l2 = l2->next; |
| 27 } | 27 } |
| 28 | 28 |
| 29 return (l1 == NULL && l2 == NULL); | 29 return (l1 == NULL && l2 == NULL); |
| 30 } | 30 } |
| 31 | 31 |
| 32 void ucx_list_free(UcxList *l) { | 32 void ucx_list_free(UcxList *l) { |
| 33 UcxList *e = l, *f; | 33 UcxList *e = l, *f; |
| 39 } | 39 } |
| 40 | 40 |
| 41 UcxList *ucx_list_append(UcxList *l, void *data) { | 41 UcxList *ucx_list_append(UcxList *l, void *data) { |
| 42 UcxList *nl = (UcxList*) malloc(sizeof(UcxList)); | 42 UcxList *nl = (UcxList*) malloc(sizeof(UcxList)); |
| 43 if (nl == NULL) return NULL; | 43 if (nl == NULL) return NULL; |
| 44 | 44 |
| 45 nl->data = data; | 45 nl->data = data; |
| 46 nl->next = NULL; | 46 nl->next = NULL; |
| 47 if (l == NULL) { | 47 if (l == NULL) { |
| 48 return nl; | 48 return nl; |
| 49 } else { | 49 } else { |
| 54 } | 54 } |
| 55 | 55 |
| 56 UcxList *ucx_list_prepend(UcxList *l, void *data) { | 56 UcxList *ucx_list_prepend(UcxList *l, void *data) { |
| 57 UcxList *nl = ucx_list_append(NULL, data); | 57 UcxList *nl = ucx_list_append(NULL, data); |
| 58 if (nl == NULL) return NULL; | 58 if (nl == NULL) return NULL; |
| 59 | 59 |
| 60 if (l != NULL) { | 60 if (l != NULL) { |
| 61 nl->next = l; | 61 nl->next = l; |
| 62 } | 62 } |
| 63 return nl; | 63 return nl; |
| 64 } | 64 } |
| 73 } | 73 } |
| 74 } | 74 } |
| 75 | 75 |
| 76 UcxList *ucx_list_last(UcxList *l) { | 76 UcxList *ucx_list_last(UcxList *l) { |
| 77 if (l == NULL) return NULL; | 77 if (l == NULL) return NULL; |
| 78 | 78 |
| 79 UcxList *e = l; | 79 UcxList *e = l; |
| 80 while (e->next != NULL) { | 80 while (e->next != NULL) { |
| 81 e = e->next; | 81 e = e->next; |
| 82 } | 82 } |
| 83 return e; | 83 return e; |
| 89 UcxList *e = l; | 89 UcxList *e = l; |
| 90 while (e->next != NULL && index > 0) { | 90 while (e->next != NULL && index > 0) { |
| 91 e = e->next; | 91 e = e->next; |
| 92 index--; | 92 index--; |
| 93 } | 93 } |
| 94 | 94 |
| 95 return index == 0 ? e : NULL; | 95 return index == 0 ? e : NULL; |
| 96 } | 96 } |
| 97 | 97 |
| 98 size_t ucx_list_size(UcxList *l) { | 98 size_t ucx_list_size(UcxList *l) { |
| 99 if (l == NULL) return 0; | 99 if (l == NULL) return 0; |
| 100 | 100 |
| 101 UcxList *e = l; | 101 UcxList *e = l; |
| 102 size_t s = 1; | 102 size_t s = 1; |
| 103 while (e->next != NULL) { | 103 while (e->next != NULL) { |
| 104 e = e->next; | 104 e = e->next; |
| 105 s++; | 105 s++; |
| 106 } | 106 } |
| 107 | 107 |
| 108 return s; | 108 return s; |
| 109 } | 109 } |
| 110 | 110 |
| 111 void ucx_list_foreach(UcxList *l, ucx_callback fnc, void* data) { | 111 UcxList *ucx_list_sort_merge(int length, |
| 112 UcxList *e = l; | 112 UcxList* ls, UcxList* rs, UcxList* le, UcxList* re, |
| 113 UcxList *n; | 113 cmp_func fnc, void* data) { |
| 114 while (e != NULL) { | 114 UcxList *sorted[length]; |
| 115 n = e->next; | 115 UcxList *rc, *lc; |
| 116 fnc(e, data); | 116 |
| 117 e = n; | 117 lc = ls; rc = rs; |
| 118 int n = 0; | |
| 119 while (lc != le && rc != re) { | |
| 120 if (fnc(lc->data, rc->data, data) <= 0) { | |
| 121 sorted[n] = lc; | |
| 122 lc = lc->next; | |
| 123 } else { | |
| 124 sorted[n] = rc; | |
| 125 rc = rc->next; | |
| 126 } | |
| 127 n++; | |
| 128 } | |
| 129 while (lc != le) { | |
| 130 sorted[n] = lc; | |
| 131 lc = lc->next; | |
| 132 n++; | |
| 133 } | |
| 134 while (rc != re) { | |
| 135 sorted[n] = rc; | |
| 136 rc = rc->next; | |
| 137 n++; | |
| 138 } | |
| 139 | |
| 140 // Update pointer | |
| 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]; | |
| 147 } | |
| 148 | |
| 149 UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) { | |
| 150 if (l == NULL) { | |
| 151 return NULL; | |
| 152 } | |
| 153 | |
| 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 | |
| 195 return l; | |
| 118 } | 196 } |
| 119 } | 197 } |
| 120 | 198 |
| 121 /* list specific functions */ | 199 /* list specific functions */ |
| 122 UcxList *ucx_list_remove(UcxList *l, UcxList *e) { | 200 UcxList *ucx_list_remove(UcxList *l, UcxList *e) { |
| 126 } else { | 204 } else { |
| 127 UcxList *f = l; | 205 UcxList *f = l; |
| 128 while (f->next != NULL && f->next != e) { | 206 while (f->next != NULL && f->next != e) { |
| 129 f = f->next; | 207 f = f->next; |
| 130 } | 208 } |
| 131 /* perform remove iff this element is found in this list */ | 209 /* perform remove if this element is found in this list */ |
| 132 if (f->next == e) { | 210 if (f->next == e) { |
| 133 f->next = e->next; | 211 f->next = e->next; |
| 134 free(e); | 212 free(e); |
| 135 } | 213 } |
| 136 } | 214 } |
