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_local.h"
11 #include <openssl/bn.h>
12
13 struct pqueue_st {
14 pitem *items;
15 int count;
16 };
17
pitem_new(unsigned char * prio64be,void * data)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
pitem_free(pitem * item)33 void pitem_free(pitem *item)
34 {
35 OPENSSL_free(item);
36 }
37
pqueue_new(void)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
pqueue_free(pqueue * pq)48 void pqueue_free(pqueue *pq)
49 {
50 OPENSSL_free(pq);
51 }
52
pqueue_insert(pqueue * pq,pitem * item)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
pqueue_peek(pqueue * pq)89 pitem *pqueue_peek(pqueue *pq)
90 {
91 return pq->items;
92 }
93
pqueue_pop(pqueue * pq)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
pqueue_find(pqueue * pq,unsigned char * prio64be)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
pqueue_iterator(pqueue * pq)129 pitem *pqueue_iterator(pqueue *pq)
130 {
131 return pqueue_peek(pq);
132 }
133
pqueue_next(piterator * item)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
pqueue_size(pqueue * pq)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