Gitiles
Code Review Sign In
git01.mediatek.com / haproxy / 12350155a404973eba02b07d9e5b8a6315c43b49 / . / src / list.c
blob: 364ed141fe015574366088568363321dd7b3b9d0 [file] [log] [blame]
willy tarreau12350152005-12-18 01:03:27 +0100[diff] [blame^]1/*
2 This File is copied from
3
4 http://www.oreilly.com/catalog/masteralgoc/index.html
5 Mastering Algorithms with C
6 By Kyle Loudon
7 ISBN: 1-56592-453-3
8 Publishd by O'Reilly
9
10 */
11
12/*****************************************************************************
13 * *
14 * -------------------------------- list.c -------------------------------- *
15 * *
16 *****************************************************************************/
17
18#include <stdlib.h>
19#include <string.h>
20
21#include <include/list.h>
22
23/*****************************************************************************
24* *
25* ------------------------------- list_init ------------------------------ *
26* *
27*****************************************************************************/
28
29void list_init(List *list, void (*destroy)(void *data)) {
30
31 /*****************************************************************************
32 * *
33 * Initialize the list. *
34 * *
35 *****************************************************************************/
36
37 list->size = 0;
38 list->destroy = destroy;
39 list->head = NULL;
40 list->tail = NULL;
41 return;
42} /* end list_init() */
43
44/*****************************************************************************
45 * *
46 * ----------------------------- list_destroy ----------------------------- *
47 * *
48 *****************************************************************************/
49
50void list_destroy(List *list) {
51
52 void *data;
53 int rc;
54
55 /*****************************************************************************
56 * *
57 * Remove each element. *
58 * *
59 *****************************************************************************/
60
61 while (list_size(list) > 0) {
62
63 rc = list_rem_next(list, NULL, (void **)&data);
64
65 if (( rc == 0) && (list->destroy != NULL)) {
66
67 /***********************************************************************
68 * *
69 * Call a user-defined function to free dynamically allocated data. *
70 * *
71 ***********************************************************************/
72
73 list->destroy(data);
74 }/* end if() */
75 }/* end while() */
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 return;
85} /* void list_destroy(List *list) */
86
87/*****************************************************************************
88 * *
89 * ----------------------------- list_ins_next ---------------------------- *
90 * *
91 *****************************************************************************/
92
93int list_ins_next(List *list, ListElmt *element, const void *data) {
94
95 ListElmt *new_element;
96
97 /*****************************************************************************
98 * *
99 * Allocate storage for the element. *
100 * *
101 *****************************************************************************/
102
103 if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
104 return -1;
105
106 /*****************************************************************************
107 * *
108 * Insert the element into the list. *
109 * *
110 *****************************************************************************/
111
112 new_element->data = (void *)data;
113
114 if (element == NULL) {
115
116 /**************************************************************************
117 * *
118 * Handle insertion at the head of the list. *
119 * *
120 **************************************************************************/
121
122 if (list_size(list) == 0)
123 list->tail = new_element;
124
125 new_element->next = list->head;
126 list->head = new_element;
127 }/* end if (element == NULL) */
128 else {
129
130 /**************************************************************************
131 * *
132 * Handle insertion somewhere other than at the head. *
133 * *
134 **************************************************************************/
135
136 if (element->next == NULL)
137 list->tail = new_element;
138
139 new_element->next = element->next;
140 element->next = new_element;
141 }/* end else */
142
143 /*****************************************************************************
144 * *
145 * Adjust the size of the list to account for the inserted element. *
146 * *
147 *****************************************************************************/
148
149 list->size++;
150 return 0;
151} /* end list_ins_next() */
152
153/*****************************************************************************
154 * *
155 * ----------------------------- list_rem_next ---------------------------- *
156 * *
157 *****************************************************************************/
158
159int list_rem_next(List *list, ListElmt *element, void **data) {
160
161 ListElmt *old_element;
162
163 /*****************************************************************************
164 * *
165 * Do not allow removal from an empty list. *
166 * *
167 *****************************************************************************/
168
169 if (list_size(list) == 0)
170 return -1;
171
172 /*****************************************************************************
173 * *
174 * Remove the element from the list. *
175 * *
176 *****************************************************************************/
177
178 if (element == NULL) {
179
180 /**************************************************************************
181 * *
182 * Handle removal from the head of the list. *
183 * *
184 **************************************************************************/
185
186 *data = list->head->data;
187 old_element = list->head;
188 list->head = list->head->next;
189
190 if (list_size(list) == 1)
191 list->tail = NULL;
192 }/* end if (element == NULL) */
193 else {
194
195 /**************************************************************************
196 * *
197 * Handle removal from somewhere other than the head. *
198 * *
199 **************************************************************************/
200
201 if (element->next == NULL)
202 return -1;
203
204 *data = element->next->data;
205 old_element = element->next;
206 element->next = element->next->next;
207
208 if (element->next == NULL)
209 list->tail = element;
210 }/* end else */
211
212 /*****************************************************************************
213 * *
214 * Free the storage allocated by the abstract data type. *
215 * *
216 *****************************************************************************/
217
218 free(old_element);
219
220 /*****************************************************************************
221 * *
222 * Adjust the size of the list to account for the removed element. *
223 * *
224 *****************************************************************************/
225
226 list->size--;
227 return 0;
228}