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