UYS  0.1
Useful Yet Simple (C libraries collection)
 All Data Structures Files Functions Typedefs Macros Pages
list.c
1  /*****************************************************************
2  *
3  * list.c
4  *
5  * Source: "Mastering Algorithms with C" (1999, p. 56) by Kyle Loudon,
6  * published by O'Reilly & Associates.
7  *
8  * This source can be freely used, adapted, and redistributed in source or
9  * binary form, so long as an acknowledgment appears in derived source files.
10  * The citation should list that the code comes from the book "Mastering
11  * Algorithms with C" by Kyle Loudon, published by O'Reilly & Associates.
12  * This code is under copyright and cannot be included in any other book,
13  * publication, or educational product without permission from O'Reilly
14  * & Associates. No warranty is attached; we cannot take responsibility for
15  * errors or fitness for use.
16  *
17  *****************************************************************/
18 
19 
20 #include <stdlib.h>
21 #include <string.h>
22 
23 #include "uys_alloc.h"
24 #include "list.h"
25 
26 
27 
28 /*************************************************************//**
29  * list_init
30  ****************************************************************/
31 void list_init(List *list, void (*destroy)(void *data)) {
32 
33  /*****************************************************************
34  * Initialize the list.
35  ****************************************************************/
36  list->size = 0;
37  list->destroy = destroy;
38  list->head = NULL;
39  list->tail = NULL;
40 
41  return;
42 }
43 
44 
45 /*****************************************************************
46  * list_destroy
47  ****************************************************************/
48 void list_destroy(List *list) {
49  void *data;
50 
51  /*****************************************************************
52  * Remove each element
53  ****************************************************************/
54  while (list_size(list) > 0) {
55 
56  if (list_rem_next(list, NULL, (void **)&data) == 0 &&
57  list->destroy != NULL) {
58  /*****************************************************************
59  * Call a user-defined function to free dynamically allocated
60  * data.
61  ****************************************************************/
62  list->destroy(data);
63  }
64  }
65 
66  /*****************************************************************
67  * No operations are allowed now, but clear the structure as a precaution.
68  ****************************************************************/
69  memset(list, 0, sizeof(List));
70 
71  return;
72 }
73 
74 
75 /*************************************************************//**
76  * list_ins_next
77  ****************************************************************/
78 int list_ins_next(List *list, ListElmt *element, const void *data) {
79  ListElmt *new_element;
80 
81  /****************************************************************
82  * Allocate storage for the element, return -1 if it fails
83  ****************************************************************/
84  if ((new_element = (ListElmt *)uys_malloc(sizeof(ListElmt))) == NULL) {
85  return -1;
86  }
87 
88  /*****************************************************************
89  * Insert the element into the list.
90  ****************************************************************/
91  new_element->data = (void *)data;
92 
93  if (element == NULL) {
94  /*****************************************************************
95  * Handle insertion at the head of the list.
96  ****************************************************************/
97  if (list_size(list) == 0) {
98  list->tail = new_element;
99  }
100  new_element->next = list->head;
101  list->head = new_element;
102 
103  } else {
104  /*****************************************************************
105  * Handle insertion somewhere other than at the head.
106  ****************************************************************/
107  if (element->next == NULL) {
108  list->tail = new_element;
109  }
110  new_element->next = element->next;
111  element->next = new_element;
112  }
113 
114  /*****************************************************************
115  * Adjust the size of the list to account for the inserted element.
116  ****************************************************************/
117  list->size++;
118 
119  return 0;
120 }
121 
122 
123 /*************************************************************//**
124  * list_rem_next
125  ****************************************************************/
126 int list_rem_next(List *list, ListElmt *element, void **data) {
127  ListElmt *old_element;
128 
129  /*****************************************************************
130  * Do not allow removal from an empty list.
131  ****************************************************************/
132  if (list_size(list) == 0) {
133  return -1;
134  }
135  /*****************************************************************
136  * Remove the element from the list.
137  ****************************************************************/
138 
139  if (element == NULL) {
140  /*****************************************************************
141  * Handle removal from the head of the list.
142  ****************************************************************/
143  *data = list->head->data;
144  old_element = list->head;
145  list->head = list->head->next;
146  if (list_size(list) == 1)
147  list->tail = NULL;
148  }
149 
150  else {
151  /*****************************************************************
152  * Handle removal from somewhere other than the head.
153  ****************************************************************/
154  if (element->next == NULL) {
155  return -1;
156  }
157  *data = element->next->data;
158  old_element = element->next;
159  element->next = element->next->next;
160  if (element->next == NULL) {
161  list->tail = element;
162  }
163  }
164 
165  /*****************************************************************
166  * Free the storage allocated by the abstract datatype.
167  ****************************************************************/
168  free(old_element);
169 
170  /*****************************************************************
171  * Adjust the size of the list to account for the removed element.
172  ****************************************************************/
173  list->size--;
174 
175  return 0;
176 }
int list_ins_next(List *list, ListElmt *element, const void *data)
Inserts an element just after element on list.
Definition: list.c:78
Interface for the linked list implementation.
void list_destroy(List *list)
Destroys the linked list specified by list.
Definition: list.c:48
void list_init(List *list, void(*destroy)(void *data))
Initializes the linked list specified by list.
Definition: list.c:31
int list_rem_next(List *list, ListElmt *element, void **data)
Removes the element just after element on list.
Definition: list.c:126
#define list_size(list)
evaluates to the number of elements on list.
Definition: list.h:166
structure for linked lists.
Definition: list.h:56
structure for linked list elements.
Definition: list.h:43