gui: Fix behavior of print preview in psppire-output-window.
[pspp] / src / libpspp / llx.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 /* 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 "libpspp/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 has data TARGET.
223    Returns NULL if no node in R0...R1 equals TARGET. */
224 struct llx *
225 llx_find (const struct llx *r0, const struct llx *r1, const void *target)
226 {
227   const struct llx *x;
228
229   for (x = r0; x != r1; x = llx_next (x))
230     if (llx_data (x) == target)
231       return CONST_CAST (struct llx *, x);
232
233   return NULL;
234 }
235
236 /* Returns the first node in R0...R1 that equals TARGET
237    according to COMPARE given auxiliary data AUX.
238    Returns R1 if no node in R0...R1 equals TARGET. */
239 struct llx *
240 llx_find_equal (const struct llx *r0, const struct llx *r1,
241                 const void *target,
242                 llx_compare_func *compare, void *aux)
243 {
244   const struct llx *x;
245
246   for (x = r0; x != r1; x = llx_next (x))
247     if (compare (llx_data (x), target, aux) == 0)
248       break;
249   return CONST_CAST (struct llx *, x);
250 }
251
252 /* Returns the first node in R0...R1 for which PREDICATE returns
253    true given auxiliary data AUX.
254    Returns R1 if PREDICATE does not return true for any node in
255    R0...R1 . */
256 struct llx *
257 llx_find_if (const struct llx *r0, const struct llx *r1,
258              llx_predicate_func *predicate, void *aux)
259 {
260   const struct llx *x;
261
262   for (x = r0; x != r1; x = llx_next (x))
263     if (predicate (llx_data (x), aux))
264       break;
265   return CONST_CAST (struct llx *, x);
266 }
267
268 /* Compares each pair of adjacent nodes in R0...R1
269    using COMPARE with auxiliary data AUX
270    and returns the first node of the first pair that compares
271    equal.
272    Returns R1 if no pair compares equal. */
273 struct llx *
274 llx_find_adjacent_equal (const struct llx *r0, const struct llx *r1,
275                          llx_compare_func *compare, void *aux)
276 {
277   if (r0 != r1)
278     {
279       const struct llx *x, *y;
280
281       for (x = r0, y = llx_next (x); y != r1; x = y, y = llx_next (y))
282         if (compare (llx_data (x), llx_data (y), aux) == 0)
283           return CONST_CAST (struct llx *, x);
284     }
285
286   return CONST_CAST (struct llx *, r1);
287 }
288
289 /* Returns the number of nodes in R0...R1.
290    Executes in O(n) time in the return value. */
291 size_t
292 llx_count_range (const struct llx *r0, const struct llx *r1)
293 {
294   return ll_count_range (&r0->ll, &r1->ll);
295 }
296
297 /* Counts and returns the number of nodes in R0...R1 that equal
298    TARGET according to COMPARE given auxiliary data AUX. */
299 size_t
300 llx_count_equal (const struct llx *r0, const struct llx *r1,
301                  const void *target,
302                  llx_compare_func *compare, void *aux)
303 {
304   const struct llx *x;
305   size_t count;
306
307   count = 0;
308   for (x = r0; x != r1; x = llx_next (x))
309     if (compare (llx_data (x), target, aux) == 0)
310       count++;
311   return count;
312 }
313
314 /* Counts and returns the number of nodes in R0...R1 for which
315    PREDICATE returns true given auxiliary data AUX. */
316 size_t
317 llx_count_if (const struct llx *r0, const struct llx *r1,
318               llx_predicate_func *predicate, void *aux)
319 {
320   const struct llx *x;
321   size_t count;
322
323   count = 0;
324   for (x = r0; x != r1; x = llx_next (x))
325     if (predicate (llx_data (x), aux))
326       count++;
327   return count;
328 }
329
330 /* Returns the greatest node in R0...R1 according to COMPARE
331    given auxiliary data AUX.
332    Returns the first of multiple, equal maxima. */
333 struct llx *
334 llx_max (const struct llx *r0, const struct llx *r1,
335          llx_compare_func *compare, void *aux)
336 {
337   const struct llx *max = r0;
338   if (r0 != r1)
339     {
340       struct llx *x;
341
342       for (x = llx_next (r0); x != r1; x = llx_next (x))
343         if (compare (llx_data (x), llx_data (max), aux) > 0)
344           max = x;
345     }
346   return CONST_CAST (struct llx *, max);
347 }
348
349 /* Returns the least node in R0...R1 according to COMPARE given
350    auxiliary data AUX.
351    Returns the first of multiple, equal minima. */
352 struct llx *
353 llx_min (const struct llx *r0, const struct llx *r1,
354          llx_compare_func *compare, void *aux)
355 {
356   const struct llx *min = r0;
357   if (r0 != r1)
358     {
359       struct llx *x;
360
361       for (x = llx_next (r0); x != r1; x = llx_next (x))
362         if (compare (llx_data (x), llx_data (min), aux) < 0)
363           min = x;
364     }
365   return CONST_CAST (struct llx *, min);
366 }
367
368 /* Lexicographically compares A0...A1 to B0...B1.
369    Returns negative if A0...A1 < B0...B1,
370    zero if A0...A1 == B0...B1, and
371    positive if A0...A1 > B0...B1
372    according to COMPARE given auxiliary data AUX. */
373 int
374 llx_lexicographical_compare_3way (const struct llx *a0, const struct llx *a1,
375                                   const struct llx *b0, const struct llx *b1,
376                                   llx_compare_func *compare, void *aux)
377 {
378   for (;;)
379     if (b0 == b1)
380       return a0 != a1;
381     else if (a0 == a1)
382       return -1;
383     else
384       {
385         int cmp = compare (llx_data (a0), llx_data (b0), aux);
386         if (cmp != 0)
387           return cmp;
388
389         a0 = llx_next (a0);
390         b0 = llx_next (b0);
391       }
392 }
393
394 /* Calls ACTION with auxiliary data AUX
395    for every node in R0...R1 in order. */
396 void
397 llx_apply (struct llx *r0, struct llx *r1,
398            llx_action_func *action, void *aux)
399 {
400   struct llx *llx;
401
402   for (llx = r0; llx != r1; llx = llx_next (llx))
403     action (llx_data (llx), aux);
404 }
405
406 /* Reverses the order of nodes R0...R1. */
407 void
408 llx_reverse (struct llx *r0, struct llx *r1)
409 {
410   ll_reverse (&r0->ll, &r1->ll);
411 }
412
413 /* Arranges R0...R1 into the lexicographically next greater
414    permutation.  Returns true if successful.
415    If R0...R1 is already the lexicographically greatest
416    permutation of its elements (i.e. ordered from greatest to
417    smallest), arranges them into the lexicographically least
418    permutation (i.e. ordered from smallest to largest) and
419    returns false.
420    COMPARE with auxiliary data AUX is used to compare nodes. */
421 bool
422 llx_next_permutation (struct llx *r0, struct llx *r1,
423                       llx_compare_func *compare, void *aux)
424 {
425   if (r0 != r1)
426     {
427       struct llx *i = llx_prev (r1);
428       while (i != r0)
429         {
430           i = llx_prev (i);
431           if (compare (llx_data (i), llx_data (llx_next (i)), aux) < 0)
432             {
433               struct llx *j;
434               for (j = llx_prev (r1);
435                    compare (llx_data (i), llx_data (j), aux) >= 0;
436                    j = llx_prev (j))
437                 continue;
438               llx_swap (i, j);
439               llx_reverse (llx_next (j), r1);
440               return true;
441             }
442         }
443
444       llx_reverse (r0, r1);
445     }
446
447   return false;
448 }
449
450 /* Arranges R0...R1 into the lexicographically next lesser
451    permutation.  Returns true if successful.
452    If R0...R1 is already the lexicographically least
453    permutation of its elements (i.e. ordered from smallest to
454    greatest), arranges them into the lexicographically greatest
455    permutation (i.e. ordered from largest to smallest) and
456    returns false.
457    COMPARE with auxiliary data AUX is used to compare nodes. */
458 bool
459 llx_prev_permutation (struct llx *r0, struct llx *r1,
460                       llx_compare_func *compare, void *aux)
461 {
462   if (r0 != r1)
463     {
464       struct llx *i = llx_prev (r1);
465       while (i != r0)
466         {
467           i = llx_prev (i);
468           if (compare (llx_data (i), llx_data (llx_next (i)), aux) > 0)
469             {
470               struct llx *j;
471               for (j = llx_prev (r1);
472                    compare (llx_data (i), llx_data (j), aux) <= 0;
473                    j = llx_prev (j))
474                 continue;
475               llx_swap (i, j);
476               llx_reverse (llx_next (j), r1);
477               return true;
478             }
479         }
480
481       llx_reverse (r0, r1);
482     }
483
484   return false;
485 }
486
487 /* Sorts R0...R1 into ascending order
488    according to COMPARE given auxiliary data AUX.
489    In use, keep in mind that R0 may move during the sort, so that
490    afterward R0...R1 may denote a different range.
491    (On the other hand, R1 is fixed in place.)
492    Runs in O(n lg n) time in the number of nodes in the range. */
493 void
494 llx_sort (struct llx *r0, struct llx *r1, llx_compare_func *compare, void *aux)
495 {
496   struct llx *pre_r0;
497   size_t output_run_cnt;
498
499   if (r0 == r1 || llx_next (r0) == r1)
500     return;
501
502   pre_r0 = llx_prev (r0);
503   do
504     {
505       struct llx *a0 = llx_next (pre_r0);
506       for (output_run_cnt = 1; ; output_run_cnt++)
507         {
508           struct llx *a1 = llx_find_run (a0, r1, compare, aux);
509           struct llx *a2 = llx_find_run (a1, r1, compare, aux);
510           if (a1 == a2)
511             break;
512
513           a0 = llx_merge (a0, a1, a1, a2, compare, aux);
514         }
515     }
516   while (output_run_cnt > 1);
517 }
518
519 /* Finds the extent of a run of nodes of increasing value
520    starting at R0 and extending no farther than R1.
521    Returns the first node in R0...R1 that is less than the
522    preceding node, or R1 if R0...R1 are arranged in nondecreasing
523    order. */
524 struct llx *
525 llx_find_run (const struct llx *r0, const struct llx *r1,
526               llx_compare_func *compare, void *aux)
527 {
528   if (r0 != r1)
529     {
530       do
531         {
532           r0 = llx_next (r0);
533         }
534       while (r0 != r1 && compare (llx_data (llx_prev (r0)),
535                                   llx_data (r0), aux) <= 0);
536     }
537
538   return CONST_CAST (struct llx *, r0);
539 }
540
541 /* Merges B0...B1 into A0...A1 according to COMPARE given
542    auxiliary data AUX.
543    The ranges may be in the same list or different lists, but
544    must not overlap.
545    The merge is "stable" if A0...A1 is considered to precede
546    B0...B1, regardless of their actual ordering.
547    Runs in O(n) time in the total number of nodes in the ranges. */
548 struct llx *
549 llx_merge (struct llx *a0, struct llx *a1, struct llx *b0, struct llx *b1,
550            llx_compare_func *compare, void *aux)
551 {
552   if (a0 != a1 && b0 != b1)
553     {
554       a1 = llx_prev (a1);
555       b1 = llx_prev (b1);
556       for (;;)
557         if (compare (llx_data (a0), llx_data (b0), aux) <= 0)
558           {
559             if (a0 == a1)
560               {
561                 llx_splice (llx_next (a0), b0, llx_next (b1));
562                 return llx_next (b1);
563               }
564             a0 = llx_next (a0);
565           }
566         else
567           {
568             if (b0 != b1)
569               {
570                 struct llx *x = b0;
571                 b0 = llx_next (b0);
572                 llx_splice (a0, x, b0);
573               }
574             else
575               {
576                 llx_splice (a0, b0, llx_next (b0));
577                 return llx_next (a1);
578               }
579           }
580     }
581   else
582     {
583       llx_splice (a0, b0, b1);
584       return b1;
585     }
586 }
587
588 /* Returns true if R0...R1 is sorted in ascending order according
589    to COMPARE given auxiliary data AUX,
590    false otherwise. */
591 bool
592 llx_is_sorted (const struct llx *r0, const struct llx *r1,
593                llx_compare_func *compare, void *aux)
594 {
595   return llx_find_run (r0, r1, compare, aux) == r1;
596 }
597
598 /* Removes all but the first in each group of sequential
599    duplicates in R0...R1.  Duplicates are determined using
600    COMPARE given auxiliary data AUX.  Removed duplicates are
601    inserted before DUPS if it is nonnull; otherwise, the removed
602    duplicates are freed with MANAGER.
603    Only sequential duplicates are removed.  llx_sort() may be used
604    to bring duplicates together, or llx_sort_unique() can do both
605    at once. */
606 size_t
607 llx_unique (struct llx *r0, struct llx *r1, struct llx *dups,
608             llx_compare_func *compare, void *aux,
609             const struct llx_manager *manager)
610 {
611   size_t count = 0;
612
613   if (r0 != r1)
614     {
615       struct llx *x = r0;
616       for (;;)
617         {
618           struct llx *y = llx_next (x);
619           if (y == r1)
620             {
621               count++;
622               break;
623             }
624
625           if (compare (llx_data (x), llx_data (y), aux) == 0)
626             {
627               if (dups != NULL)
628                 llx_splice (dups, y, llx_next (y));
629               else
630                 llx_remove (y, manager);
631             }
632           else
633             {
634               x = y;
635               count++;
636             }
637         }
638     }
639
640   return count;
641 }
642
643 /* Sorts R0...R1 and removes duplicates.
644    Removed duplicates are inserted before DUPS if it is nonnull;
645    otherwise, the removed duplicates are freed with MANAGER.
646    Comparisons are made with COMPARE given auxiliary data AUX.
647    In use, keep in mind that R0 may move during the sort, so that
648    afterward R0...R1 may denote a different range.
649    (On the other hand, R1 is fixed in place.)
650    Runs in O(n lg n) time in the number of nodes in the range. */
651 void
652 llx_sort_unique (struct llx *r0, struct llx *r1, struct llx *dups,
653                  llx_compare_func *compare, void *aux,
654                  const struct llx_manager *manager)
655 {
656   struct llx *pre_r0 = llx_prev (r0);
657   llx_sort (r0, r1, compare, aux);
658   llx_unique (llx_next (pre_r0), r1, dups, compare, aux, manager);
659 }
660
661 /* Inserts DATA in the proper position in R0...R1, which must
662    be sorted according to COMPARE given auxiliary data AUX.
663    If DATA is equal to one or more existing nodes in R0...R1,
664    then it is inserted after the existing nodes it equals.
665    Returns the new node (allocated with MANAGER), or a null
666    pointer if memory allocation failed.
667    Runs in O(n) time in the number of nodes in the range. */
668 struct llx *
669 llx_insert_ordered (struct llx *r0, struct llx *r1, void *data,
670                     llx_compare_func *compare, void *aux,
671                     const struct llx_manager *manager)
672 {
673   struct llx *x;
674
675   for (x = r0; x != r1; x = llx_next (x))
676     if (compare (llx_data (x), data, aux) > 0)
677       break;
678   return llx_insert (x, data, manager);
679 }
680
681 /* Partitions R0...R1 into those nodes for which PREDICATE given
682    auxiliary data AUX returns true, followed by those for which
683    PREDICATE returns false.
684    Returns the first node in the "false" group, or R1 if
685    PREDICATE is true for every node in R0...R1.
686    The partition is "stable" in that the nodes in each group
687    retain their original relative order.
688    Runs in O(n) time in the number of nodes in the range. */
689 struct llx *
690 llx_partition (struct llx *r0, struct llx *r1,
691                llx_predicate_func *predicate, void *aux)
692 {
693   struct llx *t0, *t1;
694
695   for (;;)
696     {
697       if (r0 == r1)
698         return r0;
699       else if (!predicate (llx_data (r0), aux))
700         break;
701
702       r0 = llx_next (r0);
703     }
704
705   for (t0 = r0;; t0 = t1)
706     {
707       do
708         {
709           t0 = llx_next (t0);
710           if (t0 == r1)
711             return r0;
712         }
713       while (!predicate (llx_data (t0), aux));
714
715       t1 = t0;
716       do
717         {
718           t1 = llx_next (t1);
719           if (t1 == r1)
720             {
721               llx_splice (r0, t0, t1);
722               return r0;
723             }
724         }
725       while (predicate (llx_data (t1), aux));
726
727       llx_splice (r0, t0, t1);
728     }
729 }
730
731 /* Verifies that R0...R1 is parititioned into a sequence of nodes
732    for which PREDICATE given auxiliary data AUX returns true,
733    followed by those for which PREDICATE returns false.
734    Returns a null pointer if R0...R1 is not partitioned this way.
735    Otherwise, returns the first node in the "false" group, or R1
736    if PREDICATE is true for every node in R0...R1. */
737 struct llx *
738 llx_find_partition (const struct llx *r0, const struct llx *r1,
739                     llx_predicate_func *predicate, void *aux)
740 {
741   const struct llx *partition, *x;
742
743   for (partition = r0; partition != r1; partition = llx_next (partition))
744     if (!predicate (llx_data (partition), aux))
745       break;
746
747   for (x = partition; x != r1; x = llx_next (x))
748     if (predicate (llx_data (x), aux))
749       return NULL;
750
751   return CONST_CAST (struct llx *, partition);
752 }
753 \f
754 /* Allocates and returns a node using malloc. */
755 static struct llx *
756 malloc_allocate_node (void *aux UNUSED)
757 {
758   return malloc (sizeof (struct llx));
759 }
760
761 /* Releases node LLX with free. */
762 static void
763 malloc_release_node (struct llx *llx, void *aux UNUSED)
764 {
765   free (llx);
766 }
767
768 /* Manager that uses the standard malloc and free routines. */
769 const struct llx_manager llx_malloc_mgr =
770   {
771     malloc_allocate_node,
772     malloc_release_node,
773     NULL,
774   };