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
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 return NULL;
24
25 memcpy(item->priority, prio64be, sizeof(item->priority));
26 item->data = data;
27 item->next = NULL;
28 return item;
29 }
30
pitem_free(pitem * item)31 void pitem_free(pitem *item)
32 {
33 OPENSSL_free(item);
34 }
35
pqueue_new(void)36 pqueue *pqueue_new(void)
37 {
38 pqueue *pq = OPENSSL_zalloc(sizeof(*pq));
39
40 return pq;
41 }
42
pqueue_free(pqueue * pq)43 void pqueue_free(pqueue *pq)
44 {
45 OPENSSL_free(pq);
46 }
47
pqueue_insert(pqueue * pq,pitem * item)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
pqueue_peek(pqueue * pq)84 pitem *pqueue_peek(pqueue *pq)
85 {
86 return pq->items;
87 }
88
pqueue_pop(pqueue * pq)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
pqueue_find(pqueue * pq,unsigned char * prio64be)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
pqueue_iterator(pqueue * pq)124 pitem *pqueue_iterator(pqueue *pq)
125 {
126 return pqueue_peek(pq);
127 }
128
pqueue_next(piterator * item)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
pqueue_size(pqueue * pq)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