prio-queue: add 'peek' operation
authorDerrick Stolee <stolee@gmail.com>
Thu, 1 Nov 2018 13:46:17 +0000 (13:46 +0000)
committerJunio C Hamano <gitster@pobox.com>
Fri, 2 Nov 2018 03:14:21 +0000 (12:14 +0900)
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: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
prio-queue.c
prio-queue.h
t/helper/test-prio-queue.c
t/t0009-prio-queue.sh

index a078451..d3f488c 100644 (file)
@@ -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;
+}
index d030ec9..682e518 100644 (file)
@@ -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 */
index 9807b64..5bc9c46 100644 (file)
@@ -22,14 +22,24 @@ 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")) {
-                       int *v;
-                       while ((v = prio_queue_get(&pq)))
-                              show(v);
-               }
-               else {
+               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")) {
+                       void *peek;
+                       void *get;
+                       while ((peek = prio_queue_peek(&pq))) {
+                               get = prio_queue_get(&pq);
+                               if (peek != get)
+                                       BUG("peek and get results do not match");
+                               show(get);
+                       }
+               } else if (!strcmp(*argv, "stack")) {
+                       pq.compare = NULL;
+               } else {
                        int *v = malloc(sizeof(*v));
                        *v = atoi(*argv);
                        prio_queue_put(&pq, v);
index e56dfce..3941ad2 100755 (executable)
@@ -47,4 +47,18 @@ test_expect_success 'notice empty queue' '
        test_cmp expect actual
 '
 
+cat >expect <<'EOF'
+3
+2
+6
+4
+5
+1
+8
+EOF
+test_expect_success 'stack order' '
+       test-tool prio-queue stack 8 1 5 4 6 2 3 dump >actual &&
+       test_cmp expect actual
+'
+
 test_done