1 /* 2 * Copyright 2005-2018 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the OpenSSL license (the "License"). You may not use 5 * this file except in compliance with the License. You can obtain a copy 6 * in the file LICENSE in the source distribution or at 7 * https://www.openssl.org/source/license.html 8 */ 9 10 #include "ssl_locl.h" 11 #include <openssl/bn.h> 12 13 struct pqueue_st { 14 pitem *items; 15 int count; 16 }; 17 18 pitem *pitem_new(unsigned char *prio64be, void *data) 19 { 20 pitem *item = OPENSSL_malloc(sizeof(*item)); 21 22 if (item == NULL) { 23 SSLerr(SSL_F_PITEM_NEW, ERR_R_MALLOC_FAILURE); 24 return NULL; 25 } 26 27 memcpy(item->priority, prio64be, sizeof(item->priority)); 28 item->data = data; 29 item->next = NULL; 30 return item; 31 } 32 33 void pitem_free(pitem *item) 34 { 35 OPENSSL_free(item); 36 } 37 38 pqueue *pqueue_new(void) 39 { 40 pqueue *pq = OPENSSL_zalloc(sizeof(*pq)); 41 42 if (pq == NULL) 43 SSLerr(SSL_F_PQUEUE_NEW, ERR_R_MALLOC_FAILURE); 44 45 return pq; 46 } 47 48 void pqueue_free(pqueue *pq) 49 { 50 OPENSSL_free(pq); 51 } 52 53 pitem *pqueue_insert(pqueue *pq, pitem *item) 54 { 55 pitem *curr, *next; 56 57 if (pq->items == NULL) { 58 pq->items = item; 59 return item; 60 } 61 62 for (curr = NULL, next = pq->items; 63 next != NULL; curr = next, next = next->next) { 64 /* 65 * we can compare 64-bit value in big-endian encoding with memcmp:-) 66 */ 67 int cmp = memcmp(next->priority, item->priority, 8); 68 if (cmp > 0) { /* next > item */ 69 item->next = next; 70 71 if (curr == NULL) 72 pq->items = item; 73 else 74 curr->next = item; 75 76 return item; 77 } 78 79 else if (cmp == 0) /* duplicates not allowed */ 80 return NULL; 81 } 82 83 item->next = NULL; 84 curr->next = item; 85 86 return item; 87 } 88 89 pitem *pqueue_peek(pqueue *pq) 90 { 91 return pq->items; 92 } 93 94 pitem *pqueue_pop(pqueue *pq) 95 { 96 pitem *item = pq->items; 97 98 if (pq->items != NULL) 99 pq->items = pq->items->next; 100 101 return item; 102 } 103 104 pitem *pqueue_find(pqueue *pq, unsigned char *prio64be) 105 { 106 pitem *next; 107 pitem *found = NULL; 108 109 if (pq->items == NULL) 110 return NULL; 111 112 for (next = pq->items; next->next != NULL; next = next->next) { 113 if (memcmp(next->priority, prio64be, 8) == 0) { 114 found = next; 115 break; 116 } 117 } 118 119 /* check the one last node */ 120 if (memcmp(next->priority, prio64be, 8) == 0) 121 found = next; 122 123 if (!found) 124 return NULL; 125 126 return found; 127 } 128 129 pitem *pqueue_iterator(pqueue *pq) 130 { 131 return pqueue_peek(pq); 132 } 133 134 pitem *pqueue_next(piterator *item) 135 { 136 pitem *ret; 137 138 if (item == NULL || *item == NULL) 139 return NULL; 140 141 /* *item != NULL */ 142 ret = *item; 143 *item = (*item)->next; 144 145 return ret; 146 } 147 148 size_t pqueue_size(pqueue *pq) 149 { 150 pitem *item = pq->items; 151 size_t count = 0; 152 153 while (item != NULL) { 154 count++; 155 item = item->next; 156 } 157 return count; 158 } 159