drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
ut0bh.cc
1/***************************************************************************/
23
24/******************************************************************/
30
31#include "ut0bh.h"
32#include "ut0mem.h"
33
34#ifdef UNIV_NONINL
35#include "ut0bh.ic"
36#endif
37
38#include <string.h>
39
40/**********************************************************************/
43UNIV_INTERN
44ib_bh_t*
46/*=========*/
47 ib_bh_cmp_t compare,
48 ulint sizeof_elem,
49 ulint max_elems)
50{
51 ulint sz;
52 ib_bh_t* ib_bh;
53
54 sz = sizeof(*ib_bh) + (sizeof_elem * max_elems);
55
56 ib_bh = (ib_bh_t*) ut_malloc(sz);
57 memset(ib_bh, 0x0, sz);
58
59 ib_bh->compare = compare;
60 ib_bh->max_elems = max_elems;
61 ib_bh->sizeof_elem = sizeof_elem;
62
63 return(ib_bh);
64}
65
66/**********************************************************************/
69UNIV_INTERN
70void
72/*=======*/
73 ib_bh_t* ib_bh)
74{
75 ut_free(ib_bh);
76}
77
78/**********************************************************************/
81UNIV_INTERN
82void*
84/*=======*/
85 ib_bh_t* ib_bh,
86 const void* elem)
87{
88 void* ptr;
89
90 if (ib_bh_is_full(ib_bh)) {
91 return(NULL);
92 } else if (ib_bh_is_empty(ib_bh)) {
93 ++ib_bh->n_elems;
94 return(ib_bh_set(ib_bh, 0, elem));
95 } else {
96 ulint i;
97
98 i = ib_bh->n_elems;
99
100 ++ib_bh->n_elems;
101
102 for (ptr = ib_bh_get(ib_bh, i >> 1);
103 i > 0 && ib_bh->compare(ptr, elem) > 0;
104 i >>= 1, ptr = ib_bh_get(ib_bh, i >> 1)) {
105
106 ib_bh_set(ib_bh, i, ptr);
107 }
108
109 ptr = ib_bh_set(ib_bh, i, elem);
110 }
111
112 return(ptr);
113}
114
115/**********************************************************************/
117UNIV_INTERN
118void
120/*======*/
121 ib_bh_t* ib_bh)
122{
123 byte* ptr;
124 byte* last;
125 ulint parent = 0;
126
127 if (ib_bh_is_empty(ib_bh)) {
128 return;
129 } else if (ib_bh_size(ib_bh) == 1) {
130 --ib_bh->n_elems;
131 return;
132 }
133
134 last = (byte*) ib_bh_last(ib_bh);
135
136 /* Start from the child node */
137 ptr = (byte*) ib_bh_get(ib_bh, 1);
138
139 while (ptr < last) {
140 /* If the "right" child node is < "left" child node */
141 if (ib_bh->compare(ptr + ib_bh->sizeof_elem, ptr) < 0) {
142 ptr += ib_bh->sizeof_elem;
143 }
144
145 if (ib_bh->compare(last, ptr) <= 0) {
146 break;
147 }
148
149 ib_bh_set(ib_bh, parent, ptr);
150
151 parent = (ptr - (byte*) ib_bh_first(ib_bh))
152 / ib_bh->sizeof_elem;
153
154 if ((parent << 1) >= ib_bh_size(ib_bh)) {
155 break;
156 }
157
158 ptr = (byte*) ib_bh_get(ib_bh, parent << 1);
159 }
160
161 --ib_bh->n_elems;
162
163 ib_bh_set(ib_bh, parent, last);
164}
ulint sizeof_elem
Definition ut0bh.h:144
ib_bh_cmp_t compare
Definition ut0bh.h:145
ulint max_elems
Definition ut0bh.h:142
ulint n_elems
Definition ut0bh.h:143
UNIV_INLINE ulint ib_bh_size(const ib_bh_t *ib_bh)
UNIV_INTERN void * ib_bh_push(ib_bh_t *ib_bh, const void *elem)
Definition ut0bh.cc:83
UNIV_INLINE ibool ib_bh_is_full(const ib_bh_t *ib_bh)
UNIV_INTERN ib_bh_t * ib_bh_create(ib_bh_cmp_t compare, ulint sizeof_elem, ulint max_elems)
Definition ut0bh.cc:45
UNIV_INLINE ibool ib_bh_is_empty(const ib_bh_t *ib_bh)
UNIV_INTERN void ib_bh_free(ib_bh_t *ib_bh)
Definition ut0bh.cc:71
UNIV_INLINE void * ib_bh_last(ib_bh_t *ib_bh)
UNIV_INLINE void * ib_bh_set(ib_bh_t *ib_bh, ulint i, const void *elem)
int(* ib_bh_cmp_t)(const void *p1, const void *p2)
Definition ut0bh.h:32
UNIV_INLINE void * ib_bh_first(ib_bh_t *ib_bh)
UNIV_INLINE void * ib_bh_get(ib_bh_t *ib_bh, ulint i)
UNIV_INTERN void ib_bh_pop(ib_bh_t *ib_bh)
Definition ut0bh.cc:119
UNIV_INTERN void ut_free(void *ptr)
Definition ut0mem.cc:294
UNIV_INTERN void * ut_malloc(ulint n)
Definition ut0mem.cc:235