nsz Git - libfirm/blob - ir/adt/plist.h

   1 /*
   2  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @author Kimon Hoffmann
  23  * @date   14.07.2005
  24  * @cvs-id $Id$
  25  * @summary Simple, non circular, double linked pointer list.
  26  *          Created because the properties of the standard circular list were
  27  *          not very well suited for the interference graph implementation.
  28  *          This list uses an obstack and a free-list to efficiently manage its
  29  *          elements.
  30  * @note    Until now the code is entirely untested so it probably contains
  31  *          plenty of errors. (Matze: Is this still true, the code seems to be
  32  *          used at some places....)
  33  */
  34 #ifndef FIRM_ADT_PLIST_H
  35 #define FIRM_ADT_PLIST_H
  36
  37 #include <stddef.h>
  38 #include "obst.h"
  39
  40 typedef struct _plist_element plist_element_t;
  41 typedef struct _plist plist_t;
  42
  43 /**
  44  * The plist data type.
  45  */
  46 struct _plist {
  47         /**
  48          * The obstack used for all allocations.
  49          */
  50         struct obstack *obst;
  51
  52         /* Set to 1 if plist uses a foreign obstack  */
  53         unsigned foreign_obstack : 1;
  54
  55         /**
  56          * First element in the list.
  57          */
  58         plist_element_t *first_element;
  59
  60         /**
  61          * Last element in the list.
  62          */
  63         plist_element_t *last_element;
  64
  65         /**
  66          * Current number of elements in the list.
  67          */
  68         int element_count;
  69
  70         /**
  71          * First element in the free list.
  72          * Please note that the free list is a single linked list and all back
  73          * references are invalid.
  74          */
  75         plist_element_t* first_free_element;
  76 };
  77
  78 /**
  79  * An element in the pointer list.
  80  */
  81 struct _plist_element {
  82         plist_element_t *next;
  83         plist_element_t *prev;
  84         void *data;
  85 };
  86
  87 /**
  88  * Creates a new pointer list and initializes it.
  89  * @return The newly created pointer list.
  90  */
  91 plist_t *plist_new(void);
  92
  93 /**
  94  * Creates a new pointer list and initializes it.
  95  * Uses the given obstack instead of creating one.
  96  * @param obst  The obstack to use
  97  * @return The newly created pointer list.
  98  */
  99 plist_t *plist_obstack_new(struct obstack *obst);
 100
 101 /**
 102  * Frees the passed pointer list.
 103  * After a call to this function all references to the list and any of
 104  * its elements are invalid.
 105  */
 106 void plist_free(plist_t *list);
 107
 108 /**
 109  * Returns the number of elements in a pointer list.
 110  * @param list the pointer list
 111  * @return The number of elements in a pointer list.
 112  */
 113 #define plist_count(list) \
 114         ((list)->element_count)
 115
 116 /**
 117  * Inserts an element at the back of a pointer list.
 118  * @param list the pointer list to append the new element to.
 119  * @param value the element value to append.
 120  */
 121 void plist_insert_back(plist_t *list, void *value);
 122
 123 /**
 124  * Inserts an element at the front of a pointer list.
 125  * @param list the pointer list to prepend the new element to.
 126  * @param value the element value to prepend.
 127  */
 128 void plist_insert_front(plist_t *list, void *value);
 129
 130 /**
 131  * Inserts an element into a pointer list before the specified element,
 132  * which must be non null.
 133  * @param list the pointer list to insert the new element into.
 134  * @param element the list element before which the new element should
 135  *              be inserted. This element must be a part of @p list.
 136  * @param value the element value to insert.
 137  */
 138 void plist_insert_before(plist_t *list, plist_element_t *element, void *value);
 139
 140 /**
 141  * Inserts an element into a pointer list after the specified element,
 142  * which must be non null.
 143  * @param list the pointer list to insert the new element into.
 144  * @param element the list element after which the new element should
 145  *              be inserted. This element must be a part of @p list.
 146  * @param value the element value to insert.
 147  */
 148 void plist_insert_after(plist_t *list, plist_element_t *element, void *value);
 149
 150 /**
 151  * Checks if list has an element with the given data pointer.
 152  * @param list   the list to check
 153  * @param value  the data pointer to look for
 154  * @return 1 if element with data pointer found, 0 otherwise
 155  */
 156 int plist_has_value(plist_t *list, void *value);
 157
 158 /**
 159  * Tries to find list element associated to the given data pointer.
 160  * @param list   the list to check
 161  * @param value  the data pointer to look for
 162  * @return The first list element associated to data pointer if found, NULL otherwise
 163  */
 164 plist_element_t *plist_find_value(plist_t *list, void *value);
 165
 166 /**
 167  * Erases the specified element from the pointer list.
 168  * @param list the pointer list from which the element should be erased.
 169  * @param element the list element to erase. This element must be a part
 170  *              of @p list.
 171  */
 172 void plist_erase(plist_t *list, plist_element_t *element);
 173
 174 /**
 175  * Erases all elements from the specified pointer list.
 176  * @param list the pointer list that should be cleared.
 177  */
 178 void plist_clear(plist_t *list);
 179
 180 /**
 181  * Returns the first element of a pointer list.
 182  * @param list the pointer list to iterate
 183  * @return a pointer to the element or NULL if the list is empty
 184  */
 185  #define plist_first(list) \
 186         ((list)->first_element)
 187
 188 /**
 189  * Returns the last element of a pointer list.
 190  * @param list the pointer list to iterate
 191  * @return a pointer to the element or NULL if the list is empty
 192  */
 193  #define plist_last(list) \
 194         ((list)->last_element)
 195
 196 /**
 197  * Checks whether a pointer list element has a successor or not.
 198  * @param element the list element that should be queried for existence
 199  *              of a successor.
 200  * @return TRUE if @p element has a successor, otherwise FALSE.
 201  */
 202 #define plist_element_has_next(element) \
 203         ((element)->next != NULL)
 204
 205 /**
 206  * Checks whether a pointer list element has a predecessor or not.
 207  * @param element the list element that should be queried for existence
 208  *              of a predecessor.
 209  * @return TRUE if @p element has a successor, otherwise FALSE.
 210  */
 211 #define plist_element_has_prev(element) \
 212         ((element)->prev != NULL)
 213
 214 /**
 215  * Gets the successor of the passed list element.
 216  * @param element the list element to return the successor of.
 217  * @return The successor of @p element or NULL if @p element is the last
 218  *              element in the sequence.
 219  */
 220 #define plist_element_get_next(element) \
 221         ((element)->next)
 222
 223 /**
 224  * Gets the predecessor of the passed list element.
 225  * @param element the list element to return the predecessor of.
 226  * @return The predecessor of @p element or NULL if @p element is the last
 227  *              element in the sequence.
 228  */
 229 #define plist_element_get_prev(element) \
 230         ((element)->prev)
 231
 232 /**
 233  * Gets the value stored in the passed list element.
 234  * @param element the list element to return the value of.
 235  * @return The value stored in @p element.
 236  */
 237 #define plist_element_get_value(element) \
 238         ((element)->data)
 239
 240 /**
 241  * Convenience macro to iterate over a plist.
 242  */
 243 #define foreach_plist(list, el) \
 244         for (el = plist_first(list); el; el = plist_element_get_next(el))
 245
 246 #endif /*_PLIST_H_*/