1 /* $OpenBSD: pqueue.c,v 1.5 2014/06/12 15:49:31 deraadt Exp $ */ 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 <stdlib.h> 61 #include <string.h> 62 63 #include "pqueue.h" 64 65 typedef struct _pqueue { 66 pitem *items; 67 int count; 68 } pqueue_s; 69 70 pitem * 71 pitem_new(unsigned char *prio64be, void *data) 72 { 73 pitem *item = malloc(sizeof(pitem)); 74 75 if (item == NULL) 76 return NULL; 77 78 memcpy(item->priority, prio64be, sizeof(item->priority)); 79 80 item->data = data; 81 item->next = NULL; 82 83 return item; 84 } 85 86 void 87 pitem_free(pitem *item) 88 { 89 free(item); 90 } 91 92 pqueue_s * 93 pqueue_new(void) 94 { 95 return calloc(1, sizeof(pqueue_s)); 96 } 97 98 void 99 pqueue_free(pqueue_s *pq) 100 { 101 free(pq); 102 } 103 104 pitem * 105 pqueue_insert(pqueue_s *pq, pitem *item) 106 { 107 pitem *curr, *next; 108 109 if (pq->items == NULL) { 110 pq->items = item; 111 return item; 112 } 113 114 for (curr = NULL, next = pq->items; next != NULL; 115 curr = next, next = next->next) { 116 /* we can compare 64-bit value in big-endian encoding 117 * with memcmp:-) */ 118 int cmp = memcmp(next->priority, item->priority, 119 sizeof(item->priority)); 120 if (cmp > 0) { /* next > item */ 121 item->next = next; 122 123 if (curr == NULL) 124 pq->items = item; 125 else 126 curr->next = item; 127 128 return item; 129 } else if (cmp == 0) /* duplicates not allowed */ 130 return NULL; 131 } 132 133 item->next = NULL; 134 curr->next = item; 135 136 return item; 137 } 138 139 pitem * 140 pqueue_peek(pqueue_s *pq) 141 { 142 return pq->items; 143 } 144 145 pitem * 146 pqueue_pop(pqueue_s *pq) 147 { 148 pitem *item = pq->items; 149 150 if (pq->items != NULL) 151 pq->items = pq->items->next; 152 153 return item; 154 } 155 156 pitem * 157 pqueue_find(pqueue_s *pq, unsigned char *prio64be) 158 { 159 pitem *next; 160 161 for (next = pq->items; next != NULL; next = next->next) 162 if (memcmp(next->priority, prio64be, 163 sizeof(next->priority)) == 0) 164 return next; 165 166 return NULL; 167 } 168 169 pitem * 170 pqueue_iterator(pqueue_s *pq) 171 { 172 return pqueue_peek(pq); 173 } 174 175 pitem * 176 pqueue_next(pitem **item) 177 { 178 pitem *ret; 179 180 if (item == NULL || *item == NULL) 181 return NULL; 182 183 /* *item != NULL */ 184 ret = *item; 185 *item = (*item)->next; 186 187 return ret; 188 } 189 190 int 191 pqueue_size(pqueue_s *pq) 192 { 193 pitem *item = pq->items; 194 int count = 0; 195 196 while (item != NULL) { 197 count++; 198 item = item->next; 199 } 200 return count; 201 } 202