ssl/pqueue.c

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