src/list.c

   1 /* Generic single linked list to keep various information
   2    Copyright (C) 1993, 1994 Free Software Foundation, Inc.
   3
   4
   5 Author: Kresten Krab Thorup
   6
   7 Many modifications by Alfredo K. Kojima
   8 Some fixes and additions by Dan Pascu
   9
  10
  11 This file is part of GNU CC.
  12
  13 GNU CC is free software; you can redistribute it and/or modify
  14 it under the terms of the GNU General Public License as published by
  15 the Free Software Foundation; either version 2, or (at your option)
  16 any later version.
  17
  18 GNU CC is distributed in the hope that it will be useful,
  19 but WITHOUT ANY WARRANTY; without even the implied warranty of
  20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21 GNU General Public License for more details.
  22
  23 You should have received a copy of the GNU General Public License
  24 along with GNU CC; see the file COPYING.  If not, write to
  25 the Free Software Foundation, 59 Temple Place - Suite 330,
  26 Boston, MA 02111-1307, USA.  */
  27
  28 /* As a special exception, if you link this library with files compiled with
  29    GCC to produce an executable, this does not cause the resulting executable
  30    to be covered by the GNU General Public License. This exception does not
  31    however invalidate any other reasons why the executable file might be
  32    covered by the GNU General Public License.  */
  33
  34 #include <WUtil.h>
  35 #include "list.h"
  36 #ifdef HAVE_SYS_TYPES_H
  37 # include <sys/types.h>
  38 #endif
  39 #include <stdlib.h>
  40
  41 #define xrealloc(ptr, size) wrealloc(ptr, size)
  42
  43 /* Return a cons cell produced from (head . tail) */
  44
  45 INLINE LinkedList*
  46 list_cons(void* head, LinkedList* tail)
  47 {
  48   LinkedList* cell;
  49
  50   cell = (LinkedList*)wmalloc(sizeof(LinkedList));
  51   cell->head = head;
  52   cell->tail = tail;
  53   return cell;
  54 }
  55
  56 /* Inserts "item" in list using "compare" function to make a sorted list */
  57
  58 INLINE void
  59 list_insert_sorted(void* item, LinkedList** list, int (*compare)(void*, void*))
  60 {
  61     LinkedList *tmp, *cell;
  62
  63     cell = (LinkedList*)wmalloc(sizeof(LinkedList));
  64     cell->head = item;
  65     if ((*list == NULL) || ((*compare)((*list)->head, item) >= 0)) {
  66         cell->tail = *list;
  67         *list = cell;
  68     } else {
  69         tmp = *list;
  70         while (tmp->tail) {
  71             if ((*compare)(tmp->tail->head, item) >= 0)
  72                 break;
  73             tmp = tmp->tail;
  74         }
  75         cell->tail = tmp->tail;
  76         tmp->tail = cell;
  77     }
  78 }
  79
  80 /* Return the length of a list, list_length(NULL) returns zero */
  81
  82 INLINE int
  83 list_length(LinkedList* list)
  84 {
  85   int i = 0;
  86   while(list)
  87     {
  88       i += 1;
  89       list = list->tail;
  90     }
  91   return i;
  92 }
  93
  94 /* Return the Nth element of LIST, where N count from zero.  If N
  95    larger than the list length, NULL is returned  */
  96
  97 INLINE void*
  98 list_nth(int index, LinkedList* list)
  99 {
 100   while(index-- != 0)
 101     {
 102       if(list->tail)
 103         list = list->tail;
 104       else
 105         return 0;
 106     }
 107   return list->head;
 108 }
 109
 110 /* Remove the element at the head by replacing it by its successor */
 111
 112 #if 0
 113 INLINE void
 114 list_remove_head(LinkedList** list)
 115 {
 116   if (!*list) return;
 117   if ((*list)->tail)
 118     {
 119       LinkedList* tail = (*list)->tail; /* fetch next */
 120       *(*list) = *tail;         /* copy next to list head */
 121       free(tail);                       /* free next */
 122     }
 123   else                          /* only one element in list */
 124     {
 125       free(*list);
 126       (*list) = 0;
 127     }
 128 }
 129
 130 /* Alfredo, is there any reason for the function to be as above,
 131  * instead of the more simple version below?
 132  * The difference is that above function do a copying of the structure
 133  * unlike the below that only changes where list points.
 134  * This makes the above function twice slower, because it copies the
 135  * whole structure, which contains 2 pointers. -Dan.
 136  *
 137  * I don't know. I just copied this file from the gcc distribution
 138  * (I liked the API). One could think that the above function would
 139  * keep the pointer to the list unchanged, while the below would change
 140  * it, but since the list is passed by reference that doesn't make any
 141  * sense. -Alfredo
 142  */
 143
 144 #else
 145 INLINE void
 146 list_remove_head(LinkedList** list)
 147 {
 148   if (!*list) return;
 149
 150   {
 151       LinkedList* next = (*list)->tail; /* fetch next */
 152       free(*list);                      /* free head */
 153       *list = next;                     /* update list pointer */
 154   }
 155 }
 156 #endif
 157
 158
 159 /* Remove the element with `car' set to ELEMENT */
 160 /*
 161 INLINE void
 162 list_remove_elem(LinkedList** list, void* elem)
 163 {
 164   while (*list)
 165     {
 166       if ((*list)->head == elem)
 167         list_remove_head(list);
 168       *list = (*list ? (*list)->tail : NULL);
 169     }
 170 }*/
 171
 172 INLINE LinkedList *
 173 list_remove_elem(LinkedList* list, void* elem)
 174 {
 175     LinkedList *tmp;
 176
 177     if (list) {
 178         if (list->head == elem) {
 179             tmp = list->tail;
 180             free(list);
 181             return tmp;
 182         }
 183         list->tail = list_remove_elem(list->tail, elem);
 184         return list;
 185     }
 186     return NULL;
 187 }
 188
 189
 190 /* Return element that has ELEM as car */
 191
 192 INLINE LinkedList*
 193 list_find(LinkedList* list, void* elem)
 194 {
 195   while(list)
 196     {
 197     if (list->head == elem)
 198       return list;
 199     list = list->tail;
 200     }
 201   return NULL;
 202 }
 203
 204 /* Free list (backwards recursive) */
 205
 206 INLINE void
 207 list_free(LinkedList* list)
 208 {
 209   if(list)
 210     {
 211       list_free(list->tail);
 212       free(list);
 213     }
 214 }
 215
 216 /* Map FUNCTION over all elements in LIST */
 217
 218 INLINE void
 219 list_mapcar(LinkedList* list, void(*function)(void*))
 220 {
 221   while(list)
 222     {
 223       (*function)(list->head);
 224       list = list->tail;
 225     }
 226 }