1 | /* |
---|
2 | * (C) 2000 UNIVERSITY OF CHICAGO |
---|
3 | * See COPYRIGHT in top-level directory. |
---|
4 | */ |
---|
5 | |
---|
6 | |
---|
7 | |
---|
8 | #ifdef SYSDARWIN |
---|
9 | #include <sys/malloc.h> |
---|
10 | #else |
---|
11 | #include <malloc.h> |
---|
12 | #endif |
---|
13 | #include <stdlib.h> |
---|
14 | #include <stdio.h> |
---|
15 | #include "listops.h" |
---|
16 | #include "listP.h" |
---|
17 | |
---|
18 | /* |
---|
19 | * list management code |
---|
20 | * |
---|
21 | * For storing singly-linked lists of pointers. |
---|
22 | * |
---|
23 | */ |
---|
24 | |
---|
25 | |
---|
26 | static int itemcount=0; |
---|
27 | static int headcount=0; |
---|
28 | |
---|
29 | |
---|
30 | /* |
---|
31 | * AP_listitem_malloc() |
---|
32 | * |
---|
33 | * malloc a new ilist item and return a pointer to it. |
---|
34 | * |
---|
35 | */ |
---|
36 | |
---|
37 | static pListitem AP_listitem_malloc(void) |
---|
38 | { |
---|
39 | pListitem item; |
---|
40 | |
---|
41 | itemcount++; |
---|
42 | item=(pListitem)malloc( (unsigned) sizeof(Listitem) ); |
---|
43 | |
---|
44 | if (!item) |
---|
45 | { |
---|
46 | perror("AP_listitem_malloc: malloc failure"); |
---|
47 | abort(); |
---|
48 | } |
---|
49 | |
---|
50 | return(item); |
---|
51 | } |
---|
52 | |
---|
53 | |
---|
54 | |
---|
55 | /* |
---|
56 | * AP_listitem_free(listitem) |
---|
57 | * |
---|
58 | * Free a listitem generated by AP_listitem_malloc() |
---|
59 | * |
---|
60 | */ |
---|
61 | |
---|
62 | static void AP_listitem_free(pListitem listitem) |
---|
63 | { |
---|
64 | free(listitem); |
---|
65 | itemcount--; |
---|
66 | } |
---|
67 | |
---|
68 | |
---|
69 | |
---|
70 | /* |
---|
71 | * AP_listitem_verify(void) |
---|
72 | * |
---|
73 | * Checks to see if there are any outstanding listitems that have been |
---|
74 | * malloc'd. Returns true if there are any. |
---|
75 | * |
---|
76 | */ |
---|
77 | |
---|
78 | int AP_listitem_verify(void) |
---|
79 | { |
---|
80 | if (itemcount!=0) |
---|
81 | fprintf(stderr,"AP_list_verify: outstanding items, count=%d\n", |
---|
82 | itemcount); |
---|
83 | |
---|
84 | if (headcount!=0) |
---|
85 | fprintf(stderr,"AP_list_verify: outstanding lists, count=%d\n", |
---|
86 | headcount); |
---|
87 | |
---|
88 | return( (itemcount!=0) || (headcount!=0) ); |
---|
89 | } |
---|
90 | |
---|
91 | |
---|
92 | |
---|
93 | |
---|
94 | pListitem AP_listitem_prev(pListitem listitem) |
---|
95 | { |
---|
96 | return(listitem->prev); |
---|
97 | } |
---|
98 | |
---|
99 | |
---|
100 | |
---|
101 | pListitem AP_listitem_next(pListitem listitem) |
---|
102 | { |
---|
103 | return(listitem->next); |
---|
104 | } |
---|
105 | |
---|
106 | |
---|
107 | |
---|
108 | |
---|
109 | void *AP_listitem_data(pListitem listitem) |
---|
110 | { |
---|
111 | return(listitem->data ); |
---|
112 | } |
---|
113 | |
---|
114 | |
---|
115 | |
---|
116 | |
---|
117 | /***************************************************************/ |
---|
118 | |
---|
119 | |
---|
120 | |
---|
121 | /* |
---|
122 | * AP_list_new(void) |
---|
123 | * |
---|
124 | * allocate an empty list return a pointer to it |
---|
125 | * |
---|
126 | */ |
---|
127 | |
---|
128 | pList AP_list_new(void) |
---|
129 | { |
---|
130 | pList list; |
---|
131 | |
---|
132 | list=(pList)malloc(sizeof(List)); |
---|
133 | |
---|
134 | if (!list) |
---|
135 | { |
---|
136 | perror("AP_list_new: malloc failure\n"); |
---|
137 | abort(); |
---|
138 | } |
---|
139 | |
---|
140 | list->head=NULL; |
---|
141 | list->tail=NULL; |
---|
142 | list->count=0; |
---|
143 | |
---|
144 | headcount++; |
---|
145 | return(list); |
---|
146 | } |
---|
147 | |
---|
148 | |
---|
149 | |
---|
150 | |
---|
151 | |
---|
152 | /* |
---|
153 | * AP_list_free(list) |
---|
154 | * |
---|
155 | * Free an entire list |
---|
156 | * |
---|
157 | */ |
---|
158 | |
---|
159 | void AP_list_free(pList list) |
---|
160 | { |
---|
161 | pListitem next,cur; |
---|
162 | int count; |
---|
163 | |
---|
164 | count=0; |
---|
165 | cur=list->head; |
---|
166 | |
---|
167 | while(cur) |
---|
168 | { |
---|
169 | next=cur->next; |
---|
170 | |
---|
171 | AP_listitem_free(cur); |
---|
172 | count++; |
---|
173 | |
---|
174 | cur=next; |
---|
175 | } |
---|
176 | |
---|
177 | if (count!=list->count) |
---|
178 | { |
---|
179 | fprintf(stderr,"AP_list_free: count %d does not match actual length %d\n", |
---|
180 | list->count,count); |
---|
181 | abort(); |
---|
182 | } |
---|
183 | |
---|
184 | headcount--; |
---|
185 | free(list); |
---|
186 | } |
---|
187 | |
---|
188 | |
---|
189 | |
---|
190 | /* |
---|
191 | * AP_list_size(list) |
---|
192 | * |
---|
193 | * return the number of items in an ilist |
---|
194 | * |
---|
195 | */ |
---|
196 | |
---|
197 | int AP_list_size(pList list) |
---|
198 | { |
---|
199 | return(list->count); |
---|
200 | } |
---|
201 | |
---|
202 | |
---|
203 | |
---|
204 | /* |
---|
205 | * AP_list_prepend(list,data) |
---|
206 | * |
---|
207 | * Prepend item to the front of list. |
---|
208 | * |
---|
209 | */ |
---|
210 | |
---|
211 | pListitem AP_list_prepend(pList list, void *data) |
---|
212 | { |
---|
213 | pListitem new; |
---|
214 | |
---|
215 | new=AP_listitem_malloc(); |
---|
216 | |
---|
217 | new->data=data; |
---|
218 | new->prev=NULL; |
---|
219 | new->next=list->head; |
---|
220 | |
---|
221 | #ifdef CHECKS |
---|
222 | new->list=list; |
---|
223 | #endif |
---|
224 | |
---|
225 | if (list->head) |
---|
226 | list->head->prev=new; |
---|
227 | |
---|
228 | list->head=new; |
---|
229 | if (!list->tail) |
---|
230 | list->tail=new; |
---|
231 | |
---|
232 | (list->count)++; |
---|
233 | |
---|
234 | return(new); |
---|
235 | } |
---|
236 | |
---|
237 | |
---|
238 | |
---|
239 | /* |
---|
240 | * AP_list_append(list,data) |
---|
241 | * |
---|
242 | * append item to end of list |
---|
243 | * |
---|
244 | */ |
---|
245 | |
---|
246 | pListitem AP_list_append(pList list, void *data) |
---|
247 | { |
---|
248 | pListitem new; |
---|
249 | |
---|
250 | new=AP_listitem_malloc(); |
---|
251 | new->data=data; |
---|
252 | new->prev=list->tail; |
---|
253 | new->next= NULL; |
---|
254 | |
---|
255 | #ifdef CHECKS |
---|
256 | new->list= list; |
---|
257 | #endif |
---|
258 | |
---|
259 | if (list->tail) |
---|
260 | list->tail->next=new; |
---|
261 | else |
---|
262 | list->head=new; |
---|
263 | |
---|
264 | list->tail=new; |
---|
265 | (list->count)++; |
---|
266 | |
---|
267 | return(new); |
---|
268 | } |
---|
269 | |
---|
270 | |
---|
271 | |
---|
272 | |
---|
273 | |
---|
274 | /* |
---|
275 | * AP_list_delete(list,data) |
---|
276 | * |
---|
277 | * delete item from list; return TRUE if successful |
---|
278 | * |
---|
279 | */ |
---|
280 | |
---|
281 | int AP_list_delete(pList list, void *data) |
---|
282 | { |
---|
283 | pListitem item; |
---|
284 | |
---|
285 | if (item=AP_list_search(list,data)) |
---|
286 | { |
---|
287 | AP_list_delete_item(list,item); |
---|
288 | return(1); |
---|
289 | } |
---|
290 | |
---|
291 | return(0); |
---|
292 | } |
---|
293 | |
---|
294 | |
---|
295 | |
---|
296 | void AP_list_delete_item(pList list, pListitem item) |
---|
297 | { |
---|
298 | |
---|
299 | #ifdef CHECKS |
---|
300 | if (item->list != list) |
---|
301 | { |
---|
302 | fprintf(stderr,"AP_list_delete_item: item is not in list\n"); |
---|
303 | abort(); |
---|
304 | } |
---|
305 | #endif |
---|
306 | |
---|
307 | /* set pointer of prior listitem */ |
---|
308 | |
---|
309 | if (item == list->head) |
---|
310 | list->head = item->next; |
---|
311 | else |
---|
312 | item->prev->next = item->next; |
---|
313 | |
---|
314 | /* set pointer of following listitem */ |
---|
315 | |
---|
316 | if (item == list->tail) |
---|
317 | list->tail = item->prev; |
---|
318 | else |
---|
319 | item->next->prev = item->prev; |
---|
320 | |
---|
321 | AP_listitem_free(item); |
---|
322 | (list->count)--; |
---|
323 | } |
---|
324 | |
---|
325 | |
---|
326 | |
---|
327 | |
---|
328 | pListitem AP_list_head_item(pList list) |
---|
329 | { |
---|
330 | return(list->head); |
---|
331 | } |
---|
332 | |
---|
333 | |
---|
334 | |
---|
335 | int AP_list_head(pList list, void **data) |
---|
336 | { |
---|
337 | if (list->head) |
---|
338 | { |
---|
339 | *data=list->head->data; |
---|
340 | return(1); |
---|
341 | } |
---|
342 | else |
---|
343 | return(0); |
---|
344 | } |
---|
345 | |
---|
346 | |
---|
347 | |
---|
348 | int AP_list_tail(pList list, void **data) |
---|
349 | { |
---|
350 | if (list->tail) |
---|
351 | { |
---|
352 | *data=list->tail->data; |
---|
353 | return(1); |
---|
354 | } |
---|
355 | else |
---|
356 | return(0); |
---|
357 | } |
---|
358 | |
---|
359 | |
---|
360 | |
---|
361 | |
---|
362 | |
---|
363 | /* |
---|
364 | * AP_list_print(str,list) |
---|
365 | * |
---|
366 | * Print out the message string followed by the |
---|
367 | * items in the list |
---|
368 | * |
---|
369 | */ |
---|
370 | |
---|
371 | void AP_list_print(char *str, pList list) |
---|
372 | { |
---|
373 | pListitem cur; |
---|
374 | |
---|
375 | printf("%s (%d items): ",str,list->count); |
---|
376 | |
---|
377 | cur=list->head; |
---|
378 | while(cur) |
---|
379 | { |
---|
380 | printf("%d ",(int)cur->data); |
---|
381 | cur=cur->next; |
---|
382 | } |
---|
383 | |
---|
384 | printf("\n"); |
---|
385 | } |
---|
386 | |
---|
387 | |
---|
388 | |
---|
389 | |
---|
390 | /* |
---|
391 | * AP_list_revprint(str,list) |
---|
392 | * |
---|
393 | * Print out the message string followed by the |
---|
394 | * items in the list |
---|
395 | * |
---|
396 | */ |
---|
397 | |
---|
398 | void AP_list_revprint(char *str, pList list) |
---|
399 | { |
---|
400 | pListitem cur; |
---|
401 | |
---|
402 | printf("%s (%d items): ",str,list->count); |
---|
403 | |
---|
404 | cur=list->tail; |
---|
405 | while(cur) |
---|
406 | { |
---|
407 | printf("%d ",(int)cur->data); |
---|
408 | cur=cur->prev; |
---|
409 | } |
---|
410 | |
---|
411 | printf("\n"); |
---|
412 | } |
---|
413 | |
---|
414 | |
---|
415 | |
---|
416 | |
---|
417 | /* |
---|
418 | * AP_list_search(list,data) |
---|
419 | * |
---|
420 | * Returns listitem if item appears in the list, otherwise NULL. |
---|
421 | * |
---|
422 | */ |
---|
423 | |
---|
424 | |
---|
425 | pListitem AP_list_search(pList list, void *data) |
---|
426 | { |
---|
427 | pListitem cur; |
---|
428 | |
---|
429 | cur=list->head; |
---|
430 | |
---|
431 | while (cur) |
---|
432 | { |
---|
433 | if (cur->data == data) |
---|
434 | return(cur); |
---|
435 | |
---|
436 | cur=cur->next; |
---|
437 | } |
---|
438 | |
---|
439 | return(NULL); |
---|
440 | } |
---|
441 | |
---|
442 | |
---|
443 | /* |
---|
444 | * AP_list_search_func(list,func,data) |
---|
445 | * |
---|
446 | * Returns listitem if func(listitem->data,data) returns true |
---|
447 | * |
---|
448 | */ |
---|
449 | |
---|
450 | |
---|
451 | pListitem AP_list_search_func(pList list, |
---|
452 | int (*func)(void *item_data, void *fixed_data), |
---|
453 | void *fixed_data) |
---|
454 | { |
---|
455 | pListitem cur; |
---|
456 | |
---|
457 | cur=list->head; |
---|
458 | |
---|
459 | while (cur) |
---|
460 | { |
---|
461 | if ( (*func)(cur->data,fixed_data) ) |
---|
462 | return(cur); |
---|
463 | |
---|
464 | cur=cur->next; |
---|
465 | } |
---|
466 | |
---|
467 | return(NULL); |
---|
468 | } |
---|
469 | |
---|
470 | |
---|
471 | |
---|
472 | /* |
---|
473 | * AP_list_next(list,data,temp) |
---|
474 | * |
---|
475 | * like PList_next() except handles NULL pointers properly. |
---|
476 | * |
---|
477 | * initially, pass in (void **) NULL in 'temp' |
---|
478 | * returns next list item through 'item' |
---|
479 | * returns nonzero if there is a next item |
---|
480 | * |
---|
481 | */ |
---|
482 | |
---|
483 | int AP_list_next(pList list, void **data, void **temp) |
---|
484 | { |
---|
485 | pListitem cur; |
---|
486 | |
---|
487 | if (*temp) /* temp is previous item */ |
---|
488 | { |
---|
489 | cur=(pListitem)(*temp); |
---|
490 | cur=cur->next; |
---|
491 | } |
---|
492 | else /* First item */ |
---|
493 | cur=list->head; |
---|
494 | |
---|
495 | if (cur) |
---|
496 | { |
---|
497 | *temp=(void *)cur; |
---|
498 | *data=cur->data; |
---|
499 | return(1); |
---|
500 | } |
---|
501 | else |
---|
502 | return(0); |
---|
503 | } |
---|
504 | |
---|
505 | |
---|
506 | /* |
---|
507 | * Compatibility routine for scorec list traversal |
---|
508 | * Does not provide any way to differentiate |
---|
509 | * between NULL in the list, and the end of the list |
---|
510 | * |
---|
511 | */ |
---|
512 | |
---|
513 | void *AP_list_braindead_next(pList list, void **temp) |
---|
514 | { |
---|
515 | void *item; |
---|
516 | |
---|
517 | if (AP_list_next(list,&item,temp)) |
---|
518 | return(item); |
---|
519 | else |
---|
520 | return(NULL); |
---|
521 | } |
---|
522 | |
---|
523 | |
---|
524 | |
---|
525 | /* |
---|
526 | * AP_list_duplicate(list) |
---|
527 | * |
---|
528 | * return a copy of the list |
---|
529 | * (Note: caller is responsible for freeing this list) |
---|
530 | * |
---|
531 | */ |
---|
532 | |
---|
533 | pList AP_list_duplicate(pList list) |
---|
534 | { |
---|
535 | pList newlist; |
---|
536 | pListitem cur,new,prev; |
---|
537 | |
---|
538 | newlist=AP_list_new(); |
---|
539 | prev=NULL; |
---|
540 | |
---|
541 | cur=list->head; |
---|
542 | while(cur) |
---|
543 | { |
---|
544 | new=AP_listitem_malloc(); |
---|
545 | new->data=cur->data; |
---|
546 | new->prev=prev; |
---|
547 | |
---|
548 | if (prev) |
---|
549 | prev->next=new; |
---|
550 | else |
---|
551 | newlist->head=new; |
---|
552 | |
---|
553 | prev=new; |
---|
554 | |
---|
555 | cur=cur->next; |
---|
556 | } |
---|
557 | |
---|
558 | if (prev) |
---|
559 | prev->next=NULL; |
---|
560 | |
---|
561 | newlist->tail=prev; |
---|
562 | newlist->count=list->count; |
---|
563 | return(newlist); |
---|
564 | } |
---|
565 | |
---|
566 | |
---|
567 | |
---|
568 | int AP_list_apply(pList list, |
---|
569 | int (*func)(void *item_data, void *fixed_data), |
---|
570 | void *fixed_data) |
---|
571 | { |
---|
572 | pListitem cur; |
---|
573 | int total; |
---|
574 | |
---|
575 | total=0; |
---|
576 | cur=list->head; |
---|
577 | |
---|
578 | while (cur) |
---|
579 | { |
---|
580 | total += (*func)(cur->data,fixed_data); |
---|
581 | |
---|
582 | cur=cur->next; |
---|
583 | } |
---|
584 | |
---|
585 | return(total); |
---|
586 | } |
---|
587 | |
---|
588 | |
---|
589 | |
---|
590 | |
---|
591 | /* |
---|
592 | * main for debugging |
---|
593 | * |
---|
594 | */ |
---|
595 | |
---|
596 | |
---|
597 | #ifdef LISTMAIN |
---|
598 | |
---|
599 | int main() |
---|
600 | { |
---|
601 | pList mylist, list2; |
---|
602 | int i; |
---|
603 | void *temp,*item; |
---|
604 | pListitem next; |
---|
605 | |
---|
606 | mylist=AP_list_new(); |
---|
607 | |
---|
608 | for (i=1; i<10; i++) |
---|
609 | { |
---|
610 | AP_list_prepend(mylist,(void *)i); |
---|
611 | AP_list_print("current",mylist); |
---|
612 | AP_list_revprint(" rev",mylist); |
---|
613 | } |
---|
614 | |
---|
615 | printf("Size %d\n",AP_list_size(mylist)); |
---|
616 | |
---|
617 | for (i=10; i<15; i++) |
---|
618 | { |
---|
619 | AP_list_append(mylist,(void *)i); |
---|
620 | AP_list_print("new",mylist); |
---|
621 | AP_list_revprint(" rev",mylist); |
---|
622 | } |
---|
623 | |
---|
624 | AP_list_delete(mylist,(void *)5); |
---|
625 | AP_list_print("less 5",mylist); |
---|
626 | AP_list_revprint(" rev",mylist); |
---|
627 | |
---|
628 | AP_list_delete(mylist,(void *)9); |
---|
629 | AP_list_print("less 9",mylist); |
---|
630 | AP_list_revprint(" rev",mylist); |
---|
631 | |
---|
632 | AP_list_delete(mylist,(void *)14); |
---|
633 | AP_list_print("less 14",mylist); |
---|
634 | AP_list_revprint(" rev",mylist); |
---|
635 | |
---|
636 | AP_list_delete(mylist,(void *)2); |
---|
637 | AP_list_print("less 2",mylist); |
---|
638 | AP_list_revprint(" rev",mylist); |
---|
639 | |
---|
640 | if (!AP_list_delete(mylist,(void *)0)) |
---|
641 | printf("(did not delete 0)\n"); |
---|
642 | else |
---|
643 | printf("ERROR - found 0\n"); |
---|
644 | AP_list_print("less 0",mylist); |
---|
645 | AP_list_revprint(" rev",mylist); |
---|
646 | |
---|
647 | if (AP_list_search(mylist,(void *)4)) |
---|
648 | printf("Found 4\n"); |
---|
649 | else |
---|
650 | printf("Did not find 4\n"); |
---|
651 | |
---|
652 | if (AP_list_search(mylist,(void *)9)) |
---|
653 | printf("Found 9\n"); |
---|
654 | else |
---|
655 | printf("Did not find 9\n"); |
---|
656 | |
---|
657 | printf("Traversal by AP_list_next()\n"); |
---|
658 | temp=NULL; |
---|
659 | while (AP_list_next(mylist,&item,&temp)) |
---|
660 | printf(" Got item %d\n",(int)item); |
---|
661 | |
---|
662 | printf("Traversal by AP_listitem_next()\n"); |
---|
663 | for (item=AP_list_head_item(mylist); item; item=AP_listitem_next(item)) |
---|
664 | printf(" Got item %d\n",(int)(AP_listitem_data(item))); |
---|
665 | |
---|
666 | |
---|
667 | list2=AP_list_duplicate(mylist); |
---|
668 | AP_list_print("Original list",mylist); |
---|
669 | AP_list_revprint(" rev",mylist); |
---|
670 | AP_list_print("Duplicate ",list2); |
---|
671 | AP_list_revprint(" rev",list2); |
---|
672 | |
---|
673 | AP_list_append(list2,(void *)99); |
---|
674 | AP_list_print("Dup add 99 ",list2); |
---|
675 | AP_list_revprint(" rev",list2); |
---|
676 | |
---|
677 | |
---|
678 | printf("Traversal by AP_listitem_next(), deleting\n"); |
---|
679 | i=0; |
---|
680 | for (item=AP_list_head_item(list2); item; ) |
---|
681 | { |
---|
682 | printf(" Got item %d",(int)(AP_listitem_data(item))); |
---|
683 | |
---|
684 | next=AP_listitem_next(item); |
---|
685 | |
---|
686 | if (i%2) |
---|
687 | { |
---|
688 | AP_list_delete_item(list2,item); |
---|
689 | printf(" - deleted\n"); |
---|
690 | } |
---|
691 | else |
---|
692 | printf("\n"); |
---|
693 | |
---|
694 | item=next; |
---|
695 | i++; |
---|
696 | } |
---|
697 | |
---|
698 | AP_list_print("After delete-traversal",list2); |
---|
699 | |
---|
700 | AP_list_free(mylist); |
---|
701 | AP_list_print("After del ",list2); |
---|
702 | AP_list_revprint(" rev",list2); |
---|
703 | |
---|
704 | AP_list_free(list2); |
---|
705 | |
---|
706 | AP_listitem_verify(); |
---|
707 | |
---|
708 | return(0); |
---|
709 | } |
---|
710 | #endif |
---|