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