1 /* 2 * Copyright 2005-2020 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the Apache License 2.0 (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_local.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 return NULL; 24 25 memcpy(item->priority, prio64be, sizeof(item->priority)); 26 item->data = data; 27 item->next = NULL; 28 return item; 29 } 30 31 void pitem_free(pitem *item) 32 { 33 OPENSSL_free(item); 34 } 35 36 pqueue *pqueue_new(void) 37 { 38 pqueue *pq = OPENSSL_zalloc(sizeof(*pq)); 39 40 return pq; 41 } 42 43 void pqueue_free(pqueue *pq) 44 { 45 OPENSSL_free(pq); 46 } 47 48 pitem *pqueue_insert(pqueue *pq, pitem *item) 49 { 50 pitem *curr, *next; 51 52 if (pq->items == NULL) { 53 pq->items = item; 54 return item; 55 } 56 57 for (curr = NULL, next = pq->items; 58 next != NULL; curr = next, next = next->next) { 59 /* 60 * we can compare 64-bit value in big-endian encoding with memcmp:-) 61 */ 62 int cmp = memcmp(next->priority, item->priority, 8); 63 if (cmp > 0) { /* next > item */ 64 item->next = next; 65 66 if (curr == NULL) 67 pq->items = item; 68 else 69 curr->next = item; 70 71 return item; 72 } 73 74 else if (cmp == 0) /* duplicates not allowed */ 75 return NULL; 76 } 77 78 item->next = NULL; 79 curr->next = item; 80 81 return item; 82 } 83 84 pitem *pqueue_peek(pqueue *pq) 85 { 86 return pq->items; 87 } 88 89 pitem *pqueue_pop(pqueue *pq) 90 { 91 pitem *item = pq->items; 92 93 if (pq->items != NULL) 94 pq->items = pq->items->next; 95 96 return item; 97 } 98 99 pitem *pqueue_find(pqueue *pq, unsigned char *prio64be) 100 { 101 pitem *next; 102 pitem *found = NULL; 103 104 if (pq->items == NULL) 105 return NULL; 106 107 for (next = pq->items; next->next != NULL; next = next->next) { 108 if (memcmp(next->priority, prio64be, 8) == 0) { 109 found = next; 110 break; 111 } 112 } 113 114 /* check the one last node */ 115 if (memcmp(next->priority, prio64be, 8) == 0) 116 found = next; 117 118 if (!found) 119 return NULL; 120 121 return found; 122 } 123 124 pitem *pqueue_iterator(pqueue *pq) 125 { 126 return pqueue_peek(pq); 127 } 128 129 pitem *pqueue_next(piterator *item) 130 { 131 pitem *ret; 132 133 if (item == NULL || *item == NULL) 134 return NULL; 135 136 /* *item != NULL */ 137 ret = *item; 138 *item = (*item)->next; 139 140 return ret; 141 } 142 143 size_t pqueue_size(pqueue *pq) 144 { 145 pitem *item = pq->items; 146 size_t count = 0; 147 148 while (item != NULL) { 149 count++; 150 item = item->next; 151 } 152 return count; 153 } 154