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