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