60 #ifndef BENTLEY_UTIL_BTREE_BTREE_H__
61 #define BENTLEY_UTIL_BTREE_BTREE_H__
67 #include <sys/types.h>
72 #include <type_traits>
76 #pragma push_macro ("min")
77 #pragma push_macro ("max")
89 typedef intptr_t ssize_t;
100 inline void btree_swap_helper(T &a, T &b) {
106 template<
bool cond,
typename A,
typename B>
111 template<
typename A,
typename B>
112 struct if_<false, A, B> {
125 struct CompileAssert {
128 #define COMPILE_ASSERT(expr, msg) \
129 typedef CompileAssert<(bool(expr))> msg[bool(expr) ? 1 : -1]
143 struct btree_key_compare_to_tag {
148 template <
typename Compare>
149 struct btree_is_key_compare_to
150 :
public std::is_convertible<Compare, btree_key_compare_to_tag> {
161 template <
typename Compare>
162 struct btree_key_compare_to_adapter : Compare {
163 btree_key_compare_to_adapter() { }
164 btree_key_compare_to_adapter(
const Compare &c) : Compare(c) { }
165 btree_key_compare_to_adapter(
const btree_key_compare_to_adapter<Compare> &c)
171 struct btree_key_compare_to_adapter<std::less<bastring> >
172 :
public btree_key_compare_to_tag {
173 btree_key_compare_to_adapter() {}
174 btree_key_compare_to_adapter(
const std::less<bastring>&) {}
175 btree_key_compare_to_adapter(
176 const btree_key_compare_to_adapter<std::less<bastring> >&) {}
183 struct btree_key_compare_to_adapter<std::greater<bastring> >
184 :
public btree_key_compare_to_tag {
185 btree_key_compare_to_adapter() {}
186 btree_key_compare_to_adapter(
const std::greater<bastring>&) {}
187 btree_key_compare_to_adapter(
188 const btree_key_compare_to_adapter<std::greater<bastring> >&) {}
194 struct btree_key_compare_to_adapter<std::less<bwstring> >
195 :
public btree_key_compare_to_tag {
196 btree_key_compare_to_adapter() {}
197 btree_key_compare_to_adapter(
const std::less<bwstring>&) {}
198 btree_key_compare_to_adapter(
199 const btree_key_compare_to_adapter<std::less<bwstring> >&) {}
206 struct btree_key_compare_to_adapter<std::greater<bwstring> >
207 :
public btree_key_compare_to_tag {
208 btree_key_compare_to_adapter() {}
209 btree_key_compare_to_adapter(
const std::greater<bwstring>&) {}
210 btree_key_compare_to_adapter(
211 const btree_key_compare_to_adapter<std::greater<bwstring> >&) {}
220 template <
typename Key,
typename Compare,
bool HaveCompareTo>
221 struct btree_key_comparer {
222 btree_key_comparer() {}
223 btree_key_comparer(Compare c) : comp(c) {}
224 static bool bool_compare(
const Compare &comp,
const Key &x,
const Key &y) {
227 bool operator()(
const Key &x,
const Key &y)
const {
228 return bool_compare(comp, x, y);
236 template <
typename Key,
typename Compare>
237 struct btree_key_comparer<Key, Compare, true> {
238 btree_key_comparer() {}
239 btree_key_comparer(Compare c) : comp(c) {}
240 static bool bool_compare(
const Compare &comp,
const Key &x,
const Key &y) {
241 return comp(x, y) < 0;
243 bool operator()(
const Key &x,
const Key &y)
const {
244 return bool_compare(comp, x, y);
253 template <
typename Key,
typename Compare>
254 static bool btree_compare_keys(
255 const Compare &comp,
const Key &x,
const Key &y) {
256 typedef btree_key_comparer<Key, Compare,
257 btree_is_key_compare_to<Compare>::value> key_comparer;
258 return key_comparer::bool_compare(comp, x, y);
261 template <
typename Key,
typename Compare,
262 typename Alloc,
int TargetNodeSize,
int ValueSize>
263 struct btree_common_params {
267 typedef typename if_<
268 btree_is_key_compare_to<Compare>::value,
269 Compare, btree_key_compare_to_adapter<Compare> >::type key_compare;
272 typedef btree_is_key_compare_to<key_compare> is_key_compare_to;
274 typedef Alloc allocator_type;
275 typedef Key key_type;
276 typedef ssize_t size_type;
277 typedef ptrdiff_t difference_type;
280 kTargetNodeSize = TargetNodeSize,
284 kNodeValueSpace = TargetNodeSize - 2 *
sizeof(
void*),
289 typedef typename if_<
290 (kNodeValueSpace / ValueSize) >= 256,
292 uint8_t>::type node_count_type;
296 template <
typename Key,
typename Data,
typename Compare,
297 typename Alloc,
int TargetNodeSize>
299 :
public btree_common_params<Key, Compare, Alloc, TargetNodeSize,
300 sizeof(Key) + sizeof(Data)> {
301 typedef Data data_type;
302 typedef Data mapped_type;
305 typedef value_type* pointer;
306 typedef const value_type* const_pointer;
307 typedef value_type& reference;
308 typedef const value_type& const_reference;
311 kValueSize =
sizeof(Key) +
sizeof(data_type),
314 static const Key& key(
const value_type &x) {
return x.
first; }
315 static const Key& key(
const mutable_value_type &x) {
return x.first; }
316 static void swap(mutable_value_type *a, mutable_value_type *b) {
317 btree_swap_helper(a->first, b->first);
318 btree_swap_helper(a->second, b->second);
323 template <
typename Key,
typename Compare,
typename Alloc,
int TargetNodeSize>
324 struct btree_set_params
325 :
public btree_common_params<Key, Compare, Alloc, TargetNodeSize,
327 typedef std::false_type data_type;
328 typedef std::false_type mapped_type;
329 typedef Key value_type;
330 typedef value_type mutable_value_type;
331 typedef value_type* pointer;
332 typedef const value_type* const_pointer;
333 typedef value_type& reference;
334 typedef const value_type& const_reference;
337 kValueSize =
sizeof(Key),
340 static const Key& key(
const value_type &x) {
return x; }
341 static void swap(mutable_value_type *a, mutable_value_type *b) {
342 btree_swap_helper<mutable_value_type>(*a, *b);
348 template <
typename Key,
typename Compare>
349 struct btree_upper_bound_adapter :
public Compare {
350 btree_upper_bound_adapter(Compare c) : Compare(c) {}
351 bool operator()(
const Key &a,
const Key &b)
const {
352 return !
static_cast<const Compare&
>(*this)(b, a);
356 template <
typename Key,
typename CompareTo>
357 struct btree_upper_bound_compare_to_adapter :
public CompareTo {
358 btree_upper_bound_compare_to_adapter(CompareTo c) : CompareTo(c) {}
359 int operator()(
const Key &a,
const Key &b)
const {
360 return static_cast<const CompareTo&
>(*this)(b, a);
365 template <
typename K,
typename N,
typename Compare>
366 struct btree_linear_search_plain_compare {
367 static int lower_bound(
const K &k,
const N &n, Compare comp) {
368 return n.linear_search_plain_compare(k, 0, n.count(), comp);
370 static int upper_bound(
const K &k,
const N &n, Compare comp) {
371 typedef btree_upper_bound_adapter<K, Compare> upper_compare;
372 return n.linear_search_plain_compare(k, 0, n.count(), upper_compare(comp));
377 template <
typename K,
typename N,
typename CompareTo>
378 struct btree_linear_search_compare_to {
379 static int lower_bound(
const K &k,
const N &n, CompareTo comp) {
380 return n.linear_search_compare_to(k, 0, n.count(), comp);
382 static int upper_bound(
const K &k,
const N &n, CompareTo comp) {
383 typedef btree_upper_bound_adapter<K,
384 btree_key_comparer<K, CompareTo, true> > upper_compare;
385 return n.linear_search_plain_compare(k, 0, n.count(), upper_compare(comp));
390 template <
typename K,
typename N,
typename Compare>
391 struct btree_binary_search_plain_compare {
392 static int lower_bound(
const K &k,
const N &n, Compare comp) {
393 return n.binary_search_plain_compare(k, 0, n.count(), comp);
395 static int upper_bound(
const K &k,
const N &n, Compare comp) {
396 typedef btree_upper_bound_adapter<K, Compare> upper_compare;
397 return n.binary_search_plain_compare(k, 0, n.count(), upper_compare(comp));
402 template <
typename K,
typename N,
typename CompareTo>
403 struct btree_binary_search_compare_to {
404 static int lower_bound(
const K &k,
const N &n, CompareTo comp) {
405 return n.binary_search_compare_to(k, 0, n.count(), CompareTo());
407 static int upper_bound(
const K &k,
const N &n, CompareTo comp) {
408 typedef btree_upper_bound_adapter<K,
409 btree_key_comparer<K, CompareTo, true> > upper_compare;
410 return n.linear_search_plain_compare(k, 0, n.count(), upper_compare(comp));
417 template <
typename Params>
420 typedef Params params_type;
421 typedef btree_node<Params> self_type;
422 typedef typename Params::key_type key_type;
423 typedef typename Params::data_type data_type;
424 typedef typename Params::value_type value_type;
425 typedef typename Params::mutable_value_type mutable_value_type;
426 typedef typename Params::pointer pointer;
427 typedef typename Params::const_pointer const_pointer;
428 typedef typename Params::reference reference;
429 typedef typename Params::const_reference const_reference;
430 typedef typename Params::key_compare key_compare;
431 typedef typename Params::size_type size_type;
432 typedef typename Params::difference_type difference_type;
434 typedef btree_linear_search_plain_compare<
435 key_type, self_type, key_compare> linear_search_plain_compare_type;
436 typedef btree_linear_search_compare_to<
437 key_type, self_type, key_compare> linear_search_compare_to_type;
438 typedef btree_binary_search_plain_compare<
439 key_type, self_type, key_compare> binary_search_plain_compare_type;
440 typedef btree_binary_search_compare_to<
441 key_type, self_type, key_compare> binary_search_compare_to_type;
444 typedef typename if_<
445 Params::is_key_compare_to::value,
446 linear_search_compare_to_type,
447 linear_search_plain_compare_type>::type linear_search_type;
450 typedef typename if_<
451 Params::is_key_compare_to::value,
452 binary_search_compare_to_type,
453 binary_search_plain_compare_type>::type binary_search_type;
457 typedef typename if_<
458 std::is_integral<key_type>::value ||
459 std::is_floating_point<key_type>::value,
460 linear_search_type, binary_search_type>::type search_type;
463 typedef typename Params::node_count_type field_type;
470 field_type max_count;
478 kValueSize = params_type::kValueSize,
479 kTargetNodeSize = params_type::kTargetNodeSize,
482 kNodeTargetValues = (kTargetNodeSize -
sizeof(base_fields)) / kValueSize,
486 kNodeValues = kNodeTargetValues >= 3 ? kNodeTargetValues : 3,
488 kExactMatch = 1 << 30,
489 kMatchMask = kExactMatch - 1,
492 struct leaf_fields :
public base_fields {
495 mutable_value_type values[kNodeValues];
498 struct internal_fields :
public leaf_fields {
502 btree_node *children[kNodeValues + 1];
505 struct root_fields :
public internal_fields {
506 btree_node *rightmost;
513 bool leaf()
const {
return fields_.leaf; }
516 int position()
const {
return fields_.position; }
517 void set_position(
int v) { fields_.position = (
typename base_fields::field_type) v; }
520 int count()
const {
return fields_.count; }
521 void set_count(
int v) { fields_.count = (
typename base_fields::field_type) v; }
522 int max_count()
const {
return fields_.max_count; }
525 btree_node* parent()
const {
return fields_.parent; }
529 bool is_root()
const {
return parent()->leaf(); }
531 assert(parent()->is_root());
532 fields_.parent = fields_.parent->parent();
536 btree_node* rightmost()
const {
return fields_.rightmost; }
537 btree_node** mutable_rightmost() {
return &fields_.rightmost; }
540 size_type
size()
const {
return fields_.size; }
541 size_type* mutable_size() {
return &fields_.size; }
544 const key_type& key(
int i)
const {
545 return params_type::key(fields_.values[i]);
547 reference value(
int i) {
548 return reinterpret_cast<reference
>(fields_.values[i]);
550 const_reference value(
int i)
const {
551 return reinterpret_cast<const_reference
>(fields_.values[i]);
553 mutable_value_type* mutable_value(
int i) {
554 return &fields_.values[i];
558 void value_swap(
int i, btree_node *x,
int j) {
563 btree_node* child(
int i)
const {
return fields_.children[i]; }
564 btree_node** mutable_child(
int i) {
return &fields_.children[i]; }
565 void set_child(
int i, btree_node *c) {
566 *mutable_child(i) = c;
567 c->fields_.parent =
this;
568 c->fields_.position = (
typename base_fields::field_type) i;
572 template <
typename Compare>
573 int lower_bound(
const key_type &k,
const Compare &comp)
const {
577 template <
typename Compare>
578 int upper_bound(
const key_type &k,
const Compare &comp)
const {
584 template <
typename Compare>
585 int linear_search_plain_compare(
586 const key_type &k,
int s,
int e,
const Compare &comp)
const {
588 if (!btree_compare_keys(comp, key(s), k)) {
598 template <
typename Compare>
599 int linear_search_compare_to(
600 const key_type &k,
int s,
int e,
const Compare &comp)
const {
602 int c = comp(key(s), k);
604 return s | kExactMatch;
615 template <
typename Compare>
616 int binary_search_plain_compare(
617 const key_type &k,
int s,
int e,
const Compare &comp)
const {
619 int mid = (s + e) / 2;
620 if (btree_compare_keys(comp, key(mid), k)) {
631 template <
typename CompareTo>
632 int binary_search_compare_to(
633 const key_type &k,
int s,
int e,
const CompareTo &comp)
const {
635 int mid = (s + e) / 2;
636 int c = comp(key(mid), k);
646 s = binary_search_compare_to(k, s, mid, comp);
647 return s | kExactMatch;
655 void insert_value(
int i,
const value_type &x);
659 void remove_value(
int i);
662 void rebalance_right_to_left(btree_node *sibling,
int to_move);
663 void rebalance_left_to_right(btree_node *sibling,
int to_move);
666 void split(btree_node *sibling,
int insert_position);
670 void merge(btree_node *sibling);
673 void swap(btree_node *src);
676 static btree_node* init_leaf(
677 leaf_fields *f, btree_node *parent,
int max_count) {
678 btree_node *n =
reinterpret_cast<btree_node*
>(f);
681 f->max_count = (
typename leaf_fields::field_type) max_count;
684 #if defined REMOVED_BY_BENTLEY
686 memset(&f->values, 0, max_count *
sizeof(value_type));
691 static btree_node* init_internal(internal_fields *f, btree_node *parent) {
692 btree_node *n = init_leaf(f, parent, kNodeValues);
694 #if defined REMOVED_BY_BENTLEY
696 memset(f->children, 0,
sizeof(f->children));
701 static btree_node* init_root(root_fields *f, btree_node *parent) {
702 btree_node *n = init_internal(f, parent);
703 f->rightmost = parent;
704 f->size = parent->count();
708 for (
int i = 0; i <
count(); ++i) {
714 void value_init(
int i) {
715 new (&fields_.values[i]) mutable_value_type;
717 void value_init(
int i,
const value_type &x) {
718 new (&fields_.values[i]) mutable_value_type(x);
720 void value_destroy(
int i) {
721 fields_.values[i].~mutable_value_type();
728 btree_node(
const btree_node&);
732 template <
typename Node,
typename Reference,
typename Po
inter>
733 struct btree_iterator {
734 typedef typename Node::key_type key_type;
735 typedef typename Node::size_type size_type;
736 typedef typename Node::difference_type difference_type;
737 typedef typename Node::params_type params_type;
739 typedef Node node_type;
740 typedef typename std::remove_const<Node>::type normal_node;
741 typedef const Node const_node;
742 typedef typename params_type::value_type value_type;
743 typedef typename params_type::pointer normal_pointer;
744 typedef typename params_type::reference normal_reference;
745 typedef typename params_type::const_pointer const_pointer;
746 typedef typename params_type::const_reference const_reference;
748 typedef Pointer pointer;
749 typedef Reference reference;
750 typedef std::bidirectional_iterator_tag iterator_category;
752 typedef btree_iterator<
753 normal_node, normal_reference, normal_pointer> iterator;
754 typedef btree_iterator<
755 const_node, const_reference, const_pointer> const_iterator;
756 typedef btree_iterator<Node, Reference, Pointer> self_type;
762 btree_iterator(Node *n,
int p)
766 btree_iterator(
const iterator &x)
768 position(x.position) {
773 if (node->leaf() && ++position < node->count()) {
778 void increment_by(
int count);
779 void increment_slow();
782 if (node->leaf() && --position >= 0) {
787 void decrement_slow();
789 bool operator==(
const const_iterator &x)
const {
790 return node == x.node && position == x.position;
792 bool operator!=(
const const_iterator &x)
const {
793 return node != x.node || position != x.position;
797 const key_type& key()
const {
798 return node->key(position);
801 return node->value(position);
803 pointer operator->()
const {
804 return &node->value(position);
807 self_type& operator++() {
811 self_type& operator--() {
815 self_type operator++(
int) {
816 self_type tmp = *
this;
820 self_type operator--(
int) {
821 self_type tmp = *
this;
833 struct btree_internal_locate_plain_compare {
834 template <
typename K,
typename T,
typename Iter>
836 return t.internal_locate_plain_compare(k, iter);
841 struct btree_internal_locate_compare_to {
842 template <
typename K,
typename T,
typename Iter>
844 return t.internal_locate_compare_to(k, iter);
848 template <
typename Params>
849 class btree :
public Params::key_compare {
850 typedef btree<Params> self_type;
851 typedef btree_node<Params> node_type;
852 typedef typename node_type::base_fields base_fields;
853 typedef typename node_type::leaf_fields leaf_fields;
854 typedef typename node_type::internal_fields internal_fields;
855 typedef typename node_type::root_fields root_fields;
856 typedef typename Params::is_key_compare_to is_key_compare_to;
858 friend struct btree_internal_locate_plain_compare;
859 friend struct btree_internal_locate_compare_to;
860 typedef typename if_<
861 is_key_compare_to::value,
862 btree_internal_locate_compare_to,
863 btree_internal_locate_plain_compare>::type internal_locate_type;
866 kNodeValues = node_type::kNodeValues,
867 kMinNodeValues = kNodeValues / 2,
868 kValueSize = node_type::kValueSize,
869 kExactMatch = node_type::kExactMatch,
870 kMatchMask = node_type::kMatchMask,
879 template <
typename Base,
typename Data>
880 struct empty_base_handle :
public Base {
881 empty_base_handle(
const Base &b,
const Data &d)
889 node_stats(ssize_t l, ssize_t i)
895 leaf_nodes += x.leaf_nodes;
896 internal_nodes += x.internal_nodes;
901 ssize_t internal_nodes;
905 typedef Params params_type;
906 typedef typename Params::key_type key_type;
907 typedef typename Params::data_type data_type;
908 typedef typename Params::mapped_type mapped_type;
909 typedef typename Params::value_type value_type;
910 typedef typename Params::key_compare key_compare;
911 typedef typename Params::pointer pointer;
912 typedef typename Params::const_pointer const_pointer;
913 typedef typename Params::reference reference;
914 typedef typename Params::const_reference const_reference;
915 typedef typename Params::size_type size_type;
916 typedef typename Params::difference_type difference_type;
917 typedef btree_iterator<node_type, reference, pointer> iterator;
918 typedef typename iterator::const_iterator const_iterator;
919 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
920 typedef std::reverse_iterator<iterator> reverse_iterator;
922 typedef typename Params::allocator_type allocator_type;
923 typedef typename allocator_type::template rebind<char>::other
924 internal_allocator_type;
928 btree(
const key_compare &comp,
const allocator_type &alloc);
931 btree(
const self_type &x);
940 return iterator(leftmost(), 0);
942 const_iterator
begin()
const {
943 return const_iterator(leftmost(), 0);
946 return iterator(rightmost(), rightmost() ? rightmost()->
count() : 0);
948 const_iterator
end()
const {
949 return const_iterator(rightmost(), rightmost() ? rightmost()->
count() : 0);
951 reverse_iterator
rbegin() {
952 return reverse_iterator(
end());
954 const_reverse_iterator
rbegin()
const {
955 return const_reverse_iterator(
end());
957 reverse_iterator
rend() {
958 return reverse_iterator(
begin());
960 const_reverse_iterator
rend()
const {
961 return const_reverse_iterator(
begin());
967 internal_lower_bound(key, iterator(root(), 0)));
969 const_iterator
lower_bound(
const key_type &key)
const {
971 internal_lower_bound(key, const_iterator(root(), 0)));
977 internal_upper_bound(key, iterator(root(), 0)));
979 const_iterator
upper_bound(
const key_type &key)
const {
981 internal_upper_bound(key, const_iterator(root(), 0)));
999 template <
typename ValuePo
inter>
1005 return insert_unique(params_type::key(v), &v);
1012 iterator insert_unique(iterator position,
const value_type &v);
1015 template <
typename InputIterator>
1016 void insert_unique(InputIterator b, InputIterator e);
1022 template <
typename ValuePo
inter>
1023 iterator insert_multi(
const key_type &key, ValuePointer value);
1026 iterator insert_multi(
const value_type &v) {
1027 return insert_multi(params_type::key(v), &v);
1034 iterator insert_multi(iterator position,
const value_type &v);
1037 template <
typename InputIterator>
1038 void insert_multi(InputIterator b, InputIterator e);
1040 void assign(
const self_type &x);
1045 iterator
erase(iterator iter);
1052 int erase_unique(
const key_type &key);
1056 int erase_multi(
const key_type &key);
1060 iterator find_unique(
const key_type &key) {
1061 return internal_end(
1062 internal_find_unique(key, iterator(root(), 0)));
1064 const_iterator find_unique(
const key_type &key)
const {
1065 return internal_end(
1066 internal_find_unique(key, const_iterator(root(), 0)));
1068 iterator find_multi(
const key_type &key) {
1069 return internal_end(
1070 internal_find_multi(key, iterator(root(), 0)));
1072 const_iterator find_multi(
const key_type &key)
const {
1073 return internal_end(
1074 internal_find_multi(key, const_iterator(root(), 0)));
1078 size_type count_unique(
const key_type &key)
const {
1079 const_iterator
begin = internal_find_unique(
1080 key, const_iterator(root(), 0));
1088 size_type count_multi(
const key_type &key)
const {
1096 void swap(self_type &x);
1099 self_type&
operator=(
const self_type &x) {
1108 key_compare* mutable_key_comp() {
1111 const key_compare&
key_comp()
const {
1114 bool compare_keys(
const key_type &x,
const key_type &y)
const {
1115 return btree_compare_keys(
key_comp(), x, y);
1118 #if defined COMPILE_BTREE_DUMP
1121 void dump(std::ostream &os)
const {
1122 if (root() !=
NULL) {
1123 internal_dump(os, root(), 0);
1129 void verify()
const;
1132 size_type
size()
const {
1133 if (
empty())
return 0;
1134 if (root()->leaf())
return root()->count();
1135 return root()->size();
1138 bool empty()
const {
return root() ==
NULL; }
1141 size_type height()
const {
1148 const node_type *n = root();
1152 }
while (n != root());
1158 size_type leaf_nodes()
const {
1159 return internal_stats(root()).leaf_nodes;
1161 size_type internal_nodes()
const {
1162 return internal_stats(root()).internal_nodes;
1164 size_type nodes()
const {
1165 node_stats stats = internal_stats(root());
1166 return stats.leaf_nodes + stats.internal_nodes;
1170 size_type bytes_used()
const {
1171 node_stats stats = internal_stats(root());
1172 if (stats.leaf_nodes == 1 && stats.internal_nodes == 0) {
1173 return sizeof(*this) +
1174 sizeof(base_fields) + root()->max_count() *
sizeof(value_type);
1176 return sizeof(*this) +
1177 sizeof(root_fields) -
sizeof(internal_fields) +
1178 stats.leaf_nodes *
sizeof(leaf_fields) +
1179 stats.internal_nodes *
sizeof(internal_fields);
1184 static double average_bytes_per_value() {
1188 return sizeof(leaf_fields) / (kNodeValues * 0.75);
1195 double fullness()
const {
1196 return double(
size()) / (nodes() * kNodeValues);
1201 double overhead()
const {
1205 return (bytes_used() -
size() * kValueSize) / double(
size());
1210 node_type* root() {
return root_.data; }
1211 const node_type* root()
const {
return root_.data; }
1212 node_type** mutable_root() {
return &root_.data; }
1215 node_type* rightmost() {
1216 return (!root() || root()->leaf()) ? root() : root()->rightmost();
1218 const node_type* rightmost()
const {
1219 return (!root() || root()->leaf()) ? root() : root()->rightmost();
1221 node_type** mutable_rightmost() {
return root()->mutable_rightmost(); }
1224 node_type* leftmost() {
return root() ? root()->parent() :
NULL; }
1225 const node_type* leftmost()
const {
return root() ? root()->parent() :
NULL; }
1228 size_type* mutable_size() {
return root()->mutable_size(); }
1231 internal_allocator_type* mutable_internal_allocator() {
1232 return static_cast<internal_allocator_type*
>(&root_);
1234 const internal_allocator_type& internal_allocator()
const {
1235 return *
static_cast<const internal_allocator_type*
>(&root_);
1239 node_type* new_internal_node(node_type *parent) {
1240 internal_fields *p =
reinterpret_cast<internal_fields*
>(
1241 mutable_internal_allocator()->allocate(
sizeof(internal_fields)));
1242 return node_type::init_internal(p, parent);
1244 node_type* new_internal_root_node() {
1245 root_fields *p =
reinterpret_cast<root_fields*
>(
1246 mutable_internal_allocator()->allocate(
sizeof(root_fields)));
1247 return node_type::init_root(p, root()->parent());
1249 node_type* new_leaf_node(node_type *parent) {
1250 leaf_fields *p =
reinterpret_cast<leaf_fields*
>(
1251 mutable_internal_allocator()->allocate(
sizeof(leaf_fields)));
1252 return node_type::init_leaf(p, parent, kNodeValues);
1254 node_type* new_leaf_root_node(
int max_count) {
1255 leaf_fields *p =
reinterpret_cast<leaf_fields*
>(
1256 mutable_internal_allocator()->allocate(
1257 sizeof(base_fields) + max_count *
sizeof(value_type)));
1258 return node_type::init_leaf(p, reinterpret_cast<node_type*>(p), max_count);
1260 void delete_internal_node(node_type *node) {
1262 assert(node != root());
1263 mutable_internal_allocator()->deallocate(
1264 reinterpret_cast<char*>(node),
sizeof(internal_fields));
1266 void delete_internal_root_node() {
1268 mutable_internal_allocator()->deallocate(
1269 reinterpret_cast<char*>(root()),
sizeof(root_fields));
1271 void delete_leaf_node(node_type *node) {
1273 mutable_internal_allocator()->deallocate(
1274 reinterpret_cast<char*>(node),
1275 sizeof(base_fields) + node->max_count() *
sizeof(value_type));
1279 void rebalance_or_split(iterator *iter);
1283 void merge_nodes(node_type *left, node_type *right);
1289 bool try_merge_or_rebalance(iterator *iter);
1294 iterator internal_end(iterator iter) {
1295 return iter.node ? iter :
end();
1297 const_iterator internal_end(const_iterator iter)
const {
1298 return iter.node ? iter :
end();
1303 iterator internal_insert(iterator iter,
const value_type &v);
1309 template <
typename IterType>
1310 static IterType internal_last(IterType iter);
1321 template <
typename IterType>
1323 const key_type &key, IterType iter)
const;
1324 template <
typename IterType>
1326 const key_type &key, IterType iter)
const;
1327 template <
typename IterType>
1329 const key_type &key, IterType iter)
const;
1332 template <
typename IterType>
1333 IterType internal_lower_bound(
1334 const key_type &key, IterType iter)
const;
1337 template <
typename IterType>
1338 IterType internal_upper_bound(
1339 const key_type &key, IterType iter)
const;
1342 template <
typename IterType>
1343 IterType internal_find_unique(
1344 const key_type &key, IterType iter)
const;
1347 template <
typename IterType>
1348 IterType internal_find_multi(
1349 const key_type &key, IterType iter)
const;
1352 void internal_clear(node_type *node);
1354 #if defined COMPILE_BTREE_DUMP
1356 void internal_dump(std::ostream &os,
const node_type *node,
int level)
const;
1360 int internal_verify(
const node_type *node,
1361 const key_type *lo,
const key_type *hi)
const;
1363 node_stats internal_stats(
const node_type *node)
const {
1365 return node_stats(0, 0);
1368 return node_stats(1, 0);
1370 node_stats res(0, 1);
1371 for (
int i = 0; i <= node->count(); ++i) {
1372 res += internal_stats(node->child(i));
1378 empty_base_handle<internal_allocator_type, node_type*> root_;
1383 template <
typename R>
1384 static typename if_<
1385 if_<is_key_compare_to::value,
1386 std::is_same<R, int>,
1387 std::is_same<R, bool> >::type::value,
1388 big_, small_>::type key_compare_checker(R);
1392 static key_compare key_compare_helper();
1400 #if REMOVED_DOESNT_COMPILE // BENTLEY
1401 static_assert(
sizeof(key_compare_checker(key_compare_helper()(key_type(), key_type()))) ==
sizeof(big_),
"key_comparison_function_must_return_bool");
1406 static_assert(kNodeValues <
1407 (1 << (8 *
sizeof(
typename base_fields::field_type))),
1408 "target_node_size_too_large");
1411 static_assert(
sizeof(base_fields) >= 2 *
sizeof(
void*),
1412 "node_space_assumption_incorrect");
1417 template <
typename P>
1418 inline void btree_node<P>::insert_value(
int i,
const value_type &x) {
1419 assert(i <=
count());
1420 value_init(
count(), x);
1421 for (
int j =
count(); j > i; --j) {
1422 value_swap(j,
this, j - 1);
1424 set_count(
count() + 1);
1428 for (
int j =
count(); j > i; --j) {
1429 *mutable_child(j) = child(j - 1);
1430 child(j)->set_position(j);
1432 *mutable_child(i) =
NULL;
1436 template <
typename P>
1437 inline void btree_node<P>::remove_value(
int i) {
1439 assert(child(i + 1)->
count() == 0);
1440 for (
int j = i + 1; j <
count(); ++j) {
1441 *mutable_child(j) = child(j + 1);
1442 child(j)->set_position(j);
1447 set_count(
count() - 1);
1448 for (; i <
count(); ++i) {
1449 value_swap(i,
this, i + 1);
1454 template <
typename P>
1455 void btree_node<P>::rebalance_right_to_left(btree_node *src,
int to_move) {
1456 assert(parent() == src->parent());
1457 assert(position() + 1 == src->position());
1458 assert(src->count() >=
count());
1459 assert(to_move >= 1);
1460 assert(to_move <= src->
count());
1463 for (
int i = 0; i < to_move; ++i) {
1464 value_init(i +
count());
1469 value_swap(
count(), parent(), position());
1470 parent()->value_swap(position(), src, to_move - 1);
1473 for (
int i = 1; i < to_move; ++i) {
1474 value_swap(
count() + i, src, i - 1);
1477 for (
int i = to_move; i < src->count(); ++i) {
1478 src->value_swap(i - to_move, src, i);
1480 for (
int i = 1; i <= to_move; ++i) {
1481 src->value_destroy(src->count() - i);
1486 for (
int i = 0; i < to_move; ++i) {
1487 set_child(1 +
count() + i, src->child(i));
1489 for (
int i = 0; i <= src->count() - to_move; ++i) {
1490 assert(i + to_move <= src->max_count());
1491 src->set_child(i, src->child(i + to_move));
1492 *src->mutable_child(i + to_move) =
NULL;
1497 set_count(
count() + to_move);
1498 src->set_count(src->count() - to_move);
1501 template <
typename P>
1502 void btree_node<P>::rebalance_left_to_right(btree_node *dest,
int to_move) {
1503 assert(parent() == dest->parent());
1504 assert(position() + 1 == dest->position());
1505 assert(
count() >= dest->count());
1506 assert(to_move >= 1);
1507 assert(to_move <=
count());
1510 for (
int i = 0; i < to_move; ++i) {
1511 dest->value_init(i + dest->count());
1513 for (
int i = dest->count() - 1; i >= 0; --i) {
1514 dest->value_swap(i, dest, i + to_move);
1519 dest->value_swap(to_move - 1, parent(), position());
1520 parent()->value_swap(position(),
this,
count() - to_move);
1521 value_destroy(
count() - to_move);
1524 for (
int i = 1; i < to_move; ++i) {
1525 value_swap(
count() - to_move + i, dest, i - 1);
1526 value_destroy(
count() - to_move + i);
1531 for (
int i = dest->count(); i >= 0; --i) {
1532 dest->set_child(i + to_move, dest->child(i));
1533 *dest->mutable_child(i) =
NULL;
1535 for (
int i = 1; i <= to_move; ++i) {
1536 dest->set_child(i - 1, child(
count() - to_move + i));
1537 *mutable_child(
count() - to_move + i) =
NULL;
1542 set_count(
count() - to_move);
1543 dest->set_count(dest->count() + to_move);
1546 template <
typename P>
1547 void btree_node<P>::split(btree_node *dest,
int insert_position) {
1548 assert(dest->count() == 0);
1554 if (insert_position == 0) {
1555 dest->set_count(
count() - 1);
1556 }
else if (insert_position == max_count()) {
1559 dest->set_count(
count() / 2);
1561 set_count(
count() - dest->count());
1562 assert(
count() >= 1);
1565 for (
int i = 0; i < dest->count(); ++i) {
1566 dest->value_init(i);
1567 value_swap(
count() + i, dest, i);
1568 value_destroy(
count() + i);
1572 set_count(
count() - 1);
1573 parent()->insert_value(position(), value_type());
1574 value_swap(
count(), parent(), position());
1575 value_destroy(
count());
1576 parent()->set_child(position() + 1, dest);
1579 for (
int i = 0; i <= dest->count(); ++i) {
1581 dest->set_child(i, child(
count() + i + 1));
1587 template <
typename P>
1588 void btree_node<P>::merge(btree_node *src) {
1589 assert(parent() == src->parent());
1590 assert(position() + 1 == src->position());
1593 value_init(
count());
1594 value_swap(
count(), parent(), position());
1597 for (
int i = 0; i < src->count(); ++i) {
1598 value_init(1 +
count() + i);
1599 value_swap(1 +
count() + i, src, i);
1600 src->value_destroy(i);
1605 for (
int i = 0; i <= src->count(); ++i) {
1606 set_child(1 +
count() + i, src->child(i));
1607 *src->mutable_child(i) =
NULL;
1612 set_count(1 +
count() + src->count());
1616 parent()->remove_value(position());
1619 template <
typename P>
1621 assert(leaf() == x->leaf());
1624 for (
int i =
count(); i < x->count(); ++i) {
1627 for (
int i = x->count(); i <
count(); ++i) {
1631 for (
int i = 0; i < n; ++i) {
1632 value_swap(i, x, i);
1634 for (
int i =
count(); i < x->count(); ++i) {
1635 x->value_destroy(i);
1637 for (
int i = x->count(); i <
count(); ++i) {
1643 for (
int i = 0; i <= n; ++i) {
1644 btree_swap_helper(*mutable_child(i), *x->mutable_child(i));
1646 for (
int i = 0; i <=
count(); ++i) {
1647 x->child(i)->fields_.parent = x;
1649 for (
int i = 0; i <= x->count(); ++i) {
1650 child(i)->fields_.parent =
this;
1655 btree_swap_helper(fields_.count, x->fields_.count);
1660 template <
typename N,
typename R,
typename P>
1661 void btree_iterator<N, R, P>::increment_slow() {
1663 assert(position >= node->count());
1664 self_type save(*
this);
1665 while (position == node->count() && !node->is_root()) {
1666 assert(node->parent()->child(node->position()) == node);
1667 position = node->position();
1668 node = node->parent();
1670 if (position == node->count()) {
1674 assert(position < node->
count());
1675 node = node->child(position + 1);
1676 while (!node->leaf()) {
1677 node = node->child(0);
1683 template <
typename N,
typename R,
typename P>
1684 void btree_iterator<N, R, P>::increment_by(
int count) {
1687 int rest = node->count() - position;
1689 count = count - rest;
1690 if (position < node->
count()) {
1700 template <
typename N,
typename R,
typename P>
1701 void btree_iterator<N, R, P>::decrement_slow() {
1703 assert(position <= -1);
1704 self_type save(*
this);
1705 while (position < 0 && !node->is_root()) {
1706 assert(node->parent()->child(node->position()) == node);
1707 position = node->position() - 1;
1708 node = node->parent();
1714 assert(position >= 0);
1715 node = node->child(position);
1716 while (!node->leaf()) {
1717 node = node->child(node->count());
1719 position = node->count() - 1;
1725 template <
typename P>
1726 btree<P>::btree(
const key_compare &comp,
const allocator_type &alloc)
1727 : key_compare(comp),
1728 root_(alloc,
NULL) {
1731 template <
typename P>
1732 btree<P>::btree(
const self_type &x)
1734 root_(x.internal_allocator(),
NULL) {
1738 template <
typename P>
template <
typename ValuePo
inter>
1740 btree<P>::insert_unique(
const key_type &key, ValuePointer value) {
1742 *mutable_root() = new_leaf_root_node(1);
1746 iterator &iter = res.
first;
1747 if (res.
second == kExactMatch) {
1749 return make_bpair(internal_last(iter),
false);
1750 }
else if (!res.
second) {
1751 iterator last = internal_last(iter);
1752 if (last.node && !compare_keys(key, last.key())) {
1758 return make_bpair(internal_insert(iter, *value),
true);
1761 template <
typename P>
1762 inline typename btree<P>::iterator
1763 btree<P>::insert_unique(iterator position,
const value_type &v) {
1765 const key_type &key = params_type::key(v);
1766 if (position ==
end() || compare_keys(key, position.key())) {
1767 iterator prev = position;
1768 if (position ==
begin() || compare_keys((--prev).key(), key)) {
1770 return internal_insert(position, v);
1772 }
else if (compare_keys(position.key(), key)) {
1773 iterator next = position;
1775 if (next ==
end() || compare_keys(key, next.key())) {
1777 return internal_insert(next, v);
1784 return insert_unique(v).first;
1787 template <
typename P>
template <
typename InputIterator>
1788 void btree<P>::insert_unique(InputIterator b, InputIterator e) {
1789 for (; b != e; ++b) {
1790 insert_unique(
end(), *b);
1794 template <
typename P>
template <
typename ValuePo
inter>
1795 typename btree<P>::iterator
1796 btree<P>::insert_multi(
const key_type &key, ValuePointer value) {
1798 *mutable_root() = new_leaf_root_node(1);
1801 iterator iter = internal_upper_bound(key, iterator(root(), 0));
1805 return internal_insert(iter, *value);
1808 template <
typename P>
1809 typename btree<P>::iterator
1810 btree<P>::insert_multi(iterator position,
const value_type &v) {
1812 const key_type &key = params_type::key(v);
1813 if (position ==
end() || !compare_keys(position.key(), key)) {
1814 iterator prev = position;
1815 if (position ==
begin() || !compare_keys(key, (--prev).key())) {
1817 return internal_insert(position, v);
1820 iterator next = position;
1822 if (next ==
end() || !compare_keys(next.key(), key)) {
1824 return internal_insert(next, v);
1828 return insert_multi(v);
1831 template <
typename P>
template <
typename InputIterator>
1832 void btree<P>::insert_multi(InputIterator b, InputIterator e) {
1833 for (; b != e; ++b) {
1834 insert_multi(
end(), *b);
1838 template <
typename P>
1839 void btree<P>::assign(
const self_type &x) {
1842 *mutable_key_comp() = x.key_comp();
1843 *mutable_internal_allocator() = x.internal_allocator();
1847 for (const_iterator iter = x.begin(); iter != x.end(); ++iter) {
1849 insert_multi(*iter);
1853 internal_insert(
end(), *iter);
1858 template <
typename P>
1860 bool internal_delete =
false;
1861 if (!iter.node->leaf()) {
1864 iterator tmp_iter(iter--);
1865 assert(iter.node->leaf());
1866 assert(!compare_keys(tmp_iter.key(), iter.key()));
1867 iter.node->value_swap(iter.position, tmp_iter.node, tmp_iter.position);
1868 internal_delete =
true;
1870 }
else if (!root()->leaf()) {
1875 iter.node->remove_value(iter.position);
1887 if (iter.node == root()) {
1894 if (iter.node->count() >= kMinNodeValues) {
1897 bool merged = try_merge_or_rebalance(&iter);
1898 if (iter.node->leaf()) {
1904 iter.node = iter.node->parent();
1909 if (res.position == res.node->count()) {
1910 res.position = res.node->count() - 1;
1914 if (internal_delete) {
1920 template <
typename P>
1922 int count = (int) std::distance(begin, end);
1923 for (
int i = 0; i <
count; i++) {
1924 begin =
erase(begin);
1929 template <
typename P>
1930 int btree<P>::erase_unique(
const key_type &key) {
1931 iterator iter = internal_find_unique(key, iterator(root(), 0));
1940 template <
typename P>
1941 int btree<P>::erase_multi(
const key_type &key) {
1942 iterator begin = internal_lower_bound(key, iterator(root(), 0));
1948 iterator end = internal_end(
1949 internal_upper_bound(key, iterator(root(), 0)));
1950 return erase(begin, end);
1953 template <
typename P>
1955 if (root() !=
NULL) {
1956 internal_clear(root());
1958 *mutable_root() =
NULL;
1961 template <
typename P>
1963 std::swap(static_cast<key_compare&>(*
this), static_cast<key_compare&>(x));
1967 template <
typename P>
1968 void btree<P>::verify()
const {
1969 if (root() !=
NULL) {
1971 assert(leftmost() == (++const_iterator(root(), -1)).node);
1972 assert(rightmost() == (--const_iterator(root(), root()->
count())).node);
1973 assert(leftmost()->leaf());
1974 assert(rightmost()->leaf());
1976 assert(
size() == 0);
1977 assert(leftmost() ==
NULL);
1978 assert(rightmost() ==
NULL);
1982 template <
typename P>
1983 void btree<P>::rebalance_or_split(iterator *iter) {
1984 node_type *&node = iter->node;
1985 int &insert_position = iter->position;
1986 assert(node->count() == node->max_count());
1989 node_type *parent = node->parent();
1990 if (node != root()) {
1991 if (node->position() > 0) {
1993 node_type *left = parent->child(node->position() - 1);
1994 if (left->count() < left->max_count()) {
1998 int to_move = (left->max_count() - left->count()) /
1999 (1 + (insert_position < left->max_count()));
2002 if (((insert_position - to_move) >= 0) ||
2003 ((left->count() + to_move) < left->max_count())) {
2004 left->rebalance_right_to_left(node, to_move);
2006 assert(node->max_count() - node->count() == to_move);
2007 insert_position = insert_position - to_move;
2008 if (insert_position < 0) {
2009 insert_position = insert_position + left->count() + 1;
2013 assert(node->count() < node->max_count());
2019 if (node->position() < parent->count()) {
2021 node_type *right = parent->child(node->position() + 1);
2022 if (right->count() < right->max_count()) {
2026 int to_move = (right->max_count() - right->count()) /
2027 (1 + (insert_position > 0));
2030 if ((insert_position <= (node->count() - to_move)) ||
2031 ((right->count() + to_move) < right->max_count())) {
2032 node->rebalance_left_to_right(right, to_move);
2034 if (insert_position > node->count()) {
2035 insert_position = insert_position - node->count() - 1;
2039 assert(node->count() < node->max_count());
2047 if (parent->count() == parent->max_count()) {
2048 iterator parent_iter(node->parent(), node->position());
2049 rebalance_or_split(&parent_iter);
2053 if (root()->leaf()) {
2056 parent = new_internal_root_node();
2057 parent->set_child(0, root());
2058 *mutable_root() = parent;
2059 assert(*mutable_rightmost() == parent->child(0));
2065 parent = new_internal_node(parent);
2066 parent->set_child(0, parent);
2067 parent->swap(root());
2073 node_type *split_node;
2075 split_node = new_leaf_node(parent);
2076 node->split(split_node, insert_position);
2077 if (rightmost() == node) {
2078 *mutable_rightmost() = split_node;
2081 split_node = new_internal_node(parent);
2082 node->split(split_node, insert_position);
2085 if (insert_position > node->count()) {
2086 insert_position = insert_position - node->count() - 1;
2091 template <
typename P>
2092 void btree<P>::merge_nodes(node_type *left, node_type *right) {
2094 if (right->leaf()) {
2095 if (rightmost() == right) {
2096 *mutable_rightmost() = left;
2098 delete_leaf_node(right);
2100 delete_internal_node(right);
2104 template <
typename P>
2105 bool btree<P>::try_merge_or_rebalance(iterator *iter) {
2106 node_type *parent = iter->node->parent();
2107 if (iter->node->position() > 0) {
2109 node_type *left = parent->child(iter->node->position() - 1);
2110 if ((1 + left->count() + iter->node->count()) <= left->max_count()) {
2111 iter->position += 1 + left->count();
2112 merge_nodes(left, iter->node);
2117 if (iter->node->position() < parent->count()) {
2119 node_type *right = parent->child(iter->node->position() + 1);
2120 if ((1 + iter->node->count() + right->count()) <= right->max_count()) {
2121 merge_nodes(iter->node, right);
2128 if ((right->count() > kMinNodeValues) &&
2129 ((iter->node->count() == 0) ||
2130 (iter->position > 0))) {
2131 int to_move = (right->count() - iter->node->count()) / 2;
2132 to_move =
std::min(to_move, right->count() - 1);
2133 iter->node->rebalance_right_to_left(right, to_move);
2137 if (iter->node->position() > 0) {
2142 node_type *left = parent->child(iter->node->position() - 1);
2143 if ((left->count() > kMinNodeValues) &&
2144 ((iter->node->count() == 0) ||
2145 (iter->position < iter->node->count()))) {
2146 int to_move = (left->count() - iter->node->count()) / 2;
2147 to_move =
std::min(to_move, left->count() - 1);
2148 left->rebalance_left_to_right(iter->node, to_move);
2149 iter->position += to_move;
2156 template <
typename P>
2157 void btree<P>::try_shrink() {
2158 if (root()->
count() > 0) {
2162 if (root()->leaf()) {
2163 assert(
size() == 0);
2164 delete_leaf_node(root());
2165 *mutable_root() =
NULL;
2167 node_type *child = root()->child(0);
2168 if (child->leaf()) {
2171 delete_internal_root_node();
2172 *mutable_root() = child;
2177 child->swap(root());
2178 delete_internal_node(child);
2183 template <
typename P>
template <
typename IterType>
2184 inline IterType btree<P>::internal_last(IterType iter) {
2185 while (iter.node && iter.position == iter.node->count()) {
2186 iter.position = iter.node->position();
2187 iter.node = iter.node->parent();
2188 if (iter.node->leaf()) {
2195 template <
typename P>
2196 inline typename btree<P>::iterator
2197 btree<P>::internal_insert(iterator iter,
const value_type &v) {
2198 if (!iter.node->leaf()) {
2204 if (iter.node->count() == iter.node->max_count()) {
2206 if (iter.node->max_count() < kNodeValues) {
2209 assert(iter.node == root());
2210 iter.node = new_leaf_root_node(
2211 std::min<int>(kNodeValues, 2 * iter.node->max_count()));
2212 iter.node->swap(root());
2213 delete_leaf_node(root());
2214 *mutable_root() = iter.node;
2216 rebalance_or_split(&iter);
2219 }
else if (!root()->leaf()) {
2222 iter.node->insert_value(iter.position, v);
2226 template <
typename P>
template <
typename IterType>
2228 const key_type &key, IterType iter)
const {
2229 return internal_locate_type::dispatch(key, *
this, iter);
2232 template <
typename P>
template <
typename IterType>
2234 const key_type &key, IterType iter)
const {
2236 iter.position = iter.node->lower_bound(key,
key_comp());
2237 if (iter.node->leaf()) {
2240 iter.node = iter.node->child(iter.position);
2245 template <
typename P>
template <
typename IterType>
2247 const key_type &key, IterType iter)
const {
2249 int res = iter.node->lower_bound(key,
key_comp());
2250 iter.position = res & kMatchMask;
2251 if (res & kExactMatch) {
2252 return make_bpair(iter, static_cast<int>(kExactMatch));
2254 if (iter.node->leaf()) {
2257 iter.node = iter.node->child(iter.position);
2262 template <
typename P>
template <
typename IterType>
2263 IterType btree<P>::internal_lower_bound(
2264 const key_type &key, IterType iter)
const {
2268 iter.node->lower_bound(key,
key_comp()) & kMatchMask;
2269 if (iter.node->leaf()) {
2272 iter.node = iter.node->child(iter.position);
2274 iter = internal_last(iter);
2279 template <
typename P>
template <
typename IterType>
2280 IterType btree<P>::internal_upper_bound(
2281 const key_type &key, IterType iter)
const {
2284 iter.position = iter.node->upper_bound(key,
key_comp());
2285 if (iter.node->leaf()) {
2288 iter.node = iter.node->child(iter.position);
2290 iter = internal_last(iter);
2295 template <
typename P>
template <
typename IterType>
2296 IterType btree<P>::internal_find_unique(
2297 const key_type &key, IterType iter)
const {
2300 if (res.
second == kExactMatch) {
2304 iter = internal_last(res.
first);
2305 if (iter.node && !compare_keys(key, iter.key())) {
2310 return IterType(
NULL, 0);
2313 template <
typename P>
template <
typename IterType>
2314 IterType btree<P>::internal_find_multi(
2315 const key_type &key, IterType iter)
const {
2317 iter = internal_lower_bound(key, iter);
2319 iter = internal_last(iter);
2320 if (iter.node && !compare_keys(key, iter.key())) {
2325 return IterType(
NULL, 0);
2328 template <
typename P>
2329 void btree<P>::internal_clear(node_type *node) {
2330 if (!node->leaf()) {
2331 for (
int i = 0; i <= node->count(); ++i) {
2332 internal_clear(node->child(i));
2334 if (node == root()) {
2335 delete_internal_root_node();
2337 delete_internal_node(node);
2340 delete_leaf_node(node);
2344 #if defined COMPILE_BTREE_DUMP
2345 template <
typename P>
2346 void btree<P>::internal_dump(
2347 std::ostream &os,
const node_type *node,
int level)
const {
2348 for (
int i = 0; i < node->count(); ++i) {
2349 if (!node->leaf()) {
2350 internal_dump(os, node->child(i), level + 1);
2352 for (
int j = 0; j < level; ++j) {
2355 os << node->key(i) <<
" [" << level <<
"]\n";
2357 if (!node->leaf()) {
2358 internal_dump(os, node->child(node->count()), level + 1);
2363 template <
typename P>
2364 int btree<P>::internal_verify(
2365 const node_type *node,
const key_type *lo,
const key_type *hi)
const {
2366 assert(node->count() > 0);
2367 assert(node->count() <= node->max_count());
2369 assert(!compare_keys(node->key(0), *lo));
2372 assert(!compare_keys(*hi, node->key(node->count() - 1)));
2374 for (
int i = 1; i < node->count(); ++i) {
2375 assert(!compare_keys(node->key(i), node->key(i - 1)));
2377 int count = node->count();
2378 if (!node->leaf()) {
2379 for (
int i = 0; i <= node->count(); ++i) {
2380 assert(node->child(i) !=
NULL);
2381 assert(node->child(i)->parent() == node);
2382 assert(node->child(i)->position() == i);
2383 count += internal_verify(
2385 (i == 0) ? lo : &node->key(i - 1),
2386 (i == node->count()) ? hi : &node->key(i));
2394 #pragma pop_macro ("min")
2395 #pragma pop_macro ("max")
2397 #endif // BENTLEY_UTIL_BTREE_BTREE_H__
bool empty() const
Definition: stdcxx/bstdmap.h:210
reverse_iterator rend()
Definition: stdcxx/bstdmap.h:202
iterator lower_bound(const key_type &__x)
Definition: stdcxx/bstdmap.h:281
void operator+=(DPoint3d &point, DVec3d const &vector)
operator overload for in-place addition of a point plus a vector
#define min(x, y)
Definition: MathUtils.h:21
first_type first
Definition: bpair.h:78
iterator begin()
Definition: stdcxx/bstdmap.h:178
iterator upper_bound(const key_type &__x)
Definition: stdcxx/bstdmap.h:285
iterator end()
Definition: stdcxx/bstdmap.h:186
key_compare key_comp() const
Definition: stdcxx/bstdmap.h:261
size_type count(const key_type &__x) const
Definition: stdcxx/bstdmap.h:277
void swap(basic_string< _CharT, _Traits, _Allocator > &__a, basic_string< _CharT, _Traits, _Allocator > &__b)
Definition: basic_string.h:1396
bpair< iterator, iterator > equal_range(const key_type &__x)
Definition: stdcxx/bstdmap.h:297
iterator erase(iterator __it)
Definition: stdcxx/bstdmap.h:242
#define NULL
Definition: Bentley.h:157
bstdmap & operator=(const bstdmap &__rhs)
Definition: stdcxx/bstdmap.h:170
#define BEGIN_BENTLEY_NAMESPACE
Definition: Bentley.r.h:24
#define max(x, y)
Definition: MathUtils.h:24
A template that has many of the capabilities of std::pair.
Definition: bpair.h:73
size_type max_size() const
Definition: stdcxx/bstdmap.h:218
bpair< _TypeT, _TypeU > make_bpair(_TypeT __x, _TypeU __y)
Definition: bpair.h:177
second_type second
Definition: bpair.h:79
DVec3d operator*(Transform const &transform, DVec3d const &vector)
operator overload for multiplication of a transform and a vector li>The vector appears on the left as...
bool operator!=(const BentleyAllocator< _Ty > &, const BentleyAllocator< _Other > &)
Definition: BentleyAllocator.h:152
Bstdcxx::basic_string< wchar_t, std::char_traits< wchar_t >, BentleyAllocator< wchar_t > > bwstring
Definition: WString.h:23
unsigned short uint16_t
Definition: Bentley.r.h:91
#define END_BENTLEY_NAMESPACE
Definition: Bentley.r.h:25
void clear()
Definition: stdcxx/bstdmap.h:257
reverse_iterator rbegin()
Definition: stdcxx/bstdmap.h:194
size_type size() const
Definition: stdcxx/bstdmap.h:214
Bstdcxx::basic_string< char, std::char_traits< char >, BentleyAllocator< char > > bastring
Definition: WString.h:22
unsigned char uint8_t
Definition: Bentley.r.h:89
bool operator==(const BentleyAllocator< _Ty > &, const BentleyAllocator< _Other > &)
Definition: BentleyAllocator.h:146