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 240