git/hashmap.c, branch main

git-compat-util: introduce MEMZERO_ARRAY() macro

2025-12-11T05:44:43Z

Introduce a new macro MEMZERO_ARRAY() that zeroes the memory allocated by ALLOC_ARRAY() and friends. And add coccinelle rule to enforce the use of this macro. Signed-off-by: Toon Claes Signed-off-by: Junio C Hamano

Merge branch 'en/hashmap-clear-fix'

2025-05-08T19:36:31Z

hashmap API clean-up to ensure hashmap_clear() leaves a cleared map in a reusable state. * en/hashmap-clear-fix: hashmap: ensure hashmaps are reusable after hashmap_clear()

hashmap: ensure hashmaps are reusable after hashmap_clear()

2025-04-29T16:51:33Z

In the series merged at bf0a430f70b5 (Merge branch 'en/strmap', 2020-11-21), strmap was built on top of hashmap and hashmap was extended in a few ways to support strmap and be more generally useful. One of the extensions was that hashmap_partial_clear() was introduced to allow reuse of the hashmap without freeing the table. Peff believed that it also made sense to introduce a hashmap_clear() which freed everything while allowing reuse. I added hashmap_clear(), but in doing so, overlooked the fact that for a hashmap to be reusable, it needs a defined cmpfn and data (the HASHMAP_INIT macro requires these fields as parameters, for example). So, if we want the hashmap to be reusable, we shouldn't zero out those fields. We probably also shouldn't zero out do_count_items. (We could zero out grow_at and shrink_at, but whether we zero those or not is irrelevant as they'll be automatically updated whenever a new entry is inserted.) Since clearing is associated with freeing map->table, and the only thing required for consistency after freeing map->table is zeroing tablesize and private_size, let's only zero those fields out. Signed-off-by: Elijah Newren Signed-off-by: Junio C Hamano

treewide: remove unnecessary cache.h includes in source files

2023-02-24T01:25:28Z

We had several C files include cache.h unnecessarily. Replace those with an include of "git-compat-util.h" instead. Much like the previous commit, these have all been verified via both ensuring that gcc -E $SOURCE_FILE | grep '"cache.h"' found no hits and that make DEVELOPER=1 ${OBJECT_FILE_FOR_SOURCE_FILE} successfully compiles without warnings. Signed-off-by: Elijah Newren Signed-off-by: Junio C Hamano

git-compat-util.h: use "UNUSED", not "UNUSED(var)"

2022-09-01T17:49:48Z

As reported in [1] the "UNUSED(var)" macro introduced in 2174b8c75de (Merge branch 'jk/unused-annotation' into next, 2022-08-24) breaks coccinelle's parsing of our sources in files where it occurs. Let's instead partially go with the approach suggested in [2] of making this not take an argument. As noted in [1] "coccinelle" will ignore such tokens in argument lists that it doesn't know about, and it's less of a surprise to syntax highlighters. This undoes the "help us notice when a parameter marked as unused is actually use" part of 9b240347543 (git-compat-util: add UNUSED macro, 2022-08-19), a subsequent commit will further tweak the macro to implement a replacement for that functionality. 1. https://lore.kernel.org/git/220825.86ilmg4mil.gmgdl@evledraar.gmail.com/ 2. https://lore.kernel.org/git/220819.868rnk54ju.gmgdl@evledraar.gmail.com/ Signed-off-by: Ævar Arnfjörð Bjarmason Signed-off-by: Junio C Hamano

hashmap: mark unused callback parameters

2022-08-19T19:18:55Z

Hashmap comparison functions must conform to a particular callback interface, but many don't use all of their parameters. Especially the void cmp_data pointer, but some do not use keydata either (because they can easily form a full struct to pass when doing lookups). Let's mark these to make -Wunused-parameter happy. Signed-off-by: Jeff King Signed-off-by: Junio C Hamano

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