ssl/pqueue.c

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