Julian Phillips <julian@xxxxxxxxxxxxxxxxx> writes:
> Currently we linearly search through lists of refs when we need to
> find a specific ref. This can be very slow if we need to lookup a
> large number of refs. By changing to a binary search we can make this
> faster.
>
> In order to be able to use a binary search we need to change from
> using linked lists to arrays, which we can manage using ALLOC_GROW.
>
> We can now also use the standard library qsort function to sort the
> refs arrays.
>
> Signed-off-by: Julian Phillips <julian@xxxxxxxxxxxxxxxxx>
> ---
>
> Something like this?
>
> refs.c | 328 ++++++++++++++++++++++++++--------------------------------------
> 1 files changed, 131 insertions(+), 197 deletions(-)
>
> diff --git a/refs.c b/refs.c
> index a49ff74..e411bea 100644
> --- a/refs.c
> +++ b/refs.c
> @@ -8,14 +8,18 @@
> #define REF_KNOWS_PEELED 04
> #define REF_BROKEN 010
>
> -struct ref_list {
> - struct ref_list *next;
> +struct ref_entry {
> unsigned char flag; /* ISSYMREF? ISPACKED? */
> unsigned char sha1[20];
> unsigned char peeled[20];
> char name[FLEX_ARRAY];
> };
>
> +struct ref_array {
> + int nr, alloc;
> + struct ref_entry **refs;
> +};
> +
Yeah, I can say "something like that" without looking at the rest of the
patch ;-) The rest should naturally follow from the above data structures.
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html