git/prio-queue.c, branch jch

prio-queue: add prio_queue_replace()

2025-07-22T14:28:35Z

Add a function to replace the top element of the queue that basically does the same as prio_queue_get() followed by prio_queue_put(), but without the work by prio_queue_get() to rebalance the heap. It can be used to optimize loops that get one element and then immediately add another one. That's common e.g., with commit history traversal, where we get out a commit and then put in its parents. Signed-off-by: René Scharfe Signed-off-by: Junio C Hamano

prio-queue: use size_t rather than int for size

2024-12-20T15:21:45Z

The alloc and nr fields of a prio-queue tell us how much memory is allocated and used in the array. So the natural type for them is size_t, which prevents overflow on 64-bit systems where "int" is still 32 bits. This is unlikely to happen in practice, as we typically use it for storing commits, and having 2^31 of those is rather a lot. But it's good to keep our generic data structures as flexible as possible. And as we start to enforce -Wsign-compare, it means that callers need to use "int", too, and the problem proliferates. Let's fix it at the source. The changes here can be put into a few groups: 1. Changing the alloc/nr fields in the struct to size_t. This requires swapping out int for size_t in negotiator/skipping.c, as well as in prio_queue_get(), because those all iterate over the array. Building with -Wsign-compare complains about these. 2. Other code that assigns or passes around indexes into the array (e.g., the swap() and compare() functions) won't trigger -Wsign-compare because we are simply truncating the values. These are caught by -Wconversion, but I've adjusted them here to future-proof us. 3. In prio_queue_reverse() we compute "queue->nr - 1" without checking if anything is in the queue, which underflows now that nr is unsigned. We can fix that by returning early when the queue is empty (there is nothing to reverse). 4. The insertion_ctr variable is currently unsigned, but can likewise grow (it is actually worse, because adding and removing an element many times will keep increasing the counter, even though "nr" does not). I've bumped that to size_t here, as well. But -Wconversion notes that computing the "cmp" result by subtracting the counters and assigning to "int" is a potential problem. And that's true even before this patch, since we use an unsigned counter (imagine comparing "2^32-1" and "0", which should be a high positive value, but instead is "-1" as a signed int). Since we only care about the sign (and not the magnitude) of the result, we could fix this by swapping out the subtraction for a ternary comparison. Probably the performance impact would be negligible, since we just called into a custom compare function and branched on its result anyway. But it's easy enough to do a branchless version by subtracting the comparison results. Signed-off-by: Jeff King Signed-off-by: Junio C Hamano

git-compat-util: move alloc macros to git-compat-util.h

2023-07-05T18:42:31Z

alloc_nr, ALLOC_GROW, and ALLOC_GROW_BY are commonly used macros for dynamic array allocation. Moving these macros to git-compat-util.h with the other alloc macros focuses alloc.[ch] to allocation for Git objects and additionally allows us to remove inclusions to alloc.h from files that solely used the above macros. Signed-off-by: Calvin Wan Signed-off-by: Junio C Hamano

alloc.h: move ALLOC_GROW() functions from cache.h

2023-02-24T01:25:28Z

This allows us to replace includes of cache.h with includes of the much smaller alloc.h in many places. It does mean that we also need to add includes of alloc.h in a number of C files. Signed-off-by: Elijah Newren Signed-off-by: Junio C Hamano

tree-wide: apply equals-null.cocci

2022-05-02T16:50:37Z

Signed-off-by: Junio C Hamano

prio-queue: add 'peek' operation

2018-11-02T03:14:21Z

When consuming a priority queue, it can be convenient to inspect the next object that will be dequeued without actually dequeueing it. Our existing library did not have such a 'peek' operation, so add it as prio_queue_peek(). Add a reference-level comparison in t/helper/test-prio-queue.c so this method is exercised by t0009-prio-queue.sh. Further, add a test that checks the behavior when the compare function is NULL (i.e. the queue becomes a stack). Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

Replace all die("BUG: ...") calls by BUG() ones

2018-05-06T10:06:13Z

In d8193743e08 (usage.c: add BUG() function, 2017-05-12), a new macro was introduced to use for reporting bugs instead of die(). It was then subsequently used to convert one single caller in 588a538ae55 (setup_git_env: convert die("BUG") to BUG(), 2017-05-12). The cover letter of the patch series containing this patch (cf 20170513032414.mfrwabt4hovujde2@sigill.intra.peff.net) is not terribly clear why only one call site was converted, or what the plan is for other, similar calls to die() to report bugs. Let's just convert all remaining ones in one fell swoop. This trick was performed by this invocation: sed -i 's/die("BUG: /BUG("/g' $(git grep -l 'die("BUG' \*.c) Signed-off-by: Johannes Schindelin Signed-off-by: Junio C Hamano

*.[ch] refactoring: make use of the FREE_AND_NULL() macro

2017-06-16T19:44:09Z

Replace occurrences of `free(ptr); ptr = NULL` which weren't caught by the coccinelle rule. These fall into two categories: - free/NULL assignments one after the other which coccinelle all put on one line, which is functionally equivalent code, but very ugly. - manually spotted occurrences where the NULL assignment isn't right after the free() call. Signed-off-by: Ævar Arnfjörð Bjarmason Signed-off-by: Junio C Hamano

Merge branch 'jk/prio-queue-avoid-swap-with-self'

2017-05-01T05:14:43Z

Code clean-up. * jk/prio-queue-avoid-swap-with-self: prio_queue_reverse: don't swap elements with themselves

prio_queue_reverse: don't swap elements with themselves

2017-04-25T04:16:44Z

Our array-reverse algorithm does the usual "walk from both ends, swapping elements". We can quit when the two indices are equal, since: 1. Swapping an element with itself is a noop. 2. If i and j are equal, then in the next iteration i is guaranteed to be bigge than j, and we will exit the loop. So exiting the loop on equality is slightly more efficient. And more importantly, the new SWAP() macro does not expect to handle noop swaps; it will call memcpy() with the same src and dst pointers in this case. It's unclear whether that causes a problem on any platforms by violating the "overlapping memory" constraint of memcpy, but it does cause valgrind to complain. Signed-off-by: Jeff King Signed-off-by: Junio C Hamano