binaries/src/clustalo/src/clustal/list.c

   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
  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
  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
 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
 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
 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
 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
 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