granicus.if.org Git - esp-idf/blob - components/nghttp/library/nghttp2_pq.c

   1 /*
   2  * nghttp2 - HTTP/2 C Library
   3  *
   4  * Copyright (c) 2012 Tatsuhiro Tsujikawa
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining
   7  * a copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sublicense, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be
  15  * included in all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  18  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  19  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  20  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  21  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  22  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  23  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  24  */
  25 #include "nghttp2_pq.h"
  26
  27 #include <stdio.h>
  28 #include <assert.h>
  29
  30 #include "nghttp2_helper.h"
  31
  32 int nghttp2_pq_init(nghttp2_pq *pq, nghttp2_less less, nghttp2_mem *mem) {
  33   pq->mem = mem;
  34   pq->capacity = 0;
  35   pq->q = NULL;
  36   pq->length = 0;
  37   pq->less = less;
  38   return 0;
  39 }
  40
  41 void nghttp2_pq_free(nghttp2_pq *pq) {
  42   nghttp2_mem_free(pq->mem, pq->q);
  43   pq->q = NULL;
  44 }
  45
  46 static void swap(nghttp2_pq *pq, size_t i, size_t j) {
  47   nghttp2_pq_entry *a = pq->q[i];
  48   nghttp2_pq_entry *b = pq->q[j];
  49
  50   pq->q[i] = b;
  51   b->index = i;
  52   pq->q[j] = a;
  53   a->index = j;
  54 }
  55
  56 static void bubble_up(nghttp2_pq *pq, size_t index) {
  57   size_t parent;
  58   while (index != 0) {
  59     parent = (index - 1) / 2;
  60     if (!pq->less(pq->q[index], pq->q[parent])) {
  61       return;
  62     }
  63     swap(pq, parent, index);
  64     index = parent;
  65   }
  66 }
  67
  68 int nghttp2_pq_push(nghttp2_pq *pq, nghttp2_pq_entry *item) {
  69   if (pq->capacity <= pq->length) {
  70     void *nq;
  71     size_t ncapacity;
  72
  73     ncapacity = nghttp2_max(4, (pq->capacity * 2));
  74
  75     nq = nghttp2_mem_realloc(pq->mem, pq->q,
  76                              ncapacity * sizeof(nghttp2_pq_entry *));
  77     if (nq == NULL) {
  78       return NGHTTP2_ERR_NOMEM;
  79     }
  80     pq->capacity = ncapacity;
  81     pq->q = nq;
  82   }
  83   pq->q[pq->length] = item;
  84   item->index = pq->length;
  85   ++pq->length;
  86   bubble_up(pq, pq->length - 1);
  87   return 0;
  88 }
  89
  90 nghttp2_pq_entry *nghttp2_pq_top(nghttp2_pq *pq) {
  91   if (pq->length == 0) {
  92     return NULL;
  93   } else {
  94     return pq->q[0];
  95   }
  96 }
  97
  98 static void bubble_down(nghttp2_pq *pq, size_t index) {
  99   size_t i, j, minindex;
 100   for (;;) {
 101     j = index * 2 + 1;
 102     minindex = index;
 103     for (i = 0; i < 2; ++i, ++j) {
 104       if (j >= pq->length) {
 105         break;
 106       }
 107       if (pq->less(pq->q[j], pq->q[minindex])) {
 108         minindex = j;
 109       }
 110     }
 111     if (minindex == index) {
 112       return;
 113     }
 114     swap(pq, index, minindex);
 115     index = minindex;
 116   }
 117 }
 118
 119 void nghttp2_pq_pop(nghttp2_pq *pq) {
 120   if (pq->length > 0) {
 121     pq->q[0] = pq->q[pq->length - 1];
 122     pq->q[0]->index = 0;
 123     --pq->length;
 124     bubble_down(pq, 0);
 125   }
 126 }
 127
 128 void nghttp2_pq_remove(nghttp2_pq *pq, nghttp2_pq_entry *item) {
 129   assert(pq->q[item->index] == item);
 130
 131   if (item->index == 0) {
 132     nghttp2_pq_pop(pq);
 133     return;
 134   }
 135
 136   if (item->index == pq->length - 1) {
 137     --pq->length;
 138     return;
 139   }
 140
 141   pq->q[item->index] = pq->q[pq->length - 1];
 142   pq->q[item->index]->index = item->index;
 143   --pq->length;
 144
 145   if (pq->less(item, pq->q[item->index])) {
 146     bubble_down(pq, item->index);
 147   } else {
 148     bubble_up(pq, item->index);
 149   }
 150 }
 151
 152 int nghttp2_pq_empty(nghttp2_pq *pq) { return pq->length == 0; }
 153
 154 size_t nghttp2_pq_size(nghttp2_pq *pq) { return pq->length; }
 155
 156 void nghttp2_pq_update(nghttp2_pq *pq, nghttp2_pq_item_cb fun, void *arg) {
 157   size_t i;
 158   int rv = 0;
 159   if (pq->length == 0) {
 160     return;
 161   }
 162   for (i = 0; i < pq->length; ++i) {
 163     rv |= (*fun)(pq->q[i], arg);
 164   }
 165   if (rv) {
 166     for (i = pq->length; i > 0; --i) {
 167       bubble_down(pq, i - 1);
 168     }
 169   }
 170 }
 171
 172 int nghttp2_pq_each(nghttp2_pq *pq, nghttp2_pq_item_cb fun, void *arg) {
 173   size_t i;
 174
 175   if (pq->length == 0) {
 176     return 0;
 177   }
 178   for (i = 0; i < pq->length; ++i) {
 179     if ((*fun)(pq->q[i], arg)) {
 180       return 1;
 181     }
 182   }
 183   return 0;
 184 }