On Tue, 2008-09-23 at 20:47 +0100, Julian Foad wrote:
> Paul and others,
>
> I noticed that some of the code in libsvn_client/merge.c seems to be
> implementing "search in a sorted array" and "insert an element into an
> array" in its own way. I would like to see those bits of algorithm moved
> out to somewhere generic so they don't clutter the mergeinfo-specific
> code.
>
> Please review the attached patch. Here is the clean version of the log
> message[*]:
>
> [[[
> Factor out some generic array manipulation logic from the code that handles
> CHILDREN_WITH_MERGEINFO arrays.
>
> Create functions for searching and inserting in a generic sorted APR array.
> Replace the search function find_child_or_parent() and the insertion
> function insert_child_to_merge() with functions that do the same jobs using
> the generic helpers. Stop requiring the caller to remember the index where
> the next item should be inserted, as that is error-prone.
>
> * subversion/libsvn_client/merge.c
> (compare_merge_path_t_as_paths): Move this function to an earlier point in
> the source file. Add a doc string.
> (get_child_with_mergeinfo): New function.
> (find_child_or_parent, find_child_with_mergeinfo): Delete.
> (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.
>
> * subversion/include/svn_sorts.h
> (svn_sort__bsearch_lower_bound, svn_sort__array_insert): New functions.
>
> * subversion/libsvn_subr/sorts.c
> (bsearch_lower_bound): New function.
> (svn_sort__bsearch_lower_bound, svn_sort__array_insert): New functions.
> ]]]
I should have mentioned: the existing code uses a linear search with the
caller helping to avoid quadratic behaviour by passing an index for
where to resume searching, and a flag saying in which direction to
search. The patch replaces this with always using a binary search. I am
just assuming that a binary search will be fast enough to match or beat
the previous implementation in general. I haven't timed it.
- Julian
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe_at_subversion.tigris.org
For additional commands, e-mail: dev-help_at_subversion.tigris.org
Received on 2008-09-23 21:58:16 CEST