1 /* Code in this file is taken from the book:
2 "Mastering Algorithms with C" by Kyle Loudon, published by O'Reilly & Associates. This
3 code is under copyright and cannot be included in any other book, publication,
4 or educational product without permission from O'Reilly & Associates. No
5 warranty is attached; we cannot take responsibility for errors or fitness for
6 use.
7 */
8
9 #include <stdlib.h>
10 #include <string.h>
11
12 #include "suma_algorithms.h"
13
14
15 /*****************************************************************************
16 * *
17 * -------------------------------- list.c -------------------------------- *
18 * *
19 *****************************************************************************/
20
21 /*****************************************************************************
22 * *
23 * ------------------------------- list_init ------------------------------ *
24 * *
25 *****************************************************************************/
26
list_init(List * list,void (* destroy)(void * data))27 void list_init(List *list, void (*destroy)(void *data)) {
28
29 /*****************************************************************************
30 * *
31 * Initialize the list. *
32 * *
33 *****************************************************************************/
34
35 list->size = 0;
36 list->destroy = destroy;
37 list->head = NULL;
38 list->tail = NULL;
39
40 return;
41
42 }
43
44 /*****************************************************************************
45 * *
46 * ----------------------------- list_destroy ----------------------------- *
47 * *
48 *****************************************************************************/
49
list_destroy(List * list)50 void list_destroy(List *list) {
51
52 void *data;
53
54 /*****************************************************************************
55 * *
56 * Remove each element. *
57 * *
58 *****************************************************************************/
59
60 while (list_size(list) > 0) {
61
62 if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy !=
63 NULL) {
64
65 /***********************************************************************
66 * *
67 * Call a user-defined function to free dynamically allocated data. *
68 * *
69 ***********************************************************************/
70
71 list->destroy(data);
72
73 }
74
75 }
76
77 /*****************************************************************************
78 * *
79 * No operations are allowed now, but clear the structure as a precaution. *
80 * *
81 *****************************************************************************/
82
83 memset(list, 0, sizeof(List));
84
85 return;
86
87 }
88
89 /*****************************************************************************
90 * *
91 * ----------------------------- list_ins_next ---------------------------- *
92 * *
93 *****************************************************************************/
94
list_ins_next(List * list,ListElmt * element,const void * data)95 int list_ins_next(List *list, ListElmt *element, const void *data) {
96
97 ListElmt *new_element;
98
99 /*****************************************************************************
100 * *
101 * Allocate storage for the element. *
102 * *
103 *****************************************************************************/
104
105 if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
106 return -1;
107
108 /*****************************************************************************
109 * *
110 * Insert the element into the list. *
111 * *
112 *****************************************************************************/
113
114 new_element->data = (void *)data;
115
116 if (element == NULL) {
117
118 /**************************************************************************
119 * *
120 * Handle insertion at the head of the list. *
121 * *
122 **************************************************************************/
123
124 if (list_size(list) == 0)
125 list->tail = new_element;
126
127 new_element->next = list->head;
128 list->head = new_element;
129
130 }
131
132 else {
133
134 /**************************************************************************
135 * *
136 * Handle insertion somewhere other than at the head. *
137 * *
138 **************************************************************************/
139
140 if (element->next == NULL)
141 list->tail = new_element;
142
143 new_element->next = element->next;
144 element->next = new_element;
145
146 }
147
148 /*****************************************************************************
149 * *
150 * Adjust the size of the list to account for the inserted element. *
151 * *
152 *****************************************************************************/
153
154 list->size++;
155
156 return 0;
157
158 }
159
160 /*****************************************************************************
161 * *
162 * ----------------------------- list_rem_next ---------------------------- *
163 * *
164 *****************************************************************************/
165
list_rem_next(List * list,ListElmt * element,void ** data)166 int list_rem_next(List *list, ListElmt *element, void **data) {
167
168 ListElmt *old_element;
169
170 /*****************************************************************************
171 * *
172 * Do not allow removal from an empty list. *
173 * *
174 *****************************************************************************/
175
176 if (list_size(list) == 0)
177 return -1;
178
179 /*****************************************************************************
180 * *
181 * Remove the element from the list. *
182 * *
183 *****************************************************************************/
184
185 if (element == NULL) {
186
187 /**************************************************************************
188 * *
189 * Handle removal from the head of the list. *
190 * *
191 **************************************************************************/
192
193 *data = list->head->data;
194 old_element = list->head;
195 list->head = list->head->next;
196
197 if (list_size(list) == 1)
198 list->tail = NULL;
199
200 }
201
202 else {
203
204 /**************************************************************************
205 * *
206 * Handle removal from somewhere other than the head. *
207 * *
208 **************************************************************************/
209
210 if (element->next == NULL)
211 return -1;
212
213 *data = element->next->data;
214 old_element = element->next;
215 element->next = element->next->next;
216
217 if (element->next == NULL)
218 list->tail = element;
219
220 }
221
222 /*****************************************************************************
223 * *
224 * Free the storage allocated by the abstract data type. *
225 * *
226 *****************************************************************************/
227
228 free(old_element);
229
230 /*****************************************************************************
231 * *
232 * Adjust the size of the list to account for the removed element. *
233 * *
234 *****************************************************************************/
235
236 list->size--;
237
238 return 0;
239
240 }
241
242 /*****************************************************************************
243 * *
244 * ------------------------------- clist.c -------------------------------- *
245 * *
246 *****************************************************************************/
247
248
249 /*****************************************************************************
250 * *
251 * ------------------------------ clist_init ------------------------------ *
252 * *
253 *****************************************************************************/
254
clist_init(CList * list,void (* destroy)(void * data))255 void clist_init(CList *list, void (*destroy)(void *data)) {
256
257 /*****************************************************************************
258 * *
259 * Initialize the list. *
260 * *
261 *****************************************************************************/
262
263 list->size = 0;
264 list->destroy = destroy;
265 list->head = NULL;
266
267 return;
268
269 }
270
271 /*****************************************************************************
272 * *
273 * ---------------------------- clist_destroy ----------------------------- *
274 * *
275 *****************************************************************************/
276
clist_destroy(CList * list)277 void clist_destroy(CList *list) {
278
279 void *data;
280
281 /*****************************************************************************
282 * *
283 * Remove each element. *
284 * *
285 *****************************************************************************/
286
287 while (clist_size(list) > 0) {
288
289 if (clist_rem_next(list, list->head, (void **)&data) == 0 && list->destroy
290 != NULL) {
291
292 /***********************************************************************
293 * *
294 * Call a user-defined function to free dynamically allocated data. *
295 * *
296 ***********************************************************************/
297
298 list->destroy(data);
299
300 }
301
302 }
303
304 /*****************************************************************************
305 * *
306 * No operations are allowed now, but clear the structure as a precaution. *
307 * *
308 *****************************************************************************/
309
310 memset(list, 0, sizeof(CList));
311
312 return;
313
314 }
315
316 /*****************************************************************************
317 * *
318 * ---------------------------- clist_ins_next ---------------------------- *
319 * *
320 *****************************************************************************/
321
clist_ins_next(CList * list,CListElmt * element,const void * data)322 int clist_ins_next(CList *list, CListElmt *element, const void *data) {
323
324 CListElmt *new_element;
325
326 /*****************************************************************************
327 * *
328 * Allocate storage for the element. *
329 * *
330 *****************************************************************************/
331
332 if ((new_element = (CListElmt *)malloc(sizeof(CListElmt))) == NULL)
333 return -1;
334
335 /*****************************************************************************
336 * *
337 * Insert the element into the list. *
338 * *
339 *****************************************************************************/
340
341 new_element->data = (void *)data;
342
343 if (clist_size(list) == 0) {
344
345 /**************************************************************************
346 * *
347 * Handle insertion when the list is empty. *
348 * *
349 **************************************************************************/
350
351 new_element->next = new_element;
352 list->head = new_element;
353
354 }
355
356 else {
357
358 /**************************************************************************
359 * *
360 * Handle insertion when the list is not empty. *
361 * *
362 **************************************************************************/
363
364 new_element->next = element->next;
365 element->next = new_element;
366
367 }
368
369 /*****************************************************************************
370 * *
371 * Adjust the size of the list to account for the inserted element. *
372 * *
373 *****************************************************************************/
374
375 list->size++;
376
377 return 0;
378
379 }
380
381 /*****************************************************************************
382 * *
383 * ---------------------------- clist_rem_next ---------------------------- *
384 * *
385 *****************************************************************************/
386
clist_rem_next(CList * list,CListElmt * element,void ** data)387 int clist_rem_next(CList *list, CListElmt *element, void **data) {
388
389 CListElmt *old_element;
390
391 /*****************************************************************************
392 * *
393 * Do not allow removal from an empty list. *
394 * *
395 *****************************************************************************/
396
397 if (clist_size(list) == 0)
398 return -1;
399
400 /*****************************************************************************
401 * *
402 * Remove the element from the list. *
403 * *
404 *****************************************************************************/
405
406 *data = element->next->data;
407
408 if (element->next == element) {
409
410 /**************************************************************************
411 * *
412 * Handle removing the last element. *
413 * *
414 **************************************************************************/
415
416 old_element = element->next;
417 list->head = NULL;
418
419 }
420
421 else {
422
423 /**************************************************************************
424 * *
425 * Handle removing other than the last element. *
426 * *
427 **************************************************************************/
428
429 old_element = element->next;
430 element->next = element->next->next;
431
432 }
433
434 /*****************************************************************************
435 * *
436 * Free the storage allocated by the abstract data type. *
437 * *
438 *****************************************************************************/
439
440 free(old_element);
441
442 /*****************************************************************************
443 * *
444 * Adjust the size of the list to account for the removed element. *
445 * *
446 *****************************************************************************/
447
448 list->size--;
449
450 return 0;
451
452 }
453 /*****************************************************************************
454 * *
455 * ------------------------------- dlist.c -------------------------------- *
456 * *
457 *****************************************************************************/
458
459 /*****************************************************************************
460 * *
461 * ------------------------------ dlist_init ------------------------------ *
462 * *
463 *****************************************************************************/
464
dlist_init(DList * list,void (* destroy)(void * data))465 void dlist_init(DList *list, void (*destroy)(void *data)) {
466
467 /*****************************************************************************
468 * *
469 * Initialize the list. *
470 * *
471 *****************************************************************************/
472
473 list->size = 0;
474 list->destroy = destroy;
475 list->head = NULL;
476 list->tail = NULL;
477
478 return;
479
480 }
481
482 /*****************************************************************************
483 * *
484 * ---------------------------- dlist_destroy ----------------------------- *
485 * *
486 *****************************************************************************/
487
dlist_destroy(DList * list)488 void dlist_destroy(DList *list) {
489 dlist_destroy_z(list, 0);
490 }
491
dlist_destroy_z(DList * list,int content_only)492 void dlist_destroy_z(DList *list, int content_only) {
493
494 void *data;
495
496 /*****************************************************************************
497 * *
498 * Remove each element. *
499 * *
500 *****************************************************************************/
501
502 while (dlist_size(list) > 0) {
503
504 if (dlist_remove(list, dlist_tail(list), (void **)&data) == 0 && list->
505 destroy != NULL) {
506
507 /***********************************************************************
508 * *
509 * Call a user-defined function to free dynamically allocated data. *
510 * *
511 ***********************************************************************/
512
513 list->destroy(data);
514
515 }
516
517 }
518
519 /*****************************************************************************
520 * *
521 * No operations are allowed now, but clear the structure as a precaution. *
522 * *
523 *****************************************************************************/
524
525 if (!content_only) memset(list, 0, sizeof(DList));
526
527 return;
528
529 }
530
531 /* Clear all content but leave list initialized */
dlist_empty(DList * list)532 void dlist_empty(DList *list) {
533 dlist_destroy_z(list, 1);
534 }
535
536
537 /*****************************************************************************
538 * *
539 * ---------------------------- dlist_ins_next ---------------------------- *
540 * *
541 *****************************************************************************/
542
dlist_ins_next(DList * list,DListElmt * element,const void * data)543 int dlist_ins_next(DList *list, DListElmt *element, const void *data) {
544
545 DListElmt *new_element;
546
547 /*****************************************************************************
548 * *
549 * Do not allow a NULL element unless the list is empty. *
550 * *
551 *****************************************************************************/
552
553 if (element == NULL && dlist_size(list) != 0)
554 return -1;
555
556 /*****************************************************************************
557 * *
558 * Allocate storage for the element. *
559 * *
560 *****************************************************************************/
561
562 if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
563 return -1;
564
565 /*****************************************************************************
566 * *
567 * Insert the new element into the list. *
568 * *
569 *****************************************************************************/
570
571 new_element->data = (void *)data;
572
573 if (dlist_size(list) == 0) {
574
575 /**************************************************************************
576 * *
577 * Handle insertion when the list is empty. *
578 * *
579 **************************************************************************/
580
581 list->head = new_element;
582 list->head->prev = NULL;
583 list->head->next = NULL;
584 list->tail = new_element;
585
586 }
587
588 else {
589
590 /**************************************************************************
591 * *
592 * Handle insertion when the list is not empty. *
593 * *
594 **************************************************************************/
595
596 new_element->next = element->next;
597 new_element->prev = element;
598
599 if (element->next == NULL)
600 list->tail = new_element;
601 else
602 element->next->prev = new_element;
603
604 element->next = new_element;
605
606 }
607
608 /*****************************************************************************
609 * *
610 * Adjust the size of the list to account for the inserted element. *
611 * *
612 *****************************************************************************/
613
614 list->size++;
615
616 return 0;
617
618 }
619
620 /*****************************************************************************
621 * *
622 * ---------------------------- dlist_ins_prev ---------------------------- *
623 * *
624 *****************************************************************************/
625
626
dlist_ins_prev(DList * list,DListElmt * element,const void * data)627 int dlist_ins_prev(DList *list, DListElmt *element, const void *data) {
628
629 DListElmt *new_element;
630
631 /*****************************************************************************
632 * *
633 * Do not allow a NULL element unless the list is empty. *
634 * *
635 *****************************************************************************/
636
637 if (element == NULL && dlist_size(list) != 0)
638 return -1;
639
640 /*****************************************************************************
641 * *
642 * Allocate storage to be managed by the abstract data type. *
643 * *
644 *****************************************************************************/
645
646 if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
647 return -1;
648
649 /*****************************************************************************
650 * *
651 * Insert the new element into the list. *
652 * *
653 *****************************************************************************/
654
655 new_element->data = (void *)data;
656
657 if (dlist_size(list) == 0) {
658
659 /**************************************************************************
660 * *
661 * Handle insertion when the list is empty. *
662 * *
663 **************************************************************************/
664
665 list->head = new_element;
666 list->head->prev = NULL;
667 list->head->next = NULL;
668 list->tail = new_element;
669
670 }
671
672
673 else {
674
675 /**************************************************************************
676 * *
677 * Handle insertion when the list is not empty. *
678 * *
679 **************************************************************************/
680
681 new_element->next = element;
682 new_element->prev = element->prev;
683
684 if (element->prev == NULL)
685 list->head = new_element;
686 else
687 element->prev->next = new_element;
688
689 element->prev = new_element;
690
691 }
692
693
694 /*****************************************************************************
695 * *
696 * Adjust the size of the list to account for the new element. *
697 * *
698 *****************************************************************************/
699
700 list->size++;
701
702 return 0;
703
704 }
705
706 /*****************************************************************************
707 * *
708 * ----------------------------- dlist_remove ----------------------------- *
709 * *
710 *****************************************************************************/
711
dlist_remove(DList * list,DListElmt * element,void ** data)712 int dlist_remove(DList *list, DListElmt *element, void **data) {
713
714 /*****************************************************************************
715 * *
716 * Do not allow a NULL element or removal from an empty list. *
717 * *
718 *****************************************************************************/
719
720 if (element == NULL || dlist_size(list) == 0)
721 return -1;
722
723 /*****************************************************************************
724 * *
725 * Remove the element from the list. *
726 * *
727 *****************************************************************************/
728
729 *data = element->data;
730
731 if (element == list->head) {
732
733 /**************************************************************************
734 * *
735 * Handle removal from the head of the list. *
736 * *
737 **************************************************************************/
738
739 list->head = element->next;
740
741 if (list->head == NULL)
742 list->tail = NULL;
743 else
744 element->next->prev = NULL;
745
746 }
747
748 else {
749
750 /**************************************************************************
751 * *
752 * Handle removal from other than the head of the list. *
753 * *
754 **************************************************************************/
755
756 element->prev->next = element->next;
757
758 if (element->next == NULL)
759 list->tail = element->prev;
760 else
761 element->next->prev = element->prev;
762
763 }
764
765 /*****************************************************************************
766 * *
767 * Free the storage allocated by the abstract data type. *
768 * *
769 *****************************************************************************/
770
771 free(element);
772
773 /*****************************************************************************
774 * *
775 * Adjust the size of the list to account for the removed element. *
776 * *
777 *****************************************************************************/
778
779 list->size--;
780
781 return 0;
782
783 }
784
dlist_ith_elmt_data(DList * list,int index)785 void *dlist_ith_elmt_data(DList *list, int index)
786 {
787 int cnt=0;
788 DListElmt *element;
789
790 if (!list || index < 0 || index > list->size-1) return(NULL);
791
792 element = list->head;
793 while (index > cnt) {
794 element = element->next; ++cnt;
795 }
796 return(dlist_data(element));
797 }
798