1 /* -*- mode: c; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
3 /*********************************************************************
4 * Clustal Omega - Multiple sequence alignment
6 * Copyright (C) 2010 University College Dublin
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.
13 * This file is part of Clustal-Omega.
15 ********************************************************************/
18 * RCS $Id: list.c 156 2010-11-18 10:52:40Z andreas $
20 * Single linked list and FIFO/Queue
22 * Based on Kyle Loudon's Mastering Algorithms with C
23 * http://oreilly.com/catalog/9781565924536
25 * Allows generic data types by using void* pointers, which works fine
26 * as long as your data is just pointers.
36 #include <string.h> /* for memset */
47 * @brief Initialise data members of a list
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...
57 ListInit(list_t *prList, void (*destroy)(void *data)) {
59 prList->destroy = destroy;
65 /* end of ListInit() */
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.
78 ListDestroy(list_t *prList) {
81 while (LIST_SIZE(prList) > 0) {
82 if (0 == ListRemoveNext(prList, NULL, (void **)&pvData)
84 NULL != prList->destroy) {
85 prList->destroy(pvData);
89 memset(prList, 0, sizeof(list_t));
93 /* end of ListDestroy() */
99 * @brief Insert data next to given element
102 * List into which to insert
103 * @param[in] prElement
104 * Current position/element. Element after which to insert. If NULL
107 * Pointer to data to store
109 * @return Non-zero on failure
112 ListInsertNext(list_t *prList, list_elem_t *prElement, const void *pvData)
114 list_elem_t *prNewElement;
116 if (NULL == (prNewElement = (list_elem_t *) malloc(sizeof(list_elem_t))))
119 prNewElement->data = (void *)pvData;
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;
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;
140 /* end of ListInsertNext() */
145 * @brief Remove next element from current element/position.
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
152 * @param[out] pvData_p
153 * Will be pointed to removed elements data.
155 * @return Non-zero on failure
158 ListRemoveNext(list_t *prList, list_elem_t *prElement, void **pvData_p)
160 list_elem_t *prOldElement;
162 if (0 == LIST_SIZE(prList))
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))
174 /* handle removal from somewhere other than the head */
175 if (NULL == prElement->next)
178 *pvData_p = prElement->next->data;
179 prOldElement = prElement->next;
180 prElement->next = prElement->next->next;
182 if (NULL == prElement->next)
183 prList->tail = prElement;
192 /* end of ListRemoveNext() */
197 * @brief Insert int next to given element
200 * List into which to insert
201 * @param[in] prElement
202 * Current position/element. Element after which to insert. If NULL
207 * @return Non-zero on failure
211 IntListInsertNext(list_t *prList, list_elem_t *prElement, const int data)
215 if (NULL == (piInt = malloc(sizeof(int)))) {
220 return ListInsertNext(prList, prElement, piInt);
222 /* end if IntListInsertNext() */
226 * @brief Remove next element from current element/position.
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
233 * @param[out] iData_p
234 * Will be pointed to removed elements data.
236 * @return Non-zero on failure
240 IntListRemoveNext(list_t *prList, list_elem_t *prElement, int *iData_p)
244 res = ListRemoveNext(prList, prElement, (void **)&piData);
246 prList->destroy(piData);
249 /* end of IntListRemoveNext */
255 /* gcc list.c -o list_test -ansi -Wall -DLIST_TEST */
257 int main(int argc, char **argv)
262 int_list_t *myintlist;
264 int_queue_t *myintqueue;
267 int iSeed = (int)time(NULL);
268 srand((unsigned int)iSeed);
270 printf("%s", "list test! also delete #include!\n");
273 mylist = malloc(sizeof(list_t));
274 ListInit(mylist, NULL);
276 printf("LIST test\n");
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);
283 while (LIST_SIZE(mylist)) {
285 if (ListRemoveNext(mylist, NULL, (void **)&argv_ptr))
286 perror("ListRemoveNext() failed");
287 printf("LIST Popped %s\n", argv_ptr);
289 printf("LIST %s", "No more elements to pop");
291 /* could become list_free */
298 myintlist = malloc(sizeof(list_t));
299 INT_LIST_INIT(myintlist);
302 printf("%s", "INT_LIST test");
304 for (i=0; i<argc; i++) {
306 res = INT_LIST_APPEND(myintlist, data);
307 printf("INT_LIST Result for appending '%d' was %d\n", data, res);
310 while (INT_LIST_SIZE(myintlist)) {
312 if (IntListRemoveNext(myintlist, NULL, &data))
313 perror("ListRemoveNext() failed\n");
314 printf("INT_LIST Popped %d\n", data);
316 printf("INT_LIST %s\n", "No more elements to pop");
318 /* could become list_free */
319 INT_LIST_DESTROY(myintlist);
326 myqueue = malloc(sizeof(queue_t));
327 QUEUE_INIT(myqueue, NULL);
330 printf("%s", "QUEUE test\n");
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);
337 while (! QUEUE_EMPTY(myqueue)) {
339 if (QUEUE_POP(myqueue, (void **)&argv_ptr))
340 perror("QUEUE_POP() failed\n");
341 printf("QUEUE Popped %s\n", argv_ptr);
343 printf("QUEUE %s\n", "QUEUE No more elements to pop");
345 /* could become list_free */
346 QUEUE_DESTROY(myqueue);
352 myintqueue = malloc(sizeof(queue_t));
353 INT_QUEUE_INIT(myintqueue);
356 printf("%s\n", "INT_QUEUE test");
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);
363 while (! INT_QUEUE_EMPTY(myintqueue)) {
366 if (INT_QUEUE_POP(myintqueue, &data))
367 perror("INT_QUEUE_POP() failed\n");
368 printf("INT_QUEUE Popped %d\n", data);
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);
376 printf("INT_QUEUE %s\n", "INT_QUEUE No more elements to pop");
378 /* could become list_free */
379 INT_QUEUE_DESTROY(myintqueue);