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
new_ctnr(void)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) */
zero_destr_ctnr(CONTAINER rootNode,DESTR_FUNC destr_func)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) */
empty_ctnr(CONTAINER rootNode)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) */
level_ctnr(CONTAINER rootNode)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) */
insert_ctnr(CONTAINER rootNode,void * object,INDEX pos)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) */
push_ctnr(CONTAINER rootNode,void * object)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) */
remove_at_ctnr(CONTAINER rootNode,INDEX pos)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) */
pop_ctnr(CONTAINER rootNode)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) */
get_ctnr(CONTAINER rootNode,INDEX pos)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) */
search_ctnr(CONTAINER rootNode,COMPARE_FUNC compare_func,void * pattern)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) */
swap_ctnr(CONTAINER rootNode,INDEX pos1,INDEX pos2)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) */
bsort_ctnr(CONTAINER rootNode,COMPARE_FUNC compare_func)305 void bsort_ctnr(CONTAINER rootNode, COMPARE_FUNC compare_func)
306 {
307 /* Use mergesort adapted from https://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) */
first_ctnr(CONTAINER rootNode)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) */
next_ctnr(CONTAINER rootNode)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) */
remove_ctnr(CONTAINER rootNode)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