Remove LIB_CLOSE variables from linker options.
[pspp] / src / libpspp / ll.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2006 Free Software Foundation, Inc.
3
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.
8
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.
13
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/>. */
16
17 /* Embedded, circular doubly linked list. */
18
19 /* These library routines have no external dependencies other
20    than the standard C library.
21
22    If you add routines in this file, please add a corresponding
23    test to ll-test.c.  This test program should achieve 100%
24    coverage of lines and branches in this code, as reported by
25    "gcov -b". */
26
27 #ifdef HAVE_CONFIG_H
28 #include <config.h>
29 #endif
30
31 #include <libpspp/ll.h>
32 #include <assert.h>
33
34 /* Returns the number of nodes in LIST (not counting the null
35    node).  Executes in O(n) time in the length of the list. */
36 size_t
37 ll_count (const struct ll_list *list)
38 {
39   return ll_count_range (ll_head (list), ll_null (list));
40 }
41
42 /* Removes R0...R1 from their current list
43    and inserts them just before BEFORE. */
44 void
45 ll_splice (struct ll *before, struct ll *r0, struct ll *r1)
46 {
47   if (before != r0 && r0 != r1)
48     {
49       /* Change exclusive range to inclusive. */
50       r1 = ll_prev (r1);
51
52       /* Remove R0...R1 from its list. */
53       r0->prev->next = r1->next;
54       r1->next->prev = r0->prev;
55
56       /* Insert R0...R1 before BEFORE. */
57       r0->prev = before->prev;
58       r1->next = before;
59       before->prev->next = r0;
60       before->prev = r1;
61     }
62 }
63
64 /* Exchanges the positions of A and B,
65    which may be in the same list or different lists. */
66 void
67 ll_swap (struct ll *a, struct ll *b)
68 {
69   if (a != b)
70     {
71       if (ll_next (a) != b)
72         {
73           struct ll *a_next = ll_remove (a);
74           struct ll *b_next = ll_remove (b);
75           ll_insert (b_next, a);
76           ll_insert (a_next, b);
77         }
78       else
79         {
80           ll_remove (b);
81           ll_insert (a, b);
82         }
83     }
84 }
85
86 /* Exchanges the positions of A0...A1 and B0...B1,
87    which may be in the same list or different lists but must not
88    overlap. */
89 void
90 ll_swap_range (struct ll *a0, struct ll *a1, struct ll *b0, struct ll *b1)
91 {
92   if (a0 == a1 || a1 == b0)
93     ll_splice (a0, b0, b1);
94   else if (b0 == b1 || b1 == a0)
95     ll_splice (b0, a0, a1);
96   else
97     {
98       struct ll *x0 = ll_prev (a0), *x1 = a1;
99       struct ll *y0 = ll_prev (b0), *y1 = b1;
100       a1 = ll_prev (a1);
101       b1 = ll_prev (b1);
102       x0->next = b0;
103       b0->prev = x0;
104       b1->next = x1;
105       x1->prev = b1;
106       y0->next = a0;
107       a0->prev = y0;
108       a1->next = y1;
109       y1->prev = a1;
110     }
111 }
112
113 /* Removes from R0...R1 all the nodes that equal TARGET
114    according to COMPARE given auxiliary data AUX.
115    Returns the number of nodes removed. */
116 size_t
117 ll_remove_equal (struct ll *r0, struct ll *r1, struct ll *target,
118                  ll_compare_func *compare, void *aux)
119 {
120   struct ll *x;
121   size_t count;
122
123   count = 0;
124   for (x = r0; x != r1; )
125     if (compare (x, target, aux) == 0)
126       {
127         x = ll_remove (x);
128         count++;
129       }
130     else
131       x = ll_next (x);
132
133   return count;
134 }
135
136 /* Removes from R0...R1 all the nodes for which PREDICATE returns
137    true given auxiliary data AUX.
138    Returns the number of nodes removed. */
139 size_t
140 ll_remove_if (struct ll *r0, struct ll *r1,
141               ll_predicate_func *predicate, void *aux)
142 {
143   struct ll *x;
144   size_t count;
145
146   count = 0;
147   for (x = r0; x != r1; )
148     if (predicate (x, aux))
149       {
150         x = ll_remove (x);
151         count++;
152       }
153     else
154       x = ll_next (x);
155
156   return count;
157 }
158
159 /* Returns the first node in R0...R1 that equals TARGET
160    according to COMPARE given auxiliary data AUX.
161    Returns R1 if no node in R0...R1 equals TARGET. */
162 struct ll *
163 ll_find_equal (const struct ll *r0, const struct ll *r1,
164                const struct ll *target,
165                ll_compare_func *compare, void *aux)
166 {
167   const struct ll *x;
168
169   for (x = r0; x != r1; x = ll_next (x))
170     if (compare (x, target, aux) == 0)
171       break;
172   return (struct ll *) x;
173 }
174
175 /* Returns the first node in R0...R1 for which PREDICATE returns
176    true given auxiliary data AUX.
177    Returns R1 if PREDICATE does not return true for any node in
178    R0...R1. */
179 struct ll *
180 ll_find_if (const struct ll *r0, const struct ll *r1,
181             ll_predicate_func *predicate, void *aux)
182 {
183   const struct ll *x;
184
185   for (x = r0; x != r1; x = ll_next (x))
186     if (predicate (x, aux))
187       break;
188   return (struct ll *) x;
189 }
190
191 /* Compares each pair of adjacent nodes in R0...R1
192    using COMPARE with auxiliary data AUX
193    and returns the first node of the first pair that compares
194    equal.
195    Returns R1 if no pair compares equal. */
196 struct ll *
197 ll_find_adjacent_equal (const struct ll *r0, const struct ll *r1,
198                         ll_compare_func *compare, void *aux)
199 {
200   if (r0 != r1)
201     {
202       const struct ll *x, *y;
203
204       for (x = r0, y = ll_next (x); y != r1; x = y, y = ll_next (y))
205         if (compare (x, y, aux) == 0)
206           return (struct ll *) x;
207     }
208
209   return (struct ll *) r1;
210 }
211
212 /* Returns the number of nodes in R0...R1.
213    Executes in O(n) time in the return value. */
214 size_t
215 ll_count_range (const struct ll *r0, const struct ll *r1)
216 {
217   const struct ll *x;
218   size_t count;
219
220   count = 0;
221   for (x = r0; x != r1; x = ll_next (x))
222     count++;
223   return count;
224 }
225
226 /* Counts and returns the number of nodes in R0...R1 that equal
227    TARGET according to COMPARE given auxiliary data AUX. */
228 size_t
229 ll_count_equal (const struct ll *r0, const struct ll *r1,
230                 const struct ll *target,
231                 ll_compare_func *compare, void *aux)
232 {
233   const struct ll *x;
234   size_t count;
235
236   count = 0;
237   for (x = r0; x != r1; x = ll_next (x))
238     if (compare (x, target, aux) == 0)
239       count++;
240   return count;
241 }
242
243 /* Counts and returns the number of nodes in R0...R1 for which
244    PREDICATE returns true given auxiliary data AUX. */
245 size_t
246 ll_count_if (const struct ll *r0, const struct ll *r1,
247              ll_predicate_func *predicate, void *aux)
248 {
249   const struct ll *x;
250   size_t count;
251
252   count = 0;
253   for (x = r0; x != r1; x = ll_next (x))
254     if (predicate (x, aux))
255       count++;
256   return count;
257 }
258
259 /* Returns the greatest node in R0...R1 according to COMPARE
260    given auxiliary data AUX.
261    Returns the first of multiple, equal maxima. */
262 struct ll *
263 ll_max (const struct ll *r0, const struct ll *r1,
264         ll_compare_func *compare, void *aux)
265 {
266   const struct ll *max = r0;
267   if (r0 != r1)
268     {
269       const struct ll *x;
270
271       for (x = ll_next (r0); x != r1; x = ll_next (x))
272         if (compare (x, max, aux) > 0)
273           max = x;
274     }
275   return (struct ll *) max;
276 }
277
278 /* Returns the least node in R0...R1 according to COMPARE given
279    auxiliary data AUX.
280    Returns the first of multiple, equal minima. */
281 struct ll *
282 ll_min (const struct ll *r0, const struct ll *r1,
283         ll_compare_func *compare, void *aux)
284 {
285   const struct ll *min = r0;
286   if (r0 != r1)
287     {
288       const struct ll *x;
289
290       for (x = ll_next (r0); x != r1; x = ll_next (x))
291         if (compare (x, min, aux) < 0)
292           min = x;
293     }
294   return (struct ll *) min;
295 }
296
297 /* Lexicographically compares A0...A1 to B0...B1.
298    Returns negative if A0...A1 < B0...B1,
299    zero if A0...A1 == B0...B1, and
300    positive if A0...A1 > B0...B1
301    according to COMPARE given auxiliary data AUX. */
302 int
303 ll_lexicographical_compare_3way (const struct ll *a0, const struct ll *a1,
304                                  const struct ll *b0, const struct ll *b1,
305                                  ll_compare_func *compare, void *aux)
306 {
307   for (;;)
308     if (b0 == b1)
309       return a0 != a1;
310     else if (a0 == a1)
311       return -1;
312     else
313       {
314         int cmp = compare (a0, b0, aux);
315         if (cmp != 0)
316           return cmp;
317
318         a0 = ll_next (a0);
319         b0 = ll_next (b0);
320       }
321 }
322
323 /* Calls ACTION with auxiliary data AUX
324    for every node in R0...R1 in order. */
325 void
326 ll_apply (struct ll *r0, struct ll *r1, ll_action_func *action, void *aux)
327 {
328   struct ll *ll;
329
330   for (ll = r0; ll != r1; ll = ll_next (ll))
331     action (ll, aux);
332 }
333
334 /* Reverses the order of nodes R0...R1. */
335 void
336 ll_reverse (struct ll *r0, struct ll *r1)
337 {
338   if (r0 != r1 && ll_next (r0) != r1)
339     {
340       struct ll *ll;
341
342       for (ll = r0; ll != r1; ll = ll->prev)
343         {
344           struct ll *tmp = ll->next;
345           ll->next = ll->prev;
346           ll->prev = tmp;
347         }
348       r0->next->next = r1->prev;
349       r1->prev->prev = r0->next;
350       r0->next = r1;
351       r1->prev = r0;
352     }
353 }
354
355 /* Arranges R0...R1 into the lexicographically next greater
356    permutation.  Returns true if successful.
357    If R0...R1 is already the lexicographically greatest
358    permutation of its elements (i.e. ordered from greatest to
359    smallest), arranges them into the lexicographically least
360    permutation (i.e. ordered from smallest to largest) and
361    returns false.
362    COMPARE with auxiliary data AUX is used to compare nodes. */
363 bool
364 ll_next_permutation (struct ll *r0, struct ll *r1,
365                      ll_compare_func *compare, void *aux)
366 {
367   if (r0 != r1)
368     {
369       struct ll *i = ll_prev (r1);
370       while (i != r0)
371         {
372           i = ll_prev (i);
373           if (compare (i, ll_next (i), aux) < 0)
374             {
375               struct ll *j;
376               for (j = ll_prev (r1); compare (i, j, aux) >= 0; j = ll_prev (j))
377                 continue;
378               ll_swap (i, j);
379               ll_reverse (ll_next (j), r1);
380               return true;
381             }
382         }
383
384       ll_reverse (r0, r1);
385     }
386
387   return false;
388 }
389
390 /* Arranges R0...R1 into the lexicographically next lesser
391    permutation.  Returns true if successful.
392    If R0...R1 is already the lexicographically least
393    permutation of its elements (i.e. ordered from smallest to
394    greatest), arranges them into the lexicographically greatest
395    permutation (i.e. ordered from largest to smallest) and
396    returns false.
397    COMPARE with auxiliary data AUX is used to compare nodes. */
398 bool
399 ll_prev_permutation (struct ll *r0, struct ll *r1,
400                      ll_compare_func *compare, void *aux)
401 {
402   if (r0 != r1)
403     {
404       struct ll *i = ll_prev (r1);
405       while (i != r0)
406         {
407           i = ll_prev (i);
408           if (compare (i, ll_next (i), aux) > 0)
409             {
410               struct ll *j;
411               for (j = ll_prev (r1); compare (i, j, aux) <= 0; j = ll_prev (j))
412                 continue;
413               ll_swap (i, j);
414               ll_reverse (ll_next (j), r1);
415               return true;
416             }
417         }
418
419       ll_reverse (r0, r1);
420     }
421
422   return false;
423 }
424
425 /* Sorts R0...R1 into ascending order
426    according to COMPARE given auxiliary data AUX.
427    In use, keep in mind that R0 may move during the sort, so that
428    afterward R0...R1 may denote a different range.
429    (On the other hand, R1 is fixed in place.)
430    The sort is stable; that is, it will not change the relative
431    order of nodes that compare equal.
432    Runs in O(n lg n) time in the number of nodes in the range. */
433 void
434 ll_sort (struct ll *r0, struct ll *r1, ll_compare_func *compare, void *aux)
435 {
436   struct ll *pre_r0;
437   size_t output_run_cnt;
438
439   if (r0 == r1 || ll_next (r0) == r1)
440     return;
441
442   pre_r0 = ll_prev (r0);
443   do
444     {
445       struct ll *a0 = ll_next (pre_r0);
446       for (output_run_cnt = 1; ; output_run_cnt++)
447         {
448           struct ll *a1 = ll_find_run (a0, r1, compare, aux);
449           struct ll *a2 = ll_find_run (a1, r1, compare, aux);
450           if (a1 == a2)
451             break;
452
453           a0 = ll_merge (a0, a1, a1, a2, compare, aux);
454         }
455     }
456   while (output_run_cnt > 1);
457 }
458
459 /* Finds the extent of a run of nodes of increasing value
460    starting at R0 and extending no farther than R1.
461    Returns the first node in R0...R1 that is less than the
462    preceding node, or R1 if R0...R1 are arranged in nondecreasing
463    order. */
464 struct ll *
465 ll_find_run (const struct ll *r0, const struct ll *r1,
466              ll_compare_func *compare, void *aux)
467 {
468   if (r0 != r1)
469     {
470       do
471         {
472           r0 = ll_next (r0);
473         }
474       while (r0 != r1 && compare (ll_prev (r0), r0, aux) <= 0);
475     }
476
477   return (struct ll *) r0;
478 }
479
480 /* Merges B0...B1 into A0...A1 according to COMPARE given
481    auxiliary data AUX.
482    The ranges may be in the same list or different lists, but
483    must not overlap.
484    Returns the end of the merged range.
485    The merge is "stable" if A0...A1 is considered to precede
486    B0...B1, regardless of their actual ordering.
487    Runs in O(n) time in the total number of nodes in the ranges. */
488 struct ll *
489 ll_merge (struct ll *a0, struct ll *a1, struct ll *b0, struct ll *b1,
490           ll_compare_func *compare, void *aux)
491 {
492   if (a0 != a1 && b0 != b1)
493     {
494       a1 = ll_prev (a1);
495       b1 = ll_prev (b1);
496       for (;;)
497         if (compare (a0, b0, aux) <= 0)
498           {
499             if (a0 == a1)
500               {
501                 ll_splice (ll_next (a0), b0, ll_next (b1));
502                 return ll_next (b1);
503               }
504             a0 = ll_next (a0);
505           }
506         else
507           {
508             if (b0 != b1)
509               {
510                 struct ll *x = b0;
511                 b0 = ll_remove (b0);
512                 ll_insert (a0, x);
513               }
514             else
515               {
516                 ll_splice (a0, b0, ll_next (b0));
517                 return ll_next (a1);
518               }
519           }
520     }
521   else
522     {
523       ll_splice (a0, b0, b1);
524       return b1;
525     }
526 }
527
528 /* Returns true if R0...R1 is sorted in ascending order according
529    to COMPARE given auxiliary data AUX, false otherwise. */
530 bool
531 ll_is_sorted (const struct ll *r0, const struct ll *r1,
532               ll_compare_func *compare, void *aux)
533 {
534   return ll_find_run (r0, r1, compare, aux) == r1;
535 }
536
537 /* Removes all but the first in each group of sequential
538    duplicates in R0...R1.  Duplicates are determined using
539    COMPARE given auxiliary data AUX.  Removed duplicates are
540    inserted before DUPS if it is nonnull; otherwise, their
541    identities are lost.
542    Only sequential duplicates are removed.  ll_sort() may be used
543    to bring duplicates together, or ll_sort_unique() can do both
544    at once. */
545 size_t
546 ll_unique (struct ll *r0, struct ll *r1, struct ll *dups,
547            ll_compare_func *compare, void *aux)
548 {
549   size_t count = 0;
550
551   if (r0 != r1)
552     {
553       struct ll *x = r0;
554       for (;;)
555         {
556           struct ll *y = ll_next (x);
557           if (y == r1)
558             {
559               count++;
560               break;
561             }
562
563           if (compare (x, y, aux) == 0)
564             {
565               ll_remove (y);
566               if (dups != NULL)
567                 ll_insert (dups, y);
568             }
569           else
570             {
571               x = y;
572               count++;
573             }
574         }
575     }
576
577   return count;
578 }
579
580 /* Sorts R0...R1 and removes duplicates.
581    Removed duplicates are inserted before DUPS if it is nonnull;
582    otherwise, their identities are lost.
583    Comparisons are made with COMPARE given auxiliary data AUX.
584    In use, keep in mind that R0 may move during the sort, so that
585    afterward R0...R1 may denote a different range.
586    (On the other hand, R1 is fixed in place.)
587    Runs in O(n lg n) time in the number of nodes in the range. */
588 void
589 ll_sort_unique (struct ll *r0, struct ll *r1, struct ll *dups,
590                 ll_compare_func *compare, void *aux)
591 {
592   struct ll *pre_r0 = ll_prev (r0);
593   ll_sort (r0, r1, compare, aux);
594   ll_unique (ll_next (pre_r0), r1, dups, compare, aux);
595 }
596
597 /* Inserts NEW_ELEM in the proper position in R0...R1, which must
598    be sorted according to COMPARE given auxiliary data AUX.
599    If NEW_ELEM is equal to one or more existing nodes in R0...R1,
600    then it is inserted after the existing nodes it equals.
601    Runs in O(n) time in the number of nodes in the range. */
602 void
603 ll_insert_ordered (struct ll *r0, struct ll *r1, struct ll *new_elem,
604                    ll_compare_func *compare, void *aux)
605 {
606   struct ll *x;
607
608   for (x = r0; x != r1; x = ll_next (x))
609     if (compare (x, new_elem, aux) > 0)
610       break;
611   ll_insert (x, new_elem);
612 }
613
614 /* Partitions R0...R1 into those nodes for which PREDICATE given
615    auxiliary data AUX returns true, followed by those for which
616    PREDICATE returns false.
617    Returns the first node in the "false" group, or R1 if
618    PREDICATE is true for every node in R0...R1.
619    The partition is "stable" in that the nodes in each group
620    retain their original relative order.
621    Runs in O(n) time in the number of nodes in the range. */
622 struct ll *
623 ll_partition (struct ll *r0, struct ll *r1,
624               ll_predicate_func *predicate, void *aux)
625 {
626   struct ll *t0, *t1;
627
628   for (;;)
629     {
630       if (r0 == r1)
631         return r0;
632       else if (!predicate (r0, aux))
633         break;
634
635       r0 = ll_next (r0);
636     }
637
638   for (t0 = r0;; t0 = t1)
639     {
640       do
641         {
642           t0 = ll_next (t0);
643           if (t0 == r1)
644             return r0;
645         }
646       while (!predicate (t0, aux));
647
648       t1 = t0;
649       do
650         {
651           t1 = ll_next (t1);
652           if (t1 == r1)
653             {
654               ll_splice (r0, t0, t1);
655               return r0;
656             }
657         }
658       while (predicate (t1, aux));
659
660       ll_splice (r0, t0, t1);
661     }
662 }
663
664 /* Verifies that R0...R1 is parititioned into a sequence of nodes
665    for which PREDICATE given auxiliary data AUX returns true,
666    followed by those for which PREDICATE returns false.
667    Returns a null pointer if R0...R1 is not partitioned this way.
668    Otherwise, returns the first node in the "false" group, or R1
669    if PREDICATE is true for every node in R0...R1. */
670 struct ll *
671 ll_find_partition (const struct ll *r0, const struct ll *r1,
672                    ll_predicate_func *predicate, void *aux)
673 {
674   const struct ll *partition, *x;
675
676   for (partition = r0; partition != r1; partition = ll_next (partition))
677     if (!predicate (partition, aux))
678       break;
679
680   for (x = partition; x != r1; x = ll_next (x))
681     if (predicate (x, aux))
682       return NULL;
683
684   return (struct ll *) partition;
685 }
686 \f