| Message ID | cc1ec4c2702d8ba35873600d321015bb0430d92e.1537551564.git.gitgitgadget@gmail.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | Use generation numbers for --topo-order | expand |
On 9/21/2018 1:39 PM, Derrick Stolee via GitGitGadget wrote: > From: Derrick Stolee <dstolee@microsoft.com> > > 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. > > Signed-off-by: Derrick Stolee <dstolee@microsoft.com> > --- > prio-queue.c | 9 +++++++++ > prio-queue.h | 6 ++++++ > t/helper/test-prio-queue.c | 10 +++++++--- > 3 files changed, 22 insertions(+), 3 deletions(-) > > diff --git a/prio-queue.c b/prio-queue.c > index a078451872..d3f488cb05 100644 > --- a/prio-queue.c > +++ b/prio-queue.c > @@ -85,3 +85,12 @@ void *prio_queue_get(struct prio_queue *queue) > } > return result; > } > + > +void *prio_queue_peek(struct prio_queue *queue) > +{ > + if (!queue->nr) > + return NULL; > + if (!queue->compare) > + return queue->array[queue->nr - 1].data; > + return queue->array[0].data; > +} The second branch here is never run by the test suite, as the only consumers never have compare== NULL. I'll add an ability to test this "stack" behavior into t0009-prio-queue.sh. -Stolee
On Fri, Sep 21, 2018 at 10:39:27AM -0700, Derrick Stolee via GitGitGadget wrote: > From: Derrick Stolee <dstolee@microsoft.com> > > 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(). Makes sense. > +void *prio_queue_peek(struct prio_queue *queue) > +{ > + if (!queue->nr) > + return NULL; > + if (!queue->compare) > + return queue->array[queue->nr - 1].data; > + return queue->array[0].data; The non-compare version of get() treats this like a LIFO, and you do the same here. Looks good. In theory get() could be implemented in terms of peek(), but the result is not actually shorter because we have to check those same conditions to decide how to remove the item anyway. > diff --git a/t/helper/test-prio-queue.c b/t/helper/test-prio-queue.c > index 9807b649b1..e817bbf464 100644 > --- a/t/helper/test-prio-queue.c > +++ b/t/helper/test-prio-queue.c > @@ -22,9 +22,13 @@ int cmd__prio_queue(int argc, const char **argv) > struct prio_queue pq = { intcmp }; > > while (*++argv) { > - if (!strcmp(*argv, "get")) > - show(prio_queue_get(&pq)); > - else if (!strcmp(*argv, "dump")) { > + if (!strcmp(*argv, "get")) { > + void *peek = prio_queue_peek(&pq); > + void *get = prio_queue_get(&pq); > + if (peek != get) > + BUG("peek and get results do not match"); > + show(get); > + } else if (!strcmp(*argv, "dump")) { This is a nice cheap way of piggy-backing on the existing get tests. -Peff
diff --git a/prio-queue.c b/prio-queue.c index a078451872..d3f488cb05 100644 --- a/prio-queue.c +++ b/prio-queue.c @@ -85,3 +85,12 @@ void *prio_queue_get(struct prio_queue *queue) } return result; } + +void *prio_queue_peek(struct prio_queue *queue) +{ + if (!queue->nr) + return NULL; + if (!queue->compare) + return queue->array[queue->nr - 1].data; + return queue->array[0].data; +} diff --git a/prio-queue.h b/prio-queue.h index d030ec9dd6..682e51867a 100644 --- a/prio-queue.h +++ b/prio-queue.h @@ -46,6 +46,12 @@ extern void prio_queue_put(struct prio_queue *, void *thing); */ extern 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. + */ +extern void *prio_queue_peek(struct prio_queue *); + extern void clear_prio_queue(struct prio_queue *); /* Reverse the LIFO elements */ diff --git a/t/helper/test-prio-queue.c b/t/helper/test-prio-queue.c index 9807b649b1..e817bbf464 100644 --- a/t/helper/test-prio-queue.c +++ b/t/helper/test-prio-queue.c @@ -22,9 +22,13 @@ int cmd__prio_queue(int argc, const char **argv) struct prio_queue pq = { intcmp }; while (*++argv) { - if (!strcmp(*argv, "get")) - show(prio_queue_get(&pq)); - else if (!strcmp(*argv, "dump")) { + if (!strcmp(*argv, "get")) { + void *peek = prio_queue_peek(&pq); + void *get = prio_queue_get(&pq); + if (peek != get) + BUG("peek and get results do not match"); + show(get); + } else if (!strcmp(*argv, "dump")) { int *v; while ((v = prio_queue_get(&pq))) show(v);