CVS commit: src/usr.bin/make

["Roland Illig" <rillig%netbsd.org@localhost>]

Module Name:    src
Committed By:   rillig
Date:           Fri Oct  2 22:20:25 UTC 2020

Modified Files:
        src/usr.bin/make: dir.c

Log Message:
make(1): use hash table for looking up open directories by name

As long as there are less than 20 open directories, it's perfectly fine
to use a doubly-linked list for name lookup.  A singly linked list or
even an array list would have been better, but anyway.

When the number of directories rises above 1000, which happens with
dirdeps.mk, linear list lookup becomes too expensive, especially since
each list entry is compared using a strcmp call, in a callback function
that is not inlined.

Using a hash table is much more efficient than linear lookup.  While
here, abstract all operations regarding the openDirectories list into a
new data type that provides a simple and straight-forward API.  This
strongly typed API is especially important since the current
implementation of the list and hash table is weakly typed, using void *
for the actual data, and StringList and CachedDirList refer to the
exactly same type, they just have different names to help the human
readers but don't provide any type safety.


To generate a diff of this commit:
cvs rdiff -u -r1.154 -r1.155 src/usr.bin/make/dir.c

Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.