binary_heap.h (7382B)
1 /* Copyright (C) 2013-2023, 2025 Vincent Forest (vaplv@free.fr) 2 * 3 * The RSys library is free software: you can redistribute it and/or modify 4 * it under the terms of the GNU General Public License as published 5 * by the Free Software Foundation, either version 3 of the License, or 6 * (at your option) any later version. 7 * 8 * The RSys library is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * GNU General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public License 14 * along with the RSys library. If not, see <http://www.gnu.org/licenses/>. */ 15 16 #if !defined(BHEAP_DATA) && !defined(BHEAP_NAME) 17 #ifndef BINARY_HEAP_H 18 #define BINARY_HEAP_H 19 20 #include "rsys.h" 21 #include "dynamic_array.h" 22 23 #endif /* BINARY_HEAP_H */ 24 #else 25 /* 26 * Generate the binary heap data type and functions with respect to the 27 * following macros: 28 * - BHEAP_NAME: prefix of the binary heap type and its functions; 29 * - BHEAP_DATA: type of the data registered into the binary heap; 30 * - BHEAP_FUNCTOR_COMPARE: comparison functor on binary heap data. Its 31 * profile is int (*)(const BHEAP_DATA* , const BHEAP_DATA* ). It returns 32 * an integer less than, equal to, or greater than zero if the first 33 * argument is considered to be sorted respectively before, at the same 34 * position, or after the second. If not defined the `<' operator is used 35 * to sort the BHEAP_DATA; 36 * - BHEAP_FUNCTOR_INIT: init functor on BHEAP_DATA. If not defined, no 37 * specific treatment is performed on the created data; 38 * - BHEAP_FUNCTOR_COPY: copy functor on DHEAP_DATA. If not defined a 39 * bitwise copy is used instead; 40 * - BHEAP_FUNCTOR_RELEASE: release functor on BHEAP_DATA. If not defined 41 * nothing is done on the release of an element; 42 * - BHEAP_FUNCTOR_COPY_AND_RELEASE: copy and release of a DHEAP_DATA. If 43 * not defined the copy and the release functors is used. 44 * 45 * The name of the generated type is: struct bheap_<BHEAP_NAME> 46 * while the generated functions are: bheap_<BHEAP_NAME>_<FUNCTION_NAME> 47 */ 48 #ifndef BHEAP_NAME 49 #error "Missing the BHEAP_NAME macro defining the structure name" 50 #endif 51 #ifndef BHEAP_DATA 52 #error "Missing the BHEAP_DATA macro defining the heap data type" 53 #endif 54 55 #define DARRAY_NAME CONCAT(BHEAP_NAME, __) 56 #define DARRAY_DATA BHEAP_DATA 57 #ifdef BHEAP_FUNCTOR_INIT 58 #define DARRAY_FUNCTOR_INIT BHEAP_FUNCTOR_INIT 59 #endif 60 #ifdef BHEAP_FUNCTOR_COPY 61 #define DARRAY_FUNCTOR_COPY BHEAP_FUNCTOR_COPY 62 #endif 63 #ifdef BHEAP_FUNCTOR_RELEASE 64 #define DARRAY_FUNCTOR_RELEASE BHEAP_FUNCTOR_RELEASE 65 #endif 66 #ifdef BHEAP_FUNCTOR_COPY_AND_RELEASE 67 #define DARRAY_FUNCTOR_COPY_AND_RELEASE BHEAP_FUNCTOR_COPY_AND_RELEASE 68 #endif 69 #include "dynamic_array.h" 70 71 /* Helper macros */ 72 #define BHEAP_FUNC__(Func) CONCAT(CONCAT(CONCAT(bheap_, BHEAP_NAME), _), Func) 73 #define BHEAP_TYPE__ CONCAT(bheap_, BHEAP_NAME) 74 #define BHEAP_NODES__ CONCAT(CONCAT(darray_, BHEAP_NAME), __) 75 #define BHEAP_NODES_FUNC__(Func) CONCAT(CONCAT(BHEAP_NODES__, _), Func) 76 77 struct BHEAP_TYPE__ { 78 struct BHEAP_NODES__ nodes; 79 }; 80 81 /******************************************************************************* 82 * Internal default functors 83 ******************************************************************************/ 84 #ifndef BHEAP_FUNCTOR_COMPARE 85 static FINLINE int 86 BHEAP_FUNC__(functor_cmp__)(const BHEAP_DATA* a, const BHEAP_DATA* b) 87 { 88 ASSERT(a && b); 89 if(*a < *b) return -1; 90 if(*a > *b) return 1; 91 return 0; 92 } 93 #define BHEAP_FUNCTOR_COMPARE BHEAP_FUNC__(functor_cmp__) 94 #endif 95 96 #ifndef BHEAP_FUNCTOR_COPY 97 #define BHEAP_FUNCTOR_COPY BHEAP_NODES_FUNC__(functor_cp__) 98 #endif 99 #ifndef BHEAP_FUNCTOR_INIT 100 #define BHEAP_FUNCTOR_INIT BHEAP_NODES_FUNC__(functor_init__) 101 #endif 102 #ifndef BHEAP_FUNCTOR_RELEASE 103 #define BHEAP_FUNCTOR_RELEASE BHEAP_NODES_FUNC__(functor_release__) 104 #endif 105 106 /******************************************************************************* 107 * Binary heap API 108 ******************************************************************************/ 109 static INLINE void 110 BHEAP_FUNC__(init) 111 (struct mem_allocator* allocator, /* May be NULL <=> use default allocator */ 112 struct BHEAP_TYPE__* heap) 113 { 114 ASSERT(heap); 115 BHEAP_NODES_FUNC__(init)(allocator, &heap->nodes); 116 } 117 118 static INLINE void 119 BHEAP_FUNC__(release)(struct BHEAP_TYPE__* heap) 120 { 121 ASSERT(heap); 122 BHEAP_NODES_FUNC__(release)(&heap->nodes); 123 } 124 125 static INLINE void 126 BHEAP_FUNC__(clear)(struct BHEAP_TYPE__* heap) 127 { 128 ASSERT(heap); 129 BHEAP_NODES_FUNC__(clear)(&heap->nodes); 130 } 131 132 static INLINE char 133 BHEAP_FUNC__(is_empty)(struct BHEAP_TYPE__* heap) 134 { 135 ASSERT(heap); 136 return BHEAP_NODES_FUNC__(size_get)(&heap->nodes) == 0; 137 } 138 139 static INLINE res_T 140 BHEAP_FUNC__(insert)(struct BHEAP_TYPE__* heap, const BHEAP_DATA* value) 141 { 142 BHEAP_DATA* nodes = NULL; 143 BHEAP_DATA tmp; 144 size_t inode = 0; 145 res_T res; 146 147 ASSERT(heap); 148 inode = BHEAP_NODES_FUNC__(size_get)(&heap->nodes); 149 150 res = BHEAP_NODES_FUNC__(push_back)(&heap->nodes, value); 151 if(res != RES_OK) 152 return res; 153 154 nodes = BHEAP_NODES_FUNC__(data_get)(&heap->nodes); 155 BHEAP_FUNCTOR_INIT(heap->nodes.allocator, &tmp); 156 while(inode) { 157 const size_t iparent = (inode - 1) / 2; 158 if(BHEAP_FUNCTOR_COMPARE(&nodes[iparent], &nodes[inode]) <= 0) 159 break; 160 161 BHEAP_FUNCTOR_COPY(&tmp, &nodes[iparent]); 162 BHEAP_FUNCTOR_COPY(&nodes[iparent], &nodes[inode]); 163 BHEAP_FUNCTOR_COPY(&nodes[inode], &tmp); 164 inode = iparent; 165 } 166 BHEAP_FUNCTOR_RELEASE(&tmp); 167 return RES_OK; 168 } 169 170 static INLINE char 171 BHEAP_FUNC__(top)(struct BHEAP_TYPE__* heap, BHEAP_DATA* top) 172 { 173 ASSERT(heap); 174 175 if(BHEAP_FUNC__(is_empty)(heap)) 176 return 0; 177 178 BHEAP_FUNCTOR_COPY(top, &BHEAP_NODES_FUNC__(data_get)(&heap->nodes)[0]); 179 return 1; 180 } 181 182 static INLINE char 183 BHEAP_FUNC__(pop)(struct BHEAP_TYPE__* heap, BHEAP_DATA* top) 184 { 185 BHEAP_DATA* nodes = NULL; 186 BHEAP_DATA tmp; 187 size_t size = 0; 188 size_t inode = 0; 189 size_t ichild = 0; 190 char res = 1; 191 ASSERT(heap); 192 193 BHEAP_FUNCTOR_INIT(heap->nodes.allocator, &tmp); 194 195 if(BHEAP_FUNC__(is_empty)(heap)) { 196 res = 0; 197 goto exit; 198 } 199 200 nodes = BHEAP_NODES_FUNC__(data_get)(&heap->nodes); 201 BHEAP_FUNCTOR_COPY(top, &nodes[0]); 202 inode = BHEAP_NODES_FUNC__(size_get)(&heap->nodes) - 1; 203 BHEAP_FUNCTOR_COPY(&tmp, &nodes[inode]); 204 BHEAP_NODES_FUNC__(pop_back)(&heap->nodes); 205 if(!inode) { 206 res = 1; 207 goto exit; 208 } 209 210 nodes = BHEAP_NODES_FUNC__(data_get)(&heap->nodes); 211 BHEAP_FUNCTOR_COPY(&nodes[0], &tmp); 212 size = inode; 213 for(inode=0, ichild=1; ichild < size; inode = ichild, ichild = 2*inode + 1) { 214 215 if(ichild + 1 < size 216 && BHEAP_FUNCTOR_COMPARE(&nodes[ichild], &nodes[ichild+1]) > 0) 217 ++ichild; 218 219 if(BHEAP_FUNCTOR_COMPARE(&nodes[inode], &nodes[ichild]) <= 0) 220 break; 221 222 BHEAP_FUNCTOR_COPY(&tmp, &nodes[inode]); 223 BHEAP_FUNCTOR_COPY(&nodes[inode], &nodes[ichild]); 224 BHEAP_FUNCTOR_COPY(&nodes[ichild], &tmp); 225 inode = ichild; 226 } 227 exit: 228 BHEAP_FUNCTOR_RELEASE(&tmp); 229 return res; 230 } 231 232 #undef BHEAP_NAME 233 #undef BHEAP_DATA 234 #undef BHEAP_FUNCTOR_COMPARE 235 #undef BHEAP_FUNCTOR_INIT 236 #undef BHEAP_FUNCTOR_COPY 237 #undef BHEAP_FUNCTOR_RELEASE 238 #undef BHEAP_FUNCTOR_COPY_AND_RELEASE 239 #undef BHEAP_FUNC__ 240 #undef BHEAP_TYPE__ 241 #undef BHEAP_NODES__ 242 #undef BHEAP_NODES_FUNC__ 243 244 #endif /* !BHEAP_NAME || !BHEAP_DATA */