MySQL 5.6.14 Source Code Document
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ut0bh.cc
Go to the documentation of this file.
1 /***************************************************************************/
19 /******************************************************************/
26 #include "ut0bh.h"
27 #include "ut0mem.h"
28 
29 #ifdef UNIV_NONINL
30 #include "ut0bh.ic"
31 #endif
32 
33 #include <string.h>
34 
35 /**********************************************************************/
38 UNIV_INTERN
39 ib_bh_t*
40 ib_bh_create(
41 /*=========*/
42  ib_bh_cmp_t compare,
43  ulint sizeof_elem,
44  ulint max_elems)
45 {
46  ulint sz;
47  ib_bh_t* ib_bh;
48 
49  sz = sizeof(*ib_bh) + (sizeof_elem * max_elems);
50 
51  ib_bh = (ib_bh_t*) ut_malloc(sz);
52  memset(ib_bh, 0x0, sz);
53 
54  ib_bh->compare = compare;
55  ib_bh->max_elems = max_elems;
56  ib_bh->sizeof_elem = sizeof_elem;
57 
58  return(ib_bh);
59 }
60 
61 /**********************************************************************/
64 UNIV_INTERN
65 void
66 ib_bh_free(
67 /*=======*/
68  ib_bh_t* ib_bh)
69 {
70  ut_free(ib_bh);
71 }
72 
73 /**********************************************************************/
76 UNIV_INTERN
77 void*
78 ib_bh_push(
79 /*=======*/
80  ib_bh_t* ib_bh,
81  const void* elem)
82 {
83  void* ptr;
84 
85  if (ib_bh_is_full(ib_bh)) {
86  return(NULL);
87  } else if (ib_bh_is_empty(ib_bh)) {
88  ++ib_bh->n_elems;
89  return(ib_bh_set(ib_bh, 0, elem));
90  } else {
91  ulint i;
92 
93  i = ib_bh->n_elems;
94 
95  ++ib_bh->n_elems;
96 
97  for (ptr = ib_bh_get(ib_bh, i >> 1);
98  i > 0 && ib_bh->compare(ptr, elem) > 0;
99  i >>= 1, ptr = ib_bh_get(ib_bh, i >> 1)) {
100 
101  ib_bh_set(ib_bh, i, ptr);
102  }
103 
104  ptr = ib_bh_set(ib_bh, i, elem);
105  }
106 
107  return(ptr);
108 }
109 
110 /**********************************************************************/
112 UNIV_INTERN
113 void
114 ib_bh_pop(
115 /*======*/
116  ib_bh_t* ib_bh)
117 {
118  byte* ptr;
119  byte* last;
120  ulint parent = 0;
121 
122  if (ib_bh_is_empty(ib_bh)) {
123  return;
124  } else if (ib_bh_size(ib_bh) == 1) {
125  --ib_bh->n_elems;
126  return;
127  }
128 
129  last = (byte*) ib_bh_last(ib_bh);
130 
131  /* Start from the child node */
132  ptr = (byte*) ib_bh_get(ib_bh, 1);
133 
134  while (ptr < last) {
135  /* If the "right" child node is < "left" child node */
136  if (ib_bh->compare(ptr + ib_bh->sizeof_elem, ptr) < 0) {
137  ptr += ib_bh->sizeof_elem;
138  }
139 
140  if (ib_bh->compare(last, ptr) <= 0) {
141  break;
142  }
143 
144  ib_bh_set(ib_bh, parent, ptr);
145 
146  parent = (ptr - (byte*) ib_bh_first(ib_bh))
147  / ib_bh->sizeof_elem;
148 
149  if ((parent << 1) >= ib_bh_size(ib_bh)) {
150  break;
151  }
152 
153  ptr = (byte*) ib_bh_get(ib_bh, parent << 1);
154  }
155 
156  --ib_bh->n_elems;
157 
158  ib_bh_set(ib_bh, parent, last);
159 }