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