1/***************************************************************************//** 2 3Copyright (c) 2011, 2013, Oracle and/or its affiliates. All Rights Reserved. 4 5This program is free software; you can redistribute it and/or modify 6it under the terms of the GNU General Public License, version 2.0, 7as published by the Free Software Foundation. 8 9This program is also distributed with certain software (including 10but not limited to OpenSSL) that is licensed under separate terms, 11as designated in a particular file or component or in included license 12documentation. The authors of MySQL hereby grant you an additional 13permission to link the program and your derivative works with the 14separately licensed software that they have included with MySQL. 15 16This program is distributed in the hope that it will be useful, 17but WITHOUT ANY WARRANTY; without even the implied warranty of 18MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19GNU General Public License, version 2.0, for more details. 20 21You should have received a copy of the GNU General Public License along with 22this program; if not, write to the Free Software Foundation, Inc., 2351 Franklin Street, Suite 500, Boston, MA 02110-1335 USA 24 25*****************************************************************************/ 26 27/******************************************************************//** 28@file include/ut0bh.ic 29Binary min-heap implementation. 30 31Created 2011-01-15 by Sunny Bains 32*******************************************************/ 33 34#include "ut0bh.h" 35#include "ut0mem.h" /* For ut_memcpy() */ 36 37/**********************************************************************//** 38Get the number of elements in the binary heap. 39@return number of elements */ 40UNIV_INLINE 41ulint 42ib_bh_size( 43/*=======*/ 44 const ib_bh_t* ib_bh) /*!< in: instance */ 45{ 46 return(ib_bh->n_elems); 47} 48 49/**********************************************************************//** 50Test if binary heap is empty. 51@return TRUE if empty. */ 52UNIV_INLINE 53ibool 54ib_bh_is_empty( 55/*===========*/ 56 const ib_bh_t* ib_bh) /*!< in: instance */ 57{ 58 return(ib_bh_size(ib_bh) == 0); 59} 60 61/**********************************************************************//** 62Test if binary heap is full. 63@return TRUE if full. */ 64UNIV_INLINE 65ibool 66ib_bh_is_full( 67/*===========*/ 68 const ib_bh_t* ib_bh) /*!< in: instance */ 69{ 70 return(ib_bh_size(ib_bh) >= ib_bh->max_elems); 71} 72 73/**********************************************************************//** 74Get a pointer to the element. 75@return pointer to element */ 76UNIV_INLINE 77void* 78ib_bh_get( 79/*=======*/ 80 ib_bh_t* ib_bh, /*!< in: instance */ 81 ulint i) /*!< in: index */ 82{ 83 byte* ptr = (byte*) (ib_bh + 1); 84 85 ut_a(i < ib_bh_size(ib_bh)); 86 87 return(ptr + (ib_bh->sizeof_elem * i)); 88} 89 90/**********************************************************************//** 91Copy an element to the binary heap. 92@return pointer to copied element */ 93UNIV_INLINE 94void* 95ib_bh_set( 96/*======*/ 97 ib_bh_t* ib_bh, /*!< in/out: instance */ 98 ulint i, /*!< in: index */ 99 const void* elem) /*!< in: element to add */ 100{ 101 void* ptr = ib_bh_get(ib_bh, i); 102 103 ut_memcpy(ptr, elem, ib_bh->sizeof_elem); 104 105 return(ptr); 106} 107 108/**********************************************************************//** 109Return the first element from the binary heap. 110@return pointer to first element or NULL if empty. */ 111UNIV_INLINE 112void* 113ib_bh_first( 114/*========*/ 115 ib_bh_t* ib_bh) /*!< in: instance */ 116{ 117 return(ib_bh_is_empty(ib_bh) ? NULL : ib_bh_get(ib_bh, 0)); 118} 119 120/**********************************************************************//** 121Return the last element from the binary heap. 122@return pointer to last element or NULL if empty. */ 123UNIV_INLINE 124void* 125ib_bh_last( 126/*========*/ 127 ib_bh_t* ib_bh) /*!< in/out: instance */ 128{ 129 return(ib_bh_is_empty(ib_bh) 130 ? NULL 131 : ib_bh_get(ib_bh, ib_bh_size(ib_bh) - 1)); 132} 133 134