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
13struct pqueue_st {
14    pitem *items;
15    int count;
16};
17
18pitem *pitem_new(unsigned char *prio64be, void *data)
19{
20    pitem *item = OPENSSL_malloc(sizeof(*item));
21
22    if (item == NULL) {
23        ERR_raise(ERR_LIB_SSL, 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
33void pitem_free(pitem *item)
34{
35    OPENSSL_free(item);
36}
37
38pqueue *pqueue_new(void)
39{
40    pqueue *pq = OPENSSL_zalloc(sizeof(*pq));
41
42    if (pq == NULL)
43        ERR_raise(ERR_LIB_SSL, ERR_R_MALLOC_FAILURE);
44
45    return pq;
46}
47
48void pqueue_free(pqueue *pq)
49{
50    OPENSSL_free(pq);
51}
52
53pitem *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
89pitem *pqueue_peek(pqueue *pq)
90{
91    return pq->items;
92}
93
94pitem *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
104pitem *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
129pitem *pqueue_iterator(pqueue *pq)
130{
131    return pqueue_peek(pq);
132}
133
134pitem *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
148size_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