Re: [PATCH 03/10] sha1-array: provide oid_array_remove_if

From: Junio C Hamano <gitster@pobox.com>
Date: Aug 9, 2018, 21:44 UTC
Message-ID: <xmqqsh3n9pvv.fsf@gitster-ct.c.googlers.com>
In-Reply-To: <20180808221752.195419-4-sbeller@google.com>

Stefan Beller <sbeller@google.com> writes:

Show 29 quoted lines

> Signed-off-by: Stefan Beller <sbeller@google.com>
> ---
>  sha1-array.c | 39 +++++++++++++++++++++++++++++++++++++++
>  sha1-array.h |  3 +++
>  2 files changed, 42 insertions(+)
>
> diff --git a/sha1-array.c b/sha1-array.c
> index 265941fbf40..10eb08b425e 100644
> --- a/sha1-array.c
> +++ b/sha1-array.c
> @@ -77,3 +77,42 @@ int oid_array_for_each_unique(struct oid_array *array,
>  	}
>  	return 0;
>  }
> +
> +int oid_array_remove_if(struct oid_array *array,
> +			for_each_oid_fn fn,
> +			void *data)
> +{
> +	int i, j;
> +	char *to_remove = xcalloc(array->nr, sizeof(char));
> +
> +	/* No oid_array_sort() here! See the api-oid-array.txt docs! */
> +
> +	for (i = 0; i < array->nr; i++) {
> +		int ret = fn(array->oid + i, data);
> +		if (ret)
> +			to_remove[i] = 1;
> +	}

Doing the same without this secondary array and loop, i.e.

	for (src = dst = 0; src < array->nr; src++) {
		if (!fn(&array->oid[src], cbdata)) {
			if (dst < src)
				oidcpy(&array->oid[dst], &array->oid[src]);
			dst++;
		}
	}
        array->nr = dst;

would be no less efficient. The only reason why you might want to measure move-span by a secondary array and preliminary counting loop like your version does is that moving contiguous area of memory may be more efficient than moving only by a single oid sized chunks, but as far as I can tell you are not doing that "optimization", either.

I doubt that remove_if() is particularly a good name. A version of this function, for which polarity of fn() is reversed, can be called "grep", or "filter", I think, and would be more understandable.