You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@subversion.apache.org by hw...@apache.org on 2011/10/19 19:19:16 UTC
svn commit: r1186352 - in /subversion/branches/1.7.x: ./ STATUS
subversion/include/svn_sorts.h subversion/libsvn_client/merge.c
subversion/libsvn_subr/mergeinfo.c subversion/libsvn_subr/sorts.c
subversion/tests/libsvn_subr/mergeinfo-test.c
Author: hwright
Date: Wed Oct 19 17:19:15 2011
New Revision: 1186352
URL: http://svn.apache.org/viewvc?rev=1186352&view=rev
Log:
Reintegrate the 1.7.x-r1180514 branch:
* r1180154, r1181090, r1181110, r1181215
Fix svn_rangelist_merge so it allocates new svn_merge_range_t elements
only when absolutely necessary.
Justification:
This addresses a serious inefficiency in memory usage when
svn_rangelist_merge (or any of its callers like
svn_mergeinfo_catalog_merge and svn_mergeinfo_merge2) are called in
a loop. Prior to this change svn_rangelist_merge2 could potentially
reallocate *every* range in both rangelists. For example, the peak
working set memory for the reintegrate merge described in
http://svn.haxx.se/dev/archive-2011-09/0254.shtml was 1,324,664 KB
with trunk@1179545. With this group that drops to 26,880 KB.
Branch:
^/subversion/branches/1.7.x-r1180154
Notes:
r1180154 is the primary fix with some new tests. r1181090 and r1181215
is a minor optimization along with more new tests. r1181110 is just
a doc string typo fix.
Votes:
+1: pburba, rhuijben, stsp
Modified:
subversion/branches/1.7.x/ (props changed)
subversion/branches/1.7.x/STATUS
subversion/branches/1.7.x/subversion/include/svn_sorts.h
subversion/branches/1.7.x/subversion/libsvn_client/merge.c
subversion/branches/1.7.x/subversion/libsvn_subr/mergeinfo.c
subversion/branches/1.7.x/subversion/libsvn_subr/sorts.c
subversion/branches/1.7.x/subversion/tests/libsvn_subr/mergeinfo-test.c
Propchange: subversion/branches/1.7.x/
------------------------------------------------------------------------------
--- svn:mergeinfo (original)
+++ svn:mergeinfo Wed Oct 19 17:19:15 2011
@@ -10,6 +10,7 @@
/subversion/branches/1.7.x-r1159093:1159097-1159230
/subversion/branches/1.7.x-r1163557:1163574-1170648
/subversion/branches/1.7.x-r1173425:1173429-1176454
+/subversion/branches/1.7.x-r1180154:1186224-1186351
/subversion/branches/atomic-revprop:965046-1000689
/subversion/branches/bdb-reverse-deltas:872050-872529
/subversion/branches/diff-callbacks3:870059-870761
@@ -64,4 +65,4 @@
/subversion/branches/tree-conflicts:868291-873154
/subversion/branches/tree-conflicts-notify:873926-874008
/subversion/branches/uris-as-urls:1060426-1064427
-/subversion/trunk:1146013,1146121,1146219,1146222,1146274,1146492,1146555,1146606,1146620,1146684,1146781,1146832,1146834,1146870,1146899,1146904,1147293,1147299,1147309,1147882,1148071,1148083,1148094,1148131,1148374,1148424,1148566,1148588,1148652,1148662,1148699,1148853,1148877,1148882,1148936,1149103,1149105,1149135,1149141,1149160,1149228,1149240,1149343,1149371-1149372,1149377,1149398,1149401,1149539,1149572,1149627,1149675,1149701,1149713,1150242,1150254,1150260-1150261,1150266,1150302,1150327,1150368,1150372,1150441,1150506,1150812,1150853,1151036,1151177,1151610,1151854,1151906,1151911,1152129,1152140,1152189-1152190,1152267,1152282,1152286,1152726,1152809,1153138,1153141,1153416,1153540,1153566,1153799,1153807,1153968,1154009,1154023,1154115,1154119,1154121,1154144,1154155,1154159,1154165,1154215,1154225,1154273,1154278,1154379,1154382,1154461,1154717-1154718,1154733,1154908,1154982,1155015,1155044,1155124,1155131,1155160,1155313,1155334,1155391,1155404,1156085,115
6098,1156216,1156218,1156312,1156527,1156717,1156721,1156750,1156827,1156838,1157416,1158187,1158193-1158194,1158196,1158201,1158207,1158209-1158210,1158217,1158285,1158288,1158303,1158309,1158407,1158419,1158421,1158436,1158455,1158616-1158617,1158634,1158854,1158875,1158886,1158893,1158896,1158919,1158924,1158963,1159093,1159098,1159101,1159132,1159136,1159148,1159230,1159275,1159400,1159686,1159760,1159772,1160605,1160671,1160682,1160704-1160705,1160756,1161063,1161080,1161185,1161210,1161683,1161721,1162024,1162033,1162201,1162516,1162880,1162974,1162995,1163243,1163383,1163557,1163792,1163953,1164027,1164386,1164426,1164517,1164535,1164554,1164580,1164614,1164645,1164760,1164765,1166500,1166555,1166678,1167062,1167173,1167209,1167269,1167503,1167659,1167681,1169524,1169531,1169650,1171708,1173111,1173425,1173639,1174051,1174060,1174652,1174761,1174797-1174798,1174806,1175888,1176915,1176949,1177001,1177492,1178280,1178282,1178942,1179680,1179767,1181155,1181609,1181666,
1182115,1182527,1182904,1182909,1183054,1183263,1183347,1185222,1185242,1185280,1185282,1185730,1185911,1185918
+/subversion/trunk:1146013,1146121,1146219,1146222,1146274,1146492,1146555,1146606,1146620,1146684,1146781,1146832,1146834,1146870,1146899,1146904,1147293,1147299,1147309,1147882,1148071,1148083,1148094,1148131,1148374,1148424,1148566,1148588,1148652,1148662,1148699,1148853,1148877,1148882,1148936,1149103,1149105,1149135,1149141,1149160,1149228,1149240,1149343,1149371-1149372,1149377,1149398,1149401,1149539,1149572,1149627,1149675,1149701,1149713,1150242,1150254,1150260-1150261,1150266,1150302,1150327,1150368,1150372,1150441,1150506,1150812,1150853,1151036,1151177,1151610,1151854,1151906,1151911,1152129,1152140,1152189-1152190,1152267,1152282,1152286,1152726,1152809,1153138,1153141,1153416,1153540,1153566,1153799,1153807,1153968,1154009,1154023,1154115,1154119,1154121,1154144,1154155,1154159,1154165,1154215,1154225,1154273,1154278,1154379,1154382,1154461,1154717-1154718,1154733,1154908,1154982,1155015,1155044,1155124,1155131,1155160,1155313,1155334,1155391,1155404,1156085,115
6098,1156216,1156218,1156312,1156527,1156717,1156721,1156750,1156827,1156838,1157416,1158187,1158193-1158194,1158196,1158201,1158207,1158209-1158210,1158217,1158285,1158288,1158303,1158309,1158407,1158419,1158421,1158436,1158455,1158616-1158617,1158634,1158854,1158875,1158886,1158893,1158896,1158919,1158924,1158963,1159093,1159098,1159101,1159132,1159136,1159148,1159230,1159275,1159400,1159686,1159760,1159772,1160605,1160671,1160682,1160704-1160705,1160756,1161063,1161080,1161185,1161210,1161683,1161721,1162024,1162033,1162201,1162516,1162880,1162974,1162995,1163243,1163383,1163557,1163792,1163953,1164027,1164386,1164426,1164517,1164535,1164554,1164580,1164614,1164645,1164760,1164765,1166500,1166555,1166678,1167062,1167173,1167209,1167269,1167503,1167659,1167681,1169524,1169531,1169650,1171708,1173111,1173425,1173639,1174051,1174060,1174652,1174761,1174797-1174798,1174806,1175888,1176915,1176949,1177001,1177492,1178280,1178282,1178942,1179680,1179767,1180154,1181090,1181110,
1181155,1181215,1181609,1181666,1182115,1182527,1182904,1182909,1183054,1183263,1183347,1185222,1185242,1185280,1185282,1185730,1185911,1185918
Modified: subversion/branches/1.7.x/STATUS
URL: http://svn.apache.org/viewvc/subversion/branches/1.7.x/STATUS?rev=1186352&r1=1186351&r2=1186352&view=diff
==============================================================================
--- subversion/branches/1.7.x/STATUS (original)
+++ subversion/branches/1.7.x/STATUS Wed Oct 19 17:19:15 2011
@@ -86,24 +86,3 @@ Veto-blocked changes:
Approved changes:
=================
-
- * r1180154, r1181090, r1181110, r1181215
- Fix svn_rangelist_merge so it allocates new svn_merge_range_t elements
- only when absolutely necessary.
- Justification:
- This addresses a serious inefficiency in memory usage when
- svn_rangelist_merge (or any of its callers like
- svn_mergeinfo_catalog_merge and svn_mergeinfo_merge2) are called in
- a loop. Prior to this change svn_rangelist_merge2 could potentially
- reallocate *every* range in both rangelists. For example, the peak
- working set memory for the reintegrate merge described in
- http://svn.haxx.se/dev/archive-2011-09/0254.shtml was 1,324,664 KB
- with trunk@1179545. With this group that drops to 26,880 KB.
- Branch:
- ^/subversion/branches/1.7.x-r1180154
- Notes:
- r1180154 is the primary fix with some new tests. r1181090 and r1181215
- is a minor optimization along with more new tests. r1181110 is just
- a doc string typo fix.
- Votes:
- +1: pburba, rhuijben, stsp
Modified: subversion/branches/1.7.x/subversion/include/svn_sorts.h
URL: http://svn.apache.org/viewvc/subversion/branches/1.7.x/subversion/include/svn_sorts.h?rev=1186352&r1=1186351&r2=1186352&view=diff
==============================================================================
--- subversion/branches/1.7.x/subversion/include/svn_sorts.h (original)
+++ subversion/branches/1.7.x/subversion/include/svn_sorts.h Wed Oct 19 17:19:15 2011
@@ -182,6 +182,16 @@ svn_sort__array_insert(const void *new_e
int insert_index);
+/* Remove ELEMENTS_TO_DELETE elements starting at DELETE_INDEX from the
+ array ARR. If DELETE_INDEX is not a valid element of ARR,
+ ELEMENTS_TO_DELETE is not greater than zero, or
+ DELETE_INDEX + ELEMENTS_TO_DELETE is greater than ARR->NELTS, then do
+ nothing. */
+void
+svn_sort__array_delete(apr_array_header_t *arr,
+ int delete_index,
+ int elements_to_delete);
+
#ifdef __cplusplus
}
#endif /* __cplusplus */
Modified: subversion/branches/1.7.x/subversion/libsvn_client/merge.c
URL: http://svn.apache.org/viewvc/subversion/branches/1.7.x/subversion/libsvn_client/merge.c?rev=1186352&r1=1186351&r2=1186352&view=diff
==============================================================================
--- subversion/branches/1.7.x/subversion/libsvn_client/merge.c (original)
+++ subversion/branches/1.7.x/subversion/libsvn_client/merge.c Wed Oct 19 17:19:15 2011
@@ -4594,30 +4594,6 @@ make_merge_conflict_error(const char *ta
r->start, r->end, svn_dirent_local_style(target_wcpath, scratch_pool));
}
-/* Remove the element at IDX from the array ARR.
- If IDX is not a valid element of ARR do nothing. */
-static void
-remove_element_from_array(apr_array_header_t *arr,
- int idx)
-{
- /* Do we have a valid index? */
- if (idx >= 0 && idx < arr->nelts)
- {
- if (idx == (arr->nelts - 1))
- {
- /* Deleting the last or only element in an array is easy. */
- apr_array_pop(arr);
- }
- else
- {
- memmove(arr->elts + arr->elt_size * idx,
- arr->elts + arr->elt_size * (idx + 1),
- arr->elt_size * (arr->nelts - 1 - idx));
- --(arr->nelts);
- }
- }
-}
-
/* Helper for do_directory_merge().
TARGET_WCPATH is a directory and CHILDREN_WITH_MERGEINFO is filled
@@ -4643,7 +4619,7 @@ remove_absent_children(const char *targe
if ((child->absent || child->scheduled_for_deletion)
&& svn_dirent_is_ancestor(target_wcpath, child->abspath))
{
- remove_element_from_array(children_with_mergeinfo, i--);
+ svn_sort__array_delete(children_with_mergeinfo, i--, 1);
}
}
}
@@ -4679,8 +4655,7 @@ remove_children_with_deleted_mergeinfo(m
child->abspath,
APR_HASH_KEY_STRING))
{
- remove_element_from_array(notify_b->children_with_mergeinfo,
- i--);
+ svn_sort__array_delete(notify_b->children_with_mergeinfo, i--, 1);
}
}
}
Modified: subversion/branches/1.7.x/subversion/libsvn_subr/mergeinfo.c
URL: http://svn.apache.org/viewvc/subversion/branches/1.7.x/subversion/libsvn_subr/mergeinfo.c?rev=1186352&r1=1186351&r2=1186352&view=diff
==============================================================================
--- subversion/branches/1.7.x/subversion/libsvn_subr/mergeinfo.c (original)
+++ subversion/branches/1.7.x/subversion/libsvn_subr/mergeinfo.c Wed Oct 19 17:19:15 2011
@@ -732,73 +732,403 @@ svn_mergeinfo_parse(svn_mergeinfo_t *mer
return err;
}
+/* Cleanup after svn_rangelist_merge when it modifies the ending range of
+ a single rangelist element in-place.
+
+ If *INDEX is not a valid element in RANGELIST do nothing. Otherwise ensure
+ that RANGELIST[*INDEX]->END does not adjoin or overlap any subsequent
+ ranges in RANGELIST.
+
+ If overlap is found, then remove, modify, and/or add elements to RANGELIST
+ as per the invariants for rangelists documented in svn_mergeinfo.h. If
+ RANGELIST[*INDEX]->END adjoins a subsequent element then combine the
+ elements if their inheritability permits -- The inheritance of intersecting
+ and adjoining ranges is handled as per svn_mergeinfo_merge2. Upon return
+ set *INDEX to the index of the youngest element modified, added, or
+ adjoined to RANGELIST[*INDEX].
+
+ Note: Adjoining rangelist elements are those where the end rev of the older
+ element is equal to the start rev of the younger element.
+
+ Any new elements inserted into RANGELIST are allocated in RESULT_POOL.*/
+static void
+adjust_remaining_ranges(apr_array_header_t *rangelist,
+ int *index,
+ apr_pool_t *result_pool)
+{
+ int i;
+ int starting_index;
+ int elements_to_delete = 0;
+ svn_merge_range_t *modified_range;
+
+ if (*index >= rangelist->nelts)
+ return;
+
+ starting_index = *index + 1;
+ modified_range = APR_ARRAY_IDX(rangelist, *index, svn_merge_range_t *);
+
+ for (i = *index + 1; i < rangelist->nelts; i++)
+ {
+ svn_merge_range_t *next_range = APR_ARRAY_IDX(rangelist, i,
+ svn_merge_range_t *);
+
+ /* If MODIFIED_RANGE doesn't adjoin or overlap the next range in
+ RANGELIST then we are finished. */
+ if (modified_range->end < next_range->start)
+ break;
+
+ /* Does MODIFIED_RANGE adjoin NEXT_RANGE? */
+ if (modified_range->end == next_range->start)
+ {
+ if (modified_range->inheritable == next_range->inheritable)
+ {
+ /* Combine adjoining ranges with the same inheritability. */
+ modified_range->end = next_range->end;
+ elements_to_delete++;
+ }
+ else
+ {
+ /* Cannot join because inheritance differs. */
+ (*index)++;
+ }
+ break;
+ }
+
+ /* Alright, we know MODIFIED_RANGE overlaps NEXT_RANGE, but how? */
+ if (modified_range->end > next_range->end)
+ {
+ /* NEXT_RANGE is a proper subset of MODIFIED_RANGE and the two
+ don't share the same end range. */
+ if (modified_range->inheritable
+ || (modified_range->inheritable == next_range->inheritable))
+ {
+ /* MODIFIED_RANGE absorbs NEXT_RANGE. */
+ elements_to_delete++;
+ }
+ else
+ {
+ /* NEXT_RANGE is a proper subset MODIFIED_RANGE but
+ MODIFIED_RANGE is non-inheritable and NEXT_RANGE is
+ inheritable. This means MODIFIED_RANGE is truncated,
+ NEXT_RANGE remains, and the portion of MODIFIED_RANGE
+ younger than NEXT_RANGE is added as a separate range:
+ ______________________________________________
+ | |
+ M MODIFIED_RANGE N
+ | (!inhertiable) |
+ |______________________________________________|
+ | |
+ O NEXT_RANGE P
+ | (inheritable)|
+ |______________|
+ |
+ V
+ _______________________________________________
+ | | | |
+ M MODIFIED_RANGE O NEXT_RANGE P NEW_RANGE N
+ | (!inhertiable) | (inheritable)| (!inheritable)|
+ |________________|______________|_______________|
+ */
+ svn_merge_range_t *new_modified_range =
+ apr_palloc(result_pool, sizeof(*new_modified_range));
+ new_modified_range->start = next_range->end;
+ new_modified_range->end = modified_range->end;
+ new_modified_range->inheritable = FALSE;
+ modified_range->end = next_range->start;
+ (*index)+=2;
+ svn_sort__array_insert(&new_modified_range, rangelist, *index);
+ /* Recurse with the new range. */
+ adjust_remaining_ranges(rangelist, index, result_pool);
+ break;
+ }
+ }
+ else if (modified_range->end == next_range->end)
+ {
+ /* NEXT_RANGE is a proper subset MODIFIED_RANGE and share
+ the same end range. */
+ if (modified_range->inheritable
+ || (modified_range->inheritable == next_range->inheritable))
+ {
+ /* MODIFIED_RANGE absorbs NEXT_RANGE. */
+ elements_to_delete++;
+ }
+ else
+ {
+ /* The intersection between MODIFIED_RANGE and NEXT_RANGE is
+ absorbed by the latter. */
+ modified_range->end = next_range->start;
+ (*index)++;
+ }
+ break;
+ }
+ else
+ {
+ /* NEXT_RANGE and MODIFIED_RANGE intersect but NEXT_RANGE is not
+ a proper subset of MODIFIED_RANGE, nor do the two share the
+ same end revision, i.e. they overlap. */
+ if (modified_range->inheritable == next_range->inheritable)
+ {
+ /* Combine overlapping ranges with the same inheritability. */
+ modified_range->end = next_range->end;
+ elements_to_delete++;
+ }
+ else if (modified_range->inheritable)
+ {
+ /* MODIFIED_RANGE absorbs the portion of NEXT_RANGE it overlaps
+ and NEXT_RANGE is truncated. */
+ next_range->start = modified_range->end;
+ (*index)++;
+ }
+ else
+ {
+ /* NEXT_RANGE absorbs the portion of MODIFIED_RANGE it overlaps
+ and MODIFIED_RANGE is truncated. */
+ modified_range->end = next_range->start;
+ (*index)++;
+ }
+ break;
+ }
+ }
+
+ if (elements_to_delete)
+ svn_sort__array_delete(rangelist, starting_index, elements_to_delete);
+}
svn_error_t *
svn_rangelist_merge(apr_array_header_t **rangelist,
const apr_array_header_t *changes,
apr_pool_t *pool)
{
- int i, j;
- apr_array_header_t *output = apr_array_make(pool, 1,
- sizeof(svn_merge_range_t *));
- i = 0;
- j = 0;
+ int i = 0;
+ int j = 0;
+ apr_pool_t *subpool = svn_pool_create(pool);
+
+ /* We may modify CHANGES, so make a copy in SUBPOOL. */
+ changes = svn_rangelist_dup(changes, subpool);
+
while (i < (*rangelist)->nelts && j < changes->nelts)
{
- svn_merge_range_t *elt1, *elt2;
- int res;
+ svn_merge_range_t *range =
+ APR_ARRAY_IDX(*rangelist, i, svn_merge_range_t *);
+ svn_merge_range_t *change =
+ APR_ARRAY_IDX(changes, j, svn_merge_range_t *);
+ int res = svn_sort_compare_ranges(&range, &change);
- elt1 = APR_ARRAY_IDX(*rangelist, i, svn_merge_range_t *);
- elt2 = APR_ARRAY_IDX(changes, j, svn_merge_range_t *);
-
- res = svn_sort_compare_ranges(&elt1, &elt2);
if (res == 0)
{
/* Only when merging two non-inheritable ranges is the result also
non-inheritable. In all other cases ensure an inheritiable
result. */
- if (elt1->inheritable || elt2->inheritable)
- elt1->inheritable = TRUE;
- SVN_ERR(combine_with_lastrange(elt1, output,
- TRUE, pool, pool));
+ if (range->inheritable || change->inheritable)
+ range->inheritable = TRUE;
i++;
j++;
}
- else if (res < 0)
+ else if (res < 0) /* CHANGE is younger than RANGE */
{
- SVN_ERR(combine_with_lastrange(elt1, output,
- TRUE, pool, pool));
- i++;
+ if (range->end < change->start)
+ {
+ /* RANGE is older than CHANGE and the two do not
+ adjoin or overlap */
+ i++;
+ }
+ else if (range->end == change->start)
+ {
+ /* RANGE and CHANGE adjoin */
+ if (range->inheritable == change->inheritable)
+ {
+ /* RANGE and CHANGE have the same inheritability so
+ RANGE expands to absord CHANGE. */
+ range->end = change->end;
+ adjust_remaining_ranges(*rangelist, &i, pool);
+ j++;
+ }
+ else
+ {
+ /* RANGE and CHANGE adjoin, but have different
+ inheritability. Since RANGE is older, just
+ move on to the next RANGE. */
+ i++;
+ }
+ }
+ else
+ {
+ /* RANGE and CHANGE overlap, but how? */
+ if ((range->inheritable == change->inheritable)
+ || range->inheritable)
+ {
+ /* If CHANGE is a proper subset of RANGE, it absorbs RANGE
+ with no adjustment otherwise only the intersection is
+ absorbed and CHANGE is truncated. */
+ if (range->end >= change->end)
+ j++;
+ else
+ change->start = range->end;
+ }
+ else
+ {
+ /* RANGE is non-inheritable and CHANGE is inheritable. */
+ if (range->start < change->start)
+ {
+ /* CHANGE absorbs intersection with RANGE and RANGE
+ is truncated. */
+ svn_merge_range_t *range_copy =
+ svn_merge_range_dup(range, pool);
+ range_copy->end = change->start;
+ range->start = change->start;
+ svn_sort__array_insert(&range_copy, *rangelist, i++);
+ }
+ else
+ {
+ /* CHANGE and RANGE share the same start rev, but
+ RANGE is considered older because its end rev
+ is older. */
+ range->inheritable = TRUE;
+ change->start = range->end;
+ }
+ }
+ }
}
- else
+ else /* res > 0, CHANGE is older than RANGE */
{
- SVN_ERR(combine_with_lastrange(elt2, output,
- TRUE, pool, pool));
- j++;
+ if (change->end < range->start)
+ {
+ /* CHANGE is older than RANGE and the two do not
+ adjoin or overlap, so insert a copy of CHANGE
+ into *RANGELIST. */
+ svn_merge_range_t *change_copy =
+ svn_merge_range_dup(change, pool);
+ svn_sort__array_insert(&change_copy, *rangelist, i++);
+ j++;
+ }
+ else if (change->end == range->start)
+ {
+ /* RANGE and CHANGE adjoin */
+ if (range->inheritable == change->inheritable)
+ {
+ /* RANGE and CHANGE have the same inheritability so we
+ can simply combine the two in place. */
+ range->start = change->start;
+ j++;
+ }
+ else
+ {
+ /* RANGE and CHANGE have different inheritability so insert
+ a copy of CHANGE into *RANGELIST. */
+ svn_merge_range_t *change_copy =
+ svn_merge_range_dup(change, pool);
+ svn_sort__array_insert(&change_copy, *rangelist, i);
+ j++;
+ }
+ }
+ else
+ {
+ /* RANGE and CHANGE overlap. */
+ if (range->inheritable == change->inheritable)
+ {
+ /* RANGE and CHANGE have the same inheritability so we
+ can simply combine the two in place... */
+ range->start = change->start;
+ if (range->end < change->end)
+ {
+ /* ...but if RANGE is expanded ensure that we don't
+ violate any rangelist invariants. */
+ range->end = change->end;
+ adjust_remaining_ranges(*rangelist, &i, pool);
+ }
+ j++;
+ }
+ else if (range->inheritable)
+ {
+ if (change->start < range->start)
+ {
+ /* RANGE is inheritable so absorbs any part of CHANGE
+ it overlaps. CHANGE is truncated and the remainder
+ inserted into *RANGELIST. */
+ svn_merge_range_t *change_copy =
+ svn_merge_range_dup(change, pool);
+ change_copy->end = range->start;
+ change->start = range->start;
+ svn_sort__array_insert(&change_copy, *rangelist, i++);
+ }
+ else
+ {
+ /* CHANGE and RANGE share the same start rev, but
+ CHANGE is considered older because CHANGE->END is
+ older than RANGE->END. */
+ j++;
+ }
+ }
+ else
+ {
+ /* RANGE is non-inheritable and CHANGE is inheritable. */
+ if (change->start < range->start)
+ {
+ if (change->end == range->end)
+ {
+ /* RANGE is a proper subset of CHANGE and share the
+ same end revision, so set RANGE equal to CHANGE. */
+ range->start = change->start;
+ range->inheritable = TRUE;
+ j++;
+ }
+ else if (change->end > range->end)
+ {
+ /* RANGE is a proper subset of CHANGE and CHANGE has
+ a younger end revision, so set RANGE equal to its
+ intersection with CHANGE and truncate CHANGE. */
+ range->start = change->start;
+ range->inheritable = TRUE;
+ change->start = range->end;
+ }
+ else
+ {
+ /* CHANGE and RANGE overlap. Set RANGE equal to its
+ intersection with CHANGE and take the remainder
+ of RANGE and insert it into *RANGELIST. */
+ svn_merge_range_t *range_copy =
+ svn_merge_range_dup(range, pool);
+ range_copy->start = change->end;
+ range->start = change->start;
+ range->end = change->end;
+ range->inheritable = TRUE;
+ svn_sort__array_insert(&range_copy, *rangelist, ++i);
+ j++;
+ }
+ }
+ else
+ {
+ /* CHANGE and RANGE share the same start rev, but
+ CHANGE is considered older because its end rev
+ is older.
+
+ Insert the intersection of RANGE and CHANGE into
+ *RANGELIST and then set RANGE to the non-intersecting
+ portion of RANGE. */
+ svn_merge_range_t *range_copy =
+ svn_merge_range_dup(range, pool);
+ range_copy->end = change->end;
+ range_copy->inheritable = TRUE;
+ range->start = change->end;
+ svn_sort__array_insert(&range_copy, *rangelist, i++);
+ j++;
+ }
+ }
+ }
}
}
- /* Copy back any remaining elements.
- Only one of these loops should end up running, if anything. */
-
- SVN_ERR_ASSERT(!(i < (*rangelist)->nelts && j < changes->nelts));
-
- for (; i < (*rangelist)->nelts; i++)
- {
- svn_merge_range_t *elt = APR_ARRAY_IDX(*rangelist, i,
- svn_merge_range_t *);
- SVN_ERR(combine_with_lastrange(elt, output,
- TRUE, pool, pool));
- }
-
- for (; j < changes->nelts; j++)
+ /* Copy any remaining elements in CHANGES into *RANGELIST. */
+ for (; j < (changes)->nelts; j++)
{
- svn_merge_range_t *elt = APR_ARRAY_IDX(changes, j, svn_merge_range_t *);
- SVN_ERR(combine_with_lastrange(elt, output,
- TRUE, pool, pool));
+ svn_merge_range_t *change =
+ APR_ARRAY_IDX(changes, j, svn_merge_range_t *);
+ svn_merge_range_t *change_copy = svn_merge_range_dup(change,
+ pool);
+ svn_sort__array_insert(&change_copy, *rangelist, (*rangelist)->nelts);
}
- *rangelist = output;
+ svn_pool_destroy(subpool);
return SVN_NO_ERROR;
}
Modified: subversion/branches/1.7.x/subversion/libsvn_subr/sorts.c
URL: http://svn.apache.org/viewvc/subversion/branches/1.7.x/subversion/libsvn_subr/sorts.c?rev=1186352&r1=1186351&r2=1186352&view=diff
==============================================================================
--- subversion/branches/1.7.x/subversion/libsvn_subr/sorts.c (original)
+++ subversion/branches/1.7.x/subversion/libsvn_subr/sorts.c Wed Oct 19 17:19:15 2011
@@ -245,3 +245,35 @@ svn_sort__array_insert(const void *new_e
/* Copy in the new element */
memcpy(new_position, new_element, array->elt_size);
}
+
+void
+svn_sort__array_delete(apr_array_header_t *arr,
+ int delete_index,
+ int elements_to_delete)
+{
+ /* Do we have a valid index and are there enough elements? */
+ if (delete_index >= 0
+ && delete_index < arr->nelts
+ && elements_to_delete > 0
+ && (elements_to_delete + delete_index) <= arr->nelts)
+ {
+ if (delete_index == (arr->nelts - 1))
+ {
+ /* Deleting the last or only element in an array is easy. */
+ apr_array_pop(arr);
+ }
+ else if ((delete_index + elements_to_delete) == arr->nelts)
+ {
+ /* Delete the last ELEMENTS_TO_DELETE elements. */
+ arr->nelts -= elements_to_delete;
+ }
+ else
+ {
+ memmove(
+ arr->elts + arr->elt_size * delete_index,
+ arr->elts + (arr->elt_size * (delete_index + elements_to_delete)),
+ arr->elt_size * (arr->nelts - elements_to_delete - delete_index));
+ arr->nelts -= elements_to_delete;
+ }
+ }
+}
Modified: subversion/branches/1.7.x/subversion/tests/libsvn_subr/mergeinfo-test.c
URL: http://svn.apache.org/viewvc/subversion/branches/1.7.x/subversion/tests/libsvn_subr/mergeinfo-test.c?rev=1186352&r1=1186351&r2=1186352&view=diff
==============================================================================
--- subversion/branches/1.7.x/subversion/tests/libsvn_subr/mergeinfo-test.c (original)
+++ subversion/branches/1.7.x/subversion/tests/libsvn_subr/mergeinfo-test.c Wed Oct 19 17:19:15 2011
@@ -1181,7 +1181,7 @@ test_rangelist_merge(apr_pool_t *pool)
svn_merge_range_t expected_merge[6];
};
- #define SIZE_OF_RANGE_MERGE_TEST_ARRAY 59
+ #define SIZE_OF_RANGE_MERGE_TEST_ARRAY 68
/* The actual test data. */
struct rangelist_merge_test_data test_data[SIZE_OF_RANGE_MERGE_TEST_ARRAY] =
{
@@ -1266,6 +1266,29 @@ test_rangelist_merge(apr_pool_t *pool)
{"/A: 2-17", "/A: 1-5*,7*,12-13*", 2,
{{0, 1, FALSE}, {1, 17, TRUE}}},
+ {"/A: 3-4*,10-15,20", "/A: 5-60*", 5,
+ {{2, 9, FALSE}, {9, 15, TRUE}, {15, 19, FALSE},{19, 20, TRUE},
+ {20, 60, FALSE}}},
+
+ {"/A: 5-60*", "/A: 3-4*,10-15,20", 5,
+ {{2, 9, FALSE}, {9, 15, TRUE}, {15, 19, FALSE},{19, 20, TRUE},
+ {20, 60, FALSE}}},
+
+ {"/A: 3-4*,50-100*", "/A: 5-60*", 1, {{2, 100, FALSE}}},
+
+ {"/A: 5-60*", "/A: 3-4*,50-100*", 1, {{2, 100, FALSE}}},
+
+ {"/A: 3-4*,50-100", "/A: 5-60*", 2, {{2, 49, FALSE}, {49, 100, TRUE}}},
+
+ {"/A: 5-60*", "/A: 3-4*,50-100", 2, {{2, 49, FALSE}, {49, 100, TRUE}}},
+
+ {"/A: 3-4,50-100*", "/A: 5-60", 2, {{2, 60, TRUE}, {60, 100, FALSE}}},
+
+ {"/A: 5-60", "/A: 3-4,50-100*", 2, {{2, 60, TRUE}, {60, 100, FALSE}}},
+
+ {"/A: 5,9,11-15,17,200-300,999", "/A: 7-50", 4,
+ {{4, 5, TRUE}, {6, 50, TRUE}, {199, 300, TRUE}, {998, 999, TRUE}}},
+
/* A rangelist merged with an empty rangelist should equal the
non-empty rangelist but in compacted form. */
{"/A: 1-44,45,46,47-50", "", 1, {{ 0, 50, TRUE }}},