[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: svn commit: r1057908 - /subversion/trunk/subversion/libsvn_client/patch.c

From: Hyrum K Wright <hyrum_at_hyrumwright.org>
Date: Tue, 11 Jan 2011 17:04:45 -0600

On Tue, Jan 11, 2011 at 4:56 PM, <stsp_at_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;
>
>
>
Received on 2011-01-12 00:05:28 CET

This is an archived mail posted to the Subversion Dev mailing list.