/src/git/prio-queue.h

Source
#ifndef PRIO_QUEUE_H
#define PRIO_QUEUE_H

/*
 * A priority queue implementation, primarily for keeping track of
 * commits in the 'date-order' so that we process them from new to old
 * as they are discovered, but can be used to hold any pointer to
 * struct.  The caller is responsible for supplying a function to
 * compare two "things".
 *
 * Alternatively, this data structure can also be used as a LIFO stack
 * by specifying NULL as the comparison function.
 */

/*
 * Compare two "things", one and two; the third parameter is cb_data
 * in the prio_queue structure.  The result is returned as a sign of
 * the return value, being the same as the sign of the result of
 * subtracting "two" from "one" (i.e. negative if "one" sorts earlier
 * than "two").
 */
typedef int (*prio_queue_compare_fn)(const void *one, const void *two, void *cb_data);

struct prio_queue_entry {
  size_t ctr;
  void *data;
};

struct prio_queue {
  prio_queue_compare_fn compare;
  size_t insertion_ctr;
  void *cb_data;
  size_t alloc, nr_; /* use prio_queue_size() for logical count */
  struct prio_queue_entry *array;
  unsigned get_pending;
};

/*
 * Add the "thing" to the queue.
 */
void prio_queue_put(struct prio_queue *, void *thing);

/*
 * Extract the "thing" that compares the smallest out of the queue,
 * or NULL.  If compare function is NULL, the queue acts as a LIFO
 * stack.
 */
void *prio_queue_get(struct prio_queue *);

/*
 * Gain access to the "thing" that would be returned by
 * prio_queue_get, but do not remove it from the queue.
 */
void *prio_queue_peek(struct prio_queue *);

static inline size_t prio_queue_size(const struct prio_queue *queue)
{
  return queue->nr_ - queue->get_pending;
}

#define prio_queue_for_each(queue, it) \
  for (size_t pq_ix_ = (queue)->get_pending; \
       pq_ix_ < (queue)->nr_ && ((it) = (queue)->array[pq_ix_].data, 1); \
       pq_ix_++)

void clear_prio_queue(struct prio_queue *);

/* Reverse the LIFO elements */
void prio_queue_reverse(struct prio_queue *);

#endif /* PRIO_QUEUE_H */

Line	Count	Source
1		#ifndef PRIO_QUEUE_H
2		#define PRIO_QUEUE_H
3
4		/*
5		* A priority queue implementation, primarily for keeping track of
6		* commits in the 'date-order' so that we process them from new to old
7		* as they are discovered, but can be used to hold any pointer to
8		* struct. The caller is responsible for supplying a function to
9		* compare two "things".
10		*
11		* Alternatively, this data structure can also be used as a LIFO stack
12		* by specifying NULL as the comparison function.
13		*/
14
15		/*
16		* Compare two "things", one and two; the third parameter is cb_data
17		* in the prio_queue structure. The result is returned as a sign of
18		* the return value, being the same as the sign of the result of
19		* subtracting "two" from "one" (i.e. negative if "one" sorts earlier
20		* than "two").
21		*/
22		typedef int (prio_queue_compare_fn)(const void one, const void two, void cb_data);
23
24		struct prio_queue_entry {
25		size_t ctr;
26		void *data;
27		};
28
29		struct prio_queue {
30		prio_queue_compare_fn compare;
31		size_t insertion_ctr;
32		void *cb_data;
33		size_t alloc, nr_; /* use prio_queue_size() for logical count */
34		struct prio_queue_entry *array;
35		unsigned get_pending;
36		};
37
38		/*
39		* Add the "thing" to the queue.
40		*/
41		void prio_queue_put(struct prio_queue , void thing);
42
43		/*
44		* Extract the "thing" that compares the smallest out of the queue,
45		* or NULL. If compare function is NULL, the queue acts as a LIFO
46		* stack.
47		*/
48		void prio_queue_get(struct prio_queue );
49
50		/*
51		* Gain access to the "thing" that would be returned by
52		* prio_queue_get, but do not remove it from the queue.
53		*/
54		void prio_queue_peek(struct prio_queue );
55
56		static inline size_t prio_queue_size(const struct prio_queue *queue)
57	0	{
58	0	return queue->nr_ - queue->get_pending;
59	0	} Unexecuted instantiation: commit.c:prio_queue_size Unexecuted instantiation: object-name.c:prio_queue_size Unexecuted instantiation: pack-bitmap.c:prio_queue_size Unexecuted instantiation: pretty.c:prio_queue_size Unexecuted instantiation: prio-queue.c:prio_queue_size Unexecuted instantiation: read-cache.c:prio_queue_size Unexecuted instantiation: reflog-walk.c:prio_queue_size Unexecuted instantiation: files-backend.c:prio_queue_size Unexecuted instantiation: remote.c:prio_queue_size Unexecuted instantiation: revision.c:prio_queue_size Unexecuted instantiation: shallow.c:prio_queue_size Unexecuted instantiation: submodule.c:prio_queue_size Unexecuted instantiation: wt-status.c:prio_queue_size Unexecuted instantiation: attr.c:prio_queue_size Unexecuted instantiation: bisect.c:prio_queue_size Unexecuted instantiation: bundle.c:prio_queue_size Unexecuted instantiation: combine-diff.c:prio_queue_size Unexecuted instantiation: commit-reach.c:prio_queue_size Unexecuted instantiation: diff-merges.c:prio_queue_size Unexecuted instantiation: diff-lib.c:prio_queue_size Unexecuted instantiation: diff.c:prio_queue_size Unexecuted instantiation: fetch-pack.c:prio_queue_size Unexecuted instantiation: graph.c:prio_queue_size Unexecuted instantiation: line-log.c:prio_queue_size Unexecuted instantiation: list-objects.c:prio_queue_size Unexecuted instantiation: log-tree.c:prio_queue_size Unexecuted instantiation: merge-ort.c:prio_queue_size Unexecuted instantiation: pack-bitmap-write.c:prio_queue_size Unexecuted instantiation: range-diff.c:prio_queue_size Unexecuted instantiation: sequencer.c:prio_queue_size Unexecuted instantiation: list-objects-filter.c:prio_queue_size Unexecuted instantiation: default.c:prio_queue_size Unexecuted instantiation: skipping.c:prio_queue_size
60
61		#define prio_queue_for_each(queue, it) \
62	0	for (size_t pq_ix_ = (queue)->get_pending; \
63	0	pq_ix_ < (queue)->nr_ && ((it) = (queue)->array[pq_ix_].data, 1); \
64	0	pq_ix_++)
65
66		void clear_prio_queue(struct prio_queue *);
67
68		/* Reverse the LIFO elements */
69		void prio_queue_reverse(struct prio_queue *);
70
71		#endif /* PRIO_QUEUE_H */

Coverage Report

Created: 2026-10-17 07:15