5188d38ec71cd8673ff5b774946651829309f696
[pspp-builds.git] / src / libpspp / llx.c
1 /* PSPP - computes sample statistics.
2    Copyright (C) 2006 Free Software Foundation, Inc.
3
4    This program is free software; you can redistribute it and/or
5    modify it under the terms of the GNU General Public License as
6    published by the Free Software Foundation; either version 2 of the
7    License, or (at your option) any later version.
8
9    This program is distributed in the hope that it will be useful, but
10    WITHOUT ANY WARRANTY; without even the implied warranty of
11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12    General Public License for more details.
13
14    You should have received a copy of the GNU General Public License
15    along with this program; if not, write to the Free Software
16    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
17    02110-1301, USA. */
18
19 /* External, circular doubly linked list. */
20
21 /* These library routines have no external dependencies, other
22    than ll.c and the standard C library.
23
24    If you add routines in this file, please add a corresponding
25    test to llx-test.c.  This test program should achieve 100%
26    coverage of lines and branches in this code, as reported by
27    "gcov -b". */
28
29 #ifdef HAVE_CONFIG_H
30 #include <config.h>
31 #endif
32
33 #include <libpspp/llx.h>
34 #include "compiler.h"
35 #include <assert.h>
36 #include <stdlib.h>
37
38 /* Destroys LIST and frees all of its nodes using MANAGER.
39    If DESTRUCTOR is non-null, each node in the list will be
40    passed to it in list order, with AUX as auxiliary data, before
41    that node is destroyed. */
42 void
43 llx_destroy (struct llx_list *list, llx_action_func *destructor, void *aux,
44              const struct llx_manager *manager)
45 {
46   struct llx *llx, *next;
47
48   for (llx = llx_head (list); llx != llx_null (list); llx = next)
49     {
50       next = llx_next (llx);
51       if (destructor != NULL)
52         destructor (llx_data (llx), aux);
53       manager->release (llx, manager->aux);
54     }
55 }
56
57 /* Returns the number of nodes in LIST (not counting the null
58    node).  Executes in O(n) time in the length of the list. */
59 size_t
60 llx_count (const struct llx_list *list)
61 {
62   return llx_count_range (llx_head (list), llx_null (list));
63 }
64
65 /* Inserts DATA at the head of LIST.
66    Returns the new node (allocated with MANAGER), or a null
67    pointer if memory allocation failed. */
68 struct llx *
69 llx_push_head (struct llx_list *list, void *data,
70                const struct llx_manager *manager)
71 {
72   return llx_insert (llx_head (list), data, manager);
73 }
74
75 /* Inserts DATA at the tail of LIST.
76    Returns the new node (allocated with MANAGER), or a null
77    pointer if memory allocation failed. */
78 struct llx *
79 llx_push_tail (struct llx_list *list, void *data,
80                const struct llx_manager *manager)
81 {
82   return llx_insert (llx_null (list), data, manager);
83 }
84
85 /* Removes the first node in LIST, which must not be empty,
86    and returns the data that the node contained.
87    Frees the node removed with MANAGER. */
88 void *
89 llx_pop_head (struct llx_list *list, const struct llx_manager *manager)
90 {
91   struct llx *llx = llx_from_ll (ll_head (&list->ll_list));
92   void *data = llx_data (llx);
93   llx_remove (llx, manager);
94   return data;
95 }
96
97 /* Removes the last node in LIST, which must not be empty,
98    and returns the data that the node contained.
99    Frees the node removed with MANAGER. */
100 void *
101 llx_pop_tail (struct llx_list *list, const struct llx_manager *manager)
102 {
103   struct llx *llx = llx_from_ll (ll_tail (&list->ll_list));
104   void *data = llx_data (llx);
105   llx_remove (llx, manager);
106   return data;
107 }
108
109 /* Inserts DATA before BEFORE.
110    Returns the new node (allocated with MANAGER), or a null
111    pointer if memory allocation failed. */
112 struct llx *
113 llx_insert (struct llx *before, void *data, const struct llx_manager *manager)
114 {
115   struct llx *llx = manager->allocate (manager->aux);
116   if (llx != NULL)
117     {
118       llx->data = data;
119       ll_insert (&before->ll, &llx->ll);
120     }
121   return llx;
122 }
123
124 /* Removes R0...R1 from their current list
125    and inserts them just before BEFORE. */
126 void
127 llx_splice (struct llx *before, struct llx *r0, struct llx *r1)
128 {
129   ll_splice (&before->ll, &r0->ll, &r1->ll);
130 }
131
132 /* Exchanges the positions of A and B,
133    which may be in the same list or different lists. */
134 void
135 llx_swap (struct llx *a, struct llx *b)
136 {
137   ll_swap (&a->ll, &b->ll);
138 }
139
140 /* Exchanges the positions of A0...A1 and B0...B1,
141    which may be in the same list or different lists but must not
142    overlap. */
143 void
144 llx_swap_range (struct llx *a0, struct llx *a1,
145                 struct llx *b0, struct llx *b1)
146 {
147   ll_swap_range (&a0->ll, &a1->ll, &b0->ll, &b1->ll);
148 }
149
150 /* Removes LLX from its list
151    and returns the node that formerly followed it.
152    Frees the node removed with MANAGER. */
153 struct llx *
154 llx_remove (struct llx *llx, const struct llx_manager *manager)
155 {
156   struct llx *next = llx_next (llx);
157   ll_remove (&llx->ll);
158   manager->release (llx, manager->aux);
159   return next;
160 }
161
162 /* Removes R0...R1 from their list.
163    Frees the removed nodes with MANAGER. */
164 void
165 llx_remove_range (struct llx *r0, struct llx *r1,
166                   const struct llx_manager *manager)
167 {
168   struct llx *llx;
169
170   for (llx = r0; llx != r1; )
171     llx = llx_remove (llx, manager);
172 }
173
174 /* Removes from R0...R1 all the nodes that equal TARGET
175    according to COMPARE given auxiliary data AUX.
176    Frees the removed nodes with MANAGER.
177    Returns the number of nodes removed. */
178 size_t
179 llx_remove_equal (struct llx *r0, struct llx *r1, const void *target,
180                   llx_compare_func *compare, void *aux,
181                   const struct llx_manager *manager)
182 {
183   struct llx *x;
184   size_t count;
185
186   count = 0;
187   for (x = r0; x != r1; )
188     if (compare (llx_data (x), target, aux) == 0)
189       {
190         x = llx_remove (x, manager);
191         count++;
192       }
193     else
194       x = llx_next (x);
195
196   return count;
197 }
198
199 /* Removes from R0...R1 all the nodes for which PREDICATE returns
200    true given auxiliary data AUX.
201    Frees the removed nodes with MANAGER.
202    Returns the number of nodes removed. */
203 size_t
204 llx_remove_if (struct llx *r0, struct llx *r1,
205                llx_predicate_func *predicate, void *aux,
206                const struct llx_manager *manager)
207 {
208   struct llx *x;
209   size_t count;
210
211   count = 0;
212   for (x = r0; x != r1; )
213     if (predicate (llx_data (x), aux))
214       {
215         x = llx_remove (x, manager);
216         count++;
217       }
218     else
219       x = llx_next (x);
220
221   return count;
222 }
223
224 /* Returns the first node in R0...R1 that equals TARGET
225    according to COMPARE given auxiliary data AUX.
226    Returns R1 if no node in R0...R1 equals TARGET. */
227 struct llx *
228 llx_find_equal (const struct llx *r0, const struct llx *r1,
229                 const void *target,
230                 llx_compare_func *compare, void *aux)
231 {
232   const struct llx *x;
233
234   for (x = r0; x != r1; x = llx_next (x))
235     if (compare (llx_data (x), target, aux) == 0)
236       break;
237   return (struct llx *) x;
238 }
239
240 /* Returns the first node in R0...R1 for which PREDICATE returns
241    true given auxiliary data AUX.
242    Returns R1 if PREDICATE does not return true for any node in
243    R0...R1 . */
244 struct llx *
245 llx_find_if (const struct llx *r0, const struct llx *r1,
246              llx_predicate_func *predicate, void *aux)
247 {
248   const struct llx *x;
249
250   for (x = r0; x != r1; x = llx_next (x))
251     if (predicate (llx_data (x), aux))
252       break;
253   return (struct llx *) x;
254 }
255
256 /* Compares each pair of adjacent nodes in R0...R1
257    using COMPARE with auxiliary data AUX
258    and returns the first node of the first pair that compares
259    equal.
260    Returns R1 if no pair compares equal. */
261 struct llx *
262 llx_find_adjacent_equal (const struct llx *r0, const struct llx *r1,
263                          llx_compare_func *compare, void *aux)
264 {
265   if (r0 != r1)
266     {
267       const struct llx *x, *y;
268
269       for (x = r0, y = llx_next (x); y != r1; x = y, y = llx_next (y))
270         if (compare (llx_data (x), llx_data (y), aux) == 0)
271           return (struct llx *) x;
272     }
273
274   return (struct llx *) r1;
275 }
276
277 /* Returns the number of nodes in R0...R1.
278    Executes in O(n) time in the return value. */
279 size_t
280 llx_count_range (const struct llx *r0, const struct llx *r1)
281 {
282   return ll_count_range (&r0->ll, &r1->ll);
283 }
284
285 /* Counts and returns the number of nodes in R0...R1 that equal
286    TARGET according to COMPARE given auxiliary data AUX. */
287 size_t
288 llx_count_equal (const struct llx *r0, const struct llx *r1,
289                  const void *target,
290                  llx_compare_func *compare, void *aux)
291 {
292   const struct llx *x;
293   size_t count;
294
295   count = 0;
296   for (x = r0; x != r1; x = llx_next (x))
297     if (compare (llx_data (x), target, aux) == 0)
298       count++;
299   return count;
300 }
301
302 /* Counts and returns the number of nodes in R0...R1 for which
303    PREDICATE returns true given auxiliary data AUX. */
304 size_t
305 llx_count_if (const struct llx *r0, const struct llx *r1,
306               llx_predicate_func *predicate, void *aux)
307 {
308   const struct llx *x;
309   size_t count;
310
311   count = 0;
312   for (x = r0; x != r1; x = llx_next (x))
313     if (predicate (llx_data (x), aux))
314       count++;
315   return count;
316 }
317
318 /* Returns the greatest node in R0...R1 according to COMPARE
319    given auxiliary data AUX.
320    Returns the first of multiple, equal maxima. */
321 struct llx *
322 llx_max (const struct llx *r0, const struct llx *r1,
323          llx_compare_func *compare, void *aux)
324 {
325   const struct llx *max = r0;
326   if (r0 != r1)
327     {
328       struct llx *x;
329
330       for (x = llx_next (r0); x != r1; x = llx_next (x))
331         if (compare (llx_data (x), llx_data (max), aux) > 0)
332           max = x;
333     }
334   return (struct llx *) max;
335 }
336
337 /* Returns the least node in R0...R1 according to COMPARE given
338    auxiliary data AUX.
339    Returns the first of multiple, equal minima. */
340 struct llx *
341 llx_min (const struct llx *r0, const struct llx *r1,
342          llx_compare_func *compare, void *aux)
343 {
344   const struct llx *min = r0;
345   if (r0 != r1)
346     {
347       struct llx *x;
348
349       for (x = llx_next (r0); x != r1; x = llx_next (x))
350         if (compare (llx_data (x), llx_data (min), aux) < 0)
351           min = x;
352     }
353   return (struct llx *) min;
354 }
355
356 /* Lexicographically compares A0...A1 to B0...B1.
357    Returns negative if A0...A1 < B0...B1,
358    zero if A0...A1 == B0...B1, and
359    positive if A0...A1 > B0...B1
360    according to COMPARE given auxiliary data AUX. */
361 int
362 llx_lexicographical_compare_3way (const struct llx *a0, const struct llx *a1,
363                                   const struct llx *b0, const struct llx *b1,
364                                   llx_compare_func *compare, void *aux)
365 {
366   for (;;)
367     if (b0 == b1)
368       return a0 != a1;
369     else if (a0 == a1)
370       return -1;
371     else
372       {
373         int cmp = compare (llx_data (a0), llx_data (b0), aux);
374         if (cmp != 0)
375           return cmp;
376
377         a0 = llx_next (a0);
378         b0 = llx_next (b0);
379       }
380 }
381
382 /* Calls ACTION with auxiliary data AUX
383    for every node in R0...R1 in order. */
384 void
385 llx_apply (struct llx *r0, struct llx *r1,
386            llx_action_func *action, void *aux)
387 {
388   struct llx *llx;
389
390   for (llx = r0; llx != r1; llx = llx_next (llx))
391     action (llx_data (llx), aux);
392 }
393
394 /* Reverses the order of nodes R0...R1. */
395 void
396 llx_reverse (struct llx *r0, struct llx *r1)
397 {
398   ll_reverse (&r0->ll, &r1->ll);
399 }
400
401 /* Arranges R0...R1 into the lexicographically next greater
402    permutation.  Returns true if successful.
403    If R0...R1 is already the lexicographically greatest
404    permutation of its elements (i.e. ordered from greatest to
405    smallest), arranges them into the lexicographically least
406    permutation (i.e. ordered from smallest to largest) and
407    returns false.
408    COMPARE with auxiliary data AUX is used to compare nodes. */
409 bool
410 llx_next_permutation (struct llx *r0, struct llx *r1,
411                       llx_compare_func *compare, void *aux)
412 {
413   if (r0 != r1)
414     {
415       struct llx *i = llx_prev (r1);
416       while (i != r0)
417         {
418           i = llx_prev (i);
419           if (compare (llx_data (i), llx_data (llx_next (i)), aux) < 0)
420             {
421               struct llx *j;
422               for (j = llx_prev (r1);
423                    compare (llx_data (i), llx_data (j), aux) >= 0;
424                    j = llx_prev (j))
425                 continue;
426               llx_swap (i, j);
427               llx_reverse (llx_next (j), r1);
428               return true;
429             }
430         }
431
432       llx_reverse (r0, r1);
433     }
434
435   return false;
436 }
437
438 /* Arranges R0...R1 into the lexicographically next lesser
439    permutation.  Returns true if successful.
440    If R0...R1 is already the lexicographically least
441    permutation of its elements (i.e. ordered from smallest to
442    greatest), arranges them into the lexicographically greatest
443    permutation (i.e. ordered from largest to smallest) and
444    returns false.
445    COMPARE with auxiliary data AUX is used to compare nodes. */
446 bool
447 llx_prev_permutation (struct llx *r0, struct llx *r1,
448                       llx_compare_func *compare, void *aux)
449 {
450   if (r0 != r1)
451     {
452       struct llx *i = llx_prev (r1);
453       while (i != r0)
454         {
455           i = llx_prev (i);
456           if (compare (llx_data (i), llx_data (llx_next (i)), aux) > 0)
457             {
458               struct llx *j;
459               for (j = llx_prev (r1);
460                    compare (llx_data (i), llx_data (j), aux) <= 0;
461                    j = llx_prev (j))
462                 continue;
463               llx_swap (i, j);
464               llx_reverse (llx_next (j), r1);
465               return true;
466             }
467         }
468
469       llx_reverse (r0, r1);
470     }
471
472   return false;
473 }
474
475 /* Sorts R0...R1 into ascending order
476    according to COMPARE given auxiliary data AUX.
477    In use, keep in mind that R0 may move during the sort, so that
478    afterward R0...R1 may denote a different range.
479    (On the other hand, R1 is fixed in place.)
480    Runs in O(n lg n) time in the number of nodes in the range. */
481 void
482 llx_sort (struct llx *r0, struct llx *r1, llx_compare_func *compare, void *aux)
483 {
484   struct llx *pre_r0;
485   size_t output_run_cnt;
486
487   if (r0 == r1 || llx_next (r0) == r1)
488     return;
489
490   pre_r0 = llx_prev (r0);
491   do
492     {
493       struct llx *a0 = llx_next (pre_r0);
494       for (output_run_cnt = 1; ; output_run_cnt++)
495         {
496           struct llx *a1 = llx_find_run (a0, r1, compare, aux);
497           struct llx *a2 = llx_find_run (a1, r1, compare, aux);
498           if (a1 == a2)
499             break;
500
501           a0 = llx_merge (a0, a1, a1, a2, compare, aux);
502         }
503     }
504   while (output_run_cnt > 1);
505 }
506
507 /* Finds the extent of a run of nodes of increasing value
508    starting at R0 and extending no farther than R1.
509    Returns the first node in R0...R1 that is less than the
510    preceding node, or R1 if R0...R1 are arranged in nondecreasing
511    order. */
512 struct llx *
513 llx_find_run (const struct llx *r0, const struct llx *r1,
514               llx_compare_func *compare, void *aux)
515 {
516   if (r0 != r1)
517     {
518       do
519         {
520           r0 = llx_next (r0);
521         }
522       while (r0 != r1 && compare (llx_data (llx_prev (r0)),
523                                   llx_data (r0), aux) <= 0);
524     }
525
526   return (struct llx *) r0;
527 }
528
529 /* Merges B0...B1 into A0...A1 according to COMPARE given
530    auxiliary data AUX.
531    The ranges may be in the same list or different lists, but
532    must not overlap.
533    The merge is "stable" if A0...A1 is considered to precede
534    B0...B1, regardless of their actual ordering.
535    Runs in O(n) time in the total number of nodes in the ranges. */
536 struct llx *
537 llx_merge (struct llx *a0, struct llx *a1, struct llx *b0, struct llx *b1,
538            llx_compare_func *compare, void *aux)
539 {
540   if (a0 != a1 && b0 != b1)
541     {
542       a1 = llx_prev (a1);
543       b1 = llx_prev (b1);
544       for (;;)
545         if (compare (llx_data (a0), llx_data (b0), aux) <= 0)
546           {
547             if (a0 == a1)
548               {
549                 llx_splice (llx_next (a0), b0, llx_next (b1));
550                 return llx_next (b1);
551               }
552             a0 = llx_next (a0);
553           }
554         else
555           {
556             if (b0 != b1)
557               {
558                 struct llx *x = b0;
559                 b0 = llx_next (b0);
560                 llx_splice (a0, x, b0);
561               }
562             else
563               {
564                 llx_splice (a0, b0, llx_next (b0));
565                 return llx_next (a1);
566               }
567           }
568     }
569   else
570     {
571       llx_splice (a0, b0, b1);
572       return b1;
573     }
574 }
575
576 /* Returns true if R0...R1 is sorted in ascending order according
577    to COMPARE given auxiliary data AUX,
578    false otherwise. */
579 bool
580 llx_is_sorted (const struct llx *r0, const struct llx *r1,
581                llx_compare_func *compare, void *aux)
582 {
583   return llx_find_run (r0, r1, compare, aux) == r1;
584 }
585
586 /* Removes all but the first in each group of sequential
587    duplicates in R0...R1.  Duplicates are determined using
588    COMPARE given auxiliary data AUX.  Removed duplicates are
589    inserted before DUPS if it is nonnull; otherwise, the removed
590    duplicates are freed with MANAGER.
591    Only sequential duplicates are removed.  llx_sort() may be used
592    to bring duplicates together, or llx_sort_unique() can do both
593    at once. */
594 size_t
595 llx_unique (struct llx *r0, struct llx *r1, struct llx *dups,
596             llx_compare_func *compare, void *aux,
597             const struct llx_manager *manager)
598 {
599   size_t count = 0;
600
601   if (r0 != r1)
602     {
603       struct llx *x = r0;
604       for (;;)
605         {
606           struct llx *y = llx_next (x);
607           if (y == r1)
608             {
609               count++;
610               break;
611             }
612
613           if (compare (llx_data (x), llx_data (y), aux) == 0)
614             {
615               if (dups != NULL)
616                 llx_splice (dups, y, llx_next (y));
617               else
618                 llx_remove (y, manager);
619             }
620           else
621             {
622               x = y;
623               count++;
624             }
625         }
626     }
627
628   return count;
629 }
630
631 /* Sorts R0...R1 and removes duplicates.
632    Removed duplicates are inserted before DUPS if it is nonnull;
633    otherwise, the removed duplicates are freed with MANAGER.
634    Comparisons are made with COMPARE given auxiliary data AUX.
635    In use, keep in mind that R0 may move during the sort, so that
636    afterward R0...R1 may denote a different range.
637    (On the other hand, R1 is fixed in place.)
638    Runs in O(n lg n) time in the number of nodes in the range. */
639 void
640 llx_sort_unique (struct llx *r0, struct llx *r1, struct llx *dups,
641                  llx_compare_func *compare, void *aux,
642                  const struct llx_manager *manager)
643 {
644   struct llx *pre_r0 = llx_prev (r0);
645   llx_sort (r0, r1, compare, aux);
646   llx_unique (llx_next (pre_r0), r1, dups, compare, aux, manager);
647 }
648
649 /* Inserts DATA in the proper position in R0...R1, which must
650    be sorted according to COMPARE given auxiliary data AUX.
651    If DATA is equal to one or more existing nodes in R0...R1,
652    then it is inserted after the existing nodes it equals.
653    Returns the new node (allocated with MANAGER), or a null
654    pointer if memory allocation failed.
655    Runs in O(n) time in the number of nodes in the range. */
656 struct llx *
657 llx_insert_ordered (struct llx *r0, struct llx *r1, void *data,
658                     llx_compare_func *compare, void *aux,
659                     const struct llx_manager *manager)
660 {
661   struct llx *x;
662
663   for (x = r0; x != r1; x = llx_next (x))
664     if (compare (llx_data (x), data, aux) > 0)
665       break;
666   return llx_insert (x, data, manager);
667 }
668
669 /* Partitions R0...R1 into those nodes for which PREDICATE given
670    auxiliary data AUX returns true, followed by those for which
671    PREDICATE returns false.
672    Returns the first node in the "false" group, or R1 if
673    PREDICATE is true for every node in R0...R1.
674    The partition is "stable" in that the nodes in each group
675    retain their original relative order.
676    Runs in O(n) time in the number of nodes in the range. */
677 struct llx *
678 llx_partition (struct llx *r0, struct llx *r1,
679                llx_predicate_func *predicate, void *aux)
680 {
681   struct llx *t0, *t1;
682
683   for (;;)
684     {
685       if (r0 == r1)
686         return r0;
687       else if (!predicate (llx_data (r0), aux))
688         break;
689
690       r0 = llx_next (r0);
691     }
692
693   for (t0 = r0;; t0 = t1)
694     {
695       do
696         {
697           t0 = llx_next (t0);
698           if (t0 == r1)
699             return r0;
700         }
701       while (!predicate (llx_data (t0), aux));
702
703       t1 = t0;
704       do
705         {
706           t1 = llx_next (t1);
707           if (t1 == r1)
708             {
709               llx_splice (r0, t0, t1);
710               return r0;
711             }
712         }
713       while (predicate (llx_data (t1), aux));
714
715       llx_splice (r0, t0, t1);
716     }
717 }
718
719 /* Verifies that R0...R1 is parititioned into a sequence of nodes
720    for which PREDICATE given auxiliary data AUX returns true,
721    followed by those for which PREDICATE returns false.
722    Returns a null pointer if R0...R1 is not partitioned this way.
723    Otherwise, returns the first node in the "false" group, or R1
724    if PREDICATE is true for every node in R0...R1. */
725 struct llx *
726 llx_find_partition (const struct llx *r0, const struct llx *r1,
727                     llx_predicate_func *predicate, void *aux)
728 {
729   const struct llx *partition, *x;
730
731   for (partition = r0; partition != r1; partition = llx_next (partition))
732     if (!predicate (llx_data (partition), aux))
733       break;
734
735   for (x = partition; x != r1; x = llx_next (x))
736     if (predicate (llx_data (x), aux))
737       return NULL;
738
739   return (struct llx *) partition;
740 }
741 \f
742 /* Allocates and returns a node using malloc. */
743 static struct llx *
744 malloc_allocate_node (void *aux UNUSED)
745 {
746   return malloc (sizeof (struct llx));
747 }
748
749 /* Releases node LLX with free. */
750 static void
751 malloc_release_node (struct llx *llx, void *aux UNUSED)
752 {
753   free (llx);
754 }
755
756 /* Manager that uses the standard malloc and free routines. */
757 const struct llx_manager llx_malloc_mgr =
758   {
759     malloc_allocate_node,
760     malloc_release_node,
761     NULL,
762   };