FreeWRL / FreeX3D 4.3.0
list.c
1/*
2
3 FreeWRL support library.
4 Linked lists.
5
6*/
7
8/****************************************************************************
9 This file is part of the FreeWRL/FreeX3D Distribution.
10
11 Copyright 2009 CRC Canada. (http://www.crc.gc.ca)
12
13 FreeWRL/FreeX3D is free software: you can redistribute it and/or modify
14 it under the terms of the GNU Lesser Public License as published by
15 the Free Software Foundation, either version 3 of the License, or
16 (at your option) any later version.
17
18 FreeWRL/FreeX3D is distributed in the hope that it will be useful,
19 but WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 GNU General Public License for more details.
22
23 You should have received a copy of the GNU General Public License
24 along with FreeWRL/FreeX3D. If not, see <http://www.gnu.org/licenses/>.
25****************************************************************************/
26
27
28
29#include <config.h>
30#include <system.h>
31#include <internal.h>
32
33#include <list.h>
34
35/* singly linked */
40#if defined(DEBUG_MALLOC) && defined(DEBUG_MALLOC_LIST)
41s_list_t* _ml_new(const void *elem, int line, char *fi)
42{
43 s_list_t *item;
44 item = freewrlMalloc(line, fi, sizeof(s_list_t), TRUE);
45 ml_elem(item) = (void *) elem;
46 return item;
47}
48#else
49s_list_t* ml_new(const void *elem)
50{
51 s_list_t *item;
52 item = XALLOC(s_list_t);
53 ml_elem(item) = (void *) elem;
54 return item;
55}
56#endif
57
61int ml_count(s_list_t *list)
62{
63 int c = 0;
64 while (list) {
65 c++;
66 list = ml_next(list);
67 }
68 return c;
69}
70
76s_list_t* ml_prev(s_list_t *list, s_list_t *item)
77{
78 s_list_t *n;
79 if (!item) return NULL;
80 while (list) {
81 n = ml_next(list);
82 if (!n)
83 return NULL;
84 if (n == item)
85 return list;
86 list = n;
87 }
88 return NULL;
89}
90
94s_list_t* ml_last(s_list_t *list)
95{
96 while (list) {
97 if (!ml_next(list))
98 break;
99 list = ml_next(list);
100 }
101 return list;
102}
103
107s_list_t* ml_find(s_list_t *list, s_list_t *item)
108{
109 while (list) {
110 if (list == item)
111 return list;
112 list = ml_next(list);
113 }
114 return NULL;
115}
116
121s_list_t* ml_find_elem(s_list_t *list, void *elem)
122{
123 while (list) {
124 if (ml_elem(list) == elem)
125 return list;
126 list = ml_next(list);
127 }
128 return NULL;
129}
130
134s_list_t* ml_insert(s_list_t *list, s_list_t *point, s_list_t *item)
135{
136 if (!list) {
137 if (item) ml_next(item) = point;
138 return item;
139 }
140 if (!point || (list == point)) {
141 if (item) ml_next(item) = list;
142 } else {
143 s_list_t *prev;
144 prev = ml_prev(list, point);
145 if (prev) {
146 ml_next(prev) = item;
147 ml_next(item) = point;
148 } else {
149 item = NULL;
150 }
151 }
152 return item;
153}
157s_list_t* ml_append(s_list_t *list, s_list_t *item)
158{
159 if (list) {
160 ml_next(ml_last(list)) = item;
161 return list;
162 }
163 return item;
164}
165
170void ml_delete(s_list_t *list, s_list_t *item)
171{
172 s_list_t *prev;
173 prev = ml_prev(list, item);
174 if (prev) {
175 ml_next(prev) = ml_next(item);
176 XFREE(item);
177 } else {
178 //ERROR_MSG("ml_delete: trying to destroy first element in a list\n");
179 }
180}
181
182s_list_t *ml_remove(s_list_t *list, s_list_t *item)
183{
184 s_list_t *prev, *newlist;
185 newlist = list;
186 prev = ml_prev(list, item);
187 if (prev) {
188 ml_next(prev) = ml_next(item);
189 } else {
190 newlist = NULL;
191 }
192 return newlist;
193}
194void ml_enqueue(s_list_t **list, s_list_t *item)
195{
196 *list = ml_insert(*list,*list,item);
197}
198s_list_t* ml_dequeue(s_list_t **list){
199 s_list_t* item = NULL;
200 item = ml_last(*list);
201 *list = ml_remove(*list,item);
202 return item;
203}
204
205/*when known to be a singlton with next=null, just free it*/
206void ml_free(s_list_t *item){
207 XFREE(item);
208}
216s_list_t* ml_delete_self(s_list_t *list, s_list_t *item)
217{
218 s_list_t *it;
219 if (list == item) {
220 /* first element */
221 it = item->next;
222 XFREE(item);
223 return it;
224 }
225 ml_delete(list, item);
226 return list;
227}
228
233void ml_delete2(s_list_t *list, s_list_t *item, f_free_t f)
234{
235 s_list_t *prev;
236 prev = ml_prev(list, item);
237 ml_next(prev) = ml_next(item);
238 if (ml_elem(item)) {
239 f(ml_elem(item));
240 } else {
241 ERROR_MSG("ml_delete2: *error* deleting empty item %p from list %p\n", item, list);
242 }
243 XFREE(item);
244}
245
250void ml_delete_all(s_list_t *list)
251{
252 s_list_t *next;
253 while (list) {
254 next = ml_next(list);
255 XFREE(list);
256 list = next;
257 }
258}
259
264void ml_delete_all2(s_list_t *list, f_free_t f)
265{
266 s_list_t *begin, *next;
267 f_free_t *FF;
268 begin = list;
269 FF = f;
270 if (!FF) FF = free;
271 while (list) {
272 if (ml_elem(list)) {
273 FF(ml_elem(list));
274 } else {
275 ERROR_MSG("ml_delete_all2: *error* deleting empty item %p from list %p\n", list, begin);
276 }
277 next = ml_next(list);
278 XFREE(list);
279 list = next;
280 }
281}
282
287s_list_t* ml_get(s_list_t* list, int index)
288{
289 int i = 0;
290
291 while (list) {
292 if (i == index)
293 return list;
294 list = ml_next(list);
295 i++;
296 }
297 return NULL;
298}
299
300void ml_dump(s_list_t *list)
301{
302 TRACE_MSG("ml_dump (%p) : ", list);
303 ml_foreach(list, TRACE_MSG("%p ", __l));
304 TRACE_MSG("\n");
305}
306
307void ml_dump_char(s_list_t *list)
308{
309 TRACE_MSG("ml_dump_char (%p) : ", list);
310 ml_foreach(list, TRACE_MSG("%s ", (char*)ml_elem(__l)));
311 TRACE_MSG("\n");
312}
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329/* circularly doubly linked - dug9 added feb 16, 2013 but did not test cdl_ functions,
330 need use for it */
334cd_list_t* cdl_new(const void *elem)
335{
336 cd_list_t *item;
337 item = XALLOC(cd_list_t);
338 cdl_elem(item) = (void *) elem;
339 item->next = item;
340 item->prev = item;
341 return item;
342}
343
347int cdl_count(cd_list_t *head)
348{
349 cd_list_t *list;
350 int c = 0;
351 list = head;
352 if(head) do{
353 c++;
354 list = cdl_next(list);
355 }while(list != head);
356 return c;
357}
358
362cd_list_t* cdl_find(cd_list_t *head, cd_list_t *item)
363{
364 cd_list_t *list = head;
365 if(!head) return NULL;
366 do {
367 if (list == item)
368 return list;
369 list = cdl_next(list);
370 }while(list != head);
371 return NULL;
372}
373
379cd_list_t* cdl_find_elem(cd_list_t *head, void *elem)
380{
381 cd_list_t *list = head;
382 if(!list) return NULL;
383 do {
384 if (cdl_elem(list) == elem)
385 return list;
386 list = cdl_next(list);
387 }while(list != head);
388 return NULL;
389}
390
395cd_list_t* cdl_insert(cd_list_t *head, cd_list_t *point, cd_list_t *item)
396{
397 cd_list_t *tmp;
398 if(!item) return head;
399 if (!head) {
400 tmp = point;
401 if (item){
402 if(!point) tmp = item;
403 item->next = tmp;
404 item->prev = tmp;
405 }
406 return tmp;
407 }
408 if(!point) point = head;
409 point->next = item;
410 item->prev = point->prev;
411 point->prev = item;
412 item->prev->next = item;
413 if(head == point) {
414 head = item;
415 }
416 return head;
417}
418
423cd_list_t* cdl_append(cd_list_t *head, cd_list_t *item)
424{
425 cd_list_t *last;
426 if (head) {
427 last = cdl_prev(head);
428 last->next = item;
429 head->prev = item;
430 item->prev = last;
431 item->next = head;
432 return head;
433 }else{
434 item->prev = item;
435 item->next = item;
436 return item;
437 }
438}
439
445cd_list_t *cdl_delete(cd_list_t *head, cd_list_t *item)
446{
447 cd_list_t *prev, *next, *ret;
448 ret = head;
449 if(!item ){
450 ERROR_MSG("cdl_delete: no head or item\n");
451 return ret;
452 }
453 if(head){
454 if(item == head) ret = head->next;
455 if(head->next == head) ret = NULL;
456 }
457 prev = cdl_prev(item);
458 next = cdl_next(item);
459 prev->next = next;
460 next->prev = prev;
461 XFREE(item);
462 return ret;
463}
464
465
471cd_list_t * cdl_delete2(cd_list_t *head, cd_list_t *item, f_free_t f)
472{
473 cd_list_t *prev, *next, *ret;
474 ret = head;
475 if(!item ){
476 ERROR_MSG("cdl_delete2: no head or item\n");
477 return ret;
478 }
479 if(head){
480 if(item == head) ret = head->next;
481 if(head->next == head) ret = NULL;
482 }
483 prev = cdl_prev(item);
484 next = cdl_next(item);
485 prev->next = next;
486 next->prev = prev;
487 if(cdl_elem(item)) {
488 f(cdl_elem(item));
489 } else {
490 ERROR_MSG("cdl_delete2: *error* deleting empty item %p from list %p\n", item, head);
491 }
492 XFREE(item);
493 return ret;
494}
495
500void cdl_delete_all(cd_list_t *head)
501{
502 cd_list_t *next, *list;
503 list = head;
504 if(list)
505 do{
506 next = cdl_next(list);
507 XFREE(list);
508 list = next;
509 }while(list != head);
510}
511
516void cdl_delete_all2(cd_list_t *head, f_free_t f)
517{
518 cd_list_t *list, *next;
519 f_free_t *FF;
520 list = head;
521 FF = f;
522 if (!FF) FF = free;
523 if(head)
524 do{
525 if (cdl_elem(list)) {
526 FF(cdl_elem(list));
527 } else {
528 ERROR_MSG("cdl_delete_all2: *error* deleting empty item %p from list %p\n", list, head);
529 }
530 next = cdl_next(list);
531 XFREE(list);
532 list = next;
533 }while(list != head);
534}
535
540cd_list_t* cdl_get(cd_list_t* head, int index)
541{
542 cd_list_t* list;
543 int i = 0;
544
545 list = head;
546 if(head)
547 do {
548 if (i == index)
549 return list;
550 list = cdl_next(list);
551 i++;
552 }while(list != head);
553 return NULL;
554}
555
556void cdl_dump(cd_list_t *head)
557{
558 TRACE_MSG("cdl_dump (%p) : ", head);
559 cdl_foreach(list, TRACE_MSG("%p ", __l));
560 TRACE_MSG("\n");
561}
562
563void cdl_dump_char(cd_list_t *head)
564{
565 TRACE_MSG("cdl_dump_char (%p) : ", head);
566 cdl_foreach(list, TRACE_MSG("%s ", (char*)cdl_elem(__l)));
567 TRACE_MSG("\n");
568}