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