### Not for committing as-is. This is some suggestions around the theme of searching CHILDREN_WITH_MERGEINFO arrays. Replace the search function find_child_or_parent() and the insertion function insert_child_to_merge(), with functions that do the same job in a more generic and hopefully more efficient way. * subversion/libsvn_client/merge.c (compare_merge_path_t_as_paths): Move this function to an earlier point in the source file. (get_child_with_mergeinfo): New function. (find_child_or_parent): Check some of the preconditions. (bsearch_lower_bound, child_with_mergeinfo_insert_index): New functions. (svn_client__merge_path_dup): New function. (insert_child_to_merge): Re-write. (insert_parent_and_sibs_of_sw_absent_del_entry, get_mergeinfo_paths, process_children_with_new_mergeinfo): Adjust for the above changes, eliminating the indexes. Index: subversion/libsvn_client/merge.c =================================================================== --- subversion/libsvn_client/merge.c (revision 32998) +++ subversion/libsvn_client/merge.c (working copy) @@ -22,6 +22,7 @@ /*** Includes ***/ +#include #include #include #include @@ -3673,6 +3674,35 @@ get_mergeinfo_error_handler(const char * } } +/* Helper for qsort() and bsearch() on an array of svn_client__merge_path_t + elements. */ +static int +compare_merge_path_t_as_paths(const void *a, + const void *b) +{ + svn_client__merge_path_t *child1 = *((svn_client__merge_path_t * const *) a); + svn_client__merge_path_t *child2 = *((svn_client__merge_path_t * const *) b); + + return svn_path_compare_paths(child1->path, child2->path); +} + +/* Return a pointer to the element of CHILDREN_WITH_MERGEINFO whose path + * is PATH, or return NULL if there is no such element. */ +static svn_client__merge_path_t * +get_child_with_mergeinfo(const apr_array_header_t *children_with_mergeinfo, + const char *path) +{ + svn_client__merge_path_t merge_path; + svn_client__merge_path_t *key; + + merge_path.path = path; + key = &merge_path; + return bsearch(&key, children_with_mergeinfo->elts, + children_with_mergeinfo->nelts, + children_with_mergeinfo->elt_size, + compare_merge_path_t_as_paths); +} + /* Helper for get_mergeinfo_paths() CHILDREN_WITH_MERGEINFO is a depth first sorted array filled with @@ -3694,6 +3724,24 @@ find_child_or_parent(apr_array_header_t int j = 0; *child_or_parent = NULL; + /* Assert that the PATH to look for is indeed a child/parent of the + * one at INDEX, as the caller claims it is. */ + { + svn_client__merge_path_t *element = + APR_ARRAY_IDX(children_with_mergeinfo, start_index, + svn_client__merge_path_t *); + int cmp = svn_path_compare_paths(path, element->path); + + if (start_index == children_with_mergeinfo->nelts - 1 + && !looking_for_child) + { + /* May be called from find_child_with_mergeinfo() + * which doesn't respect this requirement. */ + } + else + assert(looking_for_child ? (cmp > 0) : (cmp < 0)); + } + /* If possible, search forwards in the depth first sorted array to find a child PATH or backwards to find a parent PATH. */ if (start_index >= 0 && start_index < children_with_mergeinfo->nelts) @@ -3759,71 +3807,111 @@ find_child_with_mergeinfo(apr_array_head pool); } -/* Helper for get_mergeinfo_paths() +/* Return the address at which the element KEY should be inserted into the + the array of pointers ARRAY which has NELTS elements, or return NULL if + the element is already present. ARRAY must be sorted in the order + determined by the function COMPARE_FUNC which compares a pair of + elements, as defined for the standard functions qsort() and bsearch(). */ +static void * +bsearch_lower_bound(const void *key, + const void **array, + int nelts, + int (*compare_func)(const void *a, const void *b)) +{ + int lower = 0; + int upper = nelts - 1; + + /* Binary search for the position at which to insert KEY. */ + while (lower <= upper) + { + int try = (lower + upper) / 2; + int cmp = compare_func(&array[try], &key); + + if (cmp < 0) + lower = try + 1; + else if (cmp > 0) + upper = try - 1; + else + /* Found (at index TRY). */ + return NULL; + } - CHILDREN_WITH_MERGEINFO is a depth first sorted array filled with - svn_client__merge_path_t *. Insert INSERT_ELEMENT into the - CHILDREN_WITH_MERGEINFO array at index INSERT_INDEX. */ -static void -insert_child_to_merge(apr_array_header_t *children_with_mergeinfo, - svn_client__merge_path_t *insert_element, - int insert_index) + /* Not found. It would be inserted at index LOWER. */ + return &array[lower]; +} + +/* Return the address at which the element CHILD should be inserted into + CHILDREN_WITH_MERGEINFO, or NULL if the element is already present. */ +static svn_client__merge_path_t ** +child_with_mergeinfo_insert_index(apr_array_header_t *children_with_mergeinfo, + const svn_client__merge_path_t *child) { - if (insert_index == children_with_mergeinfo->nelts) - { - APR_ARRAY_PUSH(children_with_mergeinfo, - svn_client__merge_path_t *) = insert_element; - } - else - { - /* Copy the last element of CHILDREN_WITH_MERGEINFO and add it to the - end of the array. */ - int j; - svn_client__merge_path_t *curr = - APR_ARRAY_IDX(children_with_mergeinfo, - children_with_mergeinfo->nelts - 1, - svn_client__merge_path_t *); - svn_client__merge_path_t *curr_copy = - apr_palloc(children_with_mergeinfo->pool, sizeof(*curr_copy)); + return bsearch_lower_bound(child, + (const void **)children_with_mergeinfo->elts, + children_with_mergeinfo->nelts, + compare_merge_path_t_as_paths); +} - *curr_copy = *curr; - APR_ARRAY_PUSH(children_with_mergeinfo, - svn_client__merge_path_t *) = curr_copy; - - /* Move all elements from INSERT_INDEX to the end of the array forward - one spot then insert the new element. */ - for (j = children_with_mergeinfo->nelts - 2; j >= insert_index; j--) - { - svn_client__merge_path_t *prev; - curr = APR_ARRAY_IDX(children_with_mergeinfo, j, - svn_client__merge_path_t *); - if (j == insert_index) - *curr = *insert_element; - else - { - prev = APR_ARRAY_IDX(children_with_mergeinfo, j - 1, - svn_client__merge_path_t *); - *curr = *prev; - } - } - } +/* Return a deep copy of the merge-path structure OLD, allocated in POOL. */ +static svn_client__merge_path_t * +svn_client__merge_path_dup(const svn_client__merge_path_t *old, + apr_pool_t *pool) +{ + svn_client__merge_path_t *new = apr_palloc(pool, sizeof(*new)); + + new->path = apr_pstrdup(pool, old->path); + return new; } -/* Helper for get_mergeinfo_paths()'s qsort() call. */ -static int -compare_merge_path_t_as_paths(const void *a, - const void *b) +/* Insert a deep copy of INSERT_ELEMENT into the CHILDREN_WITH_MERGEINFO + array at its correct position. Allocate the new storage from the array's + pool. CHILDREN_WITH_MERGEINFO is a depth first sorted array of + (svn_client__merge_path_t *). */ +static void +insert_child_to_merge(apr_array_header_t *children_with_mergeinfo, + const svn_client__merge_path_t *insert_element) { - svn_client__merge_path_t *child1 = *((svn_client__merge_path_t * const *) a); - svn_client__merge_path_t *child2 = *((svn_client__merge_path_t * const *) b); + svn_client__merge_path_t **new_position; + int insert_index; - return svn_path_compare_paths(child1->path, child2->path); + /* Find where to insert the new element */ + { + svn_client__merge_path_t *dummy; + + /* ### Currently we try two different ways and check that they agree. + TODO: Get rid of one of these. */ + insert_index = find_child_with_mergeinfo(children_with_mergeinfo, &dummy, + insert_element->path, + children_with_mergeinfo->pool); + assert(dummy == NULL); + new_position = child_with_mergeinfo_insert_index(children_with_mergeinfo, + insert_element); + assert(new_position != NULL); + assert(&APR_ARRAY_IDX(children_with_mergeinfo, + insert_index, + svn_client__merge_path_t *) == new_position); + } + + /* Make a space for the new element */ + { + int elements_to_move = children_with_mergeinfo->nelts - insert_index; + + /* Allocate a new space at the end of the array */ + apr_array_push(children_with_mergeinfo); + + /* Move the elements after INSERT_INDEX along */ + memmove(new_position + 1, new_position, + children_with_mergeinfo->elt_size * elements_to_move); + } + + /* Copy and insert the new element */ + *new_position = svn_client__merge_path_dup(insert_element, + children_with_mergeinfo->pool); } /* Helper for get_mergeinfo_paths(). If CHILD->PATH is switched or absent then make sure its parent is marked as missing a child. - Start looking up for parent from *CURR_INDEX in - CHILDREN_WITH_MERGEINFO. Create the parent and insert it into + Create the parent and insert it into CHILDREN_WITH_MERGEINFO if necessary (and increment *CURR_INDEX so that caller don't process the inserted element). Also ensure that CHILD->PATH's siblings which are not already present in @@ -3843,15 +3931,13 @@ insert_parent_and_sibs_of_sw_absent_del_ apr_hash_t *entries; apr_hash_index_t *hi; svn_wc_adm_access_t *parent_access; - int insert_index, parent_index; if (!(child->absent || (child->switched && strcmp(merge_cmd_baton->target, child->path) != 0))) return SVN_NO_ERROR; - parent_index = find_child_or_parent(children_with_mergeinfo, &parent, - parent_path, FALSE, *curr_index, pool); + parent = get_child_with_mergeinfo(children_with_mergeinfo, parent_path); if (parent) { parent->missing_child = TRUE; @@ -3863,7 +3949,7 @@ insert_parent_and_sibs_of_sw_absent_del_ parent->path = apr_pstrdup(children_with_mergeinfo->pool, parent_path); parent->missing_child = TRUE; /* Insert PARENT into CHILDREN_WITH_MERGEINFO. */ - insert_child_to_merge(children_with_mergeinfo, parent, parent_index); + insert_child_to_merge(children_with_mergeinfo, parent); /* Increment for loop index so we don't process the inserted element. */ (*curr_index)++; } /*(parent == NULL) */ @@ -3886,9 +3972,8 @@ insert_parent_and_sibs_of_sw_absent_del_ /* Does this child already exist in CHILDREN_WITH_MERGEINFO? */ child_path = svn_path_join(parent->path, key, pool); - insert_index = find_child_or_parent(children_with_mergeinfo, - &sibling_of_missing, child_path, - TRUE, parent_index, pool); + sibling_of_missing = get_child_with_mergeinfo(children_with_mergeinfo, + child_path); /* Create the missing child and insert it into CHILDREN_WITH_MERGEINFO.*/ if (!sibling_of_missing) { @@ -3896,8 +3981,7 @@ insert_parent_and_sibs_of_sw_absent_del_ sizeof(*sibling_of_missing)); sibling_of_missing->path = apr_pstrdup(children_with_mergeinfo->pool, child_path); - insert_child_to_merge(children_with_mergeinfo, sibling_of_missing, - insert_index); + insert_child_to_merge(children_with_mergeinfo, sibling_of_missing); } } return SVN_NO_ERROR; @@ -4001,7 +4085,6 @@ get_mergeinfo_paths(apr_array_header_t * iterpool = svn_pool_create(pool); for (i = 0; i < children_with_mergeinfo->nelts; i++) { - int insert_index; svn_client__merge_path_t *child = APR_ARRAY_IDX(children_with_mergeinfo, i, svn_client__merge_path_t *); svn_pool_clear(iterpool); @@ -4061,10 +4144,8 @@ get_mergeinfo_paths(apr_array_header_t * not, create it and insert it into CHILDREN_WITH_MERGEINFO and set override mergeinfo on it. */ child_path = svn_path_join(child->path, key, iterpool); - insert_index = find_child_or_parent(children_with_mergeinfo, - &child_of_noninheritable, - child_path, TRUE, i, - iterpool); + child_of_noninheritable = + get_child_with_mergeinfo(children_with_mergeinfo, child_path); if (!child_of_noninheritable) { child_of_noninheritable = @@ -4073,8 +4154,7 @@ get_mergeinfo_paths(apr_array_header_t * child_of_noninheritable->path = apr_pstrdup(children_with_mergeinfo->pool, child_path); insert_child_to_merge(children_with_mergeinfo, - child_of_noninheritable, - insert_index); + child_of_noninheritable); if (!merge_cmd_baton->dry_run && merge_cmd_baton->same_repos) { @@ -5048,7 +5128,6 @@ process_children_with_new_mergeinfo(merg svn_mergeinfo_t path_explicit_mergeinfo; const svn_wc_entry_t *path_entry; svn_boolean_t indirect; - int index_for_new_child; svn_client__merge_path_t *new_child; apr_pool_clear(iterpool); @@ -5106,10 +5185,9 @@ process_children_with_new_mergeinfo(merg /* If the path is not in NOTIFY_B->CHILDREN_WITH_MERGEINFO then add it. */ - index_for_new_child = - find_child_with_mergeinfo(notify_b->children_with_mergeinfo, - &new_child, path_with_new_mergeinfo, - iterpool); + new_child = + get_child_with_mergeinfo(notify_b->children_with_mergeinfo, + path_with_new_mergeinfo); if (!new_child) { int parent_index = @@ -5142,7 +5220,7 @@ process_children_with_new_mergeinfo(merg parent->remaining_ranges, notify_b->children_with_mergeinfo->pool); insert_child_to_merge(notify_b->children_with_mergeinfo, - new_child, index_for_new_child); + new_child); } } /* Return MERGE_B->RA_SESSION2 to its initial state if we