Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit949840f

Browse files
committed
improve irange_list_intersection(), make irange_cmp_lossiness() inline static, more tests
1 parent07bf75f commit949840f

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(IndexRangea,IndexRangeb)
50-
{
51-
if (is_irange_lossy(a)==is_irange_lossy(b))
52-
returnIR_EQ_LOSSINESS;
53-
54-
if (is_irange_lossy(a))
55-
returnIR_A_LOSSY;
56-
57-
if (is_irange_lossy(b))
58-
returnIR_B_LOSSY;
59-
60-
returnIR_EQ_LOSSINESS;
61-
}
62-
6347

6448
/* Make union of two conjuncted ranges */
6549
IndexRange
@@ -161,6 +145,10 @@ irange_union_internal(IndexRange first,
161145
IndexRangesecond,
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
IndexRangera=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-
IndexRangeintersect,last;
330+
IndexRangeir_intersection;
331+
boolglued_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+
IndexRangelast=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+
IndexRangeir_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 nextranges. We use upper bound of currentrange 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 nextiranges. We use upper bound of currentirange to
363+
*determinewhich lists to fetch, since lower bound of next
364+
*irange is greater (orequal) 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
#defineirange_upper(irange)( (uint32) (irange.upper & IRANGE_BONDARY_MASK) )
4545

4646

47+
#definelfirst_irange(lc)( *(IndexRange *) lfirst(lc) )
48+
#definelappend_irange(list,irange)( lappend((list), alloc_irange(irange)) )
49+
#definelcons_irange(irange,list)( lcons(alloc_irange(irange), (list)) )
50+
#definelist_make1_irange(irange)( lcons(alloc_irange(irange), NIL) )
51+
#definellast_irange(list)( lfirst_irange(list_tail(list)) )
52+
#definelinitial_irange(list)( lfirst_irange(list_head(list)) )
53+
54+
4755
inlinestaticIndexRange
4856
make_irange(uint32lower,uint32upper,boollossy)
4957
{
@@ -93,14 +101,6 @@ irb_succ(uint32 boundary)
93101
}
94102

95103

96-
#definelfirst_irange(lc)( *(IndexRange *) lfirst(lc) )
97-
#definelappend_irange(list,irange)( lappend((list), alloc_irange(irange)) )
98-
#definelcons_irange(irange,list)( lcons(alloc_irange(irange), (list)) )
99-
#definelist_make1_irange(irange)( lcons(alloc_irange(irange), NIL) )
100-
#definellast_irange(list)( lfirst_irange(list_tail(list)) )
101-
#definelinitial_irange(list)( lfirst_irange(list_head(list)) )
102-
103-
104104
/* Result of function irange_cmp_lossiness() */
105105
typedefenum
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+
inlinestaticir_cmp_lossiness
114+
irange_cmp_lossiness(IndexRangea,IndexRangeb)
115+
{
116+
if (is_irange_lossy(a)==is_irange_lossy(b))
117+
returnIR_EQ_LOSSINESS;
118+
119+
if (is_irange_lossy(a))
120+
returnIR_A_LOSSY;
121+
122+
if (is_irange_lossy(b))
123+
returnIR_B_LOSSY;
124+
125+
returnIR_EQ_LOSSINESS;
126+
}
127+
112128

113129
/* Various traits */
114130
booliranges_intersect(IndexRangea,IndexRangeb);
115131
booliranges_adjoin(IndexRangea,IndexRangeb);
116132
boolirange_eq_bounds(IndexRangea,IndexRangeb);
117-
ir_cmp_lossinessirange_cmp_lossiness(IndexRangea,IndexRangeb);
118133

119134
/* Basic operations on IndexRanges */
120135
IndexRangeirange_union_simple(IndexRangea,IndexRangeb);

‎tests/cmocka/rangeset_tests.c‎

Lines changed: 68 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,9 @@
1818
staticvoidtest_irange_list_union_merge(void**state);
1919
staticvoidtest_irange_list_union_lossy_cov(void**state);
2020
staticvoidtest_irange_list_union_complete_cov(void**state);
21-
staticvoidtest_irange_list_union_intersection(void**state);
21+
staticvoidtest_irange_list_union_intersecting(void**state);
22+
23+
staticvoidtest_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 adjointlists */
50+
/* Test merges of adjointIndexRanges */
4851
staticvoid
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
staticvoid
215-
test_irange_list_union_intersection(void**state)
219+
test_irange_list_union_intersecting(void**state)
216220
{
217221
IndexRangea,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+
staticvoid
288+
test_irange_list_intersection(void**state)
289+
{
290+
IndexRangea,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)
[8]ページ先頭
©2009-2025 Movatter.jp