Mercurial > hg > webserver / file comparison

comparison: src/server/ucx/list.c

src/server/ucx/list.c

changeset 71
069c152f6272
parent 36
450d2d5f4735
equal deleted inserted replaced
70:4e6e812c1d97 71:069c152f6272
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2013 Olaf Wintermann. All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
1 #include "list.h" 29 #include "list.h"
2 30
3 UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) { 31 UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) {
4 UcxList *ret = NULL; 32 UcxList *ret = NULL;
5 while (l != NULL) { 33 while (l != NULL) {
11 l = l->next; 39 l = l->next;
12 } 40 }
13 return ret; 41 return ret;
14 } 42 }
15 43
16 int ucx_list_equals(UcxList *l1, UcxList *l2, cmp_func fnc, void* data) { 44 int ucx_list_equals(const UcxList *l1, const UcxList *l2,
45 cmp_func fnc, void* data) {
17 if (l1 == l2) return 1; 46 if (l1 == l2) return 1;
18 47
19 while (l1 != NULL && l2 != NULL) { 48 while (l1 != NULL && l2 != NULL) {
20 if (fnc == NULL) { 49 if (fnc == NULL) {
21 if (l1->data != l2->data) return 0; 50 if (l1->data != l2->data) return 0;
71 last->next = l2; 100 last->next = l2;
72 return l1; 101 return l1;
73 } 102 }
74 } 103 }
75 104
76 UcxList *ucx_list_last(UcxList *l) { 105 UcxList *ucx_list_last(const UcxList *l) {
77 if (l == NULL) return NULL; 106 if (l == NULL) return NULL;
78 107
79 UcxList *e = l; 108 const UcxList *e = l;
80 while (e->next != NULL) { 109 while (e->next != NULL) {
81 e = e->next; 110 e = e->next;
82 } 111 }
83 return e; 112 return (UcxList*)e;
84 } 113 }
85 114
86 UcxList *ucx_list_get(UcxList *l, int index) { 115 UcxList *ucx_list_get(const UcxList *l, int index) {
87 if (l == NULL) return NULL; 116 if (l == NULL) return NULL;
88 117
89 UcxList *e = l; 118 const UcxList *e = l;
90 while (e->next != NULL && index > 0) { 119 while (e->next != NULL && index > 0) {
91 e = e->next; 120 e = e->next;
92 index--; 121 index--;
93 } 122 }
94 123
95 return index == 0 ? e : NULL; 124 return (UcxList*)(index == 0 ? e : NULL);
96 } 125 }
97 126
98 size_t ucx_list_size(UcxList *l) { 127 int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) {
128 UCX_FOREACH(UcxList*, l, e) {
129 if (!fnc(elem, e->data, cmpdata)) {
130 return 1;
131 }
132 }
133 return 0;
134 }
135
136 size_t ucx_list_size(const UcxList *l) {
99 if (l == NULL) return 0; 137 if (l == NULL) return 0;
100 138
101 UcxList *e = l; 139 const UcxList *e = l;
102 size_t s = 1; 140 size_t s = 1;
103 while (e->next != NULL) { 141 while (e->next != NULL) {
104 e = e->next; 142 e = e->next;
105 s++; 143 s++;
106 } 144 }
107 145
108 return s; 146 return s;
109 } 147 }
110 148
111 UcxList *ucx_list_sort_merge(int length, 149 UcxList *ucx_list_sort_merge(int length,
112 UcxList* ls, UcxList* rs, UcxList* le, UcxList* re, 150 UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re,
113 cmp_func fnc, void* data) { 151 cmp_func fnc, void* data) {
114 UcxList *sorted[length]; 152
153 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length);
115 UcxList *rc, *lc; 154 UcxList *rc, *lc;
116 155
117 lc = ls; rc = rs; 156 lc = ls; rc = le;
118 int n = 0; 157 int n = 0;
119 while (lc != le && rc != re) { 158 while (lc && lc != le && rc != re) {
120 if (fnc(lc->data, rc->data, data) <= 0) { 159 if (fnc(lc->data, rc->data, data) <= 0) {
121 sorted[n] = lc; 160 sorted[n] = lc;
122 lc = lc->next; 161 lc = lc->next;
123 } else { 162 } else {
124 sorted[n] = rc; 163 sorted[n] = rc;
125 rc = rc->next; 164 rc = rc->next;
126 } 165 }
127 n++; 166 n++;
128 } 167 }
129 while (lc != le) { 168 while (lc && lc != le) {
130 sorted[n] = lc; 169 sorted[n] = lc;
131 lc = lc->next; 170 lc = lc->next;
132 n++; 171 n++;
133 } 172 }
134 while (rc != re) { 173 while (rc && rc != re) {
135 sorted[n] = rc; 174 sorted[n] = rc;
136 rc = rc->next; 175 rc = rc->next;
137 n++; 176 n++;
138 } 177 }
139 178
141 for (int i = 0 ; i < length-1 ; i++) { 180 for (int i = 0 ; i < length-1 ; i++) {
142 sorted[i]->next = sorted[i+1]; 181 sorted[i]->next = sorted[i+1];
143 } 182 }
144 sorted[length-1]->next = NULL; 183 sorted[length-1]->next = NULL;
145 184
146 return sorted[0]; 185 UcxList *ret = sorted[0];
186 free(sorted);
187 return ret;
147 } 188 }
148 189
149 UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) { 190 UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) {
150 if (l == NULL) { 191 if (l == NULL) {
151 return NULL; 192 return NULL;
152 } 193 }
153 194
154 UcxList *lc; 195 UcxList *lc;
155 int ln = 1; 196 int ln = 1;
156 197
157 UcxList *ls = l, *le; 198 UcxList *restrict ls = l, *restrict le, *restrict re;
158 lc = ls; 199 lc = ls;
159 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) { 200 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
160 lc = lc->next; 201 lc = lc->next;
161 ln++; 202 ln++;
162 } 203 }
163 le = lc->next; 204 le = lc->next;
164 205
165 UcxList *rs = le, *re; 206 if (le == NULL) {
166 if (rs == NULL) {
167 return l; // this list is already sorted :) 207 return l; // this list is already sorted :)
168 } else { 208 } else {
169 UcxList *rc; 209 UcxList *rc;
170 int rn = 1; 210 int rn = 1;
171 rc = rs; 211 rc = le;
172 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { 212 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
173 rc = rc->next; 213 rc = rc->next;
174 rn++; 214 rn++;
175 } 215 }
176 re = rc->next; 216 re = rc->next;
182 remainder = ucx_list_sort(remainder, fnc, data); 222 remainder = ucx_list_sort(remainder, fnc, data);
183 } 223 }
184 224
185 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them 225 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
186 UcxList *sorted = ucx_list_sort_merge(ln+rn, 226 UcxList *sorted = ucx_list_sort_merge(ln+rn,
187 ls, rs, le, re, 227 ls, le, re,
188 fnc, data); 228 fnc, data);
189 229
190 // merge sorted list with (also sorted) remainder 230 // merge sorted list with (also sorted) remainder
191 l = ucx_list_sort_merge(ln+rn+remainder_length, 231 l = ucx_list_sort_merge(ln+rn+remainder_length,
192 sorted, remainder, NULL, NULL, 232 sorted, remainder, NULL, fnc, data);
193 fnc, data);
194 233
195 return l; 234 return l;
196 } 235 }
197 } 236 }
198 237

Mercurial Repository: webserver

mercurial