Le mer. 23 sept. 2026, 23:00, Kamila Szewczyk <[email protected]>
a écrit :
> Laurent,
>
Kamila, XD
Quite annoying the notification when I was going to sleep.
I'm back on my laptop just for that.
>
> I am afraid that you misunderstand the issue at hand.
Not at all.
> Gperf indeed
> builds a perfect hash from a key set that is fixed at compile time.
> However, ls doesn't read dircolors.hin. It parses LS_COLORS at runtime
> (as you can see from src/ls.c:2761), and users can put any entries they
> like in that variable.
>
Yes, BUT the users can add entries in LS_COLORS that are or not present in
dircolors.hin.
Here is the data flow I consider for my reasoning
dircolors.hin -> DEFAULT LS_COLORS
or user CUSTOM LS_COLORS
LS_COLORS -> parsing -> filling PHT + HT or LL
Only PHT has a perfect hash function crafted for the keys of the default
LS_COLORS,
that may also be found in some custom LS_COLORS.
If some other key has the same hash than a default key,
you can detect with a single string comparison
that it is not the default key but a custom key that happened to share
the same hash, thus not filling PHT in that case,
and going to HT or LL just after.
>
> Besides that, gperf would also get many of the semantics wrong: e.g.,
> *.tar.gz match against the end of the filename at any length, matching
> is typically case-insensitive with the exception of the case being the
> only difference, and further there is a clear problem of precedence.
>
A more interesting point.
But you can have a PHT1 for case-sensitive patterns first,
then if not present check the presence/do a lookup in PHT2 for those keys
that are case-insensitive
where you do a lookup in PHT2 after lowercasing everything.
I have this in a local copy of dircolors.hin
.gz 01;31
.tar 01;31
ls just checks the .gz of .tar.gz.
Thus variable length is only handled by extension extracted out of basename
for what I see in default LS_COLORS.
Otherwise, for the end of the filename at any length,
it just mean that you have to store the possible lengths of the suffixes
that correspond to default keys that are compatible with one of the two
PHTs.
So imagine you have:
*.tar
*.gz
(instead of just .tar, .gz to somehow follow your hint
at the possibility of globbing)
at compile time you remember 4 and 3,
put 3 and 4 in an array of size 2 LA.
Then for some length in LA,
set suffix start pointer to basename end minus this length,
do a lookup in PHTs with current suffix, etc.
If nothing is found, use the LL fallback to loop on all possible globbing
patterns.
>
> A better idea is to use gnulib's built-in hashing functions.
>
> I think my explanation above would still be faster.
> --
> With Valediction,
> Kamila Szewczyk (https://iczelia.net)
>
> On 9/23/26 9:22 PM, Laurent Lyaudet wrote:
> > Hello Kamila,
> >
> >> I thought of that already, but the LS_COLORS environmental variable
> >> needs to be supported anyway (iuic). There could be a gperf fallback,
> >> though.
> > Correct me if I'm wrong:
> > - perfect hashing is about hash key not about values associated,
> > - O(1) + O(1) = O(1)
> > - So the perfect hash table (gperf) should not be used as a
> > fallback... but in first intent.
> > gperf should be used during development to obtain a perfect hash
> > function for the keys that are in the file dircolors.hin.
> > And all these keys should be preset in the corresponding hash table to
> > a default "NON-NULL" witness value.
> > Then when you parse LS_COLORS if the key exists with a default
> > "NON-NULL" witness value in PHT (Perfect Hash Table),
> > you set the value in PHT to what you read in LS_COLORS.
> > Other keys in custom LS_COLORS are to be put with their value in
> > either another hash table,
> > with a hash function that is not perfect since we cannot guarantee
> > anything on these keys,
> > or keep the current linked list to store these uncommon values.
> > Then whenever a search for a key is done in this data-structure made
> > of a front PHT and a fallback (either HT or LL),
> > if the result is from the PHT with the witness value, ignore it,
> > otherwise use it.
> >
> > PHT for common keys, something else otherwise.
> > I don't see the reason for your "but the LS_COLORS...".
> > That's simple, not over-engineered common optimizations
> > done for the usual 90 % of use cases in 10 % of the features.
> >
> > Have a nice evening, best regards,
> > Laurent
>
>
