1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/ssl/libcrypto/src/crypto/pqueue/pqueue.c Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,236 @@
1.4 +/* crypto/pqueue/pqueue.c */
1.5 +/*
1.6 + * DTLS implementation written by Nagendra Modadugu
1.7 + * (nagendra@cs.stanford.edu) for the OpenSSL project 2005.
1.8 + */
1.9 +/* ====================================================================
1.10 + * Copyright (c) 1999-2005 The OpenSSL Project. All rights reserved.
1.11 + *
1.12 + * Redistribution and use in source and binary forms, with or without
1.13 + * modification, are permitted provided that the following conditions
1.14 + * are met:
1.15 + *
1.16 + * 1. Redistributions of source code must retain the above copyright
1.17 + * notice, this list of conditions and the following disclaimer.
1.18 + *
1.19 + * 2. Redistributions in binary form must reproduce the above copyright
1.20 + * notice, this list of conditions and the following disclaimer in
1.21 + * the documentation and/or other materials provided with the
1.22 + * distribution.
1.23 + *
1.24 + * 3. All advertising materials mentioning features or use of this
1.25 + * software must display the following acknowledgment:
1.26 + * "This product includes software developed by the OpenSSL Project
1.27 + * for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
1.28 + *
1.29 + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
1.30 + * endorse or promote products derived from this software without
1.31 + * prior written permission. For written permission, please contact
1.32 + * openssl-core@OpenSSL.org.
1.33 + *
1.34 + * 5. Products derived from this software may not be called "OpenSSL"
1.35 + * nor may "OpenSSL" appear in their names without prior written
1.36 + * permission of the OpenSSL Project.
1.37 + *
1.38 + * 6. Redistributions of any form whatsoever must retain the following
1.39 + * acknowledgment:
1.40 + * "This product includes software developed by the OpenSSL Project
1.41 + * for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
1.42 + *
1.43 + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
1.44 + * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.45 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
1.46 + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
1.47 + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1.48 + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
1.49 + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
1.50 + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
1.51 + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
1.52 + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
1.53 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
1.54 + * OF THE POSSIBILITY OF SUCH DAMAGE.
1.55 + * ====================================================================
1.56 + *
1.57 + * This product includes cryptographic software written by Eric Young
1.58 + * (eay@cryptsoft.com). This product includes software written by Tim
1.59 + * Hudson (tjh@cryptsoft.com).
1.60 + *
1.61 + */
1.62 +
1.63 +#include "cryptlib.h"
1.64 +#include <openssl/bn.h>
1.65 +#include <pqueue.h>
1.66 +
1.67 +typedef struct _pqueue
1.68 + {
1.69 + pitem *items;
1.70 + int count;
1.71 + } pqueue_s;
1.72 +
1.73 +EXPORT_C pitem *
1.74 +pitem_new(PQ_64BIT priority, void *data)
1.75 + {
1.76 + pitem *item = (pitem *) OPENSSL_malloc(sizeof(pitem));
1.77 + if (item == NULL) return NULL;
1.78 +
1.79 + pq_64bit_init(&(item->priority));
1.80 + pq_64bit_assign(&item->priority, &priority);
1.81 +
1.82 + item->data = data;
1.83 + item->next = NULL;
1.84 +
1.85 + return item;
1.86 + }
1.87 +
1.88 +EXPORT_C void
1.89 +pitem_free(pitem *item)
1.90 + {
1.91 + if (item == NULL) return;
1.92 +
1.93 + pq_64bit_free(&(item->priority));
1.94 + OPENSSL_free(item);
1.95 + }
1.96 +
1.97 +EXPORT_C pqueue_s *
1.98 +pqueue_new()
1.99 + {
1.100 + pqueue_s *pq = (pqueue_s *) OPENSSL_malloc(sizeof(pqueue_s));
1.101 + if (pq == NULL) return NULL;
1.102 +
1.103 + memset(pq, 0x00, sizeof(pqueue_s));
1.104 + return pq;
1.105 + }
1.106 +
1.107 +EXPORT_C void
1.108 +pqueue_free(pqueue_s *pq)
1.109 + {
1.110 + if (pq == NULL) return;
1.111 +
1.112 + OPENSSL_free(pq);
1.113 + }
1.114 +
1.115 +EXPORT_C pitem *
1.116 +pqueue_insert(pqueue_s *pq, pitem *item)
1.117 + {
1.118 + pitem *curr, *next;
1.119 +
1.120 + if (pq->items == NULL)
1.121 + {
1.122 + pq->items = item;
1.123 + return item;
1.124 + }
1.125 +
1.126 + for(curr = NULL, next = pq->items;
1.127 + next != NULL;
1.128 + curr = next, next = next->next)
1.129 + {
1.130 + if (pq_64bit_gt(&(next->priority), &(item->priority)))
1.131 + {
1.132 + item->next = next;
1.133 +
1.134 + if (curr == NULL)
1.135 + pq->items = item;
1.136 + else
1.137 + curr->next = item;
1.138 +
1.139 + return item;
1.140 + }
1.141 + /* duplicates not allowed */
1.142 + if (pq_64bit_eq(&(item->priority), &(next->priority)))
1.143 + return NULL;
1.144 + }
1.145 +
1.146 + item->next = NULL;
1.147 + curr->next = item;
1.148 +
1.149 + return item;
1.150 + }
1.151 +
1.152 +EXPORT_C pitem *
1.153 +pqueue_peek(pqueue_s *pq)
1.154 + {
1.155 + return pq->items;
1.156 + }
1.157 +
1.158 +EXPORT_C pitem *
1.159 +pqueue_pop(pqueue_s *pq)
1.160 + {
1.161 + pitem *item = pq->items;
1.162 +
1.163 + if (pq->items != NULL)
1.164 + pq->items = pq->items->next;
1.165 +
1.166 + return item;
1.167 + }
1.168 +
1.169 +EXPORT_C pitem *
1.170 +pqueue_find(pqueue_s *pq, PQ_64BIT priority)
1.171 + {
1.172 + pitem *next, *prev = NULL;
1.173 + pitem *found = NULL;
1.174 +
1.175 + if ( pq->items == NULL)
1.176 + return NULL;
1.177 +
1.178 + for ( next = pq->items; next->next != NULL;
1.179 + prev = next, next = next->next)
1.180 + {
1.181 + if ( pq_64bit_eq(&(next->priority), &priority))
1.182 + {
1.183 + found = next;
1.184 + break;
1.185 + }
1.186 + }
1.187 +
1.188 + /* check the one last node */
1.189 + if ( pq_64bit_eq(&(next->priority), &priority))
1.190 + found = next;
1.191 +
1.192 + if ( ! found)
1.193 + return NULL;
1.194 +
1.195 +#if 0 /* find works in peek mode */
1.196 + if ( prev == NULL)
1.197 + pq->items = next->next;
1.198 + else
1.199 + prev->next = next->next;
1.200 +#endif
1.201 +
1.202 + return found;
1.203 + }
1.204 +
1.205 +#if PQ_64BIT_IS_INTEGER
1.206 +EXPORT_C void
1.207 +pqueue_print(pqueue_s *pq)
1.208 + {
1.209 + pitem *item = pq->items;
1.210 +
1.211 + while(item != NULL)
1.212 + {
1.213 + printf("item\t" PQ_64BIT_PRINT "\n", item->priority);
1.214 + item = item->next;
1.215 + }
1.216 + }
1.217 +#endif
1.218 +
1.219 +EXPORT_C pitem *
1.220 +pqueue_iterator(pqueue_s *pq)
1.221 + {
1.222 + return pqueue_peek(pq);
1.223 + }
1.224 +
1.225 +EXPORT_C pitem *
1.226 +pqueue_next(pitem **item)
1.227 + {
1.228 + pitem *ret;
1.229 +
1.230 + if ( item == NULL || *item == NULL)
1.231 + return NULL;
1.232 +
1.233 +
1.234 + /* *item != NULL */
1.235 + ret = *item;
1.236 + *item = (*item)->next;
1.237 +
1.238 + return ret;
1.239 + }