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
153
154
155
156
157
158
159
160
161
162
163
164
|
/***************************************************************************//**
Copyright (c) 2010, 2011, Oracle Corpn. All Rights Reserved.
Portions of this file contain modifications contributed and copyrighted by
Sun Microsystems, Inc. Those modifications are gratefully acknowledged and
are described briefly in the InnoDB documentation. The contributions by
Sun Microsystems are incorporated with their permission, and subject to the
conditions contained in the file COPYING.Sun_Microsystems.
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 St, Fifth Floor, Boston, MA 02110-1335 USA
*****************************************************************************/
/******************************************************************//**
@file ut/ut0bh.c
Binary min-heap implementation.
Created 2010-05-28 by Sunny Bains
*******************************************************/
#include "ut0bh.h"
#include "ut0mem.h"
#ifdef UNIV_NONINL
#include "ut0bh.ic"
#endif
#include <string.h>
/**********************************************************************//**
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 */
{
ulint sz;
ib_bh_t* ib_bh;
sz = sizeof(*ib_bh) + (sizeof_elem * max_elems);
ib_bh = (ib_bh_t*) ut_malloc(sz);
memset(ib_bh, 0x0, sz);
ib_bh->compare = compare;
ib_bh->max_elems = max_elems;
ib_bh->sizeof_elem = sizeof_elem;
return(ib_bh);
}
/**********************************************************************//**
Free a binary heap.
@return a new binary heap */
UNIV_INTERN
void
ib_bh_free(
/*=======*/
ib_bh_t* ib_bh) /*!< in/own: instance */
{
ut_free(ib_bh);
}
/**********************************************************************//**
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 */
{
void* ptr;
if (ib_bh_is_full(ib_bh)) {
return(NULL);
} else if (ib_bh_is_empty(ib_bh)) {
++ib_bh->n_elems;
return(ib_bh_set(ib_bh, 0, elem));
} else {
ulint i;
i = ib_bh->n_elems;
++ib_bh->n_elems;
for (ptr = ib_bh_get(ib_bh, i >> 1);
i > 0 && ib_bh->compare(ptr, elem) > 0;
i >>= 1, ptr = ib_bh_get(ib_bh, i >> 1)) {
ib_bh_set(ib_bh, i, ptr);
}
ptr = ib_bh_set(ib_bh, i, elem);
}
return(ptr);
}
/**********************************************************************//**
Remove the first element from the binary heap. */
UNIV_INTERN
void
ib_bh_pop(
/*======*/
ib_bh_t* ib_bh) /*!< in/out: instance */
{
byte* ptr;
byte* last;
ulint parent = 0;
if (ib_bh_is_empty(ib_bh)) {
return;
} else if (ib_bh_size(ib_bh) == 1) {
--ib_bh->n_elems;
return;
}
last = (byte*) ib_bh_last(ib_bh);
/* Start from the child node */
ptr = (byte*) ib_bh_get(ib_bh, 1);
while (ptr < last) {
/* If the "right" child node is < "left" child node */
if (ib_bh->compare(ptr + ib_bh->sizeof_elem, ptr) < 0) {
ptr += ib_bh->sizeof_elem;
}
if (ib_bh->compare(last, ptr) <= 0) {
break;
}
ib_bh_set(ib_bh, parent, ptr);
parent = (ptr - (byte*) ib_bh_first(ib_bh))
/ ib_bh->sizeof_elem;
if ((parent << 1) >= ib_bh_size(ib_bh)) {
break;
}
ptr = (byte*) ib_bh_get(ib_bh, parent << 1);
}
--ib_bh->n_elems;
ib_bh_set(ib_bh, parent, last);
}
|
