1. 02 Nov, 2018 1 commit
    • Derrick Stolee's avatar
      prio-queue: add 'peek' operation · aca4240f
      Derrick Stolee authored
      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: 's avatarDerrick Stolee <dstolee@microsoft.com>
      Signed-off-by: 's avatarJunio C Hamano <gitster@pobox.com>
  2. 06 May, 2018 1 commit
    • Johannes Schindelin's avatar
      Replace all die("BUG: ...") calls by BUG() ones · 033abf97
      Johannes Schindelin authored
      In d8193743 (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 588a538a
      (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's avatarJohannes Schindelin <johannes.schindelin@gmx.de>
      Signed-off-by: 's avatarJunio C Hamano <gitster@pobox.com>
  3. 16 Jun, 2017 1 commit
  4. 25 Apr, 2017 1 commit
    • Jeff King's avatar
      prio_queue_reverse: don't swap elements with themselves · 1f9e18b7
      Jeff King authored
      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
      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: 's avatarJeff King <peff@peff.net>
      Signed-off-by: 's avatarJunio C Hamano <gitster@pobox.com>
  5. 30 Jan, 2017 1 commit
    • René Scharfe's avatar
      use SWAP macro · 35d803bc
      René Scharfe authored
      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: 's avatarRene Scharfe <l.s.r@web.de>
      Signed-off-by: 's avatarJunio C Hamano <gitster@pobox.com>
  6. 15 Jul, 2014 2 commits
    • Jeff King's avatar
      prio-queue: make output stable with respect to insertion · e8f91e3d
      Jeff King authored
      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: 's avatarJeff King <peff@peff.net>
      Signed-off-by: 's avatarJunio C Hamano <gitster@pobox.com>
    • Jeff King's avatar
      prio-queue: factor out compare and swap operations · 6d63baa4
      Jeff King authored
      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
      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: 's avatarJeff King <peff@peff.net>
      Signed-off-by: 's avatarJunio C Hamano <gitster@pobox.com>
  7. 11 Jun, 2013 2 commits
    • Junio C Hamano's avatar
      sort-in-topological-order: use prio-queue · da24b104
      Junio C Hamano authored
      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: 's avatarJunio C Hamano <gitster@pobox.com>
    • Junio C Hamano's avatar
      prio-queue: priority queue of pointers to structs · b4b594a3
      Junio C Hamano authored
      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: 's avatarJunio C Hamano <gitster@pobox.com>