CVS log for src/usr.bin/make/hash.c

Up to [cvs.NetBSD.org] / src / usr.bin / make

Request diff between arbitrary revisions

Keyword substitution: kv
Default branch: MAIN

make: clean up

Replace 'unsigned int' with simply 'unsigned'.

In compat.c, skipping whitespace is not needed, as the loop above
already skips it.

In job.c, remove the unused header <sys/file.h>.

Inline the TMPPAT macro, as it is only needed in a single place.

make: don't track hash table chain lengths during lookup

The chain lengths are only used for debugging purposes, so avoid the
extra cost at each lookup.  Instead, calculate the maximum chain length
only when it is actually requested in -dh mode.

The reported number changes slightly: Before, it was the length of the
chain that was actually traversed to find an entry, up to that entry,
now it is the length of the largest chain in the table, no matter if it
was actually accessed or not.

make: sync comments with reality

make: simplify expression in iteration over hash tables

make: clean up API for iterating over hash tables

make: remove dead code from HashTable_DeleteEntry

make: clean up comments

No binary change, except for line numbers in assertions.

make: clean up names of local variables

No binary change.

make: fix mistakes, spelling and typos in comments and manual page

No binary change for -DNDEBUG.

make: merge duplicate code for finding an entry in a hash table

No functional change.

make: replace HashEntry_KeyEquals with strncmp

No functional change.

make: replace __func__ with actual strings

Make is supposed to be C90-compatible, and __func__ is from C99.

No functional change.

make: use consistent indentation for statements and continuations

No binary change, except for line numbers in assertions in suff.c.

make: change return type of HashTable_Set to void

None of the callers needs the HashEntry for further manipulation.

No functional change.

make: inline HashIter_Init

It is only used in non-critical code paths, but the generated code gets
smaller by inlining.

No functional change.

make: fix build for DEBUG_HASH_LOOKUP

make: avoid allocating memory for simple variable names

The main change is in ParseVarname, where a Buffer is replaced with the
newly introduced LazyBuf.  LazyBuf is inspired by
https://golang.org/src/path/path.go.

In CanonicalVarname, the pre-comparison of the first letter of the
variable name is no longer necessary.  GCC 9 optimizes a fixed-length
memcmp so well that the code can finally be written to target human
readers, leaving the optimization to the compiler.

make: backport to C90

In the past few months I had accidentally used C99 features in the make
code.  According to tools/README, tools that are used in the build
system should restrict themselves to C90.

This allows make to build with GCC's options "-pedantic
-Wno-system-headers -Dinline= -Wno-error=cast-qual".

I didn't notice anyone actively complaining though, I just wanted to see
how much work this backporting would be.  The identifier __func__ is
still used, as in other tools.

No functional change.

make: use C99 bool type instead of defining its own

No functional change.

make: clean up comments in hash.c

make(1): format multi-line comments

make(1): clean up hash function for HashTable

Expressing a multiplication as a bit shifts and subtraction is the job
of the compiler.  For humans, a multiplication is easier to read.

make(1): use tabs for indentation in hash.h and hash.c

make(1): replace a few HashTable_CreateEntry with HashTable_Set

Instead of HashTable_CreateEntry and HashEntry_Set, several places just
need the HashEntry for storing a value in it.  This makes the calling
code simpler to understand.

These parts of the code are already hard enough to understand since they
are about memory management and aliasing.  Having a too detailed API for
the HashTable only distracts from these topics.

make(1): remove redundant parentheses from sizeof operator

The parentheses are only needed if the argument is a type, not an
expression.

make(1): print hash in debug log with fixed width

This way all the keys are nicely aligned in the debug log.

make(1): rename hash functions to identify the type name

This makes it easier to spot mismatches between the function name and
its first parameter, although the compiler should already catch most of
them.  Except for void pointers.

make(1): clean up comments in hash.c

make(1): clean up hash table functions

make(1): refactor Hash_DeleteTable

make(1): refactor Hash_InitTable

First prepare all the data, then initialize the fields in declaration
order.

make(1): clean up RebuildTable for hash tables

The previous code used ++ and -- a lot, it also reused variables a lot
for different purposes.

