summaryrefslogtreecommitdiff
path: root/usr.bin/make/hash.c
AgeCommit message (Collapse)Author
2022-02-09make: fix mistakes, spelling and typos in comments and manual pagerillig
No binary change for -DNDEBUG.
2022-01-27make: merge duplicate code for finding an entry in a hash tablerillig
No functional change.
2022-01-27make: replace HashEntry_KeyEquals with strncmprillig
No functional change.
2021-12-27make: replace __func__ with actual stringsrillig
Make is supposed to be C90-compatible, and __func__ is from C99. No functional change.
2021-12-15make: use consistent indentation for statements and continuationsrillig
No binary change, except for line numbers in assertions in suff.c.
2021-12-15make: change return type of HashTable_Set to voidrillig
None of the callers needs the HashEntry for further manipulation. No functional change.
2021-12-07make: inline HashIter_Initrillig
It is only used in non-critical code paths, but the generated code gets smaller by inlining. No functional change.
2021-09-12make: fix build for DEBUG_HASH_LOOKUPrillig
2021-04-11make: avoid allocating memory for simple variable namesrillig
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.
2021-04-03make: backport to C90rillig
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.
2021-04-03make: use C99 bool type instead of defining its ownrillig
No functional change.
2021-02-01make: clean up comments in hash.crillig
2020-12-30make(1): format multi-line commentsrillig
2020-12-15make(1): clean up hash function for HashTablerillig
Expressing a multiplication as a bit shifts and subtraction is the job of the compiler. For humans, a multiplication is easier to read.
2020-11-23make(1): use tabs for indentation in hash.h and hash.crillig
2020-11-14make(1): replace a few HashTable_CreateEntry with HashTable_Setrillig
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.
2020-11-05make(1): remove redundant parentheses from sizeof operatorrillig
The parentheses are only needed if the argument is a type, not an expression.
2020-10-25make(1): print hash in debug log with fixed widthrillig
This way all the keys are nicely aligned in the debug log.
2020-10-25make(1): rename hash functions to identify the type namerillig
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.
2020-10-25make(1): clean up comments in hash.crillig
2020-10-25make(1): clean up hash table functionsrillig
2020-10-25make(1): refactor Hash_DeleteTablerillig
2020-10-25make(1): refactor Hash_InitTablerillig
First prepare all the data, then initialize the fields in declaration order.
2020-10-25make(1): clean up RebuildTable for hash tablesrillig
The previous code used ++ and -- a lot, it also reused variables a lot for different purposes.
2020-10-25make(1): reduce amount of string hashingrillig
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.
2020-10-18make(1): rename HashEntry.name to keyrillig
2020-10-18make(1): remove underscore from Hash_Table and Hash_Entryrillig
For consistency with the other type names, such as GNodeListNode.
2020-10-18make(1): make API for iterating over hash tables simplerrillig
2020-10-05make(1): make dir.c, for.c and hash.c ready for WARNS=6rillig
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.
2020-10-05make(1): revert previous commitrillig
It had accidentally reverted all the work from the past few days.
2020-10-05make(1): fix double-free bug in -DCLEANUP mode (since 2020-10-02)rillig
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.
2020-10-04make(1): merge duplicate code in Hash_FindEntry and Hash_CreateEntryrillig
2020-10-04make(1): avoid forward declaration for RebuildTablerillig
2020-10-04make(1): remove dead code from Hash_FindEntryrillig
All callers pass a properly initialized table.
2020-10-03make(1): replace strcpy with memcpy in Hash_CreateEntryrillig
The string length is already known, no need to recalculate it.
2020-10-03make(1): remove unnecessary code from Hash_DeleteEntryrillig
This function is only called 2 times, and both callers pass valid arguments.
2020-10-03make(1): clean up hash table implementationrillig
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.
2020-09-28make(1): make debugging code shorterrillig
2020-09-27make(1): normalize whitespace in source coderillig
There is no more space tab. Either only tabs or only spaces or tabs followed by spaces, but not spaces followed by tabs.
2020-09-26make(1): add Hash_FindValue, for direct access to hash table datarillig
2020-09-13make(1): clean up RCSID blocksrillig
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.
2020-09-05make(1): remove initial size argument from Hash_InitTablerillig
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.
2020-09-05make(1): make Hash_Table independent from -funsigned-charrillig
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.
2020-09-01make(1): rename Hash_Table fieldsrillig
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.
2020-08-28make(1): remove redundant comments from hash.crillig
2020-08-26make(1): remove header sprite.hrillig
Make is independent of the Sprite operating system.
2020-08-01make(1): use consistent indentation in source coderillig
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.
2020-07-20Make DEBUG_HASH less of a fire-hose.sjg
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.
2020-07-19Nix trailing whitespace.riastradh
2020-07-18Add -dh for DEBUG_HASHsjg
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