1 /* 2 * nghttp3 3 * 4 * Copyright (c) 2019 nghttp3 contributors 5 * Copyright (c) 2017 ngtcp2 contributors 6 * Copyright (c) 2012 nghttp2 contributors 7 * 8 * Permission is hereby granted, free of charge, to any person obtaining 9 * a copy of this software and associated documentation files (the 10 * "Software"), to deal in the Software without restriction, including 11 * without limitation the rights to use, copy, modify, merge, publish, 12 * distribute, sublicense, and/or sell copies of the Software, and to 13 * permit persons to whom the Software is furnished to do so, subject to 14 * the following conditions: 15 * 16 * The above copyright notice and this permission notice shall be 17 * included in all copies or substantial portions of the Software. 18 * 19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 20 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 21 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 22 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 23 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 24 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 25 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 26 */ 27 #ifndef NGHTTP3_PQ_H 28 #define NGHTTP3_PQ_H 29 30 #ifdef HAVE_CONFIG_H 31 # include <config.h> 32 #endif /* HAVE_CONFIG_H */ 33 34 #include <nghttp3/nghttp3.h> 35 36 #include "nghttp3_mem.h" 37 38 /* Implementation of priority queue */ 39 40 /* NGHTTP3_PQ_BAD_INDEX is the priority queue index which indicates 41 that an entry is not queued. Assigning this value to 42 nghttp3_pq_entry.index can check that the entry is queued or not. */ 43 #define NGHTTP3_PQ_BAD_INDEX SIZE_MAX 44 45 typedef struct nghttp3_pq_entry { 46 size_t index; 47 } nghttp3_pq_entry; 48 49 /* "less" function, return nonzero if |lhs| is less than |rhs|. */ 50 typedef int (*nghttp3_less)(const nghttp3_pq_entry *lhs, 51 const nghttp3_pq_entry *rhs); 52 53 typedef struct nghttp3_pq { 54 /* The pointer to the pointer to the item stored */ 55 nghttp3_pq_entry **q; 56 /* Memory allocator */ 57 const nghttp3_mem *mem; 58 /* The number of items stored */ 59 size_t length; 60 /* The maximum number of items this pq can store. This is 61 automatically extended when length is reached to this value. */ 62 size_t capacity; 63 /* The less function between items */ 64 nghttp3_less less; 65 } nghttp3_pq; 66 67 /* 68 * Initializes priority queue |pq| with compare function |cmp|. 69 */ 70 void nghttp3_pq_init(nghttp3_pq *pq, nghttp3_less less, const nghttp3_mem *mem); 71 72 /* 73 * Deallocates any resources allocated for |pq|. The stored items are 74 * not freed by this function. 75 */ 76 void nghttp3_pq_free(nghttp3_pq *pq); 77 78 /* 79 * Adds |item| to the priority queue |pq|. 80 * 81 * This function returns 0 if it succeeds, or one of the following 82 * negative error codes: 83 * 84 * NGHTTP3_ERR_NOMEM 85 * Out of memory. 86 */ 87 int nghttp3_pq_push(nghttp3_pq *pq, nghttp3_pq_entry *item); 88 89 /* 90 * Returns item at the top of the queue |pq|. It is undefined if the 91 * queue is empty. 92 */ 93 nghttp3_pq_entry *nghttp3_pq_top(const nghttp3_pq *pq); 94 95 /* 96 * Pops item at the top of the queue |pq|. The popped item is not 97 * freed by this function. 98 */ 99 void nghttp3_pq_pop(nghttp3_pq *pq); 100 101 /* 102 * Returns nonzero if the queue |pq| is empty. 103 */ 104 int nghttp3_pq_empty(const nghttp3_pq *pq); 105 106 /* 107 * Returns the number of items in the queue |pq|. 108 */ 109 size_t nghttp3_pq_size(const nghttp3_pq *pq); 110 111 typedef int (*nghttp3_pq_item_cb)(nghttp3_pq_entry *item, void *arg); 112 113 /* 114 * Applies |fun| to each item in |pq|. The |arg| is passed as arg 115 * parameter to callback function. This function must not change the 116 * ordering key. If the return value from callback is nonzero, this 117 * function returns 1 immediately without iterating remaining items. 118 * Otherwise this function returns 0. 119 */ 120 int nghttp3_pq_each(const nghttp3_pq *pq, nghttp3_pq_item_cb fun, void *arg); 121 122 /* 123 * Removes |item| from priority queue. 124 */ 125 void nghttp3_pq_remove(nghttp3_pq *pq, nghttp3_pq_entry *item); 126 127 void nghttp3_pq_clear(nghttp3_pq *pq); 128 129 #endif /* NGHTTP3_PQ_H */ 130