git/hashmap.c, branch v2.35.2

use CALLOC_ARRAY

2021-03-14T00:00:09Z

Add and apply a semantic patch for converting code that open-codes CALLOC_ARRAY to use it instead. It shortens the code and infers the element size automatically. Signed-off-by: René Scharfe Signed-off-by: Junio C Hamano

hashmap: provide deallocation function names

2020-11-02T20:15:50Z

hashmap_free(), hashmap_free_entries(), and hashmap_free_() have existed for a while, but aren't necessarily the clearest names, especially with hashmap_partial_clear() being added to the mix and lazy-initialization now being supported. Peff suggested we adopt the following names[1]: - hashmap_clear() - remove all entries and de-allocate any hashmap-specific data, but be ready for reuse - hashmap_clear_and_free() - ditto, but free the entries themselves - hashmap_partial_clear() - remove all entries but don't deallocate table - hashmap_partial_clear_and_free() - ditto, but free the entries This patch provides the new names and converts all existing callers over to the new naming scheme. [1] https://lore.kernel.org/git/20201030125059.GA3277724@coredump.intra.peff.net/ Signed-off-by: Elijah Newren Signed-off-by: Junio C Hamano

hashmap: introduce a new hashmap_partial_clear()

2020-11-02T20:15:50Z

merge-ort is a heavy user of strmaps, which are built on hashmap.[ch]. clear_or_reinit_internal_opts() in merge-ort was taking about 12% of overall runtime in my testcase involving rebasing 35 patches of linux.git across a big rename. clear_or_reinit_internal_opts() was calling hashmap_free() followed by hashmap_init(), meaning that not only was it freeing all the memory associated with each of the strmaps just to immediately allocate a new array again, it was allocating a new array that was likely smaller than needed (thus resulting in later need to rehash things). The ending size of the map table on the previous commit was likely almost perfectly sized for the next commit we wanted to pick, and not dropping and reallocating the table immediately is a win. Add some new API to hashmap to clear a hashmap of entries without freeing map->table (and instead only zeroing it out like alloc_table() would do, along with zeroing the count of items in the table and the shrink_at field). Signed-off-by: Elijah Newren Signed-off-by: Junio C Hamano

hashmap: allow re-use after hashmap_free()

2020-11-02T20:15:50Z

Previously, once map->table had been freed, any calls to hashmap_put(), hashmap_get(), or hashmap_remove() would cause a NULL pointer dereference (since hashmap_free_() also zeros the memory; without that zeroing, calling these functions would cause a use-after-free problem). Modify these functions to check for a NULL table and automatically allocate as needed. Also add a HASHMAP_INIT(fn, data) macro for initializing hashmaps on the stack without calling hashmap_init(). Signed-off-by: Elijah Newren Signed-off-by: Junio C Hamano

hashmap: adjust spacing to fix argument alignment

2020-11-02T20:15:50Z

No actual code changes; just whitespace adjustments. Signed-off-by: Elijah Newren Signed-off-by: Junio C Hamano

Fix spelling errors in code comments

2019-11-10T07:00:54Z

Reported-by: Jens Schleusener Signed-off-by: Elijah Newren Signed-off-by: Junio C Hamano

hashmap: remove type arg from hashmap_{get,put,remove}_entry

2019-10-07T01:20:12Z

Since these macros already take a `keyvar' pointer of a known type, we can rely on OFFSETOF_VAR to get the correct offset without relying on non-portable `__typeof__' and `offsetof'. Argument order is also rearranged, so `keyvar' and `member' are sequential as they are used as: `keyvar->member' Signed-off-by: Eric Wong Reviewed-by: Derrick Stolee Signed-off-by: Junio C Hamano

hashmap: introduce hashmap_free_entries

2019-10-07T01:20:11Z

`hashmap_free_entries' behaves like `container_of' and passes the offset of the hashmap_entry struct to the internal `hashmap_free_' function, allowing the function to free any struct pointer regardless of where the hashmap_entry field is located. `hashmap_free' no longer takes any arguments aside from the hashmap itself. Signed-off-by: Eric Wong Reviewed-by: Derrick Stolee Signed-off-by: Junio C Hamano

hashmap: hashmap_{put,remove} return hashmap_entry *

2019-10-07T01:20:11Z

And add *_entry variants to perform container_of as necessary to simplify most callers. Signed-off-by: Eric Wong Reviewed-by: Derrick Stolee Signed-off-by: Junio C Hamano

hashmap: use *_entry APIs for iteration

2019-10-07T01:20:11Z

Inspired by list_for_each_entry in the Linux kernel. Once again, these are somewhat compromised usability-wise by compilers lacking __typeof__ support. Signed-off-by: Eric Wong Reviewed-by: Derrick Stolee Signed-off-by: Junio C Hamano