lib/nghttp2_pq.h

   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 #ifndef NGHTTP2_PQ_H
  26 #define NGHTTP2_PQ_H
  27
  28 #ifdef HAVE_CONFIG_H
  29 #include <config.h>
  30 #endif /* HAVE_CONFIG_H */
  31
  32 #include <nghttp2/nghttp2.h>
  33 #include "nghttp2_int.h"
  34 #include "nghttp2_mem.h"
  35
  36 /* Implementation of priority queue */
  37
  38 typedef struct {
  39   /* The pointer to the pointer to the item stored */
  40   void **q;
  41   /* Memory allocator */
  42   nghttp2_mem *mem;
  43   /* The number of items sotred */
  44   size_t length;
  45   /* The maximum number of items this pq can store. This is
  46      automatically extended when length is reached to this value. */
  47   size_t capacity;
  48   /* The compare function between items */
  49   nghttp2_compar compar;
  50 } nghttp2_pq;
  51
  52 /*
  53  * Initializes priority queue |pq| with compare function |cmp|.
  54  *
  55  * This function returns 0 if it succeeds, or one of the following
  56  * negative error codes:
  57  *
  58  * NGHTTP2_ERR_NOMEM
  59  *     Out of memory.
  60  */
  61 int nghttp2_pq_init(nghttp2_pq *pq, nghttp2_compar cmp, nghttp2_mem *mem);
  62
  63 /*
  64  * Deallocates any resources allocated for |pq|.  The stored items are
  65  * not freed by this function.
  66  */
  67 void nghttp2_pq_free(nghttp2_pq *pq);
  68
  69 /*
  70  * Adds |item| to the priority queue |pq|.
  71  *
  72  * This function returns 0 if it succeds, or one of the following
  73  * negative error codes:
  74  *
  75  * NGHTTP2_ERR_NOMEM
  76  *     Out of memory.
  77  */
  78 int nghttp2_pq_push(nghttp2_pq *pq, void *item);
  79
  80 /*
  81  * Returns item at the top of the queue |pq|. If the queue is empty,
  82  * this function returns NULL.
  83  */
  84 void *nghttp2_pq_top(nghttp2_pq *pq);
  85
  86 /*
  87  * Pops item at the top of the queue |pq|. The popped item is not
  88  * freed by this function.
  89  */
  90 void nghttp2_pq_pop(nghttp2_pq *pq);
  91
  92 /*
  93  * Returns nonzero if the queue |pq| is empty.
  94  */
  95 int nghttp2_pq_empty(nghttp2_pq *pq);
  96
  97 /*
  98  * Returns the number of items in the queue |pq|.
  99  */
 100 size_t nghttp2_pq_size(nghttp2_pq *pq);
 101
 102 typedef int (*nghttp2_pq_item_cb)(void *item, void *arg);
 103
 104 /*
 105  * Updates each item in |pq| using function |fun| and re-construct
 106  * priority queue. The |fun| must return non-zero if it modifies the
 107  * item in a way that it affects ordering in the priority queue. The
 108  * |arg| is passed to the 2nd parameter of |fun|.
 109  */
 110 void nghttp2_pq_update(nghttp2_pq *pq, nghttp2_pq_item_cb fun, void *arg);
 111
 112 #endif /* NGHTTP2_PQ_H */