Re: Question About Sorting the Index

From: Junio C Hamano <gitster@pobox.com>
Date: May 28, 2025, 02:34 UTC
Message-ID: <xmqqbjrdtqed.fsf@gitster.g>
In-Reply-To: <9befdb3e-ff6e-4416-8735-1eea99dbbf01@gmail.com>

Jon Forrest <nobozo@gmail.com> writes:

Show 10 quoted lines

> On 5/17/25 11:36 AM, Junio C Hamano wrote:
>
>> For example, the fact that the index is first read into core, each
>> entry is represented as a cache_entry in-core structure, and the
>> code accesses them via an array active_cache[], and that array is
>> sorted per pathnames, haven't changed.  
>
> I had a thought. What if the in-memory cache were stored in a hash,
> where the pathname is the key? That way nothing would have to be
> sorted in order to lookup a particular file.

The index must be in sorted order in order to allow a set of tree objects written out of it. Hash may be good for looking up, but it is not the best data structure for stable and efficient enumeration.