On Tue, Jan 11, 2011 at 4:56 PM, <s...@apache.org> wrote:
> Author: stsp
> Date: Tue Jan 11 22:56:34 2011
> New Revision: 1057908
>
> URL: http://svn.apache.org/viewvc?rev=1057908&view=rev
> Log:
> Significantly reduce the time spent by "svn patch" to figure out whether
> there are empty directories to be deleted after patching.
>
> * subversion/libsvn_client/patch.c
> (check_dir_empty): Rename deleted_abspath_list to deleted_abspath_hash.
> The type changed from an array to a hash table so adjust code accordingly.
> (push_if_unique): Remove.
> (delete_empty_dirs): Track empty directories in a hash table rather
> than an array. Also add a table for known non-empty directories.
> Check both tables before calling check_dir_empty() on a directory.
> Before this change, the code would potentially call check_dir_empty()
> many times for the same directory. This caused a very notable delay
> for large trees (test case was a Linux kernel tree being patched from
> version 2.4.37.11 to version 2.6.37 -- svn patch used to take several
> minutes looking for empty directories, and now takes less than a minute).
>
> Modified:
> subversion/trunk/subversion/libsvn_client/patch.c
>
> Modified: subversion/trunk/subversion/libsvn_client/patch.c
> URL:
> http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_client/patch.c?rev=1057908&r1=1057907&r2=1057908&view=diff
> ==============================================================================
> --- subversion/trunk/subversion/libsvn_client/patch.c (original)
> +++ subversion/trunk/subversion/libsvn_client/patch.c Tue Jan 11 22:56:34 2011
> @@ -2372,14 +2372,14 @@ find_existing_children(void *baton,
>
> /* Indicate in *EMPTY whether the directory at LOCAL_ABSPATH has any
> * versioned or unversioned children. Consider any DELETED_TARGETS,
> - * as well as paths listed in DELETED_ABSPATHS_LIST (which may be NULL)
> - * as already deleted. Use WC_CTX as the working copy context.
> + * as well as paths occuring as keys of DELETED_ABSPATHS_HASH (which may
> + * be NULL) as already deleted. Use WC_CTX as the working copy context.
> * Do temporary allocations in SCRATCH_POOL. */
> static svn_error_t *
> check_dir_empty(svn_boolean_t *empty, const char *local_abspath,
> svn_wc_context_t *wc_ctx,
> apr_array_header_t *deleted_targets,
> - apr_array_header_t *deleted_abspath_list,
> + apr_hash_t *deleted_abspath_hash,
> apr_pool_t *scratch_pool)
> {
> struct status_baton btn;
> @@ -2427,13 +2427,17 @@ check_dir_empty(svn_boolean_t *empty, co
> break;
> }
> }
> - if (! deleted && deleted_abspath_list)
> + if (! deleted && deleted_abspath_hash)
> {
> - for (j = 0; j < deleted_abspath_list->nelts; j++)
> + apr_hash_index_t *hi;
> +
> + for (hi = apr_hash_first(scratch_pool, deleted_abspath_hash);
> + hi;
> + hi = apr_hash_next(hi))
> {
> const char *abspath;
>
> - abspath = APR_ARRAY_IDX(deleted_abspath_list, j, const char *);
> + abspath = svn__apr_hash_index_key(hi);
> if (! svn_path_compare_paths(found, abspath))
> {
> deleted = TRUE;
> @@ -2451,33 +2455,6 @@ check_dir_empty(svn_boolean_t *empty, co
> return SVN_NO_ERROR;
> }
>
> -/* Push a copy of EMPTY_DIR, allocated in RESULT_POOL, onto the EMPTY_DIRS
> - * array if no directory matching EMPTY_DIR is already in the array. */
> -static void
> -push_if_unique(apr_array_header_t *empty_dirs, const char *empty_dir,
> - apr_pool_t *result_pool)
> -{
> - svn_boolean_t is_unique;
> - int i;
> -
> - is_unique = TRUE;
> - for (i = 0; i < empty_dirs->nelts; i++)
> - {
> - const char *empty_dir2;
> -
> - empty_dir2 = APR_ARRAY_IDX(empty_dirs, i, const char *);
> - if (strcmp(empty_dir, empty_dir2) == 0)
> - {
> - is_unique = FALSE;
> - break;
> - }
> - }
> -
> - if (is_unique)
> - APR_ARRAY_PUSH(empty_dirs, const char *) = apr_pstrdup(result_pool,
> - empty_dir);
> -}
> -
> /* Delete all directories from the working copy which are left empty
> * by deleted TARGETS. Use client context CTX.
> * If DRY_RUN is TRUE, do not modify the working copy.
> @@ -2486,11 +2463,13 @@ static svn_error_t *
> delete_empty_dirs(apr_array_header_t *targets_info, svn_client_ctx_t *ctx,
> svn_boolean_t dry_run, apr_pool_t *scratch_pool)
> {
> - apr_array_header_t *empty_dirs;
> + apr_hash_t *empty_dirs;
> + apr_hash_t *non_empty_dirs;
> apr_array_header_t *deleted_targets;
> apr_pool_t *iterpool;
> svn_boolean_t again;
> int i;
> + apr_hash_index_t *hi;
>
> /* Get a list of all deleted targets. */
> deleted_targets = apr_array_make(scratch_pool, 0, sizeof(patch_target_t *));
> @@ -2508,7 +2487,8 @@ delete_empty_dirs(apr_array_header_t *ta
> return SVN_NO_ERROR;
>
> /* Look for empty parent directories of deleted targets. */
> - empty_dirs = apr_array_make(scratch_pool, 0, sizeof(const char *));
> + empty_dirs = apr_hash_make(scratch_pool);
> + non_empty_dirs = apr_hash_make(scratch_pool);
> iterpool = svn_pool_create(scratch_pool);
> for (i = 0; i < targets_info->nelts; i++)
> {
> @@ -2523,17 +2503,24 @@ delete_empty_dirs(apr_array_header_t *ta
>
> target_info = APR_ARRAY_IDX(targets_info, i, patch_target_info_t *);
> parent = svn_dirent_dirname(target_info->local_abspath, iterpool);
> +
> + if (apr_hash_get(non_empty_dirs, parent, APR_HASH_KEY_STRING))
> + continue;
> + else if (apr_hash_get(empty_dirs, parent, APR_HASH_KEY_STRING))
> + continue;
> +
> SVN_ERR(check_dir_empty(&parent_empty, parent, ctx->wc_ctx,
> deleted_targets, NULL, iterpool));
> if (parent_empty)
> - {
> - APR_ARRAY_PUSH(empty_dirs, const char *) =
> - apr_pstrdup(scratch_pool, parent);
> - }
> + apr_hash_set(empty_dirs, apr_pstrdup(scratch_pool, parent),
> + APR_HASH_KEY_STRING, "");
> + else
> + apr_hash_set(non_empty_dirs, apr_pstrdup(scratch_pool, parent),
> + APR_HASH_KEY_STRING, "");
> }
>
> /* We have nothing to do if there aren't any empty directories. */
> - if (empty_dirs->nelts == 0)
> + if (apr_hash_count(empty_dirs) == 0)
> {
> svn_pool_destroy(iterpool);
> return SVN_NO_ERROR;
> @@ -2542,7 +2529,7 @@ delete_empty_dirs(apr_array_header_t *ta
> /* Determine the minimal set of empty directories we need to delete. */
> do
> {
> - apr_array_header_t *empty_dirs_copy;
> + apr_hash_t *empty_dirs_copy;
>
> svn_pool_clear(iterpool);
>
> @@ -2552,32 +2539,43 @@ delete_empty_dirs(apr_array_header_t *ta
> /* Rebuild the empty dirs list, replacing empty dirs which have
> * an empty parent with their parent. */
> again = FALSE;
> - empty_dirs_copy = apr_array_copy(iterpool, empty_dirs);
> - apr_array_clear(empty_dirs);
> - for (i = 0; i < empty_dirs_copy->nelts; i++)
> + empty_dirs_copy = apr_hash_copy(iterpool, empty_dirs);
> + apr_hash_clear(empty_dirs);
Should use svn_hash__clear() here, since apr_hash_clear() isn't
defined in APR 0.9.
-Hyrum
> +
> + for (hi = apr_hash_first(iterpool, empty_dirs_copy);
> + hi;
> + hi = apr_hash_next(hi))
> {
> svn_boolean_t parent_empty;
> const char *empty_dir;
> const char *parent;
>
> - empty_dir = APR_ARRAY_IDX(empty_dirs_copy, i, const char *);
> + empty_dir = svn__apr_hash_index_key(hi);
> parent = svn_dirent_dirname(empty_dir, iterpool);
> +
> + if (apr_hash_get(empty_dirs, parent, APR_HASH_KEY_STRING))
> + continue;
> +
> SVN_ERR(check_dir_empty(&parent_empty, parent, ctx->wc_ctx,
> deleted_targets, empty_dirs_copy,
> iterpool));
> if (parent_empty)
> {
> again = TRUE;
> - push_if_unique(empty_dirs, parent, scratch_pool);
> + apr_hash_set(empty_dirs, apr_pstrdup(scratch_pool, parent),
> + APR_HASH_KEY_STRING, "");
> }
> else
> - push_if_unique(empty_dirs, empty_dir, scratch_pool);
> + apr_hash_set(empty_dirs, apr_pstrdup(scratch_pool, empty_dir),
> + APR_HASH_KEY_STRING, "");
> }
> }
> while (again);
>
> /* Finally, delete empty directories. */
> - for (i = 0; i < empty_dirs->nelts; i++)
> + for (hi = apr_hash_first(scratch_pool, empty_dirs);
> + hi;
> + hi = apr_hash_next(hi))
> {
> const char *empty_dir;
>
> @@ -2586,7 +2584,7 @@ delete_empty_dirs(apr_array_header_t *ta
> if (ctx->cancel_func)
> SVN_ERR(ctx->cancel_func(ctx->cancel_baton));
>
> - empty_dir = APR_ARRAY_IDX(empty_dirs, i, const char *);
> + empty_dir = svn__apr_hash_index_key(hi);
> if (ctx->notify_func2)
> {
> svn_wc_notify_t *notify;
>
>
>
