summaryrefslogtreecommitdiff
path: root/prio-queue.c
AgeCommit message (Collapse)AuthorFilesLines
2017-05-01Merge branch 'jk/prio-queue-avoid-swap-with-self'Libravatar Junio C Hamano1-1/+1
Code clean-up. * jk/prio-queue-avoid-swap-with-self: prio_queue_reverse: don't swap elements with themselves
2017-04-24prio_queue_reverse: don't swap elements with themselvesLibravatar Jeff King1-1/+1
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 <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2017-01-30use SWAP macroLibravatar René Scharfe1-3/+1
Apply the semantic patch swap.cocci to convert hand-rolled swaps to use the macro SWAP. The resulting code is shorter and easier to read, the object code is effectively unchanged. The patch for object.c had to be hand-edited in order to preserve the comment before the change; Coccinelle tried to eat it for some reason. Signed-off-by: Rene Scharfe <l.s.r@web.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-07-15prio-queue: make output stable with respect to insertionLibravatar Jeff King1-5/+10
If two items are added to a prio_queue and compare equal, they currently come out in an apparently random order (this order is deterministic for a particular sequence of insertions and removals, but does not necessarily match the insertion order). This makes it unlike using a date-ordered commit_list, which is one of the main types we would like to replace with it (because prio_queue does not suffer from O(n) insertions). We can make the priority queue stable by keeping an insertion counter for each element, and using it to break ties. This does increase the memory usage of the structure (one int per element), but in practice it does not seem to affect runtime. A best-of-five "git rev-list --topo-order" on linux.git showed less than 1% difference (well within the run-to-run noise). In an ideal world, we would offer both stable and unstable priority queues (the latter to try to maximize performance). However, given the lack of a measurable performance difference, it is not worth the extra code. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-07-15prio-queue: factor out compare and swap operationsLibravatar Jeff King1-24/+25
When manipulating the priority queue's heap, we frequently have to compare and swap heap entries. As we are storing only void pointers right now, this is quite easy to do inline in a few lines. However, when we start using a more complicated heap entry in a future patch, that will get longer. Factoring out these operations lets us make future changes in one place. It also makes the code a little shorter and more readable. Note that we actually accept indices into the queue array instead of pointers. This is slightly less flexible than passing pointers-to-pointers (we could not swap items from unrelated arrays, but we would not want to), but will make further refactoring simpler (and lets us avoid repeating "queue->array" at each callsite, which led to some long lines). And finally, note that we are cleaning up an accidental use of a "struct commit" pointer to hold a temporary entry during swap. Even though we currently only use this code for commits, it is supposed to be type-agnostic. In practice this didn't matter anyway because we never dereferenced the commit pointer (and on most systems, the pointer values themselves are interchangeable between types). Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2013-06-11sort-in-topological-order: use prio-queueLibravatar Junio C Hamano1-0/+13
Use the prio-queue data structure to implement a priority queue of commits sorted by committer date, when handling --date-order. The structure can also be used as a simple LIFO stack, which is a good match for --topo-order processing. Signed-off-by: Junio C Hamano <gitster@pobox.com>
2013-06-11prio-queue: priority queue of pointers to structsLibravatar Junio C Hamano1-0/+71
Traditionally we used a singly linked list of commits to hold a set of in-flight commits while traversing history. The most typical use of the list is to add commits that are newly discovered to it, keep the list sorted by commit timestamp, pick up the newest one from the list, and keep digging. The cost of keeping the singly linked list sorted is nontrivial, and this typical use pattern better matches a priority queue. Introduce a prio-queue structure, that can be used either as a LIFO stack, or a priority queue. This will be used in the next patch to hold in-flight commits during sort-in-topological-order. Tests and the idea to make it usable for any "void *" pointers to "things" are by Jeff King. Bugs are mine. Signed-off-by: Junio C Hamano <gitster@pobox.com>