Sorry Dan overlooked at it.
Philip's patch seems to be very concise and seems perfect to me.
Attaching the patch and log for the same.
With regards
Kamesh Jayachandran
Daniel Rall wrote:
> Hey Kamesh, did you see Philip's patch for this thread, and his
> subsequent comments? Was the consensus was that Philip's fix was both
> simpler and fully correct?
>
> Thanks, Dan
>
> On Mon, 11 Sep 2006, Kamesh Jayachandran wrote:
>
>
>> Thanks Jonathan,
>> Your patch looks perfect to me.
>>
>> I am attaching my tweaks to it.(Adding the MIN macro and a log message.)
>>
>> Someone with a karma please check in the same.
>>
>> It is not about optimizing the code, rather easy comprehension.
>>
>>
>> With regards
>> Kamesh Jayachandran
>> Jonathan Gilbert wrote:
>>
>>> At 09:40 PM 06/09/2006 +0100, Philip Martin wrote:
>>>
>>>
>>>> "Jonathan Gilbert" <o2w9gs702@sneakemail.com> writes:
>>>>
>>>>
>>>>> static svn_boolean_t
>>>>> combine_ranges(svn_merge_range_t **output, svn_merge_range_t *in1,
>>>>> svn_merge_range_t *in2)
>>>>> {
>>>>> if (range_contains_revision(in1, in2->start)
>>>>> || range_contains_revision(in2, in1->start)
>>>>> || ranges_are_adjacent(in1, in2))
>>>>> {
>>>>>
>>>>>
>>> [snip]
>>>
>>>
>>>> I haven't been following the merge tracking stuff, but detecting
>>>> overlapping ranges is notorious for being both tricky and simple: it's
>>>> tricky to get the algorithm right, but the right algorithm is simple.
>>>>
>>>> static svn_boolean_t
>>>> combine_ranges(svn_merge_range_t **output,
>>>> svn_merge_range_t *in1,
>>>> svn_merge_range_t *in2)
>>>> {
>>>> if (in1->start <= in2->end + 1 && in2->start <= in1->end + 1)
>>>> {
>>>>
>>>>
>>> [snip]
>>>
>>> Wow, that _is_ concise :-) I actually had a feeling something like that
>>> would be possible when I was composing my message, but it didn't spring
>>> into my head at the time. In any case, though my example is more verbose
>>> and adds two extra functions, I think it's more maintainable, and it is
>>> certainly more self-documenting.
>>>
>>> The added functions could also probably be used elsewhere to improve the
>>> readability/maintainability of other code that needs similar operations.
>>> Certainly, there's no reason to overoptimize something that is only
>>> O(number of revisions/ranges of revisions to be merged). :-)
>>>
>>> Jonathan Gilbert
>>>
>>> ---------------------------------------------------------------------
>>> To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
>>> For additional commands, e-mail: dev-help@subversion.tigris.org
>>>
>>>
>>>
>
>
>> [[[
>> Patch by: Jonathan Gilbert<o2w9gs702@sneakemail.com>
>> Kamesh Jayachandran <kamesh@collab.net>
>>
>> Simplifying the code.
>>
>> * subversion/libsvn_subr/mergeinfo.c
>> (MIN): New macro.
>> (range_contains_revision): New function.
>> (ranges_are_adjacent): New function.
>> (combine_ranges):
>> New simplified equivalent implementation.
>> Removes the revert range combining.
>> ]]]
>>
>
>
>> Index: subversion/libsvn_subr/mergeinfo.c
>> ===================================================================
>> --- subversion/libsvn_subr/mergeinfo.c (revision 21420)
>> +++ subversion/libsvn_subr/mergeinfo.c (working copy)
>> @@ -32,61 +32,37 @@
>> #define MAX(a, b) ((a) < (b) ? (b) : (a))
>> #endif
>>
>> +/* Define a MIN macro if we don't already have one */
>> +#ifndef MIN
>> +#define MIN(a, b) ((a) < (b) ? (a) : (b))
>> +#endif
>> +
>> +static svn_boolean_t
>> +range_contains_revision(svn_merge_range_t *range, svn_revnum_t revision)
>> +{
>> + return (range->start <= revision) && (range->end >= revision);
>> +}
>> +
>> +static svn_boolean_t
>> +ranges_are_adjacent(svn_merge_range_t *in1, svn_merge_range_t *in2)
>> +{
>> + return (in1->end + 1 == in2->start) || (in2->end + 1 == in1->start);
>> +}
>> +
>> /* Attempt to combine two ranges, IN1 and IN2, and put the result in
>> OUTPUT. Return whether they could be combined. */
>> static svn_boolean_t
>> combine_ranges(svn_merge_range_t **output, svn_merge_range_t *in1,
>> svn_merge_range_t *in2)
>> {
>> - if (in1->start == in2->start)
>> + if (range_contains_revision(in1, in2->start)
>> + || range_contains_revision(in2, in1->start)
>> + || ranges_are_adjacent(in1, in2))
>> {
>> - (*output)->start = in1->start;
>> + (*output)->start = MIN(in1->start, in2->start);
>> (*output)->end = MAX(in1->end, in2->end);
>> return TRUE;
>> }
>> - /* [1,4] U [5,9] = [1,9] in subversion revisions */
>> - else if (in2->start == in1->end
>> - || in2->start == in1->end + 1)
>> - {
>> - (*output)->start = in1->start;
>> - (*output)->end = in2->end;
>> - return TRUE;
>> - }
>> - else if (in1->start == in2->end
>> - || in1->start == in2->end + 1)
>> - {
>> - (*output)->start = in2->start;
>> - (*output)->end = in1->end;
>> - return TRUE;
>> - }
>> - else if (in1->start <= in2->start
>> - && in1->end >= in2->start)
>> - {
>> - (*output)->start = in1->start;
>> - (*output)->end = MAX(in1->end, in2->end);
>> - return TRUE;
>> - }
>> - else if (in2->start <= in1->start
>> - && in2->end >= in1->start)
>> - {
>> - (*output)->start = in2->start;
>> - (*output)->end = MAX(in1->end, in2->end);
>> - return TRUE;
>> - }
>> - else if (in1->start >= in2->start
>> - && in1->end <= in2->end)
>> - {
>> - (*output)->start = in2->start;
>> - (*output)->end = in2->end;
>> - return TRUE;
>> - }
>> - else if (in2->start >= in1->start
>> - && in2->end <= in1->end)
>> - {
>> - (*output)->start = in1->start;
>> - (*output)->end = in1->end;
>> - return TRUE;
>> - }
>>
>> return FALSE;
>> }
>>
[[[
Patch by: Philip Martin <philip@codematters.co.uk>
Kamesh Jayachandran <kamesh@collab.net>
Reviewed by: Jonathan Gilbert<o2w9gs702@sneakemail.com>
Simplifying the code to make use of the standard alogrithm.
* subversion/libsvn_subr/mergeinfo.c
(MIN): New macro.
(combine_ranges):
New simplified equivalent implementation based on range overlapping
detection algorithm.
]]]
Index: subversion/libsvn_subr/mergeinfo.c
===================================================================
--- subversion/libsvn_subr/mergeinfo.c (revision 21420)
+++ subversion/libsvn_subr/mergeinfo.c (working copy)
@@ -32,62 +32,26 @@
#define MAX(a, b) ((a) < (b) ? (b) : (a))
#endif
+/* Define a MIN macro if we don't already have one */
+#ifndef MIN
+#define MIN(a, b) ((a) < (b) ? (a) : (b))
+#endif
+
/* Attempt to combine two ranges, IN1 and IN2, and put the result in
- OUTPUT. Return whether they could be combined. */
+ OUTPUT. Return whether they could be combined.
+ Range overlapping detection algorithm from
+ http://c2.com/cgi-bin/wiki/fullSearch?TestIfDateRangesOverlap
+*/
static svn_boolean_t
combine_ranges(svn_merge_range_t **output, svn_merge_range_t *in1,
svn_merge_range_t *in2)
{
- if (in1->start == in2->start)
+ if (in1->start <= in2->end + 1 && in2->start <= in1->end + 1)
{
- (*output)->start = in1->start;
+ (*output)->start = MIN(in1->start, in2->start);
(*output)->end = MAX(in1->end, in2->end);
return TRUE;
}
- /* [1,4] U [5,9] = [1,9] in subversion revisions */
- else if (in2->start == in1->end
- || in2->start == in1->end + 1)
- {
- (*output)->start = in1->start;
- (*output)->end = in2->end;
- return TRUE;
- }
- else if (in1->start == in2->end
- || in1->start == in2->end + 1)
- {
- (*output)->start = in2->start;
- (*output)->end = in1->end;
- return TRUE;
- }
- else if (in1->start <= in2->start
- && in1->end >= in2->start)
- {
- (*output)->start = in1->start;
- (*output)->end = MAX(in1->end, in2->end);
- return TRUE;
- }
- else if (in2->start <= in1->start
- && in2->end >= in1->start)
- {
- (*output)->start = in2->start;
- (*output)->end = MAX(in1->end, in2->end);
- return TRUE;
- }
- else if (in1->start >= in2->start
- && in1->end <= in2->end)
- {
- (*output)->start = in2->start;
- (*output)->end = in2->end;
- return TRUE;
- }
- else if (in2->start >= in1->start
- && in2->end <= in1->end)
- {
- (*output)->start = in1->start;
- (*output)->end = in1->end;
- return TRUE;
- }
-
return FALSE;
}
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Tue Sep 12 09:28:13 2006