Hi,
Small doc change to make it easy to understand the logic of how the
'match' is computed in vdelta generator, which has taken few hours of mine.
Once this clarity fixes find its place, will send the refactored vdelta
generator basically to modularise the code to make it easy to understand
rather than going across 3 loops spanning 105 lines.
With regards
Kamesh Jayachandran
[[[
Clarity fix.
Patch by: Kamesh Jayachandran <kamesh@collab.net>
* subversion/libsvn_delta/vdelta.c
(Vdelta Generator doc):
Mention of how much to 'check backwards' from the candidate.
(vdelta):
Removed redundant initialization of current_match_len.
Initializing 'current_match' to NULL and 'key' to 'here' while
declaring
rather than doing it before do-while loop.
Relocated the declaration of 'slot' to a do-while loop, as
'slot' is consumed solely inside this do-while loop.
Mention of 'check backwards' near match pointer computation.
The current_match_len can either be 0 or greater than
or equal to VD_KEY_SIZE. The 'no-match check' of
(current_match_len < VD_KEY_SIZE) can be simplified to
(!current_match_len) for clarity.
]]]
Kamesh Jayachandran wrote:
> Few more small corrections.
>
> make check ran successfully.
>
> With regards
> Kamesh Jayachandran
> [[[
> Clarity fix.
>
> Patch by: Kamesh Jayachandran <kamesh@collab.net>
>
> * subversion/libsvn_delta/vdelta.c
> (vdelta):
> Removed redundant initialization of current_match_len.
>
> Initializing 'current_match' to NULL and 'key' to 'here' while
> declaring
> rather than doing it before do-while loop.
>
> Relocated the declaration of 'slot' to a do-while loop, as
> 'slot' is consumed solely inside this do-while loop.
>
> The current_match_len can either be 0 or greater than
> or equal to VD_KEY_SIZE. The 'no-match check' of
> (current_match_len < VD_KEY_SIZE) can be simplified to
> (!current_match_len) for clarity.
>
> ]]]
>
> Kamesh Jayachandran wrote:
>> Hi All,
>> Trying to understand the vdelta implementation in subversion.
>> I have the following clarity suggestion to the code.
>> In the vdelta(): current_match_len can either be 0 or >= to VD_KEY_SIZE.
>> The 'no-match check' of (current_match_len < VD_KEY_SIZE) can be
>> simplified to
>> (!current_match_len) for clarity.
>>
>> Ran make check and it is successful.
>>
>> Find the attached patch.
>>
>> With regards
>> Kamesh Jayachandran
>>
>>
>> [[[
>> Clarity fix.
>>
>> Patch by: Kamesh Jayachandran <kamesh@collab.net>
>> * subversion/libsvn_delta/vdelta.c
>> (vdelta): The current_match_len can either be 0 or greater than
>> or equal to VD_KEY_SIZE.
>> The 'no-match check' of (current_match_len < VD_KEY_SIZE)
>> can be
>> simplified to (!current_match_len) for clarity.
>>
>> ]]]
>>
>> ------------------------------------------------------------------------
>>
>> Index: subversion/libsvn_delta/vdelta.c
>> ===================================================================
>> --- subversion/libsvn_delta/vdelta.c (revision 19309)
>> +++ subversion/libsvn_delta/vdelta.c (working copy)
>> @@ -255,7 +255,7 @@
>> }
>> while (progress && end - key >= VD_KEY_SIZE);
>>
>> - if (current_match_len < VD_KEY_SIZE)
>> + if (!current_match_len)
>> {
>> /* There is no match here; store a mapping and insert this
>> byte. */
>> store_mapping(table, here, here - data);
>>
>>
>> ------------------------------------------------------------------------
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
>> For additional commands, e-mail: dev-help@subversion.tigris.org
>
> ------------------------------------------------------------------------
>
> Index: subversion/libsvn_delta/vdelta.c
> ===================================================================
> --- subversion/libsvn_delta/vdelta.c (revision 19309)
> +++ subversion/libsvn_delta/vdelta.c (working copy)
> @@ -197,9 +197,9 @@
>
> for (;;)
> {
> - const char *current_match, *key;
> + const char *current_match = NULL;
> + const char *key = here;
> apr_size_t current_match_len = 0;
> - hash_slot_t *slot;
> svn_boolean_t progress;
>
> /* If we're near the end, just insert the last few bytes. */
> @@ -214,9 +214,6 @@
> }
>
> /* Search for the longest match. */
> - current_match = NULL;
> - current_match_len = 0;
> - key = here;
> do
> {
> /* Try to extend the current match. Our key is the last
> @@ -224,6 +221,7 @@
> have a current match, or just the four bytes where we are
> if we don't have a current match yet. See which mapping
> yields the longest extension. */
> + hash_slot_t *slot;
> progress = FALSE;
> for (slot = table->buckets[get_bucket(table, key)];
> slot != NULL;
> @@ -255,7 +253,7 @@
> }
> while (progress && end - key >= VD_KEY_SIZE);
>
> - if (current_match_len < VD_KEY_SIZE)
> + if (!current_match_len)
> {
> /* There is no match here; store a mapping and insert this byte. */
> store_mapping(table, here, here - data);
>
Index: subversion/libsvn_delta/vdelta.c
===================================================================
--- subversion/libsvn_delta/vdelta.c (revision 19309)
+++ subversion/libsvn_delta/vdelta.c (working copy)
@@ -142,6 +142,9 @@
4. For each candidate, check backwards to see if it matches
the entire match so far. If no candidates satisfy that
constraint, the current match is the best match; go to step 6.
+ By 'check backwards' we mean, to check candidate backwards by
+ (number of bytes 'current lookup key' is advanced from current
+ position) with current position also known as entire match.
5. Among the candidates which do satisfy the constraint,
determine which one yields the longest extension. This
@@ -197,9 +200,9 @@
for (;;)
{
- const char *current_match, *key;
+ const char *current_match = NULL;
+ const char *key = here;
apr_size_t current_match_len = 0;
- hash_slot_t *slot;
svn_boolean_t progress;
/* If we're near the end, just insert the last few bytes. */
@@ -214,9 +217,6 @@
}
/* Search for the longest match. */
- current_match = NULL;
- current_match_len = 0;
- key = here;
do
{
/* Try to extend the current match. Our key is the last
@@ -224,6 +224,7 @@
have a current match, or just the four bytes where we are
if we don't have a current match yet. See which mapping
yields the longest extension. */
+ hash_slot_t *slot;
progress = FALSE;
for (slot = table->buckets[get_bucket(table, key)];
slot != NULL;
@@ -234,6 +235,8 @@
if (slot - table->slots < key - here) /* Too close to start */
continue;
+
+ /* checking backwards by 'key-here' as mentioned in step4 */
match = data + (slot - table->slots) - (key - here);
match_len = find_match_len(match, here, end);
@@ -255,7 +258,7 @@
}
while (progress && end - key >= VD_KEY_SIZE);
- if (current_match_len < VD_KEY_SIZE)
+ if (!current_match_len)
{
/* There is no match here; store a mapping and insert this byte. */
store_mapping(table, here, here - data);
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Fri Apr 14 21:23:10 2006