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>
diff --git a/include/openssl/pqueue.h b/include/openssl/pqueue.h
index af6f7f1..eb0861e 100644
--- a/include/openssl/pqueue.h
+++ b/include/openssl/pqueue.h
@@ -111,7 +111,7 @@
/* pqueue_find returns the item whose priority matches |prio64be| or NULL if no
* such item exists. */
-pitem *pqueue_find(pqueue pq, unsigned char *prio64be);
+pitem *pqueue_find(pqueue pq, uint8_t *prio64be);
/* Queue mutation functions */
@@ -131,7 +131,7 @@
/* pqueue_iterator returns an iterator that can be used to iterate over the
* contents of the queue. */
-pitem *pqueue_iterator(pqueue pq);
+piterator pqueue_iterator(pqueue pq);
/* pqueue_next returns the current value of |iter| and advances it to the next
* position. If the iterator has advanced over all the elements, it returns
diff --git a/ssl/pqueue/CMakeLists.txt b/ssl/pqueue/CMakeLists.txt
index 58963ff..6049350 100644
--- a/ssl/pqueue/CMakeLists.txt
+++ b/ssl/pqueue/CMakeLists.txt
@@ -7,3 +7,11 @@
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 4c68cb1..4c94355 100644
--- a/ssl/pqueue/pqueue.c
+++ b/ssl/pqueue/pqueue.c
@@ -111,7 +111,7 @@
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 @@
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 @@
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 @@
}
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 0000000..112afed
--- /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;
+}
diff --git a/util/all_tests.sh b/util/all_tests.sh
index 43dd880..e4f3126 100644
--- a/util/all_tests.sh
+++ b/util/all_tests.sh
@@ -20,33 +20,34 @@
fi
TESTS="
-./crypto/cipher/aead_test aes-128-gcm $SRC/crypto/cipher/aes_128_gcm_tests.txt
-./crypto/cipher/aead_test aes-256-gcm $SRC/crypto/cipher/aes_256_gcm_tests.txt
-./crypto/cipher/aead_test chacha20-poly1305 $SRC/crypto/cipher/chacha20_poly1305_tests.txt
-./crypto/cipher/aead_test rc4-md5 $SRC/crypto/cipher/rc4_md5_tests.txt
-./crypto/cipher/aead_test aes-128-key-wrap $SRC/crypto/cipher/aes_128_key_wrap_tests.txt
-./crypto/cipher/aead_test aes-256-key-wrap $SRC/crypto/cipher/aes_256_key_wrap_tests.txt
./crypto/base64/base64_test
./crypto/bio/bio_test
./crypto/bn/bn_test
+./crypto/bytestring/bytestring_test
+./crypto/cipher/aead_test aes-128-gcm $SRC/crypto/cipher/aes_128_gcm_tests.txt
+./crypto/cipher/aead_test aes-128-key-wrap $SRC/crypto/cipher/aes_128_key_wrap_tests.txt
+./crypto/cipher/aead_test aes-256-gcm $SRC/crypto/cipher/aes_256_gcm_tests.txt
+./crypto/cipher/aead_test aes-256-key-wrap $SRC/crypto/cipher/aes_256_key_wrap_tests.txt
+./crypto/cipher/aead_test chacha20-poly1305 $SRC/crypto/cipher/chacha20_poly1305_tests.txt
+./crypto/cipher/aead_test rc4-md5 $SRC/crypto/cipher/rc4_md5_tests.txt
./crypto/cipher/cipher_test $SRC/crypto/cipher/cipher_test.txt
./crypto/dh/dh_test
./crypto/dsa/dsa_test
-./crypto/err/err_test
./crypto/ec/example_mul
./crypto/ecdsa/ecdsa_test
+./crypto/err/err_test
./crypto/evp/example_sign
./crypto/hmac/hmac_test
./crypto/lhash/lhash_test
./crypto/md5/md5_test
./crypto/modes/gcm_test
+./crypto/pkcs8/pkcs12_test
./crypto/rsa/rsa_test
./crypto/sha/sha1_test
+./crypto/x509/pkcs7_test
./crypto/x509v3/tab_test
./crypto/x509v3/v3name_test
-./crypto/bytestring/bytestring_test
-./crypto/x509/pkcs7_test
-./crypto/pkcs8/pkcs12_test
+./ssl/pqueue/pqueue_test
./ssl/ssl_test
"
