git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 2/4] basic priority queue implementation

From
Jeff King <peff@peff.net>
Date
May 20, 2011, 07:38 UTC
Message-ID
<20110520073821.GA3663@sigill.intra.peff.net>
In-Reply-To
<BANLkTikLSwWanxUksf3Ezx7uhaTR4mMiWw@mail.gmail.com>
On Thu, May 19, 2011 at 09:47:38PM -0300, Thiago Farina wrote:
> > +void queue_insert(struct queue *pq, void *item);
> I'd rename this to queue_append as we add |item| to the end of the
> array (like you did for sha1_array_append), opposed of inserting it at
> some position/index.

It's definitely not an append. The data structure is a priority queue, so the element is inserted within the heap at the proper position according to the comparison function (notice that we stick at the end, but then heapify_up).

Speaking of naming, though, the real problem is that this data structure should be called "pqueue" or something similar to indicate that it is not a simple FIFO. Unfortunately, the short-and-sweet "pqueue" is taken by openssl, which pollutes all over the global namespace.

-Peff

PS If you don't mind, please try to trim your quoted text a bit. Finding your 3-line paragraph amid 200 lines of quoted text was a little challenging. :)

Previous: Thiago FarinaNext: Thiago Farina
Message 6 of 12 in “fetch: avoid repeated commits in mark_complete”
  1. fetch: avoid repeated commits in mark_completeJeff King, May 19, 2011
  2. 0/4 commit lists as priority queuesJeff King, May 19, 2011
  3. 1/4 Makefile: sort TEST_PROGRAMS listJeff King, May 19, 2011
  4. 2/4 basic priority queue implementationJeff King, May 19, 2011
  5. Thiago FarinaMay 20, 2011
  6. Jeff KingMay 20, 2011
  7. Thiago FarinaMay 20, 2011
  8. Jeff KingMay 20, 2011
  9. 3/4 commit: add infrastructure for priority queues of commitsJeff King, May 19, 2011
  10. 4/4 fetch-pack: use priority queue for mark_completeJeff King, May 19, 2011
  11. Junio C HamanoMay 20, 2011
  12. Junio C HamanoMay 20, 2011

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.