Re: [PATCH 09/15] refs/packed-backend.c: implement skip lists to avoid excluded pattern(s)

From

Taylor Blau <me@ttaylorr.com>

Date

May 9, 2023, 21:15 UTC

Message-ID

<ZFq31XquMwJrPEOK@nand.local>

In-Reply-To

<ZFqzW2vqcFJqqPXH@nand.local>

On Tue, May 09, 2023 at 04:55:55PM -0400, Taylor Blau wrote:

> Good catch. I think applying this on top should do the trick:
>
> --- 8< ---
> diff --git a/refs/packed-backend.c b/refs/packed-backend.c
> index 137a4233f6..3b1337267a 100644
> --- a/refs/packed-backend.c
> +++ b/refs/packed-backend.c
> @@ -1054,9 +1054,9 @@ static void populate_excluded_skip_list(struct packed_ref_iterator *iter,
>  	 * we want to combine that into a single entry jumping from A to
>  	 * C.
>  	 */
> -	for (i = 1, j = 1; i < iter->skip_nr; i++) {
> +	for (i = 0, j = 0; i < iter->skip_nr; i++) {
>  		struct skip_list_entry *ours = &iter->skip[i];
> -		struct skip_list_entry *prev = &iter->skip[i - 1];
> +		struct skip_list_entry *prev = &iter->skip[j];
>
>  		if (ours->start == ours->end) {
>  			/* ignore empty regions (no matching entries) */
> @@ -1066,7 +1066,7 @@ static void populate_excluded_skip_list(struct packed_ref_iterator *iter,
>  			prev->end = ptr_max(prev->end, ours->end);
>  		} else {
>  			/* otherwise, insert a new region */
> -			iter->skip[j++] = *ours;
> +			iter->skip[++j] = *ours;
>  		}
>  	}
> --- >8 ---

Oops, this is wrong. It should be something like this instead:

--- 8< ---

diff --git a/refs/packed-backend.c b/refs/packed-backend.c
index 137a4233f6..574f32d67f 100644
--- a/refs/packed-backend.c
+++ b/refs/packed-backend.c
@@ -1007,6 +1007,7 @@ static void populate_excluded_skip_list(struct packed_ref_iterator *iter,
 {
 	size_t i, j;
 	const char **pattern;
+	struct skip_list_entry *last_disjoint;

 	if (!excluded_patterns)
 		return;
@@ -1054,19 +1055,22 @@ static void populate_excluded_skip_list(struct packed_ref_iterator *iter,
 	 * we want to combine that into a single entry jumping from A to
 	 * C.
 	 */
+	last_disjoint = iter->skip;
+
 	for (i = 1, j = 1; i < iter->skip_nr; i++) {
 		struct skip_list_entry *ours = &iter->skip[i];
-		struct skip_list_entry *prev = &iter->skip[i - 1];

 		if (ours->start == ours->end) {
 			/* ignore empty regions (no matching entries) */
 			continue;
-		} else if (prev->end >= ours->start) {
+		} else if (ours->start <= last_disjoint->end) {
 			/* overlapping regions extend the previous one */
-			prev->end = ptr_max(prev->end, ours->end);
+			last_disjoint->end = ptr_max(last_disjoint->end, ours->end);
 		} else {
 			/* otherwise, insert a new region */
 			iter->skip[j++] = *ours;
+			last_disjoint = ours;
+
 		}
 	}
--- >8 ---

Thanks,
Taylor