Re: Start handling references internally as a sorted in-memory list

From: Junio C Hamano <junkio@cox.net>
Date: Sep 11, 2006, 23:57 UTC
Message-ID: <7vsliyez2m.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <Pine.LNX.4.64.0609111632050.27779@g5.osdl.org>

Linus Torvalds <torvalds@osdl.org> writes:

Show 6 quoted lines

> This also adds some very rudimentary support for the notion of packed
> And yeah, I know that the "sorting" code is O(n**2) thanks to doing an 
> insertion sort into a simple linked list. Tough. I didn't care enough to 
> do it well. With "n" usually being a few hundred at most, we really don't 
> care, and if we ever do, we _can_ fix it later on to use a heap or 
> something.

I thought what triggered the restructuring of this part was N actually being large enough to cause pain to some people, so I suspect later might need to be reasonably soon ;-).

Show 7 quoted lines

> +static const char *parse_ref_line(char *line, unsigned char *sha1)
> +{
> +	/*
> +	 * 42: the answer to everything.
> +	 *
> +	 * In this case, it happens to be the answer to
>...

Rof,l.

I've been wondering what happens if you pack "refs/heads/foo", delete it, and create "refs/heads/foo/bar" with your proposal. I'll find the answer (which is _not_ "42") in the updated do_for_each_ref(), I guess.