1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159#include "test_util.h"
160#include "sparsebit.h"
161#include <limits.h>
162#include <assert.h>
163
164#define DUMP_LINE_MAX 100
165
166typedef uint32_t mask_t;
167#define MASK_BITS (sizeof(mask_t) * CHAR_BIT)
168
169struct node {
170 struct node *parent;
171 struct node *left;
172 struct node *right;
173 sparsebit_idx_t idx;
174 sparsebit_num_t num_after;
175 mask_t mask;
176};
177
178struct sparsebit {
179
180
181
182
183
184 struct node *root;
185
186
187
188
189
190
191
192 sparsebit_num_t num_set;
193};
194
195
196
197
198static sparsebit_num_t node_num_set(struct node *nodep)
199{
200 return nodep->num_after + __builtin_popcount(nodep->mask);
201}
202
203
204
205
206static struct node *node_first(struct sparsebit *s)
207{
208 struct node *nodep;
209
210 for (nodep = s->root; nodep && nodep->left; nodep = nodep->left)
211 ;
212
213 return nodep;
214}
215
216
217
218
219
220static struct node *node_next(struct sparsebit *s, struct node *np)
221{
222 struct node *nodep = np;
223
224
225
226
227
228 if (nodep->right) {
229 for (nodep = nodep->right; nodep->left; nodep = nodep->left)
230 ;
231 return nodep;
232 }
233
234
235
236
237
238 while (nodep->parent && nodep == nodep->parent->right)
239 nodep = nodep->parent;
240
241 return nodep->parent;
242}
243
244
245
246
247
248static struct node *node_prev(struct sparsebit *s, struct node *np)
249{
250 struct node *nodep = np;
251
252
253
254
255
256 if (nodep->left) {
257 for (nodep = nodep->left; nodep->right; nodep = nodep->right)
258 ;
259 return (struct node *) nodep;
260 }
261
262
263
264
265
266 while (nodep->parent && nodep == nodep->parent->left)
267 nodep = nodep->parent;
268
269 return (struct node *) nodep->parent;
270}
271
272
273
274
275
276
277static struct node *node_copy_subtree(struct node *subtree)
278{
279 struct node *root;
280
281
282 root = calloc(1, sizeof(*root));
283 if (!root) {
284 perror("calloc");
285 abort();
286 }
287
288 root->idx = subtree->idx;
289 root->mask = subtree->mask;
290 root->num_after = subtree->num_after;
291
292
293 if (subtree->left) {
294 root->left = node_copy_subtree(subtree->left);
295 root->left->parent = root;
296 }
297
298 if (subtree->right) {
299 root->right = node_copy_subtree(subtree->right);
300 root->right->parent = root;
301 }
302
303 return root;
304}
305
306
307
308
309
310
311static struct node *node_find(struct sparsebit *s, sparsebit_idx_t idx)
312{
313 struct node *nodep;
314
315
316 for (nodep = s->root; nodep;
317 nodep = nodep->idx > idx ? nodep->left : nodep->right) {
318 if (idx >= nodep->idx &&
319 idx <= nodep->idx + MASK_BITS + nodep->num_after - 1)
320 break;
321 }
322
323 return nodep;
324}
325
326
327
328
329
330
331
332
333
334static struct node *node_add(struct sparsebit *s, sparsebit_idx_t idx)
335{
336 struct node *nodep, *parentp, *prev;
337
338
339 nodep = calloc(1, sizeof(*nodep));
340 if (!nodep) {
341 perror("calloc");
342 abort();
343 }
344
345 nodep->idx = idx & -MASK_BITS;
346
347
348 if (!s->root) {
349 s->root = nodep;
350 return nodep;
351 }
352
353
354
355
356
357 parentp = s->root;
358 while (true) {
359 if (idx < parentp->idx) {
360 if (!parentp->left) {
361 parentp->left = nodep;
362 nodep->parent = parentp;
363 break;
364 }
365 parentp = parentp->left;
366 } else {
367 assert(idx > parentp->idx + MASK_BITS + parentp->num_after - 1);
368 if (!parentp->right) {
369 parentp->right = nodep;
370 nodep->parent = parentp;
371 break;
372 }
373 parentp = parentp->right;
374 }
375 }
376
377
378
379
380
381
382 prev = node_prev(s, nodep);
383 while (prev && prev->idx + MASK_BITS + prev->num_after - 1 >= nodep->idx) {
384 unsigned int n1 = (prev->idx + MASK_BITS + prev->num_after - 1)
385 - nodep->idx;
386 assert(prev->num_after > 0);
387 assert(n1 < MASK_BITS);
388 assert(!(nodep->mask & (1 << n1)));
389 nodep->mask |= (1 << n1);
390 prev->num_after--;
391 }
392
393 return nodep;
394}
395
396
397bool sparsebit_all_set(struct sparsebit *s)
398{
399
400
401
402
403
404 return s->root && s->num_set == 0;
405}
406
407
408
409
410static void node_rm(struct sparsebit *s, struct node *nodep)
411{
412 struct node *tmp;
413 sparsebit_num_t num_set;
414
415 num_set = node_num_set(nodep);
416 assert(s->num_set >= num_set || sparsebit_all_set(s));
417 s->num_set -= node_num_set(nodep);
418
419
420 if (nodep->left && nodep->right) {
421
422
423
424
425 for (tmp = nodep->right; tmp->left; tmp = tmp->left)
426 ;
427 tmp->left = nodep->left;
428 nodep->left = NULL;
429 tmp->left->parent = tmp;
430 }
431
432
433 if (nodep->left) {
434 if (!nodep->parent) {
435 s->root = nodep->left;
436 nodep->left->parent = NULL;
437 } else {
438 nodep->left->parent = nodep->parent;
439 if (nodep == nodep->parent->left)
440 nodep->parent->left = nodep->left;
441 else {
442 assert(nodep == nodep->parent->right);
443 nodep->parent->right = nodep->left;
444 }
445 }
446
447 nodep->parent = nodep->left = nodep->right = NULL;
448 free(nodep);
449
450 return;
451 }
452
453
454
455 if (nodep->right) {
456 if (!nodep->parent) {
457 s->root = nodep->right;
458 nodep->right->parent = NULL;
459 } else {
460 nodep->right->parent = nodep->parent;
461 if (nodep == nodep->parent->left)
462 nodep->parent->left = nodep->right;
463 else {
464 assert(nodep == nodep->parent->right);
465 nodep->parent->right = nodep->right;
466 }
467 }
468
469 nodep->parent = nodep->left = nodep->right = NULL;
470 free(nodep);
471
472 return;
473 }
474
475
476 if (!nodep->parent) {
477 s->root = NULL;
478 } else {
479 if (nodep->parent->left == nodep)
480 nodep->parent->left = NULL;
481 else {
482 assert(nodep == nodep->parent->right);
483 nodep->parent->right = NULL;
484 }
485 }
486
487 nodep->parent = nodep->left = nodep->right = NULL;
488 free(nodep);
489
490 return;
491}
492
493
494
495
496
497
498
499static struct node *node_split(struct sparsebit *s, sparsebit_idx_t idx)
500{
501 struct node *nodep1, *nodep2;
502 sparsebit_idx_t offset;
503 sparsebit_num_t orig_num_after;
504
505 assert(!(idx % MASK_BITS));
506
507
508
509
510
511 nodep1 = node_find(s, idx);
512 if (!nodep1)
513 return node_add(s, idx);
514
515
516
517
518
519 if (nodep1->idx == idx)
520 return nodep1;
521
522
523
524
525
526
527
528
529
530
531 offset = idx - (nodep1->idx + MASK_BITS);
532 orig_num_after = nodep1->num_after;
533
534
535
536
537
538 nodep1->num_after = offset;
539 nodep2 = node_add(s, idx);
540
541
542 nodep2->num_after = orig_num_after - offset;
543 if (nodep2->num_after >= MASK_BITS) {
544 nodep2->mask = ~(mask_t) 0;
545 nodep2->num_after -= MASK_BITS;
546 } else {
547 nodep2->mask = (1 << nodep2->num_after) - 1;
548 nodep2->num_after = 0;
549 }
550
551 return nodep2;
552}
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600static void node_reduce(struct sparsebit *s, struct node *nodep)
601{
602 bool reduction_performed;
603
604 do {
605 reduction_performed = false;
606 struct node *prev, *next, *tmp;
607
608
609
610
611 if (nodep->mask == 0 && nodep->num_after == 0) {
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633 tmp = node_next(s, nodep);
634 if (!tmp)
635 tmp = node_prev(s, nodep);
636
637 node_rm(s, nodep);
638 nodep = NULL;
639
640 nodep = tmp;
641 reduction_performed = true;
642 continue;
643 }
644
645
646
647
648
649 if (nodep->mask == 0) {
650 assert(nodep->num_after != 0);
651 assert(nodep->idx + MASK_BITS > nodep->idx);
652
653 nodep->idx += MASK_BITS;
654
655 if (nodep->num_after >= MASK_BITS) {
656 nodep->mask = ~0;
657 nodep->num_after -= MASK_BITS;
658 } else {
659 nodep->mask = (1u << nodep->num_after) - 1;
660 nodep->num_after = 0;
661 }
662
663 reduction_performed = true;
664 continue;
665 }
666
667
668
669
670
671 prev = node_prev(s, nodep);
672 if (prev) {
673 sparsebit_idx_t prev_highest_bit;
674
675
676 if (prev->mask == 0 && prev->num_after == 0) {
677 node_rm(s, prev);
678
679 reduction_performed = true;
680 continue;
681 }
682
683
684
685
686
687 if (nodep->mask + 1 == 0 &&
688 prev->idx + MASK_BITS == nodep->idx) {
689 prev->num_after += MASK_BITS + nodep->num_after;
690 nodep->mask = 0;
691 nodep->num_after = 0;
692
693 reduction_performed = true;
694 continue;
695 }
696
697
698
699
700
701
702 prev_highest_bit = prev->idx + MASK_BITS - 1 + prev->num_after;
703 if (prev_highest_bit + 1 == nodep->idx &&
704 (nodep->mask | (nodep->mask >> 1)) == nodep->mask) {
705
706
707
708
709
710
711
712 unsigned int num_contiguous
713 = __builtin_popcount(nodep->mask);
714 assert((num_contiguous > 0) &&
715 ((1ULL << num_contiguous) - 1) == nodep->mask);
716
717 prev->num_after += num_contiguous;
718 nodep->mask = 0;
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733 if (num_contiguous == MASK_BITS) {
734 prev->num_after += nodep->num_after;
735 nodep->num_after = 0;
736 }
737
738 reduction_performed = true;
739 continue;
740 }
741 }
742
743
744
745
746
747 next = node_next(s, nodep);
748 if (next) {
749
750 if (next->mask == 0 && next->num_after == 0) {
751 node_rm(s, next);
752 reduction_performed = true;
753 continue;
754 }
755
756
757
758
759
760 if (next->idx == nodep->idx + MASK_BITS + nodep->num_after &&
761 next->mask == ~(mask_t) 0) {
762 nodep->num_after += MASK_BITS;
763 next->mask = 0;
764 nodep->num_after += next->num_after;
765 next->num_after = 0;
766
767 node_rm(s, next);
768 next = NULL;
769
770 reduction_performed = true;
771 continue;
772 }
773 }
774 } while (nodep && reduction_performed);
775}
776
777
778
779
780bool sparsebit_is_set(struct sparsebit *s, sparsebit_idx_t idx)
781{
782 struct node *nodep;
783
784
785 for (nodep = s->root; nodep;
786 nodep = nodep->idx > idx ? nodep->left : nodep->right)
787 if (idx >= nodep->idx &&
788 idx <= nodep->idx + MASK_BITS + nodep->num_after - 1)
789 goto have_node;
790
791 return false;
792
793have_node:
794
795 if (nodep->num_after && idx >= nodep->idx + MASK_BITS)
796 return true;
797
798
799 assert(idx >= nodep->idx && idx - nodep->idx < MASK_BITS);
800 return !!(nodep->mask & (1 << (idx - nodep->idx)));
801}
802
803
804
805
806static void bit_set(struct sparsebit *s, sparsebit_idx_t idx)
807{
808 struct node *nodep;
809
810
811 if (sparsebit_is_set(s, idx))
812 return;
813
814
815
816
817
818
819 nodep = node_split(s, idx & -MASK_BITS);
820
821
822 assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1);
823 assert(!(nodep->mask & (1 << (idx - nodep->idx))));
824 nodep->mask |= 1 << (idx - nodep->idx);
825 s->num_set++;
826
827 node_reduce(s, nodep);
828}
829
830
831
832
833static void bit_clear(struct sparsebit *s, sparsebit_idx_t idx)
834{
835 struct node *nodep;
836
837
838 if (!sparsebit_is_set(s, idx))
839 return;
840
841
842 nodep = node_find(s, idx);
843 if (!nodep)
844 return;
845
846
847
848
849
850 if (idx >= nodep->idx + MASK_BITS)
851 nodep = node_split(s, idx & -MASK_BITS);
852
853
854
855
856
857 assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1);
858 assert(nodep->mask & (1 << (idx - nodep->idx)));
859 nodep->mask &= ~(1 << (idx - nodep->idx));
860 assert(s->num_set > 0 || sparsebit_all_set(s));
861 s->num_set--;
862
863 node_reduce(s, nodep);
864}
865
866
867
868
869
870
871
872
873static void dump_nodes(FILE *stream, struct node *nodep,
874 unsigned int indent)
875{
876 char *node_type;
877
878
879 if (!nodep->parent)
880 node_type = "root";
881 else if (nodep == nodep->parent->left)
882 node_type = "left";
883 else {
884 assert(nodep == nodep->parent->right);
885 node_type = "right";
886 }
887 fprintf(stream, "%*s---- %s nodep: %p\n", indent, "", node_type, nodep);
888 fprintf(stream, "%*s parent: %p left: %p right: %p\n", indent, "",
889 nodep->parent, nodep->left, nodep->right);
890 fprintf(stream, "%*s idx: 0x%lx mask: 0x%x num_after: 0x%lx\n",
891 indent, "", nodep->idx, nodep->mask, nodep->num_after);
892
893
894 if (nodep->left)
895 dump_nodes(stream, nodep->left, indent + 2);
896
897
898 if (nodep->right)
899 dump_nodes(stream, nodep->right, indent + 2);
900}
901
902static inline sparsebit_idx_t node_first_set(struct node *nodep, int start)
903{
904 mask_t leading = (mask_t)1 << start;
905 int n1 = __builtin_ctz(nodep->mask & -leading);
906
907 return nodep->idx + n1;
908}
909
910static inline sparsebit_idx_t node_first_clear(struct node *nodep, int start)
911{
912 mask_t leading = (mask_t)1 << start;
913 int n1 = __builtin_ctz(~nodep->mask & -leading);
914
915 return nodep->idx + n1;
916}
917
918
919
920
921
922
923
924
925
926static void sparsebit_dump_internal(FILE *stream, struct sparsebit *s,
927 unsigned int indent)
928{
929
930 fprintf(stream, "%*sroot: %p\n", indent, "", s->root);
931 fprintf(stream, "%*snum_set: 0x%lx\n", indent, "", s->num_set);
932
933 if (s->root)
934 dump_nodes(stream, s->root, indent);
935}
936
937
938
939
940struct sparsebit *sparsebit_alloc(void)
941{
942 struct sparsebit *s;
943
944
945 s = calloc(1, sizeof(*s));
946 if (!s) {
947 perror("calloc");
948 abort();
949 }
950
951 return s;
952}
953
954
955
956
957void sparsebit_free(struct sparsebit **sbitp)
958{
959 struct sparsebit *s = *sbitp;
960
961 if (!s)
962 return;
963
964 sparsebit_clear_all(s);
965 free(s);
966 *sbitp = NULL;
967}
968
969
970
971
972
973
974void sparsebit_copy(struct sparsebit *d, struct sparsebit *s)
975{
976
977 sparsebit_clear_all(d);
978
979 if (s->root) {
980 d->root = node_copy_subtree(s->root);
981 d->num_set = s->num_set;
982 }
983}
984
985
986bool sparsebit_is_set_num(struct sparsebit *s,
987 sparsebit_idx_t idx, sparsebit_num_t num)
988{
989 sparsebit_idx_t next_cleared;
990
991 assert(num > 0);
992 assert(idx + num - 1 >= idx);
993
994
995 if (!sparsebit_is_set(s, idx))
996 return false;
997
998
999 next_cleared = sparsebit_next_clear(s, idx);
1000
1001
1002
1003
1004
1005
1006 return next_cleared == 0 || next_cleared - idx >= num;
1007}
1008
1009
1010bool sparsebit_is_clear(struct sparsebit *s,
1011 sparsebit_idx_t idx)
1012{
1013 return !sparsebit_is_set(s, idx);
1014}
1015
1016
1017bool sparsebit_is_clear_num(struct sparsebit *s,
1018 sparsebit_idx_t idx, sparsebit_num_t num)
1019{
1020 sparsebit_idx_t next_set;
1021
1022 assert(num > 0);
1023 assert(idx + num - 1 >= idx);
1024
1025
1026 if (!sparsebit_is_clear(s, idx))
1027 return false;
1028
1029
1030 next_set = sparsebit_next_set(s, idx);
1031
1032
1033
1034
1035
1036
1037 return next_set == 0 || next_set - idx >= num;
1038}
1039
1040
1041
1042
1043
1044
1045
1046sparsebit_num_t sparsebit_num_set(struct sparsebit *s)
1047{
1048 return s->num_set;
1049}
1050
1051
1052bool sparsebit_any_set(struct sparsebit *s)
1053{
1054
1055
1056
1057
1058 if (!s->root)
1059 return false;
1060
1061
1062
1063
1064
1065
1066 assert(s->root->mask != 0);
1067 assert(s->num_set > 0 ||
1068 (s->root->num_after == ((sparsebit_num_t) 0) - MASK_BITS &&
1069 s->root->mask == ~(mask_t) 0));
1070
1071 return true;
1072}
1073
1074
1075bool sparsebit_all_clear(struct sparsebit *s)
1076{
1077 return !sparsebit_any_set(s);
1078}
1079
1080
1081bool sparsebit_any_clear(struct sparsebit *s)
1082{
1083 return !sparsebit_all_set(s);
1084}
1085
1086
1087
1088sparsebit_idx_t sparsebit_first_set(struct sparsebit *s)
1089{
1090 struct node *nodep;
1091
1092
1093 assert(sparsebit_any_set(s));
1094
1095 nodep = node_first(s);
1096 return node_first_set(nodep, 0);
1097}
1098
1099
1100
1101
1102sparsebit_idx_t sparsebit_first_clear(struct sparsebit *s)
1103{
1104 struct node *nodep1, *nodep2;
1105
1106
1107 assert(sparsebit_any_clear(s));
1108
1109
1110 nodep1 = node_first(s);
1111 if (!nodep1 || nodep1->idx > 0)
1112 return 0;
1113
1114
1115 if (nodep1->mask != ~(mask_t) 0)
1116 return node_first_clear(nodep1, 0);
1117
1118
1119
1120
1121
1122
1123 nodep2 = node_next(s, nodep1);
1124 if (!nodep2) {
1125
1126
1127
1128
1129 assert(nodep1->mask == ~(mask_t) 0);
1130 assert(nodep1->idx + MASK_BITS + nodep1->num_after != (sparsebit_idx_t) 0);
1131 return nodep1->idx + MASK_BITS + nodep1->num_after;
1132 }
1133
1134
1135
1136
1137
1138
1139
1140 if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx)
1141 return nodep1->idx + MASK_BITS + nodep1->num_after;
1142
1143
1144
1145
1146
1147
1148
1149
1150 return node_first_clear(nodep2, 0);
1151}
1152
1153
1154
1155
1156sparsebit_idx_t sparsebit_next_set(struct sparsebit *s,
1157 sparsebit_idx_t prev)
1158{
1159 sparsebit_idx_t lowest_possible = prev + 1;
1160 sparsebit_idx_t start;
1161 struct node *nodep;
1162
1163
1164 if (lowest_possible == 0)
1165 return 0;
1166
1167
1168
1169
1170
1171 struct node *candidate = NULL;
1172
1173
1174 bool contains = false;
1175
1176
1177
1178
1179
1180
1181 for (nodep = s->root; nodep;) {
1182 if ((nodep->idx + MASK_BITS + nodep->num_after - 1)
1183 >= lowest_possible) {
1184 candidate = nodep;
1185 if (candidate->idx <= lowest_possible) {
1186 contains = true;
1187 break;
1188 }
1189 nodep = nodep->left;
1190 } else {
1191 nodep = nodep->right;
1192 }
1193 }
1194 if (!candidate)
1195 return 0;
1196
1197 assert(candidate->mask != 0);
1198
1199
1200 if (!contains) {
1201
1202
1203
1204
1205
1206 assert(candidate->idx > lowest_possible);
1207
1208 return node_first_set(candidate, 0);
1209 }
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219 start = lowest_possible - candidate->idx;
1220
1221 if (start < MASK_BITS && candidate->mask >= (1 << start))
1222 return node_first_set(candidate, start);
1223
1224 if (candidate->num_after) {
1225 sparsebit_idx_t first_num_after_idx = candidate->idx + MASK_BITS;
1226
1227 return lowest_possible < first_num_after_idx
1228 ? first_num_after_idx : lowest_possible;
1229 }
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239 candidate = node_next(s, candidate);
1240 if (!candidate)
1241 return 0;
1242
1243 return node_first_set(candidate, 0);
1244}
1245
1246
1247
1248
1249sparsebit_idx_t sparsebit_next_clear(struct sparsebit *s,
1250 sparsebit_idx_t prev)
1251{
1252 sparsebit_idx_t lowest_possible = prev + 1;
1253 sparsebit_idx_t idx;
1254 struct node *nodep1, *nodep2;
1255
1256
1257 if (lowest_possible == 0)
1258 return 0;
1259
1260
1261
1262
1263
1264 nodep1 = node_find(s, lowest_possible);
1265 if (!nodep1)
1266 return lowest_possible;
1267
1268
1269 for (idx = lowest_possible - nodep1->idx; idx < MASK_BITS; idx++)
1270 if (!(nodep1->mask & (1 << idx)))
1271 return nodep1->idx + idx;
1272
1273
1274
1275
1276
1277
1278 nodep2 = node_next(s, nodep1);
1279 if (!nodep2)
1280 return nodep1->idx + MASK_BITS + nodep1->num_after;
1281
1282
1283
1284
1285
1286
1287
1288 if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx)
1289 return nodep1->idx + MASK_BITS + nodep1->num_after;
1290
1291
1292
1293
1294
1295
1296
1297
1298 return node_first_clear(nodep2, 0);
1299}
1300
1301
1302
1303
1304
1305sparsebit_idx_t sparsebit_next_set_num(struct sparsebit *s,
1306 sparsebit_idx_t start, sparsebit_num_t num)
1307{
1308 sparsebit_idx_t idx;
1309
1310 assert(num >= 1);
1311
1312 for (idx = sparsebit_next_set(s, start);
1313 idx != 0 && idx + num - 1 >= idx;
1314 idx = sparsebit_next_set(s, idx)) {
1315 assert(sparsebit_is_set(s, idx));
1316
1317
1318
1319
1320
1321 if (sparsebit_is_set_num(s, idx, num))
1322 return idx;
1323
1324
1325
1326
1327
1328 idx = sparsebit_next_clear(s, idx);
1329 if (idx == 0)
1330 return 0;
1331 }
1332
1333 return 0;
1334}
1335
1336
1337
1338
1339
1340sparsebit_idx_t sparsebit_next_clear_num(struct sparsebit *s,
1341 sparsebit_idx_t start, sparsebit_num_t num)
1342{
1343 sparsebit_idx_t idx;
1344
1345 assert(num >= 1);
1346
1347 for (idx = sparsebit_next_clear(s, start);
1348 idx != 0 && idx + num - 1 >= idx;
1349 idx = sparsebit_next_clear(s, idx)) {
1350 assert(sparsebit_is_clear(s, idx));
1351
1352
1353
1354
1355
1356 if (sparsebit_is_clear_num(s, idx, num))
1357 return idx;
1358
1359
1360
1361
1362
1363 idx = sparsebit_next_set(s, idx);
1364 if (idx == 0)
1365 return 0;
1366 }
1367
1368 return 0;
1369}
1370
1371
1372void sparsebit_set_num(struct sparsebit *s,
1373 sparsebit_idx_t start, sparsebit_num_t num)
1374{
1375 struct node *nodep, *next;
1376 unsigned int n1;
1377 sparsebit_idx_t idx;
1378 sparsebit_num_t n;
1379 sparsebit_idx_t middle_start, middle_end;
1380
1381 assert(num > 0);
1382 assert(start + num - 1 >= start);
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404 for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--)
1405 bit_set(s, idx);
1406
1407
1408 middle_start = idx;
1409 middle_end = middle_start + (n & -MASK_BITS) - 1;
1410 if (n >= MASK_BITS) {
1411 nodep = node_split(s, middle_start);
1412
1413
1414
1415
1416
1417
1418 if (middle_end + 1 > middle_end)
1419 (void) node_split(s, middle_end + 1);
1420
1421
1422 for (next = node_next(s, nodep);
1423 next && (next->idx < middle_end);
1424 next = node_next(s, nodep)) {
1425 assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end);
1426 node_rm(s, next);
1427 next = NULL;
1428 }
1429
1430
1431 for (n1 = 0; n1 < MASK_BITS; n1++) {
1432 if (!(nodep->mask & (1 << n1))) {
1433 nodep->mask |= 1 << n1;
1434 s->num_set++;
1435 }
1436 }
1437
1438 s->num_set -= nodep->num_after;
1439 nodep->num_after = middle_end - middle_start + 1 - MASK_BITS;
1440 s->num_set += nodep->num_after;
1441
1442 node_reduce(s, nodep);
1443 }
1444 idx = middle_end + 1;
1445 n -= middle_end - middle_start + 1;
1446
1447
1448 assert(n < MASK_BITS);
1449 for (; n > 0; idx++, n--)
1450 bit_set(s, idx);
1451}
1452
1453
1454void sparsebit_clear_num(struct sparsebit *s,
1455 sparsebit_idx_t start, sparsebit_num_t num)
1456{
1457 struct node *nodep, *next;
1458 unsigned int n1;
1459 sparsebit_idx_t idx;
1460 sparsebit_num_t n;
1461 sparsebit_idx_t middle_start, middle_end;
1462
1463 assert(num > 0);
1464 assert(start + num - 1 >= start);
1465
1466
1467 for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--)
1468 bit_clear(s, idx);
1469
1470
1471 middle_start = idx;
1472 middle_end = middle_start + (n & -MASK_BITS) - 1;
1473 if (n >= MASK_BITS) {
1474 nodep = node_split(s, middle_start);
1475
1476
1477
1478
1479
1480
1481 if (middle_end + 1 > middle_end)
1482 (void) node_split(s, middle_end + 1);
1483
1484
1485 for (next = node_next(s, nodep);
1486 next && (next->idx < middle_end);
1487 next = node_next(s, nodep)) {
1488 assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end);
1489 node_rm(s, next);
1490 next = NULL;
1491 }
1492
1493
1494 for (n1 = 0; n1 < MASK_BITS; n1++) {
1495 if (nodep->mask & (1 << n1)) {
1496 nodep->mask &= ~(1 << n1);
1497 s->num_set--;
1498 }
1499 }
1500
1501
1502 s->num_set -= nodep->num_after;
1503 nodep->num_after = 0;
1504
1505
1506
1507
1508
1509
1510 node_reduce(s, nodep);
1511 nodep = NULL;
1512 }
1513 idx = middle_end + 1;
1514 n -= middle_end - middle_start + 1;
1515
1516
1517 assert(n < MASK_BITS);
1518 for (; n > 0; idx++, n--)
1519 bit_clear(s, idx);
1520}
1521
1522
1523void sparsebit_set(struct sparsebit *s, sparsebit_idx_t idx)
1524{
1525 sparsebit_set_num(s, idx, 1);
1526}
1527
1528
1529void sparsebit_clear(struct sparsebit *s, sparsebit_idx_t idx)
1530{
1531 sparsebit_clear_num(s, idx, 1);
1532}
1533
1534
1535void sparsebit_set_all(struct sparsebit *s)
1536{
1537 sparsebit_set(s, 0);
1538 sparsebit_set_num(s, 1, ~(sparsebit_idx_t) 0);
1539 assert(sparsebit_all_set(s));
1540}
1541
1542
1543void sparsebit_clear_all(struct sparsebit *s)
1544{
1545 sparsebit_clear(s, 0);
1546 sparsebit_clear_num(s, 1, ~(sparsebit_idx_t) 0);
1547 assert(!sparsebit_any_set(s));
1548}
1549
1550static size_t display_range(FILE *stream, sparsebit_idx_t low,
1551 sparsebit_idx_t high, bool prepend_comma_space)
1552{
1553 char *fmt_str;
1554 size_t sz;
1555
1556
1557 if (low == high)
1558 fmt_str = prepend_comma_space ? ", 0x%lx" : "0x%lx";
1559 else
1560 fmt_str = prepend_comma_space ? ", 0x%lx:0x%lx" : "0x%lx:0x%lx";
1561
1562
1563
1564
1565
1566 if (!stream)
1567 sz = snprintf(NULL, 0, fmt_str, low, high);
1568 else
1569 sz = fprintf(stream, fmt_str, low, high);
1570
1571 return sz;
1572}
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588void sparsebit_dump(FILE *stream, struct sparsebit *s,
1589 unsigned int indent)
1590{
1591 size_t current_line_len = 0;
1592 size_t sz;
1593 struct node *nodep;
1594
1595 if (!sparsebit_any_set(s))
1596 return;
1597
1598
1599 fprintf(stream, "%*s", indent, "");
1600
1601
1602 for (nodep = node_first(s); nodep; nodep = node_next(s, nodep)) {
1603 unsigned int n1;
1604 sparsebit_idx_t low, high;
1605
1606
1607 for (n1 = 0; n1 < MASK_BITS; n1++) {
1608 if (nodep->mask & (1 << n1)) {
1609 low = high = nodep->idx + n1;
1610
1611 for (; n1 < MASK_BITS; n1++) {
1612 if (nodep->mask & (1 << n1))
1613 high = nodep->idx + n1;
1614 else
1615 break;
1616 }
1617
1618 if ((n1 == MASK_BITS) && nodep->num_after)
1619 high += nodep->num_after;
1620
1621
1622
1623
1624
1625 sz = display_range(NULL, low, high,
1626 current_line_len != 0);
1627
1628
1629
1630
1631
1632
1633 if (current_line_len + sz > DUMP_LINE_MAX) {
1634 fputs("\n", stream);
1635 fprintf(stream, "%*s", indent, "");
1636 current_line_len = 0;
1637 }
1638
1639
1640 sz = display_range(stream, low, high,
1641 current_line_len != 0);
1642 current_line_len += sz;
1643 }
1644 }
1645
1646
1647
1648
1649
1650
1651 if (!(nodep->mask & (1 << (MASK_BITS - 1))) && nodep->num_after) {
1652 low = nodep->idx + MASK_BITS;
1653 high = nodep->idx + MASK_BITS + nodep->num_after - 1;
1654
1655
1656
1657
1658
1659 sz = display_range(NULL, low, high,
1660 current_line_len != 0);
1661
1662
1663
1664
1665
1666
1667 if (current_line_len + sz > DUMP_LINE_MAX) {
1668 fputs("\n", stream);
1669 fprintf(stream, "%*s", indent, "");
1670 current_line_len = 0;
1671 }
1672
1673
1674 sz = display_range(stream, low, high,
1675 current_line_len != 0);
1676 current_line_len += sz;
1677 }
1678 }
1679 fputs("\n", stream);
1680}
1681
1682
1683
1684
1685
1686void sparsebit_validate_internal(struct sparsebit *s)
1687{
1688 bool error_detected = false;
1689 struct node *nodep, *prev = NULL;
1690 sparsebit_num_t total_bits_set = 0;
1691 unsigned int n1;
1692
1693
1694 for (nodep = node_first(s); nodep;
1695 prev = nodep, nodep = node_next(s, nodep)) {
1696
1697
1698
1699
1700
1701 for (n1 = 0; n1 < MASK_BITS; n1++)
1702 if (nodep->mask & (1 << n1))
1703 total_bits_set++;
1704
1705 total_bits_set += nodep->num_after;
1706
1707
1708
1709
1710
1711
1712
1713
1714 if (nodep->mask == 0) {
1715 fprintf(stderr, "Node mask of zero, "
1716 "nodep: %p nodep->mask: 0x%x",
1717 nodep, nodep->mask);
1718 error_detected = true;
1719 break;
1720 }
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733 if (nodep->num_after
1734 > (~(sparsebit_num_t) 0) - MASK_BITS + 1) {
1735 fprintf(stderr, "num_after too large, "
1736 "nodep: %p nodep->num_after: 0x%lx",
1737 nodep, nodep->num_after);
1738 error_detected = true;
1739 break;
1740 }
1741
1742
1743 if (nodep->idx % MASK_BITS) {
1744 fprintf(stderr, "Node index not divisible by "
1745 "mask size,\n"
1746 " nodep: %p nodep->idx: 0x%lx "
1747 "MASK_BITS: %lu\n",
1748 nodep, nodep->idx, MASK_BITS);
1749 error_detected = true;
1750 break;
1751 }
1752
1753
1754
1755
1756
1757 if ((nodep->idx + MASK_BITS + nodep->num_after - 1) < nodep->idx) {
1758 fprintf(stderr, "Bits described by node wrap "
1759 "beyond highest supported index,\n"
1760 " nodep: %p nodep->idx: 0x%lx\n"
1761 " MASK_BITS: %lu nodep->num_after: 0x%lx",
1762 nodep, nodep->idx, MASK_BITS, nodep->num_after);
1763 error_detected = true;
1764 break;
1765 }
1766
1767
1768 if (nodep->left) {
1769 if (nodep->left->parent != nodep) {
1770 fprintf(stderr, "Left child parent pointer "
1771 "doesn't point to this node,\n"
1772 " nodep: %p nodep->left: %p "
1773 "nodep->left->parent: %p",
1774 nodep, nodep->left,
1775 nodep->left->parent);
1776 error_detected = true;
1777 break;
1778 }
1779 }
1780
1781 if (nodep->right) {
1782 if (nodep->right->parent != nodep) {
1783 fprintf(stderr, "Right child parent pointer "
1784 "doesn't point to this node,\n"
1785 " nodep: %p nodep->right: %p "
1786 "nodep->right->parent: %p",
1787 nodep, nodep->right,
1788 nodep->right->parent);
1789 error_detected = true;
1790 break;
1791 }
1792 }
1793
1794 if (!nodep->parent) {
1795 if (s->root != nodep) {
1796 fprintf(stderr, "Unexpected root node, "
1797 "s->root: %p nodep: %p",
1798 s->root, nodep);
1799 error_detected = true;
1800 break;
1801 }
1802 }
1803
1804 if (prev) {
1805
1806
1807
1808
1809 if (prev->idx >= nodep->idx) {
1810 fprintf(stderr, "Previous node index "
1811 ">= current node index,\n"
1812 " prev: %p prev->idx: 0x%lx\n"
1813 " nodep: %p nodep->idx: 0x%lx",
1814 prev, prev->idx, nodep, nodep->idx);
1815 error_detected = true;
1816 break;
1817 }
1818
1819
1820
1821
1822
1823 if ((prev->idx + MASK_BITS + prev->num_after - 1)
1824 >= nodep->idx) {
1825 fprintf(stderr, "Previous node bit range "
1826 "overlap with current node bit range,\n"
1827 " prev: %p prev->idx: 0x%lx "
1828 "prev->num_after: 0x%lx\n"
1829 " nodep: %p nodep->idx: 0x%lx "
1830 "nodep->num_after: 0x%lx\n"
1831 " MASK_BITS: %lu",
1832 prev, prev->idx, prev->num_after,
1833 nodep, nodep->idx, nodep->num_after,
1834 MASK_BITS);
1835 error_detected = true;
1836 break;
1837 }
1838
1839
1840
1841
1842
1843
1844 if (nodep->mask == ~(mask_t) 0 &&
1845 prev->idx + MASK_BITS + prev->num_after == nodep->idx) {
1846 fprintf(stderr, "Current node has mask with "
1847 "all bits set and is adjacent to the "
1848 "previous node,\n"
1849 " prev: %p prev->idx: 0x%lx "
1850 "prev->num_after: 0x%lx\n"
1851 " nodep: %p nodep->idx: 0x%lx "
1852 "nodep->num_after: 0x%lx\n"
1853 " MASK_BITS: %lu",
1854 prev, prev->idx, prev->num_after,
1855 nodep, nodep->idx, nodep->num_after,
1856 MASK_BITS);
1857
1858 error_detected = true;
1859 break;
1860 }
1861 }
1862 }
1863
1864 if (!error_detected) {
1865
1866
1867
1868
1869 if (s->num_set != total_bits_set) {
1870 fprintf(stderr, "Number of bits set missmatch,\n"
1871 " s->num_set: 0x%lx total_bits_set: 0x%lx",
1872 s->num_set, total_bits_set);
1873
1874 error_detected = true;
1875 }
1876 }
1877
1878 if (error_detected) {
1879 fputs(" dump_internal:\n", stderr);
1880 sparsebit_dump_internal(stderr, s, 4);
1881 abort();
1882 }
1883}
1884
1885
1886#ifdef FUZZ
1887
1888
1889
1890
1891
1892
1893#include <stdlib.h>
1894#include <assert.h>
1895
1896struct range {
1897 sparsebit_idx_t first, last;
1898 bool set;
1899};
1900
1901struct sparsebit *s;
1902struct range ranges[1000];
1903int num_ranges;
1904
1905static bool get_value(sparsebit_idx_t idx)
1906{
1907 int i;
1908
1909 for (i = num_ranges; --i >= 0; )
1910 if (ranges[i].first <= idx && idx <= ranges[i].last)
1911 return ranges[i].set;
1912
1913 return false;
1914}
1915
1916static void operate(int code, sparsebit_idx_t first, sparsebit_idx_t last)
1917{
1918 sparsebit_num_t num;
1919 sparsebit_idx_t next;
1920
1921 if (first < last) {
1922 num = last - first + 1;
1923 } else {
1924 num = first - last + 1;
1925 first = last;
1926 last = first + num - 1;
1927 }
1928
1929 switch (code) {
1930 case 0:
1931 sparsebit_set(s, first);
1932 assert(sparsebit_is_set(s, first));
1933 assert(!sparsebit_is_clear(s, first));
1934 assert(sparsebit_any_set(s));
1935 assert(!sparsebit_all_clear(s));
1936 if (get_value(first))
1937 return;
1938 if (num_ranges == 1000)
1939 exit(0);
1940 ranges[num_ranges++] = (struct range)
1941 { .first = first, .last = first, .set = true };
1942 break;
1943 case 1:
1944 sparsebit_clear(s, first);
1945 assert(!sparsebit_is_set(s, first));
1946 assert(sparsebit_is_clear(s, first));
1947 assert(sparsebit_any_clear(s));
1948 assert(!sparsebit_all_set(s));
1949 if (!get_value(first))
1950 return;
1951 if (num_ranges == 1000)
1952 exit(0);
1953 ranges[num_ranges++] = (struct range)
1954 { .first = first, .last = first, .set = false };
1955 break;
1956 case 2:
1957 assert(sparsebit_is_set(s, first) == get_value(first));
1958 assert(sparsebit_is_clear(s, first) == !get_value(first));
1959 break;
1960 case 3:
1961 if (sparsebit_any_set(s))
1962 assert(get_value(sparsebit_first_set(s)));
1963 if (sparsebit_any_clear(s))
1964 assert(!get_value(sparsebit_first_clear(s)));
1965 sparsebit_set_all(s);
1966 assert(!sparsebit_any_clear(s));
1967 assert(sparsebit_all_set(s));
1968 num_ranges = 0;
1969 ranges[num_ranges++] = (struct range)
1970 { .first = 0, .last = ~(sparsebit_idx_t)0, .set = true };
1971 break;
1972 case 4:
1973 if (sparsebit_any_set(s))
1974 assert(get_value(sparsebit_first_set(s)));
1975 if (sparsebit_any_clear(s))
1976 assert(!get_value(sparsebit_first_clear(s)));
1977 sparsebit_clear_all(s);
1978 assert(!sparsebit_any_set(s));
1979 assert(sparsebit_all_clear(s));
1980 num_ranges = 0;
1981 break;
1982 case 5:
1983 next = sparsebit_next_set(s, first);
1984 assert(next == 0 || next > first);
1985 assert(next == 0 || get_value(next));
1986 break;
1987 case 6:
1988 next = sparsebit_next_clear(s, first);
1989 assert(next == 0 || next > first);
1990 assert(next == 0 || !get_value(next));
1991 break;
1992 case 7:
1993 next = sparsebit_next_clear(s, first);
1994 if (sparsebit_is_set_num(s, first, num)) {
1995 assert(next == 0 || next > last);
1996 if (first)
1997 next = sparsebit_next_set(s, first - 1);
1998 else if (sparsebit_any_set(s))
1999 next = sparsebit_first_set(s);
2000 else
2001 return;
2002 assert(next == first);
2003 } else {
2004 assert(sparsebit_is_clear(s, first) || next <= last);
2005 }
2006 break;
2007 case 8:
2008 next = sparsebit_next_set(s, first);
2009 if (sparsebit_is_clear_num(s, first, num)) {
2010 assert(next == 0 || next > last);
2011 if (first)
2012 next = sparsebit_next_clear(s, first - 1);
2013 else if (sparsebit_any_clear(s))
2014 next = sparsebit_first_clear(s);
2015 else
2016 return;
2017 assert(next == first);
2018 } else {
2019 assert(sparsebit_is_set(s, first) || next <= last);
2020 }
2021 break;
2022 case 9:
2023 sparsebit_set_num(s, first, num);
2024 assert(sparsebit_is_set_num(s, first, num));
2025 assert(!sparsebit_is_clear_num(s, first, num));
2026 assert(sparsebit_any_set(s));
2027 assert(!sparsebit_all_clear(s));
2028 if (num_ranges == 1000)
2029 exit(0);
2030 ranges[num_ranges++] = (struct range)
2031 { .first = first, .last = last, .set = true };
2032 break;
2033 case 10:
2034 sparsebit_clear_num(s, first, num);
2035 assert(!sparsebit_is_set_num(s, first, num));
2036 assert(sparsebit_is_clear_num(s, first, num));
2037 assert(sparsebit_any_clear(s));
2038 assert(!sparsebit_all_set(s));
2039 if (num_ranges == 1000)
2040 exit(0);
2041 ranges[num_ranges++] = (struct range)
2042 { .first = first, .last = last, .set = false };
2043 break;
2044 case 11:
2045 sparsebit_validate_internal(s);
2046 break;
2047 default:
2048 break;
2049 }
2050}
2051
2052unsigned char get8(void)
2053{
2054 int ch;
2055
2056 ch = getchar();
2057 if (ch == EOF)
2058 exit(0);
2059 return ch;
2060}
2061
2062uint64_t get64(void)
2063{
2064 uint64_t x;
2065
2066 x = get8();
2067 x = (x << 8) | get8();
2068 x = (x << 8) | get8();
2069 x = (x << 8) | get8();
2070 x = (x << 8) | get8();
2071 x = (x << 8) | get8();
2072 x = (x << 8) | get8();
2073 return (x << 8) | get8();
2074}
2075
2076int main(void)
2077{
2078 s = sparsebit_alloc();
2079 for (;;) {
2080 uint8_t op = get8() & 0xf;
2081 uint64_t first = get64();
2082 uint64_t last = get64();
2083
2084 operate(op, first, last);
2085 }
2086}
2087#endif
2088