1 /* pspp - a program for statistical analysis.
2 Copyright (C) 2007, 2009, 2011, 2012, 2013 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 /* Bitmap, implemented as a balanced binary tree. */
18
19 /* If you add routines in this file, please add a corresponding
20 test to range-tower-test.c. This test program should achieve
21 100% coverage of lines and branches in this code, as reported
22 by "gcov -b". */
23
24 #include <config.h>
25
26 #include "libpspp/range-tower.h"
27
28 #include <limits.h>
29 #include <stdlib.h>
30
31 #include "libpspp/assertion.h"
32 #include "libpspp/compiler.h"
33 #include "libpspp/pool.h"
34
35 #include "gl/minmax.h"
36 #include "gl/xalloc.h"
37
38 static void reaugment_range_tower_node (struct abt_node *, const void *aux);
39 static void delete_node (struct range_tower *, struct range_tower_node *);
40
41 static void destroy_pool (void *);
42
43 static void
print_structure(const struct abt_node * node_)44 print_structure (const struct abt_node *node_)
45 {
46 struct range_tower_node *node;
47
48 if (node_ == NULL)
49 return;
50 node = ABT_DATA (node_, struct range_tower_node, abt_node);
51 printf ("%lu+%lu/%d", node->n_zeros, node->n_ones, node->abt_node.level);
52 if (node->abt_node.down[0] || node->abt_node.down[1])
53 {
54 printf ("(");
55 print_structure (node->abt_node.down[0]);
56 printf (",");
57 print_structure (node->abt_node.down[1]);
58 printf (")");
59 }
60 }
61
62 /* Prints the regions in RT to stdout. */
63 static void UNUSED
print_regions(const char * title,const struct range_tower * rt)64 print_regions (const char *title, const struct range_tower *rt)
65 {
66 const struct range_tower_node *node;
67
68 printf ("%s:", title);
69 for (node = range_tower_first__ (rt); node != NULL;
70 node = range_tower_next__ (rt, node))
71 printf (" (%lu,%lu)", node->n_zeros, node->n_ones);
72 printf ("\n");
73 printf ("structure:");
74 print_structure (rt->abt.root);
75 printf ("\n");
76 }
77
78 static struct range_tower_node *
range_tower_node_from_abt_node(const struct abt_node * abt_node)79 range_tower_node_from_abt_node (const struct abt_node *abt_node)
80 {
81 return ABT_DATA (abt_node, struct range_tower_node, abt_node);
82 }
83
84 /* Returns the total width (zeros and ones) of the nodes in the subtree rooted
85 at P, or 0 if P is null. */
86 static unsigned long int
subtree_width(const struct abt_node * p)87 subtree_width (const struct abt_node *p)
88 {
89 return p != NULL ? range_tower_node_from_abt_node (p)->subtree_width : 0;
90 }
91
92 /* Returns the position of the first 1-bit in NODE.
93
94 The performance of this function is O(lg n) in the number of nodes in the
95 range tower. It is often possible to avoid calling this function, either by
96 taking advantage of the NODE_START parameter to tower_lookup or by
97 incrementally keeping track of height while iterating through a tower. In
98 the former case the asymptotic performance is no different, since
99 tower_lookup is also O(lg n), but in the latter case performance improves
100 from O(lg n) to O(1). */
101 unsigned long int
range_tower_node_get_start(const struct range_tower_node * node)102 range_tower_node_get_start (const struct range_tower_node *node)
103 {
104 const struct abt_node *p = &node->abt_node;
105 unsigned long start = subtree_width (p->down[0]) + range_tower_node_from_abt_node (p)->n_zeros;
106 while (p->up != NULL)
107 {
108 if (p == p->up->down[1])
109 {
110 const struct range_tower_node *up
111 = range_tower_node_from_abt_node (p->up);
112 start += subtree_width (p->up->down[0]) + up->n_zeros + up->n_ones;
113 }
114 p = p->up;
115 }
116 return start;
117 }
118
119 /* Returns one past the position of the last 1-bit in NODE.
120
121 Like range_tower_node_get_start(), the performance of this function is O(lg
122 n) in the number of nodes in the range tower. */
123 unsigned long int
range_tower_node_get_end(const struct range_tower_node * node)124 range_tower_node_get_end (const struct range_tower_node *node)
125 {
126 return range_tower_node_get_start (node) + node->n_ones;
127 }
128
129 /* Creates and returns a new, empty range tower. */
130 struct range_tower *
range_tower_create(void)131 range_tower_create (void)
132 {
133 return range_tower_create_pool (NULL);
134 }
135
136 static struct range_tower *
range_tower_create_pool__(struct pool * pool)137 range_tower_create_pool__ (struct pool *pool)
138 {
139 struct range_tower *rt = xmalloc (sizeof *rt);
140
141 rt->pool = pool;
142 if (pool != NULL)
143 pool_register (pool, destroy_pool, rt);
144
145 abt_init (&rt->abt, NULL, reaugment_range_tower_node, NULL);
146 rt->cache_end = 0;
147
148 return rt;
149 }
150
151 /* Creates and returns a new, empty range tower in the given POOL. */
152 struct range_tower *
range_tower_create_pool(struct pool * pool)153 range_tower_create_pool (struct pool *pool)
154 {
155 struct range_tower_node *node;
156 struct range_tower *rt;
157
158 rt = range_tower_create_pool__ (pool);
159
160 node = xmalloc (sizeof *node);
161 node->n_zeros = ULONG_MAX;
162 node->n_ones = 0;
163 abt_insert_after (&rt->abt, NULL, &node->abt_node);
164
165 return rt;
166 }
167
168 /* Creates and returns a clone of OLD range tower in the given POOL
169 (which may be null). */
170 struct range_tower *
range_tower_clone(const struct range_tower * old,struct pool * pool)171 range_tower_clone (const struct range_tower *old, struct pool *pool)
172 {
173 const struct range_tower_node *old_node;
174 struct abt_node *prev_node;
175 struct range_tower *new;
176
177 new = range_tower_create_pool__ (pool);
178 prev_node = NULL;
179 for (old_node = range_tower_first__ (old); old_node != NULL;
180 old_node = range_tower_next__ (old, old_node))
181 {
182 struct range_tower_node *new_node;
183
184 new_node = xmalloc (sizeof *new_node);
185 new_node->n_zeros = old_node->n_zeros;
186 new_node->n_ones = old_node->n_ones;
187
188 abt_insert_after (&new->abt, prev_node, &new_node->abt_node);
189 prev_node = &new_node->abt_node;
190 }
191 return new;
192 }
193
194 /* Destroys range tower RT. */
195 void
range_tower_destroy(struct range_tower * rt)196 range_tower_destroy (struct range_tower *rt)
197 {
198 if (rt != NULL)
199 {
200 if (rt->pool != NULL)
201 pool_unregister (rt->pool, rt);
202 while (!abt_is_empty (&rt->abt))
203 delete_node (rt, range_tower_first__ (rt));
204 free (rt);
205 }
206 }
207
208 /* Sets the WIDTH bits starting at START in RT to 1-bits. */
209 void
range_tower_set1(struct range_tower * rt,unsigned long int start,unsigned long int width)210 range_tower_set1 (struct range_tower *rt,
211 unsigned long int start, unsigned long int width)
212 {
213 struct range_tower_node *node;
214 unsigned long int node_start;
215
216 assert (width == 0 || start + width - 1 >= start);
217
218 node = range_tower_lookup (rt, start, &node_start);
219 while (width > 0)
220 {
221 unsigned long int node_ofs = start - node_start;
222
223 if (node_ofs >= node->n_zeros)
224 {
225 /* There are already some 1-bits here, so skip them. */
226 unsigned long ones_left = (node->n_zeros + node->n_ones) - node_ofs;
227 if (width <= ones_left)
228 return;
229
230 start += ones_left;
231 width -= ones_left;
232 node_start += node->n_zeros + node->n_ones;
233 node_ofs = 0;
234 node = range_tower_next__ (rt, node);
235 }
236
237 /* Invalidate cache. */
238 rt->cache_end = 0;
239
240 if (node_ofs == 0)
241 {
242 if (node_start > 0)
243 {
244 struct range_tower_node *prev = range_tower_prev__ (rt, node);
245 if (width >= node->n_zeros)
246 {
247 /* All zeros in NODE are replaced by ones. Change NODE's
248 entire width into PREV's trailing ones, e.g. 00001111
249 00001111 becomes 0000111111111111. */
250 int node_width = node->n_zeros + node->n_ones;
251 delete_node (rt, node);
252 prev->n_ones += node_width;
253 abt_reaugmented (&rt->abt, &prev->abt_node);
254 if (width <= node_width)
255 return;
256
257 /* Go around again with NODE replaced by PREV's new
258 successor. */
259 width -= node_width;
260 start += node_width;
261 node = range_tower_next__ (rt, prev);
262 node_start += node_width;
263 }
264 else
265 {
266 /* Leading zeros in NODE change into trailing ones in PREV,
267 but trailing zeros in NODE remain, e.g. 00001111 00001111
268 becomes 0000111111 001111. */
269 node->n_zeros -= width;
270 abt_reaugmented (&rt->abt, &node->abt_node);
271
272 prev->n_ones += width;
273 abt_reaugmented (&rt->abt, &prev->abt_node);
274 return;
275 }
276 }
277 else
278 {
279 if (width >= node->n_zeros)
280 {
281 /* All zeros in NODE are replaced by ones, e.g. 00001111
282 becomes 11111111. */
283 node->n_ones += node->n_zeros;
284 node->n_zeros = 0;
285 if (width <= node->n_ones)
286 return;
287
288 start += node->n_ones;
289 node_start += node->n_ones;
290 width -= node->n_ones;
291 node = range_tower_next__ (rt, node);
292 }
293 else
294 {
295 /* Leading zeros in NODE (which starts at offset 0) are
296 replaced by ones, but some zeros remain. This requires a
297 node split, e.g. 00001111 becomes 11 001111. */
298 struct range_tower_node *new_node;
299
300 node->n_zeros -= width;
301 abt_reaugmented (&rt->abt, &node->abt_node);
302
303 new_node = xmalloc (sizeof *new_node);
304 new_node->n_zeros = 0;
305 new_node->n_ones = width;
306 abt_insert_before (&rt->abt, &node->abt_node,
307 &new_node->abt_node);
308 return;
309 }
310 }
311 }
312 else
313 {
314 unsigned long int zeros_left = node->n_zeros - node_ofs;
315 if (width >= zeros_left)
316 {
317 /* Trailing zeros in NODE are replaced by ones, but leading
318 zeros remain, e.g. 00001111 becomes 00111111. */
319 node->n_zeros -= zeros_left;
320 node->n_ones += zeros_left;
321 if (width <= node->n_ones)
322 return;
323 start += node->n_ones;
324 width -= node->n_ones;
325 node_start += node->n_zeros + node->n_ones;
326 node = range_tower_next__ (rt, node);
327 }
328 else
329 {
330 /* Zeros that are neither leading or trailing turn into ones.
331 Split the node into two nodes, e.g. 00001111 becomes 011
332 01111. */
333 struct range_tower_node *new_node;
334
335 new_node = xmalloc (sizeof *new_node);
336 new_node->n_ones = node->n_ones;
337 new_node->n_zeros = zeros_left - width;
338
339 node->n_zeros = node_ofs;
340 node->n_ones = width;
341 abt_reaugmented (&rt->abt, &node->abt_node);
342
343 abt_insert_after (&rt->abt, &node->abt_node,
344 &new_node->abt_node);
345 return;
346 }
347 }
348 }
349 }
350
351 /* Sets the WIDTH bits starting at START in RT to 0-bits. */
352 void
range_tower_set0(struct range_tower * rt,unsigned long int start,unsigned long int width)353 range_tower_set0 (struct range_tower *rt,
354 unsigned long int start, unsigned long int width)
355 {
356 struct range_tower_node *node;
357 unsigned long int node_start;
358
359 assert (width == 0 || start + width - 1 >= start);
360
361 node = range_tower_lookup (rt, start, &node_start);
362 while (width > 0)
363 {
364 unsigned long int node_ofs = start - node_start;
365
366 if (node_ofs < node->n_zeros)
367 {
368 /* Deleting zeros is a no-op, so skip them. */
369 unsigned long zeros_left = node->n_zeros - node_ofs;
370 if (zeros_left >= width)
371 {
372 /* We are deleting only existing zeros. Nothing to do. */
373 return;
374 }
375
376 width -= zeros_left;
377 start += zeros_left;
378 node_ofs = node->n_zeros;
379 }
380
381 rt->cache_end = 0;
382
383 if (node_ofs == node->n_zeros)
384 {
385 if (node->n_ones > width)
386 {
387 /* DELTA leading ones within NODE turn into zeros, but some ones
388 remain, e.g. 00001111 becomes 00111111. No reaugmentation
389 because n_zeros + n_ones doesn't change. */
390 node->n_zeros += width;
391 node->n_ones -= width;
392 return;
393 }
394 else
395 {
396 /* All ones in NODE turn into zeros, so merge NODE with the
397 following node, e.g. 00001111 00001111 becomes
398 0000000000001111, and then do it again with the merged
399 node. */
400 unsigned long int next_zeros, next_ones;
401 struct range_tower_node *next;
402
403 next = range_tower_next__ (rt, node);
404 if (next == NULL)
405 {
406 node->n_zeros += node->n_ones;
407 node->n_ones = 0;
408 return;
409 }
410
411 next_zeros = next->n_zeros;
412 next_ones = next->n_ones;
413 delete_node (rt, next);
414
415 node->n_zeros += node->n_ones + next_zeros;
416 node->n_ones = next_ones;
417 abt_reaugmented (&rt->abt, &node->abt_node);
418 }
419 }
420 else if (node_ofs + width >= node->n_zeros + node->n_ones)
421 {
422 /* Trailing ones in NODE turn into zeros, but leading ones remain,
423 e.g. 000011{11} 00001111 becomes 000011 {00}00001111. Give the
424 trailing ones to the next node as zeros and go around again with
425 the next node. */
426 struct range_tower_node *next;
427 unsigned long int delta;
428
429 delta = node->n_ones - (node_ofs - node->n_zeros);
430 node->n_ones -= delta;
431 abt_reaugmented (&rt->abt, &node->abt_node);
432
433 next = range_tower_next__ (rt, node);
434 if (next == NULL)
435 {
436 struct range_tower_node *new_node;
437
438 new_node = xmalloc (sizeof *new_node);
439 new_node->n_zeros = delta;
440 new_node->n_ones = 0;
441
442 abt_insert_before (&rt->abt, NULL, &new_node->abt_node);
443 return;
444 }
445
446 next->n_zeros += delta;
447 abt_reaugmented (&rt->abt, &next->abt_node);
448
449 node_start += node->n_zeros + node->n_ones;
450 start = node_start;
451 node = next;
452 }
453 else
454 {
455 /* Ones that are neither leading or trailing turn into zeros,
456 e.g. 00001111 becomes 00001 001. Split the node into two nodes
457 and we're done. */
458 unsigned long int end = start + width;
459 struct range_tower_node *new_node;
460
461 new_node = xmalloc (sizeof *new_node);
462 new_node->n_zeros = width;
463 new_node->n_ones = (node_start + node->n_zeros + node->n_ones) - end;
464
465 node->n_ones = node_ofs - node->n_zeros;
466 abt_reaugmented (&rt->abt, &node->abt_node);
467
468 abt_insert_after (&rt->abt, &node->abt_node, &new_node->abt_node);
469 return;
470 }
471 }
472 }
473
474 static void
range_tower_delete__(struct range_tower * rt,unsigned long int start,unsigned long int width)475 range_tower_delete__ (struct range_tower *rt,
476 unsigned long int start, unsigned long int width)
477 {
478 struct range_tower_node *node;
479 unsigned long int node_start;
480
481 rt->cache_end = 0;
482 node = range_tower_lookup (rt, start, &node_start);
483 for (;;)
484 {
485 unsigned long int node_ofs = start - node_start;
486
487 if (node_ofs < node->n_zeros)
488 {
489 if (node_ofs + width < node->n_zeros)
490 {
491 node->n_zeros -= width;
492 abt_reaugmented (&rt->abt, &node->abt_node);
493 break;
494 }
495 else if (node_ofs > 0)
496 {
497 width -= node->n_zeros - node_ofs;
498 node->n_zeros = node_ofs;
499 abt_reaugmented (&rt->abt, &node->abt_node);
500 if (width == 0)
501 break;
502 /* Continue with 1-bits. */
503 }
504 else if (width < node->n_zeros + node->n_ones)
505 {
506 struct range_tower_node *prev = range_tower_prev__ (rt, node);
507 unsigned long int ones_left;
508
509 ones_left = (node->n_zeros + node->n_ones) - width;
510 if (prev != NULL)
511 {
512 delete_node (rt, node);
513 prev->n_ones += ones_left;
514 abt_reaugmented (&rt->abt, &prev->abt_node);
515 }
516 else
517 {
518 node->n_zeros = 0;
519 node->n_ones = ones_left;
520 abt_reaugmented (&rt->abt, &node->abt_node);
521 }
522 break;
523 }
524 else
525 {
526 /* Delete entire node. */
527 struct range_tower_node *next = range_tower_next__ (rt, node);
528
529 width -= node->n_zeros + node->n_ones;
530 delete_node (rt, node);
531 if (next == NULL)
532 break;
533
534 node = next;
535 continue;
536 }
537 }
538
539 if (node_ofs + width < node->n_zeros + node->n_ones)
540 {
541 node->n_ones -= width;
542 abt_reaugmented (&rt->abt, &node->abt_node);
543 break;
544 }
545 else if (node_ofs > node->n_zeros)
546 {
547 unsigned long int ones_ofs = node_ofs - node->n_zeros;
548 width -= node->n_ones - ones_ofs;
549 node->n_ones = ones_ofs;
550 abt_reaugmented (&rt->abt, &node->abt_node);
551 if (width == 0)
552 break;
553 /* continue with next node */
554 node_start += node->n_zeros + node->n_ones;
555 node = range_tower_next__ (rt, node);
556 }
557 else
558 {
559 /* Merge with next node */
560 struct range_tower_node *next = range_tower_next__ (rt, node);
561 if (next != NULL)
562 {
563 unsigned long int next_zeros = next->n_zeros;
564 unsigned long int next_ones = next->n_ones;
565
566 delete_node (rt, next);
567
568 width -= node->n_ones;
569
570 node->n_zeros += next_zeros;
571 node->n_ones = next_ones;
572 abt_reaugmented (&rt->abt, &node->abt_node);
573
574 if (width == 0)
575 break;
576 }
577 else
578 {
579 node->n_ones = 0;
580 abt_reaugmented (&rt->abt, &node->abt_node);
581 break;
582 }
583 }
584 }
585 }
586
587 void
range_tower_delete(struct range_tower * rt,unsigned long int start,unsigned long int width)588 range_tower_delete (struct range_tower *rt,
589 unsigned long int start, unsigned long int width)
590 {
591 struct range_tower_node *node;
592
593 if (width == 0)
594 return;
595
596 assert (start + width - 1 >= start);
597
598 range_tower_delete__ (rt, start, width);
599
600 node = range_tower_last__ (rt);
601 if (node != NULL && node->n_ones == 0)
602 {
603 node->n_zeros += width;
604 abt_reaugmented (&rt->abt, &node->abt_node);
605 }
606 else
607 {
608 struct range_tower_node *new_node;
609
610 new_node = xmalloc (sizeof *new_node);
611 new_node->n_zeros = width;
612 new_node->n_ones = 0;
613
614 abt_insert_before (&rt->abt, NULL, &new_node->abt_node);
615 }
616 }
617
618 static struct range_tower_node *
range_tower_insert0__(struct range_tower * rt,struct range_tower_node * node,unsigned long int * node_startp,unsigned long int start,unsigned long int width)619 range_tower_insert0__ (struct range_tower *rt, struct range_tower_node *node,
620 unsigned long int *node_startp,
621 unsigned long int start, unsigned long int width)
622 {
623 unsigned long int node_ofs = start - *node_startp;
624
625 if (node_ofs <= node->n_zeros)
626 {
627 /* 00+00+001111 => 0000001111. */
628 node->n_zeros += width;
629 abt_reaugmented (&rt->abt, &node->abt_node);
630
631 return node;
632 }
633 else
634 {
635 /* 000011+00+11 => 000011 0011. */
636 struct range_tower_node *new_node;
637
638 new_node = xmalloc (sizeof *new_node);
639 new_node->n_zeros = width;
640 new_node->n_ones = node->n_zeros + node->n_ones - node_ofs;
641
642 node->n_ones -= new_node->n_ones;
643 abt_reaugmented (&rt->abt, &node->abt_node);
644 abt_insert_after (&rt->abt, &node->abt_node, &new_node->abt_node);
645
646 *node_startp += node->n_zeros + node->n_ones;
647 return new_node;
648 }
649 }
650
651 void
range_tower_insert0(struct range_tower * rt,unsigned long int start,unsigned long int width)652 range_tower_insert0 (struct range_tower *rt,
653 unsigned long int start, unsigned long int width)
654 {
655 if (width == 0)
656 return;
657
658 assert (width == 0 || start + width - 1 >= start);
659
660 if (start + width == ULONG_MAX)
661 range_tower_set0 (rt, start, width);
662 else
663 {
664 struct range_tower_node *node;
665 unsigned long int node_start;
666
667 range_tower_delete__ (rt, ULONG_MAX - width, width);
668
669 node = range_tower_lookup (rt, start, &node_start);
670 range_tower_insert0__ (rt, node, &node_start, start, width);
671 }
672 }
673
674 static struct range_tower_node *
range_tower_insert1__(struct range_tower * rt,struct range_tower_node * node,unsigned long int * node_startp,unsigned long int start,unsigned long int width)675 range_tower_insert1__ (struct range_tower *rt, struct range_tower_node *node,
676 unsigned long int *node_startp,
677 unsigned long int start, unsigned long int width)
678 {
679
680 unsigned long int node_start = *node_startp;
681 unsigned long int node_ofs = start - node_start;
682
683 if (node_ofs >= node->n_zeros)
684 {
685 node->n_ones += width;
686 abt_reaugmented (&rt->abt, &node->abt_node);
687 return node;
688 }
689 else if (node_ofs == 0 && node_start > 0)
690 {
691 struct range_tower_node *prev = range_tower_prev__ (rt, node);
692
693 prev->n_ones += width;
694 abt_reaugmented (&rt->abt, &prev->abt_node);
695
696 *node_startp += width;
697 return node;
698 }
699 else
700 {
701 /* 00001111 => 0+11+0001111 => 011 0001111 */
702 struct range_tower_node *new_node;
703
704 new_node = xmalloc (sizeof *new_node);
705 new_node->n_zeros = node->n_zeros - node_ofs;
706 new_node->n_ones = node->n_ones;
707
708 node->n_zeros = node_ofs;
709 node->n_ones = width;
710 abt_reaugmented (&rt->abt, &node->abt_node);
711
712 abt_insert_after (&rt->abt, &node->abt_node, &new_node->abt_node);
713
714 *node_startp += node->n_zeros + node->n_ones;
715 return new_node;
716 }
717 }
718
719 void
range_tower_insert1(struct range_tower * rt,unsigned long int start,unsigned long int width)720 range_tower_insert1 (struct range_tower *rt,
721 unsigned long int start, unsigned long int width)
722 {
723 struct range_tower_node *node;
724 unsigned long int node_start;
725
726 if (width == 0)
727 return;
728
729 range_tower_delete__ (rt, ULONG_MAX - width, width);
730
731 assert (width == 0 || start + width - 1 >= start);
732
733 node = range_tower_lookup (rt, start, &node_start);
734 range_tower_insert1__ (rt, node, &node_start, start, width);
735 }
736
737 void
range_tower_move(struct range_tower * rt,unsigned long int old_start,unsigned long int new_start,unsigned long int width)738 range_tower_move (struct range_tower *rt,
739 unsigned long int old_start,
740 unsigned long int new_start,
741 unsigned long int width)
742 {
743 unsigned long int node_start;
744
745 if (width == 0 || old_start == new_start)
746 return;
747
748 assert (old_start + width - 1 >= old_start);
749 assert (new_start + width - 1 >= new_start);
750
751 do
752 {
753 struct range_tower_node *node;
754 unsigned long int node_ofs;
755 unsigned long int zeros, ones;
756
757 node = range_tower_lookup (rt, old_start, &node_start);
758 node_ofs = old_start - node_start;
759
760 if (node_ofs >= node->n_zeros)
761 {
762 unsigned long int max_ones;
763
764 zeros = 0;
765 max_ones = (node->n_zeros + node->n_ones) - node_ofs;
766 ones = MIN (width, max_ones);
767 }
768 else
769 {
770 unsigned long int max_zeros;
771
772 max_zeros = node->n_zeros - node_ofs;
773 zeros = MIN (width, max_zeros);
774 if (zeros < width)
775 ones = MIN (width - zeros, node->n_ones);
776 else
777 ones = 0;
778 }
779
780 node->n_zeros -= zeros;
781 node->n_ones -= ones;
782 abt_reaugmented (&rt->abt, &node->abt_node);
783
784 if (node->n_zeros == 0)
785 {
786 if (node->n_ones == 0)
787 delete_node (rt, node);
788 else if (node_start > 0)
789 {
790 /* Merge with previous. */
791 unsigned long int n_ones = node->n_ones;
792 struct range_tower_node *prev = range_tower_prev__ (rt, node);
793
794 delete_node (rt, node);
795 prev->n_ones += n_ones;
796 abt_reaugmented (&rt->abt, &prev->abt_node);
797 }
798 }
799 else if (node->n_ones == 0)
800 {
801 struct range_tower_node *next = range_tower_next__ (rt, node);
802 if (next != NULL)
803 {
804 /* Merge with next. */
805 unsigned long int n_zeros = node->n_zeros;
806
807 delete_node (rt, node);
808 next->n_zeros += n_zeros;
809 abt_reaugmented (&rt->abt, &next->abt_node);
810 }
811 }
812
813 if (new_start < old_start)
814 {
815 node = range_tower_lookup (rt, new_start, &node_start);
816 if (zeros)
817 {
818 node = range_tower_insert0__ (rt, node, &node_start,
819 new_start, zeros);
820 old_start += zeros;
821 new_start += zeros;
822 }
823
824 if (ones)
825 {
826 node = range_tower_insert1__ (rt, node, &node_start,
827 new_start, ones);
828 old_start += ones;
829 new_start += ones;
830 }
831 }
832 else
833 {
834 unsigned long int remaining = width - (zeros + ones);
835
836 if (new_start + remaining < ULONG_MAX - (zeros + ones))
837 {
838 node = range_tower_lookup (rt, new_start + remaining,
839 &node_start);
840 if (zeros)
841 {
842 node = range_tower_insert0__ (rt, node, &node_start,
843 new_start + remaining, zeros);
844 new_start += zeros;
845 }
846
847 if (ones)
848 {
849 node = range_tower_insert1__ (rt, node, &node_start,
850 new_start + remaining, ones);
851 new_start += ones;
852 }
853 }
854 else
855 {
856 node = range_tower_last__ (rt);
857 if (zeros)
858 {
859 if (node->n_ones)
860 {
861 struct range_tower_node *new_node;
862
863 new_node = xmalloc (sizeof *new_node);
864 new_node->n_zeros = zeros;
865 new_node->n_ones = 0;
866
867 abt_insert_after (&rt->abt, &node->abt_node,
868 &new_node->abt_node);
869
870 node_start += node->n_zeros + node->n_ones;
871 node = new_node;
872 }
873 else
874 {
875 node->n_zeros += zeros;
876 abt_reaugmented (&rt->abt, &node->abt_node);
877 }
878 }
879 if (ones)
880 {
881 node->n_ones += ones;
882 abt_reaugmented (&rt->abt, &node->abt_node);
883 }
884
885 new_start += zeros + ones;
886 }
887 }
888 width -= zeros + ones;
889 }
890 while (width > 0);
891 }
892
893 /* Returns true if there is a 1-bit at the given POSITION in RT,
894 false otherwise. */
895 bool
range_tower_contains(const struct range_tower * rt_,unsigned long int position)896 range_tower_contains (const struct range_tower *rt_, unsigned long int position)
897 {
898 struct range_tower *rt = CONST_CAST (struct range_tower *, rt_);
899 if (position >= rt->cache_end || position < rt->cache_start)
900 {
901 struct range_tower_node *node;
902 unsigned long int node_start;
903
904 node = range_tower_lookup (rt, position, &node_start);
905 if (position < node_start + node->n_zeros)
906 {
907 rt->cache_start = node_start;
908 rt->cache_end = node_start + node->n_zeros;
909 rt->cache_value = false;
910 }
911 else
912 {
913 rt->cache_start = node_start + node->n_zeros;
914 rt->cache_end = rt->cache_start + node->n_ones;
915 rt->cache_value = true;
916 }
917 }
918 return rt->cache_value;
919 }
920
921 /* Returns the smallest position of a 1-bit greater than or
922 equal to START. Returns ULONG_MAX if there is no 1-bit with
923 position greater than or equal to START. */
924 unsigned long int
range_tower_scan(const struct range_tower * rt_,unsigned long int start)925 range_tower_scan (const struct range_tower *rt_, unsigned long int start)
926 {
927 struct range_tower *rt = CONST_CAST (struct range_tower *, rt_);
928
929 if (start < rt->cache_end && start >= rt->cache_start && rt->cache_value)
930 return start;
931
932 if (start != ULONG_MAX)
933 {
934 struct range_tower_node *node;
935 unsigned long int node_start;
936
937 node = range_tower_lookup (rt, start, &node_start);
938 if (node->n_ones)
939 {
940 rt->cache_start = node_start + node->n_zeros;
941 rt->cache_end = rt->cache_start + node->n_ones;
942 rt->cache_value = true;
943 return MAX (start, rt->cache_start);
944 }
945 else
946 {
947 rt->cache_start = node_start;
948 rt->cache_end = ULONG_MAX;
949 rt->cache_value = false;
950 }
951 }
952 return ULONG_MAX;
953 }
954
955 /* Recalculates the subtree_width of NODE based on its LEFT and
956 RIGHT children's "subtree_width"s. */
957 static void
reaugment_range_tower_node(struct abt_node * node_,const void * aux UNUSED)958 reaugment_range_tower_node (struct abt_node *node_, const void *aux UNUSED)
959 {
960 struct range_tower_node *node = range_tower_node_from_abt_node (node_);
961
962 node->subtree_width = node->n_zeros + node->n_ones;
963 if (node->abt_node.down[0] != NULL)
964 {
965 struct range_tower_node *left;
966
967 left = range_tower_node_from_abt_node (node->abt_node.down[0]);
968 node->subtree_width += left->subtree_width;
969 }
970 if (node->abt_node.down[1] != NULL)
971 {
972 struct range_tower_node *right;
973
974 right = range_tower_node_from_abt_node (node->abt_node.down[1]);
975 node->subtree_width += right->subtree_width;
976 }
977 }
978
979 /* Deletes NODE from RT and frees it. */
980 static void
delete_node(struct range_tower * rt,struct range_tower_node * node)981 delete_node (struct range_tower *rt, struct range_tower_node *node)
982 {
983 abt_delete (&rt->abt, &node->abt_node);
984 free (node);
985 }
986
987 struct range_tower_node *
range_tower_lookup(const struct range_tower * rt,unsigned long int position,unsigned long int * node_start)988 range_tower_lookup (const struct range_tower *rt, unsigned long int position,
989 unsigned long int *node_start)
990 {
991 const struct range_tower_node *node;
992 const struct abt_node *abt_node;
993
994 abt_node = rt->abt.root;
995 node = range_tower_node_from_abt_node (abt_node);
996 *node_start = subtree_width (abt_node->down[0]);
997 for (;;)
998 {
999 unsigned long int left_width = subtree_width (abt_node->down[0]);
1000
1001 if (position < left_width)
1002 {
1003 abt_node = abt_node->down[0];
1004 *node_start -= left_width - subtree_width (abt_node->down[0]);
1005 }
1006 else
1007 {
1008 unsigned long int node_width = node->n_zeros + node->n_ones;
1009
1010 position -= left_width;
1011 if (position < node_width)
1012 return CONST_CAST (struct range_tower_node *, node);
1013
1014 position -= node_width;
1015 abt_node = abt_node->down[1];
1016 left_width = subtree_width (abt_node->down[0]);
1017 *node_start += node_width + left_width;
1018 }
1019 node = range_tower_node_from_abt_node (abt_node);
1020 }
1021 }
1022
1023 /* Destroys range tower RT.
1024 Helper function for range_tower_create_pool. */
1025 static void
destroy_pool(void * rt_)1026 destroy_pool (void *rt_)
1027 {
1028 struct range_tower *rt = rt_;
1029 rt->pool = NULL;
1030 range_tower_destroy (rt);
1031 }
1032