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 }