plist.h 5.39 KB
Newer Older
1
2
3
4
5
6
7
/**
 * Simple, non circular, double linked pointer list.
 * Created because the properties of the standard circular list were not
 * very well suited for the interference graph implementation.
 * This list uses an obstack and a free-list to efficiently manage its
 * elements.
 * @author Kimon Hoffmann
Christian Würdig's avatar
Christian Würdig committed
8
9
 * @date   14.07.2005
 * @cvs-id $Id$
10
11
12
13
14
15
16
 * @note Until now the code is entirely untested so it probably contains
 * 		plenty of errors.
 */
#ifndef _PLIST_H_
#define _PLIST_H_

#include <stddef.h>
17
18
#include "obst.h"

Christian Würdig's avatar
Christian Würdig committed
19
20
typedef struct _plist_element plist_element_t;
typedef struct _plist plist_t;
21
22

/**
Christian Würdig's avatar
Christian Würdig committed
23
 * The plist data type.
24
 */
Christian Würdig's avatar
Christian Würdig committed
25
struct _plist {
26
27
28
29
30
31
32
	/**
	 * The obstack used for all allocations.
	 */
	struct obstack obst;
	/**
	 * First element in the list.
	 */
Christian Würdig's avatar
Christian Würdig committed
33
	plist_element_t *first_element;
34
35
36
	/**
	 * Last element in the list.
	 */
Christian Würdig's avatar
Christian Würdig committed
37
	plist_element_t *last_element;
38
39
40
	/**
	 * Current number of elements in the list.
	 */
Christian Würdig's avatar
Christian Würdig committed
41
	int element_count;
42
43
44
45
46
	/**
	 * First element in the free list.
	 * Please note that the free list is a single linked list and all back
	 * references are invalid.
	 */
Christian Würdig's avatar
Christian Würdig committed
47
	plist_element_t* first_free_element;
48
};
49
50
51
52

/**
 * An element in the pointer list.
 */
Christian Würdig's avatar
Christian Würdig committed
53
54
55
struct _plist_element {
	plist_element_t* next;
	plist_element_t* prev;
56
57
	void* data;
};
58
59

/**
60
 * Creates a new pointer list and initializes it.
61
62
 * @return The newly created pointer list.
 */
Christian Würdig's avatar
Christian Würdig committed
63
plist_t* plist_new(void);
64
65
66
67
68
69

/**
 * Frees the passed pointer list.
 * After a call to this function all references to the list and any of
 * its elements are invalid.
 */
Christian Würdig's avatar
Christian Würdig committed
70
void plist_free(plist_t* list);
71
72
73
74
75
76
77

/**
 * Returns the number of elements in a pointer list.
 * @param list the pointer list
 * @return The number of elements in a pointer list.
 */
#define plist_count(list) \
Christian Würdig's avatar
Christian Würdig committed
78
 	((list)->element_count)
79
80
81
82
83
84

/**
 * Inserts an element at the back of a pointer list.
 * @param list the pointer list to append the new element to.
 * @param value the element value to append.
 */
Christian Würdig's avatar
Christian Würdig committed
85
void plist_insert_back(plist_t* list, void* value);
86
87
88
89
90
91

/**
 * Inserts an element at the front of a pointer list.
 * @param list the pointer list to prepend the new element to.
 * @param value the element value to prepend.
 */
Christian Würdig's avatar
Christian Würdig committed
92
void plist_insert_front(plist_t* list, void* value);
93
94
95
96
97
98
99
100
101

/**
 * Inserts an element into a pointer list before the specified element,
 * which must be non null.
 * @param list the pointer list to insert the new element into.
 * @param element the list element before which the new element should
 * 		be inserted. This element must be a part of @p list.
 * @param value the element value to insert.
 */
Christian Würdig's avatar
Christian Würdig committed
102
void plist_insert_before(plist_t* list, plist_element_t* element, void* value);
103
104
105
106
107
108
109
110
111

/**
 * Inserts an element into a pointer list after the specified element,
 * which must be non null.
 * @param list the pointer list to insert the new element into.
 * @param element the list element after which the new element should
 * 		be inserted. This element must be a part of @p list.
 * @param value the element value to insert.
 */
Christian Würdig's avatar
Christian Würdig committed
112
void plist_insert_after(plist_t* list, plist_element_t* element, void* value);
113
114
115
116
117
118
119

/**
 * Erases the specified element from the pointer list.
 * @param list the pointer list from which the lement should be erased.
 * @param element the list element to erase. This element must be a part
 * 		of @p list.
 */
Christian Würdig's avatar
Christian Würdig committed
120
void plist_erase(plist_t* list, plist_element_t* element);
121
122
123
124
125

/**
 * Erases all elements from the specified pointer list.
 * @param list the pointer list that should be cleard.
 */
Christian Würdig's avatar
Christian Würdig committed
126
void plist_clear(plist_t* list);
127
128
129
130
131
132
133

/**
 * Returns the first element of a pointer list.
 * @param list the pointer list to iterate
 * @return a pointer to the element or NULL if the list is empty
 */
 #define plist_first(list) \
Christian Würdig's avatar
Christian Würdig committed
134
 	((list)->first_element)
135
136
137
138
139
140
141

/**
 * Returns the last element of a pointer list.
 * @param list the pointer list to iterate
 * @return a pointer to the element or NULL if the list is empty
 */
 #define plist_last(list) \
Christian Würdig's avatar
Christian Würdig committed
142
 	((list)->last_element)
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187

/**
 * Checks whether a pointer list element has a successor or not.
 * @param element the list element that should be queried for existance
 * 		of a successor.
 * @return TRUE if @p element has a successor, otherwise FALSE.
 */
#define plist_element_has_next(element) \
	((element)->next != NULL)

/**
 * Checks whether a pointer list element has a predecessor or not.
 * @param element the list element that should be queried for existance
 * 		of a predecessor.
 * @return TRUE if @p element has a successor, otherwise FALSE.
 */
#define plist_element_has_prev(element) \
	((element)->prev != NULL)

/**
 * Gets the successor of the passed list element.
 * @param element the list element to return the successor of.
 * @return The successor of @p element or NULL if @p element is the last
 * 		element in the sequence.
 */
#define plist_element_get_next(element) \
	((element)->next)

/**
 * Gets the predecessor of the passed list element.
 * @param element the list element to return the predecessor of.
 * @return The predecessor of @p element or NULL if @p element is the last
 * 		element in the sequence.
 */
#define plist_element_get_prev(element) \
	((element)->prev)

/**
 * Gets the value stored in the passed list element.
 * @param element the list element to return the value of.
 * @return The value stored in @p element.
 */
#define plist_element_get_value(element) \
	((element)->data)

Christian Würdig's avatar
Christian Würdig committed
188
189
190
191
192
193
/**
 * Convenience macro to iterate over a plist.
 */
#define foreach_plist(list, el) \
	for (el = plist_first(list); el; el = plist_element_get_next(el))

194
#endif /*_PLIST_H_*/