ssl/pqueue.c

   1 /*
   2  * Copyright 2005-2017 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #include "ssl_locl.h"
  11 #include <openssl/bn.h>
  12
  13 struct pqueue_st {
  14     pitem *items;
  15     int count;
  16 };
  17
  18 pitem *pitem_new(unsigned char *prio64be, void *data)
  19 {
  20     pitem *item = OPENSSL_malloc(sizeof(*item));
  21     if (item == NULL)
  22         return NULL;
  23
  24     memcpy(item->priority, prio64be, sizeof(item->priority));
  25
  26     item->data = data;
  27     item->next = NULL;
  28
  29     return item;
  30 }
  31
  32 void pitem_free(pitem *item)
  33 {
  34     OPENSSL_free(item);
  35 }
  36
  37 pqueue *pqueue_new()
  38 {
  39     pqueue *pq = OPENSSL_zalloc(sizeof(*pq));
  40
  41     return pq;
  42 }
  43
  44 void pqueue_free(pqueue *pq)
  45 {
  46     OPENSSL_free(pq);
  47 }
  48
  49 pitem *pqueue_insert(pqueue *pq, pitem *item)
  50 {
  51     pitem *curr, *next;
  52
  53     if (pq->items == NULL) {
  54         pq->items = item;
  55         return item;
  56     }
  57
  58     for (curr = NULL, next = pq->items;
  59          next != NULL; curr = next, next = next->next) {
  60         /*
  61          * we can compare 64-bit value in big-endian encoding with memcmp:-)
  62          */
  63         int cmp = memcmp(next->priority, item->priority, 8);
  64         if (cmp > 0) {          /* next > item */
  65             item->next = next;
  66
  67             if (curr == NULL)
  68                 pq->items = item;
  69             else
  70                 curr->next = item;
  71
  72             return item;
  73         }
  74
  75         else if (cmp == 0)      /* duplicates not allowed */
  76             return NULL;
  77     }
  78
  79     item->next = NULL;
  80     curr->next = item;
  81
  82     return item;
  83 }
  84
  85 pitem *pqueue_peek(pqueue *pq)
  86 {
  87     return pq->items;
  88 }
  89
  90 pitem *pqueue_pop(pqueue *pq)
  91 {
  92     pitem *item = pq->items;
  93
  94     if (pq->items != NULL)
  95         pq->items = pq->items->next;
  96
  97     return item;
  98 }
  99
 100 pitem *pqueue_find(pqueue *pq, unsigned char *prio64be)
 101 {
 102     pitem *next;
 103     pitem *found = NULL;
 104
 105     if (pq->items == NULL)
 106         return NULL;
 107
 108     for (next = pq->items; next->next != NULL; next = next->next) {
 109         if (memcmp(next->priority, prio64be, 8) == 0) {
 110             found = next;
 111             break;
 112         }
 113     }
 114
 115     /* check the one last node */
 116     if (memcmp(next->priority, prio64be, 8) == 0)
 117         found = next;
 118
 119     if (!found)
 120         return NULL;
 121
 122     return found;
 123 }
 124
 125 pitem *pqueue_iterator(pqueue *pq)
 126 {
 127     return pqueue_peek(pq);
 128 }
 129
 130 pitem *pqueue_next(piterator *item)
 131 {
 132     pitem *ret;
 133
 134     if (item == NULL || *item == NULL)
 135         return NULL;
 136
 137     /* *item != NULL */
 138     ret = *item;
 139     *item = (*item)->next;
 140
 141     return ret;
 142 }
 143
 144 size_t pqueue_size(pqueue *pq)
 145 {
 146     pitem *item = pq->items;
 147     size_t count = 0;
 148
 149     while (item != NULL) {
 150         count++;
 151         item = item->next;
 152     }
 153     return count;
 154 }