1d9e397b599b13d642138480a28c14db7a136bf0Adam Langley/* Copyright (c) 2014, Google Inc. 2d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 3d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Permission to use, copy, modify, and/or distribute this software for any 4d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * purpose with or without fee is hereby granted, provided that the above 5d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * copyright notice and this permission notice appear in all copies. 6d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 7d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 8d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 9d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 10d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 11d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION 12d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 13d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ 14d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 15d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include <stdio.h> 16d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include <string.h> 17d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 18d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include <openssl/pqueue.h> 19d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include <openssl/ssl.h> 20d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 21d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 22e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langleystatic void clear_and_free_queue(pqueue q) { 23e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley for (;;) { 24e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley pitem *item = pqueue_pop(q); 25e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (item == NULL) { 26e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley break; 27e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 28e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley pitem_free(item); 29e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 30e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley pqueue_free(q); 31e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley} 32e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley 33d9e397b599b13d642138480a28c14db7a136bf0Adam Langleystatic int trivial(void) { 34d9e397b599b13d642138480a28c14db7a136bf0Adam Langley pqueue q = pqueue_new(); 35d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (q == NULL) { 36d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 37d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 38d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int32_t data = 0xdeadbeef; 39d9e397b599b13d642138480a28c14db7a136bf0Adam Langley uint8_t priority[8] = {0}; 40d9e397b599b13d642138480a28c14db7a136bf0Adam Langley pitem *item = pitem_new(priority, &data); 41d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (item == NULL || 42d9e397b599b13d642138480a28c14db7a136bf0Adam Langley pqueue_insert(q, item) != item || 43d9e397b599b13d642138480a28c14db7a136bf0Adam Langley pqueue_size(q) != 1 || 44d9e397b599b13d642138480a28c14db7a136bf0Adam Langley pqueue_peek(q) != item || 45d9e397b599b13d642138480a28c14db7a136bf0Adam Langley pqueue_pop(q) != item || 46d9e397b599b13d642138480a28c14db7a136bf0Adam Langley pqueue_size(q) != 0 || 47d9e397b599b13d642138480a28c14db7a136bf0Adam Langley pqueue_pop(q) != NULL) { 48d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 49d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 50d9e397b599b13d642138480a28c14db7a136bf0Adam Langley pitem_free(item); 51e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley clear_and_free_queue(q); 52d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 53d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 54d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 55d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#define NUM_ITEMS 10 56d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 57d9e397b599b13d642138480a28c14db7a136bf0Adam Langleystatic int fixed_random(void) { 58d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Random order of 10 elements, chosen by 59d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * random.choice(list(itertools.permutations(range(10)))) */ 60d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int ordering[NUM_ITEMS] = {9, 6, 3, 4, 0, 2, 7, 1, 8, 5}; 61d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int i; 62d9e397b599b13d642138480a28c14db7a136bf0Adam Langley pqueue q = pqueue_new(); 63d9e397b599b13d642138480a28c14db7a136bf0Adam Langley uint8_t priority[8] = {0}; 64d9e397b599b13d642138480a28c14db7a136bf0Adam Langley piterator iter; 65d9e397b599b13d642138480a28c14db7a136bf0Adam Langley pitem *curr, *item; 66d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 67d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (q == NULL) { 68d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 69d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 70d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 71d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Insert the elements */ 72d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (i = 0; i < NUM_ITEMS; i++) { 73d9e397b599b13d642138480a28c14db7a136bf0Adam Langley priority[7] = ordering[i]; 74d9e397b599b13d642138480a28c14db7a136bf0Adam Langley item = pitem_new(priority, &ordering[i]); 7553b272a2813a0b11f107d77100ff8805ada8fbd2Adam Langley if (item == NULL || pqueue_insert(q, item) != item) { 76d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 77d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 78d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 79d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 80d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Insert the elements again. This inserts duplicates and should 81d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * fail. */ 82d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (i = 0; i < NUM_ITEMS; i++) { 83d9e397b599b13d642138480a28c14db7a136bf0Adam Langley priority[7] = ordering[i]; 84d9e397b599b13d642138480a28c14db7a136bf0Adam Langley item = pitem_new(priority, &ordering[i]); 8553b272a2813a0b11f107d77100ff8805ada8fbd2Adam Langley if (item == NULL || pqueue_insert(q, item) != NULL) { 86d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 87d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 88d9e397b599b13d642138480a28c14db7a136bf0Adam Langley pitem_free(item); 89d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 90d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 91d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (pqueue_size(q) != NUM_ITEMS) { 92d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 93d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 94d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 95d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Iterate over the elements. */ 96d9e397b599b13d642138480a28c14db7a136bf0Adam Langley iter = pqueue_iterator(q); 97d9e397b599b13d642138480a28c14db7a136bf0Adam Langley curr = pqueue_next(&iter); 98d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (curr == NULL) { 99d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 100d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 101d9e397b599b13d642138480a28c14db7a136bf0Adam Langley while (1) { 102d9e397b599b13d642138480a28c14db7a136bf0Adam Langley pitem *next = pqueue_next(&iter); 103d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int *curr_data, *next_data; 104d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 105d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (next == NULL) { 106d9e397b599b13d642138480a28c14db7a136bf0Adam Langley break; 107d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 108d9e397b599b13d642138480a28c14db7a136bf0Adam Langley curr_data = (int*)curr->data; 109d9e397b599b13d642138480a28c14db7a136bf0Adam Langley next_data = (int*)next->data; 110d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (*curr_data >= *next_data) { 111d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 112d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 113d9e397b599b13d642138480a28c14db7a136bf0Adam Langley curr = next; 114d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 115e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley clear_and_free_queue(q); 116d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 117d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 118d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 119d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint main(void) { 120d9e397b599b13d642138480a28c14db7a136bf0Adam Langley SSL_library_init(); 121d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 122d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!trivial() || !fixed_random()) { 123d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 124d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 125d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 126d9e397b599b13d642138480a28c14db7a136bf0Adam Langley printf("PASS\n"); 127d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 128d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 129