Author: stefan2
Date: Wed Aug 12 11:44:05 2015
New Revision: 1695484
URL: http://svn.apache.org/r1695484
Log:
On the svn-mergeinfo-normalizer branch:
Make searching for deletions as efficient as searching for copies, O(log n).
We will need that soon to identify surviving copies of deleted branches.
* tools/client-side/svn-mergeinfo-normalizer/log.c
(log_entry_t): Deletions are no longer stored locally at the revision.
(deletion_t): New struct, similar to copy_t.
(svn_min__log_t): Add global DELETIONS array similar to COPIES.
(deletion_order): New sorting criterion, similar to copy_order.
(log_entry_receiver): Store copies globally instead of locally now.
(svn_min__log): Update constructor code.
(svn_min__find_deletion,
svn_min__find_deletions): Replace the linear scan for deletions with an
O(log n) lookup.
* tools/client-side/svn-mergeinfo-normalizer/mergeinfo-normalizer.h
(svn_min__find_deletion,
svn_min__find_deletions): Update declarations to match the implementation.
* tools/client-side/svn-mergeinfo-normalizer/logic.c
(remove_overlapping_history,
show_obsoletes_summary): Update callers.
Modified:
subversion/branches/svn-mergeinfo-normalizer/tools/client-side/svn-mergeinfo-normalizer/log.c
subversion/branches/svn-mergeinfo-normalizer/tools/client-side/svn-mergeinfo-normalizer/logic.c
subversion/branches/svn-mergeinfo-normalizer/tools/client-side/svn-mergeinfo-normalizer/mergeinfo-normalizer.h
Modified:
subversion/branches/svn-mergeinfo-normalizer/tools/client-side/svn-mergeinfo-normalizer/log.c
URL:
http://svn.apache.org/viewvc/subversion/branches/svn-mergeinfo-normalizer/tools/client-side/svn-mergeinfo-normalizer/log.c?rev=1695484&r1=1695483&r2=1695484&view=diff
==============================================================================
---
subversion/branches/svn-mergeinfo-normalizer/tools/client-side/svn-mergeinfo-normalizer/log.c
(original)
+++
subversion/branches/svn-mergeinfo-normalizer/tools/client-side/svn-mergeinfo-normalizer/log.c
Wed Aug 12 11:44:05 2015
@@ -47,7 +47,6 @@ typedef struct log_entry_t
svn_revnum_t revision;
const char *common_base;
apr_array_header_t *paths;
- apr_array_header_t *deletions;
} log_entry_t;
typedef struct copy_t
@@ -59,6 +58,12 @@ typedef struct copy_t
svn_revnum_t copyfrom_revision;
} copy_t;
+typedef struct deletion_t
+{
+ const char *path;
+ svn_revnum_t revision;
+} deletion_t;
+
struct svn_min__log_t
{
apr_hash_t *unique_paths;
@@ -69,6 +74,7 @@ struct svn_min__log_t
apr_array_header_t *entries;
apr_array_header_t *copies;
+ apr_array_header_t *deletions;
svn_boolean_t quiet;
};
@@ -90,6 +96,23 @@ copy_order(const void *lhs,
return lhs_copy->revision == rhs_copy->revision ? 0 : 1;
}
+static int
+deletion_order(const void *lhs,
+ const void *rhs)
+{
+ const deletion_t *lhs_deletion = *(const deletion_t * const *)lhs;
+ const deletion_t *rhs_deletion = *(const deletion_t * const *)rhs;
+
+ int diff = strcmp(lhs_deletion->path, rhs_deletion->path);
+ if (diff)
+ return diff;
+
+ if (lhs_deletion->revision < rhs_deletion->revision)
+ return -1;
+
+ return lhs_deletion->revision == rhs_deletion->revision ? 0 : 1;
+}
+
static const char *
internalize(apr_hash_t *unique_paths,
const char *path,
@@ -126,7 +149,6 @@ log_entry_receiver(void *baton,
entry->paths = apr_array_make(result_pool,
apr_hash_count(log_entry->changed_paths),
sizeof(const char *));
- entry->deletions = NULL;
for (hi = apr_hash_first(scratch_pool, log_entry->changed_paths);
hi;
@@ -141,11 +163,11 @@ log_entry_receiver(void *baton,
if (change->action == 'D' || change->action == 'R')
{
- if (!entry->deletions)
- entry->deletions = apr_array_make(result_pool, 4,
- sizeof(const char *));
+ deletion_t *deletion = apr_pcalloc(log->pool, sizeof(*deletion));
+ deletion->path = path;
+ deletion->revision = log_entry->revision;
- APR_ARRAY_PUSH(entry->deletions, const char *) = path;
+ APR_ARRAY_PUSH(log->deletions, deletion_t *) = deletion;
}
if (SVN_IS_VALID_REVNUM(change->copyfrom_rev))
@@ -229,6 +251,7 @@ svn_min__log(svn_min__log_t **log,
result->head_rev = SVN_INVALID_REVNUM;
result->entries = apr_array_make(result_pool, 1024, sizeof(log_entry_t *));
result->copies = apr_array_make(result_pool, 1024, sizeof(copy_t *));
+ result->deletions = apr_array_make(result_pool, 1024, sizeof(deletion_t *));
result->quiet = baton->opt_state->quiet;
if (!baton->opt_state->quiet)
@@ -254,6 +277,7 @@ svn_min__log(svn_min__log_t **log,
svn_sort__array_reverse(result->entries, scratch_pool);
svn_sort__array(result->copies, copy_order);
+ svn_sort__array(result->deletions, deletion_order);
if (!baton->opt_state->quiet)
{
@@ -440,63 +464,92 @@ svn_min__operative_outside_subtree(svn_m
svn_revnum_t
svn_min__find_deletion(svn_min__log_t *log,
const char *path,
- svn_revnum_t end_rev)
-{
- int i, k;
- for (i = log->entries->nelts - 1; i >= 0; --i)
- {
- const log_entry_t *entry = APR_ARRAY_IDX(log->entries, i,
- const log_entry_t *);
- if (entry->revision < end_rev)
- break;
-
- if (!entry->deletions)
- continue;
-
- if (!is_relevant(entry->common_base, path, NULL))
- continue;
-
- for (k = 0; k < entry->deletions->nelts; ++k)
+ svn_revnum_t lower_rev,
+ svn_revnum_t upper_rev,
+ apr_pool_t *scratch_pool)
+{
+ svn_revnum_t latest = SVN_INVALID_REVNUM;
+
+ deletion_t *to_find = apr_pcalloc(scratch_pool, sizeof(*to_find));
+ to_find->path = path;
+ to_find->revision = lower_rev;
+
+ if (!SVN_IS_VALID_REVNUM(upper_rev))
+ upper_rev = log->head_rev;
+
+ if (!svn_fspath__is_root(to_find->path, strlen(to_find->path)))
+ {
+ int i;
+ for (i = svn_sort__bsearch_lower_bound(log->deletions, &to_find,
+ deletion_order);
+ i < log->deletions->nelts;
+ ++i)
{
- const char *deleted_path
- = APR_ARRAY_IDX(entry->paths, k, const char *);
+ const deletion_t *deletion = APR_ARRAY_IDX(log->deletions, i,
+ const deletion_t *);
+ if (strcmp(deletion->path, to_find->path))
+ break;
+ if (deletion->revision > upper_rev)
+ break;
- if (in_subtree(path, deleted_path, NULL))
- return entry->revision;
+ latest = deletion->revision;
+ to_find->revision = deletion->revision;
}
+
+ to_find->path = svn_fspath__dirname(to_find->path, scratch_pool);
}
- return SVN_INVALID_REVNUM;
+ return latest;
}
apr_array_header_t *
svn_min__find_deletions(svn_min__log_t *log,
const char *path,
- apr_pool_t *result_pool)
+ apr_pool_t *result_pool,
+ apr_pool_t *scratch_pool)
{
apr_array_header_t *result = apr_array_make(result_pool, 0,
sizeof(svn_revnum_t));
- int i, k;
- for (i = log->entries->nelts - 1; i >= 0; --i)
- {
- const log_entry_t *entry = APR_ARRAY_IDX(log->entries, i,
- const log_entry_t *);
- if (!entry->deletions)
- continue;
-
- if (!is_relevant(entry->common_base, path, NULL))
- continue;
+ int source, dest;
- for (k = 0; k < entry->deletions->nelts; ++k)
+ deletion_t *to_find = apr_pcalloc(scratch_pool, sizeof(*to_find));
+ to_find->path = path;
+ to_find->revision = 0;
+
+ if (!svn_fspath__is_root(to_find->path, strlen(to_find->path)))
+ {
+ int i;
+ for (i = svn_sort__bsearch_lower_bound(log->deletions, &to_find,
+ deletion_order);
+ i < log->deletions->nelts;
+ ++i)
{
- const char *deleted_path
- = APR_ARRAY_IDX(entry->paths, k, const char *);
+ const deletion_t *deletion = APR_ARRAY_IDX(log->deletions, i,
+ const deletion_t *);
+ if (strcmp(deletion->path, to_find->path))
+ break;
+
+ APR_ARRAY_PUSH(result, svn_revnum_t) = deletion->revision;
+ }
+
+ to_find->path = svn_fspath__dirname(to_find->path, scratch_pool);
+ }
- if (in_subtree(path, deleted_path, NULL))
- APR_ARRAY_PUSH(result, svn_revnum_t) = entry->revision;
+ svn_sort__array(result, svn_sort_compare_revisions);
+ for (source = 1, dest = 0; source < result->nelts; ++source)
+ {
+ svn_revnum_t source_rev = APR_ARRAY_IDX(result, source, svn_revnum_t);
+ svn_revnum_t dest_rev = APR_ARRAY_IDX(result, dest, svn_revnum_t);
+ if (source_rev != dest_rev)
+ {
+ ++dest_rev;
+ APR_ARRAY_IDX(result, dest, svn_revnum_t) = source_rev;
}
}
+ if (result->nelts)
+ result->nelts = dest + 1;
+
return result;
}
Modified:
subversion/branches/svn-mergeinfo-normalizer/tools/client-side/svn-mergeinfo-normalizer/logic.c
URL:
http://svn.apache.org/viewvc/subversion/branches/svn-mergeinfo-normalizer/tools/client-side/svn-mergeinfo-normalizer/logic.c?rev=1695484&r1=1695483&r2=1695484&view=diff
==============================================================================
---
subversion/branches/svn-mergeinfo-normalizer/tools/client-side/svn-mergeinfo-normalizer/logic.c
(original)
+++
subversion/branches/svn-mergeinfo-normalizer/tools/client-side/svn-mergeinfo-normalizer/logic.c
Wed Aug 12 11:44:05 2015
@@ -369,7 +369,8 @@ remove_overlapping_history(svn_rangelist
/* Collect the deletion revisions, i.e. the revisons separating different
branches with the same name. */
- deletions = svn_min__find_deletions(log, source_path, scratch_pool);
+ deletions = svn_min__find_deletions(log, source_path, scratch_pool,
+ scratch_pool);
next_deletion = SVN_INVALID_REVNUM;
/* Get the history of each of these branches up to the point where the
@@ -867,8 +868,7 @@ normalize(apr_array_header_t *wc_mergein
SVN_ERR(show_elision_header(parent_path, relpath, opt_state,
scratch_pool));
- /* Modify only a copy of the mergeinfo - until we know it can all
- be removed. */
+ /* Modify the mergeinfo here. */
subtree_mergeinfo_copy = svn_mergeinfo_dup(subtree_mergeinfo,
iterpool);
@@ -1007,7 +1007,9 @@ show_obsoletes_summary(svn_min__branch_l
const char *path = APR_ARRAY_IDX(paths, i, const char *);
svn_pool_clear(iterpool);
- deletion_rev = log ? svn_min__find_deletion(log, path, 0)
+ deletion_rev = log ? svn_min__find_deletion(log, path, 0,
+ SVN_INVALID_REVNUM,
+ iterpool)
: SVN_INVALID_REVNUM;
if (SVN_IS_VALID_REVNUM(deletion_rev))
Modified:
subversion/branches/svn-mergeinfo-normalizer/tools/client-side/svn-mergeinfo-normalizer/mergeinfo-normalizer.h
URL:
http://svn.apache.org/viewvc/subversion/branches/svn-mergeinfo-normalizer/tools/client-side/svn-mergeinfo-normalizer/mergeinfo-normalizer.h?rev=1695484&r1=1695483&r2=1695484&view=diff
==============================================================================
---
subversion/branches/svn-mergeinfo-normalizer/tools/client-side/svn-mergeinfo-normalizer/mergeinfo-normalizer.h
(original)
+++
subversion/branches/svn-mergeinfo-normalizer/tools/client-side/svn-mergeinfo-normalizer/mergeinfo-normalizer.h
Wed Aug 12 11:44:05 2015
@@ -188,14 +188,17 @@ svn_min__operative_outside_subtree(svn_m
apr_pool_t *result_pool);
svn_revnum_t
-svn_min__find_deletion(svn_min__log_t* log,
- const char* path,
- svn_revnum_t end_rev);
+svn_min__find_deletion(svn_min__log_t *log,
+ const char *path,
+ svn_revnum_t lower_rev,
+ svn_revnum_t upper_rev,
+ apr_pool_t *scratch_pool);
apr_array_header_t *
svn_min__find_deletions(svn_min__log_t *log,
const char *path,
- apr_pool_t *result_pool);
+ apr_pool_t *result_pool,
+ apr_pool_t *scratch_pool);
apr_array_header_t *
svn_min__get_history(svn_min__log_t *log,
