"Fossies" - the Fresh Open Source Software Archive

Member "xdelta3-3.1.0/cpp-btree/btree.h" (26 Sep 2015, 82081 Bytes) of package /linux/misc/xdelta3-3.1.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "btree.h" see the Fossies "Dox" file reference documentation.

    1 // Copyright 2013 Google Inc. All Rights Reserved.
    2 //
    3 // Licensed under the Apache License, Version 2.0 (the "License");
    4 // you may not use this file except in compliance with the License.
    5 // You may obtain a copy of the License at
    6 //
    7 //     http://www.apache.org/licenses/LICENSE-2.0
    8 //
    9 // Unless required by applicable law or agreed to in writing, software
   10 // distributed under the License is distributed on an "AS IS" BASIS,
   11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   12 // See the License for the specific language governing permissions and
   13 // limitations under the License.
   14 //
   15 // A btree implementation of the STL set and map interfaces. A btree is both
   16 // smaller and faster than STL set/map. The red-black tree implementation of
   17 // STL set/map has an overhead of 3 pointers (left, right and parent) plus the
   18 // node color information for each stored value. So a set<int32> consumes 20
   19 // bytes for each value stored. This btree implementation stores multiple
   20 // values on fixed size nodes (usually 256 bytes) and doesn't store child
   21 // pointers for leaf nodes. The result is that a btree_set<int32> may use much
   22 // less memory per stored value. For the random insertion benchmark in
   23 // btree_test.cc, a btree_set<int32> with node-size of 256 uses 4.9 bytes per
   24 // stored value.
   25 //
   26 // The packing of multiple values on to each node of a btree has another effect
   27 // besides better space utilization: better cache locality due to fewer cache
   28 // lines being accessed. Better cache locality translates into faster
   29 // operations.
   30 //
   31 // CAVEATS
   32 //
   33 // Insertions and deletions on a btree can cause splitting, merging or
   34 // rebalancing of btree nodes. And even without these operations, insertions
   35 // and deletions on a btree will move values around within a node. In both
   36 // cases, the result is that insertions and deletions can invalidate iterators
   37 // pointing to values other than the one being inserted/deleted. This is
   38 // notably different from STL set/map which takes care to not invalidate
   39 // iterators on insert/erase except, of course, for iterators pointing to the
   40 // value being erased.  A partial workaround when erasing is available:
   41 // erase() returns an iterator pointing to the item just after the one that was
   42 // erased (or end() if none exists).  See also safe_btree.
   43 
   44 // PERFORMANCE
   45 //
   46 //   btree_bench --benchmarks=. 2>&1 | ./benchmarks.awk
   47 //
   48 // Run on pmattis-warp.nyc (4 X 2200 MHz CPUs); 2010/03/04-15:23:06
   49 // Benchmark                 STL(ns) B-Tree(ns) @    <size>
   50 // --------------------------------------------------------
   51 // BM_set_int32_insert        1516      608  +59.89%  <256>    [40.0,  5.2]
   52 // BM_set_int32_lookup        1160      414  +64.31%  <256>    [40.0,  5.2]
   53 // BM_set_int32_fulllookup     960      410  +57.29%  <256>    [40.0,  4.4]
   54 // BM_set_int32_delete        1741      528  +69.67%  <256>    [40.0,  5.2]
   55 // BM_set_int32_queueaddrem   3078     1046  +66.02%  <256>    [40.0,  5.5]
   56 // BM_set_int32_mixedaddrem   3600     1384  +61.56%  <256>    [40.0,  5.3]
   57 // BM_set_int32_fifo           227      113  +50.22%  <256>    [40.0,  4.4]
   58 // BM_set_int32_fwditer        158       26  +83.54%  <256>    [40.0,  5.2]
   59 // BM_map_int32_insert        1551      636  +58.99%  <256>    [48.0, 10.5]
   60 // BM_map_int32_lookup        1200      508  +57.67%  <256>    [48.0, 10.5]
   61 // BM_map_int32_fulllookup     989      487  +50.76%  <256>    [48.0,  8.8]
   62 // BM_map_int32_delete        1794      628  +64.99%  <256>    [48.0, 10.5]
   63 // BM_map_int32_queueaddrem   3189     1266  +60.30%  <256>    [48.0, 11.6]
   64 // BM_map_int32_mixedaddrem   3822     1623  +57.54%  <256>    [48.0, 10.9]
   65 // BM_map_int32_fifo           151      134  +11.26%  <256>    [48.0,  8.8]
   66 // BM_map_int32_fwditer        161       32  +80.12%  <256>    [48.0, 10.5]
   67 // BM_set_int64_insert        1546      636  +58.86%  <256>    [40.0, 10.5]
   68 // BM_set_int64_lookup        1200      512  +57.33%  <256>    [40.0, 10.5]
   69 // BM_set_int64_fulllookup     971      487  +49.85%  <256>    [40.0,  8.8]
   70 // BM_set_int64_delete        1745      616  +64.70%  <256>    [40.0, 10.5]
   71 // BM_set_int64_queueaddrem   3163     1195  +62.22%  <256>    [40.0, 11.6]
   72 // BM_set_int64_mixedaddrem   3760     1564  +58.40%  <256>    [40.0, 10.9]
   73 // BM_set_int64_fifo           146      103  +29.45%  <256>    [40.0,  8.8]
   74 // BM_set_int64_fwditer        162       31  +80.86%  <256>    [40.0, 10.5]
   75 // BM_map_int64_insert        1551      720  +53.58%  <256>    [48.0, 20.7]
   76 // BM_map_int64_lookup        1214      612  +49.59%  <256>    [48.0, 20.7]
   77 // BM_map_int64_fulllookup     994      592  +40.44%  <256>    [48.0, 17.2]
   78 // BM_map_int64_delete        1778      764  +57.03%  <256>    [48.0, 20.7]
   79 // BM_map_int64_queueaddrem   3189     1547  +51.49%  <256>    [48.0, 20.9]
   80 // BM_map_int64_mixedaddrem   3779     1887  +50.07%  <256>    [48.0, 21.6]
   81 // BM_map_int64_fifo           147      145   +1.36%  <256>    [48.0, 17.2]
   82 // BM_map_int64_fwditer        162       41  +74.69%  <256>    [48.0, 20.7]
   83 // BM_set_string_insert       1989     1966   +1.16%  <256>    [64.0, 44.5]
   84 // BM_set_string_lookup       1709     1600   +6.38%  <256>    [64.0, 44.5]
   85 // BM_set_string_fulllookup   1573     1529   +2.80%  <256>    [64.0, 35.4]
   86 // BM_set_string_delete       2520     1920  +23.81%  <256>    [64.0, 44.5]
   87 // BM_set_string_queueaddrem  4706     4309   +8.44%  <256>    [64.0, 48.3]
   88 // BM_set_string_mixedaddrem  5080     4654   +8.39%  <256>    [64.0, 46.7]
   89 // BM_set_string_fifo          318      512  -61.01%  <256>    [64.0, 35.4]
   90 // BM_set_string_fwditer       182       93  +48.90%  <256>    [64.0, 44.5]
   91 // BM_map_string_insert       2600     2227  +14.35%  <256>    [72.0, 55.8]
   92 // BM_map_string_lookup       2068     1730  +16.34%  <256>    [72.0, 55.8]
   93 // BM_map_string_fulllookup   1859     1618  +12.96%  <256>    [72.0, 44.0]
   94 // BM_map_string_delete       3168     2080  +34.34%  <256>    [72.0, 55.8]
   95 // BM_map_string_queueaddrem  5840     4701  +19.50%  <256>    [72.0, 59.4]
   96 // BM_map_string_mixedaddrem  6400     5200  +18.75%  <256>    [72.0, 57.8]
   97 // BM_map_string_fifo          398      596  -49.75%  <256>    [72.0, 44.0]
   98 // BM_map_string_fwditer       243      113  +53.50%  <256>    [72.0, 55.8]
   99 
  100 #ifndef UTIL_BTREE_BTREE_H__
  101 #define UTIL_BTREE_BTREE_H__
  102 
  103 #include <assert.h>
  104 #include <stddef.h>
  105 #include <string.h>
  106 #include <sys/types.h>
  107 #include <algorithm>
  108 #include <functional>
  109 #include <iostream>
  110 #include <iterator>
  111 #include <limits>
  112 #include <type_traits>
  113 #include <new>
  114 #include <ostream>
  115 #include <string>
  116 #include <utility>
  117 
  118 #ifndef NDEBUG
  119 #define NDEBUG 1
  120 #endif
  121 
  122 namespace btree {
  123 
  124 // Inside a btree method, if we just call swap(), it will choose the
  125 // btree::swap method, which we don't want. And we can't say ::swap
  126 // because then MSVC won't pickup any std::swap() implementations. We
  127 // can't just use std::swap() directly because then we don't get the
  128 // specialization for types outside the std namespace. So the solution
  129 // is to have a special swap helper function whose name doesn't
  130 // collide with other swap functions defined by the btree classes.
  131 template <typename T>
  132 inline void btree_swap_helper(T &a, T &b) {
  133   using std::swap;
  134   swap(a, b);
  135 }
  136 
  137 // A template helper used to select A or B based on a condition.
  138 template<bool cond, typename A, typename B>
  139 struct if_{
  140   typedef A type;
  141 };
  142 
  143 template<typename A, typename B>
  144 struct if_<false, A, B> {
  145   typedef B type;
  146 };
  147 
  148 // Types small_ and big_ are promise that sizeof(small_) < sizeof(big_)
  149 typedef char small_;
  150 
  151 struct big_ {
  152   char dummy[2];
  153 };
  154 
  155 // A compile-time assertion.
  156 template <bool>
  157 struct CompileAssert {
  158 };
  159 
  160 #define COMPILE_ASSERT(expr, msg) \
  161   typedef CompileAssert<(bool(expr))> msg[bool(expr) ? 1 : -1]
  162 
  163 // A helper type used to indicate that a key-compare-to functor has been
  164 // provided. A user can specify a key-compare-to functor by doing:
  165 //
  166 //  struct MyStringComparer
  167 //      : public util::btree::btree_key_compare_to_tag {
  168 //    int operator()(const string &a, const string &b) const {
  169 //      return a.compare(b);
  170 //    }
  171 //  };
  172 //
  173 // Note that the return type is an int and not a bool. There is a
  174 // COMPILE_ASSERT which enforces this return type.
  175 struct btree_key_compare_to_tag {
  176 };
  177 
  178 // A helper class that indicates if the Compare parameter is derived from
  179 // btree_key_compare_to_tag.
  180 template <typename Compare>
  181 struct btree_is_key_compare_to
  182     : public std::is_convertible<Compare, btree_key_compare_to_tag> {
  183 };
  184 
  185 // A helper class to convert a boolean comparison into a three-way
  186 // "compare-to" comparison that returns a negative value to indicate
  187 // less-than, zero to indicate equality and a positive value to
  188 // indicate greater-than. This helper class is specialized for
  189 // less<string> and greater<string>. The btree_key_compare_to_adapter
  190 // class is provided so that btree users automatically get the more
  191 // efficient compare-to code when using common google string types
  192 // with common comparison functors.
  193 template <typename Compare>
  194 struct btree_key_compare_to_adapter : Compare {
  195   btree_key_compare_to_adapter() { }
  196   btree_key_compare_to_adapter(const Compare &c) : Compare(c) { }
  197   btree_key_compare_to_adapter(const btree_key_compare_to_adapter<Compare> &c)
  198       : Compare(c) {
  199   }
  200 };
  201 
  202 template <>
  203 struct btree_key_compare_to_adapter<std::less<std::string> >
  204     : public btree_key_compare_to_tag {
  205   btree_key_compare_to_adapter() {}
  206   btree_key_compare_to_adapter(const std::less<std::string>&) {}
  207   btree_key_compare_to_adapter(
  208       const btree_key_compare_to_adapter<std::less<std::string> >&) {}
  209   int operator()(const std::string &a, const std::string &b) const {
  210     return a.compare(b);
  211   }
  212 };
  213 
  214 template <>
  215 struct btree_key_compare_to_adapter<std::greater<std::string> >
  216     : public btree_key_compare_to_tag {
  217   btree_key_compare_to_adapter() {}
  218   btree_key_compare_to_adapter(const std::greater<std::string>&) {}
  219   btree_key_compare_to_adapter(
  220       const btree_key_compare_to_adapter<std::greater<std::string> >&) {}
  221   int operator()(const std::string &a, const std::string &b) const {
  222     return b.compare(a);
  223   }
  224 };
  225 
  226 // A helper class that allows a compare-to functor to behave like a plain
  227 // compare functor. This specialization is used when we do not have a
  228 // compare-to functor.
  229 template <typename Key, typename Compare, bool HaveCompareTo>
  230 struct btree_key_comparer {
  231   btree_key_comparer() {}
  232   btree_key_comparer(Compare c) : comp(c) {}
  233   static bool bool_compare(const Compare &comp, const Key &x, const Key &y) {
  234     return comp(x, y);
  235   }
  236   bool operator()(const Key &x, const Key &y) const {
  237     return bool_compare(comp, x, y);
  238   }
  239   Compare comp;
  240 };
  241 
  242 // A specialization of btree_key_comparer when a compare-to functor is
  243 // present. We need a plain (boolean) comparison in some parts of the btree
  244 // code, such as insert-with-hint.
  245 template <typename Key, typename Compare>
  246 struct btree_key_comparer<Key, Compare, true> {
  247   btree_key_comparer() {}
  248   btree_key_comparer(Compare c) : comp(c) {}
  249   static bool bool_compare(const Compare &comp, const Key &x, const Key &y) {
  250     return comp(x, y) < 0;
  251   }
  252   bool operator()(const Key &x, const Key &y) const {
  253     return bool_compare(comp, x, y);
  254   }
  255   Compare comp;
  256 };
  257 
  258 // A helper function to compare to keys using the specified compare
  259 // functor. This dispatches to the appropriate btree_key_comparer comparison,
  260 // depending on whether we have a compare-to functor or not (which depends on
  261 // whether Compare is derived from btree_key_compare_to_tag).
  262 template <typename Key, typename Compare>
  263 static bool btree_compare_keys(
  264     const Compare &comp, const Key &x, const Key &y) {
  265   typedef btree_key_comparer<Key, Compare,
  266       btree_is_key_compare_to<Compare>::value> key_comparer;
  267   return key_comparer::bool_compare(comp, x, y);
  268 }
  269 
  270 template <typename Key, typename Compare,
  271           typename Alloc, int TargetNodeSize, int ValueSize>
  272 struct btree_common_params {
  273   // If Compare is derived from btree_key_compare_to_tag then use it as the
  274   // key_compare type. Otherwise, use btree_key_compare_to_adapter<> which will
  275   // fall-back to Compare if we don't have an appropriate specialization.
  276   typedef typename if_<
  277     btree_is_key_compare_to<Compare>::value,
  278     Compare, btree_key_compare_to_adapter<Compare> >::type key_compare;
  279   // A type which indicates if we have a key-compare-to functor or a plain old
  280   // key-compare functor.
  281   typedef btree_is_key_compare_to<key_compare> is_key_compare_to;
  282 
  283   typedef Alloc allocator_type;
  284   typedef Key key_type;
  285   typedef ssize_t size_type;
  286   typedef ptrdiff_t difference_type;
  287 
  288   enum {
  289     kTargetNodeSize = TargetNodeSize,
  290 
  291     // Available space for values.  This is largest for leaf nodes,
  292     // which has overhead no fewer than two pointers.
  293     kNodeValueSpace = TargetNodeSize - 2 * sizeof(void*),
  294   };
  295 
  296   // This is an integral type large enough to hold as many
  297   // ValueSize-values as will fit a node of TargetNodeSize bytes.
  298   typedef typename if_<
  299     (kNodeValueSpace / ValueSize) >= 256,
  300     uint16_t,
  301     uint8_t>::type node_count_type;
  302 };
  303 
  304 // A parameters structure for holding the type parameters for a btree_map.
  305 template <typename Key, typename Data, typename Compare,
  306           typename Alloc, int TargetNodeSize>
  307 struct btree_map_params
  308     : public btree_common_params<Key, Compare, Alloc, TargetNodeSize,
  309                                  sizeof(Key) + sizeof(Data)> {
  310   typedef Data data_type;
  311   typedef Data mapped_type;
  312   typedef std::pair<const Key, data_type> value_type;
  313   typedef std::pair<Key, data_type> mutable_value_type;
  314   typedef value_type* pointer;
  315   typedef const value_type* const_pointer;
  316   typedef value_type& reference;
  317   typedef const value_type& const_reference;
  318 
  319   enum {
  320     kValueSize = sizeof(Key) + sizeof(data_type),
  321   };
  322 
  323   static const Key& key(const value_type &x) { return x.first; }
  324   static const Key& key(const mutable_value_type &x) { return x.first; }
  325   static void swap(mutable_value_type *a, mutable_value_type *b) {
  326     btree_swap_helper(a->first, b->first);
  327     btree_swap_helper(a->second, b->second);
  328   }
  329 };
  330 
  331 // A parameters structure for holding the type parameters for a btree_set.
  332 template <typename Key, typename Compare, typename Alloc, int TargetNodeSize>
  333 struct btree_set_params
  334     : public btree_common_params<Key, Compare, Alloc, TargetNodeSize,
  335                                  sizeof(Key)> {
  336   typedef std::false_type data_type;
  337   typedef std::false_type mapped_type;
  338   typedef Key value_type;
  339   typedef value_type mutable_value_type;
  340   typedef value_type* pointer;
  341   typedef const value_type* const_pointer;
  342   typedef value_type& reference;
  343   typedef const value_type& const_reference;
  344 
  345   enum {
  346     kValueSize = sizeof(Key),
  347   };
  348 
  349   static const Key& key(const value_type &x) { return x; }
  350   static void swap(mutable_value_type *a, mutable_value_type *b) {
  351     btree_swap_helper<mutable_value_type>(*a, *b);
  352   }
  353 };
  354 
  355 // An adapter class that converts a lower-bound compare into an upper-bound
  356 // compare.
  357 template <typename Key, typename Compare>
  358 struct btree_upper_bound_adapter : public Compare {
  359   btree_upper_bound_adapter(Compare c) : Compare(c) {}
  360   bool operator()(const Key &a, const Key &b) const {
  361     return !static_cast<const Compare&>(*this)(b, a);
  362   }
  363 };
  364 
  365 template <typename Key, typename CompareTo>
  366 struct btree_upper_bound_compare_to_adapter : public CompareTo {
  367   btree_upper_bound_compare_to_adapter(CompareTo c) : CompareTo(c) {}
  368   int operator()(const Key &a, const Key &b) const {
  369     return static_cast<const CompareTo&>(*this)(b, a);
  370   }
  371 };
  372 
  373 // Dispatch helper class for using linear search with plain compare.
  374 template <typename K, typename N, typename Compare>
  375 struct btree_linear_search_plain_compare {
  376   static int lower_bound(const K &k, const N &n, Compare comp)  {
  377     return n.linear_search_plain_compare(k, 0, n.count(), comp);
  378   }
  379   static int upper_bound(const K &k, const N &n, Compare comp)  {
  380     typedef btree_upper_bound_adapter<K, Compare> upper_compare;
  381     return n.linear_search_plain_compare(k, 0, n.count(), upper_compare(comp));
  382   }
  383 };
  384 
  385 // Dispatch helper class for using linear search with compare-to
  386 template <typename K, typename N, typename CompareTo>
  387 struct btree_linear_search_compare_to {
  388   static int lower_bound(const K &k, const N &n, CompareTo comp)  {
  389     return n.linear_search_compare_to(k, 0, n.count(), comp);
  390   }
  391   static int upper_bound(const K &k, const N &n, CompareTo comp)  {
  392     typedef btree_upper_bound_adapter<K,
  393         btree_key_comparer<K, CompareTo, true> > upper_compare;
  394     return n.linear_search_plain_compare(k, 0, n.count(), upper_compare(comp));
  395   }
  396 };
  397 
  398 // Dispatch helper class for using binary search with plain compare.
  399 template <typename K, typename N, typename Compare>
  400 struct btree_binary_search_plain_compare {
  401   static int lower_bound(const K &k, const N &n, Compare comp)  {
  402     return n.binary_search_plain_compare(k, 0, n.count(), comp);
  403   }
  404   static int upper_bound(const K &k, const N &n, Compare comp)  {
  405     typedef btree_upper_bound_adapter<K, Compare> upper_compare;
  406     return n.binary_search_plain_compare(k, 0, n.count(), upper_compare(comp));
  407   }
  408 };
  409 
  410 // Dispatch helper class for using binary search with compare-to.
  411 template <typename K, typename N, typename CompareTo>
  412 struct btree_binary_search_compare_to {
  413   static int lower_bound(const K &k, const N &n, CompareTo comp)  {
  414     return n.binary_search_compare_to(k, 0, n.count(), CompareTo());
  415   }
  416   static int upper_bound(const K &k, const N &n, CompareTo comp)  {
  417     typedef btree_upper_bound_adapter<K,
  418         btree_key_comparer<K, CompareTo, true> > upper_compare;
  419     return n.linear_search_plain_compare(k, 0, n.count(), upper_compare(comp));
  420   }
  421 };
  422 
  423 // A node in the btree holding. The same node type is used for both internal
  424 // and leaf nodes in the btree, though the nodes are allocated in such a way
  425 // that the children array is only valid in internal nodes.
  426 template <typename Params>
  427 class btree_node {
  428  public:
  429   typedef Params params_type;
  430   typedef btree_node<Params> self_type;
  431   typedef typename Params::key_type key_type;
  432   typedef typename Params::data_type data_type;
  433   typedef typename Params::value_type value_type;
  434   typedef typename Params::mutable_value_type mutable_value_type;
  435   typedef typename Params::pointer pointer;
  436   typedef typename Params::const_pointer const_pointer;
  437   typedef typename Params::reference reference;
  438   typedef typename Params::const_reference const_reference;
  439   typedef typename Params::key_compare key_compare;
  440   typedef typename Params::size_type size_type;
  441   typedef typename Params::difference_type difference_type;
  442   // Typedefs for the various types of node searches.
  443   typedef btree_linear_search_plain_compare<
  444     key_type, self_type, key_compare> linear_search_plain_compare_type;
  445   typedef btree_linear_search_compare_to<
  446     key_type, self_type, key_compare> linear_search_compare_to_type;
  447   typedef btree_binary_search_plain_compare<
  448     key_type, self_type, key_compare> binary_search_plain_compare_type;
  449   typedef btree_binary_search_compare_to<
  450     key_type, self_type, key_compare> binary_search_compare_to_type;
  451   // If we have a valid key-compare-to type, use linear_search_compare_to,
  452   // otherwise use linear_search_plain_compare.
  453   typedef typename if_<
  454     Params::is_key_compare_to::value,
  455     linear_search_compare_to_type,
  456     linear_search_plain_compare_type>::type linear_search_type;
  457   // If we have a valid key-compare-to type, use binary_search_compare_to,
  458   // otherwise use binary_search_plain_compare.
  459   typedef typename if_<
  460     Params::is_key_compare_to::value,
  461     binary_search_compare_to_type,
  462     binary_search_plain_compare_type>::type binary_search_type;
  463   // If the key is an integral or floating point type, use linear search which
  464   // is faster than binary search for such types. Might be wise to also
  465   // configure linear search based on node-size.
  466   typedef typename if_<
  467     std::is_integral<key_type>::value ||
  468     std::is_floating_point<key_type>::value,
  469     linear_search_type, binary_search_type>::type search_type;
  470 
  471   struct base_fields {
  472     typedef typename Params::node_count_type field_type;
  473 
  474     // A boolean indicating whether the node is a leaf or not.
  475     bool leaf;
  476     // The position of the node in the node's parent.
  477     field_type position;
  478     // The maximum number of values the node can hold.
  479     field_type max_count;
  480     // The count of the number of values in the node.
  481     field_type count;
  482     // A pointer to the node's parent.
  483     btree_node *parent;
  484   };
  485 
  486   enum {
  487     kValueSize = params_type::kValueSize,
  488     kTargetNodeSize = params_type::kTargetNodeSize,
  489 
  490     // Compute how many values we can fit onto a leaf node.
  491     kNodeTargetValues = (kTargetNodeSize - sizeof(base_fields)) / kValueSize,
  492     // We need a minimum of 3 values per internal node in order to perform
  493     // splitting (1 value for the two nodes involved in the split and 1 value
  494     // propagated to the parent as the delimiter for the split).
  495     kNodeValues = kNodeTargetValues >= 3 ? kNodeTargetValues : 3,
  496 
  497     kExactMatch = 1 << 30,
  498     kMatchMask = kExactMatch - 1,
  499   };
  500 
  501   struct leaf_fields : public base_fields {
  502     // The array of values. Only the first count of these values have been
  503     // constructed and are valid.
  504     mutable_value_type values[kNodeValues];
  505   };
  506 
  507   struct internal_fields : public leaf_fields {
  508     // The array of child pointers. The keys in children_[i] are all less than
  509     // key(i). The keys in children_[i + 1] are all greater than key(i). There
  510     // are always count + 1 children.
  511     btree_node *children[kNodeValues + 1];
  512   };
  513 
  514   struct root_fields : public internal_fields {
  515     btree_node *rightmost;
  516     size_type size;
  517   };
  518 
  519  public:
  520   // Getter/setter for whether this is a leaf node or not. This value doesn't
  521   // change after the node is created.
  522   bool leaf() const { return fields_.leaf; }
  523 
  524   // Getter for the position of this node in its parent.
  525   int position() const { return fields_.position; }
  526   void set_position(int v) { fields_.position = v; }
  527 
  528   // Getter/setter for the number of values stored in this node.
  529   int count() const { return fields_.count; }
  530   void set_count(int v) { fields_.count = v; }
  531   int max_count() const { return fields_.max_count; }
  532 
  533   // Getter for the parent of this node.
  534   btree_node* parent() const { return fields_.parent; }
  535   // Getter for whether the node is the root of the tree. The parent of the
  536   // root of the tree is the leftmost node in the tree which is guaranteed to
  537   // be a leaf.
  538   bool is_root() const { return parent()->leaf(); }
  539   void make_root() {
  540     assert(parent()->is_root());
  541     fields_.parent = fields_.parent->parent();
  542   }
  543 
  544   // Getter for the rightmost root node field. Only valid on the root node.
  545   btree_node* rightmost() const { return fields_.rightmost; }
  546   btree_node** mutable_rightmost() { return &fields_.rightmost; }
  547 
  548   // Getter for the size root node field. Only valid on the root node.
  549   size_type size() const { return fields_.size; }
  550   size_type* mutable_size() { return &fields_.size; }
  551 
  552   // Getters for the key/value at position i in the node.
  553   const key_type& key(int i) const {
  554     return params_type::key(fields_.values[i]);
  555   }
  556   reference value(int i) {
  557     return reinterpret_cast<reference>(fields_.values[i]);
  558   }
  559   const_reference value(int i) const {
  560     return reinterpret_cast<const_reference>(fields_.values[i]);
  561   }
  562   mutable_value_type* mutable_value(int i) {
  563     return &fields_.values[i];
  564   }
  565 
  566   // Swap value i in this node with value j in node x.
  567   void value_swap(int i, btree_node *x, int j) {
  568     params_type::swap(mutable_value(i), x->mutable_value(j));
  569   }
  570 
  571   // Getters/setter for the child at position i in the node.
  572   btree_node* child(int i) const { return fields_.children[i]; }
  573   btree_node** mutable_child(int i) { return &fields_.children[i]; }
  574   void set_child(int i, btree_node *c) {
  575     *mutable_child(i) = c;
  576     c->fields_.parent = this;
  577     c->fields_.position = i;
  578   }
  579 
  580   // Returns the position of the first value whose key is not less than k.
  581   template <typename Compare>
  582   int lower_bound(const key_type &k, const Compare &comp) const {
  583     return search_type::lower_bound(k, *this, comp);
  584   }
  585   // Returns the position of the first value whose key is greater than k.
  586   template <typename Compare>
  587   int upper_bound(const key_type &k, const Compare &comp) const {
  588     return search_type::upper_bound(k, *this, comp);
  589   }
  590 
  591   // Returns the position of the first value whose key is not less than k using
  592   // linear search performed using plain compare.
  593   template <typename Compare>
  594   int linear_search_plain_compare(
  595       const key_type &k, int s, int e, const Compare &comp) const {
  596     while (s < e) {
  597       if (!btree_compare_keys(comp, key(s), k)) {
  598         break;
  599       }
  600       ++s;
  601     }
  602     return s;
  603   }
  604 
  605   // Returns the position of the first value whose key is not less than k using
  606   // linear search performed using compare-to.
  607   template <typename Compare>
  608   int linear_search_compare_to(
  609       const key_type &k, int s, int e, const Compare &comp) const {
  610     while (s < e) {
  611       int c = comp(key(s), k);
  612       if (c == 0) {
  613         return s | kExactMatch;
  614       } else if (c > 0) {
  615         break;
  616       }
  617       ++s;
  618     }
  619     return s;
  620   }
  621 
  622   // Returns the position of the first value whose key is not less than k using
  623   // binary search performed using plain compare.
  624   template <typename Compare>
  625   int binary_search_plain_compare(
  626       const key_type &k, int s, int e, const Compare &comp) const {
  627     while (s != e) {
  628       int mid = (s + e) / 2;
  629       if (btree_compare_keys(comp, key(mid), k)) {
  630         s = mid + 1;
  631       } else {
  632         e = mid;
  633       }
  634     }
  635     return s;
  636   }
  637 
  638   // Returns the position of the first value whose key is not less than k using
  639   // binary search performed using compare-to.
  640   template <typename CompareTo>
  641   int binary_search_compare_to(
  642       const key_type &k, int s, int e, const CompareTo &comp) const {
  643     while (s != e) {
  644       int mid = (s + e) / 2;
  645       int c = comp(key(mid), k);
  646       if (c < 0) {
  647         s = mid + 1;
  648       } else if (c > 0) {
  649         e = mid;
  650       } else {
  651         // Need to return the first value whose key is not less than k, which
  652         // requires continuing the binary search. Note that we are guaranteed
  653         // that the result is an exact match because if "key(mid-1) < k" the
  654         // call to binary_search_compare_to() will return "mid".
  655         s = binary_search_compare_to(k, s, mid, comp);
  656         return s | kExactMatch;
  657       }
  658     }
  659     return s;
  660   }
  661 
  662   // Inserts the value x at position i, shifting all existing values and
  663   // children at positions >= i to the right by 1.
  664   void insert_value(int i, const value_type &x);
  665 
  666   // Removes the value at position i, shifting all existing values and children
  667   // at positions > i to the left by 1.
  668   void remove_value(int i);
  669 
  670   // Rebalances a node with its right sibling.
  671   void rebalance_right_to_left(btree_node *sibling, int to_move);
  672   void rebalance_left_to_right(btree_node *sibling, int to_move);
  673 
  674   // Splits a node, moving a portion of the node's values to its right sibling.
  675   void split(btree_node *sibling, int insert_position);
  676 
  677   // Merges a node with its right sibling, moving all of the values and the
  678   // delimiting key in the parent node onto itself.
  679   void merge(btree_node *sibling);
  680 
  681   // Swap the contents of "this" and "src".
  682   void swap(btree_node *src);
  683 
  684   // Node allocation/deletion routines.
  685   static btree_node* init_leaf(
  686       leaf_fields *f, btree_node *parent, int max_count) {
  687     btree_node *n = reinterpret_cast<btree_node*>(f);
  688     f->leaf = 1;
  689     f->position = 0;
  690     f->max_count = max_count;
  691     f->count = 0;
  692     f->parent = parent;
  693     if (!NDEBUG) {
  694       memset(&f->values, 0, max_count * sizeof(value_type));
  695     }
  696     return n;
  697   }
  698   static btree_node* init_internal(internal_fields *f, btree_node *parent) {
  699     btree_node *n = init_leaf(f, parent, kNodeValues);
  700     f->leaf = 0;
  701     if (!NDEBUG) {
  702       memset(f->children, 0, sizeof(f->children));
  703     }
  704     return n;
  705   }
  706   static btree_node* init_root(root_fields *f, btree_node *parent) {
  707     btree_node *n = init_internal(f, parent);
  708     f->rightmost = parent;
  709     f->size = parent->count();
  710     return n;
  711   }
  712   void destroy() {
  713     for (int i = 0; i < count(); ++i) {
  714       value_destroy(i);
  715     }
  716   }
  717 
  718  private:
  719   void value_init(int i) {
  720     new (&fields_.values[i]) mutable_value_type;
  721   }
  722   void value_init(int i, const value_type &x) {
  723     new (&fields_.values[i]) mutable_value_type(x);
  724   }
  725   void value_destroy(int i) {
  726     fields_.values[i].~mutable_value_type();
  727   }
  728 
  729  private:
  730   root_fields fields_;
  731 
  732  private:
  733   btree_node(const btree_node&);
  734   void operator=(const btree_node&);
  735 };
  736 
  737 template <typename Node, typename Reference, typename Pointer>
  738 struct btree_iterator {
  739   typedef typename Node::key_type key_type;
  740   typedef typename Node::size_type size_type;
  741   typedef typename Node::difference_type difference_type;
  742   typedef typename Node::params_type params_type;
  743 
  744   typedef Node node_type;
  745   typedef typename std::remove_const<Node>::type normal_node;
  746   typedef const Node const_node;
  747   typedef typename params_type::value_type value_type;
  748   typedef typename params_type::pointer normal_pointer;
  749   typedef typename params_type::reference normal_reference;
  750   typedef typename params_type::const_pointer const_pointer;
  751   typedef typename params_type::const_reference const_reference;
  752 
  753   typedef Pointer pointer;
  754   typedef Reference reference;
  755   typedef std::bidirectional_iterator_tag iterator_category;
  756 
  757   typedef btree_iterator<
  758     normal_node, normal_reference, normal_pointer> iterator;
  759   typedef btree_iterator<
  760     const_node, const_reference, const_pointer> const_iterator;
  761   typedef btree_iterator<Node, Reference, Pointer> self_type;
  762 
  763   btree_iterator()
  764       : node(NULL),
  765         position(-1) {
  766   }
  767   btree_iterator(Node *n, int p)
  768       : node(n),
  769         position(p) {
  770   }
  771   btree_iterator(const iterator &x)
  772       : node(x.node),
  773         position(x.position) {
  774   }
  775 
  776   // Increment/decrement the iterator.
  777   void increment() {
  778     if (node->leaf() && ++position < node->count()) {
  779       return;
  780     }
  781     increment_slow();
  782   }
  783   void increment_by(int count);
  784   void increment_slow();
  785 
  786   void decrement() {
  787     if (node->leaf() && --position >= 0) {
  788       return;
  789     }
  790     decrement_slow();
  791   }
  792   void decrement_slow();
  793 
  794   bool operator==(const const_iterator &x) const {
  795     return node == x.node && position == x.position;
  796   }
  797   bool operator!=(const const_iterator &x) const {
  798     return node != x.node || position != x.position;
  799   }
  800 
  801   // Accessors for the key/value the iterator is pointing at.
  802   const key_type& key() const {
  803     return node->key(position);
  804   }
  805   reference operator*() const {
  806     return node->value(position);
  807   }
  808   pointer operator->() const {
  809     return &node->value(position);
  810   }
  811 
  812   self_type& operator++() {
  813     increment();
  814     return *this;
  815   }
  816   self_type& operator--() {
  817     decrement();
  818     return *this;
  819   }
  820   self_type operator++(int) {
  821     self_type tmp = *this;
  822     ++*this;
  823     return tmp;
  824   }
  825   self_type operator--(int) {
  826     self_type tmp = *this;
  827     --*this;
  828     return tmp;
  829   }
  830 
  831   // The node in the tree the iterator is pointing at.
  832   Node *node;
  833   // The position within the node of the tree the iterator is pointing at.
  834   int position;
  835 };
  836 
  837 // Dispatch helper class for using btree::internal_locate with plain compare.
  838 struct btree_internal_locate_plain_compare {
  839   template <typename K, typename T, typename Iter>
  840   static std::pair<Iter, int> dispatch(const K &k, const T &t, Iter iter) {
  841     return t.internal_locate_plain_compare(k, iter);
  842   }
  843 };
  844 
  845 // Dispatch helper class for using btree::internal_locate with compare-to.
  846 struct btree_internal_locate_compare_to {
  847   template <typename K, typename T, typename Iter>
  848   static std::pair<Iter, int> dispatch(const K &k, const T &t, Iter iter) {
  849     return t.internal_locate_compare_to(k, iter);
  850   }
  851 };
  852 
  853 template <typename Params>
  854 class btree : public Params::key_compare {
  855   typedef btree<Params> self_type;
  856   typedef btree_node<Params> node_type;
  857   typedef typename node_type::base_fields base_fields;
  858   typedef typename node_type::leaf_fields leaf_fields;
  859   typedef typename node_type::internal_fields internal_fields;
  860   typedef typename node_type::root_fields root_fields;
  861   typedef typename Params::is_key_compare_to is_key_compare_to;
  862 
  863   friend struct btree_internal_locate_plain_compare;
  864   friend struct btree_internal_locate_compare_to;
  865   typedef typename if_<
  866     is_key_compare_to::value,
  867     btree_internal_locate_compare_to,
  868     btree_internal_locate_plain_compare>::type internal_locate_type;
  869 
  870   enum {
  871     kNodeValues = node_type::kNodeValues,
  872     kMinNodeValues = kNodeValues / 2,
  873     kValueSize = node_type::kValueSize,
  874     kExactMatch = node_type::kExactMatch,
  875     kMatchMask = node_type::kMatchMask,
  876   };
  877 
  878   // A helper class to get the empty base class optimization for 0-size
  879   // allocators. Base is internal_allocator_type.
  880   // (e.g. empty_base_handle<internal_allocator_type, node_type*>). If Base is
  881   // 0-size, the compiler doesn't have to reserve any space for it and
  882   // sizeof(empty_base_handle) will simply be sizeof(Data). Google [empty base
  883   // class optimization] for more details.
  884   template <typename Base, typename Data>
  885   struct empty_base_handle : public Base {
  886     empty_base_handle(const Base &b, const Data &d)
  887         : Base(b),
  888           data(d) {
  889     }
  890     Data data;
  891   };
  892 
  893   struct node_stats {
  894     node_stats(ssize_t l, ssize_t i)
  895         : leaf_nodes(l),
  896           internal_nodes(i) {
  897     }
  898 
  899     node_stats& operator+=(const node_stats &x) {
  900       leaf_nodes += x.leaf_nodes;
  901       internal_nodes += x.internal_nodes;
  902       return *this;
  903     }
  904 
  905     ssize_t leaf_nodes;
  906     ssize_t internal_nodes;
  907   };
  908 
  909  public:
  910   typedef Params params_type;
  911   typedef typename Params::key_type key_type;
  912   typedef typename Params::data_type data_type;
  913   typedef typename Params::mapped_type mapped_type;
  914   typedef typename Params::value_type value_type;
  915   typedef typename Params::key_compare key_compare;
  916   typedef typename Params::pointer pointer;
  917   typedef typename Params::const_pointer const_pointer;
  918   typedef typename Params::reference reference;
  919   typedef typename Params::const_reference const_reference;
  920   typedef typename Params::size_type size_type;
  921   typedef typename Params::difference_type difference_type;
  922   typedef btree_iterator<node_type, reference, pointer> iterator;
  923   typedef typename iterator::const_iterator const_iterator;
  924   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  925   typedef std::reverse_iterator<iterator> reverse_iterator;
  926 
  927   typedef typename Params::allocator_type allocator_type;
  928   typedef typename allocator_type::template rebind<char>::other
  929     internal_allocator_type;
  930 
  931  public:
  932   // Default constructor.
  933   btree(const key_compare &comp, const allocator_type &alloc);
  934 
  935   // Copy constructor.
  936   btree(const self_type &x);
  937 
  938   // Destructor.
  939   ~btree() {
  940     clear();
  941   }
  942 
  943   // Iterator routines.
  944   iterator begin() {
  945     return iterator(leftmost(), 0);
  946   }
  947   const_iterator begin() const {
  948     return const_iterator(leftmost(), 0);
  949   }
  950   iterator end() {
  951     return iterator(rightmost(), rightmost() ? rightmost()->count() : 0);
  952   }
  953   const_iterator end() const {
  954     return const_iterator(rightmost(), rightmost() ? rightmost()->count() : 0);
  955   }
  956   reverse_iterator rbegin() {
  957     return reverse_iterator(end());
  958   }
  959   const_reverse_iterator rbegin() const {
  960     return const_reverse_iterator(end());
  961   }
  962   reverse_iterator rend() {
  963     return reverse_iterator(begin());
  964   }
  965   const_reverse_iterator rend() const {
  966     return const_reverse_iterator(begin());
  967   }
  968 
  969   // Finds the first element whose key is not less than key.
  970   iterator lower_bound(const key_type &key) {
  971     return internal_end(
  972         internal_lower_bound(key, iterator(root(), 0)));
  973   }
  974   const_iterator lower_bound(const key_type &key) const {
  975     return internal_end(
  976         internal_lower_bound(key, const_iterator(root(), 0)));
  977   }
  978 
  979   // Finds the first element whose key is greater than key.
  980   iterator upper_bound(const key_type &key) {
  981     return internal_end(
  982         internal_upper_bound(key, iterator(root(), 0)));
  983   }
  984   const_iterator upper_bound(const key_type &key) const {
  985     return internal_end(
  986         internal_upper_bound(key, const_iterator(root(), 0)));
  987   }
  988 
  989   // Finds the range of values which compare equal to key. The first member of
  990   // the returned pair is equal to lower_bound(key). The second member pair of
  991   // the pair is equal to upper_bound(key).
  992   std::pair<iterator,iterator> equal_range(const key_type &key) {
  993     return std::make_pair(lower_bound(key), upper_bound(key));
  994   }
  995   std::pair<const_iterator,const_iterator> equal_range(const key_type &key) const {
  996     return std::make_pair(lower_bound(key), upper_bound(key));
  997   }
  998 
  999   // Inserts a value into the btree only if it does not already exist. The
 1000   // boolean return value indicates whether insertion succeeded or failed. The
 1001   // ValuePointer type is used to avoid instatiating the value unless the key
 1002   // is being inserted. Value is not dereferenced if the key already exists in
 1003   // the btree. See btree_map::operator[].
 1004   template <typename ValuePointer>
 1005   std::pair<iterator,bool> insert_unique(const key_type &key, ValuePointer value);
 1006 
 1007   // Inserts a value into the btree only if it does not already exist. The
 1008   // boolean return value indicates whether insertion succeeded or failed.
 1009   std::pair<iterator,bool> insert_unique(const value_type &v) {
 1010     return insert_unique(params_type::key(v), &v);
 1011   }
 1012 
 1013   // Insert with hint. Check to see if the value should be placed immediately
 1014   // before position in the tree. If it does, then the insertion will take
 1015   // amortized constant time. If not, the insertion will take amortized
 1016   // logarithmic time as if a call to insert_unique(v) were made.
 1017   iterator insert_unique(iterator position, const value_type &v);
 1018 
 1019   // Insert a range of values into the btree.
 1020   template <typename InputIterator>
 1021   void insert_unique(InputIterator b, InputIterator e);
 1022 
 1023   // Inserts a value into the btree. The ValuePointer type is used to avoid
 1024   // instatiating the value unless the key is being inserted. Value is not
 1025   // dereferenced if the key already exists in the btree. See
 1026   // btree_map::operator[].
 1027   template <typename ValuePointer>
 1028   iterator insert_multi(const key_type &key, ValuePointer value);
 1029 
 1030   // Inserts a value into the btree.
 1031   iterator insert_multi(const value_type &v) {
 1032     return insert_multi(params_type::key(v), &v);
 1033   }
 1034 
 1035   // Insert with hint. Check to see if the value should be placed immediately
 1036   // before position in the tree. If it does, then the insertion will take
 1037   // amortized constant time. If not, the insertion will take amortized
 1038   // logarithmic time as if a call to insert_multi(v) were made.
 1039   iterator insert_multi(iterator position, const value_type &v);
 1040 
 1041   // Insert a range of values into the btree.
 1042   template <typename InputIterator>
 1043   void insert_multi(InputIterator b, InputIterator e);
 1044 
 1045   void assign(const self_type &x);
 1046 
 1047   // Erase the specified iterator from the btree. The iterator must be valid
 1048   // (i.e. not equal to end()).  Return an iterator pointing to the node after
 1049   // the one that was erased (or end() if none exists).
 1050   iterator erase(iterator iter);
 1051 
 1052   // Erases range. Returns the number of keys erased.
 1053   int erase(iterator begin, iterator end);
 1054 
 1055   // Erases the specified key from the btree. Returns 1 if an element was
 1056   // erased and 0 otherwise.
 1057   int erase_unique(const key_type &key);
 1058 
 1059   // Erases all of the entries matching the specified key from the
 1060   // btree. Returns the number of elements erased.
 1061   int erase_multi(const key_type &key);
 1062 
 1063   // Finds the iterator corresponding to a key or returns end() if the key is
 1064   // not present.
 1065   iterator find_unique(const key_type &key) {
 1066     return internal_end(
 1067         internal_find_unique(key, iterator(root(), 0)));
 1068   }
 1069   const_iterator find_unique(const key_type &key) const {
 1070     return internal_end(
 1071         internal_find_unique(key, const_iterator(root(), 0)));
 1072   }
 1073   iterator find_multi(const key_type &key) {
 1074     return internal_end(
 1075         internal_find_multi(key, iterator(root(), 0)));
 1076   }
 1077   const_iterator find_multi(const key_type &key) const {
 1078     return internal_end(
 1079         internal_find_multi(key, const_iterator(root(), 0)));
 1080   }
 1081 
 1082   // Returns a count of the number of times the key appears in the btree.
 1083   size_type count_unique(const key_type &key) const {
 1084     const_iterator b = internal_find_unique(
 1085         key, const_iterator(root(), 0));
 1086     if (!b.node) {
 1087       // The key doesn't exist in the tree.
 1088       return 0;
 1089     }
 1090     return 1;
 1091   }
 1092   // Returns a count of the number of times the key appears in the btree.
 1093   size_type count_multi(const key_type &key) const {
 1094     return distance(lower_bound(key), upper_bound(key));
 1095   }
 1096 
 1097   // Clear the btree, deleting all of the values it contains.
 1098   void clear();
 1099 
 1100   // Swap the contents of *this and x.
 1101   void swap(self_type &x);
 1102 
 1103   // Assign the contents of x to *this.
 1104   self_type& operator=(const self_type &x) {
 1105     if (&x == this) {
 1106       // Don't copy onto ourselves.
 1107       return *this;
 1108     }
 1109     assign(x);
 1110     return *this;
 1111   }
 1112 
 1113   key_compare* mutable_key_comp() {
 1114     return this;
 1115   }
 1116   const key_compare& key_comp() const {
 1117     return *this;
 1118   }
 1119   bool compare_keys(const key_type &x, const key_type &y) const {
 1120     return btree_compare_keys(key_comp(), x, y);
 1121   }
 1122 
 1123   // Dump the btree to the specified ostream. Requires that operator<< is
 1124   // defined for Key and Value.
 1125   void dump(std::ostream &os) const {
 1126     if (root() != NULL) {
 1127       internal_dump(os, root(), 0);
 1128     }
 1129   }
 1130 
 1131   // Verifies the structure of the btree.
 1132   void verify() const;
 1133 
 1134   // Size routines. Note that empty() is slightly faster than doing size()==0.
 1135   size_type size() const {
 1136     if (empty()) return 0;
 1137     if (root()->leaf()) return root()->count();
 1138     return root()->size();
 1139   }
 1140   size_type max_size() const { return std::numeric_limits<size_type>::max(); }
 1141   bool empty() const { return root() == NULL; }
 1142 
 1143   // The height of the btree. An empty tree will have height 0.
 1144   size_type height() const {
 1145     size_type h = 0;
 1146     if (root()) {
 1147       // Count the length of the chain from the leftmost node up to the
 1148       // root. We actually count from the root back around to the level below
 1149       // the root, but the calculation is the same because of the circularity
 1150       // of that traversal.
 1151       const node_type *n = root();
 1152       do {
 1153         ++h;
 1154         n = n->parent();
 1155       } while (n != root());
 1156     }
 1157     return h;
 1158   }
 1159 
 1160   // The number of internal, leaf and total nodes used by the btree.
 1161   size_type leaf_nodes() const {
 1162     return internal_stats(root()).leaf_nodes;
 1163   }
 1164   size_type internal_nodes() const {
 1165     return internal_stats(root()).internal_nodes;
 1166   }
 1167   size_type nodes() const {
 1168     node_stats stats = internal_stats(root());
 1169     return stats.leaf_nodes + stats.internal_nodes;
 1170   }
 1171 
 1172   // The total number of bytes used by the btree.
 1173   size_type bytes_used() const {
 1174     node_stats stats = internal_stats(root());
 1175     if (stats.leaf_nodes == 1 && stats.internal_nodes == 0) {
 1176       return sizeof(*this) +
 1177           sizeof(base_fields) + root()->max_count() * sizeof(value_type);
 1178     } else {
 1179       return sizeof(*this) +
 1180           sizeof(root_fields) - sizeof(internal_fields) +
 1181           stats.leaf_nodes * sizeof(leaf_fields) +
 1182           stats.internal_nodes * sizeof(internal_fields);
 1183     }
 1184   }
 1185 
 1186   // The average number of bytes used per value stored in the btree.
 1187   static double average_bytes_per_value() {
 1188     // Returns the number of bytes per value on a leaf node that is 75%
 1189     // full. Experimentally, this matches up nicely with the computed number of
 1190     // bytes per value in trees that had their values inserted in random order.
 1191     return sizeof(leaf_fields) / (kNodeValues * 0.75);
 1192   }
 1193 
 1194   // The fullness of the btree. Computed as the number of elements in the btree
 1195   // divided by the maximum number of elements a tree with the current number
 1196   // of nodes could hold. A value of 1 indicates perfect space
 1197   // utilization. Smaller values indicate space wastage.
 1198   double fullness() const {
 1199     return double(size()) / (nodes() * kNodeValues);
 1200   }
 1201   // The overhead of the btree structure in bytes per node. Computed as the
 1202   // total number of bytes used by the btree minus the number of bytes used for
 1203   // storing elements divided by the number of elements.
 1204   double overhead() const {
 1205     if (empty()) {
 1206       return 0.0;
 1207     }
 1208     return (bytes_used() - size() * kValueSize) / double(size());
 1209   }
 1210 
 1211  private:
 1212   // Internal accessor routines.
 1213   node_type* root() { return root_.data; }
 1214   const node_type* root() const { return root_.data; }
 1215   node_type** mutable_root() { return &root_.data; }
 1216 
 1217   // The rightmost node is stored in the root node.
 1218   node_type* rightmost() {
 1219     return (!root() || root()->leaf()) ? root() : root()->rightmost();
 1220   }
 1221   const node_type* rightmost() const {
 1222     return (!root() || root()->leaf()) ? root() : root()->rightmost();
 1223   }
 1224   node_type** mutable_rightmost() { return root()->mutable_rightmost(); }
 1225 
 1226   // The leftmost node is stored as the parent of the root node.
 1227   node_type* leftmost() { return root() ? root()->parent() : NULL; }
 1228   const node_type* leftmost() const { return root() ? root()->parent() : NULL; }
 1229 
 1230   // The size of the tree is stored in the root node.
 1231   size_type* mutable_size() { return root()->mutable_size(); }
 1232 
 1233   // Allocator routines.
 1234   internal_allocator_type* mutable_internal_allocator() {
 1235     return static_cast<internal_allocator_type*>(&root_);
 1236   }
 1237   const internal_allocator_type& internal_allocator() const {
 1238     return *static_cast<const internal_allocator_type*>(&root_);
 1239   }
 1240 
 1241   // Node creation/deletion routines.
 1242   node_type* new_internal_node(node_type *parent) {
 1243     internal_fields *p = reinterpret_cast<internal_fields*>(
 1244         mutable_internal_allocator()->allocate(sizeof(internal_fields)));
 1245     return node_type::init_internal(p, parent);
 1246   }
 1247   node_type* new_internal_root_node() {
 1248     root_fields *p = reinterpret_cast<root_fields*>(
 1249         mutable_internal_allocator()->allocate(sizeof(root_fields)));
 1250     return node_type::init_root(p, root()->parent());
 1251   }
 1252   node_type* new_leaf_node(node_type *parent) {
 1253     leaf_fields *p = reinterpret_cast<leaf_fields*>(
 1254         mutable_internal_allocator()->allocate(sizeof(leaf_fields)));
 1255     return node_type::init_leaf(p, parent, kNodeValues);
 1256   }
 1257   node_type* new_leaf_root_node(int max_count) {
 1258     leaf_fields *p = reinterpret_cast<leaf_fields*>(
 1259         mutable_internal_allocator()->allocate(
 1260             sizeof(base_fields) + max_count * sizeof(value_type)));
 1261     return node_type::init_leaf(p, reinterpret_cast<node_type*>(p), max_count);
 1262   }
 1263   void delete_internal_node(node_type *node) {
 1264     node->destroy();
 1265     assert(node != root());
 1266     mutable_internal_allocator()->deallocate(
 1267         reinterpret_cast<char*>(node), sizeof(internal_fields));
 1268   }
 1269   void delete_internal_root_node() {
 1270     root()->destroy();
 1271     mutable_internal_allocator()->deallocate(
 1272         reinterpret_cast<char*>(root()), sizeof(root_fields));
 1273   }
 1274   void delete_leaf_node(node_type *node) {
 1275     node->destroy();
 1276     mutable_internal_allocator()->deallocate(
 1277         reinterpret_cast<char*>(node),
 1278         sizeof(base_fields) + node->max_count() * sizeof(value_type));
 1279   }
 1280 
 1281   // Rebalances or splits the node iter points to.
 1282   void rebalance_or_split(iterator *iter);
 1283 
 1284   // Merges the values of left, right and the delimiting key on their parent
 1285   // onto left, removing the delimiting key and deleting right.
 1286   void merge_nodes(node_type *left, node_type *right);
 1287 
 1288   // Tries to merge node with its left or right sibling, and failing that,
 1289   // rebalance with its left or right sibling. Returns true if a merge
 1290   // occurred, at which point it is no longer valid to access node. Returns
 1291   // false if no merging took place.
 1292   bool try_merge_or_rebalance(iterator *iter);
 1293 
 1294   // Tries to shrink the height of the tree by 1.
 1295   void try_shrink();
 1296 
 1297   iterator internal_end(iterator iter) {
 1298     return iter.node ? iter : end();
 1299   }
 1300   const_iterator internal_end(const_iterator iter) const {
 1301     return iter.node ? iter : end();
 1302   }
 1303 
 1304   // Inserts a value into the btree immediately before iter. Requires that
 1305   // key(v) <= iter.key() and (--iter).key() <= key(v).
 1306   iterator internal_insert(iterator iter, const value_type &v);
 1307 
 1308   // Returns an iterator pointing to the first value >= the value "iter" is
 1309   // pointing at. Note that "iter" might be pointing to an invalid location as
 1310   // iter.position == iter.node->count(). This routine simply moves iter up in
 1311   // the tree to a valid location.
 1312   template <typename IterType>
 1313   static IterType internal_last(IterType iter);
 1314 
 1315   // Returns an iterator pointing to the leaf position at which key would
 1316   // reside in the tree. We provide 2 versions of internal_locate. The first
 1317   // version (internal_locate_plain_compare) always returns 0 for the second
 1318   // field of the pair. The second version (internal_locate_compare_to) is for
 1319   // the key-compare-to specialization and returns either kExactMatch (if the
 1320   // key was found in the tree) or -kExactMatch (if it wasn't) in the second
 1321   // field of the pair. The compare_to specialization allows the caller to
 1322   // avoid a subsequent comparison to determine if an exact match was made,
 1323   // speeding up string keys.
 1324   template <typename IterType>
 1325   std::pair<IterType, int> internal_locate(
 1326       const key_type &key, IterType iter) const;
 1327   template <typename IterType>
 1328   std::pair<IterType, int> internal_locate_plain_compare(
 1329       const key_type &key, IterType iter) const;
 1330   template <typename IterType>
 1331   std::pair<IterType, int> internal_locate_compare_to(
 1332       const key_type &key, IterType iter) const;
 1333 
 1334   // Internal routine which implements lower_bound().
 1335   template <typename IterType>
 1336   IterType internal_lower_bound(
 1337       const key_type &key, IterType iter) const;
 1338 
 1339   // Internal routine which implements upper_bound().
 1340   template <typename IterType>
 1341   IterType internal_upper_bound(
 1342       const key_type &key, IterType iter) const;
 1343 
 1344   // Internal routine which implements find_unique().
 1345   template <typename IterType>
 1346   IterType internal_find_unique(
 1347       const key_type &key, IterType iter) const;
 1348 
 1349   // Internal routine which implements find_multi().
 1350   template <typename IterType>
 1351   IterType internal_find_multi(
 1352       const key_type &key, IterType iter) const;
 1353 
 1354   // Deletes a node and all of its children.
 1355   void internal_clear(node_type *node);
 1356 
 1357   // Dumps a node and all of its children to the specified ostream.
 1358   void internal_dump(std::ostream &os, const node_type *node, int level) const;
 1359 
 1360   // Verifies the tree structure of node.
 1361   int internal_verify(const node_type *node,
 1362                       const key_type *lo, const key_type *hi) const;
 1363 
 1364   node_stats internal_stats(const node_type *node) const {
 1365     if (!node) {
 1366       return node_stats(0, 0);
 1367     }
 1368     if (node->leaf()) {
 1369       return node_stats(1, 0);
 1370     }
 1371     node_stats res(0, 1);
 1372     for (int i = 0; i <= node->count(); ++i) {
 1373       res += internal_stats(node->child(i));
 1374     }
 1375     return res;
 1376   }
 1377 
 1378  private:
 1379   empty_base_handle<internal_allocator_type, node_type*> root_;
 1380 
 1381  private:
 1382   // A never instantiated helper function that returns big_ if we have a
 1383   // key-compare-to functor or if R is bool and small_ otherwise.
 1384   template <typename R>
 1385   static typename if_<
 1386    if_<is_key_compare_to::value,
 1387              std::is_same<R, int>,
 1388              std::is_same<R, bool> >::type::value,
 1389    big_, small_>::type key_compare_checker(R);
 1390 
 1391   // A never instantiated helper function that returns the key comparison
 1392   // functor.
 1393   static key_compare key_compare_helper();
 1394 
 1395   // Verify that key_compare returns a bool. This is similar to the way
 1396   // is_convertible in base/type_traits.h works. Note that key_compare_checker
 1397   // is never actually invoked. The compiler will select which
 1398   // key_compare_checker() to instantiate and then figure out the size of the
 1399   // return type of key_compare_checker() at compile time which we then check
 1400   // against the sizeof of big_.
 1401   COMPILE_ASSERT(
 1402       sizeof(key_compare_checker(key_compare_helper()(key_type(), key_type()))) ==
 1403       sizeof(big_),
 1404       key_comparison_function_must_return_bool);
 1405 
 1406   // Note: We insist on kTargetValues, which is computed from
 1407   // Params::kTargetNodeSize, must fit the base_fields::field_type.
 1408   COMPILE_ASSERT(kNodeValues <
 1409                  (1 << (8 * sizeof(typename base_fields::field_type))),
 1410                  target_node_size_too_large);
 1411 
 1412   // Test the assumption made in setting kNodeValueSpace.
 1413   COMPILE_ASSERT(sizeof(base_fields) >= 2 * sizeof(void*),
 1414                  node_space_assumption_incorrect);
 1415 };
 1416 
 1417 ////
 1418 // btree_node methods
 1419 template <typename P>
 1420 inline void btree_node<P>::insert_value(int i, const value_type &x) {
 1421   assert(i <= count());
 1422   value_init(count(), x);
 1423   for (int j = count(); j > i; --j) {
 1424     value_swap(j, this, j - 1);
 1425   }
 1426   set_count(count() + 1);
 1427 
 1428   if (!leaf()) {
 1429     ++i;
 1430     for (int j = count(); j > i; --j) {
 1431       *mutable_child(j) = child(j - 1);
 1432       child(j)->set_position(j);
 1433     }
 1434     *mutable_child(i) = NULL;
 1435   }
 1436 }
 1437 
 1438 template <typename P>
 1439 inline void btree_node<P>::remove_value(int i) {
 1440   if (!leaf()) {
 1441     assert(child(i + 1)->count() == 0);
 1442     for (int j = i + 1; j < count(); ++j) {
 1443       *mutable_child(j) = child(j + 1);
 1444       child(j)->set_position(j);
 1445     }
 1446     *mutable_child(count()) = NULL;
 1447   }
 1448 
 1449   set_count(count() - 1);
 1450   for (; i < count(); ++i) {
 1451     value_swap(i, this, i + 1);
 1452   }
 1453   value_destroy(i);
 1454 }
 1455 
 1456 template <typename P>
 1457 void btree_node<P>::rebalance_right_to_left(btree_node *src, int to_move) {
 1458   assert(parent() == src->parent());
 1459   assert(position() + 1 == src->position());
 1460   assert(src->count() >= count());
 1461   assert(to_move >= 1);
 1462   assert(to_move <= src->count());
 1463 
 1464   // Make room in the left node for the new values.
 1465   for (int i = 0; i < to_move; ++i) {
 1466     value_init(i + count());
 1467   }
 1468 
 1469   // Move the delimiting value to the left node and the new delimiting value
 1470   // from the right node.
 1471   value_swap(count(), parent(), position());
 1472   parent()->value_swap(position(), src, to_move - 1);
 1473 
 1474   // Move the values from the right to the left node.
 1475   for (int i = 1; i < to_move; ++i) {
 1476     value_swap(count() + i, src, i - 1);
 1477   }
 1478   // Shift the values in the right node to their correct position.
 1479   for (int i = to_move; i < src->count(); ++i) {
 1480     src->value_swap(i - to_move, src, i);
 1481   }
 1482   for (int i = 1; i <= to_move; ++i) {
 1483     src->value_destroy(src->count() - i);
 1484   }
 1485 
 1486   if (!leaf()) {
 1487     // Move the child pointers from the right to the left node.
 1488     for (int i = 0; i < to_move; ++i) {
 1489       set_child(1 + count() + i, src->child(i));
 1490     }
 1491     for (int i = 0; i <= src->count() - to_move; ++i) {
 1492       assert(i + to_move <= src->max_count());
 1493       src->set_child(i, src->child(i + to_move));
 1494       *src->mutable_child(i + to_move) = NULL;
 1495     }
 1496   }
 1497 
 1498   // Fixup the counts on the src and dest nodes.
 1499   set_count(count() + to_move);
 1500   src->set_count(src->count() - to_move);
 1501 }
 1502 
 1503 template <typename P>
 1504 void btree_node<P>::rebalance_left_to_right(btree_node *dest, int to_move) {
 1505   assert(parent() == dest->parent());
 1506   assert(position() + 1 == dest->position());
 1507   assert(count() >= dest->count());
 1508   assert(to_move >= 1);
 1509   assert(to_move <= count());
 1510 
 1511   // Make room in the right node for the new values.
 1512   for (int i = 0; i < to_move; ++i) {
 1513     dest->value_init(i + dest->count());
 1514   }
 1515   for (int i = dest->count() - 1; i >= 0; --i) {
 1516     dest->value_swap(i, dest, i + to_move);
 1517   }
 1518 
 1519   // Move the delimiting value to the right node and the new delimiting value
 1520   // from the left node.
 1521   dest->value_swap(to_move - 1, parent(), position());
 1522   parent()->value_swap(position(), this, count() - to_move);
 1523   value_destroy(count() - to_move);
 1524 
 1525   // Move the values from the left to the right node.
 1526   for (int i = 1; i < to_move; ++i) {
 1527     value_swap(count() - to_move + i, dest, i - 1);
 1528     value_destroy(count() - to_move + i);
 1529   }
 1530 
 1531   if (!leaf()) {
 1532     // Move the child pointers from the left to the right node.
 1533     for (int i = dest->count(); i >= 0; --i) {
 1534       dest->set_child(i + to_move, dest->child(i));
 1535       *dest->mutable_child(i) = NULL;
 1536     }
 1537     for (int i = 1; i <= to_move; ++i) {
 1538       dest->set_child(i - 1, child(count() - to_move + i));
 1539       *mutable_child(count() - to_move + i) = NULL;
 1540     }
 1541   }
 1542 
 1543   // Fixup the counts on the src and dest nodes.
 1544   set_count(count() - to_move);
 1545   dest->set_count(dest->count() + to_move);
 1546 }
 1547 
 1548 template <typename P>
 1549 void btree_node<P>::split(btree_node *dest, int insert_position) {
 1550   assert(dest->count() == 0);
 1551 
 1552   // We bias the split based on the position being inserted. If we're
 1553   // inserting at the beginning of the left node then bias the split to put
 1554   // more values on the right node. If we're inserting at the end of the
 1555   // right node then bias the split to put more values on the left node.
 1556   if (insert_position == 0) {
 1557     dest->set_count(count() - 1);
 1558   } else if (insert_position == max_count()) {
 1559     dest->set_count(0);
 1560   } else {
 1561     dest->set_count(count() / 2);
 1562   }
 1563   set_count(count() - dest->count());
 1564   assert(count() >= 1);
 1565 
 1566   // Move values from the left sibling to the right sibling.
 1567   for (int i = 0; i < dest->count(); ++i) {
 1568     dest->value_init(i);
 1569     value_swap(count() + i, dest, i);
 1570     value_destroy(count() + i);
 1571   }
 1572 
 1573   // The split key is the largest value in the left sibling.
 1574   set_count(count() - 1);
 1575   parent()->insert_value(position(), value_type());
 1576   value_swap(count(), parent(), position());
 1577   value_destroy(count());
 1578   parent()->set_child(position() + 1, dest);
 1579 
 1580   if (!leaf()) {
 1581     for (int i = 0; i <= dest->count(); ++i) {
 1582       assert(child(count() + i + 1) != NULL);
 1583       dest->set_child(i, child(count() + i + 1));
 1584       *mutable_child(count() + i + 1) = NULL;
 1585     }
 1586   }
 1587 }
 1588 
 1589 template <typename P>
 1590 void btree_node<P>::merge(btree_node *src) {
 1591   assert(parent() == src->parent());
 1592   assert(position() + 1 == src->position());
 1593 
 1594   // Move the delimiting value to the left node.
 1595   value_init(count());
 1596   value_swap(count(), parent(), position());
 1597 
 1598   // Move the values from the right to the left node.
 1599   for (int i = 0; i < src->count(); ++i) {
 1600     value_init(1 + count() + i);
 1601     value_swap(1 + count() + i, src, i);
 1602     src->value_destroy(i);
 1603   }
 1604 
 1605   if (!leaf()) {
 1606     // Move the child pointers from the right to the left node.
 1607     for (int i = 0; i <= src->count(); ++i) {
 1608       set_child(1 + count() + i, src->child(i));
 1609       *src->mutable_child(i) = NULL;
 1610     }
 1611   }
 1612 
 1613   // Fixup the counts on the src and dest nodes.
 1614   set_count(1 + count() + src->count());
 1615   src->set_count(0);
 1616 
 1617   // Remove the value on the parent node.
 1618   parent()->remove_value(position());
 1619 }
 1620 
 1621 template <typename P>
 1622 void btree_node<P>::swap(btree_node *x) {
 1623   assert(leaf() == x->leaf());
 1624 
 1625   // Swap the values.
 1626   for (int i = count(); i < x->count(); ++i) {
 1627     value_init(i);
 1628   }
 1629   for (int i = x->count(); i < count(); ++i) {
 1630     x->value_init(i);
 1631   }
 1632   int n = std::max(count(), x->count());
 1633   for (int i = 0; i < n; ++i) {
 1634     value_swap(i, x, i);
 1635   }
 1636   for (int i = count(); i < x->count(); ++i) {
 1637     x->value_destroy(i);
 1638   }
 1639   for (int i = x->count(); i < count(); ++i) {
 1640     value_destroy(i);
 1641   }
 1642 
 1643   if (!leaf()) {
 1644     // Swap the child pointers.
 1645     for (int i = 0; i <= n; ++i) {
 1646       btree_swap_helper(*mutable_child(i), *x->mutable_child(i));
 1647     }
 1648     for (int i = 0; i <= count(); ++i) {
 1649       x->child(i)->fields_.parent = x;
 1650     }
 1651     for (int i = 0; i <= x->count(); ++i) {
 1652       child(i)->fields_.parent = this;
 1653     }
 1654   }
 1655 
 1656   // Swap the counts.
 1657   btree_swap_helper(fields_.count, x->fields_.count);
 1658 }
 1659 
 1660 ////
 1661 // btree_iterator methods
 1662 template <typename N, typename R, typename P>
 1663 void btree_iterator<N, R, P>::increment_slow() {
 1664   if (node->leaf()) {
 1665     assert(position >= node->count());
 1666     self_type save(*this);
 1667     while (position == node->count() && !node->is_root()) {
 1668       assert(node->parent()->child(node->position()) == node);
 1669       position = node->position();
 1670       node = node->parent();
 1671     }
 1672     if (position == node->count()) {
 1673       *this = save;
 1674     }
 1675   } else {
 1676     assert(position < node->count());
 1677     node = node->child(position + 1);
 1678     while (!node->leaf()) {
 1679       node = node->child(0);
 1680     }
 1681     position = 0;
 1682   }
 1683 }
 1684 
 1685 template <typename N, typename R, typename P>
 1686 void btree_iterator<N, R, P>::increment_by(int count) {
 1687   while (count > 0) {
 1688     if (node->leaf()) {
 1689       int rest = node->count() - position;
 1690       position += std::min(rest, count);
 1691       count = count - rest;
 1692       if (position < node->count()) {
 1693         return;
 1694       }
 1695     } else {
 1696       --count;
 1697     }
 1698     increment_slow();
 1699   }
 1700 }
 1701 
 1702 template <typename N, typename R, typename P>
 1703 void btree_iterator<N, R, P>::decrement_slow() {
 1704   if (node->leaf()) {
 1705     assert(position <= -1);
 1706     self_type save(*this);
 1707     while (position < 0 && !node->is_root()) {
 1708       assert(node->parent()->child(node->position()) == node);
 1709       position = node->position() - 1;
 1710       node = node->parent();
 1711     }
 1712     if (position < 0) {
 1713       *this = save;
 1714     }
 1715   } else {
 1716     assert(position >= 0);
 1717     node = node->child(position);
 1718     while (!node->leaf()) {
 1719       node = node->child(node->count());
 1720     }
 1721     position = node->count() - 1;
 1722   }
 1723 }
 1724 
 1725 ////
 1726 // btree methods
 1727 template <typename P>
 1728 btree<P>::btree(const key_compare &comp, const allocator_type &alloc)
 1729     : key_compare(comp),
 1730       root_(alloc, NULL) {
 1731 }
 1732 
 1733 template <typename P>
 1734 btree<P>::btree(const self_type &x)
 1735     : key_compare(x.key_comp()),
 1736       root_(x.internal_allocator(), NULL) {
 1737   assign(x);
 1738 }
 1739 
 1740 template <typename P> template <typename ValuePointer>
 1741 std::pair<typename btree<P>::iterator, bool>
 1742 btree<P>::insert_unique(const key_type &key, ValuePointer value) {
 1743   if (empty()) {
 1744     *mutable_root() = new_leaf_root_node(1);
 1745   }
 1746 
 1747   std::pair<iterator, int> res = internal_locate(key, iterator(root(), 0));
 1748   iterator &iter = res.first;
 1749   if (res.second == kExactMatch) {
 1750     // The key already exists in the tree, do nothing.
 1751     return std::make_pair(internal_last(iter), false);
 1752   } else if (!res.second) {
 1753     iterator last = internal_last(iter);
 1754     if (last.node && !compare_keys(key, last.key())) {
 1755       // The key already exists in the tree, do nothing.
 1756       return std::make_pair(last, false);
 1757     }
 1758   }
 1759 
 1760   return std::make_pair(internal_insert(iter, *value), true);
 1761 }
 1762 
 1763 template <typename P>
 1764 inline typename btree<P>::iterator
 1765 btree<P>::insert_unique(iterator position, const value_type &v) {
 1766   if (!empty()) {
 1767     const key_type &key = params_type::key(v);
 1768     if (position == end() || compare_keys(key, position.key())) {
 1769       iterator prev = position;
 1770       if (position == begin() || compare_keys((--prev).key(), key)) {
 1771         // prev.key() < key < position.key()
 1772         return internal_insert(position, v);
 1773       }
 1774     } else if (compare_keys(position.key(), key)) {
 1775       iterator next = position;
 1776       ++next;
 1777       if (next == end() || compare_keys(key, next.key())) {
 1778         // position.key() < key < next.key()
 1779         return internal_insert(next, v);
 1780       }
 1781     } else {
 1782       // position.key() == key
 1783       return position;
 1784     }
 1785   }
 1786   return insert_unique(v).first;
 1787 }
 1788 
 1789 template <typename P> template <typename InputIterator>
 1790 void btree<P>::insert_unique(InputIterator b, InputIterator e) {
 1791   for (; b != e; ++b) {
 1792     insert_unique(end(), *b);
 1793   }
 1794 }
 1795 
 1796 template <typename P> template <typename ValuePointer>
 1797 typename btree<P>::iterator
 1798 btree<P>::insert_multi(const key_type &key, ValuePointer value) {
 1799   if (empty()) {
 1800     *mutable_root() = new_leaf_root_node(1);
 1801   }
 1802 
 1803   iterator iter = internal_upper_bound(key, iterator(root(), 0));
 1804   if (!iter.node) {
 1805     iter = end();
 1806   }
 1807   return internal_insert(iter, *value);
 1808 }
 1809 
 1810 template <typename P>
 1811 typename btree<P>::iterator
 1812 btree<P>::insert_multi(iterator position, const value_type &v) {
 1813   if (!empty()) {
 1814     const key_type &key = params_type::key(v);
 1815     if (position == end() || !compare_keys(position.key(), key)) {
 1816       iterator prev = position;
 1817       if (position == begin() || !compare_keys(key, (--prev).key())) {
 1818         // prev.key() <= key <= position.key()
 1819         return internal_insert(position, v);
 1820       }
 1821     } else {
 1822       iterator next = position;
 1823       ++next;
 1824       if (next == end() || !compare_keys(next.key(), key)) {
 1825         // position.key() < key <= next.key()
 1826         return internal_insert(next, v);
 1827       }
 1828     }
 1829   }
 1830   return insert_multi(v);
 1831 }
 1832 
 1833 template <typename P> template <typename InputIterator>
 1834 void btree<P>::insert_multi(InputIterator b, InputIterator e) {
 1835   for (; b != e; ++b) {
 1836     insert_multi(end(), *b);
 1837   }
 1838 }
 1839 
 1840 template <typename P>
 1841 void btree<P>::assign(const self_type &x) {
 1842   clear();
 1843 
 1844   *mutable_key_comp() = x.key_comp();
 1845   *mutable_internal_allocator() = x.internal_allocator();
 1846 
 1847   // Assignment can avoid key comparisons because we know the order of the
 1848   // values is the same order we'll store them in.
 1849   for (const_iterator iter = x.begin(); iter != x.end(); ++iter) {
 1850     if (empty()) {
 1851       insert_multi(*iter);
 1852     } else {
 1853       // If the btree is not empty, we can just insert the new value at the end
 1854       // of the tree!
 1855       internal_insert(end(), *iter);
 1856     }
 1857   }
 1858 }
 1859 
 1860 template <typename P>
 1861 typename btree<P>::iterator btree<P>::erase(iterator iter) {
 1862   bool internal_delete = false;
 1863   if (!iter.node->leaf()) {
 1864     // Deletion of a value on an internal node. Swap the key with the largest
 1865     // value of our left child. This is easy, we just decrement iter.
 1866     iterator tmp_iter(iter--);
 1867     assert(iter.node->leaf());
 1868     assert(!compare_keys(tmp_iter.key(), iter.key()));
 1869     iter.node->value_swap(iter.position, tmp_iter.node, tmp_iter.position);
 1870     internal_delete = true;
 1871     --*mutable_size();
 1872   } else if (!root()->leaf()) {
 1873     --*mutable_size();
 1874   }
 1875 
 1876   // Delete the key from the leaf.
 1877   iter.node->remove_value(iter.position);
 1878 
 1879   // We want to return the next value after the one we just erased. If we
 1880   // erased from an internal node (internal_delete == true), then the next
 1881   // value is ++(++iter). If we erased from a leaf node (internal_delete ==
 1882   // false) then the next value is ++iter. Note that ++iter may point to an
 1883   // internal node and the value in the internal node may move to a leaf node
 1884   // (iter.node) when rebalancing is performed at the leaf level.
 1885 
 1886   // Merge/rebalance as we walk back up the tree.
 1887   iterator res(iter);
 1888   for (;;) {
 1889     if (iter.node == root()) {
 1890       try_shrink();
 1891       if (empty()) {
 1892         return end();
 1893       }
 1894       break;
 1895     }
 1896     if (iter.node->count() >= kMinNodeValues) {
 1897       break;
 1898     }
 1899     bool merged = try_merge_or_rebalance(&iter);
 1900     if (iter.node->leaf()) {
 1901       res = iter;
 1902     }
 1903     if (!merged) {
 1904       break;
 1905     }
 1906     iter.node = iter.node->parent();
 1907   }
 1908 
 1909   // Adjust our return value. If we're pointing at the end of a node, advance
 1910   // the iterator.
 1911   if (res.position == res.node->count()) {
 1912     res.position = res.node->count() - 1;
 1913     ++res;
 1914   }
 1915   // If we erased from an internal node, advance the iterator.
 1916   if (internal_delete) {
 1917     ++res;
 1918   }
 1919   return res;
 1920 }
 1921 
 1922 template <typename P>
 1923 int btree<P>::erase(iterator b, iterator e) {
 1924   int count = distance(b, e);
 1925   for (int i = 0; i < count; i++) {
 1926     b = erase(b);
 1927   }
 1928   return count;
 1929 }
 1930 
 1931 template <typename P>
 1932 int btree<P>::erase_unique(const key_type &key) {
 1933   iterator iter = internal_find_unique(key, iterator(root(), 0));
 1934   if (!iter.node) {
 1935     // The key doesn't exist in the tree, return nothing done.
 1936     return 0;
 1937   }
 1938   erase(iter);
 1939   return 1;
 1940 }
 1941 
 1942 template <typename P>
 1943 int btree<P>::erase_multi(const key_type &key) {
 1944   iterator b = internal_lower_bound(key, iterator(root(), 0));
 1945   if (!b.node) {
 1946     // The key doesn't exist in the tree, return nothing done.
 1947     return 0;
 1948   }
 1949   // Delete all of the keys between begin and upper_bound(key).
 1950   iterator e = internal_end(
 1951       internal_upper_bound(key, iterator(root(), 0)));
 1952   return erase(b, e);
 1953 }
 1954 
 1955 template <typename P>
 1956 void btree<P>::clear() {
 1957   if (root() != NULL) {
 1958     internal_clear(root());
 1959   }
 1960   *mutable_root() = NULL;
 1961 }
 1962 
 1963 template <typename P>
 1964 void btree<P>::swap(self_type &x) {
 1965   std::swap(static_cast<key_compare&>(*this), static_cast<key_compare&>(x));
 1966   std::swap(root_, x.root_);
 1967 }
 1968 
 1969 template <typename P>
 1970 void btree<P>::verify() const {
 1971   if (root() != NULL) {
 1972     assert(size() == internal_verify(root(), NULL, NULL));
 1973     assert(leftmost() == (++const_iterator(root(), -1)).node);
 1974     assert(rightmost() == (--const_iterator(root(), root()->count())).node);
 1975     assert(leftmost()->leaf());
 1976     assert(rightmost()->leaf());
 1977   } else {
 1978     assert(size() == 0);
 1979     assert(leftmost() == NULL);
 1980     assert(rightmost() == NULL);
 1981   }
 1982 }
 1983 
 1984 template <typename P>
 1985 void btree<P>::rebalance_or_split(iterator *iter) {
 1986   node_type *&node = iter->node;
 1987   int &insert_position = iter->position;
 1988   assert(node->count() == node->max_count());
 1989 
 1990   // First try to make room on the node by rebalancing.
 1991   node_type *parent = node->parent();
 1992   if (node != root()) {
 1993     if (node->position() > 0) {
 1994       // Try rebalancing with our left sibling.
 1995       node_type *left = parent->child(node->position() - 1);
 1996       if (left->count() < left->max_count()) {
 1997         // We bias rebalancing based on the position being inserted. If we're
 1998         // inserting at the end of the right node then we bias rebalancing to
 1999         // fill up the left node.
 2000         int to_move = (left->max_count() - left->count()) /
 2001             (1 + (insert_position < left->max_count()));
 2002         to_move = std::max(1, to_move);
 2003 
 2004         if (((insert_position - to_move) >= 0) ||
 2005             ((left->count() + to_move) < left->max_count())) {
 2006           left->rebalance_right_to_left(node, to_move);
 2007 
 2008           assert(node->max_count() - node->count() == to_move);
 2009           insert_position = insert_position - to_move;
 2010           if (insert_position < 0) {
 2011             insert_position = insert_position + left->count() + 1;
 2012             node = left;
 2013           }
 2014 
 2015           assert(node->count() < node->max_count());
 2016           return;
 2017         }
 2018       }
 2019     }
 2020 
 2021     if (node->position() < parent->count()) {
 2022       // Try rebalancing with our right sibling.
 2023       node_type *right = parent->child(node->position() + 1);
 2024       if (right->count() < right->max_count()) {
 2025         // We bias rebalancing based on the position being inserted. If we're
 2026         // inserting at the beginning of the left node then we bias rebalancing
 2027         // to fill up the right node.
 2028         int to_move = (right->max_count() - right->count()) /
 2029             (1 + (insert_position > 0));
 2030         to_move = std::max(1, to_move);
 2031 
 2032         if ((insert_position <= (node->count() - to_move)) ||
 2033             ((right->count() + to_move) < right->max_count())) {
 2034           node->rebalance_left_to_right(right, to_move);
 2035 
 2036           if (insert_position > node->count()) {
 2037             insert_position = insert_position - node->count() - 1;
 2038             node = right;
 2039           }
 2040 
 2041           assert(node->count() < node->max_count());
 2042           return;
 2043         }
 2044       }
 2045     }
 2046 
 2047     // Rebalancing failed, make sure there is room on the parent node for a new
 2048     // value.
 2049     if (parent->count() == parent->max_count()) {
 2050       iterator parent_iter(node->parent(), node->position());
 2051       rebalance_or_split(&parent_iter);
 2052     }
 2053   } else {
 2054     // Rebalancing not possible because this is the root node.
 2055     if (root()->leaf()) {
 2056       // The root node is currently a leaf node: create a new root node and set
 2057       // the current root node as the child of the new root.
 2058       parent = new_internal_root_node();
 2059       parent->set_child(0, root());
 2060       *mutable_root() = parent;
 2061       assert(*mutable_rightmost() == parent->child(0));
 2062     } else {
 2063       // The root node is an internal node. We do not want to create a new root
 2064       // node because the root node is special and holds the size of the tree
 2065       // and a pointer to the rightmost node. So we create a new internal node
 2066       // and move all of the items on the current root into the new node.
 2067       parent = new_internal_node(parent);
 2068       parent->set_child(0, parent);
 2069       parent->swap(root());
 2070       node = parent;
 2071     }
 2072   }
 2073 
 2074   // Split the node.
 2075   node_type *split_node;
 2076   if (node->leaf()) {
 2077     split_node = new_leaf_node(parent);
 2078     node->split(split_node, insert_position);
 2079     if (rightmost() == node) {
 2080       *mutable_rightmost() = split_node;
 2081     }
 2082   } else {
 2083     split_node = new_internal_node(parent);
 2084     node->split(split_node, insert_position);
 2085   }
 2086 
 2087   if (insert_position > node->count()) {
 2088     insert_position = insert_position - node->count() - 1;
 2089     node = split_node;
 2090   }
 2091 }
 2092 
 2093 template <typename P>
 2094 void btree<P>::merge_nodes(node_type *left, node_type *right) {
 2095   left->merge(right);
 2096   if (right->leaf()) {
 2097     if (rightmost() == right) {
 2098       *mutable_rightmost() = left;
 2099     }
 2100     delete_leaf_node(right);
 2101   } else {
 2102     delete_internal_node(right);
 2103   }
 2104 }
 2105 
 2106 template <typename P>
 2107 bool btree<P>::try_merge_or_rebalance(iterator *iter) {
 2108   node_type *parent = iter->node->parent();
 2109   if (iter->node->position() > 0) {
 2110     // Try merging with our left sibling.
 2111     node_type *left = parent->child(iter->node->position() - 1);
 2112     if ((1 + left->count() + iter->node->count()) <= left->max_count()) {
 2113       iter->position += 1 + left->count();
 2114       merge_nodes(left, iter->node);
 2115       iter->node = left;
 2116       return true;
 2117     }
 2118   }
 2119   if (iter->node->position() < parent->count()) {
 2120     // Try merging with our right sibling.
 2121     node_type *right = parent->child(iter->node->position() + 1);
 2122     if ((1 + iter->node->count() + right->count()) <= right->max_count()) {
 2123       merge_nodes(iter->node, right);
 2124       return true;
 2125     }
 2126     // Try rebalancing with our right sibling. We don't perform rebalancing if
 2127     // we deleted the first element from iter->node and the node is not
 2128     // empty. This is a small optimization for the common pattern of deleting
 2129     // from the front of the tree.
 2130     if ((right->count() > kMinNodeValues) &&
 2131         ((iter->node->count() == 0) ||
 2132          (iter->position > 0))) {
 2133       int to_move = (right->count() - iter->node->count()) / 2;
 2134       to_move = std::min(to_move, right->count() - 1);
 2135       iter->node->rebalance_right_to_left(right, to_move);
 2136       return false;
 2137     }
 2138   }
 2139   if (iter->node->position() > 0) {
 2140     // Try rebalancing with our left sibling. We don't perform rebalancing if
 2141     // we deleted the last element from iter->node and the node is not
 2142     // empty. This is a small optimization for the common pattern of deleting
 2143     // from the back of the tree.
 2144     node_type *left = parent->child(iter->node->position() - 1);
 2145     if ((left->count() > kMinNodeValues) &&
 2146         ((iter->node->count() == 0) ||
 2147          (iter->position < iter->node->count()))) {
 2148       int to_move = (left->count() - iter->node->count()) / 2;
 2149       to_move = std::min(to_move, left->count() - 1);
 2150       left->rebalance_left_to_right(iter->node, to_move);
 2151       iter->position += to_move;
 2152       return false;
 2153     }
 2154   }
 2155   return false;
 2156 }
 2157 
 2158 template <typename P>
 2159 void btree<P>::try_shrink() {
 2160   if (root()->count() > 0) {
 2161     return;
 2162   }
 2163   // Deleted the last item on the root node, shrink the height of the tree.
 2164   if (root()->leaf()) {
 2165     assert(size() == 0);
 2166     delete_leaf_node(root());
 2167     *mutable_root() = NULL;
 2168   } else {
 2169     node_type *child = root()->child(0);
 2170     if (child->leaf()) {
 2171       // The child is a leaf node so simply make it the root node in the tree.
 2172       child->make_root();
 2173       delete_internal_root_node();
 2174       *mutable_root() = child;
 2175     } else {
 2176       // The child is an internal node. We want to keep the existing root node
 2177       // so we move all of the values from the child node into the existing
 2178       // (empty) root node.
 2179       child->swap(root());
 2180       delete_internal_node(child);
 2181     }
 2182   }
 2183 }
 2184 
 2185 template <typename P> template <typename IterType>
 2186 inline IterType btree<P>::internal_last(IterType iter) {
 2187   while (iter.node && iter.position == iter.node->count()) {
 2188     iter.position = iter.node->position();
 2189     iter.node = iter.node->parent();
 2190     if (iter.node->leaf()) {
 2191       iter.node = NULL;
 2192     }
 2193   }
 2194   return iter;
 2195 }
 2196 
 2197 template <typename P>
 2198 inline typename btree<P>::iterator
 2199 btree<P>::internal_insert(iterator iter, const value_type &v) {
 2200   if (!iter.node->leaf()) {
 2201     // We can't insert on an internal node. Instead, we'll insert after the
 2202     // previous value which is guaranteed to be on a leaf node.
 2203     --iter;
 2204     ++iter.position;
 2205   }
 2206   if (iter.node->count() == iter.node->max_count()) {
 2207     // Make room in the leaf for the new item.
 2208     if (iter.node->max_count() < kNodeValues) {
 2209       // Insertion into the root where the root is smaller that the full node
 2210       // size. Simply grow the size of the root node.
 2211       assert(iter.node == root());
 2212       iter.node = new_leaf_root_node(
 2213           std::min<int>(kNodeValues, 2 * iter.node->max_count()));
 2214       iter.node->swap(root());
 2215       delete_leaf_node(root());
 2216       *mutable_root() = iter.node;
 2217     } else {
 2218       rebalance_or_split(&iter);
 2219       ++*mutable_size();
 2220     }
 2221   } else if (!root()->leaf()) {
 2222     ++*mutable_size();
 2223   }
 2224   iter.node->insert_value(iter.position, v);
 2225   return iter;
 2226 }
 2227 
 2228 template <typename P> template <typename IterType>
 2229 inline std::pair<IterType, int> btree<P>::internal_locate(
 2230     const key_type &key, IterType iter) const {
 2231   return internal_locate_type::dispatch(key, *this, iter);
 2232 }
 2233 
 2234 template <typename P> template <typename IterType>
 2235 inline std::pair<IterType, int> btree<P>::internal_locate_plain_compare(
 2236     const key_type &key, IterType iter) const {
 2237   for (;;) {
 2238     iter.position = iter.node->lower_bound(key, key_comp());
 2239     if (iter.node->leaf()) {
 2240       break;
 2241     }
 2242     iter.node = iter.node->child(iter.position);
 2243   }
 2244   return std::make_pair(iter, 0);
 2245 }
 2246 
 2247 template <typename P> template <typename IterType>
 2248 inline std::pair<IterType, int> btree<P>::internal_locate_compare_to(
 2249     const key_type &key, IterType iter) const {
 2250   for (;;) {
 2251     int res = iter.node->lower_bound(key, key_comp());
 2252     iter.position = res & kMatchMask;
 2253     if (res & kExactMatch) {
 2254       return std::make_pair(iter, static_cast<int>(kExactMatch));
 2255     }
 2256     if (iter.node->leaf()) {
 2257       break;
 2258     }
 2259     iter.node = iter.node->child(iter.position);
 2260   }
 2261   return std::make_pair(iter, -kExactMatch);
 2262 }
 2263 
 2264 template <typename P> template <typename IterType>
 2265 IterType btree<P>::internal_lower_bound(
 2266     const key_type &key, IterType iter) const {
 2267   if (iter.node) {
 2268     for (;;) {
 2269       iter.position =
 2270           iter.node->lower_bound(key, key_comp()) & kMatchMask;
 2271       if (iter.node->leaf()) {
 2272         break;
 2273       }
 2274       iter.node = iter.node->child(iter.position);
 2275     }
 2276     iter = internal_last(iter);
 2277   }
 2278   return iter;
 2279 }
 2280 
 2281 template <typename P> template <typename IterType>
 2282 IterType btree<P>::internal_upper_bound(
 2283     const key_type &key, IterType iter) const {
 2284   if (iter.node) {
 2285     for (;;) {
 2286       iter.position = iter.node->upper_bound(key, key_comp());
 2287       if (iter.node->leaf()) {
 2288         break;
 2289       }
 2290       iter.node = iter.node->child(iter.position);
 2291     }
 2292     iter = internal_last(iter);
 2293   }
 2294   return iter;
 2295 }
 2296 
 2297 template <typename P> template <typename IterType>
 2298 IterType btree<P>::internal_find_unique(
 2299     const key_type &key, IterType iter) const {
 2300   if (iter.node) {
 2301     std::pair<IterType, int> res = internal_locate(key, iter);
 2302     if (res.second == kExactMatch) {
 2303       return res.first;
 2304     }
 2305     if (!res.second) {
 2306       iter = internal_last(res.first);
 2307       if (iter.node && !compare_keys(key, iter.key())) {
 2308         return iter;
 2309       }
 2310     }
 2311   }
 2312   return IterType(NULL, 0);
 2313 }
 2314 
 2315 template <typename P> template <typename IterType>
 2316 IterType btree<P>::internal_find_multi(
 2317     const key_type &key, IterType iter) const {
 2318   if (iter.node) {
 2319     iter = internal_lower_bound(key, iter);
 2320     if (iter.node) {
 2321       iter = internal_last(iter);
 2322       if (iter.node && !compare_keys(key, iter.key())) {
 2323         return iter;
 2324       }
 2325     }
 2326   }
 2327   return IterType(NULL, 0);
 2328 }
 2329 
 2330 template <typename P>
 2331 void btree<P>::internal_clear(node_type *node) {
 2332   if (!node->leaf()) {
 2333     for (int i = 0; i <= node->count(); ++i) {
 2334       internal_clear(node->child(i));
 2335     }
 2336     if (node == root()) {
 2337       delete_internal_root_node();
 2338     } else {
 2339       delete_internal_node(node);
 2340     }
 2341   } else {
 2342     delete_leaf_node(node);
 2343   }
 2344 }
 2345 
 2346 template <typename P>
 2347 void btree<P>::internal_dump(
 2348     std::ostream &os, const node_type *node, int level) const {
 2349   for (int i = 0; i < node->count(); ++i) {
 2350     if (!node->leaf()) {
 2351       internal_dump(os, node->child(i), level + 1);
 2352     }
 2353     for (int j = 0; j < level; ++j) {
 2354       os << "  ";
 2355     }
 2356     os << node->key(i) << " [" << level << "]\n";
 2357   }
 2358   if (!node->leaf()) {
 2359     internal_dump(os, node->child(node->count()), level + 1);
 2360   }
 2361 }
 2362 
 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());
 2368   if (lo) {
 2369     assert(!compare_keys(node->key(0), *lo));
 2370   }
 2371   if (hi) {
 2372     assert(!compare_keys(*hi, node->key(node->count() - 1)));
 2373   }
 2374   for (int i = 1; i < node->count(); ++i) {
 2375     assert(!compare_keys(node->key(i), node->key(i - 1)));
 2376   }
 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(
 2384           node->child(i),
 2385           (i == 0) ? lo : &node->key(i - 1),
 2386           (i == node->count()) ? hi : &node->key(i));
 2387     }
 2388   }
 2389   return count;
 2390 }
 2391 
 2392 } // namespace btree
 2393 
 2394 #endif  // UTIL_BTREE_BTREE_H__