Flush the journal after every write.
[pspp] / src / libpspp / tower.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2007, 2009 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 #include <config.h>
18
19 #include <libpspp/tower.h>
20
21 #include <limits.h>
22
23 #include <libpspp/assertion.h>
24 #include <libpspp/cast.h>
25 #include <libpspp/compiler.h>
26
27 static struct tower_node *abt_to_tower_node (const struct abt_node *);
28 static struct tower_node *first_node (const struct tower *);
29 static struct tower_node *last_node (const struct tower *);
30 static struct tower_node *next_node (const struct tower *,
31                                      const struct tower_node *);
32 static struct tower_node *prev_node (const struct tower *,
33                                      const struct tower_node *);
34 static unsigned long int get_subtree_size (const struct abt_node *);
35 static unsigned long int get_subtree_count (const struct abt_node *);
36 static void reaugment_tower_node (struct abt_node *,
37                                   const struct abt_node *,
38                                   const struct abt_node *,
39                                   const void *aux);
40
41 /* Returns the height of the bottom of the given tower NODE.
42
43    The performance of this function is O(lg n) in the number of
44    nodes in the tower.  It is often possible to avoid calling
45    this function, either by taking advantage of the NODE_START
46    parameter to tower_lookup or by incrementally keeping track of
47    height while iterating through a tower.  In the former case
48    the asymptotic performance is no different, since tower_lookup
49    is also O(lg n), but in the latter case performance improves
50    from O(lg n) to O(1). */
51 unsigned long int
52 tower_node_get_level (const struct tower_node *node)
53 {
54   const struct abt_node *p = &node->abt_node;
55   unsigned long level = get_subtree_size (p->down[0]);
56   while (p->up != NULL) 
57     {
58       if (p == p->up->down[1])
59         level += (get_subtree_size (p->up->down[0]) 
60                   + abt_to_tower_node (p->up)->size);
61       p = p->up;
62     }
63   return level;
64 }
65
66 /* Returns the index of the given tower NODE.
67
68    The performance of this function is O(lg n) in the number of
69    nodes in the tower.  It is often possible to avoid calling
70    this function by keeping track of the index while iterating
71    through a tower.  Doing so when possible will improve
72    performance from O(lg n) to O(1). */
73 unsigned long int
74 tower_node_get_index (const struct tower_node *node)
75 {
76   const struct abt_node *p = &node->abt_node;
77   unsigned long index = get_subtree_count (p->down[0]);
78   while (p->up != NULL) 
79     {
80       if (p == p->up->down[1])
81         index += get_subtree_count (p->up->down[0]) + 1;
82       p = p->up;
83     }
84   return index;
85 }
86
87 /* Initializes T as an empty tower. */
88 void
89 tower_init (struct tower *t)
90 {
91   abt_init (&t->abt, NULL, reaugment_tower_node, NULL);
92   t->cache_bottom = ULONG_MAX;
93 }
94
95 /* Returns true if T contains no nodes, false otherwise. */
96 bool
97 tower_is_empty (const struct tower *t)
98 {
99   return t->abt.root == NULL;
100 }
101
102 /* Returns the number of nodes in tower T. */
103 unsigned long int
104 tower_count (const struct tower *t)
105 {
106   return get_subtree_count (t->abt.root);
107 }
108
109 /* Returns the total height of tower T. */
110 unsigned long
111 tower_height (const struct tower *t)
112 {
113   return get_subtree_size (t->abt.root);
114 }
115
116 /* Inserts node NEW with the specified SIZE into T just below
117    node UNDER, or at the top of T if UNDER is a null pointer. */
118 void
119 tower_insert (struct tower *t, unsigned long size, struct tower_node *new,
120               struct tower_node *under)
121 {
122   assert (size > 0);
123   new->size = size;
124   abt_insert_before (&t->abt, under ? &under->abt_node : NULL,
125                      &new->abt_node);
126   t->cache_bottom = ULONG_MAX;
127 }
128
129 /* Deletes NODE from tower T. */
130 struct tower_node *
131 tower_delete (struct tower *t, struct tower_node *node)
132 {
133   struct tower_node *next = next_node (t, node);
134   abt_delete (&t->abt, &node->abt_node);
135   t->cache_bottom = ULONG_MAX;
136   return next;
137 }
138
139 /* Changes the size of NODE in tower T to NEW_SIZE. */
140 void
141 tower_resize (struct tower *t, struct tower_node *node,
142               unsigned long new_size)
143 {
144   assert (new_size > 0);
145   node->size = new_size;
146   abt_reaugmented (&t->abt, &node->abt_node);
147   t->cache_bottom = ULONG_MAX;
148 }
149
150 /* Removes nodes FIRST through LAST (exclusive) from tower SRC
151    and splices them into tower DST just below node UNDER, or at
152    the top of DST if UNDER is a null pointer.
153
154    It might be better to implement an abt_splice function and
155    turn this into a wrapper, but the asymptotic performance would
156    be the same. */
157 void
158 tower_splice (struct tower *dst, struct tower_node *under,
159               struct tower *src,
160               struct tower_node *first, struct tower_node *last)
161 {
162   struct tower_node *next;
163
164   /* Conceptually, DST == SRC is valid.
165      Practically, it's more difficult to get it right, and our
166      client code doesn't need it. */
167   assert (dst != src);
168
169   for (; first != last; first = next)
170     {
171       next = tower_delete (src, first);
172       abt_insert_before (&dst->abt, under ? &under->abt_node : NULL,
173                          &first->abt_node);
174     }
175   dst->cache_bottom = src->cache_bottom = ULONG_MAX;
176 }
177
178 /* Returns the node at the given HEIGHT from the bottom of tower
179    T.  HEIGHT must be less than T's height (as returned by
180    tower_height).  Stores in *NODE_START the height of the bottom
181    of the returned node, which may be less than HEIGHT if HEIGHT
182    refers to the middle of a node instead of its bottom. */
183 struct tower_node *
184 tower_lookup (const struct tower *t_,
185               unsigned long height,
186               unsigned long *node_start)
187 {
188   struct tower *t = CONST_CAST (struct tower *, t_);
189   struct abt_node *p;
190
191   assert (height < tower_height (t));
192
193   if (height >= t->cache_bottom && height - t->cache_bottom < t->cache->size)
194     {
195       *node_start = t->cache_bottom;
196       return t->cache;
197     }
198
199   *node_start = 0;
200   p = t->abt.root;
201   for (;;)
202     {
203       unsigned long left_size = get_subtree_size (p->down[0]);
204       if (height < left_size)
205         {
206           /* Our goal height must lie within the left subtree. */
207           p = p->down[0];
208         }
209       else
210         {
211           /* Our goal height cannot be in the left subtree. */
212           struct tower_node *node = abt_to_tower_node (p);
213           unsigned long int node_size = node->size;
214
215           height -= left_size;
216           *node_start += left_size;
217           if (height < node_size)
218             {
219               /* Our goal height is in P. */
220               t->cache = node;
221               t->cache_bottom = *node_start;
222               return node;
223             }
224           else
225             {
226               /* Our goal height is in the right subtree. */
227               p = p->down[1];
228               height -= node_size;
229               *node_start += node_size;
230             }
231         }
232     }
233 }
234
235 /* Returns the node with the given 0-based INDEX, which must be
236    less than the number of nodes in T (as returned by
237    tower_count). */
238 struct tower_node *
239 tower_get (const struct tower *t_, unsigned long int index) 
240 {
241   struct tower *t = CONST_CAST (struct tower *, t_);
242   struct abt_node *p;
243
244   assert (index < tower_count (t));
245
246   p = t->abt.root;
247   for (;;)
248     {
249       unsigned long left_count = get_subtree_count (p->down[0]);
250       if (index < left_count)
251         p = p->down[0];
252       else if (index == left_count)
253         return abt_to_tower_node (p);
254       else
255         {
256           p = p->down[1];
257           index -= left_count + 1;
258         }
259     }
260 }
261
262 /* Returns the node at height 0 in tower T, or a null pointer if
263    T is empty. */
264 struct tower_node *
265 tower_first (const struct tower *t)
266 {
267   return first_node (t);
268 }
269
270 /* Returns the node at the top of tower T, or a null pointer if T
271    is empty. */
272 struct tower_node *
273 tower_last (const struct tower *t)
274 {
275   return last_node (t);
276 }
277
278 /* If NODE is nonnull, returns the node just above NODE in tower
279    T, or a null pointer if NODE is the topmost node in T.
280    If NODE is null, acts like tower_first. */
281 struct tower_node *
282 tower_next (const struct tower *t, const struct tower_node *node)
283 {
284   return node != NULL ? next_node (t, node) : first_node (t);
285 }
286
287 /* If NODE is nonnull, returns the node just below NODE in tower
288    T, or a null pointer if NODE is the bottommost node in T.
289    If NODE is null, acts like tower_last. */
290 struct tower_node *
291 tower_prev (const struct tower *t, const struct tower_node *node)
292 {
293   return node != NULL ? prev_node (t, node) : last_node (t);
294 }
295 \f
296 /* Returns the tower node corresponding to the given ABT_NODE. */
297 static struct tower_node *
298 abt_to_tower_node (const struct abt_node *abt_node)
299 {
300   return abt_data (abt_node, struct tower_node, abt_node);
301 }
302
303 /* Returns the tower node corresponding to the given ABT_NODE. */
304 static struct tower_node *
305 abt_to_tower_node_null (const struct abt_node *abt_node)
306 {
307   return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
308 }
309
310 /* Returns the first node in TOWER. */
311 static struct tower_node *
312 first_node (const struct tower *t)
313 {
314   return abt_to_tower_node_null (abt_first (&t->abt));
315 }
316
317 /* Returns the first node in TOWER. */
318 static struct tower_node *
319 last_node (const struct tower *t)
320 {
321   return abt_to_tower_node_null (abt_last (&t->abt));
322 }
323
324 /* Returns the next node in TOWER after NODE. */
325 static struct tower_node *
326 next_node (const struct tower *t, const struct tower_node *node)
327 {
328   return abt_to_tower_node_null (abt_next (&t->abt, &node->abt_node));
329 }
330
331 /* Returns the previous node in TOWER before NODE. */
332 static struct tower_node *
333 prev_node (const struct tower *t, const struct tower_node *node)
334 {
335   return abt_to_tower_node_null (abt_prev (&t->abt, &node->abt_node));
336 }
337
338 /* Returns the total size of the nodes in the subtree rooted at
339    P, or 0 if P is null. */
340 static unsigned long int
341 get_subtree_size (const struct abt_node *p)
342 {
343   return p != NULL ? abt_to_tower_node (p)->subtree_size : 0;
344 }
345
346 /* Returns the total number of nodes in the subtree rooted at P,
347    or 0 if P is null. */
348 static unsigned long int
349 get_subtree_count (const struct abt_node *p)
350 {
351   return p != NULL ? abt_to_tower_node (p)->subtree_count : 0;
352 }
353
354 /* Recalculates the subtree_size of NODE based on its LEFT and
355    RIGHT children's subtree_sizes. */
356 static void
357 reaugment_tower_node (struct abt_node *node_,
358                       const struct abt_node *left,
359                       const struct abt_node *right,
360                       const void *aux UNUSED)
361 {
362   struct tower_node *node = abt_to_tower_node (node_);
363   node->subtree_size = node->size;
364   node->subtree_count = 1;
365   if (left != NULL) 
366     {
367       struct tower_node *left_node = abt_to_tower_node (left);
368       node->subtree_size += left_node->subtree_size;
369       node->subtree_count += left_node->subtree_count; 
370     }
371   if (right != NULL) 
372     {
373       struct tower_node *right_node = abt_to_tower_node (right);
374       node->subtree_size += right_node->subtree_size;
375       node->subtree_count += right_node->subtree_count; 
376     }
377 }