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