1 /* PSPP - computes sample statistics.
2 Copyright (C) 2006 Free Software Foundation, Inc.
3 Written by Ben Pfaff <blp@gnu.org>.
5 This program is free software; you can redistribute it and/or
6 modify it under the terms of the GNU General Public License as
7 published by the Free Software Foundation; either version 2 of the
8 License, or (at your option) any later version.
10 This program is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
20 /* Circular doubly linked lists.
22 This header (llx.h) supplies "external" circular doubly linked
23 lists. Its companion header (ll.h) supplies "embedded"
24 circular doubly linked lists. The two variants are described
25 briefly here. The external variant, for which this is the
26 header, is described in slightly more detail below. Each
27 function also has a detailed usage comment at its point of
30 The "ll" embedded linked list implementation puts the linked
31 list node within the data structure that the list contains.
32 This makes allocation efficient, in space and time. It also
33 makes it easy to find the list node associated with a given
34 object. However, it's difficult to include a given object in
35 an arbitrary number of lists, or to include a single object in
36 a single list in multiple positions.
38 The "llx" external linked list implementation allocates linked
39 list nodes separately from the objects in the list. Adding
40 and removing linked list nodes requires dynamic allocation, so
41 it is normally slower and takes more memory than the embedded
42 implementation. It also requires searching the list to find
43 the list node associated with a given object. However, it's
44 easy to include a given object in an arbitrary number of
45 lists, or to include a single object more than once within a
46 single list. It's also possible to create an external linked
47 list without adding a member to the data structure that the
55 #include <libpspp/ll.h>
57 /* External, circular doubly linked list.
59 Each list contains a single "null" element that separates the
60 head and the tail of the list. The null element is both
61 before the head and after the tail of the list. An empty list
62 contains just the null element.
64 An external linked list is represented as `struct llx_list'.
65 Each node in the list consists of a `struct llx' that contains
66 a `void *' pointer to the node's data. Use the llx_data()
67 function to extract the data pointer from a node.
69 Many list functions take ranges of nodes as arguments. Ranges
70 are "half-open"; that is, R0...R1 includes R0 but not R1. A
71 range whose endpoints are the same (e.g. R0...R0) contains no
74 Consider the following declarations:
80 int x; // Data member.
83 Here's an example of iteration from head to tail:
86 for (llx = llx_head (&list); llx != llx_null (&list);
89 struct foo *foo = llx_data (llx);
90 ...do something with foo->x...
93 Here's another way to do it:
95 struct llx *llx = llx_null (&list);
96 while ((llx = llx_next (llx)) != llx_null (&list))
98 struct foo *foo = llx_data (llx);
99 ...do something with foo->x...
103 /* External linked list node. */
106 struct ll ll; /* Node. */
107 void *data; /* Member data. */
113 struct ll_list ll_list; /* The list. */
116 /* Memory manager. */
119 /* Allocates and returns memory for a new struct llx.
120 If space is unavailable, returns a null pointer. */
121 struct llx *(*allocate) (void *aux);
123 /* Releases a previously allocated struct llx. */
124 void (*release) (struct llx *, void *aux);
126 /* Auxiliary data passed to allocate and release
131 /* Manager that uses the standard malloc and free routines. */
132 extern const struct llx_manager llx_malloc_mgr;
134 /* Returns negative if A < B, zero if A == B, positive if A > B. */
135 typedef int llx_compare_func (const void *a, const void *b, void *aux);
137 /* Returns true or false depending on properties of DATA. */
138 typedef bool llx_predicate_func (const void *data, void *aux);
140 /* Takes some action on DATA. */
141 typedef void llx_action_func (void *data, void *aux);
144 static inline void llx_init (struct llx_list *);
145 void llx_destroy (struct llx_list *, llx_action_func *destructor, void *aux,
146 const struct llx_manager *manager);
147 static inline bool llx_is_empty (const struct llx_list *);
148 size_t llx_count (const struct llx_list *);
151 static inline struct llx *llx_head (const struct llx_list *);
152 static inline struct llx *llx_tail (const struct llx_list *);
153 static inline struct llx *llx_null (const struct llx_list *);
154 static inline struct llx *llx_next (const struct llx *);
155 static inline struct llx *llx_prev (const struct llx *);
156 static inline void *llx_data (const struct llx *);
158 /* Stack- and queue-like behavior. */
159 struct llx *llx_push_head (struct llx_list *, void *,
160 const struct llx_manager *);
161 struct llx *llx_push_tail (struct llx_list *, void *,
162 const struct llx_manager *);
163 void *llx_pop_head (struct llx_list *, const struct llx_manager *);
164 void *llx_pop_tail (struct llx_list *, const struct llx_manager *);
167 struct llx *llx_insert (struct llx *before, void *,
168 const struct llx_manager *);
169 void llx_splice (struct llx *before, struct llx *r0, struct llx *r1);
170 void llx_swap (struct llx *a, struct llx *b);
171 void llx_swap_range (struct llx *a0, struct llx *a1,
172 struct llx *b0, struct llx *b1);
175 struct llx *llx_remove (struct llx *, const struct llx_manager *);
176 void llx_remove_range (struct llx *r0, struct llx *r1,
177 const struct llx_manager *);
178 size_t llx_remove_equal (struct llx *r0, struct llx *r1, const void *target,
179 llx_compare_func *, void *aux,
180 const struct llx_manager *);
181 size_t llx_remove_if (struct llx *r0, struct llx *r1,
182 llx_predicate_func *, void *aux,
183 const struct llx_manager *);
185 /* Non-mutating algorithms. */
186 struct llx *llx_find_equal (const struct llx *r0, const struct llx *r1,
188 llx_compare_func *, void *aux);
189 struct llx *llx_find_if (const struct llx *r0, const struct llx *r1,
190 llx_predicate_func *, void *aux);
191 struct llx *llx_find_adjacent_equal (const struct llx *r0,
192 const struct llx *r1,
193 llx_compare_func *, void *aux);
194 size_t llx_count_range (const struct llx *r0, const struct llx *r1);
195 size_t llx_count_equal (const struct llx *r0, const struct llx *r1,
197 llx_compare_func *, void *aux);
198 size_t llx_count_if (const struct llx *r0, const struct llx *r1,
199 llx_predicate_func *, void *aux);
200 struct llx *llx_max (const struct llx *r0, const struct llx *r1,
201 llx_compare_func *, void *aux);
202 struct llx *llx_min (const struct llx *r0, const struct llx *r1,
203 llx_compare_func *, void *aux);
204 int llx_lexicographical_compare_3way (const struct llx *a0,
205 const struct llx *a1,
206 const struct llx *b0,
207 const struct llx *b1,
208 llx_compare_func *, void *aux);
210 /* Mutating algorithms. */
211 void llx_apply (struct llx *r0, struct llx *r1, llx_action_func *, void *aux);
212 void llx_reverse (struct llx *r0, struct llx *r1);
213 bool llx_next_permutation (struct llx *r0, struct llx *r1,
214 llx_compare_func *, void *aux);
215 bool llx_prev_permutation (struct llx *r0, struct llx *r1,
216 llx_compare_func *, void *aux);
218 /* Sorted list functions. */
219 void llx_sort (struct llx *r0, struct llx *r1, llx_compare_func *, void *aux);
220 struct llx *llx_find_run (const struct llx *r0, const struct llx *r1,
221 llx_compare_func *, void *aux);
222 bool llx_is_sorted (const struct llx *r0, const struct llx *r1,
223 llx_compare_func *, void *aux);
224 struct llx *llx_merge (struct llx *a0, struct llx *a1,
225 struct llx *b0, struct llx *b1,
226 llx_compare_func *, void *aux);
227 size_t llx_unique (struct llx *r0, struct llx *r1, struct llx *dups,
228 llx_compare_func *, void *aux,
229 const struct llx_manager *);
230 void llx_sort_unique (struct llx *r0, struct llx *r1, struct llx *dups,
231 llx_compare_func *, void *aux,
232 const struct llx_manager *);
233 struct llx *llx_insert_ordered (struct llx *r0, struct llx *r1, void *data,
234 llx_compare_func *, void *aux,
235 const struct llx_manager *);
236 struct llx *llx_partition (struct llx *r0, struct llx *r1,
237 llx_predicate_func *, void *aux);
238 struct llx *llx_find_partition (const struct llx *r0, const struct llx *r1,
239 llx_predicate_func *, void *aux);
241 /* Returns the llx within which LL is embedded. */
243 llx_from_ll (struct ll *ll)
245 return ll_data (ll, struct llx, ll);
248 /* Initializes LIST as an empty list. */
250 llx_init (struct llx_list *list)
252 ll_init (&list->ll_list);
255 /* Returns true if LIST is empty (contains just the null node),
256 false if LIST is not empty (has at least one other node).
257 Executes in O(1) time. */
259 llx_is_empty (const struct llx_list *list)
261 return ll_is_empty (&list->ll_list);
264 /* Returns the first node in LIST,
265 or the null node if LIST is empty. */
266 static inline struct llx *
267 llx_head (const struct llx_list *list)
269 return llx_from_ll (ll_head (&list->ll_list));
272 /* Returns the last node in LIST,
273 or the null node if LIST is empty. */
274 static inline struct llx *
275 llx_tail (const struct llx_list *list)
277 return llx_from_ll (ll_tail (&list->ll_list));
280 /* Returns LIST's null node. */
281 static inline struct llx *
282 llx_null (const struct llx_list *list)
284 return llx_from_ll (ll_null (&list->ll_list));
287 /* Returns the node following LLX in its list,
288 or the null node if LLX is at the end of its list.
289 (In an empty list, the null node follows itself.) */
290 static inline struct llx *
291 llx_next (const struct llx *llx)
293 return llx_from_ll (ll_next (&llx->ll));
296 /* Returns the node preceding LLX in its list,
297 or the null node if LLX is the first node in its list.
298 (In an empty list, the null node precedes itself.) */
299 static inline struct llx *
300 llx_prev (const struct llx *llx)
302 return llx_from_ll (ll_prev (&llx->ll));
305 /* Returns the data in node LLX. */
307 llx_data (const struct llx *llx)