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