lists.c

   1 /*\r
   2  * lists.c -- Functions to implement a double linked list\r
   3  * XBoard $Id: lists.c,v 2.1 2003/10/27 19:21:00 mann Exp $\r
   4  *\r
   5  * Copyright 1995 Free Software Foundation, Inc.\r
   6  *\r
   7  * ------------------------------------------------------------------------\r
   8  * This program is free software; you can redistribute it and/or modify\r
   9  * it under the terms of the GNU General Public License as published by\r
  10  * the Free Software Foundation; either version 2 of the License, or\r
  11  * (at your option) any later version.\r
  12  *\r
  13  * This program is distributed in the hope that it will be useful,\r
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  16  * GNU General Public License for more details.\r
  17  *\r
  18  * You should have received a copy of the GNU General Public License\r
  19  * along with this program; if not, write to the Free Software\r
  20  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111 USA.\r
  21  * ------------------------------------------------------------------------\r
  22  *\r
  23  * This file could well be a part of backend.c, but I prefer it this\r
  24  * way.\r
  25  */\r
  26 \r
  27 #include "config.h"\r
  28 \r
  29 #include <stdio.h>\r
  30 #if STDC_HEADERS\r
  31 # include <stdlib.h>\r
  32 #endif /* not STDC_HEADERS */\r
  33 \r
  34 #include "common.h"\r
  35 #include "lists.h"\r
  36 \r
  37 \r
  38 \r
  39 /* Check, if List l is empty; returns TRUE, if it is, FALSE\r
  40  * otherwise.\r
  41  */\r
  42 int ListEmpty(l)\r
  43     List *l;\r
  44 {\r
  45     return(l->head == (ListNode *) &l->tail);\r
  46 }\r
  47 \r
  48 \r
  49 /* Initialize a list. Must be executed before list is used.\r
  50  */\r
  51 void ListNew(l)\r
  52     List *l;\r
  53 {\r
  54     l->head = (ListNode *) &l->tail;\r
  55     l->tail = NULL;\r
  56     l->tailPred = (ListNode *) l;\r
  57 }\r
  58 \r
  59 \r
  60 /* Remove node n from the list it is inside.\r
  61  */\r
  62 void ListRemove(n)\r
  63     ListNode *n;\r
  64 {\r
  65     if (n->succ != NULL) {  /*  Be safe  */\r
  66         n->pred->succ = n->succ;\r
  67         n->succ->pred = n->pred;\r
  68         n->succ = NULL;     /*  Mark node as no longer being member */\r
  69         n->pred = NULL;     /*  of a list.                          */\r
  70     }\r
  71 }\r
  72 \r
  73 \r
  74 /* Delete node n.\r
  75  */\r
  76 void ListNodeFree(n)\r
  77     ListNode *n;\r
  78 {\r
  79     if (n) {\r
  80         ListRemove(n);\r
  81         free(n);\r
  82     }\r
  83 }\r
  84 \r
  85 \r
  86 /* Create a list node with size s. Returns NULL, if out of memory.\r
  87  */\r
  88 ListNode *ListNodeCreate(s)\r
  89     size_t s;\r
  90 {\r
  91     ListNode *n;\r
  92 \r
  93     if ((n = (ListNode*) malloc(s))) {\r
  94         n->succ = NULL; /*  Mark node as not being member of a list.    */\r
  95         n->pred = NULL;\r
  96     }\r
  97     return(n);\r
  98 }\r
  99 \r
 100 \r
 101 /* Insert node n into the list of node m after m.\r
 102  */\r
 103 void ListInsert(m, n)\r
 104     ListNode *m, *n;\r
 105 {\r
 106     n->succ = m->succ;\r
 107     n->pred = m;\r
 108     m->succ = n;\r
 109     n->succ->pred = n;\r
 110 }\r
 111 \r
 112 \r
 113 /* Add node n to the head of list l.\r
 114  */\r
 115 void ListAddHead(l, n)\r
 116     List *l;\r
 117     ListNode *n;\r
 118 {\r
 119     ListInsert((ListNode *) &l->head, n);\r
 120 }\r
 121 \r
 122 \r
 123 /* Add node n to the tail of list l.\r
 124  */\r
 125 void ListAddTail(l, n)\r
 126     List *l;\r
 127     ListNode *n;\r
 128 {\r
 129     ListInsert((ListNode *) l->tailPred, n);\r
 130 }\r
 131 \r
 132 \r
 133 /* Return element with number n of list l. (NULL, if n doesn't exist.)\r
 134  * Counting starts with 0.\r
 135  */\r
 136 ListNode *ListElem(l, n)\r
 137     List *l;\r
 138     int n;\r
 139 {\r
 140     ListNode *ln;\r
 141 \r
 142     for (ln = l->head;  ln->succ;  ln = ln->succ) {\r
 143         if (!n--) {\r
 144             return (ln);\r
 145         }\r
 146     }\r
 147 \r
 148     return(NULL);\r
 149 }\r