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