Change the INSTALL documentation for unified builds
[openssl.git] / ssl / pqueue.c
1 /*
2  * DTLS implementation written by Nagendra Modadugu
3  * (nagendra@cs.stanford.edu) for the OpenSSL project 2005.
4  */
5 /* ====================================================================
6  * Copyright (c) 1999-2005 The OpenSSL Project.  All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * 1. Redistributions of source code must retain the above copyright
13  *    notice, this list of conditions and the following disclaimer.
14  *
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in
17  *    the documentation and/or other materials provided with the
18  *    distribution.
19  *
20  * 3. All advertising materials mentioning features or use of this
21  *    software must display the following acknowledgment:
22  *    "This product includes software developed by the OpenSSL Project
23  *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
24  *
25  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
26  *    endorse or promote products derived from this software without
27  *    prior written permission. For written permission, please contact
28  *    openssl-core@OpenSSL.org.
29  *
30  * 5. Products derived from this software may not be called "OpenSSL"
31  *    nor may "OpenSSL" appear in their names without prior written
32  *    permission of the OpenSSL Project.
33  *
34  * 6. Redistributions of any form whatsoever must retain the following
35  *    acknowledgment:
36  *    "This product includes software developed by the OpenSSL Project
37  *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
38  *
39  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
40  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
41  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
42  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
43  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
44  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
45  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
46  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
48  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
49  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
50  * OF THE POSSIBILITY OF SUCH DAMAGE.
51  * ====================================================================
52  *
53  * This product includes cryptographic software written by Eric Young
54  * (eay@cryptsoft.com).  This product includes software written by Tim
55  * Hudson (tjh@cryptsoft.com).
56  *
57  */
58
59 #include "ssl_locl.h"
60 #include <openssl/bn.h>
61
62 struct pqueue_st {
63     pitem *items;
64     int count;
65 };
66
67 pitem *pitem_new(unsigned char *prio64be, void *data)
68 {
69     pitem *item = OPENSSL_malloc(sizeof(*item));
70     if (item == NULL)
71         return NULL;
72
73     memcpy(item->priority, prio64be, sizeof(item->priority));
74
75     item->data = data;
76     item->next = NULL;
77
78     return item;
79 }
80
81 void pitem_free(pitem *item)
82 {
83     OPENSSL_free(item);
84 }
85
86 pqueue *pqueue_new()
87 {
88     pqueue *pq = OPENSSL_zalloc(sizeof(*pq));
89
90     return pq;
91 }
92
93 void pqueue_free(pqueue *pq)
94 {
95     OPENSSL_free(pq);
96 }
97
98 pitem *pqueue_insert(pqueue *pq, pitem *item)
99 {
100     pitem *curr, *next;
101
102     if (pq->items == NULL) {
103         pq->items = item;
104         return item;
105     }
106
107     for (curr = NULL, next = pq->items;
108          next != NULL; curr = next, next = next->next) {
109         /*
110          * we can compare 64-bit value in big-endian encoding with memcmp:-)
111          */
112         int cmp = memcmp(next->priority, item->priority, 8);
113         if (cmp > 0) {          /* next > item */
114             item->next = next;
115
116             if (curr == NULL)
117                 pq->items = item;
118             else
119                 curr->next = item;
120
121             return item;
122         }
123
124         else if (cmp == 0)      /* duplicates not allowed */
125             return NULL;
126     }
127
128     item->next = NULL;
129     curr->next = item;
130
131     return item;
132 }
133
134 pitem *pqueue_peek(pqueue *pq)
135 {
136     return pq->items;
137 }
138
139 pitem *pqueue_pop(pqueue *pq)
140 {
141     pitem *item = pq->items;
142
143     if (pq->items != NULL)
144         pq->items = pq->items->next;
145
146     return item;
147 }
148
149 pitem *pqueue_find(pqueue *pq, unsigned char *prio64be)
150 {
151     pitem *next;
152     pitem *found = NULL;
153
154     if (pq->items == NULL)
155         return NULL;
156
157     for (next = pq->items; next->next != NULL; next = next->next) {
158         if (memcmp(next->priority, prio64be, 8) == 0) {
159             found = next;
160             break;
161         }
162     }
163
164     /* check the one last node */
165     if (memcmp(next->priority, prio64be, 8) == 0)
166         found = next;
167
168     if (!found)
169         return NULL;
170
171     return found;
172 }
173
174 void pqueue_print(pqueue *pq)
175 {
176     pitem *item = pq->items;
177
178     while (item != NULL) {
179         printf("item\t%02x%02x%02x%02x%02x%02x%02x%02x\n",
180                item->priority[0], item->priority[1],
181                item->priority[2], item->priority[3],
182                item->priority[4], item->priority[5],
183                item->priority[6], item->priority[7]);
184         item = item->next;
185     }
186 }
187
188 pitem *pqueue_iterator(pqueue *pq)
189 {
190     return pqueue_peek(pq);
191 }
192
193 pitem *pqueue_next(pitem **item)
194 {
195     pitem *ret;
196
197     if (item == NULL || *item == NULL)
198         return NULL;
199
200     /* *item != NULL */
201     ret = *item;
202     *item = (*item)->next;
203
204     return ret;
205 }
206
207 int pqueue_size(pqueue *pq)
208 {
209     pitem *item = pq->items;
210     int count = 0;
211
212     while (item != NULL) {
213         count++;
214         item = item->next;
215     }
216     return count;
217 }