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

Re: svn commit: r11830 - trunk/subversion/libsvn_diff

From: <kfogel_at_collab.net>
Date: 2004-11-12 20:32:18 CET

striker@tigris.org writes:
> --- trunk/subversion/libsvn_diff/diff.h (original)
> +++ trunk/subversion/libsvn_diff/diff.h Wed Nov 10 19:26:57 2004
> @@ -67,6 +67,7 @@
> svn_diff__lcs_t *next;
> svn_diff__position_t *position[2];
> apr_off_t length;
> + int refcount;
> };

I suggest documenting the exact meaning of the refcount field. For
example, is an svn_diff__lcs_t born with a refcount of 0 or 1? Does
it count the number of nodes before it or after it, inclusive or
exclusive?
 
> --- trunk/subversion/libsvn_diff/lcs.c (original)
> +++ trunk/subversion/libsvn_diff/lcs.c Wed Nov 10 19:26:57 2004
> @@ -51,6 +51,7 @@
> svn_diff__snake(apr_off_t k,
> svn_diff__snake_t *fp,
> int idx,
> + svn_diff__lcs_t **freelist,
> apr_pool_t *pool)
> {
> svn_diff__position_t *start_position[2];
> @@ -58,6 +59,24 @@
> svn_diff__lcs_t *lcs;
> svn_diff__lcs_t *previous_lcs;
>
> + /* The previous entry at fp[k] is going to be replaced. See if we
> + * can mark that lcs node for reuse, because the sequence up to this
> + * point was a dead end.
> + */
> + lcs = fp[k].lcs;
> + while (lcs)
> + {
> + lcs->refcount--;
> + if (lcs->refcount)
> + break;
> +
> + previous_lcs = lcs->next;
> + lcs->next = *freelist;
> + lcs->next = *freelist;
> + *freelist = lcs;
> + lcs = previous_lcs;
> + }

Duplicate line, there?

   lcs->next = *freelist;
   lcs->next = *freelist;

(Not that it causes any problems, of course.)

> if (fp[k - 1].y + 1 > fp[k + 1].y)
> {
> start_position[0] = fp[k - 1].position[0];
> @@ -73,6 +92,7 @@
> previous_lcs = fp[k + 1].lcs;
> }
>
> +
> /* ### Optimization, skip all positions that don't have matchpoints
> * ### anyway. Beware of the sentinel, don't skip it!
> */
> @@ -85,16 +105,24 @@
> position[0] = position[0]->next;
> position[1] = position[1]->next;
> }
> -
> +
> if (position[1] != start_position[1])
> {
> - lcs = apr_palloc(pool, sizeof(*lcs));
> + lcs = *freelist;
> + if (lcs)
> + {
> + *freelist = lcs->next;
> + }
> + else
> + {
> + lcs = apr_palloc(pool, sizeof(*lcs));
> + }
>
> lcs->position[idx] = start_position[0];
> lcs->position[abs(1 - idx)] = start_position[1];
> lcs->length = position[1]->offset - start_position[1]->offset;
> -
> lcs->next = previous_lcs;
> + lcs->refcount = 1;

See, if that refcount field had been documented, I wouldn't have to
pause and think at this line :-).

> + /* strikerXXX: here we allocate the furthest point array, which is
> + * strikerXXX: sized M + N + 3 (!)
> + */
> fp = apr_pcalloc(pool,
> sizeof(*fp) * (apr_size_t)(length[0] + length[1] + 3));
> fp += length[idx] + 1;

And the problem with that is that it the array could be very large,
because we have to preallocate the whole thing, right? (Asking as a
sanity check.)

> @@ -196,12 +233,12 @@
> /* Forward */
> for (k = -p; k < d; k++)
> {
> - svn_diff__snake(k, fp, idx, pool);
> + svn_diff__snake(k, fp, idx, &lcs_freelist, pool);
> }
>
> for (k = d + p; k >= d; k--)
> {
> - svn_diff__snake(k, fp, idx, pool);
> + svn_diff__snake(k, fp, idx, &lcs_freelist, pool);
> }

Niiiiiice.

-K

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Fri Nov 12 22:28:21 2004

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