Skip to content

Commit 949840f

Browse files
funbringerfunbringer
committed
improve irange_list_intersection(), make irange_cmp_lossiness() inline static, more tests
1 parent 07bf75f commit 949840f

File tree

3 files changed

+123
-47
lines changed

3 files changed

+123
-47
lines changed

‎src/rangeset.c

Lines changed: 31 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -44,22 +44,6 @@ irange_eq_bounds(IndexRange a, IndexRange b)
4444
(irange_upper(a) == irange_upper(b));
4545
}
4646

47-
/* Comapre lossiness factor of two ranges */
48-
ir_cmp_lossiness
49-
irange_cmp_lossiness(IndexRange a, IndexRange b)
50-
{
51-
if (is_irange_lossy(a) == is_irange_lossy(b))
52-
return IR_EQ_LOSSINESS;
53-
54-
if (is_irange_lossy(a))
55-
return IR_A_LOSSY;
56-
57-
if (is_irange_lossy(b))
58-
return IR_B_LOSSY;
59-
60-
return IR_EQ_LOSSINESS;
61-
}
62-
6347

6448
/* Make union of two conjuncted ranges */
6549
IndexRange
@@ -161,6 +145,10 @@ irange_union_internal(IndexRange first,
161145
IndexRange second,
162146
List **new_iranges)
163147
{
148+
/* Assert that both IndexRanges are valid */
149+
Assert(is_irange_valid(first));
150+
Assert(is_irange_valid(second));
151+
164152
/* Swap 'first' and 'second' if order is incorrect */
165153
if (irange_lower(first) > irange_lower(second))
166154
{
@@ -332,39 +320,48 @@ irange_list_intersection(List *a, List *b)
332320
IndexRange ra = lfirst_irange(ca),
333321
rb = lfirst_irange(cb);
334322

323+
/* Assert that both IndexRanges are valid */
324+
Assert(is_irange_valid(ra));
325+
Assert(is_irange_valid(rb));
326+
335327
/* Only care about intersecting ranges */
336328
if (iranges_intersect(ra, rb))
337329
{
338-
IndexRange intersect, last;
330+
IndexRange ir_intersection;
331+
bool glued_to_last = false;
339332

340333
/*
341334
* Get intersection and try to "glue" it to
342-
* previous range, put it separately otherwise.
335+
* last irange, put it separately otherwise.
343336
*/
344-
intersect = irange_intersection_simple(ra, rb);
337+
ir_intersection = irange_intersection_simple(ra, rb);
345338
if (result != NIL)
346339
{
347-
last = llast_irange(result);
348-
if (iranges_adjoin(last, intersect) &&
349-
is_irange_lossy(last) == is_irange_lossy(intersect))
350-
{
351-
llast(result) = alloc_irange(irange_union_simple(last, intersect));
352-
}
353-
else
340+
IndexRange last = llast_irange(result);
341+
342+
/* Test if we can glue 'last' and 'ir_intersection' */
343+
if (irange_cmp_lossiness(last, ir_intersection) == IR_EQ_LOSSINESS &&
344+
iranges_adjoin(last, ir_intersection))
354345
{
355-
result = lappend_irange(result, intersect);
346+
IndexRange ir_union = irange_union_simple(last, ir_intersection);
347+
348+
/* We allocate a new IndexRange for safety */
349+
llast(result) = alloc_irange(ir_union);
350+
351+
/* Successfully glued them */
352+
glued_to_last = true;
356353
}
357354
}
358-
else
359-
{
360-
result = lappend_irange(result, intersect);
361-
}
355+
356+
/* Append IndexRange if we couldn't glue it */
357+
if (!glued_to_last)
358+
result = lappend_irange(result, ir_intersection);
362359
}
363360

364361
/*
365-
* Fetch next ranges. We use upper bound of current range to determine
366-
* which lists to fetch, since lower bound of next range is greater (or
367-
* equal) to upper bound of current.
362+
* Fetch next iranges. We use upper bound of current irange to
363+
* determine which lists to fetch, since lower bound of next
364+
* irange is greater (or equal) to upper bound of current.
368365
*/
369366
if (irange_upper(ra) <= irange_upper(rb))
370367
ca = lnext(ca);

‎src/rangeset.h

Lines changed: 24 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,14 @@ typedef struct {
4444
#define irange_upper(irange) ( (uint32) (irange.upper & IRANGE_BONDARY_MASK) )
4545

4646

47+
#define lfirst_irange(lc) ( *(IndexRange *) lfirst(lc) )
48+
#define lappend_irange(list, irange) ( lappend((list), alloc_irange(irange)) )
49+
#define lcons_irange(irange, list) ( lcons(alloc_irange(irange), (list)) )
50+
#define list_make1_irange(irange) ( lcons(alloc_irange(irange), NIL) )
51+
#define llast_irange(list) ( lfirst_irange(list_tail(list)) )
52+
#define linitial_irange(list) ( lfirst_irange(list_head(list)) )
53+
54+
4755
inline static IndexRange
4856
make_irange(uint32 lower, uint32 upper, bool lossy)
4957
{
@@ -93,14 +101,6 @@ irb_succ(uint32 boundary)
93101
}
94102

95103

96-
#define lfirst_irange(lc) ( *(IndexRange *) lfirst(lc) )
97-
#define lappend_irange(list, irange) ( lappend((list), alloc_irange(irange)) )
98-
#define lcons_irange(irange, list) ( lcons(alloc_irange(irange), (list)) )
99-
#define list_make1_irange(irange) ( lcons(alloc_irange(irange), NIL) )
100-
#define llast_irange(list) ( lfirst_irange(list_tail(list)) )
101-
#define linitial_irange(list) ( lfirst_irange(list_head(list)) )
102-
103-
104104
/* Result of function irange_cmp_lossiness() */
105105
typedef enum
106106
{
@@ -109,12 +109,27 @@ typedef enum
109109
IR_B_LOSSY /* IndexRange 'b' is lossy ('a' is not) */
110110
} ir_cmp_lossiness;
111111

112+
/* Comapre lossiness factor of two IndexRanges */
113+
inline static ir_cmp_lossiness
114+
irange_cmp_lossiness(IndexRange a, IndexRange b)
115+
{
116+
if (is_irange_lossy(a) == is_irange_lossy(b))
117+
return IR_EQ_LOSSINESS;
118+
119+
if (is_irange_lossy(a))
120+
return IR_A_LOSSY;
121+
122+
if (is_irange_lossy(b))
123+
return IR_B_LOSSY;
124+
125+
return IR_EQ_LOSSINESS;
126+
}
127+
112128

113129
/* Various traits */
114130
bool iranges_intersect(IndexRange a, IndexRange b);
115131
bool iranges_adjoin(IndexRange a, IndexRange b);
116132
bool irange_eq_bounds(IndexRange a, IndexRange b);
117-
ir_cmp_lossiness irange_cmp_lossiness(IndexRange a, IndexRange b);
118133

119134
/* Basic operations on IndexRanges */
120135
IndexRange irange_union_simple(IndexRange a, IndexRange b);

‎tests/cmocka/rangeset_tests.c

Lines changed: 68 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,9 @@
1818
static void test_irange_list_union_merge(void **state);
1919
static void test_irange_list_union_lossy_cov(void **state);
2020
static void test_irange_list_union_complete_cov(void **state);
21-
static void test_irange_list_union_intersection(void **state);
21+
static void test_irange_list_union_intersecting(void **state);
22+
23+
static void test_irange_list_intersection(void **state);
2224

2325

2426
/* Entrypoint */
@@ -31,7 +33,8 @@ main(void)
3133
cmocka_unit_test(test_irange_list_union_merge),
3234
cmocka_unit_test(test_irange_list_union_lossy_cov),
3335
cmocka_unit_test(test_irange_list_union_complete_cov),
34-
cmocka_unit_test(test_irange_list_union_intersection),
36+
cmocka_unit_test(test_irange_list_union_intersecting),
37+
cmocka_unit_test(test_irange_list_intersection),
3538
};
3639

3740
/* Run series of tests */
@@ -44,7 +47,7 @@ main(void)
4447
* ----------------------
4548
*/
4649

47-
/* Test merges of adjoint lists */
50+
/* Test merges of adjoint IndexRanges */
4851
static void
4952
test_irange_list_union_merge(void **state)
5053
{
@@ -211,8 +214,9 @@ test_irange_list_union_complete_cov(void **state)
211214
"[0-100]C");
212215
}
213216

217+
/* Several IndexRanges intersect, unite them */
214218
static void
215-
test_irange_list_union_intersection(void **state)
219+
test_irange_list_union_intersecting(void **state)
216220
{
217221
IndexRange a, b;
218222
List *unmerged,
@@ -277,3 +281,63 @@ test_irange_list_union_intersection(void **state)
277281
assert_string_equal(rangeset_print(union_result),
278282
"[0-45]C, [46-63]L, [64-100]C");
279283
}
284+
285+
286+
/* Test intersection of IndexRanges */
287+
static void
288+
test_irange_list_intersection(void **state)
289+
{
290+
IndexRange a, b;
291+
List *intersection_result;
292+
293+
294+
/* Subtest #0 */
295+
a = make_irange(0, 100, IR_LOSSY);
296+
b = make_irange(10, 20, IR_LOSSY);
297+
298+
intersection_result = irange_list_intersection(list_make1_irange(a),
299+
list_make1_irange(b));
300+
301+
assert_string_equal(rangeset_print(intersection_result),
302+
"[10-20]L");
303+
304+
/* Subtest #1 */
305+
a = make_irange(0, 100, IR_LOSSY);
306+
b = make_irange(10, 20, IR_COMPLETE);
307+
308+
intersection_result = irange_list_intersection(list_make1_irange(a),
309+
list_make1_irange(b));
310+
311+
assert_string_equal(rangeset_print(intersection_result),
312+
"[10-20]L");
313+
314+
/* Subtest #2 */
315+
a = make_irange(0, 100, IR_COMPLETE);
316+
b = make_irange(10, 20, IR_LOSSY);
317+
318+
intersection_result = irange_list_intersection(list_make1_irange(a),
319+
list_make1_irange(b));
320+
321+
assert_string_equal(rangeset_print(intersection_result),
322+
"[10-20]L");
323+
324+
/* Subtest #3 */
325+
a = make_irange(15, 25, IR_COMPLETE);
326+
b = make_irange(10, 20, IR_LOSSY);
327+
328+
intersection_result = irange_list_intersection(list_make1_irange(a),
329+
list_make1_irange(b));
330+
331+
assert_string_equal(rangeset_print(intersection_result),
332+
"[15-20]L");
333+
334+
/* Subtest #4 */
335+
a = make_irange(15, 25, IR_COMPLETE);
336+
b = make_irange(10, 20, IR_COMPLETE);
337+
338+
intersection_result = irange_list_intersection(list_make1_irange(a),
339+
list_make1_irange(b));
340+
341+
assert_string_equal(rangeset_print(intersection_result),
342+
"[15-20]C");
343+
}

0 commit comments

Comments
 (0)