1 /***************************************************************************//** 2 3 Copyright (c) 2011, 2013, Oracle Corpn. All Rights Reserved. 4 5 This program is free software; you can redistribute it and/or modify 6 it under the terms of the GNU General Public License, version 2.0, 7 as published by the Free Software Foundation. 8 9 This program is also distributed with certain software (including 10 but not limited to OpenSSL) that is licensed under separate terms, 11 as designated in a particular file or component or in included license 12 documentation. The authors of MySQL hereby grant you an additional 13 permission to link the program and your derivative works with the 14 separately licensed software that they have included with MySQL. 15 16 This program is distributed in the hope that it will be useful, 17 but WITHOUT ANY WARRANTY; without even the implied warranty of 18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19 GNU General Public License, version 2.0, for more details. 20 21 You should have received a copy of the GNU General Public License along with 22 this program; if not, write to the Free Software Foundation, Inc., 23 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA 24 25 *****************************************************************************/ 26 27 /******************************************************************//** 28 @file include/ut0bh.h 29 Binary min-heap interface. 30 31 Created 2010-05-28 by Sunny Bains 32 *******************************************************/ 33 34 #ifndef INNOBASE_UT0BH_H 35 #define INNOBASE_UT0BH_H 36 37 #include "univ.i" 38 39 /** Comparison function for objects in the binary heap. */ 40 typedef int (*ib_bh_cmp_t)(const void* p1, const void* p2); 41 42 struct ib_bh_t; 43 44 /**********************************************************************//** 45 Get the number of elements in the binary heap. 46 @return number of elements */ 47 UNIV_INLINE 48 ulint 49 ib_bh_size( 50 /*=======*/ 51 const ib_bh_t* ib_bh); /*!< in: instance */ 52 53 /**********************************************************************//** 54 Test if binary heap is empty. 55 @return TRUE if empty. */ 56 UNIV_INLINE 57 ibool 58 ib_bh_is_empty( 59 /*===========*/ 60 const ib_bh_t* ib_bh); /*!< in: instance */ 61 62 /**********************************************************************//** 63 Test if binary heap is full. 64 @return TRUE if full. */ 65 UNIV_INLINE 66 ibool 67 ib_bh_is_full( 68 /*===========*/ 69 const ib_bh_t* ib_bh); /*!< in: instance */ 70 71 /**********************************************************************//** 72 Get a pointer to the element. 73 @return pointer to element */ 74 UNIV_INLINE 75 void* 76 ib_bh_get( 77 /*=======*/ 78 ib_bh_t* ib_bh, /*!< in: instance */ 79 ulint i); /*!< in: index */ 80 81 /**********************************************************************//** 82 Copy an element to the binary heap. 83 @return pointer to copied element */ 84 UNIV_INLINE 85 void* 86 ib_bh_set( 87 /*======*/ 88 ib_bh_t* ib_bh, /*!< in/out: instance */ 89 ulint i, /*!< in: index */ 90 const void* elem); /*!< in: element to add */ 91 92 /**********************************************************************//** 93 Return the first element from the binary heap. 94 @return pointer to first element or NULL if empty. */ 95 UNIV_INLINE 96 void* 97 ib_bh_first( 98 /*========*/ 99 ib_bh_t* ib_bh); /*!< in: instance */ 100 101 /**********************************************************************//** 102 Return the last element from the binary heap. 103 @return pointer to last element or NULL if empty. */ 104 UNIV_INLINE 105 void* 106 ib_bh_last( 107 /*========*/ 108 ib_bh_t* ib_bh); /*!< in/out: instance */ 109 110 /**********************************************************************//** 111 Create a binary heap. 112 @return a new binary heap */ 113 UNIV_INTERN 114 ib_bh_t* 115 ib_bh_create( 116 /*=========*/ 117 ib_bh_cmp_t compare, /*!< in: comparator */ 118 ulint sizeof_elem, /*!< in: size of one element */ 119 ulint max_elems); /*!< in: max elements allowed */ 120 121 /**********************************************************************//** 122 Free a binary heap. 123 @return a new binary heap */ 124 UNIV_INTERN 125 void 126 ib_bh_free( 127 /*=======*/ 128 ib_bh_t* ib_bh); /*!< in,own: instance */ 129 130 /**********************************************************************//** 131 Add an element to the binary heap. Note: The element is copied. 132 @return pointer to added element or NULL if full. */ 133 UNIV_INTERN 134 void* 135 ib_bh_push( 136 /*=======*/ 137 ib_bh_t* ib_bh, /*!< in/out: instance */ 138 const void* elem); /*!< in: element to add */ 139 140 /**********************************************************************//** 141 Remove the first element from the binary heap. */ 142 UNIV_INTERN 143 void 144 ib_bh_pop( 145 /*======*/ 146 ib_bh_t* ib_bh); /*!< in/out: instance */ 147 148 /** Binary heap data structure */ 149 struct ib_bh_t { 150 ulint max_elems; /*!< max elements allowed */ 151 ulint n_elems; /*!< current size */ 152 ulint sizeof_elem; /*!< sizeof element */ 153 ib_bh_cmp_t compare; /*!< comparator */ 154 }; 155 156 #ifndef UNIV_NONINL 157 #include "ut0bh.ic" 158 #endif 159 160 #endif /* INNOBASE_UT0BH_H */ 161