1 | /* |
2 | Lightweight C Container Library |
3 | |
4 | Copyright (c) 2002 Tobias Koenig <tokoe@kde.org> |
5 | |
6 | Original code was written by Chris Schlaeger <cs@kde.org> |
7 | |
8 | This library is free software; you can redistribute it and/or |
9 | modify it under the terms of the GNU Library General Public |
10 | License as published by the Free Software Foundation; either |
11 | version 2 of the License, or (at your option) any later version. |
12 | |
13 | This library is distributed in the hope that it will be useful, |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
16 | Library General Public License for more details. |
17 | |
18 | You should have received a copy of the GNU Library General Public License |
19 | along with this library; see the file COPYING.LIB. If not, write to |
20 | the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, |
21 | Boston, MA 02110-1301, USA. |
22 | |
23 | */ |
24 | |
25 | #include "ccont.h" |
26 | |
27 | #include <stdio.h> |
28 | #include <stdlib.h> |
29 | #include <assert.h> |
30 | |
31 | struct container_info { |
32 | INDEX count; |
33 | CONTAINER currentNode; |
34 | }; |
35 | |
36 | typedef struct container_info T_CONTAINER_INFO; |
37 | typedef struct container_info* CONTAINER_INFO; |
38 | |
39 | #define rpterr(x) fprintf(stderr, "%s\n", x) |
40 | |
41 | CONTAINER new_ctnr(void) |
42 | { |
43 | CONTAINER_INFO info; |
44 | CONTAINER rootNode; |
45 | |
46 | rootNode = (CONTAINER)malloc(sizeof(T_CONTAINER)); |
47 | |
48 | info = (CONTAINER_INFO)malloc(sizeof(T_CONTAINER_INFO)); |
49 | info->count = 0; |
50 | info->currentNode = rootNode; |
51 | |
52 | rootNode->next = rootNode; |
53 | rootNode->prev = rootNode; |
54 | rootNode->data = info; |
55 | |
56 | return rootNode; |
57 | } |
58 | |
59 | /* O(n) */ |
60 | void zero_destr_ctnr(CONTAINER rootNode, DESTR_FUNC destr_func) |
61 | { |
62 | INDEX counter; |
63 | |
64 | if (rootNode == NIL || destr_func == NIL) { |
65 | rpterr("destr_ctnr: NIL argument" ); |
66 | return; |
67 | } |
68 | |
69 | for (counter = level_ctnr(rootNode); counter > -1; --counter) |
70 | destr_func(pop_ctnr(rootNode)); |
71 | |
72 | assert(rootNode->data); |
73 | free(rootNode->data); |
74 | |
75 | free(rootNode); |
76 | rootNode = 0; |
77 | |
78 | return; |
79 | } |
80 | |
81 | /* O(n) */ |
82 | void empty_ctnr(CONTAINER rootNode) |
83 | { |
84 | INDEX i; |
85 | |
86 | if (rootNode == NIL) { |
87 | rpterr("empty_ctnr: NIL argument" ); |
88 | return; |
89 | } |
90 | |
91 | for ( i = level_ctnr( rootNode ); i >= 0; --i ) |
92 | free( pop_ctnr( rootNode ) ); |
93 | |
94 | return; |
95 | } |
96 | |
97 | /* O(1) */ |
98 | INDEX level_ctnr(CONTAINER rootNode) |
99 | { |
100 | if (rootNode == NIL) { |
101 | rpterr("level_ctnr: NIL argument" ); |
102 | return -1; |
103 | } |
104 | |
105 | return ((CONTAINER_INFO)rootNode->data)->count; |
106 | } |
107 | |
108 | /* This function is never used */ |
109 | /* O(n) */ |
110 | void insert_ctnr(CONTAINER rootNode, void* object, INDEX pos) |
111 | { |
112 | CONTAINER it; |
113 | INDEX counter = 0; |
114 | |
115 | if (rootNode == NIL || object == NIL) { |
116 | rpterr("insert_ctnr: NIL argument" ); |
117 | return; |
118 | } |
119 | |
120 | for (it = rootNode->next; it != rootNode; it = it->next) { |
121 | if (counter == pos) { |
122 | CONTAINER newNode = (CONTAINER)malloc(sizeof(T_CONTAINER)); |
123 | |
124 | newNode->prev = it; |
125 | newNode->next = it->next; |
126 | it->next->prev = newNode; |
127 | it->next = newNode; |
128 | |
129 | newNode->data = object; |
130 | ((CONTAINER_INFO)rootNode->data)->count++; |
131 | return; |
132 | } |
133 | |
134 | counter++; |
135 | } |
136 | } |
137 | |
138 | /* O(1) */ |
139 | void push_ctnr(CONTAINER rootNode, void* object) |
140 | { |
141 | CONTAINER newNode; |
142 | |
143 | if (rootNode == NIL || object == NIL) { |
144 | rpterr("push_ctnr: NIL argument" ); |
145 | return; |
146 | } |
147 | |
148 | newNode = (CONTAINER)malloc(sizeof(T_CONTAINER)); |
149 | newNode->next = rootNode; |
150 | newNode->prev = rootNode->prev; |
151 | rootNode->prev->next = newNode; |
152 | rootNode->prev = newNode; |
153 | |
154 | newNode->data = object; |
155 | ((CONTAINER_INFO)rootNode->data)->count++; |
156 | } |
157 | |
158 | /* This function is never used */ |
159 | /* O(n) */ |
160 | void* remove_at_ctnr(CONTAINER rootNode, INDEX pos) |
161 | { |
162 | CONTAINER it; |
163 | INDEX counter = 0; |
164 | void* retval; |
165 | |
166 | if (rootNode == NIL) { |
167 | rpterr("remove_ctnr: NIL argument" ); |
168 | return NIL; |
169 | } |
170 | |
171 | for (it = rootNode->next; it != rootNode; it = it->next) { |
172 | if (counter == pos) { |
173 | retval = it->data; |
174 | |
175 | it->prev->next = it->next; |
176 | it->next->prev = it->prev; |
177 | |
178 | free(it); |
179 | |
180 | ((CONTAINER_INFO)rootNode->data)->count--; |
181 | return retval; |
182 | } |
183 | |
184 | counter++; |
185 | } |
186 | |
187 | return NIL; |
188 | } |
189 | |
190 | /* This function is only used within ccont.c */ |
191 | /* O(1) */ |
192 | void* pop_ctnr(CONTAINER rootNode) |
193 | { |
194 | CONTAINER ptr; |
195 | void* retval; |
196 | |
197 | if (rootNode == NIL) { |
198 | rpterr("pop_ctnr: NIL argument" ); |
199 | return NIL; |
200 | } |
201 | |
202 | if (rootNode->next == rootNode) |
203 | return NIL; |
204 | |
205 | ptr = rootNode->next; |
206 | retval = ptr->data; |
207 | |
208 | rootNode->next = ptr->next; |
209 | ptr->next->prev = rootNode; |
210 | |
211 | ((CONTAINER_INFO)rootNode->data)->count--; |
212 | |
213 | free(ptr); |
214 | |
215 | return retval; |
216 | } |
217 | |
218 | /* O(n) */ |
219 | void* get_ctnr(CONTAINER rootNode, INDEX pos) |
220 | { |
221 | CONTAINER it; |
222 | INDEX counter = 0; |
223 | |
224 | if (rootNode == NIL) { |
225 | rpterr("get_ctnr: NIL argument" ); |
226 | return NIL; |
227 | } |
228 | |
229 | for (it = rootNode->next; it != rootNode; it = it->next) { |
230 | if (counter == pos) |
231 | return it->data; |
232 | |
233 | counter++; |
234 | } |
235 | |
236 | return NIL; |
237 | } |
238 | |
239 | /* This should return a reference to the node found instead of its index. |
240 | The index is never used, except as an argument to a O(n) function to |
241 | get a reference to the node. */ |
242 | /* O(n) */ |
243 | INDEX search_ctnr(CONTAINER rootNode, COMPARE_FUNC compare_func, void* pattern) |
244 | { |
245 | CONTAINER it; |
246 | INDEX counter = 0; |
247 | |
248 | if (rootNode == NIL || compare_func == NIL || pattern == NIL) { |
249 | rpterr("search_ctnr: NIL argument" ); |
250 | return -1; |
251 | } |
252 | |
253 | for (it = rootNode->next; it != rootNode; it = it->next) { |
254 | if (compare_func(pattern, it->data) == 0) |
255 | return counter; |
256 | |
257 | counter++; |
258 | } |
259 | |
260 | return -1; |
261 | } |
262 | |
263 | /* This function is never used */ |
264 | /* O(n) */ |
265 | void swap_ctnr(CONTAINER rootNode, INDEX pos1, INDEX pos2) |
266 | { |
267 | CONTAINER it, node1 = 0, node2 = 0; |
268 | INDEX counter = 0; |
269 | int found = 0; |
270 | void* tmpData; |
271 | |
272 | if (rootNode == NIL) { |
273 | rpterr("swap_ctnr: NIL argument" ); |
274 | return; |
275 | } |
276 | |
277 | if (pos1 == pos2) |
278 | return; |
279 | |
280 | for (it = rootNode->next; it != rootNode; it = it->next) { |
281 | if (counter == pos1) { |
282 | node1 = it; |
283 | found++; |
284 | if (found == 2) |
285 | break; |
286 | } |
287 | if (counter == pos2) { |
288 | node2 = it; |
289 | found++; |
290 | if (found == 2) |
291 | break; |
292 | } |
293 | |
294 | counter++; |
295 | } |
296 | |
297 | if (found == 2) { |
298 | tmpData = node1->data; |
299 | node1->data = node2->data; |
300 | node2->data = tmpData; |
301 | } |
302 | } |
303 | |
304 | /* O(n log n) */ |
305 | void bsort_ctnr(CONTAINER rootNode, COMPARE_FUNC compare_func) |
306 | { |
307 | /* Use mergesort adapted from http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.c */ |
308 | |
309 | CONTAINER p, q, e, tail, oldhead; |
310 | INDEX insize, nmerges, psize, qsize, i; |
311 | |
312 | if (rootNode == NIL || compare_func == NIL) { |
313 | rpterr("bsort_ctnr: NIL argument" ); |
314 | return; |
315 | } |
316 | |
317 | if (level_ctnr(rootNode) == 0) { |
318 | /* Nothing to sort */ |
319 | return; |
320 | } |
321 | |
322 | insize = 1; |
323 | |
324 | while (1) { |
325 | p = rootNode->next; |
326 | oldhead = rootNode; /* only used for circular linkage */ |
327 | rootNode->next = NULL; |
328 | tail = NULL; |
329 | |
330 | nmerges = 0; /* count number of merges we do in this pass */ |
331 | |
332 | while (p) { |
333 | nmerges++; /* there exists a merge to be done */ |
334 | /* step `insize' places along from p */ |
335 | q = p; |
336 | psize = 0; |
337 | for (i = 0; i < insize; i++) { |
338 | psize++; |
339 | q = (q->next == oldhead ? NULL : q->next); |
340 | if (!q) break; |
341 | } |
342 | |
343 | /* if q hasn't fallen off end, we have two lists to merge */ |
344 | qsize = insize; |
345 | |
346 | /* now we have two lists; merge them */ |
347 | while (psize > 0 || (qsize > 0 && q)) { |
348 | /* decide whether next element of merge comes from p or q */ |
349 | if (psize == 0) { |
350 | assert(q); |
351 | /* p is empty; e must come from q. */ |
352 | e = q; q = q->next; qsize--; |
353 | if (q == oldhead) q = NULL; |
354 | } else if (qsize == 0 || !q) { |
355 | assert(p); |
356 | /* q is empty; e must come from p. */ |
357 | e = p; p = p->next; psize--; |
358 | if (p == oldhead) p = NULL; |
359 | } else if (compare_func(p,q) <= 0) { |
360 | /* First element of p is lower (or same); |
361 | * e must come from p. */ |
362 | e = p; p = p->next; psize--; |
363 | if (p == oldhead) p = NULL; |
364 | } else { |
365 | /* First element of q is lower; e must come from q. */ |
366 | e = q; q = q->next; qsize--; |
367 | if (q == oldhead) q = NULL; |
368 | } |
369 | |
370 | /* add the next element to the merged list */ |
371 | if (tail) { |
372 | tail->next = e; |
373 | e->prev = tail; |
374 | } else { |
375 | rootNode->next = e; |
376 | e->prev = rootNode; |
377 | } |
378 | |
379 | tail = e; |
380 | } |
381 | |
382 | /* now p has stepped `insize' places along, and q has too */ |
383 | p = q; |
384 | } |
385 | |
386 | if (tail) |
387 | tail->next = rootNode; |
388 | rootNode->prev = tail; |
389 | |
390 | /* If we have done only one merge, we're finished. */ |
391 | if (nmerges <= 1) { /* allow for nmerges==0, the empty list case */ |
392 | break; |
393 | } |
394 | |
395 | /* Otherwise repeat, merging lists twice the size */ |
396 | insize *= 2; |
397 | } |
398 | } |
399 | |
400 | /* O(1) */ |
401 | void* first_ctnr(CONTAINER rootNode) |
402 | { |
403 | if (rootNode == NIL) { |
404 | rpterr("first_ctnr: NIL argument" ); |
405 | return NIL; |
406 | } |
407 | |
408 | if (rootNode->next == rootNode) |
409 | return NIL; |
410 | |
411 | ((CONTAINER_INFO)rootNode->data)->currentNode = rootNode->next; |
412 | |
413 | return rootNode->next->data; |
414 | } |
415 | |
416 | /* O(1) */ |
417 | void* next_ctnr(CONTAINER rootNode) |
418 | { |
419 | CONTAINER_INFO info; |
420 | |
421 | if (rootNode == NIL) { |
422 | rpterr("next_ctnr: NIL argument" ); |
423 | return NIL; |
424 | } |
425 | |
426 | info = (CONTAINER_INFO)rootNode->data; |
427 | |
428 | if (info->currentNode->next == rootNode) |
429 | return NIL; |
430 | |
431 | info->currentNode = info->currentNode->next; |
432 | |
433 | return info->currentNode->data; |
434 | } |
435 | |
436 | /* O(1) */ |
437 | void* remove_ctnr(CONTAINER rootNode) |
438 | { |
439 | CONTAINER currentNode, tmp; |
440 | CONTAINER_INFO info; |
441 | void* retval; |
442 | |
443 | if (rootNode == NIL) { |
444 | rpterr("remove_curr_ctnr: NIL argument" ); |
445 | return NIL; |
446 | } |
447 | |
448 | info = (CONTAINER_INFO)rootNode->data; |
449 | currentNode = info->currentNode; |
450 | |
451 | if (currentNode == rootNode) { /* should never happen */ |
452 | rpterr("remove_curr_ctnr: delete root node" ); |
453 | return NIL; |
454 | } |
455 | |
456 | retval = currentNode->data; |
457 | tmp = currentNode->prev; |
458 | |
459 | currentNode->prev->next = currentNode->next; |
460 | currentNode->next->prev = currentNode->prev; |
461 | |
462 | free(currentNode); |
463 | |
464 | info->count--; |
465 | info->currentNode = tmp; |
466 | |
467 | return retval; |
468 | } |
469 | |