--- /dev/null
+/* -*- mode: c; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
+
+/*********************************************************************
+ * Clustal Omega - Multiple sequence alignment
+ *
+ * Copyright (C) 2010 University College Dublin
+ *
+ * Clustal-Omega is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * This file is part of Clustal-Omega.
+ *
+ ********************************************************************/
+
+/*
+ * RCS $Id: list.c 156 2010-11-18 10:52:40Z andreas $
+ *
+ * Single linked list and FIFO/Queue
+ *
+ * Based on Kyle Loudon's Mastering Algorithms with C
+ * http://oreilly.com/catalog/9781565924536
+ *
+ * Allows generic data types by using void* pointers, which works fine
+ * as long as your data is just pointers.
+ *
+ */
+
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <assert.h>
+#include <string.h> /* for memset */
+
+#include "list.h"
+
+#ifdef LIST_TEST
+#include <stdio.h>
+#include "queue.h"
+#include "time.h"
+#endif
+
+/**
+ * @brief Initialise data members of a list
+ *
+ * @param[in] prList
+ * List to initialise
+ * @param[in] destroy
+ * A function to be called with pointer to data when destroying the
+ * list. NULL if in doubt, free in most other cases.
+ * Note: doxygen will always fail to parse this...
+ */
+void
+ListInit(list_t *prList, void (*destroy)(void *data)) {
+ prList->size = 0;
+ prList->destroy = destroy;
+ prList->head = NULL;
+ prList->tail = NULL;
+
+ return;
+}
+/* end of ListInit() */
+
+
+
+/**
+ * @brief Calls user defined function to free data in list and resets
+ * the list to NULL. Call even if your destroy function is NULL.
+ *
+ * @param[in] prList
+ * The list to destroy
+ *
+ */
+void
+ListDestroy(list_t *prList) {
+ void *pvData;
+
+ while (LIST_SIZE(prList) > 0) {
+ if (0 == ListRemoveNext(prList, NULL, (void **)&pvData)
+ &&
+ NULL != prList->destroy) {
+ prList->destroy(pvData);
+ }
+ }
+ /* precaution */
+ memset(prList, 0, sizeof(list_t));
+
+ return;
+}
+/* end of ListDestroy() */
+
+
+
+/**
+ *
+ * @brief Insert data next to given element
+ *
+ * @param[in] prList
+ * List into which to insert
+ * @param[in] prElement
+ * Current position/element. Element after which to insert. If NULL
+ * head is used.
+ * @param[in] pvData
+ * Pointer to data to store
+ *
+ * @return Non-zero on failure
+ */
+int
+ListInsertNext(list_t *prList, list_elem_t *prElement, const void *pvData)
+{
+ list_elem_t *prNewElement;
+
+ if (NULL == (prNewElement = (list_elem_t *) malloc(sizeof(list_elem_t))))
+ return -1;
+
+ prNewElement->data = (void *)pvData;
+
+ if (NULL == prElement) {
+ /* insertion at head */
+ if (LIST_SIZE(prList) == 0)
+ prList->tail = prNewElement;
+ prNewElement->next = prList->head;
+ prList->head = prNewElement;
+
+ } else {
+ /* insert somewhere other than at head */
+ if (NULL == prElement->next)
+ prList->tail = prNewElement;
+ prNewElement->next = prElement->next;
+ prElement->next = prNewElement;
+ }
+
+ prList->size++;
+
+ return 0;
+}
+/* end of ListInsertNext() */
+
+
+
+/**
+ * @brief Remove next element from current element/position.
+ *
+ * @param[in] prList
+ * List from which an element is to be removed.
+ * @param[in] prElement
+ * Current element/position. Next item will be removed. If NULL head
+ * is used.
+ * @param[out] pvData_p
+ * Will be pointed to removed elements data.
+ *
+ * @return Non-zero on failure
+ */
+int
+ListRemoveNext(list_t *prList, list_elem_t *prElement, void **pvData_p)
+{
+ list_elem_t *prOldElement;
+
+ if (0 == LIST_SIZE(prList))
+ return -1;
+
+ if (NULL == prElement) {
+ /* handle removal from the head of the list */
+ *pvData_p = prList->head->data;
+ prOldElement = prList->head;
+ prList->head = prList->head->next;
+ if (1 == LIST_SIZE(prList))
+ prList->tail = NULL;
+
+ } else {
+ /* handle removal from somewhere other than the head */
+ if (NULL == prElement->next)
+ return -1;
+
+ *pvData_p = prElement->next->data;
+ prOldElement = prElement->next;
+ prElement->next = prElement->next->next;
+
+ if (NULL == prElement->next)
+ prList->tail = prElement;
+ }
+
+ free(prOldElement);
+
+ prList->size--;
+
+ return 0;
+}
+/* end of ListRemoveNext() */
+
+
+
+/**
+ * @brief Insert int next to given element
+ *
+ * @param[in] prList
+ * List into which to insert
+ * @param[in] prElement
+ * Current position/element. Element after which to insert. If NULL
+ * head is used.
+ * @param[in] data
+ * int to store
+ *
+ * @return Non-zero on failure
+ *
+ */
+int
+IntListInsertNext(list_t *prList, list_elem_t *prElement, const int data)
+{
+ int *piInt;
+
+ if (NULL == (piInt = malloc(sizeof(int)))) {
+ return -1;
+ }
+ *piInt = data;
+
+ return ListInsertNext(prList, prElement, piInt);
+ }
+/* end if IntListInsertNext() */
+
+
+/**
+ * @brief Remove next element from current element/position.
+ *
+ * @param[in] prList
+ * List from which an element is to be removed.
+ * @param[in] prElement
+ * Current element/position. Next item will be removed. If NULL head
+ * is used.
+ * @param[out] iData_p
+ * Will be pointed to removed elements data.
+ *
+ * @return Non-zero on failure
+ *
+ */
+int
+IntListRemoveNext(list_t *prList, list_elem_t *prElement, int *iData_p)
+{
+ int *piData;
+ int res;
+ res = ListRemoveNext(prList, prElement, (void **)&piData);
+ *iData_p = *piData;
+ prList->destroy(piData);
+ return res;
+}
+/* end of IntListRemoveNext */
+
+
+
+
+#ifdef LIST_TEST
+/* gcc list.c -o list_test -ansi -Wall -DLIST_TEST */
+
+int main(int argc, char **argv)
+{
+
+ int i;
+ list_t *mylist;
+ int_list_t *myintlist;
+ queue_t *myqueue;
+ int_queue_t *myintqueue;
+ int res;
+
+ int iSeed = (int)time(NULL);
+ srand((unsigned int)iSeed);
+
+ printf("%s", "list test! also delete #include!\n");
+
+
+ mylist = malloc(sizeof(list_t));
+ ListInit(mylist, NULL);
+
+ printf("LIST test\n");
+
+ for (i=0; i<argc; i++) {
+ res = LIST_APPEND(mylist, argv[i]);
+ printf("LIST Result for appending '%s' was %d\n", argv[i], res);
+ }
+
+ while (LIST_SIZE(mylist)) {
+ char *argv_ptr;
+ if (ListRemoveNext(mylist, NULL, (void **)&argv_ptr))
+ perror("ListRemoveNext() failed");
+ printf("LIST Popped %s\n", argv_ptr);
+ }
+ printf("LIST %s", "No more elements to pop");
+
+ /* could become list_free */
+ ListDestroy(mylist);
+ free(mylist);
+
+
+
+
+ myintlist = malloc(sizeof(list_t));
+ INT_LIST_INIT(myintlist);
+
+ printf("\n");
+ printf("%s", "INT_LIST test");
+
+ for (i=0; i<argc; i++) {
+ int data = 666-i;
+ res = INT_LIST_APPEND(myintlist, data);
+ printf("INT_LIST Result for appending '%d' was %d\n", data, res);
+ }
+
+ while (INT_LIST_SIZE(myintlist)) {
+ int data;
+ if (IntListRemoveNext(myintlist, NULL, &data))
+ perror("ListRemoveNext() failed\n");
+ printf("INT_LIST Popped %d\n", data);
+ }
+ printf("INT_LIST %s\n", "No more elements to pop");
+
+ /* could become list_free */
+ INT_LIST_DESTROY(myintlist);
+ free(myintlist);
+
+
+
+
+
+ myqueue = malloc(sizeof(queue_t));
+ QUEUE_INIT(myqueue, NULL);
+
+ printf("\n");
+ printf("%s", "QUEUE test\n");
+
+ for (i=0; i<argc; i++) {
+ res = QUEUE_PUSH(myqueue, argv[i]);
+ printf("QUEUE Result for pushing '%s' was %d\n", argv[i], res);
+ }
+
+ while (! QUEUE_EMPTY(myqueue)) {
+ char *argv_ptr;
+ if (QUEUE_POP(myqueue, (void **)&argv_ptr))
+ perror("QUEUE_POP() failed\n");
+ printf("QUEUE Popped %s\n", argv_ptr);
+ }
+ printf("QUEUE %s\n", "QUEUE No more elements to pop");
+
+ /* could become list_free */
+ QUEUE_DESTROY(myqueue);
+ free(myqueue);
+
+
+
+
+ myintqueue = malloc(sizeof(queue_t));
+ INT_QUEUE_INIT(myintqueue);
+
+ printf("\n");
+ printf("%s\n", "INT_QUEUE test");
+
+ for (i=0; i<argc; i++) {
+ res = INT_QUEUE_PUSH(myintqueue, i);
+ printf("INT_QUEUE Result for appending '%d' was %d\n", i, res);
+ }
+
+ while (! INT_QUEUE_EMPTY(myintqueue)) {
+ int data;
+ int rand_data;
+ if (INT_QUEUE_POP(myintqueue, &data))
+ perror("INT_QUEUE_POP() failed\n");
+ printf("INT_QUEUE Popped %d\n", data);
+
+ rand_data = (int)( 10.0 * rand() / ( RAND_MAX+1.0));
+ if (! (rand_data%3)) {
+ res = INT_QUEUE_PUSH(myintqueue, rand_data);
+ printf("INT_QUEUE Result for pushing random number '%d' was %d\n", rand_data, res);
+ }
+ }
+ printf("INT_QUEUE %s\n", "INT_QUEUE No more elements to pop");
+
+ /* could become list_free */
+ INT_QUEUE_DESTROY(myintqueue);
+ free(myintqueue);
+
+
+ exit(0);
+}
+
+#endif
+
+
+