Add comment explaining the meaning of encoding to data_out
[pspp-builds.git] / src / libpspp / abt.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2007 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 /* Augmented binary tree (ABT) data structure. */
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 abt-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/abt.h>
32
33 #include <stdbool.h>
34
35 #include <libpspp/assertion.h>
36
37 static struct abt_node **down_link (struct abt *, struct abt_node *);
38 static struct abt_node *skew (struct abt *, struct abt_node *);
39 static struct abt_node *split (struct abt *, struct abt_node *);
40
41 /* Initializes ABT as an empty ABT that uses COMPARE and
42    REAUGMENT functions, passing in AUX as auxiliary data.
43
44    The comparison function is optional.  If it is null, this
45    indicates that the tree is being used for its augmentations
46    only.  ABT functions that compare nodes may not be used with
47    trees that lack comparison functions; contrariwise, other
48    functions that could disrupt the ordering of a tree may not be
49    used if a comparison function is specified.  Refer to
50    individual function descriptions for details. */
51 void
52 abt_init (struct abt *abt,
53           abt_compare_func *compare,
54           abt_reaugment_func *reaugment,
55           const void *aux)
56 {
57   assert (reaugment != NULL);
58   abt->root = NULL;
59   abt->compare = compare;
60   abt->reaugment = reaugment;
61   abt->aux = aux;
62 }
63
64 /* Inserts the given NODE into ABT.
65    Returns a null pointer if successful.
66    Returns the existing node already in ABT equal to NODE, on
67    failure.
68    This function may be used only if ABT has a comparison
69    function. */
70 struct abt_node *
71 abt_insert (struct abt *abt, struct abt_node *node)
72 {
73   node->down[0] = NULL;
74   node->down[1] = NULL;
75   node->level = 1;
76
77   if (abt->root == NULL)
78     {
79       abt->root = node;
80       node->up = NULL;
81       abt_reaugmented (abt, node);
82     }
83   else
84     {
85       struct abt_node *p = abt->root;
86       for (;;)
87         {
88           int cmp, dir;
89
90           cmp = abt->compare (node, p, abt->aux);
91           if (cmp == 0)
92             return p;
93
94           dir = cmp > 0;
95           if (p->down[dir] == NULL)
96             {
97               p->down[dir] = node;
98               node->up = p;
99               abt_reaugmented (abt, node);
100               break;
101             }
102           p = p->down[dir];
103         }
104     }
105
106   while ((node = node->up) != NULL)
107     {
108       node = skew (abt, node);
109       node = split (abt, node);
110     }
111
112   return NULL;
113 }
114
115 /* Inserts NODE before or after node P in ABT, depending on the
116    value of AFTER.
117    If P is null, then the node is inserted as the first node in
118    the tree, if AFTER is true, or the last node, if AFTER is
119    false. */
120 static inline void
121 insert_relative (struct abt *abt, const struct abt_node *p, bool after,
122                  struct abt_node *node)
123 {
124   node->down[0] = NULL;
125   node->down[1] = NULL;
126   node->level = 1;
127
128   if (abt->root == NULL)
129     {
130       assert (p == NULL);
131       abt->root = node;
132       node->up = NULL;
133       abt_reaugmented (abt, node);
134     }
135   else
136     {
137       int dir = after;
138       if (p == NULL)
139         {
140           p = abt->root;
141           dir = !after;
142         }
143       while (p->down[dir] != NULL)
144         {
145           p = p->down[dir];
146           dir = !after;
147         }
148       ((struct abt_node *) p)->down[dir] = node;
149       node->up = (struct abt_node *) p;
150       abt_reaugmented (abt, node);
151     }
152
153   while ((node = node->up) != NULL)
154     {
155       node = skew (abt, node);
156       node = split (abt, node);
157     }
158 }
159
160 /* Inserts NODE after node P in ABT.
161    If P is null, then the node is inserted as the first node in
162    the tree.
163    This function may be used only if ABT lacks a comparison
164    function. */
165 void
166 abt_insert_after (struct abt *abt,
167                   const struct abt_node *p, struct abt_node *node)
168 {
169   assert (abt->compare == NULL);
170   insert_relative (abt, p, true, node);
171 }
172
173 /* Inserts NODE before node P in ABT.
174    If P is null, then the node is inserted as the last node in
175    the tree.
176    This function may be used only if ABT lacks a comparison
177    function. */
178 void
179 abt_insert_before (struct abt *abt,
180                    const struct abt_node *p, struct abt_node *node)
181 {
182   assert (abt->compare == NULL);
183   insert_relative (abt, p, false, node);
184 }
185
186 /* Deletes P from ABT. */
187 void
188 abt_delete (struct abt *abt, struct abt_node *p)
189 {
190   struct abt_node **q = down_link (abt, p);
191   struct abt_node *r = p->down[1];
192   if (r == NULL)
193     {
194       *q = NULL;
195       p = p->up;
196     }
197   else if (r->down[0] == NULL)
198     {
199       r->down[0] = p->down[0];
200       *q = r;
201       r->up = p->up;
202       if (r->down[0] != NULL)
203         r->down[0]->up = r;
204       r->level = p->level;
205       p = r;
206     }
207   else
208     {
209       struct abt_node *s = r->down[0];
210       while (s->down[0] != NULL)
211         s = s->down[0];
212       r = s->up;
213       r->down[0] = s->down[1];
214       s->down[0] = p->down[0];
215       s->down[1] = p->down[1];
216       *q = s;
217       s->down[0]->up = s;
218       s->down[1]->up = s;
219       s->up = p->up;
220       s->level = p->level;
221       if (r->down[0] != NULL)
222         r->down[0]->up = r;
223       p = r;
224     }
225   abt_reaugmented (abt, p);
226
227   for (; p != NULL; p = p->up)
228     if ((p->down[0] != NULL ? p->down[0]->level : 0) < p->level - 1
229         || (p->down[1] != NULL ? p->down[1]->level : 0) < p->level - 1)
230       {
231         p->level--;
232         if (p->down[1] != NULL && p->down[1]->level > p->level)
233           p->down[1]->level = p->level;
234
235         p = skew (abt, p);
236         skew (abt, p->down[1]);
237         if (p->down[1]->down[1] != NULL)
238           skew (abt, p->down[1]->down[1]);
239
240         p = split (abt, p);
241         split (abt, p->down[1]);
242       }
243 }
244
245 /* Returns the node with minimum value in ABT, or a null pointer
246    if ABT is empty. */
247 struct abt_node *
248 abt_first (const struct abt *abt)
249 {
250   struct abt_node *p = abt->root;
251   if (p != NULL)
252     while (p->down[0] != NULL)
253       p = p->down[0];
254   return p;
255 }
256
257 /* Returns the node with maximum value in ABT, or a null pointer
258    if ABT is empty. */
259 struct abt_node *
260 abt_last (const struct abt *abt)
261 {
262   struct abt_node *p = abt->root;
263   if (p != NULL)
264     while (p->down[1] != NULL)
265       p = p->down[1];
266   return p;
267 }
268
269 /* Searches ABT for a node equal to TARGET.
270    Returns the node if found, or a null pointer otherwise.
271    This function may be used only if ABT has a comparison
272    function. */
273 struct abt_node *
274 abt_find (const struct abt *abt, const struct abt_node *target)
275 {
276   const struct abt_node *p;
277   int cmp;
278
279   for (p = abt->root; p != NULL; p = p->down[cmp > 0])
280     {
281       cmp = abt->compare (target, p, abt->aux);
282       if (cmp == 0)
283         return (struct abt_node *) p;
284     }
285
286   return NULL;
287 }
288
289 /* Returns the node in ABT following P in in-order.
290    If P is null, returns the minimum node in ABT.
291    Returns a null pointer if P is the maximum node in ABT or if P
292    is null and ABT is empty. */
293 struct abt_node *
294 abt_next (const struct abt *abt, const struct abt_node *p)
295 {
296   if (p == NULL)
297     return abt_first (abt);
298   else if (p->down[1] == NULL)
299     {
300       struct abt_node *q;
301       for (q = p->up; ; p = q, q = q->up)
302         if (q == NULL || p == q->down[0])
303           return q;
304     }
305   else
306     {
307       p = p->down[1];
308       while (p->down[0] != NULL)
309         p = p->down[0];
310       return (struct abt_node *) p;
311     }
312 }
313
314 /* Returns the node in ABT preceding P in in-order.
315    If P is null, returns the maximum node in ABT.
316    Returns a null pointer if P is the minimum node in ABT or if P
317    is null and ABT is empty. */
318 struct abt_node *
319 abt_prev (const struct abt *abt, const struct abt_node *p)
320 {
321   if (p == NULL)
322     return abt_last (abt);
323   else if (p->down[0] == NULL)
324     {
325       struct abt_node *q;
326       for (q = p->up; ; p = q, q = q->up)
327         if (q == NULL || p == q->down[1])
328           return q;
329     }
330   else
331     {
332       p = p->down[0];
333       while (p->down[1] != NULL)
334         p = p->down[1];
335       return (struct abt_node *) p;
336     }
337 }
338
339 /* Calls ABT's reaugmentation function to compensate for
340    augmentation data in P having been modified.  Use abt_changed,
341    instead, if the key data in P has changed.
342
343    It is not safe to update more than one node's augmentation
344    data, then to call this function for each node.  Instead,
345    update a single node's data, call this function, update
346    another node's data, and so on.  Alternatively, remove all
347    affected nodes from the tree, update their values, then
348    re-insert all of them. */
349 void
350 abt_reaugmented (const struct abt *abt, struct abt_node *p)
351 {
352   for (; p != NULL; p = p->up)
353     abt->reaugment (p, p->down[0], p->down[1], abt->aux);
354 }
355
356 /* Moves P around in ABT to compensate for its key having
357    changed.  Returns a null pointer if successful.  If P's new
358    value is equal to that of some other node in ABT, returns the
359    other node after removing P from ABT.
360
361    This function is an optimization only if it is likely that P
362    can actually retain its relative position in ABT, e.g. its key
363    has only been adjusted slightly.  Otherwise, it is more
364    efficient to simply remove P from ABT, change its key, and
365    re-insert P.
366
367    It is not safe to update more than one node's key, then to
368    call this function for each node.  Instead, update a single
369    node's key, call this function, update another node's key, and
370    so on.  Alternatively, remove all affected nodes from the
371    tree, update their keys, then re-insert all of them.
372
373    This function may be used only if ABT has a comparison
374    function.  If it doesn't, then you probably just want
375    abt_reaugmented. */
376 struct abt_node *
377 abt_changed (struct abt *abt, struct abt_node *p)
378 {
379   struct abt_node *prev = abt_prev (abt, p);
380   struct abt_node *next = abt_next (abt, p);
381
382   if ((prev != NULL && abt->compare (prev, p, abt->aux) >= 0)
383       || (next != NULL && abt->compare (p, next, abt->aux) >= 0))
384     {
385       abt_delete (abt, p);
386       return abt_insert (abt, p);
387     }
388   else
389     {
390       abt_reaugmented (abt, p);
391       return NULL;
392     }
393 }
394
395 /* ABT nodes may be moved around in memory as necessary, e.g. as
396    the result of an realloc operation on a block that contains a
397    node.  Once this is done, call this function passing node P
398    that was moved and its ABT before attempting any other
399    operation on ABT.
400
401    It is not safe to move more than one node, then to call this
402    function for each node.  Instead, move a single node, call
403    this function, move another node, and so on.  Alternatively,
404    remove all affected nodes from the tree, move them, then
405    re-insert all of them.
406
407    This function may be used only if ABT has a comparison
408    function. */
409 void
410 abt_moved (struct abt *abt, struct abt_node *p)
411 {
412   if (p->up != NULL)
413     {
414       int d = p->up->down[0] == NULL || abt->compare (p, p->up, abt->aux) > 0;
415       p->up->down[d] = p;
416     }
417   else
418     abt->root = p;
419   if (p->down[0] != NULL)
420     p->down[0]->up = p;
421   if (p->down[1] != NULL)
422     p->down[1]->up = p;
423 }
424 \f
425 /* Returns the address of the pointer that points down to P
426    within ABT. */
427 static struct abt_node **
428 down_link (struct abt *abt, struct abt_node *p)
429 {
430   return (p->up != NULL
431           ? &p->up->down[p->up->down[0] != p]
432           : &abt->root);
433 }
434
435 /* Remove a left "horizontal link" at A, if present.
436    Returns the node that occupies the position previously
437    occupied by A. */
438 static struct abt_node *
439 skew (struct abt *abt, struct abt_node *a)
440 {
441   struct abt_node *b = a->down[0];
442   if (b != NULL && b->level == a->level)
443     {
444       /* Rotate right. */
445       a->down[0] = b->down[1];
446       b->down[1] = a;
447       *down_link (abt, a) = b;
448
449       if (a->down[0] != NULL)
450         a->down[0]->up = a;
451       b->up = a->up;
452       a->up = b;
453
454       abt->reaugment (a, a->down[0], a->down[1], abt->aux);
455       abt->reaugment (b, b->down[0], b->down[1], abt->aux);
456
457       return b;
458     }
459   else
460     return a;
461 }
462
463 /* Removes a pair of consecutive right "horizontal links" at A,
464    if present.
465    Returns the node that occupies the position previously
466    occupied by A. */
467 static struct abt_node *
468 split (struct abt *abt, struct abt_node *a)
469 {
470   struct abt_node *b = a->down[1];
471   if (b != NULL && b->down[1] != NULL && b->down[1]->level == a->level)
472     {
473       /* Rotate left. */
474       a->down[1] = b->down[0];
475       b->down[0] = a;
476       *down_link (abt, a) = b;
477
478       if (a->down[1] != NULL)
479         a->down[1]->up = a;
480       b->up = a->up;
481       a->up = b;
482
483       b->level++;
484
485       abt->reaugment (a, a->down[0], a->down[1], abt->aux);
486       abt->reaugment (b, b->down[0], b->down[1], abt->aux);
487
488       return b;
489     }
490   else
491     return a;
492 }