make(1): reduce amount of string hashing

In pkgsrc, running "bmake show-all" in pkgtools/pkglint called the hash
function 249130 times before, and only 115502 times after.

Still, a single call to Var_Set hashes the same string 3 times.

make(1): rename HashEntry.name to key

make(1): remove underscore from Hash_Table and Hash_Entry

For consistency with the other type names, such as GNodeListNode.

make(1): make API for iterating over hash tables simpler

make(1): make dir.c, for.c and hash.c ready for WARNS=6

Some types have changed from int to unsigned int, size_t or time_t.

The variable i in hash.c has been kept as int since it counts down to
-1, which generates efficient machine code, at least on x86_64.

make(1): revert previous commit

It had accidentally reverted all the work from the past few days.

make(1): fix double-free bug in -DCLEANUP mode (since 2020-10-02)

The bug had been introduced with dir.c 1.155 on 2020-10-02 22:20:25.  In
that commit, openDirectories was replaced with a combination of a list
with a hash table, for more efficient lookup by name.

Upon cleanup, OpenDirs_Done is called, which in turn called
Dir_ClearPath.  Dir_ClearPath takes full ownership of the given list and
empties it.  This was no problem before since afterwards the list was
empty and calling Lst_Free just frees the remaining list pointer.

With OpenDirs, this list was combined with a hash table, and the hash
table contains the list nodes, assuming that the OpenDirs functions have
full ownership of both the list and the hash table.  This assumption was
generally correct, except for the one moment during cleanup where full
ownership of the list was passed to Dir_ClearPath, while the hash table
still contained pointers to the (now freed) list nodes.  This by itself
was not a problem since the hash table would be freed afterwards.  But
as part of Dir_ClearPath, OpenDirs_Remove was called, which looked up
the freed directory by name and now found the freed list node, trying to
free it again.  Boom.

Fixed by replacing the call to Dir_ClearPath with code that only frees
the directories, without giving up control over the list.

make(1): merge duplicate code in Hash_FindEntry and Hash_CreateEntry

make(1): avoid forward declaration for RebuildTable

make(1): remove dead code from Hash_FindEntry

All callers pass a properly initialized table.

make(1): replace strcpy with memcpy in Hash_CreateEntry

The string length is already known, no need to recalculate it.

make(1): remove unnecessary code from Hash_DeleteEntry

This function is only called 2 times, and both callers pass valid
arguments.

make(1): clean up hash table implementation

Having the hash function potentially redefined is a bit too much
flexibility.  If actually needed, this should be done using a patch, not
using the C preprocessor.

Converting the macro to a function made the control flow easier to
understand.  It also revealed that the variable p was unnecessary in
both Hash_FindEntry and Hash_CreateEntry.

make(1): make debugging code shorter

make(1): normalize whitespace in source code

There is no more space tab.  Either only tabs or only spaces or tabs
followed by spaces, but not spaces followed by tabs.

make(1): add Hash_FindValue, for direct access to hash table data

make(1): clean up RCSID blocks

These blocks mostly consisted of redundant structure, following the same
#ifndef pattern over and over, with only minimal variation.

It's easier to maintain if the common structure is only written once and
encapsulated in a macro.

To avoid "defined but unused" warnings from GCC in the case where
MAKE_NATIVE is not defined, I had to add volatile.  Adding
MAKE_ATTR_UNUSED alone would not preserve the rcsid variable in the
resulting binary.

make(1): remove initial size argument from Hash_InitTable

In all but one case this argument was set to auto-detect anyway.  The
one case where it was set was not worth keeping this complicated API.

make(1): make Hash_Table independent from -funsigned-char

This only makes a difference for Hash_Table keys outside the ASCII
character set, and these are barely used in practice, if at all.

The effects of this change can only be seen in debug mode, when printing
the full contents of the variable namespaces.  In this output, the order
of the entries might change.

All other use cases stay the same as before.

make(1): rename Hash_Table fields

Back in the 1980s it made sense to have the type information encoded in
the variable names.  At the time when make was imported into the NetBSD
tree (1993-03-21), the functions did indeed not have prototypes, they
only had return types.  The void type was already invented at that time.
Since the compiler could not verify the types of function parameters, it
made perfect sense to have each variable tell whether it was a pointer
or not.

