1 | /* |
2 | * Copyright 2005-2018 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 | 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 | |