As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option.
Alternatively you can here view or download the uninterpreted source code file.

1 /* 2 * Copyright (C) 2007 François Pesce : francois.pesce (at) gmail (dot) com 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef NAPR_HEAP_H 18 #define NAPR_HEAP_H 19 20 typedef struct napr_heap_t napr_heap_t; 21 typedef int (napr_heap_cmp_callback_fn_t) (const void *, const void *); 22 typedef void (napr_heap_display_callback_fn_t) (const void *); 23 typedef void (napr_heap_del_callback_fn_t) (void *); 24 25 26 #ifdef HAVE_APR 27 #include <apr_pools.h> 28 /** 29 * Return the allocator associated to the heap, thus you can allow elements 30 * that will be automatically freed when the heap will be. 31 * @param heap The heap you are working with. 32 * @return Return a pointer to the allcator of type apr_pool_t. 33 */ 34 apr_pool_t *napr_heap_get_allocator(const napr_heap_t *heap); 35 /* APR_POOL_DECLARE_ACCESSOR(heap); */ 36 37 /** 38 * Make a new heap structure, a heap is a structure that is able to return the 39 * smallest (or highest, according to the way you compare data) element of its 40 * set, in a complexity of O(lg n) the same as the complexity to insert a 41 * random element. 42 * @param pool The associated pool. 43 * @param cmp The function that compare two elements to return the smallest. 44 * @return Return a pointer to a newly allocated heap NULL if an error occured. 45 */ 46 napr_heap_t *napr_heap_make(apr_pool_t *pool, napr_heap_cmp_callback_fn_t *cmp); 47 48 /** 49 * Re-entrant (Thread safe) version of napr_heap_make. 50 * @param pool The associated pool. 51 * @param cmp The function that compare two elements to return the smallest. 52 * @return Return a pointer to a newly allocated heap NULL if an error occured. 53 */ 54 napr_heap_t *napr_heap_make_r(apr_pool_t *pool, napr_heap_cmp_callback_fn_t *cmp); 55 56 #else /* !HAVE_APR */ 57 /** 58 * Make a new heap structure, a heap is a structure that is able to return the 59 * smallest (or highest, according to the way you compare data) element of its 60 * set, in a complexity of O(lg n) the same as the complexity to insert a 61 * random element. 62 * @param cmp The function that compare two elements to return the smallest. 63 * @param del The function that destroy (de-allocate) an element. 64 * @return Return a pointer to a newly allocated heap NULL if an error occured. 65 */ 66 napr_heap_t *napr_heap_make(napr_heap_cmp_callback_fn_t *cmp, napr_heap_del_callback_fn_t *del); 67 68 /** 69 * Re-entrant (Thread safe) version of napr_heap_make. 70 * @param cmp The function that compare two elements to return the smallest. 71 * @param del The function that destroy (de-allocate) an element. 72 * @return Return a pointer to a newly allocated heap NULL if an error occured. 73 */ 74 napr_heap_t *napr_heap_make_r(napr_heap_cmp_callback_fn_t *cmp, napr_heap_del_callback_fn_t *del); 75 #endif /* HAVE_APR */ 76 77 /** 78 * Deallocate the heap;(NB: if the heap is using apr_pool_t (HAVE_APR macro 79 * defined), then it will deallocate elements that have been allocated using 80 * the heap allocator, otherwise the function del is used on each element. 81 * @param heap The heap you are working with. 82 * @return nothing. 83 */ 84 void napr_heap_destroy(napr_heap_t *heap); 85 86 /** 87 * Insert an element in the heap. 88 * @param heap The heap you are working with. 89 * @param datum The datum you want to insert. 90 * @return 0 if no error occured, -1 otherwise. 91 */ 92 int napr_heap_insert(napr_heap_t *heap, void *datum); 93 94 /** 95 * Extract the highest (or the lowest using cmp function) element in the heap, 96 * remove it and return it. 97 * @param heap The heap you are working with. 98 * @return The highest (or lowest according to cmp function) element of the 99 * heap, NULL if the heap is empty. 100 */ 101 void *napr_heap_extract(napr_heap_t *heap); 102 103 /** 104 * Get the nth element element in the heap. 105 * @param heap The heap you are working with. 106 * @param n The index of the tree (take the nth element you encounter in a 107 * breadth first traversal of a binary tree) 108 * @return A pointer on the nth element of the heap, NULL if there's no 109 * such element. 110 * @remark if you modify the part of this element that is used in the 111 * comparation function, you're doing something really bad! 112 */ 113 void *napr_heap_get_nth(const napr_heap_t *heap, unsigned int n); 114 115 /** 116 * Get the nth element (to a const pointer because you can't extract it until 117 * it is the highest or the lowest using cmp function) element in the heap. 118 * @param heap The heap you are working with. 119 * @param datum The adress of the datum you want to set. 120 * @param n The index of the tree (take the nth element you encounter in a 121 * breadth first traversal of a binary tree) 122 * @return 0 if no error occured, -1 otherwise. 123 */ 124 unsigned int napr_heap_size(const napr_heap_t *heap); 125 126 /** 127 * Re-entrant (Thread safe) version of napr_heap_insert, heap must have been 128 * initialized with napr_heap_make_r. 129 * @param heap The heap you are working with. 130 * @param datum The datum you want to insert. 131 * @return 0 if no error occured, -1 otherwise. 132 */ 133 int napr_heap_insert_r(napr_heap_t *heap, void *datum); 134 135 /** 136 * Re-entrant (Thread safe) version of napr_heap_extract, heap must have been 137 * initialized with napr_heap_make_r. 138 * @param heap The heap you are working with. 139 * @return The highest (or lowest according to cmp function) element of the 140 * heap, NULL if the heap is empty. 141 */ 142 void *napr_heap_extract_r(napr_heap_t *heap); 143 144 /** 145 * Attach a callback to the heap in order to display the data stored. 146 * @param heap The heap you are working with. 147 * @param display A callback used to display content of a datum. 148 */ 149 void napr_heap_set_display_cb(napr_heap_t *heap, napr_heap_display_callback_fn_t display); 150 151 /** 152 * Display the binary tree using the display callback. 153 * @param heap The heap you are working with. 154 */ 155 void napr_heap_display(const napr_heap_t *heap); 156 #endif /* NAPR_HEAP_H */