1 #include "range_set.hpp"
2
rangeset_add_range(RangeSet * rs,BigInt * first,BigInt * last,AstNode * source_node)3 AstNode *rangeset_add_range(RangeSet *rs, BigInt *first, BigInt *last, AstNode *source_node) {
4 for (size_t i = 0; i < rs->src_range_list.length; i += 1) {
5 RangeWithSrc *range_with_src = &rs->src_range_list.at(i);
6 Range *range = &range_with_src->range;
7 if ((bigint_cmp(first, &range->first) == CmpLT && bigint_cmp(last, &range->first) == CmpLT) ||
8 (bigint_cmp(first, &range->last) == CmpGT && bigint_cmp(last, &range->last) == CmpGT))
9 {
10 // first...last is completely before/after `range`
11 }
12 else
13 {
14 return range_with_src->source_node;
15 }
16 }
17 rs->src_range_list.append({{*first, *last}, source_node});
18
19 return nullptr;
20
21 }
22
compare_rangeset(const void * a,const void * b)23 static int compare_rangeset(const void *a, const void *b) {
24 const Range *r1 = &static_cast<const RangeWithSrc*>(a)->range;
25 const Range *r2 = &static_cast<const RangeWithSrc*>(b)->range;
26 // Assume no two ranges overlap
27 switch (bigint_cmp(&r1->first, &r2->first)) {
28 case CmpLT: return -1;
29 case CmpGT: return 1;
30 case CmpEQ: return 0;
31 }
32 zig_unreachable();
33 }
34
rangeset_sort(RangeSet * rs)35 void rangeset_sort(RangeSet *rs) {
36 if (rs->src_range_list.length > 1) {
37 qsort(rs->src_range_list.items, rs->src_range_list.length,
38 sizeof(RangeWithSrc), compare_rangeset);
39 }
40 }
41
rangeset_spans(RangeSet * rs,BigInt * first,BigInt * last)42 bool rangeset_spans(RangeSet *rs, BigInt *first, BigInt *last) {
43 if (rs->src_range_list.length == 0)
44 return false;
45
46 rangeset_sort(rs);
47
48 const Range *first_range = &rs->src_range_list.at(0).range;
49 if (bigint_cmp(&first_range->first, first) != CmpEQ)
50 return false;
51
52 const Range *last_range = &rs->src_range_list.last().range;
53 if (bigint_cmp(&last_range->last, last) != CmpEQ)
54 return false;
55
56 BigInt one;
57 bigint_init_unsigned(&one, 1);
58
59 // Make sure there are no holes in the first...last range
60 for (size_t i = 1; i < rs->src_range_list.length; i++) {
61 const Range *range = &rs->src_range_list.at(i).range;
62 const Range *prev_range = &rs->src_range_list.at(i - 1).range;
63
64 assert(bigint_cmp(&prev_range->last, &range->first) == CmpLT);
65
66 BigInt last_plus_one;
67 bigint_add(&last_plus_one, &prev_range->last, &one);
68
69 if (bigint_cmp(&last_plus_one, &range->first) != CmpEQ)
70 return false;
71 }
72
73 return true;
74 }
75