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

   1 /*
   2  * Copyright (C) 1995-2008 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  * @brief   Simple, non circular, double linked pointer list.
  25  *          Created because the properties of the standard circular list were
  26  *          not very well suited for the interference graph implementation.
  27  *          This list uses an obstack and a free-list to efficiently manage its
  28  *          elements.
  29  * @deprecated
  30  */
  31 #ifndef FIRM_ADT_PLIST_H
  32 #define FIRM_ADT_PLIST_H
  33
  34 #include <stddef.h>
  35 #include "obst.h"
  36
  37 #include "../begin.h"
  38
  39 /**
  40  * @ingroup adt
  41  * @defgroup plist     pointer lists (deprecated)
  42  * @{
  43  */
  44
  45 typedef struct plist_element plist_element_t;
  46 typedef struct plist plist_t;
  47
  48 /**
  49  * The plist data type.
  50  */
  51 struct plist {
  52         /** The obstack used for all allocations. */
  53         struct obstack *obst;
  54
  55         /** Set to 1 if plist uses a foreign obstack */
  56         unsigned foreign_obstack : 1;
  57
  58         /** First element in the list. */
  59         plist_element_t *first_element;
  60
  61         /** Last element in the list. */
  62         plist_element_t *last_element;
  63
  64         /** Current number of elements in the list. */
  65         int element_count;
  66
  67         /**
  68          * First element in the free list.
  69          * Please note that the free list is a single linked list and all back
  70          * references are invalid.
  71          */
  72         plist_element_t* first_free_element;
  73 };
  74
  75 /**
  76  * An element in the pointer list.
  77  */
  78 struct plist_element {
  79         plist_element_t *next; /**< next element in double linked list */
  80         plist_element_t *prev; /**< previous element in double linked list */
  81         void            *data; /**< element data */
  82 };
  83
  84 /**
  85  * Creates a new pointer list and initializes it.
  86  * @return The newly created pointer list.
  87  */
  88 FIRM_API plist_t *plist_new(void);
  89
  90 /**
  91  * Creates a new pointer list and initializes it.
  92  * Uses the given obstack instead of creating one.
  93  * @param obst  The obstack to use
  94  * @return The newly created pointer list.
  95  */
  96 FIRM_API plist_t *plist_obstack_new(struct obstack *obst);
  97
  98 /**
  99  * Frees the passed pointer list.
 100  * After a call to this function all references to the list and any of
 101  * its elements are invalid.
 102  */
 103 FIRM_API void plist_free(plist_t *list);
 104
 105 /**
 106  * Returns the number of elements in a pointer list.
 107  * @param list the pointer list
 108  * @return The number of elements in a pointer list.
 109  */
 110 #define plist_count(list) \
 111         ((list)->element_count)
 112
 113 /**
 114  * Inserts an element at the back of a pointer list.
 115  * @param list the pointer list to append the new element to.
 116  * @param value the element value to append.
 117  */
 118 FIRM_API void plist_insert_back(plist_t *list, void *value);
 119
 120 /**
 121  * Inserts an element at the front of a pointer list.
 122  * @param list the pointer list to prepend the new element to.
 123  * @param value the element value to prepend.
 124  */
 125 FIRM_API void plist_insert_front(plist_t *list, void *value);
 126
 127 /**
 128  * Inserts an element into a pointer list before the specified element,
 129  * which must be non null.
 130  * @param list the pointer list to insert the new element into.
 131  * @param element the list element before which the new element should
 132  *                be inserted. This element must be a part of @p list.
 133  * @param value the element value to insert.
 134  */
 135 FIRM_API void plist_insert_before(plist_t *list, plist_element_t *element, void *value);
 136
 137 /**
 138  * Inserts an element into a pointer list after the specified element,
 139  * which must be non null.
 140  * @param list the pointer list to insert the new element into.
 141  * @param element the list element after which the new element should
 142  *                be inserted. This element must be a part of @p list.
 143  * @param value the element value to insert.
 144  */
 145 FIRM_API void plist_insert_after(plist_t *list, plist_element_t *element, void *value);
 146
 147 /**
 148  * Checks if list has an element with the given data pointer.
 149  * @param list   the list to check
 150  * @param value  the data pointer to look for
 151  * @return 1 if element with data pointer found, 0 otherwise
 152  */
 153 FIRM_API int plist_has_value(plist_t *list, void *value);
 154
 155 /**
 156  * Tries to find list element associated to the given data pointer.
 157  * @param list   the list to check
 158  * @param value  the data pointer to look for
 159  * @return The first list element associated to data pointer if found, NULL otherwise
 160  */
 161 FIRM_API plist_element_t *plist_find_value(plist_t *list, void *value);
 162
 163 /**
 164  * Erases the specified element from the pointer list.
 165  * @param list the pointer list from which the element should be erased.
 166  * @param element the list element to erase. This element must be a part
 167  *                of @p list.
 168  */
 169 FIRM_API void plist_erase(plist_t *list, plist_element_t *element);
 170
 171 /**
 172  * Erases all elements from the specified pointer list.
 173  * @param list the pointer list that should be cleared.
 174  */
 175 FIRM_API void plist_clear(plist_t *list);
 176
 177 /**
 178  * Returns the first element of a pointer list.
 179  * @param list the pointer list to iterate
 180  * @return a pointer to the element or NULL if the list is empty
 181  */
 182 #define plist_first(list) \
 183         ((list)->first_element)
 184
 185 /**
 186  * Returns the last element of a pointer list.
 187  * @param list the pointer list to iterate
 188  * @return a pointer to the element or NULL if the list is empty
 189  */
 190 #define plist_last(list) \
 191         ((list)->last_element)
 192
 193 /**
 194  * Checks whether a pointer list element has a successor or not.
 195  * @param element the list element that should be queried for existence
 196  *                of a successor.
 197  * @return TRUE if @p element has a successor, otherwise FALSE.
 198  */
 199 #define plist_element_has_next(element) \
 200         ((element)->next != NULL)
 201
 202 /**
 203  * Checks whether a pointer list element has a predecessor or not.
 204  * @param element the list element that should be queried for existence
 205  *                of a predecessor.
 206  * @return TRUE if @p element has a successor, otherwise FALSE.
 207  */
 208 #define plist_element_has_prev(element) \
 209         ((element)->prev != NULL)
 210
 211 /**
 212  * Gets the successor of the passed list element.
 213  * @param element the list element to return the successor of.
 214  * @return The successor of @p element or NULL if @p element is the last
 215  *         element in the sequence.
 216  */
 217 #define plist_element_get_next(element) \
 218         ((element)->next)
 219
 220 /**
 221  * Gets the predecessor of the passed list element.
 222  * @param element the list element to return the predecessor of.
 223  * @return The predecessor of @p element or NULL if @p element is the last
 224  *         element in the sequence.
 225  */
 226 #define plist_element_get_prev(element) \
 227         ((element)->prev)
 228
 229 /**
 230  * Gets the value stored in the passed list element.
 231  * @param element the list element to return the value of.
 232  * @return The value stored in @p element.
 233  */
 234 #define plist_element_get_value(element) \
 235         ((element)->data)
 236
 237 /**
 238  * Convenience macro to iterate over a plist.
 239  */
 240 #define foreach_plist(list, el) \
 241         for (el = plist_first(list); el; el = plist_element_get_next(el))
 242
 243 /** @} */
 244
 245 #include "../end.h"
 246
 247 #endif