summaryrefslogtreecommitdiff
path: root/t/helper/test-hashmap.c
AgeCommit message (Collapse)AuthorFilesLines
2020-11-11Use new HASHMAP_INIT macro to simplify hashmap initializationLibravatar Elijah Newren1-2/+1
Now that hashamp has lazy initialization and a HASHMAP_INIT macro, hashmaps allocated on the stack can be initialized without a call to hashmap_init() and in some cases makes the code a bit shorter. Convert some callsites over to take advantage of this. Signed-off-by: Elijah Newren <newren@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2020-11-02hashmap: provide deallocation function namesLibravatar Elijah Newren1-3/+3
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 <newren@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-10-07hashmap_entry: remove first member requirement from docsLibravatar Eric Wong1-0/+1
Comments stating that "struct hashmap_entry" must be the first member in a struct are no longer valid. Suggested-by: Phillip Wood <phillip.wood123@gmail.com> Signed-off-by: Eric Wong <e@80x24.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-10-07hashmap: remove type arg from hashmap_{get,put,remove}_entryLibravatar Eric Wong1-3/+1
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 <e@80x24.org> Reviewed-by: Derrick Stolee <stolee@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-10-07OFFSETOF_VAR macro to simplify hashmap iteratorsLibravatar Eric Wong1-4/+1
While we cannot rely on a `__typeof__' operator being portable to use with `offsetof'; we can calculate the pointer offset using an existing pointer and the address of a member using pointer arithmetic for compilers without `__typeof__'. This allows us to simplify usage of hashmap iterator macros by not having to specify a type when a pointer of that type is already given. In the future, list iterator macros (e.g. list_for_each_entry) may also be implemented using OFFSETOF_VAR to save hackers the trouble of using container_of/list_entry macros and without relying on non-portable `__typeof__'. v3: use `__typeof__' to avoid clang warnings Signed-off-by: Eric Wong <e@80x24.org> Reviewed-by: Derrick Stolee <stolee@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-10-07hashmap: introduce hashmap_free_entriesLibravatar Eric Wong1-3/+3
`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 <e@80x24.org> Reviewed-by: Derrick Stolee <stolee@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-10-07hashmap: hashmap_{put,remove} return hashmap_entry *Libravatar Eric Wong1-2/+7
And add *_entry variants to perform container_of as necessary to simplify most callers. Signed-off-by: Eric Wong <e@80x24.org> Reviewed-by: Derrick Stolee <stolee@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-10-07hashmap: use *_entry APIs for iterationLibravatar Eric Wong1-3/+4
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 <e@80x24.org> Reviewed-by: Derrick Stolee <stolee@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-10-07hashmap_cmp_fn takes hashmap_entry paramsLibravatar Eric Wong1-4/+6
Another step in eliminating the requirement of hashmap_entry being the first member of a struct. Signed-off-by: Eric Wong <e@80x24.org> Reviewed-by: Derrick Stolee <stolee@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-10-07hashmap: use *_entry APIs to wrap container_ofLibravatar Eric Wong1-7/+5
Using `container_of' can be verbose and choosing names for intermediate "struct hashmap_entry" pointers is a hard problem. So introduce "*_entry" APIs inspired by similar linked-list APIs in the Linux kernel. Unfortunately, `__typeof__' is not portable C, so we need an extra parameter to specify the type. Signed-off-by: Eric Wong <e@80x24.org> Reviewed-by: Derrick Stolee <stolee@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-10-07hashmap_get_next returns "struct hashmap_entry *"Libravatar Eric Wong1-4/+6
This is a step towards removing the requirement for hashmap_entry being the first field of a struct. Signed-off-by: Eric Wong <e@80x24.org> Reviewed-by: Derrick Stolee <stolee@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-10-07hashmap_put takes "struct hashmap_entry *"Libravatar Eric Wong1-1/+1
This is less error-prone than "void *" as the compiler now detects invalid types being passed. Signed-off-by: Eric Wong <e@80x24.org> Reviewed-by: Derrick Stolee <stolee@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-10-07hashmap_add takes "struct hashmap_entry *"Libravatar Eric Wong1-3/+3
This is less error-prone than "void *" as the compiler now detects invalid types being passed. Signed-off-by: Eric Wong <e@80x24.org> Reviewed-by: Derrick Stolee <stolee@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-10-07hashmap_get_next takes "const struct hashmap_entry *"Libravatar Eric Wong1-1/+1
This is less error-prone than "const void *" as the compiler now detects invalid types being passed. Signed-off-by: Eric Wong <e@80x24.org> Reviewed-by: Derrick Stolee <stolee@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-10-07hashmap_entry_init takes "struct hashmap_entry *"Libravatar Eric Wong1-3/+3
C compilers do type checking to make life easier for us. So rely on that and update all hashmap_entry_init callers to take "struct hashmap_entry *" to avoid future bugs while improving safety and readability. Signed-off-by: Eric Wong <e@80x24.org> Reviewed-by: Derrick Stolee <stolee@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2019-06-17test-hashmap: remove 'hash' commandLibravatar Christian Couder1-8/+1
If hashes like strhash() are updated, for example to use a different hash algorithm, we should not have to be updating t0011 to change out the hashes. As long as hashmap can store and retrieve values, and that it performs well, we should not care what are the values of the hashes. Let's just focus on the externally visible behavior instead. Suggested-by: Jeff King <peff@peff.net> Signed-off-by: Christian Couder <chriscool@tuxfamily.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-03-27t/helper: merge test-hashmap into test-toolLibravatar Nguyễn Thái Ngọc Duy1-2/+3
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-02-14test-hashmap: use "unsigned int" for hash storageLibravatar Jeff King1-2/+3
The hashmap API always use an unsigned value for storing and comparing hashes. Whereas this test code uses "int". This works out in practice since one can typically round-trip between "int" and "unsigned int". But since this is essentially reference code for the hashmap API, we should model using the correct types. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-02-14test-hashmap: simplify alloc_test_entryLibravatar Jeff King1-18/+17
This function takes two ptr/len pairs, which implies that they can be arbitrary buffers. But internally, it assumes that each "ptr" is NUL-terminated at "len" (because we memcpy an extra byte to pick up the NUL terminator). In practice this works because each caller only ever passes strlen(ptr) as the length. But let's drop the "len" parameters to make our expectations clear. Note that we can get rid of the "l1" and "l2" variables from cmd_main() as a further cleanup, since they are now mostly used to check whether the p1 and p2 arguments are present (technically the length parameters conflated NULL with the empty string, which we no longer do, but I think that is actually an improvement). Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-02-14test-hashmap: use strbuf_getline rather than fgetsLibravatar Jeff King1-3/+5
Using fgets() with a fixed-size buffer can lead to lines being accidentally split across two calls if they are larger than the buffer size. As this is just a test helper, this is unlikely to be a problem in practice. But since people may look at test helpers as reference code, it's a good idea for them to model the preferred behavior. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-02-14test-hashmap: use xsnprintf rather than snprintfLibravatar Jeff King1-1/+1
In general, using a bare snprintf can truncate the resulting buffer, leading to confusing results. In this case we know that our buffer is sized large enough to accommodate our loop, so there's no bug. However, we should use xsnprintf() to document (and check) that assumption, and to model good practice to people reading the code. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-02-14test-hashmap: check allocation computation for overflowLibravatar Jeff King1-2/+1
When we allocate the test_entry flex-struct, we have to add up all of the elements that go into the flex array. If these were to overflow a size_t, this would allocate a too-small buffer, which we would then overflow in our memcpy steps. Since this is just a test-helper, it probably doesn't matter in practice, but we should model the correct technique by using the st_add() macros. Unfortunately, we cannot use the FLEX_ALLOC() macros here, because we are stuffing two different buffers into a single flex array. While we're here, let's also swap out "malloc" for our error-checking "xmalloc", and use the preferred "sizeof(*var)" instead of "sizeof(type)". Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-02-14test-hashmap: use ALLOC_ARRAY rather than bare mallocLibravatar Jeff King1-2/+2
These two array allocations have several minor flaws: - they use bare malloc, rather than our error-checking xmalloc - they do a bare multiplication to determine the total size (which in theory can overflow, though in this case the sizes are all constants) - they use sizeof(type), but the type in the second one doesn't match the actual array (though it's "int" versus "unsigned int", which are guaranteed by C99 to have the same size) None of these are likely to be problems in practice, and this is just a test helper. But since people often look at test helpers as reference code, we should do our best to model the recommended techniques. Switching to ALLOC_ARRAY fixes all three. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2017-09-07hashmap: add API to disable item counting when threadedLibravatar Jeff Hostetler1-1/+2
This is to address concerns raised by ThreadSanitizer on the mailing list about threaded unprotected R/W access to map.size with my previous "disallow rehash" change (0607e10009ee4e37cb49b4cec8d28a9dda1656a4). See: https://public-inbox.org/git/adb37b70139fd1e2bac18bfd22c8b96683ae18eb.1502780344.git.martin.agren@gmail.com/ Add API to hashmap to disable item counting and thus automatic rehashing. Also include API to later re-enable them. When item counting is disabled, the map.size field is invalid. So to prevent accidents, the field has been renamed and an accessor function hashmap_get_size() has been added. All direct references to this field have been been updated. And the name of the field changed to map.private_size to communicate this. Here is the relevant output from ThreadSanitizer showing the problem: WARNING: ThreadSanitizer: data race (pid=10554) Read of size 4 at 0x00000082d488 by thread T2 (mutexes: write M16): #0 hashmap_add hashmap.c:209 #1 hash_dir_entry_with_parent_and_prefix name-hash.c:302 #2 handle_range_dir name-hash.c:347 #3 handle_range_1 name-hash.c:415 #4 lazy_dir_thread_proc name-hash.c:471 #5 <null> <null> Previous write of size 4 at 0x00000082d488 by thread T1 (mutexes: write M31): #0 hashmap_add hashmap.c:209 #1 hash_dir_entry_with_parent_and_prefix name-hash.c:302 #2 handle_range_dir name-hash.c:347 #3 handle_range_1 name-hash.c:415 #4 handle_range_dir name-hash.c:380 #5 handle_range_1 name-hash.c:415 #6 lazy_dir_thread_proc name-hash.c:471 #7 <null> <null> Martin gives instructions for running TSan on test t3008 in this post: https://public-inbox.org/git/CAN0heSoJDL9pWELD6ciLTmWf-a=oyxe4EXXOmCKvsG5MSuzxsA@mail.gmail.com/ Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2017-07-05t/helper/test-hashmap: use custom data instead of duplicate cmp functionsLibravatar Stefan Beller1-18/+16
With the new field that is passed to the compare function, we can pass through flags there instead of having multiple compare functions. Also drop the cast to hashmap_cmp_fn. Signed-off-by: Stefan Beller <sbeller@google.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2017-06-30hashmap.h: compare function has access to a data fieldLibravatar Stefan Beller1-7/+12
When using the hashmap a common need is to have access to caller provided data in the compare function. A couple of times we abuse the keydata field to pass in the data needed. This happens for example in patch-ids.c. This patch changes the function signature of the compare function to have one more void pointer available. The pointer given for each invocation of the compare function must be defined in the init function of the hashmap and is just passed through. Documentation of this new feature is deferred to a later patch. This is a rather mechanical conversion, just adding the new pass-through parameter. However while at it improve the naming of the fields of all compare functions used by hashmaps by ensuring unused parameters are prefixed with 'unused_' and naming the parameters what they are (instead of 'unused' make it 'unused_keydata'). Signed-off-by: Stefan Beller <sbeller@google.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-07-06Merge branch 'jk/common-main-2.8' into jk/common-mainLibravatar Junio C Hamano1-1/+1
* jk/common-main-2.8: mingw: declare main()'s argv as const common-main: call git_setup_gettext() common-main: call restore_sigpipe_to_default() common-main: call sanitize_stdfds() common-main: call git_extract_argv0_path() add an extra level of indirection to main()
2016-04-15test helpers: move test-* to t/helper/ subdirectoryLibravatar Nguyễn Thái Ngọc Duy1-0/+264
This keeps top dir a bit less crowded. And because these programs are for testing purposes, it makes sense that they stay somewhere in t/ Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>