Commit Graph

8 Commits

Author SHA1 Message Date
Junio C Hamano 37e73233c3 strmap: make callers of strmap_remove() to call it in void context
Two "static inline" functions, both of which return void, call
strmap_remove() and tries to return the value it returns as their
return value, which is just bogus, as strmap_remove() returns void
itself.  Call it in the void context and fall-thru the control to
the end instead.

Reported-by: Randall S. Becker <>
Signed-off-by: Junio C Hamano <>
2020-12-15 15:30:44 -08:00
Elijah Newren 23a276a9c4 strmap: take advantage of FLEXPTR_ALLOC_STR when relevant
By default, we do not use a mempool and strdup_strings is true; in this
case, we can avoid both an extra allocation and an extra free by just
over-allocating for the strmap_entry leaving enough space at the end to
copy the key.  FLEXPTR_ALLOC_STR exists for exactly this purpose, so
make use of it.

Also, adjust the case when we are using a memory pool and strdup_strings
is true to just do one allocation from the memory pool instead of two so
that the strmap_clear() and strmap_remove() code can just avoid freeing
the key in all cases.

Signed-off-by: Elijah Newren <>
Signed-off-by: Junio C Hamano <>
2020-11-11 12:55:27 -08:00
Elijah Newren a208ec1f0b strmap: enable allocations to come from a mem_pool
For heavy users of strmaps, allowing the keys and entries to be
allocated from a memory pool can provide significant overhead savings.
Add an option to strmap_init_with_options() to specify a memory pool.

Signed-off-by: Elijah Newren <>
Signed-off-by: Junio C Hamano <>
2020-11-11 12:55:27 -08:00
Elijah Newren 1201eb628a strmap: add a strset sub-type
Similar to adding strintmap for special-casing a string -> int mapping,
add a strset type for cases where we really are only interested in using
strmap for storing a set rather than a mapping.  In this case, we'll
always just store NULL for the value but the different struct type makes
it clearer than code comments how a variable is intended to be used.

The difference in usage also results in some differences in API: a few
things that aren't necessary or meaningful are dropped (namely, the
free_values argument to *_clear(), and the *_get() function), and
strset_add() is chosen as the API instead of strset_put().

Signed-off-by: Elijah Newren <>
Signed-off-by: Junio C Hamano <>
2020-11-06 09:33:35 -08:00
Elijah Newren 4fa1d501f7 strmap: add functions facilitating use as a string->int map
Although strmap could be used as a string->int map, one either had to
allocate an int for every entry and then deallocate later, or one had to
do a bunch of casting between (void*) and (intptr_t).

Add some special functions that do the casting.  Also, rename put->set
for such wrapper functions since 'put' implied there may be some
deallocation needed if the string was already found in the map, which
isn't the case when we're storing an int value directly in the void*
slot instead of using the void* slot as a pointer to data.

Signed-off-by: Elijah Newren <>
Signed-off-by: Junio C Hamano <>
2020-11-04 17:09:49 -08:00
Elijah Newren 6ccdfc2a20 strmap: enable faster clearing and reusing of strmaps
When strmaps are used heavily, such as is done by my new merge-ort
algorithm, and strmaps need to be cleared but then re-used (because of
e.g. picking multiple commits to cherry-pick, or due to a recursive
merge having several different merges while recursing), free-ing and
reallocating map->table repeatedly can add up in time, especially since
it will likely be reallocated to a much smaller size but the previous
merge provides a good guide to the right size to use for the next merge.

Introduce strmap_partial_clear() to take advantage of this type of
situation; it will act similar to strmap_clear() except that
map->table's entries are zeroed instead of map->table being free'd.
Making use of this function reduced the cost of
clear_or_reinit_internal_opts() by about 20% in mert-ort, and dropped
the overall runtime of my rebase testcase by just under 2%.

Signed-off-by: Elijah Newren <>
Signed-off-by: Junio C Hamano <>
2020-11-04 17:09:49 -08:00
Elijah Newren b70c82e6ed strmap: add more utility functions
This adds a number of additional convienence functions I want/need:
  * strmap_get_size()
  * strmap_empty()
  * strmap_remove()
  * strmap_for_each_entry()
  * strmap_get_entry()

I suspect the first four are self-explanatory.

strmap_get_entry() is similar to strmap_get() except that instead of just
returning the void* value that the string maps to, it returns the
strmap_entry that contains both the string and the void* value (or
NULL if the string isn't in the map).  This is helpful because it avoids
multiple lookups, e.g. in some cases a caller would need to call:
  * strmap_contains() to check that the map has an entry for the string
  * strmap_get() to get the void* value
  * <do some work to update the value>
  * strmap_put() to update/overwrite the value
If the void* pointer returned really is a pointer, then the last step is
unnecessary, but if the void* pointer is just cast to an integer then
strmap_put() will be needed.  In contrast, one can call strmap_get_entry()
and then:
  * check if the string was in the map by whether the pointer is NULL
  * access the value via entry->value
  * directly update entry->value
meaning that we can replace two or three hash table lookups with one.

Signed-off-by: Elijah Newren <>
Signed-off-by: Junio C Hamano <>
2020-11-04 17:09:49 -08:00
Elijah Newren ae20bf1ad9 strmap: new utility functions
Add strmap as a new struct and associated utility functions,
specifically for hashmaps that map strings to some value.  The API is
taken directly from Peff's proposal at

Note that similar string-list, I have a strdup_strings setting.
However, unlike string-list, strmap_init() does not take a parameter for
this setting and instead automatically sets it to 1; callers who want to
control this detail need to instead call strmap_init_with_options().
(Future patches will add additional parameters to

Signed-off-by: Elijah Newren <>
Signed-off-by: Junio C Hamano <>
2020-11-02 12:15:50 -08:00