lib/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 int nghttp2_pq_init(nghttp2_pq *pq, nghttp2_compar compar, nghttp2_mem *mem) {
  28   pq->mem = mem;
  29   pq->capacity = 128;
  30   pq->q = nghttp2_mem_malloc(mem, pq->capacity * sizeof(void *));
  31   if (pq->q == NULL) {
  32     return NGHTTP2_ERR_NOMEM;
  33   }
  34   pq->length = 0;
  35   pq->compar = compar;
  36   return 0;
  37 }
  38
  39 void nghttp2_pq_free(nghttp2_pq *pq) {
  40   nghttp2_mem_free(pq->mem, pq->q);
  41   pq->q = NULL;
  42 }
  43
  44 static void swap(nghttp2_pq *pq, size_t i, size_t j) {
  45   void *t = pq->q[i];
  46   pq->q[i] = pq->q[j];
  47   pq->q[j] = t;
  48 }
  49
  50 static void bubble_up(nghttp2_pq *pq, size_t index) {
  51   if (index == 0) {
  52     return;
  53   } else {
  54     size_t parent = (index - 1) / 2;
  55     if (pq->compar(pq->q[parent], pq->q[index]) > 0) {
  56       swap(pq, parent, index);
  57       bubble_up(pq, parent);
  58     }
  59   }
  60 }
  61
  62 int nghttp2_pq_push(nghttp2_pq *pq, void *item) {
  63   if (pq->capacity <= pq->length) {
  64     void *nq;
  65     nq = nghttp2_mem_realloc(pq->mem, pq->q,
  66                              (pq->capacity * 2) * sizeof(void *));
  67     if (nq == NULL) {
  68       return NGHTTP2_ERR_NOMEM;
  69     }
  70     pq->capacity *= 2;
  71     pq->q = nq;
  72   }
  73   pq->q[pq->length] = item;
  74   ++pq->length;
  75   bubble_up(pq, pq->length - 1);
  76   return 0;
  77 }
  78
  79 void *nghttp2_pq_top(nghttp2_pq *pq) {
  80   if (pq->length == 0) {
  81     return NULL;
  82   } else {
  83     return pq->q[0];
  84   }
  85 }
  86
  87 static void bubble_down(nghttp2_pq *pq, size_t index) {
  88   size_t lchild = index * 2 + 1;
  89   size_t minindex = index;
  90   size_t i, j;
  91   for (i = 0; i < 2; ++i) {
  92     j = lchild + i;
  93     if (j >= pq->length) {
  94       break;
  95     }
  96     if (pq->compar(pq->q[minindex], pq->q[j]) > 0) {
  97       minindex = j;
  98     }
  99   }
 100   if (minindex != index) {
 101     swap(pq, index, minindex);
 102     bubble_down(pq, minindex);
 103   }
 104 }
 105
 106 void nghttp2_pq_pop(nghttp2_pq *pq) {
 107   if (pq->length > 0) {
 108     pq->q[0] = pq->q[pq->length - 1];
 109     --pq->length;
 110     bubble_down(pq, 0);
 111   }
 112 }
 113
 114 int nghttp2_pq_empty(nghttp2_pq *pq) { return pq->length == 0; }
 115
 116 size_t nghttp2_pq_size(nghttp2_pq *pq) { return pq->length; }
 117
 118 void nghttp2_pq_update(nghttp2_pq *pq, nghttp2_pq_item_cb fun, void *arg) {
 119   size_t i;
 120   int rv = 0;
 121   if (pq->length == 0) {
 122     return;
 123   }
 124   for (i = 0; i < pq->length; ++i) {
 125     rv |= (*fun)(pq->q[i], arg);
 126   }
 127   if (rv) {
 128     for (i = pq->length; i > 0; --i) {
 129       bubble_down(pq, i - 1);
 130     }
 131   }
 132 }