Add tests for pqueue

Reorder the tests in all_tests.sh to be in alphabetical order.

Change-Id: Idc6df6ab4a25709312a6f58635061bb643582c70
Reviewed-on: https://boringssl-review.googlesource.com/1680
Reviewed-by: Adam Langley <agl@google.com>

3 files changed, 105 insertions, 7 deletions

diff --git a/ssl/pqueue/CMakeLists.txt b/ssl/pqueue/CMakeLists.txt
index 58963ffc..60493505 100644
--- a/ssl/pqueue/CMakeLists.txt
+++ b/ssl/pqueue/CMakeLists.txt
@@ -7,3 +7,11 @@ add_library(
 
 	pqueue.c
 )
+
+add_executable(
+	pqueue_test
+
+	pqueue_test.c
+)
+
+target_link_libraries(pqueue_test ssl)
diff --git a/ssl/pqueue/pqueue.c b/ssl/pqueue/pqueue.c
index 4c68cb1f..4c94355c 100644
--- a/ssl/pqueue/pqueue.c
+++ b/ssl/pqueue/pqueue.c
@@ -111,7 +111,7 @@ pitem *pqueue_find(pqueue_s *pq, uint8_t *prio64be) {
   pitem *curr;
 
   for (curr = pq->items; curr; curr = curr->next) {
-    if (memcmp(curr->priority, prio64be, 8) == 0) {
+    if (memcmp(curr->priority, prio64be, sizeof(curr->priority)) == 0) {
       return curr;
     }
   }
@@ -130,9 +130,9 @@ size_t pqueue_size(pqueue_s *pq) {
   return count;
 }
 
-pitem *pqueue_iterator(pqueue_s *pq) { return pq->items; }
+piterator pqueue_iterator(pqueue_s *pq) { return pq->items; }
 
-pitem *pqueue_next(pitem **item) {
+pitem *pqueue_next(piterator *item) {
   pitem *ret;
 
   if (item == NULL || *item == NULL) {
@@ -156,9 +156,9 @@ pitem *pqueue_insert(pqueue_s *pq, pitem *item) {
   for (curr = NULL, next = pq->items; next != NULL;
        curr = next, next = next->next) {
     /* we can compare 64-bit value in big-endian encoding with memcmp. */
-    int cmp = memcmp(next->priority, item->priority, 8);
-    if (cmp > 0) /* next > item */
-    {
+    int cmp = memcmp(next->priority, item->priority, sizeof(item->priority));
+    if (cmp > 0) {
+      /* next > item */
       item->next = next;
 
       if (curr == NULL) {
@@ -168,8 +168,10 @@ pitem *pqueue_insert(pqueue_s *pq, pitem *item) {
       }
 
       return item;
-    } else if (cmp == 0) /* duplicates not allowed */
+    } else if (cmp == 0) {
+      /* duplicates not allowed */
       return NULL;
+    }
   }
 
   item->next = NULL;
diff --git a/ssl/pqueue/pqueue_test.c b/ssl/pqueue/pqueue_test.c
new file mode 100644
index 00000000..112afedf
--- /dev/null
+++ b/ssl/pqueue/pqueue_test.c
@@ -0,0 +1,88 @@
+/* Copyright (c) 2014, Google Inc.
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
+
+#include <stdio.h>
+#include <string.h>
+
+#include <openssl/pqueue.h>
+
+
+static int trivial() {
+  pqueue q = pqueue_new();
+  if (q == NULL) {
+    return 0;
+  }
+  int32_t data = 0xdeadbeef;
+  uint8_t priority[8] = {0};
+  pitem *item = pitem_new(priority, &data);
+  if (item == NULL ||
+      pqueue_insert(q, item) != item ||
+      pqueue_size(q) != 1 ||
+      pqueue_peek(q) != item ||
+      pqueue_pop(q) != item ||
+      pqueue_size(q) != 0 ||
+      pqueue_pop(q) != NULL) {
+    return 0;
+  }
+  pitem_free(item);
+  pqueue_free(q);
+  return 1;
+}
+
+#define NUM_ITEMS 10
+
+static int fixed_random() {
+  /* Random order of 10 elements, chosen by
+     random.choice(list(itertools.permutations(range(10)))) */
+  int ordering[NUM_ITEMS] = {9, 6, 3, 4, 0, 2, 7, 1, 8, 5};
+  int i;
+  pqueue q = pqueue_new();
+  if (q == NULL) {
+    return 0;
+  }
+  uint8_t priority[8] = {0};
+  /* Insert the elements */
+  for (i = 0; i < NUM_ITEMS; i++) {
+    priority[7] = ordering[i];
+    pitem *item = pitem_new(priority, &ordering[i]);
+    pqueue_insert(q, item);
+  }
+  piterator iter = pqueue_iterator(q);
+  pitem *curr = pqueue_next(&iter);
+  if (curr == NULL) {
+    return 0;
+  }
+  while (1) {
+    pitem *next = pqueue_next(&iter);
+    if (next == NULL) {
+      break;
+    }
+    int *curr_data = (int*)curr->data;
+    int *next_data = (int*)next->data;
+    if (*curr_data >= *next_data) {
+      return 0;
+    }
+    curr = next;
+  }
+  return 1;
+}
+
+int main(void) {
+  if (!trivial() || !fixed_random()) {
+    return 1;
+  }
+
+  printf("PASS\n");
+  return 0;
+}