1 /* -*- mode: c; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2
3 /*********************************************************************
4 * Clustal Omega - Multiple sequence alignment
5 *
6 * Copyright (C) 2010 University College Dublin
7 *
8 * Clustal-Omega is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License as
10 * published by the Free Software Foundation; either version 2 of the
11 * License, or (at your option) any later version.
12 *
13 * This file is part of Clustal-Omega.
14 *
15 ********************************************************************/
16
17 /*
18 * RCS $Id: list.c 156 2010-11-18 10:52:40Z andreas $
19 *
20 * Single linked list and FIFO/Queue
21 *
22 * Based on Kyle Loudon's Mastering Algorithms with C
23 * http://oreilly.com/catalog/9781565924536
24 *
25 * Allows generic data types by using void* pointers, which works fine
26 * as long as your data is just pointers.
27 *
28 */
29
30
31 #ifdef HAVE_CONFIG_H
32 #include "config.h"
33 #endif
34
35 #include <assert.h>
36 #include <string.h> /* for memset */
37
38 #include "list.h"
39
40 #ifdef LIST_TEST
41 #include <stdio.h>
42 #include "queue.h"
43 #include "time.h"
44 #endif
45
46 /**
47 * @brief Initialise data members of a list
48 *
49 * @param[in] prList
50 * List to initialise
51 * @param[in] destroy
52 * A function to be called with pointer to data when destroying the
53 * list. NULL if in doubt, free in most other cases.
54 * Note: doxygen will always fail to parse this...
55 */
56 void
ListInit(list_t * prList,void (* destroy)(void * data))57 ListInit(list_t *prList, void (*destroy)(void *data)) {
58 prList->size = 0;
59 prList->destroy = destroy;
60 prList->head = NULL;
61 prList->tail = NULL;
62
63 return;
64 }
65 /* end of ListInit() */
66
67
68
69 /**
70 * @brief Calls user defined function to free data in list and resets
71 * the list to NULL. Call even if your destroy function is NULL.
72 *
73 * @param[in] prList
74 * The list to destroy
75 *
76 */
77 void
ListDestroy(list_t * prList)78 ListDestroy(list_t *prList) {
79 void *pvData;
80
81 while (LIST_SIZE(prList) > 0) {
82 if (0 == ListRemoveNext(prList, NULL, (void **)&pvData)
83 &&
84 NULL != prList->destroy) {
85 prList->destroy(pvData);
86 }
87 }
88 /* precaution */
89 memset(prList, 0, sizeof(list_t));
90
91 return;
92 }
93 /* end of ListDestroy() */
94
95
96
97 /**
98 *
99 * @brief Insert data next to given element
100 *
101 * @param[in] prList
102 * List into which to insert
103 * @param[in] prElement
104 * Current position/element. Element after which to insert. If NULL
105 * head is used.
106 * @param[in] pvData
107 * Pointer to data to store
108 *
109 * @return Non-zero on failure
110 */
111 int
ListInsertNext(list_t * prList,list_elem_t * prElement,const void * pvData)112 ListInsertNext(list_t *prList, list_elem_t *prElement, const void *pvData)
113 {
114 list_elem_t *prNewElement;
115
116 if (NULL == (prNewElement = (list_elem_t *) malloc(sizeof(list_elem_t))))
117 return -1;
118
119 prNewElement->data = (void *)pvData;
120
121 if (NULL == prElement) {
122 /* insertion at head */
123 if (LIST_SIZE(prList) == 0)
124 prList->tail = prNewElement;
125 prNewElement->next = prList->head;
126 prList->head = prNewElement;
127
128 } else {
129 /* insert somewhere other than at head */
130 if (NULL == prElement->next)
131 prList->tail = prNewElement;
132 prNewElement->next = prElement->next;
133 prElement->next = prNewElement;
134 }
135
136 prList->size++;
137
138 return 0;
139 }
140 /* end of ListInsertNext() */
141
142
143
144 /**
145 * @brief Remove next element from current element/position.
146 *
147 * @param[in] prList
148 * List from which an element is to be removed.
149 * @param[in] prElement
150 * Current element/position. Next item will be removed. If NULL head
151 * is used.
152 * @param[out] pvData_p
153 * Will be pointed to removed elements data.
154 *
155 * @return Non-zero on failure
156 */
157 int
ListRemoveNext(list_t * prList,list_elem_t * prElement,void ** pvData_p)158 ListRemoveNext(list_t *prList, list_elem_t *prElement, void **pvData_p)
159 {
160 list_elem_t *prOldElement;
161
162 if (0 == LIST_SIZE(prList))
163 return -1;
164
165 if (NULL == prElement) {
166 /* handle removal from the head of the list */
167 *pvData_p = prList->head->data;
168 prOldElement = prList->head;
169 prList->head = prList->head->next;
170 if (1 == LIST_SIZE(prList))
171 prList->tail = NULL;
172
173 } else {
174 /* handle removal from somewhere other than the head */
175 if (NULL == prElement->next)
176 return -1;
177
178 *pvData_p = prElement->next->data;
179 prOldElement = prElement->next;
180 prElement->next = prElement->next->next;
181
182 if (NULL == prElement->next)
183 prList->tail = prElement;
184 }
185
186 free(prOldElement);
187
188 prList->size--;
189
190 return 0;
191 }
192 /* end of ListRemoveNext() */
193
194
195
196 /**
197 * @brief Insert int next to given element
198 *
199 * @param[in] prList
200 * List into which to insert
201 * @param[in] prElement
202 * Current position/element. Element after which to insert. If NULL
203 * head is used.
204 * @param[in] data
205 * int to store
206 *
207 * @return Non-zero on failure
208 *
209 */
210 int
IntListInsertNext(list_t * prList,list_elem_t * prElement,const int data)211 IntListInsertNext(list_t *prList, list_elem_t *prElement, const int data)
212 {
213 int *piInt;
214
215 if (NULL == (piInt = malloc(sizeof(int)))) {
216 return -1;
217 }
218 *piInt = data;
219
220 return ListInsertNext(prList, prElement, piInt);
221 }
222 /* end if IntListInsertNext() */
223
224
225 /**
226 * @brief Remove next element from current element/position.
227 *
228 * @param[in] prList
229 * List from which an element is to be removed.
230 * @param[in] prElement
231 * Current element/position. Next item will be removed. If NULL head
232 * is used.
233 * @param[out] iData_p
234 * Will be pointed to removed elements data.
235 *
236 * @return Non-zero on failure
237 *
238 */
239 int
IntListRemoveNext(list_t * prList,list_elem_t * prElement,int * iData_p)240 IntListRemoveNext(list_t *prList, list_elem_t *prElement, int *iData_p)
241 {
242 int *piData;
243 int res;
244 res = ListRemoveNext(prList, prElement, (void **)&piData);
245 *iData_p = *piData;
246 prList->destroy(piData);
247 return res;
248 }
249 /* end of IntListRemoveNext */
250
251
252
253
254 #ifdef LIST_TEST
255 /* gcc list.c -o list_test -ansi -Wall -DLIST_TEST */
256
main(int argc,char ** argv)257 int main(int argc, char **argv)
258 {
259
260 int i;
261 list_t *mylist;
262 int_list_t *myintlist;
263 queue_t *myqueue;
264 int_queue_t *myintqueue;
265 int res;
266
267 int iSeed = (int)time(NULL);
268 srand((unsigned int)iSeed);
269
270 printf("%s", "list test! also delete #include!\n");
271
272
273 mylist = malloc(sizeof(list_t));
274 ListInit(mylist, NULL);
275
276 printf("LIST test\n");
277
278 for (i=0; i<argc; i++) {
279 res = LIST_APPEND(mylist, argv[i]);
280 printf("LIST Result for appending '%s' was %d\n", argv[i], res);
281 }
282
283 while (LIST_SIZE(mylist)) {
284 char *argv_ptr;
285 if (ListRemoveNext(mylist, NULL, (void **)&argv_ptr))
286 perror("ListRemoveNext() failed");
287 printf("LIST Popped %s\n", argv_ptr);
288 }
289 printf("LIST %s", "No more elements to pop");
290
291 /* could become list_free */
292 ListDestroy(mylist);
293 free(mylist);
294
295
296
297
298 myintlist = malloc(sizeof(list_t));
299 INT_LIST_INIT(myintlist);
300
301 printf("\n");
302 printf("%s", "INT_LIST test");
303
304 for (i=0; i<argc; i++) {
305 int data = 666-i;
306 res = INT_LIST_APPEND(myintlist, data);
307 printf("INT_LIST Result for appending '%d' was %d\n", data, res);
308 }
309
310 while (INT_LIST_SIZE(myintlist)) {
311 int data;
312 if (IntListRemoveNext(myintlist, NULL, &data))
313 perror("ListRemoveNext() failed\n");
314 printf("INT_LIST Popped %d\n", data);
315 }
316 printf("INT_LIST %s\n", "No more elements to pop");
317
318 /* could become list_free */
319 INT_LIST_DESTROY(myintlist);
320 free(myintlist);
321
322
323
324
325
326 myqueue = malloc(sizeof(queue_t));
327 QUEUE_INIT(myqueue, NULL);
328
329 printf("\n");
330 printf("%s", "QUEUE test\n");
331
332 for (i=0; i<argc; i++) {
333 res = QUEUE_PUSH(myqueue, argv[i]);
334 printf("QUEUE Result for pushing '%s' was %d\n", argv[i], res);
335 }
336
337 while (! QUEUE_EMPTY(myqueue)) {
338 char *argv_ptr;
339 if (QUEUE_POP(myqueue, (void **)&argv_ptr))
340 perror("QUEUE_POP() failed\n");
341 printf("QUEUE Popped %s\n", argv_ptr);
342 }
343 printf("QUEUE %s\n", "QUEUE No more elements to pop");
344
345 /* could become list_free */
346 QUEUE_DESTROY(myqueue);
347 free(myqueue);
348
349
350
351
352 myintqueue = malloc(sizeof(queue_t));
353 INT_QUEUE_INIT(myintqueue);
354
355 printf("\n");
356 printf("%s\n", "INT_QUEUE test");
357
358 for (i=0; i<argc; i++) {
359 res = INT_QUEUE_PUSH(myintqueue, i);
360 printf("INT_QUEUE Result for appending '%d' was %d\n", i, res);
361 }
362
363 while (! INT_QUEUE_EMPTY(myintqueue)) {
364 int data;
365 int rand_data;
366 if (INT_QUEUE_POP(myintqueue, &data))
367 perror("INT_QUEUE_POP() failed\n");
368 printf("INT_QUEUE Popped %d\n", data);
369
370 rand_data = (int)( 10.0 * rand() / ( RAND_MAX+1.0));
371 if (! (rand_data%3)) {
372 res = INT_QUEUE_PUSH(myintqueue, rand_data);
373 printf("INT_QUEUE Result for pushing random number '%d' was %d\n", rand_data, res);
374 }
375 }
376 printf("INT_QUEUE %s\n", "INT_QUEUE No more elements to pop");
377
378 /* could become list_free */
379 INT_QUEUE_DESTROY(myintqueue);
380 free(myintqueue);
381
382
383 exit(0);
384 }
385
386 #endif
387
388
389
390