Since ISO C90 this is no longer necessary since the compiler checks
this.  The variable names can now focus on the application level and
their high-level meaning, expressing the relationship to other
variables instead of encoding redundant type information.

make(1): remove redundant comments from hash.c

make(1): remove header sprite.h

Make is independent of the Sprite operating system.

make(1): use consistent indentation in source code

Tabs for multiples of 8, then spaces.

The usage string has been kept as-is since the spaces there are
indentional and do influence the output.

Make DEBUG_HASH less of a fire-hose.

Reporting keys on every lookup is overkill unless
playing with a new HASH, so wrap in #ifdef DEBUG_HASH_LOOKUP
Also add some stats at the end so we can see
final size and max chain length - maxchain is a better
variable name than maxlen.

Nix trailing whitespace.

Add -dh for DEBUG_HASH

Allow tracking of max chain length, to see how well the hash
tables are working.
Pull the actual hash operation into a marco so it can be
easily changed - for experimenting.

The current hash, is pretty good.

Reviewed by: christos

make(1): add Hash_ForEach to avoid duplicate code

make(1): remove redundant parentheses around return values

Rebase to HEAD as of a few days ago.

sync with head.

for a reference, the tree before this commit was tagged
as yamt-pagecache-tag8.

this commit was splitted into small chunks to avoid
a limitation of cvs.  ("Protocol error: too many arguments")

Don't SEGV when Hash_Table is uninitialized

Don't cast 'time_t' to 'void *' and back it will lose precision.

Use NULL instead of -1 cast to the relavant type (usually via NIL).
This was a suggestion from christos - so blame him if there is a deep
reason for using -1 :-)

Don't use emalloc and friends directly, but call them consistently
bmake_malloc and friends. Implement them via macros for the native case
and provide fallback implementations otherwise. Avoid polluting the
namespace by not defining enomem globally. Don't bother to provide
strdup and strndup, they were only used for the estrdup and estrndup
comapt code.

This addresses the presence of emalloc in system libraries on A/UX and
resulted strange issues as reported by Timothy E. Larson.

remove unnecessary casts to void * functions (Max Okumoto)

Whitespace KNF cleanup from Max Okumoto

PR/29203, PR/29204: Max Okumoto: KNF changes to make [no functional changes]

Pull up revision 1.13 (requested by sjg in ticket #282):
Simplify build, no functional changes.
Instead of adding MAKE_BOOTSTRAP for hosted environments, i.e., when
you want things simple, instead add MAKE_NATIVE to get those hugely
important features like __RCSID().
It's now possible to build make on some hosts with: cc *.c */*.c

Simplify build, no functional changes.

Instead of adding MAKE_BOOTSTRAP for hosted environments, i.e., when
you want things simple, instead add MAKE_NATIVE to get those hugely
important features like __RCSID().

It's now possible to build make on some hosts with: cc *.c */*.c

Move UCB-licensed code from 4-clause to 3-clause licence.

Patches provided by Joel Baker in PR 22365, verified by myself.

Pass WARNS=3

Remove !__STDC__ stuff, de-__P(), ANSIfy, and de-register.

Sync w/ netbsd-1-5-base.

Use a lower threshold for rebuilding hash tables.

wrap #include <sys/cdefs.h>, __RCSID(...) stuff in #ifndef MAKE_BOOTSTRAP

Add WARNS=1
RCSID police

Update make(1) from trunk, by request from Christos Zoulas.  Fixes many bugs.

Import 4.4BSD-Lite2 sources onto CSRG branch (already merged at head)

- Merge in FreeBSD and Lite2 changes.
- Fix bug where a non-archive target with a .a suffix would always
  be considered to be out of date, since it does not have a TOC.

- $NetBSD$ rcsids
- Fixed so that .[A-Z]* targets that do not match keywords are ignored as
  Posix mandates
- Added .PHONY target keyword

fixes/improvements from Christos Zoulas <christos@deshaw.com>.

Include appropriate header files to bring prototypes into scope.

Add RCS identifiers.

initial import of 386bsd-0.1 sources

Initial revision