Drizzled Public API Documentation

ut0bh.cc
1 /***************************************************************************/
24 /******************************************************************/
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 /**********************************************************************/
43 UNIV_INTERN
44 ib_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 /**********************************************************************/
69 UNIV_INTERN
70 void
72 /*=======*/
73  ib_bh_t* ib_bh)
74 {
75  ut_free(ib_bh);
76 }
77 
78 /**********************************************************************/
81 UNIV_INTERN
82 void*
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 /**********************************************************************/
117 UNIV_INTERN
118 void
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 }
UNIV_INLINE void * ib_bh_get(ib_bh_t *ib_bh, ulint i)
ulint sizeof_elem
Definition: ut0bh.h:144
UNIV_INLINE ibool ib_bh_is_full(const ib_bh_t *ib_bh)
int(* ib_bh_cmp_t)(const void *p1, const void *p2)
Definition: ut0bh.h:32
UNIV_INTERN void * ut_malloc(ulint n)
Definition: ut0mem.cc:235
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 void * ib_bh_set(ib_bh_t *ib_bh, ulint i, const void *elem)
UNIV_INLINE void * ib_bh_last(ib_bh_t *ib_bh)
UNIV_INLINE ibool ib_bh_is_empty(const ib_bh_t *ib_bh)
ulint n_elems
Definition: ut0bh.h:143
ib_bh_cmp_t compare
Definition: ut0bh.h:145
UNIV_INTERN void * ib_bh_push(ib_bh_t *ib_bh, const void *elem)
Definition: ut0bh.cc:83
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_INLINE ulint ib_bh_size(const ib_bh_t *ib_bh)
UNIV_INLINE void * ib_bh_first(ib_bh_t *ib_bh)
UNIV_INTERN void ib_bh_free(ib_bh_t *ib_bh)
Definition: ut0bh.cc:71