1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2006 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
17 /* Circular doubly linked lists.
19 This header (llx.h) supplies "external" circular doubly linked
20 lists. Its companion header (ll.h) supplies "embedded"
21 circular doubly linked lists. The two variants are described
22 briefly here. The external variant, for which this is the
23 header, is described in slightly more detail below. Each
24 function also has a detailed usage comment at its point of
27 The "ll" embedded linked list implementation puts the linked
28 list node within the data structure that the list contains.
29 This makes allocation efficient, in space and time. It also
30 makes it easy to find the list node associated with a given
31 object. However, it's difficult to include a given object in
32 an arbitrary number of lists, or to include a single object in
33 a single list in multiple positions.
35 The "llx" external linked list implementation allocates linked
36 list nodes separately from the objects in the list. Adding
37 and removing linked list nodes requires dynamic allocation, so
38 it is normally slower and takes more memory than the embedded
39 implementation. It also requires searching the list to find
40 the list node associated with a given object. However, it's
41 easy to include a given object in an arbitrary number of
42 lists, or to include a single object more than once within a
43 single list. It's also possible to create an external linked
44 list without adding a member to the data structure that the
52 #include <libpspp/ll.h>
54 /* External, circular doubly linked list.
56 Each list contains a single "null" element that separates the
57 head and the tail of the list. The null element is both
58 before the head and after the tail of the list. An empty list
59 contains just the null element.
61 An external linked list is represented as `struct llx_list'.
62 Each node in the list consists of a `struct llx' that contains
63 a `void *' pointer to the node's data. Use the llx_data()
64 function to extract the data pointer from a node.
66 Many list functions take ranges of nodes as arguments. Ranges
67 are "half-open"; that is, R0...R1 includes R0 but not R1. A
68 range whose endpoints are the same (e.g. R0...R0) contains no
71 Consider the following declarations:
77 int x; // Data member.
80 Here's an example of iteration from head to tail:
83 for (llx = llx_head (&list); llx != llx_null (&list);
86 struct foo *foo = llx_data (llx);
87 ...do something with foo->x...
90 Here's another way to do it:
92 struct llx *llx = llx_null (&list);
93 while ((llx = llx_next (llx)) != llx_null (&list))
95 struct foo *foo = llx_data (llx);
96 ...do something with foo->x...
100 /* External linked list node. */
103 struct ll ll; /* Node. */
104 void *data; /* Member data. */
110 struct ll_list ll_list; /* The list. */
113 /* Suitable for use as the initializer for a `struct llx_list'
114 named LIST. Typical usage:
115 struct llx_list list = LLX_INITIALIZER (list);
116 LLX_INITIALIZER() is an alternative to llx_init(). */
117 #define LLX_INITIALIZER(LIST) { LL_INITIALIZER ((LIST).ll_list) }
119 /* Memory manager. */
122 /* Allocates and returns memory for a new struct llx.
123 If space is unavailable, returns a null pointer. */
124 struct llx *(*allocate) (void *aux);
126 /* Releases a previously allocated struct llx. */
127 void (*release) (struct llx *, void *aux);
129 /* Auxiliary data passed to allocate and release
134 /* Manager that uses the standard malloc and free routines. */
135 extern const struct llx_manager llx_malloc_mgr;
137 /* Returns negative if A < B, zero if A == B, positive if A > B. */
138 typedef int llx_compare_func (const void *a, const void *b, void *aux);
140 /* Returns true or false depending on properties of DATA. */
141 typedef bool llx_predicate_func (const void *data, void *aux);
143 /* Takes some action on DATA. */
144 typedef void llx_action_func (void *data, void *aux);
147 static inline void llx_init (struct llx_list *);
148 void llx_destroy (struct llx_list *, llx_action_func *destructor, void *aux,
149 const struct llx_manager *manager);
150 static inline bool llx_is_empty (const struct llx_list *);
151 size_t llx_count (const struct llx_list *);
154 static inline struct llx *llx_head (const struct llx_list *);
155 static inline struct llx *llx_tail (const struct llx_list *);
156 static inline struct llx *llx_null (const struct llx_list *);
157 static inline struct llx *llx_next (const struct llx *);
158 static inline struct llx *llx_prev (const struct llx *);
159 static inline void *llx_data (const struct llx *);
161 /* Stack- and queue-like behavior. */
162 struct llx *llx_push_head (struct llx_list *, void *,
163 const struct llx_manager *);
164 struct llx *llx_push_tail (struct llx_list *, void *,
165 const struct llx_manager *);
166 void *llx_pop_head (struct llx_list *, const struct llx_manager *);
167 void *llx_pop_tail (struct llx_list *, const struct llx_manager *);
170 struct llx *llx_insert (struct llx *before, void *,
171 const struct llx_manager *);
172 void llx_splice (struct llx *before, struct llx *r0, struct llx *r1);
173 void llx_swap (struct llx *a, struct llx *b);
174 void llx_swap_range (struct llx *a0, struct llx *a1,
175 struct llx *b0, struct llx *b1);
178 struct llx *llx_remove (struct llx *, const struct llx_manager *);
179 void llx_remove_range (struct llx *r0, struct llx *r1,
180 const struct llx_manager *);
181 size_t llx_remove_equal (struct llx *r0, struct llx *r1, const void *target,
182 llx_compare_func *, void *aux,
183 const struct llx_manager *);
184 size_t llx_remove_if (struct llx *r0, struct llx *r1,
185 llx_predicate_func *, void *aux,
186 const struct llx_manager *);
188 /* Non-mutating algorithms. */
189 struct llx *llx_find_equal (const struct llx *r0, const struct llx *r1,
191 llx_compare_func *, void *aux);
192 struct llx *llx_find_if (const struct llx *r0, const struct llx *r1,
193 llx_predicate_func *, void *aux);
194 struct llx *llx_find_adjacent_equal (const struct llx *r0,
195 const struct llx *r1,
196 llx_compare_func *, void *aux);
197 size_t llx_count_range (const struct llx *r0, const struct llx *r1);
198 size_t llx_count_equal (const struct llx *r0, const struct llx *r1,
200 llx_compare_func *, void *aux);
201 size_t llx_count_if (const struct llx *r0, const struct llx *r1,
202 llx_predicate_func *, void *aux);
203 struct llx *llx_max (const struct llx *r0, const struct llx *r1,
204 llx_compare_func *, void *aux);
205 struct llx *llx_min (const struct llx *r0, const struct llx *r1,
206 llx_compare_func *, void *aux);
207 int llx_lexicographical_compare_3way (const struct llx *a0,
208 const struct llx *a1,
209 const struct llx *b0,
210 const struct llx *b1,
211 llx_compare_func *, void *aux);
213 /* Mutating algorithms. */
214 void llx_apply (struct llx *r0, struct llx *r1, llx_action_func *, void *aux);
215 void llx_reverse (struct llx *r0, struct llx *r1);
216 bool llx_next_permutation (struct llx *r0, struct llx *r1,
217 llx_compare_func *, void *aux);
218 bool llx_prev_permutation (struct llx *r0, struct llx *r1,
219 llx_compare_func *, void *aux);
221 /* Sorted list functions. */
222 void llx_sort (struct llx *r0, struct llx *r1, llx_compare_func *, void *aux);
223 struct llx *llx_find_run (const struct llx *r0, const struct llx *r1,
224 llx_compare_func *, void *aux);
225 bool llx_is_sorted (const struct llx *r0, const struct llx *r1,
226 llx_compare_func *, void *aux);
227 struct llx *llx_merge (struct llx *a0, struct llx *a1,
228 struct llx *b0, struct llx *b1,
229 llx_compare_func *, void *aux);
230 size_t llx_unique (struct llx *r0, struct llx *r1, struct llx *dups,
231 llx_compare_func *, void *aux,
232 const struct llx_manager *);
233 void llx_sort_unique (struct llx *r0, struct llx *r1, struct llx *dups,
234 llx_compare_func *, void *aux,
235 const struct llx_manager *);
236 struct llx *llx_insert_ordered (struct llx *r0, struct llx *r1, void *data,
237 llx_compare_func *, void *aux,
238 const struct llx_manager *);
239 struct llx *llx_partition (struct llx *r0, struct llx *r1,
240 llx_predicate_func *, void *aux);
241 struct llx *llx_find_partition (const struct llx *r0, const struct llx *r1,
242 llx_predicate_func *, void *aux);
244 /* Returns the llx within which LL is embedded. */
246 llx_from_ll (struct ll *ll)
248 return ll_data (ll, struct llx, ll);
251 /* Initializes LIST as an empty list. */
253 llx_init (struct llx_list *list)
255 ll_init (&list->ll_list);
258 /* Returns true if LIST is empty (contains just the null node),
259 false if LIST is not empty (has at least one other node).
260 Executes in O(1) time. */
262 llx_is_empty (const struct llx_list *list)
264 return ll_is_empty (&list->ll_list);
267 /* Returns the first node in LIST,
268 or the null node if LIST is empty. */
269 static inline struct llx *
270 llx_head (const struct llx_list *list)
272 return llx_from_ll (ll_head (&list->ll_list));
275 /* Returns the last node in LIST,
276 or the null node if LIST is empty. */
277 static inline struct llx *
278 llx_tail (const struct llx_list *list)
280 return llx_from_ll (ll_tail (&list->ll_list));
283 /* Returns LIST's null node. */
284 static inline struct llx *
285 llx_null (const struct llx_list *list)
287 return llx_from_ll (ll_null (&list->ll_list));
290 /* Returns the node following LLX in its list,
291 or the null node if LLX is at the end of its list.
292 (In an empty list, the null node follows itself.) */
293 static inline struct llx *
294 llx_next (const struct llx *llx)
296 return llx_from_ll (ll_next (&llx->ll));
299 /* Returns the node preceding LLX in its list,
300 or the null node if LLX is the first node in its list.
301 (In an empty list, the null node precedes itself.) */
302 static inline struct llx *
303 llx_prev (const struct llx *llx)
305 return llx_from_ll (ll_prev (&llx->ll));
308 /* Returns the data in node LLX. */
310 llx_data (const struct llx *llx)