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