diff options
Diffstat (limited to 'cpp-btree')
| -rw-r--r-- | cpp-btree/CMakeLists.txt | 40 | ||||
| -rw-r--r-- | cpp-btree/COPYING | 202 | ||||
| -rw-r--r-- | cpp-btree/README | 31 | ||||
| -rw-r--r-- | cpp-btree/btree.h | 2394 | ||||
| -rw-r--r-- | cpp-btree/btree_bench.cc | 593 | ||||
| -rw-r--r-- | cpp-btree/btree_container.h | 349 | ||||
| -rw-r--r-- | cpp-btree/btree_map.h | 130 | ||||
| -rw-r--r-- | cpp-btree/btree_set.h | 121 | ||||
| -rw-r--r-- | cpp-btree/btree_test.cc | 270 | ||||
| -rw-r--r-- | cpp-btree/btree_test.h | 940 | ||||
| -rw-r--r-- | cpp-btree/btree_test_flags.cc | 20 | ||||
| -rw-r--r-- | cpp-btree/safe_btree.h | 395 | ||||
| -rw-r--r-- | cpp-btree/safe_btree_map.h | 89 | ||||
| -rw-r--r-- | cpp-btree/safe_btree_set.h | 88 | ||||
| -rw-r--r-- | cpp-btree/safe_btree_test.cc | 116 |
15 files changed, 0 insertions, 5778 deletions
diff --git a/cpp-btree/CMakeLists.txt b/cpp-btree/CMakeLists.txt deleted file mode 100644 index d005e15..0000000 --- a/cpp-btree/CMakeLists.txt +++ /dev/null @@ -1,40 +0,0 @@ -# Copyright 2013 Google Inc. All Rights Reserved. -# -# Licensed under the Apache License, Version 2.0 (the "License"); -# you may not use this file except in compliance with the License. -# You may obtain a copy of the License at -# -# http://www.apache.org/licenses/LICENSE-2.0 -# -# Unless required by applicable law or agreed to in writing, software -# distributed under the License is distributed on an "AS IS" BASIS, -# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -# See the License for the specific language governing permissions and -# limitations under the License. - -cmake_minimum_required(VERSION 2.6) - -project(cppbtree CXX) - -option(build_tests "Build B-tree tests" OFF) -add_definitions(-std=c++11) -set(CMAKE_CXX_FLAGS "-g -O2") - -# CMake doesn't have a way to pure template library, -# add_library(cppbtree btree.h btree_map.h btree_set.h -# safe_btree.h safe_btree_map.h safe_btree_set.h) -# set_target_properties(cppbtree PROPERTIES LINKER_LANGUAGE CXX) - -if(build_tests) - enable_testing() - include_directories($ENV{GTEST_ROOT}/include) - link_directories($ENV{GTEST_ROOT}) - include_directories($ENV{GFLAGS_ROOT}/include) - link_directories($ENV{GFLAGS_ROOT}/lib) - add_executable(btree_test btree_test.cc btree_test_flags.cc) - add_executable(safe_btree_test safe_btree_test.cc btree_test_flags.cc) - add_executable(btree_bench btree_bench.cc btree_test_flags.cc) - target_link_libraries(btree_test gtest_main gtest gflags) - target_link_libraries(safe_btree_test gtest_main gtest gflags) - target_link_libraries(btree_bench gflags gtest) -endif() diff --git a/cpp-btree/COPYING b/cpp-btree/COPYING deleted file mode 100644 index d645695..0000000 --- a/cpp-btree/COPYING +++ /dev/null @@ -1,202 +0,0 @@ - - Apache License - Version 2.0, January 2004 - http://www.apache.org/licenses/ - - TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION - - 1. Definitions. - - "License" shall mean the terms and conditions for use, reproduction, - and distribution as defined by Sections 1 through 9 of this document. - - "Licensor" shall mean the copyright owner or entity authorized by - the copyright owner that is granting the License. - - "Legal Entity" shall mean the union of the acting entity and all - other entities that control, are controlled by, or are under common - control with that entity. For the purposes of this definition, - "control" means (i) the power, direct or indirect, to cause the - direction or management of such entity, whether by contract or - otherwise, or (ii) ownership of fifty percent (50%) or more of the - outstanding shares, or (iii) beneficial ownership of such entity. - - "You" (or "Your") shall mean an individual or Legal Entity - exercising permissions granted by this License. - - "Source" form shall mean the preferred form for making modifications, - including but not limited to software source code, documentation - source, and configuration files. - - "Object" form shall mean any form resulting from mechanical - transformation or translation of a Source form, including but - not limited to compiled object code, generated documentation, - and conversions to other media types. - - "Work" shall mean the work of authorship, whether in Source or - Object form, made available under the License, as indicated by a - copyright notice that is included in or attached to the work - (an example is provided in the Appendix below). - - "Derivative Works" shall mean any work, whether in Source or Object - form, that is based on (or derived from) the Work and for which the - editorial revisions, annotations, elaborations, or other modifications - represent, as a whole, an original work of authorship. For the purposes - of this License, Derivative Works shall not include works that remain - separable from, or merely link (or bind by name) to the interfaces of, - the Work and Derivative Works thereof. - - "Contribution" shall mean any work of authorship, including - the original version of the Work and any modifications or additions - to that Work or Derivative Works thereof, that is intentionally - submitted to Licensor for inclusion in the Work by the copyright owner - or by an individual or Legal Entity authorized to submit on behalf of - the copyright owner. For the purposes of this definition, "submitted" - means any form of electronic, verbal, or written communication sent - to the Licensor or its representatives, including but not limited to - communication on electronic mailing lists, source code control systems, - and issue tracking systems that are managed by, or on behalf of, the - Licensor for the purpose of discussing and improving the Work, but - excluding communication that is conspicuously marked or otherwise - designated in writing by the copyright owner as "Not a Contribution." - - "Contributor" shall mean Licensor and any individual or Legal Entity - on behalf of whom a Contribution has been received by Licensor and - subsequently incorporated within the Work. - - 2. Grant of Copyright License. Subject to the terms and conditions of - this License, each Contributor hereby grants to You a perpetual, - worldwide, non-exclusive, no-charge, royalty-free, irrevocable - copyright license to reproduce, prepare Derivative Works of, - publicly display, publicly perform, sublicense, and distribute the - Work and such Derivative Works in Source or Object form. - - 3. Grant of Patent License. Subject to the terms and conditions of - this License, each Contributor hereby grants to You a perpetual, - worldwide, non-exclusive, no-charge, royalty-free, irrevocable - (except as stated in this section) patent license to make, have made, - use, offer to sell, sell, import, and otherwise transfer the Work, - where such license applies only to those patent claims licensable - by such Contributor that are necessarily infringed by their - Contribution(s) alone or by combination of their Contribution(s) - with the Work to which such Contribution(s) was submitted. If You - institute patent litigation against any entity (including a - cross-claim or counterclaim in a lawsuit) alleging that the Work - or a Contribution incorporated within the Work constitutes direct - or contributory patent infringement, then any patent licenses - granted to You under this License for that Work shall terminate - as of the date such litigation is filed. - - 4. Redistribution. You may reproduce and distribute copies of the - Work or Derivative Works thereof in any medium, with or without - modifications, and in Source or Object form, provided that You - meet the following conditions: - - (a) You must give any other recipients of the Work or - Derivative Works a copy of this License; and - - (b) You must cause any modified files to carry prominent notices - stating that You changed the files; and - - (c) You must retain, in the Source form of any Derivative Works - that You distribute, all copyright, patent, trademark, and - attribution notices from the Source form of the Work, - excluding those notices that do not pertain to any part of - the Derivative Works; and - - (d) If the Work includes a "NOTICE" text file as part of its - distribution, then any Derivative Works that You distribute must - include a readable copy of the attribution notices contained - within such NOTICE file, excluding those notices that do not - pertain to any part of the Derivative Works, in at least one - of the following places: within a NOTICE text file distributed - as part of the Derivative Works; within the Source form or - documentation, if provided along with the Derivative Works; or, - within a display generated by the Derivative Works, if and - wherever such third-party notices normally appear. The contents - of the NOTICE file are for informational purposes only and - do not modify the License. You may add Your own attribution - notices within Derivative Works that You distribute, alongside - or as an addendum to the NOTICE text from the Work, provided - that such additional attribution notices cannot be construed - as modifying the License. - - You may add Your own copyright statement to Your modifications and - may provide additional or different license terms and conditions - for use, reproduction, or distribution of Your modifications, or - for any such Derivative Works as a whole, provided Your use, - reproduction, and distribution of the Work otherwise complies with - the conditions stated in this License. - - 5. Submission of Contributions. Unless You explicitly state otherwise, - any Contribution intentionally submitted for inclusion in the Work - by You to the Licensor shall be under the terms and conditions of - this License, without any additional terms or conditions. - Notwithstanding the above, nothing herein shall supersede or modify - the terms of any separate license agreement you may have executed - with Licensor regarding such Contributions. - - 6. Trademarks. This License does not grant permission to use the trade - names, trademarks, service marks, or product names of the Licensor, - except as required for reasonable and customary use in describing the - origin of the Work and reproducing the content of the NOTICE file. - - 7. Disclaimer of Warranty. Unless required by applicable law or - agreed to in writing, Licensor provides the Work (and each - Contributor provides its Contributions) on an "AS IS" BASIS, - WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or - implied, including, without limitation, any warranties or conditions - of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A - PARTICULAR PURPOSE. You are solely responsible for determining the - appropriateness of using or redistributing the Work and assume any - risks associated with Your exercise of permissions under this License. - - 8. Limitation of Liability. In no event and under no legal theory, - whether in tort (including negligence), contract, or otherwise, - unless required by applicable law (such as deliberate and grossly - negligent acts) or agreed to in writing, shall any Contributor be - liable to You for damages, including any direct, indirect, special, - incidental, or consequential damages of any character arising as a - result of this License or out of the use or inability to use the - Work (including but not limited to damages for loss of goodwill, - work stoppage, computer failure or malfunction, or any and all - other commercial damages or losses), even if such Contributor - has been advised of the possibility of such damages. - - 9. Accepting Warranty or Additional Liability. While redistributing - the Work or Derivative Works thereof, You may choose to offer, - and charge a fee for, acceptance of support, warranty, indemnity, - or other liability obligations and/or rights consistent with this - License. However, in accepting such obligations, You may act only - on Your own behalf and on Your sole responsibility, not on behalf - of any other Contributor, and only if You agree to indemnify, - defend, and hold each Contributor harmless for any liability - incurred by, or claims asserted against, such Contributor by reason - of your accepting any such warranty or additional liability. - - END OF TERMS AND CONDITIONS - - APPENDIX: How to apply the Apache License to your work. - - To apply the Apache License to your work, attach the following - boilerplate notice, with the fields enclosed by brackets "[]" - replaced with your own identifying information. (Don't include - the brackets!) The text should be enclosed in the appropriate - comment syntax for the file format. We also recommend that a - file or class name and description of purpose be included on the - same "printed page" as the copyright notice for easier - identification within third-party archives. - - Copyright [yyyy] [name of copyright owner] - - Licensed under the Apache License, Version 2.0 (the "License"); - you may not use this file except in compliance with the License. - You may obtain a copy of the License at - - http://www.apache.org/licenses/LICENSE-2.0 - - Unless required by applicable law or agreed to in writing, software - distributed under the License is distributed on an "AS IS" BASIS, - WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - See the License for the specific language governing permissions and - limitations under the License. diff --git a/cpp-btree/README b/cpp-btree/README deleted file mode 100644 index 319fe9b..0000000 --- a/cpp-btree/README +++ /dev/null @@ -1,31 +0,0 @@ -This library is a C++ template library and, as such, there is no -library to build and install. Copy the .h files and use them! - -See http://code.google.com/p/cpp-btree/wiki/UsageInstructions for -details. - ----- - -To build and run the provided tests, however, you will need to install -CMake, the Google C++ Test framework, and the Google flags package. - -Download and install CMake from http://www.cmake.org - -Download and build the GoogleTest framework from -http://code.google.com/p/googletest - -Download and install gflags from https://code.google.com/p/gflags - -Set GTEST_ROOT to the directory where GTEST was built. -Set GFLAGS_ROOT to the directory prefix where GFLAGS is installed. - -export GTEST_ROOT=/path/for/gtest-x.y -export GFLAGS_ROOT=/opt - -cmake . -Dbuild_tests=ON - -For example, to build on a Unix system with the clang++ compiler, - -export GTEST_ROOT=$(HOME)/src/googletest -export GFLAGS_ROOT=/opt -cmake . -G "Unix Makefiles" -Dbuild_tests=ON -DCMAKE_CXX_COMPILER=clang++ diff --git a/cpp-btree/btree.h b/cpp-btree/btree.h deleted file mode 100644 index cdd2b52..0000000 --- a/cpp-btree/btree.h +++ /dev/null @@ -1,2394 +0,0 @@ -// Copyright 2013 Google Inc. All Rights Reserved. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. -// -// A btree implementation of the STL set and map interfaces. A btree is both -// smaller and faster than STL set/map. The red-black tree implementation of -// STL set/map has an overhead of 3 pointers (left, right and parent) plus the -// node color information for each stored value. So a set<int32> consumes 20 -// bytes for each value stored. This btree implementation stores multiple -// values on fixed size nodes (usually 256 bytes) and doesn't store child -// pointers for leaf nodes. The result is that a btree_set<int32> may use much -// less memory per stored value. For the random insertion benchmark in -// btree_test.cc, a btree_set<int32> with node-size of 256 uses 4.9 bytes per -// stored value. -// -// The packing of multiple values on to each node of a btree has another effect -// besides better space utilization: better cache locality due to fewer cache -// lines being accessed. Better cache locality translates into faster -// operations. -// -// CAVEATS -// -// Insertions and deletions on a btree can cause splitting, merging or -// rebalancing of btree nodes. And even without these operations, insertions -// and deletions on a btree will move values around within a node. In both -// cases, the result is that insertions and deletions can invalidate iterators -// pointing to values other than the one being inserted/deleted. This is -// notably different from STL set/map which takes care to not invalidate -// iterators on insert/erase except, of course, for iterators pointing to the -// value being erased. A partial workaround when erasing is available: -// erase() returns an iterator pointing to the item just after the one that was -// erased (or end() if none exists). See also safe_btree. - -// PERFORMANCE -// -// btree_bench --benchmarks=. 2>&1 | ./benchmarks.awk -// -// Run on pmattis-warp.nyc (4 X 2200 MHz CPUs); 2010/03/04-15:23:06 -// Benchmark STL(ns) B-Tree(ns) @ <size> -// -------------------------------------------------------- -// BM_set_int32_insert 1516 608 +59.89% <256> [40.0, 5.2] -// BM_set_int32_lookup 1160 414 +64.31% <256> [40.0, 5.2] -// BM_set_int32_fulllookup 960 410 +57.29% <256> [40.0, 4.4] -// BM_set_int32_delete 1741 528 +69.67% <256> [40.0, 5.2] -// BM_set_int32_queueaddrem 3078 1046 +66.02% <256> [40.0, 5.5] -// BM_set_int32_mixedaddrem 3600 1384 +61.56% <256> [40.0, 5.3] -// BM_set_int32_fifo 227 113 +50.22% <256> [40.0, 4.4] -// BM_set_int32_fwditer 158 26 +83.54% <256> [40.0, 5.2] -// BM_map_int32_insert 1551 636 +58.99% <256> [48.0, 10.5] -// BM_map_int32_lookup 1200 508 +57.67% <256> [48.0, 10.5] -// BM_map_int32_fulllookup 989 487 +50.76% <256> [48.0, 8.8] -// BM_map_int32_delete 1794 628 +64.99% <256> [48.0, 10.5] -// BM_map_int32_queueaddrem 3189 1266 +60.30% <256> [48.0, 11.6] -// BM_map_int32_mixedaddrem 3822 1623 +57.54% <256> [48.0, 10.9] -// BM_map_int32_fifo 151 134 +11.26% <256> [48.0, 8.8] -// BM_map_int32_fwditer 161 32 +80.12% <256> [48.0, 10.5] -// BM_set_int64_insert 1546 636 +58.86% <256> [40.0, 10.5] -// BM_set_int64_lookup 1200 512 +57.33% <256> [40.0, 10.5] -// BM_set_int64_fulllookup 971 487 +49.85% <256> [40.0, 8.8] -// BM_set_int64_delete 1745 616 +64.70% <256> [40.0, 10.5] -// BM_set_int64_queueaddrem 3163 1195 +62.22% <256> [40.0, 11.6] -// BM_set_int64_mixedaddrem 3760 1564 +58.40% <256> [40.0, 10.9] -// BM_set_int64_fifo 146 103 +29.45% <256> [40.0, 8.8] -// BM_set_int64_fwditer 162 31 +80.86% <256> [40.0, 10.5] -// BM_map_int64_insert 1551 720 +53.58% <256> [48.0, 20.7] -// BM_map_int64_lookup 1214 612 +49.59% <256> [48.0, 20.7] -// BM_map_int64_fulllookup 994 592 +40.44% <256> [48.0, 17.2] -// BM_map_int64_delete 1778 764 +57.03% <256> [48.0, 20.7] -// BM_map_int64_queueaddrem 3189 1547 +51.49% <256> [48.0, 20.9] -// BM_map_int64_mixedaddrem 3779 1887 +50.07% <256> [48.0, 21.6] -// BM_map_int64_fifo 147 145 +1.36% <256> [48.0, 17.2] -// BM_map_int64_fwditer 162 41 +74.69% <256> [48.0, 20.7] -// BM_set_string_insert 1989 1966 +1.16% <256> [64.0, 44.5] -// BM_set_string_lookup 1709 1600 +6.38% <256> [64.0, 44.5] -// BM_set_string_fulllookup 1573 1529 +2.80% <256> [64.0, 35.4] -// BM_set_string_delete 2520 1920 +23.81% <256> [64.0, 44.5] -// BM_set_string_queueaddrem 4706 4309 +8.44% <256> [64.0, 48.3] -// BM_set_string_mixedaddrem 5080 4654 +8.39% <256> [64.0, 46.7] -// BM_set_string_fifo 318 512 -61.01% <256> [64.0, 35.4] -// BM_set_string_fwditer 182 93 +48.90% <256> [64.0, 44.5] -// BM_map_string_insert 2600 2227 +14.35% <256> [72.0, 55.8] -// BM_map_string_lookup 2068 1730 +16.34% <256> [72.0, 55.8] -// BM_map_string_fulllookup 1859 1618 +12.96% <256> [72.0, 44.0] -// BM_map_string_delete 3168 2080 +34.34% <256> [72.0, 55.8] -// BM_map_string_queueaddrem 5840 4701 +19.50% <256> [72.0, 59.4] -// BM_map_string_mixedaddrem 6400 5200 +18.75% <256> [72.0, 57.8] -// BM_map_string_fifo 398 596 -49.75% <256> [72.0, 44.0] -// BM_map_string_fwditer 243 113 +53.50% <256> [72.0, 55.8] - -#ifndef UTIL_BTREE_BTREE_H__ -#define UTIL_BTREE_BTREE_H__ - -#include <assert.h> -#include <stddef.h> -#include <string.h> -#include <sys/types.h> -#include <algorithm> -#include <functional> -#include <iostream> -#include <iterator> -#include <limits> -#include <type_traits> -#include <new> -#include <ostream> -#include <string> -#include <utility> - -#ifndef NDEBUG -#define NDEBUG 1 -#endif - -namespace btree { - -// Inside a btree method, if we just call swap(), it will choose the -// btree::swap method, which we don't want. And we can't say ::swap -// because then MSVC won't pickup any std::swap() implementations. We -// can't just use std::swap() directly because then we don't get the -// specialization for types outside the std namespace. So the solution -// is to have a special swap helper function whose name doesn't -// collide with other swap functions defined by the btree classes. -template <typename T> -inline void btree_swap_helper(T &a, T &b) { - using std::swap; - swap(a, b); -} - -// A template helper used to select A or B based on a condition. -template<bool cond, typename A, typename B> -struct if_{ - typedef A type; -}; - -template<typename A, typename B> -struct if_<false, A, B> { - typedef B type; -}; - -// Types small_ and big_ are promise that sizeof(small_) < sizeof(big_) -typedef char small_; - -struct big_ { - char dummy[2]; -}; - -// A compile-time assertion. -template <bool> -struct CompileAssert { -}; - -#define COMPILE_ASSERT(expr, msg) \ - typedef CompileAssert<(bool(expr))> msg[bool(expr) ? 1 : -1] - -// A helper type used to indicate that a key-compare-to functor has been -// provided. A user can specify a key-compare-to functor by doing: -// -// struct MyStringComparer -// : public util::btree::btree_key_compare_to_tag { -// int operator()(const string &a, const string &b) const { -// return a.compare(b); -// } -// }; -// -// Note that the return type is an int and not a bool. There is a -// COMPILE_ASSERT which enforces this return type. -struct btree_key_compare_to_tag { -}; - -// A helper class that indicates if the Compare parameter is derived from -// btree_key_compare_to_tag. -template <typename Compare> -struct btree_is_key_compare_to - : public std::is_convertible<Compare, btree_key_compare_to_tag> { -}; - -// A helper class to convert a boolean comparison into a three-way -// "compare-to" comparison that returns a negative value to indicate -// less-than, zero to indicate equality and a positive value to -// indicate greater-than. This helper class is specialized for -// less<string> and greater<string>. The btree_key_compare_to_adapter -// class is provided so that btree users automatically get the more -// efficient compare-to code when using common google string types -// with common comparison functors. -template <typename Compare> -struct btree_key_compare_to_adapter : Compare { - btree_key_compare_to_adapter() { } - btree_key_compare_to_adapter(const Compare &c) : Compare(c) { } - btree_key_compare_to_adapter(const btree_key_compare_to_adapter<Compare> &c) - : Compare(c) { - } -}; - -template <> -struct btree_key_compare_to_adapter<std::less<std::string> > - : public btree_key_compare_to_tag { - btree_key_compare_to_adapter() {} - btree_key_compare_to_adapter(const std::less<std::string>&) {} - btree_key_compare_to_adapter( - const btree_key_compare_to_adapter<std::less<std::string> >&) {} - int operator()(const std::string &a, const std::string &b) const { - return a.compare(b); - } -}; - -template <> -struct btree_key_compare_to_adapter<std::greater<std::string> > - : public btree_key_compare_to_tag { - btree_key_compare_to_adapter() {} - btree_key_compare_to_adapter(const std::greater<std::string>&) {} - btree_key_compare_to_adapter( - const btree_key_compare_to_adapter<std::greater<std::string> >&) {} - int operator()(const std::string &a, const std::string &b) const { - return b.compare(a); - } -}; - -// A helper class that allows a compare-to functor to behave like a plain -// compare functor. This specialization is used when we do not have a -// compare-to functor. -template <typename Key, typename Compare, bool HaveCompareTo> -struct btree_key_comparer { - btree_key_comparer() {} - btree_key_comparer(Compare c) : comp(c) {} - static bool bool_compare(const Compare &comp, const Key &x, const Key &y) { - return comp(x, y); - } - bool operator()(const Key &x, const Key &y) const { - return bool_compare(comp, x, y); - } - Compare comp; -}; - -// A specialization of btree_key_comparer when a compare-to functor is -// present. We need a plain (boolean) comparison in some parts of the btree -// code, such as insert-with-hint. -template <typename Key, typename Compare> -struct btree_key_comparer<Key, Compare, true> { - btree_key_comparer() {} - btree_key_comparer(Compare c) : comp(c) {} - static bool bool_compare(const Compare &comp, const Key &x, const Key &y) { - return comp(x, y) < 0; - } - bool operator()(const Key &x, const Key &y) const { - return bool_compare(comp, x, y); - } - Compare comp; -}; - -// A helper function to compare to keys using the specified compare -// functor. This dispatches to the appropriate btree_key_comparer comparison, -// depending on whether we have a compare-to functor or not (which depends on -// whether Compare is derived from btree_key_compare_to_tag). -template <typename Key, typename Compare> -static bool btree_compare_keys( - const Compare &comp, const Key &x, const Key &y) { - typedef btree_key_comparer<Key, Compare, - btree_is_key_compare_to<Compare>::value> key_comparer; - return key_comparer::bool_compare(comp, x, y); -} - -template <typename Key, typename Compare, - typename Alloc, int TargetNodeSize, int ValueSize> -struct btree_common_params { - // If Compare is derived from btree_key_compare_to_tag then use it as the - // key_compare type. Otherwise, use btree_key_compare_to_adapter<> which will - // fall-back to Compare if we don't have an appropriate specialization. - typedef typename if_< - btree_is_key_compare_to<Compare>::value, - Compare, btree_key_compare_to_adapter<Compare> >::type key_compare; - // A type which indicates if we have a key-compare-to functor or a plain old - // key-compare functor. - typedef btree_is_key_compare_to<key_compare> is_key_compare_to; - - typedef Alloc allocator_type; - typedef Key key_type; - typedef ssize_t size_type; - typedef ptrdiff_t difference_type; - - enum { - kTargetNodeSize = TargetNodeSize, - - // Available space for values. This is largest for leaf nodes, - // which has overhead no fewer than two pointers. - kNodeValueSpace = TargetNodeSize - 2 * sizeof(void*), - }; - - // This is an integral type large enough to hold as many - // ValueSize-values as will fit a node of TargetNodeSize bytes. - typedef typename if_< - (kNodeValueSpace / ValueSize) >= 256, - uint16_t, - uint8_t>::type node_count_type; -}; - -// A parameters structure for holding the type parameters for a btree_map. -template <typename Key, typename Data, typename Compare, - typename Alloc, int TargetNodeSize> -struct btree_map_params - : public btree_common_params<Key, Compare, Alloc, TargetNodeSize, - sizeof(Key) + sizeof(Data)> { - typedef Data data_type; - typedef Data mapped_type; - typedef std::pair<const Key, data_type> value_type; - typedef std::pair<Key, data_type> mutable_value_type; - typedef value_type* pointer; - typedef const value_type* const_pointer; - typedef value_type& reference; - typedef const value_type& const_reference; - - enum { - kValueSize = sizeof(Key) + sizeof(data_type), - }; - - static const Key& key(const value_type &x) { return x.first; } - static const Key& key(const mutable_value_type &x) { return x.first; } - static void swap(mutable_value_type *a, mutable_value_type *b) { - btree_swap_helper(a->first, b->first); - btree_swap_helper(a->second, b->second); - } -}; - -// A parameters structure for holding the type parameters for a btree_set. -template <typename Key, typename Compare, typename Alloc, int TargetNodeSize> -struct btree_set_params - : public btree_common_params<Key, Compare, Alloc, TargetNodeSize, - sizeof(Key)> { - typedef std::false_type data_type; - typedef std::false_type mapped_type; - typedef Key value_type; - typedef value_type mutable_value_type; - typedef value_type* pointer; - typedef const value_type* const_pointer; - typedef value_type& reference; - typedef const value_type& const_reference; - - enum { - kValueSize = sizeof(Key), - }; - - static const Key& key(const value_type &x) { return x; } - static void swap(mutable_value_type *a, mutable_value_type *b) { - btree_swap_helper<mutable_value_type>(*a, *b); - } -}; - -// An adapter class that converts a lower-bound compare into an upper-bound -// compare. -template <typename Key, typename Compare> -struct btree_upper_bound_adapter : public Compare { - btree_upper_bound_adapter(Compare c) : Compare(c) {} - bool operator()(const Key &a, const Key &b) const { - return !static_cast<const Compare&>(*this)(b, a); - } -}; - -template <typename Key, typename CompareTo> -struct btree_upper_bound_compare_to_adapter : public CompareTo { - btree_upper_bound_compare_to_adapter(CompareTo c) : CompareTo(c) {} - int operator()(const Key &a, const Key &b) const { - return static_cast<const CompareTo&>(*this)(b, a); - } -}; - -// Dispatch helper class for using linear search with plain compare. -template <typename K, typename N, typename Compare> -struct btree_linear_search_plain_compare { - static int lower_bound(const K &k, const N &n, Compare comp) { - return n.linear_search_plain_compare(k, 0, n.count(), comp); - } - static int upper_bound(const K &k, const N &n, Compare comp) { - typedef btree_upper_bound_adapter<K, Compare> upper_compare; - return n.linear_search_plain_compare(k, 0, n.count(), upper_compare(comp)); - } -}; - -// Dispatch helper class for using linear search with compare-to -template <typename K, typename N, typename CompareTo> -struct btree_linear_search_compare_to { - static int lower_bound(const K &k, const N &n, CompareTo comp) { - return n.linear_search_compare_to(k, 0, n.count(), comp); - } - static int upper_bound(const K &k, const N &n, CompareTo comp) { - typedef btree_upper_bound_adapter<K, - btree_key_comparer<K, CompareTo, true> > upper_compare; - return n.linear_search_plain_compare(k, 0, n.count(), upper_compare(comp)); - } -}; - -// Dispatch helper class for using binary search with plain compare. -template <typename K, typename N, typename Compare> -struct btree_binary_search_plain_compare { - static int lower_bound(const K &k, const N &n, Compare comp) { - return n.binary_search_plain_compare(k, 0, n.count(), comp); - } - static int upper_bound(const K &k, const N &n, Compare comp) { - typedef btree_upper_bound_adapter<K, Compare> upper_compare; - return n.binary_search_plain_compare(k, 0, n.count(), upper_compare(comp)); - } -}; - -// Dispatch helper class for using binary search with compare-to. -template <typename K, typename N, typename CompareTo> -struct btree_binary_search_compare_to { - static int lower_bound(const K &k, const N &n, CompareTo comp) { - return n.binary_search_compare_to(k, 0, n.count(), CompareTo()); - } - static int upper_bound(const K &k, const N &n, CompareTo comp) { - typedef btree_upper_bound_adapter<K, - btree_key_comparer<K, CompareTo, true> > upper_compare; - return n.linear_search_plain_compare(k, 0, n.count(), upper_compare(comp)); - } -}; - -// A node in the btree holding. The same node type is used for both internal -// and leaf nodes in the btree, though the nodes are allocated in such a way -// that the children array is only valid in internal nodes. -template <typename Params> -class btree_node { - public: - typedef Params params_type; - typedef btree_node<Params> self_type; - typedef typename Params::key_type key_type; - typedef typename Params::data_type data_type; - typedef typename Params::value_type value_type; - typedef typename Params::mutable_value_type mutable_value_type; - typedef typename Params::pointer pointer; - typedef typename Params::const_pointer const_pointer; - typedef typename Params::reference reference; - typedef typename Params::const_reference const_reference; - typedef typename Params::key_compare key_compare; - typedef typename Params::size_type size_type; - typedef typename Params::difference_type difference_type; - // Typedefs for the various types of node searches. - typedef btree_linear_search_plain_compare< - key_type, self_type, key_compare> linear_search_plain_compare_type; - typedef btree_linear_search_compare_to< - key_type, self_type, key_compare> linear_search_compare_to_type; - typedef btree_binary_search_plain_compare< - key_type, self_type, key_compare> binary_search_plain_compare_type; - typedef btree_binary_search_compare_to< - key_type, self_type, key_compare> binary_search_compare_to_type; - // If we have a valid key-compare-to type, use linear_search_compare_to, - // otherwise use linear_search_plain_compare. - typedef typename if_< - Params::is_key_compare_to::value, - linear_search_compare_to_type, - linear_search_plain_compare_type>::type linear_search_type; - // If we have a valid key-compare-to type, use binary_search_compare_to, - // otherwise use binary_search_plain_compare. - typedef typename if_< - Params::is_key_compare_to::value, - binary_search_compare_to_type, - binary_search_plain_compare_type>::type binary_search_type; - // If the key is an integral or floating point type, use linear search which - // is faster than binary search for such types. Might be wise to also - // configure linear search based on node-size. - typedef typename if_< - std::is_integral<key_type>::value || - std::is_floating_point<key_type>::value, - linear_search_type, binary_search_type>::type search_type; - - struct base_fields { - typedef typename Params::node_count_type field_type; - - // A boolean indicating whether the node is a leaf or not. - bool leaf; - // The position of the node in the node's parent. - field_type position; - // The maximum number of values the node can hold. - field_type max_count; - // The count of the number of values in the node. - field_type count; - // A pointer to the node's parent. - btree_node *parent; - }; - - enum { - kValueSize = params_type::kValueSize, - kTargetNodeSize = params_type::kTargetNodeSize, - - // Compute how many values we can fit onto a leaf node. - kNodeTargetValues = (kTargetNodeSize - sizeof(base_fields)) / kValueSize, - // We need a minimum of 3 values per internal node in order to perform - // splitting (1 value for the two nodes involved in the split and 1 value - // propagated to the parent as the delimiter for the split). - kNodeValues = kNodeTargetValues >= 3 ? kNodeTargetValues : 3, - - kExactMatch = 1 << 30, - kMatchMask = kExactMatch - 1, - }; - - struct leaf_fields : public base_fields { - // The array of values. Only the first count of these values have been - // constructed and are valid. - mutable_value_type values[kNodeValues]; - }; - - struct internal_fields : public leaf_fields { - // The array of child pointers. The keys in children_[i] are all less than - // key(i). The keys in children_[i + 1] are all greater than key(i). There - // are always count + 1 children. - btree_node *children[kNodeValues + 1]; - }; - - struct root_fields : public internal_fields { - btree_node *rightmost; - size_type size; - }; - - public: - // Getter/setter for whether this is a leaf node or not. This value doesn't - // change after the node is created. - bool leaf() const { return fields_.leaf; } - - // Getter for the position of this node in its parent. - int position() const { return fields_.position; } - void set_position(int v) { fields_.position = v; } - - // Getter/setter for the number of values stored in this node. - int count() const { return fields_.count; } - void set_count(int v) { fields_.count = v; } - int max_count() const { return fields_.max_count; } - - // Getter for the parent of this node. - btree_node* parent() const { return fields_.parent; } - // Getter for whether the node is the root of the tree. The parent of the - // root of the tree is the leftmost node in the tree which is guaranteed to - // be a leaf. - bool is_root() const { return parent()->leaf(); } - void make_root() { - assert(parent()->is_root()); - fields_.parent = fields_.parent->parent(); - } - - // Getter for the rightmost root node field. Only valid on the root node. - btree_node* rightmost() const { return fields_.rightmost; } - btree_node** mutable_rightmost() { return &fields_.rightmost; } - - // Getter for the size root node field. Only valid on the root node. - size_type size() const { return fields_.size; } - size_type* mutable_size() { return &fields_.size; } - - // Getters for the key/value at position i in the node. - const key_type& key(int i) const { - return params_type::key(fields_.values[i]); - } - reference value(int i) { - return reinterpret_cast<reference>(fields_.values[i]); - } - const_reference value(int i) const { - return reinterpret_cast<const_reference>(fields_.values[i]); - } - mutable_value_type* mutable_value(int i) { - return &fields_.values[i]; - } - - // Swap value i in this node with value j in node x. - void value_swap(int i, btree_node *x, int j) { - params_type::swap(mutable_value(i), x->mutable_value(j)); - } - - // Getters/setter for the child at position i in the node. - btree_node* child(int i) const { return fields_.children[i]; } - btree_node** mutable_child(int i) { return &fields_.children[i]; } - void set_child(int i, btree_node *c) { - *mutable_child(i) = c; - c->fields_.parent = this; - c->fields_.position = i; - } - - // Returns the position of the first value whose key is not less than k. - template <typename Compare> - int lower_bound(const key_type &k, const Compare &comp) const { - return search_type::lower_bound(k, *this, comp); - } - // Returns the position of the first value whose key is greater than k. - template <typename Compare> - int upper_bound(const key_type &k, const Compare &comp) const { - return search_type::upper_bound(k, *this, comp); - } - - // Returns the position of the first value whose key is not less than k using - // linear search performed using plain compare. - template <typename Compare> - int linear_search_plain_compare( - const key_type &k, int s, int e, const Compare &comp) const { - while (s < e) { - if (!btree_compare_keys(comp, key(s), k)) { - break; - } - ++s; - } - return s; - } - - // Returns the position of the first value whose key is not less than k using - // linear search performed using compare-to. - template <typename Compare> - int linear_search_compare_to( - const key_type &k, int s, int e, const Compare &comp) const { - while (s < e) { - int c = comp(key(s), k); - if (c == 0) { - return s | kExactMatch; - } else if (c > 0) { - break; - } - ++s; - } - return s; - } - - // Returns the position of the first value whose key is not less than k using - // binary search performed using plain compare. - template <typename Compare> - int binary_search_plain_compare( - const key_type &k, int s, int e, const Compare &comp) const { - while (s != e) { - int mid = (s + e) / 2; - if (btree_compare_keys(comp, key(mid), k)) { - s = mid + 1; - } else { - e = mid; - } - } - return s; - } - - // Returns the position of the first value whose key is not less than k using - // binary search performed using compare-to. - template <typename CompareTo> - int binary_search_compare_to( - const key_type &k, int s, int e, const CompareTo &comp) const { - while (s != e) { - int mid = (s + e) / 2; - int c = comp(key(mid), k); - if (c < 0) { - s = mid + 1; - } else if (c > 0) { - e = mid; - } else { - // Need to return the first value whose key is not less than k, which - // requires continuing the binary search. Note that we are guaranteed - // that the result is an exact match because if "key(mid-1) < k" the - // call to binary_search_compare_to() will return "mid". - s = binary_search_compare_to(k, s, mid, comp); - return s | kExactMatch; - } - } - return s; - } - - // Inserts the value x at position i, shifting all existing values and - // children at positions >= i to the right by 1. - void insert_value(int i, const value_type &x); - - // Removes the value at position i, shifting all existing values and children - // at positions > i to the left by 1. - void remove_value(int i); - - // Rebalances a node with its right sibling. - void rebalance_right_to_left(btree_node *sibling, int to_move); - void rebalance_left_to_right(btree_node *sibling, int to_move); - - // Splits a node, moving a portion of the node's values to its right sibling. - void split(btree_node *sibling, int insert_position); - - // Merges a node with its right sibling, moving all of the values and the - // delimiting key in the parent node onto itself. - void merge(btree_node *sibling); - - // Swap the contents of "this" and "src". - void swap(btree_node *src); - - // Node allocation/deletion routines. - static btree_node* init_leaf( - leaf_fields *f, btree_node *parent, int max_count) { - btree_node *n = reinterpret_cast<btree_node*>(f); - f->leaf = 1; - f->position = 0; - f->max_count = max_count; - f->count = 0; - f->parent = parent; - if (!NDEBUG) { - memset(&f->values, 0, max_count * sizeof(value_type)); - } - return n; - } - static btree_node* init_internal(internal_fields *f, btree_node *parent) { - btree_node *n = init_leaf(f, parent, kNodeValues); - f->leaf = 0; - if (!NDEBUG) { - memset(f->children, 0, sizeof(f->children)); - } - return n; - } - static btree_node* init_root(root_fields *f, btree_node *parent) { - btree_node *n = init_internal(f, parent); - f->rightmost = parent; - f->size = parent->count(); - return n; - } - void destroy() { - for (int i = 0; i < count(); ++i) { - value_destroy(i); - } - } - - private: - void value_init(int i) { - new (&fields_.values[i]) mutable_value_type; - } - void value_init(int i, const value_type &x) { - new (&fields_.values[i]) mutable_value_type(x); - } - void value_destroy(int i) { - fields_.values[i].~mutable_value_type(); - } - - private: - root_fields fields_; - - private: - btree_node(const btree_node&); - void operator=(const btree_node&); -}; - -template <typename Node, typename Reference, typename Pointer> -struct btree_iterator { - typedef typename Node::key_type key_type; - typedef typename Node::size_type size_type; - typedef typename Node::difference_type difference_type; - typedef typename Node::params_type params_type; - - typedef Node node_type; - typedef typename std::remove_const<Node>::type normal_node; - typedef const Node const_node; - typedef typename params_type::value_type value_type; - typedef typename params_type::pointer normal_pointer; - typedef typename params_type::reference normal_reference; - typedef typename params_type::const_pointer const_pointer; - typedef typename params_type::const_reference const_reference; - - typedef Pointer pointer; - typedef Reference reference; - typedef std::bidirectional_iterator_tag iterator_category; - - typedef btree_iterator< - normal_node, normal_reference, normal_pointer> iterator; - typedef btree_iterator< - const_node, const_reference, const_pointer> const_iterator; - typedef btree_iterator<Node, Reference, Pointer> self_type; - - btree_iterator() - : node(NULL), - position(-1) { - } - btree_iterator(Node *n, int p) - : node(n), - position(p) { - } - btree_iterator(const iterator &x) - : node(x.node), - position(x.position) { - } - - // Increment/decrement the iterator. - void increment() { - if (node->leaf() && ++position < node->count()) { - return; - } - increment_slow(); - } - void increment_by(int count); - void increment_slow(); - - void decrement() { - if (node->leaf() && --position >= 0) { - return; - } - decrement_slow(); - } - void decrement_slow(); - - bool operator==(const const_iterator &x) const { - return node == x.node && position == x.position; - } - bool operator!=(const const_iterator &x) const { - return node != x.node || position != x.position; - } - - // Accessors for the key/value the iterator is pointing at. - const key_type& key() const { - return node->key(position); - } - reference operator*() const { - return node->value(position); - } - pointer operator->() const { - return &node->value(position); - } - - self_type& operator++() { - increment(); - return *this; - } - self_type& operator--() { - decrement(); - return *this; - } - self_type operator++(int) { - self_type tmp = *this; - ++*this; - return tmp; - } - self_type operator--(int) { - self_type tmp = *this; - --*this; - return tmp; - } - - // The node in the tree the iterator is pointing at. - Node *node; - // The position within the node of the tree the iterator is pointing at. - int position; -}; - -// Dispatch helper class for using btree::internal_locate with plain compare. -struct btree_internal_locate_plain_compare { - template <typename K, typename T, typename Iter> - static std::pair<Iter, int> dispatch(const K &k, const T &t, Iter iter) { - return t.internal_locate_plain_compare(k, iter); - } -}; - -// Dispatch helper class for using btree::internal_locate with compare-to. -struct btree_internal_locate_compare_to { - template <typename K, typename T, typename Iter> - static std::pair<Iter, int> dispatch(const K &k, const T &t, Iter iter) { - return t.internal_locate_compare_to(k, iter); - } -}; - -template <typename Params> -class btree : public Params::key_compare { - typedef btree<Params> self_type; - typedef btree_node<Params> node_type; - typedef typename node_type::base_fields base_fields; - typedef typename node_type::leaf_fields leaf_fields; - typedef typename node_type::internal_fields internal_fields; - typedef typename node_type::root_fields root_fields; - typedef typename Params::is_key_compare_to is_key_compare_to; - - friend struct btree_internal_locate_plain_compare; - friend struct btree_internal_locate_compare_to; - typedef typename if_< - is_key_compare_to::value, - btree_internal_locate_compare_to, - btree_internal_locate_plain_compare>::type internal_locate_type; - - enum { - kNodeValues = node_type::kNodeValues, - kMinNodeValues = kNodeValues / 2, - kValueSize = node_type::kValueSize, - kExactMatch = node_type::kExactMatch, - kMatchMask = node_type::kMatchMask, - }; - - // A helper class to get the empty base class optimization for 0-size - // allocators. Base is internal_allocator_type. - // (e.g. empty_base_handle<internal_allocator_type, node_type*>). If Base is - // 0-size, the compiler doesn't have to reserve any space for it and - // sizeof(empty_base_handle) will simply be sizeof(Data). Google [empty base - // class optimization] for more details. - template <typename Base, typename Data> - struct empty_base_handle : public Base { - empty_base_handle(const Base &b, const Data &d) - : Base(b), - data(d) { - } - Data data; - }; - - struct node_stats { - node_stats(ssize_t l, ssize_t i) - : leaf_nodes(l), - internal_nodes(i) { - } - - node_stats& operator+=(const node_stats &x) { - leaf_nodes += x.leaf_nodes; - internal_nodes += x.internal_nodes; - return *this; - } - - ssize_t leaf_nodes; - ssize_t internal_nodes; - }; - - public: - typedef Params params_type; - typedef typename Params::key_type key_type; - typedef typename Params::data_type data_type; - typedef typename Params::mapped_type mapped_type; - typedef typename Params::value_type value_type; - typedef typename Params::key_compare key_compare; - typedef typename Params::pointer pointer; - typedef typename Params::const_pointer const_pointer; - typedef typename Params::reference reference; - typedef typename Params::const_reference const_reference; - typedef typename Params::size_type size_type; - typedef typename Params::difference_type difference_type; - typedef btree_iterator<node_type, reference, pointer> iterator; - typedef typename iterator::const_iterator const_iterator; - typedef std::reverse_iterator<const_iterator> const_reverse_iterator; - typedef std::reverse_iterator<iterator> reverse_iterator; - - typedef typename Params::allocator_type allocator_type; - typedef typename allocator_type::template rebind<char>::other - internal_allocator_type; - - public: - // Default constructor. - btree(const key_compare &comp, const allocator_type &alloc); - - // Copy constructor. - btree(const self_type &x); - - // Destructor. - ~btree() { - clear(); - } - - // Iterator routines. - iterator begin() { - return iterator(leftmost(), 0); - } - const_iterator begin() const { - return const_iterator(leftmost(), 0); - } - iterator end() { - return iterator(rightmost(), rightmost() ? rightmost()->count() : 0); - } - const_iterator end() const { - return const_iterator(rightmost(), rightmost() ? rightmost()->count() : 0); - } - reverse_iterator rbegin() { - return reverse_iterator(end()); - } - const_reverse_iterator rbegin() const { - return const_reverse_iterator(end()); - } - reverse_iterator rend() { - return reverse_iterator(begin()); - } - const_reverse_iterator rend() const { - return const_reverse_iterator(begin()); - } - - // Finds the first element whose key is not less than key. - iterator lower_bound(const key_type &key) { - return internal_end( - internal_lower_bound(key, iterator(root(), 0))); - } - const_iterator lower_bound(const key_type &key) const { - return internal_end( - internal_lower_bound(key, const_iterator(root(), 0))); - } - - // Finds the first element whose key is greater than key. - iterator upper_bound(const key_type &key) { - return internal_end( - internal_upper_bound(key, iterator(root(), 0))); - } - const_iterator upper_bound(const key_type &key) const { - return internal_end( - internal_upper_bound(key, const_iterator(root(), 0))); - } - - // Finds the range of values which compare equal to key. The first member of - // the returned pair is equal to lower_bound(key). The second member pair of - // the pair is equal to upper_bound(key). - std::pair<iterator,iterator> equal_range(const key_type &key) { - return std::make_pair(lower_bound(key), upper_bound(key)); - } - std::pair<const_iterator,const_iterator> equal_range(const key_type &key) const { - return std::make_pair(lower_bound(key), upper_bound(key)); - } - - // Inserts a value into the btree only if it does not already exist. The - // boolean return value indicates whether insertion succeeded or failed. The - // ValuePointer type is used to avoid instatiating the value unless the key - // is being inserted. Value is not dereferenced if the key already exists in - // the btree. See btree_map::operator[]. - template <typename ValuePointer> - std::pair<iterator,bool> insert_unique(const key_type &key, ValuePointer value); - - // Inserts a value into the btree only if it does not already exist. The - // boolean return value indicates whether insertion succeeded or failed. - std::pair<iterator,bool> insert_unique(const value_type &v) { - return insert_unique(params_type::key(v), &v); - } - - // Insert with hint. Check to see if the value should be placed immediately - // before position in the tree. If it does, then the insertion will take - // amortized constant time. If not, the insertion will take amortized - // logarithmic time as if a call to insert_unique(v) were made. - iterator insert_unique(iterator position, const value_type &v); - - // Insert a range of values into the btree. - template <typename InputIterator> - void insert_unique(InputIterator b, InputIterator e); - - // Inserts a value into the btree. The ValuePointer type is used to avoid - // instatiating the value unless the key is being inserted. Value is not - // dereferenced if the key already exists in the btree. See - // btree_map::operator[]. - template <typename ValuePointer> - iterator insert_multi(const key_type &key, ValuePointer value); - - // Inserts a value into the btree. - iterator insert_multi(const value_type &v) { - return insert_multi(params_type::key(v), &v); - } - - // Insert with hint. Check to see if the value should be placed immediately - // before position in the tree. If it does, then the insertion will take - // amortized constant time. If not, the insertion will take amortized - // logarithmic time as if a call to insert_multi(v) were made. - iterator insert_multi(iterator position, const value_type &v); - - // Insert a range of values into the btree. - template <typename InputIterator> - void insert_multi(InputIterator b, InputIterator e); - - void assign(const self_type &x); - - // Erase the specified iterator from the btree. The iterator must be valid - // (i.e. not equal to end()). Return an iterator pointing to the node after - // the one that was erased (or end() if none exists). - iterator erase(iterator iter); - - // Erases range. Returns the number of keys erased. - int erase(iterator begin, iterator end); - - // Erases the specified key from the btree. Returns 1 if an element was - // erased and 0 otherwise. - int erase_unique(const key_type &key); - - // Erases all of the entries matching the specified key from the - // btree. Returns the number of elements erased. - int erase_multi(const key_type &key); - - // Finds the iterator corresponding to a key or returns end() if the key is - // not present. - iterator find_unique(const key_type &key) { - return internal_end( - internal_find_unique(key, iterator(root(), 0))); - } - const_iterator find_unique(const key_type &key) const { - return internal_end( - internal_find_unique(key, const_iterator(root(), 0))); - } - iterator find_multi(const key_type &key) { - return internal_end( - internal_find_multi(key, iterator(root(), 0))); - } - const_iterator find_multi(const key_type &key) const { - return internal_end( - internal_find_multi(key, const_iterator(root(), 0))); - } - - // Returns a count of the number of times the key appears in the btree. - size_type count_unique(const key_type &key) const { - const_iterator b = internal_find_unique( - key, const_iterator(root(), 0)); - if (!b.node) { - // The key doesn't exist in the tree. - return 0; - } - return 1; - } - // Returns a count of the number of times the key appears in the btree. - size_type count_multi(const key_type &key) const { - return distance(lower_bound(key), upper_bound(key)); - } - - // Clear the btree, deleting all of the values it contains. - void clear(); - - // Swap the contents of *this and x. - void swap(self_type &x); - - // Assign the contents of x to *this. - self_type& operator=(const self_type &x) { - if (&x == this) { - // Don't copy onto ourselves. - return *this; - } - assign(x); - return *this; - } - - key_compare* mutable_key_comp() { - return this; - } - const key_compare& key_comp() const { - return *this; - } - bool compare_keys(const key_type &x, const key_type &y) const { - return btree_compare_keys(key_comp(), x, y); - } - - // Dump the btree to the specified ostream. Requires that operator<< is - // defined for Key and Value. - void dump(std::ostream &os) const { - if (root() != NULL) { - internal_dump(os, root(), 0); - } - } - - // Verifies the structure of the btree. - void verify() const; - - // Size routines. Note that empty() is slightly faster than doing size()==0. - size_type size() const { - if (empty()) return 0; - if (root()->leaf()) return root()->count(); - return root()->size(); - } - size_type max_size() const { return std::numeric_limits<size_type>::max(); } - bool empty() const { return root() == NULL; } - - // The height of the btree. An empty tree will have height 0. - size_type height() const { - size_type h = 0; - if (root()) { - // Count the length of the chain from the leftmost node up to the - // root. We actually count from the root back around to the level below - // the root, but the calculation is the same because of the circularity - // of that traversal. - const node_type *n = root(); - do { - ++h; - n = n->parent(); - } while (n != root()); - } - return h; - } - - // The number of internal, leaf and total nodes used by the btree. - size_type leaf_nodes() const { - return internal_stats(root()).leaf_nodes; - } - size_type internal_nodes() const { - return internal_stats(root()).internal_nodes; - } - size_type nodes() const { - node_stats stats = internal_stats(root()); - return stats.leaf_nodes + stats.internal_nodes; - } - - // The total number of bytes used by the btree. - size_type bytes_used() const { - node_stats stats = internal_stats(root()); - if (stats.leaf_nodes == 1 && stats.internal_nodes == 0) { - return sizeof(*this) + - sizeof(base_fields) + root()->max_count() * sizeof(value_type); - } else { - return sizeof(*this) + - sizeof(root_fields) - sizeof(internal_fields) + - stats.leaf_nodes * sizeof(leaf_fields) + - stats.internal_nodes * sizeof(internal_fields); - } - } - - // The average number of bytes used per value stored in the btree. - static double average_bytes_per_value() { - // Returns the number of bytes per value on a leaf node that is 75% - // full. Experimentally, this matches up nicely with the computed number of - // bytes per value in trees that had their values inserted in random order. - return sizeof(leaf_fields) / (kNodeValues * 0.75); - } - - // The fullness of the btree. Computed as the number of elements in the btree - // divided by the maximum number of elements a tree with the current number - // of nodes could hold. A value of 1 indicates perfect space - // utilization. Smaller values indicate space wastage. - double fullness() const { - return double(size()) / (nodes() * kNodeValues); - } - // The overhead of the btree structure in bytes per node. Computed as the - // total number of bytes used by the btree minus the number of bytes used for - // storing elements divided by the number of elements. - double overhead() const { - if (empty()) { - return 0.0; - } - return (bytes_used() - size() * kValueSize) / double(size()); - } - - private: - // Internal accessor routines. - node_type* root() { return root_.data; } - const node_type* root() const { return root_.data; } - node_type** mutable_root() { return &root_.data; } - - // The rightmost node is stored in the root node. - node_type* rightmost() { - return (!root() || root()->leaf()) ? root() : root()->rightmost(); - } - const node_type* rightmost() const { - return (!root() || root()->leaf()) ? root() : root()->rightmost(); - } - node_type** mutable_rightmost() { return root()->mutable_rightmost(); } - - // The leftmost node is stored as the parent of the root node. - node_type* leftmost() { return root() ? root()->parent() : NULL; } - const node_type* leftmost() const { return root() ? root()->parent() : NULL; } - - // The size of the tree is stored in the root node. - size_type* mutable_size() { return root()->mutable_size(); } - - // Allocator routines. - internal_allocator_type* mutable_internal_allocator() { - return static_cast<internal_allocator_type*>(&root_); - } - const internal_allocator_type& internal_allocator() const { - return *static_cast<const internal_allocator_type*>(&root_); - } - - // Node creation/deletion routines. - node_type* new_internal_node(node_type *parent) { - internal_fields *p = reinterpret_cast<internal_fields*>( - mutable_internal_allocator()->allocate(sizeof(internal_fields))); - return node_type::init_internal(p, parent); - } - node_type* new_internal_root_node() { - root_fields *p = reinterpret_cast<root_fields*>( - mutable_internal_allocator()->allocate(sizeof(root_fields))); - return node_type::init_root(p, root()->parent()); - } - node_type* new_leaf_node(node_type *parent) { - leaf_fields *p = reinterpret_cast<leaf_fields*>( - mutable_internal_allocator()->allocate(sizeof(leaf_fields))); - return node_type::init_leaf(p, parent, kNodeValues); - } - node_type* new_leaf_root_node(int max_count) { - leaf_fields *p = reinterpret_cast<leaf_fields*>( - mutable_internal_allocator()->allocate( - sizeof(base_fields) + max_count * sizeof(value_type))); - return node_type::init_leaf(p, reinterpret_cast<node_type*>(p), max_count); - } - void delete_internal_node(node_type *node) { - node->destroy(); - assert(node != root()); - mutable_internal_allocator()->deallocate( - reinterpret_cast<char*>(node), sizeof(internal_fields)); - } - void delete_internal_root_node() { - root()->destroy(); - mutable_internal_allocator()->deallocate( - reinterpret_cast<char*>(root()), sizeof(root_fields)); - } - void delete_leaf_node(node_type *node) { - node->destroy(); - mutable_internal_allocator()->deallocate( - reinterpret_cast<char*>(node), - sizeof(base_fields) + node->max_count() * sizeof(value_type)); - } - - // Rebalances or splits the node iter points to. - void rebalance_or_split(iterator *iter); - - // Merges the values of left, right and the delimiting key on their parent - // onto left, removing the delimiting key and deleting right. - void merge_nodes(node_type *left, node_type *right); - - // Tries to merge node with its left or right sibling, and failing that, - // rebalance with its left or right sibling. Returns true if a merge - // occurred, at which point it is no longer valid to access node. Returns - // false if no merging took place. - bool try_merge_or_rebalance(iterator *iter); - - // Tries to shrink the height of the tree by 1. - void try_shrink(); - - iterator internal_end(iterator iter) { - return iter.node ? iter : end(); - } - const_iterator internal_end(const_iterator iter) const { - return iter.node ? iter : end(); - } - - // Inserts a value into the btree immediately before iter. Requires that - // key(v) <= iter.key() and (--iter).key() <= key(v). - iterator internal_insert(iterator iter, const value_type &v); - - // Returns an iterator pointing to the first value >= the value "iter" is - // pointing at. Note that "iter" might be pointing to an invalid location as - // iter.position == iter.node->count(). This routine simply moves iter up in - // the tree to a valid location. - template <typename IterType> - static IterType internal_last(IterType iter); - - // Returns an iterator pointing to the leaf position at which key would - // reside in the tree. We provide 2 versions of internal_locate. The first - // version (internal_locate_plain_compare) always returns 0 for the second - // field of the pair. The second version (internal_locate_compare_to) is for - // the key-compare-to specialization and returns either kExactMatch (if the - // key was found in the tree) or -kExactMatch (if it wasn't) in the second - // field of the pair. The compare_to specialization allows the caller to - // avoid a subsequent comparison to determine if an exact match was made, - // speeding up string keys. - template <typename IterType> - std::pair<IterType, int> internal_locate( - const key_type &key, IterType iter) const; - template <typename IterType> - std::pair<IterType, int> internal_locate_plain_compare( - const key_type &key, IterType iter) const; - template <typename IterType> - std::pair<IterType, int> internal_locate_compare_to( - const key_type &key, IterType iter) const; - - // Internal routine which implements lower_bound(). - template <typename IterType> - IterType internal_lower_bound( - const key_type &key, IterType iter) const; - - // Internal routine which implements upper_bound(). - template <typename IterType> - IterType internal_upper_bound( - const key_type &key, IterType iter) const; - - // Internal routine which implements find_unique(). - template <typename IterType> - IterType internal_find_unique( - const key_type &key, IterType iter) const; - - // Internal routine which implements find_multi(). - template <typename IterType> - IterType internal_find_multi( - const key_type &key, IterType iter) const; - - // Deletes a node and all of its children. - void internal_clear(node_type *node); - - // Dumps a node and all of its children to the specified ostream. - void internal_dump(std::ostream &os, const node_type *node, int level) const; - - // Verifies the tree structure of node. - int internal_verify(const node_type *node, - const key_type *lo, const key_type *hi) const; - - node_stats internal_stats(const node_type *node) const { - if (!node) { - return node_stats(0, 0); - } - if (node->leaf()) { - return node_stats(1, 0); - } - node_stats res(0, 1); - for (int i = 0; i <= node->count(); ++i) { - res += internal_stats(node->child(i)); - } - return res; - } - - private: - empty_base_handle<internal_allocator_type, node_type*> root_; - - private: - // A never instantiated helper function that returns big_ if we have a - // key-compare-to functor or if R is bool and small_ otherwise. - template <typename R> - static typename if_< - if_<is_key_compare_to::value, - std::is_same<R, int>, - std::is_same<R, bool> >::type::value, - big_, small_>::type key_compare_checker(R); - - // A never instantiated helper function that returns the key comparison - // functor. - static key_compare key_compare_helper(); - - // Verify that key_compare returns a bool. This is similar to the way - // is_convertible in base/type_traits.h works. Note that key_compare_checker - // is never actually invoked. The compiler will select which - // key_compare_checker() to instantiate and then figure out the size of the - // return type of key_compare_checker() at compile time which we then check - // against the sizeof of big_. - COMPILE_ASSERT( - sizeof(key_compare_checker(key_compare_helper()(key_type(), key_type()))) == - sizeof(big_), - key_comparison_function_must_return_bool); - - // Note: We insist on kTargetValues, which is computed from - // Params::kTargetNodeSize, must fit the base_fields::field_type. - COMPILE_ASSERT(kNodeValues < - (1 << (8 * sizeof(typename base_fields::field_type))), - target_node_size_too_large); - - // Test the assumption made in setting kNodeValueSpace. - COMPILE_ASSERT(sizeof(base_fields) >= 2 * sizeof(void*), - node_space_assumption_incorrect); -}; - -//// -// btree_node methods -template <typename P> -inline void btree_node<P>::insert_value(int i, const value_type &x) { - assert(i <= count()); - value_init(count(), x); - for (int j = count(); j > i; --j) { - value_swap(j, this, j - 1); - } - set_count(count() + 1); - - if (!leaf()) { - ++i; - for (int j = count(); j > i; --j) { - *mutable_child(j) = child(j - 1); - child(j)->set_position(j); - } - *mutable_child(i) = NULL; - } -} - -template <typename P> -inline void btree_node<P>::remove_value(int i) { - if (!leaf()) { - assert(child(i + 1)->count() == 0); - for (int j = i + 1; j < count(); ++j) { - *mutable_child(j) = child(j + 1); - child(j)->set_position(j); - } - *mutable_child(count()) = NULL; - } - - set_count(count() - 1); - for (; i < count(); ++i) { - value_swap(i, this, i + 1); - } - value_destroy(i); -} - -template <typename P> -void btree_node<P>::rebalance_right_to_left(btree_node *src, int to_move) { - assert(parent() == src->parent()); - assert(position() + 1 == src->position()); - assert(src->count() >= count()); - assert(to_move >= 1); - assert(to_move <= src->count()); - - // Make room in the left node for the new values. - for (int i = 0; i < to_move; ++i) { - value_init(i + count()); - } - - // Move the delimiting value to the left node and the new delimiting value - // from the right node. - value_swap(count(), parent(), position()); - parent()->value_swap(position(), src, to_move - 1); - - // Move the values from the right to the left node. - for (int i = 1; i < to_move; ++i) { - value_swap(count() + i, src, i - 1); - } - // Shift the values in the right node to their correct position. - for (int i = to_move; i < src->count(); ++i) { - src->value_swap(i - to_move, src, i); - } - for (int i = 1; i <= to_move; ++i) { - src->value_destroy(src->count() - i); - } - - if (!leaf()) { - // Move the child pointers from the right to the left node. - for (int i = 0; i < to_move; ++i) { - set_child(1 + count() + i, src->child(i)); - } - for (int i = 0; i <= src->count() - to_move; ++i) { - assert(i + to_move <= src->max_count()); - src->set_child(i, src->child(i + to_move)); - *src->mutable_child(i + to_move) = NULL; - } - } - - // Fixup the counts on the src and dest nodes. - set_count(count() + to_move); - src->set_count(src->count() - to_move); -} - -template <typename P> -void btree_node<P>::rebalance_left_to_right(btree_node *dest, int to_move) { - assert(parent() == dest->parent()); - assert(position() + 1 == dest->position()); - assert(count() >= dest->count()); - assert(to_move >= 1); - assert(to_move <= count()); - - // Make room in the right node for the new values. - for (int i = 0; i < to_move; ++i) { - dest->value_init(i + dest->count()); - } - for (int i = dest->count() - 1; i >= 0; --i) { - dest->value_swap(i, dest, i + to_move); - } - - // Move the delimiting value to the right node and the new delimiting value - // from the left node. - dest->value_swap(to_move - 1, parent(), position()); - parent()->value_swap(position(), this, count() - to_move); - value_destroy(count() - to_move); - - // Move the values from the left to the right node. - for (int i = 1; i < to_move; ++i) { - value_swap(count() - to_move + i, dest, i - 1); - value_destroy(count() - to_move + i); - } - - if (!leaf()) { - // Move the child pointers from the left to the right node. - for (int i = dest->count(); i >= 0; --i) { - dest->set_child(i + to_move, dest->child(i)); - *dest->mutable_child(i) = NULL; - } - for (int i = 1; i <= to_move; ++i) { - dest->set_child(i - 1, child(count() - to_move + i)); - *mutable_child(count() - to_move + i) = NULL; - } - } - - // Fixup the counts on the src and dest nodes. - set_count(count() - to_move); - dest->set_count(dest->count() + to_move); -} - -template <typename P> -void btree_node<P>::split(btree_node *dest, int insert_position) { - assert(dest->count() == 0); - - // We bias the split based on the position being inserted. If we're - // inserting at the beginning of the left node then bias the split to put - // more values on the right node. If we're inserting at the end of the - // right node then bias the split to put more values on the left node. - if (insert_position == 0) { - dest->set_count(count() - 1); - } else if (insert_position == max_count()) { - dest->set_count(0); - } else { - dest->set_count(count() / 2); - } - set_count(count() - dest->count()); - assert(count() >= 1); - - // Move values from the left sibling to the right sibling. - for (int i = 0; i < dest->count(); ++i) { - dest->value_init(i); - value_swap(count() + i, dest, i); - value_destroy(count() + i); - } - - // The split key is the largest value in the left sibling. - set_count(count() - 1); - parent()->insert_value(position(), value_type()); - value_swap(count(), parent(), position()); - value_destroy(count()); - parent()->set_child(position() + 1, dest); - - if (!leaf()) { - for (int i = 0; i <= dest->count(); ++i) { - assert(child(count() + i + 1) != NULL); - dest->set_child(i, child(count() + i + 1)); - *mutable_child(count() + i + 1) = NULL; - } - } -} - -template <typename P> -void btree_node<P>::merge(btree_node *src) { - assert(parent() == src->parent()); - assert(position() + 1 == src->position()); - - // Move the delimiting value to the left node. - value_init(count()); - value_swap(count(), parent(), position()); - - // Move the values from the right to the left node. - for (int i = 0; i < src->count(); ++i) { - value_init(1 + count() + i); - value_swap(1 + count() + i, src, i); - src->value_destroy(i); - } - - if (!leaf()) { - // Move the child pointers from the right to the left node. - for (int i = 0; i <= src->count(); ++i) { - set_child(1 + count() + i, src->child(i)); - *src->mutable_child(i) = NULL; - } - } - - // Fixup the counts on the src and dest nodes. - set_count(1 + count() + src->count()); - src->set_count(0); - - // Remove the value on the parent node. - parent()->remove_value(position()); -} - -template <typename P> -void btree_node<P>::swap(btree_node *x) { - assert(leaf() == x->leaf()); - - // Swap the values. - for (int i = count(); i < x->count(); ++i) { - value_init(i); - } - for (int i = x->count(); i < count(); ++i) { - x->value_init(i); - } - int n = std::max(count(), x->count()); - for (int i = 0; i < n; ++i) { - value_swap(i, x, i); - } - for (int i = count(); i < x->count(); ++i) { - x->value_destroy(i); - } - for (int i = x->count(); i < count(); ++i) { - value_destroy(i); - } - - if (!leaf()) { - // Swap the child pointers. - for (int i = 0; i <= n; ++i) { - btree_swap_helper(*mutable_child(i), *x->mutable_child(i)); - } - for (int i = 0; i <= count(); ++i) { - x->child(i)->fields_.parent = x; - } - for (int i = 0; i <= x->count(); ++i) { - child(i)->fields_.parent = this; - } - } - - // Swap the counts. - btree_swap_helper(fields_.count, x->fields_.count); -} - -//// -// btree_iterator methods -template <typename N, typename R, typename P> -void btree_iterator<N, R, P>::increment_slow() { - if (node->leaf()) { - assert(position >= node->count()); - self_type save(*this); - while (position == node->count() && !node->is_root()) { - assert(node->parent()->child(node->position()) == node); - position = node->position(); - node = node->parent(); - } - if (position == node->count()) { - *this = save; - } - } else { - assert(position < node->count()); - node = node->child(position + 1); - while (!node->leaf()) { - node = node->child(0); - } - position = 0; - } -} - -template <typename N, typename R, typename P> -void btree_iterator<N, R, P>::increment_by(int count) { - while (count > 0) { - if (node->leaf()) { - int rest = node->count() - position; - position += std::min(rest, count); - count = count - rest; - if (position < node->count()) { - return; - } - } else { - --count; - } - increment_slow(); - } -} - -template <typename N, typename R, typename P> -void btree_iterator<N, R, P>::decrement_slow() { - if (node->leaf()) { - assert(position <= -1); - self_type save(*this); - while (position < 0 && !node->is_root()) { - assert(node->parent()->child(node->position()) == node); - position = node->position() - 1; - node = node->parent(); - } - if (position < 0) { - *this = save; - } - } else { - assert(position >= 0); - node = node->child(position); - while (!node->leaf()) { - node = node->child(node->count()); - } - position = node->count() - 1; - } -} - -//// -// btree methods -template <typename P> -btree<P>::btree(const key_compare &comp, const allocator_type &alloc) - : key_compare(comp), - root_(alloc, NULL) { -} - -template <typename P> -btree<P>::btree(const self_type &x) - : key_compare(x.key_comp()), - root_(x.internal_allocator(), NULL) { - assign(x); -} - -template <typename P> template <typename ValuePointer> -std::pair<typename btree<P>::iterator, bool> -btree<P>::insert_unique(const key_type &key, ValuePointer value) { - if (empty()) { - *mutable_root() = new_leaf_root_node(1); - } - - std::pair<iterator, int> res = internal_locate(key, iterator(root(), 0)); - iterator &iter = res.first; - if (res.second == kExactMatch) { - // The key already exists in the tree, do nothing. - return std::make_pair(internal_last(iter), false); - } else if (!res.second) { - iterator last = internal_last(iter); - if (last.node && !compare_keys(key, last.key())) { - // The key already exists in the tree, do nothing. - return std::make_pair(last, false); - } - } - - return std::make_pair(internal_insert(iter, *value), true); -} - -template <typename P> -inline typename btree<P>::iterator -btree<P>::insert_unique(iterator position, const value_type &v) { - if (!empty()) { - const key_type &key = params_type::key(v); - if (position == end() || compare_keys(key, position.key())) { - iterator prev = position; - if (position == begin() || compare_keys((--prev).key(), key)) { - // prev.key() < key < position.key() - return internal_insert(position, v); - } - } else if (compare_keys(position.key(), key)) { - iterator next = position; - ++next; - if (next == end() || compare_keys(key, next.key())) { - // position.key() < key < next.key() - return internal_insert(next, v); - } - } else { - // position.key() == key - return position; - } - } - return insert_unique(v).first; -} - -template <typename P> template <typename InputIterator> -void btree<P>::insert_unique(InputIterator b, InputIterator e) { - for (; b != e; ++b) { - insert_unique(end(), *b); - } -} - -template <typename P> template <typename ValuePointer> -typename btree<P>::iterator -btree<P>::insert_multi(const key_type &key, ValuePointer value) { - if (empty()) { - *mutable_root() = new_leaf_root_node(1); - } - - iterator iter = internal_upper_bound(key, iterator(root(), 0)); - if (!iter.node) { - iter = end(); - } - return internal_insert(iter, *value); -} - -template <typename P> -typename btree<P>::iterator -btree<P>::insert_multi(iterator position, const value_type &v) { - if (!empty()) { - const key_type &key = params_type::key(v); - if (position == end() || !compare_keys(position.key(), key)) { - iterator prev = position; - if (position == begin() || !compare_keys(key, (--prev).key())) { - // prev.key() <= key <= position.key() - return internal_insert(position, v); - } - } else { - iterator next = position; - ++next; - if (next == end() || !compare_keys(next.key(), key)) { - // position.key() < key <= next.key() - return internal_insert(next, v); - } - } - } - return insert_multi(v); -} - -template <typename P> template <typename InputIterator> -void btree<P>::insert_multi(InputIterator b, InputIterator e) { - for (; b != e; ++b) { - insert_multi(end(), *b); - } -} - -template <typename P> -void btree<P>::assign(const self_type &x) { - clear(); - - *mutable_key_comp() = x.key_comp(); - *mutable_internal_allocator() = x.internal_allocator(); - - // Assignment can avoid key comparisons because we know the order of the - // values is the same order we'll store them in. - for (const_iterator iter = x.begin(); iter != x.end(); ++iter) { - if (empty()) { - insert_multi(*iter); - } else { - // If the btree is not empty, we can just insert the new value at the end - // of the tree! - internal_insert(end(), *iter); - } - } -} - -template <typename P> -typename btree<P>::iterator btree<P>::erase(iterator iter) { - bool internal_delete = false; - if (!iter.node->leaf()) { - // Deletion of a value on an internal node. Swap the key with the largest - // value of our left child. This is easy, we just decrement iter. - iterator tmp_iter(iter--); - assert(iter.node->leaf()); - assert(!compare_keys(tmp_iter.key(), iter.key())); - iter.node->value_swap(iter.position, tmp_iter.node, tmp_iter.position); - internal_delete = true; - --*mutable_size(); - } else if (!root()->leaf()) { - --*mutable_size(); - } - - // Delete the key from the leaf. - iter.node->remove_value(iter.position); - - // We want to return the next value after the one we just erased. If we - // erased from an internal node (internal_delete == true), then the next - // value is ++(++iter). If we erased from a leaf node (internal_delete == - // false) then the next value is ++iter. Note that ++iter may point to an - // internal node and the value in the internal node may move to a leaf node - // (iter.node) when rebalancing is performed at the leaf level. - - // Merge/rebalance as we walk back up the tree. - iterator res(iter); - for (;;) { - if (iter.node == root()) { - try_shrink(); - if (empty()) { - return end(); - } - break; - } - if (iter.node->count() >= kMinNodeValues) { - break; - } - bool merged = try_merge_or_rebalance(&iter); - if (iter.node->leaf()) { - res = iter; - } - if (!merged) { - break; - } - iter.node = iter.node->parent(); - } - - // Adjust our return value. If we're pointing at the end of a node, advance - // the iterator. - if (res.position == res.node->count()) { - res.position = res.node->count() - 1; - ++res; - } - // If we erased from an internal node, advance the iterator. - if (internal_delete) { - ++res; - } - return res; -} - -template <typename P> -int btree<P>::erase(iterator b, iterator e) { - int count = distance(b, e); - for (int i = 0; i < count; i++) { - b = erase(b); - } - return count; -} - -template <typename P> -int btree<P>::erase_unique(const key_type &key) { - iterator iter = internal_find_unique(key, iterator(root(), 0)); - if (!iter.node) { - // The key doesn't exist in the tree, return nothing done. - return 0; - } - erase(iter); - return 1; -} - -template <typename P> -int btree<P>::erase_multi(const key_type &key) { - iterator b = internal_lower_bound(key, iterator(root(), 0)); - if (!b.node) { - // The key doesn't exist in the tree, return nothing done. - return 0; - } - // Delete all of the keys between begin and upper_bound(key). - iterator e = internal_end( - internal_upper_bound(key, iterator(root(), 0))); - return erase(b, e); -} - -template <typename P> -void btree<P>::clear() { - if (root() != NULL) { - internal_clear(root()); - } - *mutable_root() = NULL; -} - -template <typename P> -void btree<P>::swap(self_type &x) { - std::swap(static_cast<key_compare&>(*this), static_cast<key_compare&>(x)); - std::swap(root_, x.root_); -} - -template <typename P> -void btree<P>::verify() const { - if (root() != NULL) { - assert(size() == internal_verify(root(), NULL, NULL)); - assert(leftmost() == (++const_iterator(root(), -1)).node); - assert(rightmost() == (--const_iterator(root(), root()->count())).node); - assert(leftmost()->leaf()); - assert(rightmost()->leaf()); - } else { - assert(size() == 0); - assert(leftmost() == NULL); - assert(rightmost() == NULL); - } -} - -template <typename P> -void btree<P>::rebalance_or_split(iterator *iter) { - node_type *&node = iter->node; - int &insert_position = iter->position; - assert(node->count() == node->max_count()); - - // First try to make room on the node by rebalancing. - node_type *parent = node->parent(); - if (node != root()) { - if (node->position() > 0) { - // Try rebalancing with our left sibling. - node_type *left = parent->child(node->position() - 1); - if (left->count() < left->max_count()) { - // We bias rebalancing based on the position being inserted. If we're - // inserting at the end of the right node then we bias rebalancing to - // fill up the left node. - int to_move = (left->max_count() - left->count()) / - (1 + (insert_position < left->max_count())); - to_move = std::max(1, to_move); - - if (((insert_position - to_move) >= 0) || - ((left->count() + to_move) < left->max_count())) { - left->rebalance_right_to_left(node, to_move); - - assert(node->max_count() - node->count() == to_move); - insert_position = insert_position - to_move; - if (insert_position < 0) { - insert_position = insert_position + left->count() + 1; - node = left; - } - - assert(node->count() < node->max_count()); - return; - } - } - } - - if (node->position() < parent->count()) { - // Try rebalancing with our right sibling. - node_type *right = parent->child(node->position() + 1); - if (right->count() < right->max_count()) { - // We bias rebalancing based on the position being inserted. If we're - // inserting at the beginning of the left node then we bias rebalancing - // to fill up the right node. - int to_move = (right->max_count() - right->count()) / - (1 + (insert_position > 0)); - to_move = std::max(1, to_move); - - if ((insert_position <= (node->count() - to_move)) || - ((right->count() + to_move) < right->max_count())) { - node->rebalance_left_to_right(right, to_move); - - if (insert_position > node->count()) { - insert_position = insert_position - node->count() - 1; - node = right; - } - - assert(node->count() < node->max_count()); - return; - } - } - } - - // Rebalancing failed, make sure there is room on the parent node for a new - // value. - if (parent->count() == parent->max_count()) { - iterator parent_iter(node->parent(), node->position()); - rebalance_or_split(&parent_iter); - } - } else { - // Rebalancing not possible because this is the root node. - if (root()->leaf()) { - // The root node is currently a leaf node: create a new root node and set - // the current root node as the child of the new root. - parent = new_internal_root_node(); - parent->set_child(0, root()); - *mutable_root() = parent; - assert(*mutable_rightmost() == parent->child(0)); - } else { - // The root node is an internal node. We do not want to create a new root - // node because the root node is special and holds the size of the tree - // and a pointer to the rightmost node. So we create a new internal node - // and move all of the items on the current root into the new node. - parent = new_internal_node(parent); - parent->set_child(0, parent); - parent->swap(root()); - node = parent; - } - } - - // Split the node. - node_type *split_node; - if (node->leaf()) { - split_node = new_leaf_node(parent); - node->split(split_node, insert_position); - if (rightmost() == node) { - *mutable_rightmost() = split_node; - } - } else { - split_node = new_internal_node(parent); - node->split(split_node, insert_position); - } - - if (insert_position > node->count()) { - insert_position = insert_position - node->count() - 1; - node = split_node; - } -} - -template <typename P> -void btree<P>::merge_nodes(node_type *left, node_type *right) { - left->merge(right); - if (right->leaf()) { - if (rightmost() == right) { - *mutable_rightmost() = left; - } - delete_leaf_node(right); - } else { - delete_internal_node(right); - } -} - -template <typename P> -bool btree<P>::try_merge_or_rebalance(iterator *iter) { - node_type *parent = iter->node->parent(); - if (iter->node->position() > 0) { - // Try merging with our left sibling. - node_type *left = parent->child(iter->node->position() - 1); - if ((1 + left->count() + iter->node->count()) <= left->max_count()) { - iter->position += 1 + left->count(); - merge_nodes(left, iter->node); - iter->node = left; - return true; - } - } - if (iter->node->position() < parent->count()) { - // Try merging with our right sibling. - node_type *right = parent->child(iter->node->position() + 1); - if ((1 + iter->node->count() + right->count()) <= right->max_count()) { - merge_nodes(iter->node, right); - return true; - } - // Try rebalancing with our right sibling. We don't perform rebalancing if - // we deleted the first element from iter->node and the node is not - // empty. This is a small optimization for the common pattern of deleting - // from the front of the tree. - if ((right->count() > kMinNodeValues) && - ((iter->node->count() == 0) || - (iter->position > 0))) { - int to_move = (right->count() - iter->node->count()) / 2; - to_move = std::min(to_move, right->count() - 1); - iter->node->rebalance_right_to_left(right, to_move); - return false; - } - } - if (iter->node->position() > 0) { - // Try rebalancing with our left sibling. We don't perform rebalancing if - // we deleted the last element from iter->node and the node is not - // empty. This is a small optimization for the common pattern of deleting - // from the back of the tree. - node_type *left = parent->child(iter->node->position() - 1); - if ((left->count() > kMinNodeValues) && - ((iter->node->count() == 0) || - (iter->position < iter->node->count()))) { - int to_move = (left->count() - iter->node->count()) / 2; - to_move = std::min(to_move, left->count() - 1); - left->rebalance_left_to_right(iter->node, to_move); - iter->position += to_move; - return false; - } - } - return false; -} - -template <typename P> -void btree<P>::try_shrink() { - if (root()->count() > 0) { - return; - } - // Deleted the last item on the root node, shrink the height of the tree. - if (root()->leaf()) { - assert(size() == 0); - delete_leaf_node(root()); - *mutable_root() = NULL; - } else { - node_type *child = root()->child(0); - if (child->leaf()) { - // The child is a leaf node so simply make it the root node in the tree. - child->make_root(); - delete_internal_root_node(); - *mutable_root() = child; - } else { - // The child is an internal node. We want to keep the existing root node - // so we move all of the values from the child node into the existing - // (empty) root node. - child->swap(root()); - delete_internal_node(child); - } - } -} - -template <typename P> template <typename IterType> -inline IterType btree<P>::internal_last(IterType iter) { - while (iter.node && iter.position == iter.node->count()) { - iter.position = iter.node->position(); - iter.node = iter.node->parent(); - if (iter.node->leaf()) { - iter.node = NULL; - } - } - return iter; -} - -template <typename P> -inline typename btree<P>::iterator -btree<P>::internal_insert(iterator iter, const value_type &v) { - if (!iter.node->leaf()) { - // We can't insert on an internal node. Instead, we'll insert after the - // previous value which is guaranteed to be on a leaf node. - --iter; - ++iter.position; - } - if (iter.node->count() == iter.node->max_count()) { - // Make room in the leaf for the new item. - if (iter.node->max_count() < kNodeValues) { - // Insertion into the root where the root is smaller that the full node - // size. Simply grow the size of the root node. - assert(iter.node == root()); - iter.node = new_leaf_root_node( - std::min<int>(kNodeValues, 2 * iter.node->max_count())); - iter.node->swap(root()); - delete_leaf_node(root()); - *mutable_root() = iter.node; - } else { - rebalance_or_split(&iter); - ++*mutable_size(); - } - } else if (!root()->leaf()) { - ++*mutable_size(); - } - iter.node->insert_value(iter.position, v); - return iter; -} - -template <typename P> template <typename IterType> -inline std::pair<IterType, int> btree<P>::internal_locate( - const key_type &key, IterType iter) const { - return internal_locate_type::dispatch(key, *this, iter); -} - -template <typename P> template <typename IterType> -inline std::pair<IterType, int> btree<P>::internal_locate_plain_compare( - const key_type &key, IterType iter) const { - for (;;) { - iter.position = iter.node->lower_bound(key, key_comp()); - if (iter.node->leaf()) { - break; - } - iter.node = iter.node->child(iter.position); - } - return std::make_pair(iter, 0); -} - -template <typename P> template <typename IterType> -inline std::pair<IterType, int> btree<P>::internal_locate_compare_to( - const key_type &key, IterType iter) const { - for (;;) { - int res = iter.node->lower_bound(key, key_comp()); - iter.position = res & kMatchMask; - if (res & kExactMatch) { - return std::make_pair(iter, static_cast<int>(kExactMatch)); - } - if (iter.node->leaf()) { - break; - } - iter.node = iter.node->child(iter.position); - } - return std::make_pair(iter, -kExactMatch); -} - -template <typename P> template <typename IterType> -IterType btree<P>::internal_lower_bound( - const key_type &key, IterType iter) const { - if (iter.node) { - for (;;) { - iter.position = - iter.node->lower_bound(key, key_comp()) & kMatchMask; - if (iter.node->leaf()) { - break; - } - iter.node = iter.node->child(iter.position); - } - iter = internal_last(iter); - } - return iter; -} - -template <typename P> template <typename IterType> -IterType btree<P>::internal_upper_bound( - const key_type &key, IterType iter) const { - if (iter.node) { - for (;;) { - iter.position = iter.node->upper_bound(key, key_comp()); - if (iter.node->leaf()) { - break; - } - iter.node = iter.node->child(iter.position); - } - iter = internal_last(iter); - } - return iter; -} - -template <typename P> template <typename IterType> -IterType btree<P>::internal_find_unique( - const key_type &key, IterType iter) const { - if (iter.node) { - std::pair<IterType, int> res = internal_locate(key, iter); - if (res.second == kExactMatch) { - return res.first; - } - if (!res.second) { - iter = internal_last(res.first); - if (iter.node && !compare_keys(key, iter.key())) { - return iter; - } - } - } - return IterType(NULL, 0); -} - -template <typename P> template <typename IterType> -IterType btree<P>::internal_find_multi( - const key_type &key, IterType iter) const { - if (iter.node) { - iter = internal_lower_bound(key, iter); - if (iter.node) { - iter = internal_last(iter); - if (iter.node && !compare_keys(key, iter.key())) { - return iter; - } - } - } - return IterType(NULL, 0); -} - -template <typename P> -void btree<P>::internal_clear(node_type *node) { - if (!node->leaf()) { - for (int i = 0; i <= node->count(); ++i) { - internal_clear(node->child(i)); - } - if (node == root()) { - delete_internal_root_node(); - } else { - delete_internal_node(node); - } - } else { - delete_leaf_node(node); - } -} - -template <typename P> -void btree<P>::internal_dump( - std::ostream &os, const node_type *node, int level) const { - for (int i = 0; i < node->count(); ++i) { - if (!node->leaf()) { - internal_dump(os, node->child(i), level + 1); - } - for (int j = 0; j < level; ++j) { - os << " "; - } - os << node->key(i) << " [" << level << "]\n"; - } - if (!node->leaf()) { - internal_dump(os, node->child(node->count()), level + 1); - } -} - -template <typename P> -int btree<P>::internal_verify( - const node_type *node, const key_type *lo, const key_type *hi) const { - assert(node->count() > 0); - assert(node->count() <= node->max_count()); - if (lo) { - assert(!compare_keys(node->key(0), *lo)); - } - if (hi) { - assert(!compare_keys(*hi, node->key(node->count() - 1))); - } - for (int i = 1; i < node->count(); ++i) { - assert(!compare_keys(node->key(i), node->key(i - 1))); - } - int count = node->count(); - if (!node->leaf()) { - for (int i = 0; i <= node->count(); ++i) { - assert(node->child(i) != NULL); - assert(node->child(i)->parent() == node); - assert(node->child(i)->position() == i); - count += internal_verify( - node->child(i), - (i == 0) ? lo : &node->key(i - 1), - (i == node->count()) ? hi : &node->key(i)); - } - } - return count; -} - -} // namespace btree - -#endif // UTIL_BTREE_BTREE_H__ diff --git a/cpp-btree/btree_bench.cc b/cpp-btree/btree_bench.cc deleted file mode 100644 index 6eaed99..0000000 --- a/cpp-btree/btree_bench.cc +++ /dev/null @@ -1,593 +0,0 @@ -// Copyright 2013 Google Inc. All Rights Reserved. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -#include <stdint.h> -#include <stdlib.h> -#include <algorithm> -#include <functional> -#include <map> -#include <set> -#include <string> -#include <sys/time.h> -#include <type_traits> -#include <vector> - -#include "gflags/gflags.h" -#include "btree_map.h" -#include "btree_set.h" -#include "btree_test.h" - -DEFINE_int32(test_random_seed, 123456789, "Seed for srand()"); -DEFINE_int32(benchmark_max_iters, 10000000, "Maximum test iterations"); -DEFINE_int32(benchmark_min_iters, 100, "Minimum test iterations"); -DEFINE_int32(benchmark_target_seconds, 1, - "Attempt to benchmark for this many seconds"); - -using std::allocator; -using std::less; -using std::map; -using std::max; -using std::min; -using std::multimap; -using std::multiset; -using std::set; -using std::string; -using std::vector; - -namespace btree { -namespace { - -struct RandGen { - typedef ptrdiff_t result_type; - RandGen(result_type seed) { - srand(seed); - } - result_type operator()(result_type l) { - return rand() % l; - } -}; - -struct BenchmarkRun { - BenchmarkRun(const char *name, void (*func)(int)); - void Run(); - void Stop(); - void Start(); - void Reset(); - - BenchmarkRun *next_benchmark; - const char *benchmark_name; - void (*benchmark_func)(int); - int64_t accum_micros; - int64_t last_started; -}; - -BenchmarkRun *first_benchmark; -BenchmarkRun *current_benchmark; - -int64_t get_micros () { - timeval tv; - gettimeofday(&tv, NULL); - return tv.tv_sec * 1000000 + tv.tv_usec; -} - -BenchmarkRun::BenchmarkRun(const char *name, void (*func)(int)) - : next_benchmark(first_benchmark), - benchmark_name(name), - benchmark_func(func), - accum_micros(0), - last_started(0) { - first_benchmark = this; -} - -#define BTREE_BENCHMARK(name) \ - BTREE_BENCHMARK2(#name, name, __COUNTER__) -#define BTREE_BENCHMARK2(name, func, counter) \ - BTREE_BENCHMARK3(name, func, counter) -#define BTREE_BENCHMARK3(name, func, counter) \ - BenchmarkRun bench ## counter (name, func) - -void StopBenchmarkTiming() { - current_benchmark->Stop(); -} - -void StartBenchmarkTiming() { - current_benchmark->Start(); -} - -void RunBenchmarks() { - for (BenchmarkRun *bench = first_benchmark; bench; - bench = bench->next_benchmark) { - bench->Run(); - } -} - -void BenchmarkRun::Start() { - assert(!last_started); - last_started = get_micros(); -} - -void BenchmarkRun::Stop() { - if (last_started == 0) { - return; - } - accum_micros += get_micros() - last_started; - last_started = 0; -} - -void BenchmarkRun::Reset() { - last_started = 0; - accum_micros = 0; -} - -void BenchmarkRun::Run() { - assert(current_benchmark == NULL); - current_benchmark = this; - int iters = FLAGS_benchmark_min_iters; - for (;;) { - Reset(); - Start(); - benchmark_func(iters); - Stop(); - if (accum_micros > FLAGS_benchmark_target_seconds * 1000000 || - iters >= FLAGS_benchmark_max_iters) { - break; - } else if (accum_micros == 0) { - iters *= 100; - } else { - int64_t target_micros = FLAGS_benchmark_target_seconds * 1000000; - iters = target_micros * iters / accum_micros; - } - iters = min(iters, FLAGS_benchmark_max_iters); - } - std::cout << benchmark_name << "\t" - << accum_micros * 1000 / iters << "\t" - << iters; - current_benchmark = NULL; -} - -// Used to avoid compiler optimizations for these benchmarks. -template <typename T> -void sink(const T& t0) { - volatile T t = t0; -} - -// Benchmark insertion of values into a container. -template <typename T> -void BM_Insert(int n) { - typedef typename std::remove_const<typename T::value_type>::type V; - typename KeyOfValue<typename T::key_type, V>::type key_of_value; - - // Disable timing while we perform some initialization. - StopBenchmarkTiming(); - - T container; - vector<V> values = GenerateValues<V>(FLAGS_benchmark_values); - for (int i = 0; i < values.size(); i++) { - container.insert(values[i]); - } - - for (int i = 0; i < n; ) { - // Remove and re-insert 10% of the keys - int m = min(n - i, FLAGS_benchmark_values / 10); - - for (int j = i; j < i + m; j++) { - int x = j % FLAGS_benchmark_values; - container.erase(key_of_value(values[x])); - } - - StartBenchmarkTiming(); - - for (int j = i; j < i + m; j++) { - int x = j % FLAGS_benchmark_values; - container.insert(values[x]); - } - - StopBenchmarkTiming(); - - i += m; - } -} - -// Benchmark lookup of values in a container. -template <typename T> -void BM_Lookup(int n) { - typedef typename std::remove_const<typename T::value_type>::type V; - typename KeyOfValue<typename T::key_type, V>::type key_of_value; - - // Disable timing while we perform some initialization. - StopBenchmarkTiming(); - - T container; - vector<V> values = GenerateValues<V>(FLAGS_benchmark_values); - - for (int i = 0; i < values.size(); i++) { - container.insert(values[i]); - } - - V r = V(); - - StartBenchmarkTiming(); - - for (int i = 0; i < n; i++) { - int m = i % values.size(); - r = *container.find(key_of_value(values[m])); - } - - StopBenchmarkTiming(); - - sink(r); // Keep compiler from optimizing away r. -} - -// Benchmark lookup of values in a full container, meaning that values -// are inserted in-order to take advantage of biased insertion, which -// yields a full tree. -template <typename T> -void BM_FullLookup(int n) { - typedef typename std::remove_const<typename T::value_type>::type V; - typename KeyOfValue<typename T::key_type, V>::type key_of_value; - - // Disable timing while we perform some initialization. - StopBenchmarkTiming(); - - T container; - vector<V> values = GenerateValues<V>(FLAGS_benchmark_values); - vector<V> sorted(values); - sort(sorted.begin(), sorted.end()); - - for (int i = 0; i < sorted.size(); i++) { - container.insert(sorted[i]); - } - - V r = V(); - - StartBenchmarkTiming(); - - for (int i = 0; i < n; i++) { - int m = i % values.size(); - r = *container.find(key_of_value(values[m])); - } - - StopBenchmarkTiming(); - - sink(r); // Keep compiler from optimizing away r. -} - -// Benchmark deletion of values from a container. -template <typename T> -void BM_Delete(int n) { - typedef typename std::remove_const<typename T::value_type>::type V; - typename KeyOfValue<typename T::key_type, V>::type key_of_value; - - // Disable timing while we perform some initialization. - StopBenchmarkTiming(); - - T container; - vector<V> values = GenerateValues<V>(FLAGS_benchmark_values); - for (int i = 0; i < values.size(); i++) { - container.insert(values[i]); - } - - for (int i = 0; i < n; ) { - // Remove and re-insert 10% of the keys - int m = min(n - i, FLAGS_benchmark_values / 10); - - StartBenchmarkTiming(); - - for (int j = i; j < i + m; j++) { - int x = j % FLAGS_benchmark_values; - container.erase(key_of_value(values[x])); - } - - StopBenchmarkTiming(); - - for (int j = i; j < i + m; j++) { - int x = j % FLAGS_benchmark_values; - container.insert(values[x]); - } - - i += m; - } -} - -// Benchmark steady-state insert (into first half of range) and remove -// (from second second half of range), treating the container -// approximately like a queue with log-time access for all elements. -// This benchmark does not test the case where insertion and removal -// happen in the same region of the tree. This benchmark counts two -// value constructors. -template <typename T> -void BM_QueueAddRem(int n) { - typedef typename std::remove_const<typename T::value_type>::type V; - typename KeyOfValue<typename T::key_type, V>::type key_of_value; - - // Disable timing while we perform some initialization. - StopBenchmarkTiming(); - assert(FLAGS_benchmark_values % 2 == 0); - - T container; - - const int half = FLAGS_benchmark_values / 2; - vector<int> remove_keys(half); - vector<int> add_keys(half); - - for (int i = 0; i < half; i++) { - remove_keys[i] = i; - add_keys[i] = i; - } - - RandGen rand(FLAGS_test_random_seed); - - random_shuffle(remove_keys.begin(), remove_keys.end(), rand); - random_shuffle(add_keys.begin(), add_keys.end(), rand); - - Generator<V> g(FLAGS_benchmark_values + FLAGS_benchmark_max_iters); - - for (int i = 0; i < half; i++) { - container.insert(g(add_keys[i])); - container.insert(g(half + remove_keys[i])); - } - - // There are three parts each of size "half": - // 1 is being deleted from [offset - half, offset) - // 2 is standing [offset, offset + half) - // 3 is being inserted into [offset + half, offset + 2 * half) - int offset = 0; - - StartBenchmarkTiming(); - - for (int i = 0; i < n; i++) { - int idx = i % half; - - if (idx == 0) { - StopBenchmarkTiming(); - random_shuffle(remove_keys.begin(), remove_keys.end(), rand); - random_shuffle(add_keys.begin(), add_keys.end(), rand); - offset += half; - StartBenchmarkTiming(); - } - - int e = container.erase(key_of_value(g(offset - half + remove_keys[idx]))); - assert(e == 1); - container.insert(g(offset + half + add_keys[idx])); - } - - StopBenchmarkTiming(); -} - -// Mixed insertion and deletion in the same range using pre-constructed values. -template <typename T> -void BM_MixedAddRem(int n) { - typedef typename std::remove_const<typename T::value_type>::type V; - typename KeyOfValue<typename T::key_type, V>::type key_of_value; - - // Disable timing while we perform some initialization. - StopBenchmarkTiming(); - assert(FLAGS_benchmark_values % 2 == 0); - - T container; - RandGen rand(FLAGS_test_random_seed); - - vector<V> values = GenerateValues<V>(FLAGS_benchmark_values * 2); - - // Create two random shuffles - vector<int> remove_keys(FLAGS_benchmark_values); - vector<int> add_keys(FLAGS_benchmark_values); - - // Insert the first half of the values (already in random order) - for (int i = 0; i < FLAGS_benchmark_values; i++) { - container.insert(values[i]); - - // remove_keys and add_keys will be swapped before each round, - // therefore fill add_keys here w/ the keys being inserted, so - // they'll be the first to be removed. - remove_keys[i] = i + FLAGS_benchmark_values; - add_keys[i] = i; - } - - StartBenchmarkTiming(); - - for (int i = 0; i < n; i++) { - int idx = i % FLAGS_benchmark_values; - - if (idx == 0) { - StopBenchmarkTiming(); - remove_keys.swap(add_keys); - random_shuffle(remove_keys.begin(), remove_keys.end(), rand); - random_shuffle(add_keys.begin(), add_keys.end(), rand); - StartBenchmarkTiming(); - } - - int e = container.erase(key_of_value(values[remove_keys[idx]])); - assert(e == 1); - container.insert(values[add_keys[idx]]); - } - - StopBenchmarkTiming(); -} - -// Insertion at end, removal from the beginning. This benchmark -// counts two value constructors. -template <typename T> -void BM_Fifo(int n) { - typedef typename std::remove_const<typename T::value_type>::type V; - - // Disable timing while we perform some initialization. - StopBenchmarkTiming(); - - T container; - Generator<V> g(FLAGS_benchmark_values + FLAGS_benchmark_max_iters); - - for (int i = 0; i < FLAGS_benchmark_values; i++) { - container.insert(g(i)); - } - - StartBenchmarkTiming(); - - for (int i = 0; i < n; i++) { - container.erase(container.begin()); - container.insert(container.end(), g(i + FLAGS_benchmark_values)); - } - - StopBenchmarkTiming(); -} - -// Iteration (forward) through the tree -template <typename T> -void BM_FwdIter(int n) { - typedef typename std::remove_const<typename T::value_type>::type V; - - // Disable timing while we perform some initialization. - StopBenchmarkTiming(); - - T container; - vector<V> values = GenerateValues<V>(FLAGS_benchmark_values); - - for (int i = 0; i < FLAGS_benchmark_values; i++) { - container.insert(values[i]); - } - - typename T::iterator iter; - - V r = V(); - - StartBenchmarkTiming(); - - for (int i = 0; i < n; i++) { - int idx = i % FLAGS_benchmark_values; - - if (idx == 0) { - iter = container.begin(); - } - r = *iter; - ++iter; - } - - StopBenchmarkTiming(); - - sink(r); // Keep compiler from optimizing away r. -} - -typedef set<int32_t> stl_set_int32; -typedef set<int64_t> stl_set_int64; -typedef set<string> stl_set_string; - -typedef map<int32_t, intptr_t> stl_map_int32; -typedef map<int64_t, intptr_t> stl_map_int64; -typedef map<string, intptr_t> stl_map_string; - -typedef multiset<int32_t> stl_multiset_int32; -typedef multiset<int64_t> stl_multiset_int64; -typedef multiset<string> stl_multiset_string; - -typedef multimap<int32_t, intptr_t> stl_multimap_int32; -typedef multimap<int64_t, intptr_t> stl_multimap_int64; -typedef multimap<string, intptr_t> stl_multimap_string; - -#define MY_BENCHMARK_TYPES2(value, name, size) \ - typedef btree ## _set<value, less<value>, allocator<value>, size> \ - btree ## _ ## size ## _set_ ## name; \ - typedef btree ## _map<value, int, less<value>, allocator<value>, size> \ - btree ## _ ## size ## _map_ ## name; \ - typedef btree ## _multiset<value, less<value>, allocator<value>, size> \ - btree ## _ ## size ## _multiset_ ## name; \ - typedef btree ## _multimap<value, int, less<value>, allocator<value>, size> \ - btree ## _ ## size ## _multimap_ ## name - -#define MY_BENCHMARK_TYPES(value, name) \ - MY_BENCHMARK_TYPES2(value, name, 128); \ - MY_BENCHMARK_TYPES2(value, name, 160); \ - MY_BENCHMARK_TYPES2(value, name, 192); \ - MY_BENCHMARK_TYPES2(value, name, 224); \ - MY_BENCHMARK_TYPES2(value, name, 256); \ - MY_BENCHMARK_TYPES2(value, name, 288); \ - MY_BENCHMARK_TYPES2(value, name, 320); \ - MY_BENCHMARK_TYPES2(value, name, 352); \ - MY_BENCHMARK_TYPES2(value, name, 384); \ - MY_BENCHMARK_TYPES2(value, name, 416); \ - MY_BENCHMARK_TYPES2(value, name, 448); \ - MY_BENCHMARK_TYPES2(value, name, 480); \ - MY_BENCHMARK_TYPES2(value, name, 512); \ - MY_BENCHMARK_TYPES2(value, name, 1024); \ - MY_BENCHMARK_TYPES2(value, name, 1536); \ - MY_BENCHMARK_TYPES2(value, name, 2048) - -MY_BENCHMARK_TYPES(int32_t, int32); -MY_BENCHMARK_TYPES(int64_t, int64); -MY_BENCHMARK_TYPES(string, string); - -#define MY_BENCHMARK4(type, name, func) \ - void BM_ ## type ## _ ## name(int n) { BM_ ## func <type>(n); } \ - BTREE_BENCHMARK(BM_ ## type ## _ ## name) - -// Define NODESIZE_TESTING when running btree_perf.py. - -#ifdef NODESIZE_TESTING -#define MY_BENCHMARK3(tree, type, name, func) \ - MY_BENCHMARK4(tree ## _128_ ## type, name, func); \ - MY_BENCHMARK4(tree ## _160_ ## type, name, func); \ - MY_BENCHMARK4(tree ## _192_ ## type, name, func); \ - MY_BENCHMARK4(tree ## _224_ ## type, name, func); \ - MY_BENCHMARK4(tree ## _256_ ## type, name, func); \ - MY_BENCHMARK4(tree ## _288_ ## type, name, func); \ - MY_BENCHMARK4(tree ## _320_ ## type, name, func); \ - MY_BENCHMARK4(tree ## _352_ ## type, name, func); \ - MY_BENCHMARK4(tree ## _384_ ## type, name, func); \ - MY_BENCHMARK4(tree ## _416_ ## type, name, func); \ - MY_BENCHMARK4(tree ## _448_ ## type, name, func); \ - MY_BENCHMARK4(tree ## _480_ ## type, name, func); \ - MY_BENCHMARK4(tree ## _512_ ## type, name, func); \ - MY_BENCHMARK4(tree ## _1024_ ## type, name, func); \ - MY_BENCHMARK4(tree ## _1536_ ## type, name, func); \ - MY_BENCHMARK4(tree ## _2048_ ## type, name, func) -#else -#define MY_BENCHMARK3(tree, type, name, func) \ - MY_BENCHMARK4(tree ## _256_ ## type, name, func); \ - MY_BENCHMARK4(tree ## _2048_ ## type, name, func) -#endif - -#define MY_BENCHMARK2(type, name, func) \ - MY_BENCHMARK4(stl_ ## type, name, func); \ - MY_BENCHMARK3(btree, type, name, func) - -#define MY_BENCHMARK(type) \ - MY_BENCHMARK2(type, insert, Insert); \ - MY_BENCHMARK2(type, lookup, Lookup); \ - MY_BENCHMARK2(type, fulllookup, FullLookup); \ - MY_BENCHMARK2(type, delete, Delete); \ - MY_BENCHMARK2(type, queueaddrem, QueueAddRem); \ - MY_BENCHMARK2(type, mixedaddrem, MixedAddRem); \ - MY_BENCHMARK2(type, fifo, Fifo); \ - MY_BENCHMARK2(type, fwditer, FwdIter) - -MY_BENCHMARK(set_int32); -MY_BENCHMARK(map_int32); -MY_BENCHMARK(set_int64); -MY_BENCHMARK(map_int64); -MY_BENCHMARK(set_string); -MY_BENCHMARK(map_string); - -MY_BENCHMARK(multiset_int32); -MY_BENCHMARK(multimap_int32); -MY_BENCHMARK(multiset_int64); -MY_BENCHMARK(multimap_int64); -MY_BENCHMARK(multiset_string); -MY_BENCHMARK(multimap_string); - -} // namespace -} // namespace btree - -int main(int argc, char **argv) { - btree::RunBenchmarks(); - return 0; -} diff --git a/cpp-btree/btree_container.h b/cpp-btree/btree_container.h deleted file mode 100644 index fb617ab..0000000 --- a/cpp-btree/btree_container.h +++ /dev/null @@ -1,349 +0,0 @@ -// Copyright 2013 Google Inc. All Rights Reserved. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -#ifndef UTIL_BTREE_BTREE_CONTAINER_H__ -#define UTIL_BTREE_BTREE_CONTAINER_H__ - -#include <iosfwd> -#include <utility> - -#include "btree.h" - -namespace btree { - -// A common base class for btree_set, btree_map, btree_multiset and -// btree_multimap. -template <typename Tree> -class btree_container { - typedef btree_container<Tree> self_type; - - public: - typedef typename Tree::params_type params_type; - typedef typename Tree::key_type key_type; - typedef typename Tree::value_type value_type; - typedef typename Tree::key_compare key_compare; - typedef typename Tree::allocator_type allocator_type; - typedef typename Tree::pointer pointer; - typedef typename Tree::const_pointer const_pointer; - typedef typename Tree::reference reference; - typedef typename Tree::const_reference const_reference; - typedef typename Tree::size_type size_type; - typedef typename Tree::difference_type difference_type; - typedef typename Tree::iterator iterator; - typedef typename Tree::const_iterator const_iterator; - typedef typename Tree::reverse_iterator reverse_iterator; - typedef typename Tree::const_reverse_iterator const_reverse_iterator; - - public: - // Default constructor. - btree_container(const key_compare &comp, const allocator_type &alloc) - : tree_(comp, alloc) { - } - - // Copy constructor. - btree_container(const self_type &x) - : tree_(x.tree_) { - } - - // Iterator routines. - iterator begin() { return tree_.begin(); } - const_iterator begin() const { return tree_.begin(); } - iterator end() { return tree_.end(); } - const_iterator end() const { return tree_.end(); } - reverse_iterator rbegin() { return tree_.rbegin(); } - const_reverse_iterator rbegin() const { return tree_.rbegin(); } - reverse_iterator rend() { return tree_.rend(); } - const_reverse_iterator rend() const { return tree_.rend(); } - - // Lookup routines. - iterator lower_bound(const key_type &key) { - return tree_.lower_bound(key); - } - const_iterator lower_bound(const key_type &key) const { - return tree_.lower_bound(key); - } - iterator upper_bound(const key_type &key) { - return tree_.upper_bound(key); - } - const_iterator upper_bound(const key_type &key) const { - return tree_.upper_bound(key); - } - std::pair<iterator,iterator> equal_range(const key_type &key) { - return tree_.equal_range(key); - } - std::pair<const_iterator,const_iterator> equal_range(const key_type &key) const { - return tree_.equal_range(key); - } - - // Utility routines. - void clear() { - tree_.clear(); - } - void swap(self_type &x) { - tree_.swap(x.tree_); - } - void dump(std::ostream &os) const { - tree_.dump(os); - } - void verify() const { - tree_.verify(); - } - - // Size routines. - size_type size() const { return tree_.size(); } - size_type max_size() const { return tree_.max_size(); } - bool empty() const { return tree_.empty(); } - size_type height() const { return tree_.height(); } - size_type internal_nodes() const { return tree_.internal_nodes(); } - size_type leaf_nodes() const { return tree_.leaf_nodes(); } - size_type nodes() const { return tree_.nodes(); } - size_type bytes_used() const { return tree_.bytes_used(); } - static double average_bytes_per_value() { - return Tree::average_bytes_per_value(); - } - double fullness() const { return tree_.fullness(); } - double overhead() const { return tree_.overhead(); } - - bool operator==(const self_type& x) const { - if (size() != x.size()) { - return false; - } - for (const_iterator i = begin(), xi = x.begin(); i != end(); ++i, ++xi) { - if (*i != *xi) { - return false; - } - } - return true; - } - - bool operator!=(const self_type& other) const { - return !operator==(other); - } - - - protected: - Tree tree_; -}; - -template <typename T> -inline std::ostream& operator<<(std::ostream &os, const btree_container<T> &b) { - b.dump(os); - return os; -} - -// A common base class for btree_set and safe_btree_set. -template <typename Tree> -class btree_unique_container : public btree_container<Tree> { - typedef btree_unique_container<Tree> self_type; - typedef btree_container<Tree> super_type; - - public: - typedef typename Tree::key_type key_type; - typedef typename Tree::value_type value_type; - typedef typename Tree::size_type size_type; - typedef typename Tree::key_compare key_compare; - typedef typename Tree::allocator_type allocator_type; - typedef typename Tree::iterator iterator; - typedef typename Tree::const_iterator const_iterator; - - public: - // Default constructor. - btree_unique_container(const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(comp, alloc) { - } - - // Copy constructor. - btree_unique_container(const self_type &x) - : super_type(x) { - } - - // Range constructor. - template <class InputIterator> - btree_unique_container(InputIterator b, InputIterator e, - const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(comp, alloc) { - insert(b, e); - } - - // Lookup routines. - iterator find(const key_type &key) { - return this->tree_.find_unique(key); - } - const_iterator find(const key_type &key) const { - return this->tree_.find_unique(key); - } - size_type count(const key_type &key) const { - return this->tree_.count_unique(key); - } - - // Insertion routines. - std::pair<iterator,bool> insert(const value_type &x) { - return this->tree_.insert_unique(x); - } - iterator insert(iterator position, const value_type &x) { - return this->tree_.insert_unique(position, x); - } - template <typename InputIterator> - void insert(InputIterator b, InputIterator e) { - this->tree_.insert_unique(b, e); - } - - // Deletion routines. - int erase(const key_type &key) { - return this->tree_.erase_unique(key); - } - // Erase the specified iterator from the btree. The iterator must be valid - // (i.e. not equal to end()). Return an iterator pointing to the node after - // the one that was erased (or end() if none exists). - iterator erase(const iterator &iter) { - return this->tree_.erase(iter); - } - void erase(const iterator &first, const iterator &last) { - this->tree_.erase(first, last); - } -}; - -// A common base class for btree_map and safe_btree_map. -template <typename Tree> -class btree_map_container : public btree_unique_container<Tree> { - typedef btree_map_container<Tree> self_type; - typedef btree_unique_container<Tree> super_type; - - public: - typedef typename Tree::key_type key_type; - typedef typename Tree::data_type data_type; - typedef typename Tree::value_type value_type; - typedef typename Tree::mapped_type mapped_type; - typedef typename Tree::key_compare key_compare; - typedef typename Tree::allocator_type allocator_type; - - private: - // A pointer-like object which only generates its value when - // dereferenced. Used by operator[] to avoid constructing an empty data_type - // if the key already exists in the map. - struct generate_value { - generate_value(const key_type &k) - : key(k) { - } - value_type operator*() const { - return std::make_pair(key, data_type()); - } - const key_type &key; - }; - - public: - // Default constructor. - btree_map_container(const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(comp, alloc) { - } - - // Copy constructor. - btree_map_container(const self_type &x) - : super_type(x) { - } - - // Range constructor. - template <class InputIterator> - btree_map_container(InputIterator b, InputIterator e, - const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(b, e, comp, alloc) { - } - - // Insertion routines. - data_type& operator[](const key_type &key) { - return this->tree_.insert_unique(key, generate_value(key)).first->second; - } -}; - -// A common base class for btree_multiset and btree_multimap. -template <typename Tree> -class btree_multi_container : public btree_container<Tree> { - typedef btree_multi_container<Tree> self_type; - typedef btree_container<Tree> super_type; - - public: - typedef typename Tree::key_type key_type; - typedef typename Tree::value_type value_type; - typedef typename Tree::size_type size_type; - typedef typename Tree::key_compare key_compare; - typedef typename Tree::allocator_type allocator_type; - typedef typename Tree::iterator iterator; - typedef typename Tree::const_iterator const_iterator; - - public: - // Default constructor. - btree_multi_container(const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(comp, alloc) { - } - - // Copy constructor. - btree_multi_container(const self_type &x) - : super_type(x) { - } - - // Range constructor. - template <class InputIterator> - btree_multi_container(InputIterator b, InputIterator e, - const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(comp, alloc) { - insert(b, e); - } - - // Lookup routines. - iterator find(const key_type &key) { - return this->tree_.find_multi(key); - } - const_iterator find(const key_type &key) const { - return this->tree_.find_multi(key); - } - size_type count(const key_type &key) const { - return this->tree_.count_multi(key); - } - - // Insertion routines. - iterator insert(const value_type &x) { - return this->tree_.insert_multi(x); - } - iterator insert(iterator position, const value_type &x) { - return this->tree_.insert_multi(position, x); - } - template <typename InputIterator> - void insert(InputIterator b, InputIterator e) { - this->tree_.insert_multi(b, e); - } - - // Deletion routines. - int erase(const key_type &key) { - return this->tree_.erase_multi(key); - } - // Erase the specified iterator from the btree. The iterator must be valid - // (i.e. not equal to end()). Return an iterator pointing to the node after - // the one that was erased (or end() if none exists). - iterator erase(const iterator &iter) { - return this->tree_.erase(iter); - } - void erase(const iterator &first, const iterator &last) { - this->tree_.erase(first, last); - } -}; - -} // namespace btree - -#endif // UTIL_BTREE_BTREE_CONTAINER_H__ diff --git a/cpp-btree/btree_map.h b/cpp-btree/btree_map.h deleted file mode 100644 index b83489f..0000000 --- a/cpp-btree/btree_map.h +++ /dev/null @@ -1,130 +0,0 @@ -// Copyright 2013 Google Inc. All Rights Reserved. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. -// -// A btree_map<> implements the STL unique sorted associative container -// interface and the pair associative container interface (a.k.a map<>) using a -// btree. A btree_multimap<> implements the STL multiple sorted associative -// container interface and the pair associtive container interface (a.k.a -// multimap<>) using a btree. See btree.h for details of the btree -// implementation and caveats. - -#ifndef UTIL_BTREE_BTREE_MAP_H__ -#define UTIL_BTREE_BTREE_MAP_H__ - -#include <algorithm> -#include <functional> -#include <memory> -#include <string> -#include <utility> - -#include "btree.h" -#include "btree_container.h" - -namespace btree { - -// The btree_map class is needed mainly for its constructors. -template <typename Key, typename Value, - typename Compare = std::less<Key>, - typename Alloc = std::allocator<std::pair<const Key, Value> >, - int TargetNodeSize = 256> -class btree_map : public btree_map_container< - btree<btree_map_params<Key, Value, Compare, Alloc, TargetNodeSize> > > { - - typedef btree_map<Key, Value, Compare, Alloc, TargetNodeSize> self_type; - typedef btree_map_params< - Key, Value, Compare, Alloc, TargetNodeSize> params_type; - typedef btree<params_type> btree_type; - typedef btree_map_container<btree_type> super_type; - - public: - typedef typename btree_type::key_compare key_compare; - typedef typename btree_type::allocator_type allocator_type; - - public: - // Default constructor. - btree_map(const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(comp, alloc) { - } - - // Copy constructor. - btree_map(const self_type &x) - : super_type(x) { - } - - // Range constructor. - template <class InputIterator> - btree_map(InputIterator b, InputIterator e, - const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(b, e, comp, alloc) { - } -}; - -template <typename K, typename V, typename C, typename A, int N> -inline void swap(btree_map<K, V, C, A, N> &x, - btree_map<K, V, C, A, N> &y) { - x.swap(y); -} - -// The btree_multimap class is needed mainly for its constructors. -template <typename Key, typename Value, - typename Compare = std::less<Key>, - typename Alloc = std::allocator<std::pair<const Key, Value> >, - int TargetNodeSize = 256> -class btree_multimap : public btree_multi_container< - btree<btree_map_params<Key, Value, Compare, Alloc, TargetNodeSize> > > { - - typedef btree_multimap<Key, Value, Compare, Alloc, TargetNodeSize> self_type; - typedef btree_map_params< - Key, Value, Compare, Alloc, TargetNodeSize> params_type; - typedef btree<params_type> btree_type; - typedef btree_multi_container<btree_type> super_type; - - public: - typedef typename btree_type::key_compare key_compare; - typedef typename btree_type::allocator_type allocator_type; - typedef typename btree_type::data_type data_type; - typedef typename btree_type::mapped_type mapped_type; - - public: - // Default constructor. - btree_multimap(const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(comp, alloc) { - } - - // Copy constructor. - btree_multimap(const self_type &x) - : super_type(x) { - } - - // Range constructor. - template <class InputIterator> - btree_multimap(InputIterator b, InputIterator e, - const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(b, e, comp, alloc) { - } -}; - -template <typename K, typename V, typename C, typename A, int N> -inline void swap(btree_multimap<K, V, C, A, N> &x, - btree_multimap<K, V, C, A, N> &y) { - x.swap(y); -} - -} // namespace btree - -#endif // UTIL_BTREE_BTREE_MAP_H__ diff --git a/cpp-btree/btree_set.h b/cpp-btree/btree_set.h deleted file mode 100644 index f9b2e75..0000000 --- a/cpp-btree/btree_set.h +++ /dev/null @@ -1,121 +0,0 @@ -// Copyright 2013 Google Inc. All Rights Reserved. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. -// -// A btree_set<> implements the STL unique sorted associative container -// interface (a.k.a set<>) using a btree. A btree_multiset<> implements the STL -// multiple sorted associative container interface (a.k.a multiset<>) using a -// btree. See btree.h for details of the btree implementation and caveats. - -#ifndef UTIL_BTREE_BTREE_SET_H__ -#define UTIL_BTREE_BTREE_SET_H__ - -#include <functional> -#include <memory> -#include <string> - -#include "btree.h" -#include "btree_container.h" - -namespace btree { - -// The btree_set class is needed mainly for its constructors. -template <typename Key, - typename Compare = std::less<Key>, - typename Alloc = std::allocator<Key>, - int TargetNodeSize = 256> -class btree_set : public btree_unique_container< - btree<btree_set_params<Key, Compare, Alloc, TargetNodeSize> > > { - - typedef btree_set<Key, Compare, Alloc, TargetNodeSize> self_type; - typedef btree_set_params<Key, Compare, Alloc, TargetNodeSize> params_type; - typedef btree<params_type> btree_type; - typedef btree_unique_container<btree_type> super_type; - - public: - typedef typename btree_type::key_compare key_compare; - typedef typename btree_type::allocator_type allocator_type; - - public: - // Default constructor. - btree_set(const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(comp, alloc) { - } - - // Copy constructor. - btree_set(const self_type &x) - : super_type(x) { - } - - // Range constructor. - template <class InputIterator> - btree_set(InputIterator b, InputIterator e, - const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(b, e, comp, alloc) { - } -}; - -template <typename K, typename C, typename A, int N> -inline void swap(btree_set<K, C, A, N> &x, btree_set<K, C, A, N> &y) { - x.swap(y); -} - -// The btree_multiset class is needed mainly for its constructors. -template <typename Key, - typename Compare = std::less<Key>, - typename Alloc = std::allocator<Key>, - int TargetNodeSize = 256> -class btree_multiset : public btree_multi_container< - btree<btree_set_params<Key, Compare, Alloc, TargetNodeSize> > > { - - typedef btree_multiset<Key, Compare, Alloc, TargetNodeSize> self_type; - typedef btree_set_params<Key, Compare, Alloc, TargetNodeSize> params_type; - typedef btree<params_type> btree_type; - typedef btree_multi_container<btree_type> super_type; - - public: - typedef typename btree_type::key_compare key_compare; - typedef typename btree_type::allocator_type allocator_type; - - public: - // Default constructor. - btree_multiset(const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(comp, alloc) { - } - - // Copy constructor. - btree_multiset(const self_type &x) - : super_type(x) { - } - - // Range constructor. - template <class InputIterator> - btree_multiset(InputIterator b, InputIterator e, - const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(b, e, comp, alloc) { - } -}; - -template <typename K, typename C, typename A, int N> -inline void swap(btree_multiset<K, C, A, N> &x, - btree_multiset<K, C, A, N> &y) { - x.swap(y); -} - -} // namespace btree - -#endif // UTIL_BTREE_BTREE_SET_H__ diff --git a/cpp-btree/btree_test.cc b/cpp-btree/btree_test.cc deleted file mode 100644 index 6b1837d..0000000 --- a/cpp-btree/btree_test.cc +++ /dev/null @@ -1,270 +0,0 @@ -// Copyright 2013 Google Inc. All Rights Reserved. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -#include "gtest/gtest.h" -#include "btree_map.h" -#include "btree_set.h" -#include "btree_test.h" - -namespace btree { -namespace { - -template <typename K, int N> -void SetTest() { - typedef TestAllocator<K> TestAlloc; - ASSERT_EQ(sizeof(btree_set<K>), sizeof(void*)); - BtreeTest<btree_set<K, std::less<K>, std::allocator<K>, N>, std::set<K> >(); - BtreeAllocatorTest<btree_set<K, std::less<K>, TestAlloc, N> >(); -} - -template <typename K, int N> -void MapTest() { - typedef TestAllocator<K> TestAlloc; - ASSERT_EQ(sizeof(btree_map<K, K>), sizeof(void*)); - BtreeTest<btree_map<K, K, std::less<K>, std::allocator<K>, N>, std::map<K, K> >(); - BtreeAllocatorTest<btree_map<K, K, std::less<K>, TestAlloc, N> >(); - BtreeMapTest<btree_map<K, K, std::less<K>, std::allocator<K>, N> >(); -} - -TEST(Btree, set_int32_32) { SetTest<int32_t, 32>(); } -TEST(Btree, set_int32_64) { SetTest<int32_t, 64>(); } -TEST(Btree, set_int32_128) { SetTest<int32_t, 128>(); } -TEST(Btree, set_int32_256) { SetTest<int32_t, 256>(); } -TEST(Btree, set_int64_256) { SetTest<int64_t, 256>(); } -TEST(Btree, set_string_256) { SetTest<std::string, 256>(); } -TEST(Btree, set_pair_256) { SetTest<std::pair<int, int>, 256>(); } -TEST(Btree, map_int32_256) { MapTest<int32_t, 256>(); } -TEST(Btree, map_int64_256) { MapTest<int64_t, 256>(); } -TEST(Btree, map_string_256) { MapTest<std::string, 256>(); } -TEST(Btree, map_pair_256) { MapTest<std::pair<int, int>, 256>(); } - -// Large-node tests -TEST(Btree, map_int32_1024) { MapTest<int32_t, 1024>(); } -TEST(Btree, map_int32_1032) { MapTest<int32_t, 1032>(); } -TEST(Btree, map_int32_1040) { MapTest<int32_t, 1040>(); } -TEST(Btree, map_int32_1048) { MapTest<int32_t, 1048>(); } -TEST(Btree, map_int32_1056) { MapTest<int32_t, 1056>(); } - -TEST(Btree, map_int32_2048) { MapTest<int32_t, 2048>(); } -TEST(Btree, map_int32_4096) { MapTest<int32_t, 4096>(); } -TEST(Btree, set_int32_1024) { SetTest<int32_t, 1024>(); } -TEST(Btree, set_int32_2048) { SetTest<int32_t, 2048>(); } -TEST(Btree, set_int32_4096) { SetTest<int32_t, 4096>(); } -TEST(Btree, map_string_1024) { MapTest<std::string, 1024>(); } -TEST(Btree, map_string_2048) { MapTest<std::string, 2048>(); } -TEST(Btree, map_string_4096) { MapTest<std::string, 4096>(); } -TEST(Btree, set_string_1024) { SetTest<std::string, 1024>(); } -TEST(Btree, set_string_2048) { SetTest<std::string, 2048>(); } -TEST(Btree, set_string_4096) { SetTest<std::string, 4096>(); } - -template <typename K, int N> -void MultiSetTest() { - typedef TestAllocator<K> TestAlloc; - ASSERT_EQ(sizeof(btree_multiset<K>), sizeof(void*)); - BtreeMultiTest<btree_multiset<K, std::less<K>, std::allocator<K>, N>, - std::multiset<K> >(); - BtreeAllocatorTest<btree_multiset<K, std::less<K>, TestAlloc, N> >(); -} - -template <typename K, int N> -void MultiMapTest() { - typedef TestAllocator<K> TestAlloc; - ASSERT_EQ(sizeof(btree_multimap<K, K>), sizeof(void*)); - BtreeMultiTest<btree_multimap<K, K, std::less<K>, std::allocator<K>, N>, - std::multimap<K, K> >(); - BtreeMultiMapTest<btree_multimap<K, K, std::less<K>, std::allocator<K>, N> >(); - BtreeAllocatorTest<btree_multimap<K, K, std::less<K>, TestAlloc, N> >(); -} - -TEST(Btree, multiset_int32_256) { MultiSetTest<int32_t, 256>(); } -TEST(Btree, multiset_int64_256) { MultiSetTest<int64_t, 256>(); } -TEST(Btree, multiset_string_256) { MultiSetTest<std::string, 256>(); } -TEST(Btree, multiset_pair_256) { MultiSetTest<std::pair<int, int>, 256>(); } -TEST(Btree, multimap_int32_256) { MultiMapTest<int32_t, 256>(); } -TEST(Btree, multimap_int64_256) { MultiMapTest<int64_t, 256>(); } -TEST(Btree, multimap_string_256) { MultiMapTest<std::string, 256>(); } -TEST(Btree, multimap_pair_256) { MultiMapTest<std::pair<int, int>, 256>(); } - -// Large-node tests -TEST(Btree, multimap_int32_1024) { MultiMapTest<int32_t, 1024>(); } -TEST(Btree, multimap_int32_2048) { MultiMapTest<int32_t, 2048>(); } -TEST(Btree, multimap_int32_4096) { MultiMapTest<int32_t, 4096>(); } -TEST(Btree, multiset_int32_1024) { MultiSetTest<int32_t, 1024>(); } -TEST(Btree, multiset_int32_2048) { MultiSetTest<int32_t, 2048>(); } -TEST(Btree, multiset_int32_4096) { MultiSetTest<int32_t, 4096>(); } -TEST(Btree, multimap_string_1024) { MultiMapTest<std::string, 1024>(); } -TEST(Btree, multimap_string_2048) { MultiMapTest<std::string, 2048>(); } -TEST(Btree, multimap_string_4096) { MultiMapTest<std::string, 4096>(); } -TEST(Btree, multiset_string_1024) { MultiSetTest<std::string, 1024>(); } -TEST(Btree, multiset_string_2048) { MultiSetTest<std::string, 2048>(); } -TEST(Btree, multiset_string_4096) { MultiSetTest<std::string, 4096>(); } - -// Verify that swapping btrees swaps the key comparision functors. -struct SubstringLess { - SubstringLess() : n(2) {} - SubstringLess(size_t length) - : n(length) { - } - bool operator()(const std::string &a, const std::string &b) const { - std::string as(a.data(), std::min(n, a.size())); - std::string bs(b.data(), std::min(n, b.size())); - return as < bs; - } - size_t n; -}; - -TEST(Btree, SwapKeyCompare) { - typedef btree_set<std::string, SubstringLess> SubstringSet; - SubstringSet s1(SubstringLess(1), SubstringSet::allocator_type()); - SubstringSet s2(SubstringLess(2), SubstringSet::allocator_type()); - - ASSERT_TRUE(s1.insert("a").second); - ASSERT_FALSE(s1.insert("aa").second); - - ASSERT_TRUE(s2.insert("a").second); - ASSERT_TRUE(s2.insert("aa").second); - ASSERT_FALSE(s2.insert("aaa").second); - - swap(s1, s2); - - ASSERT_TRUE(s1.insert("b").second); - ASSERT_TRUE(s1.insert("bb").second); - ASSERT_FALSE(s1.insert("bbb").second); - - ASSERT_TRUE(s2.insert("b").second); - ASSERT_FALSE(s2.insert("bb").second); -} - -TEST(Btree, UpperBoundRegression) { - // Regress a bug where upper_bound would default-construct a new key_compare - // instead of copying the existing one. - typedef btree_set<std::string, SubstringLess> SubstringSet; - SubstringSet my_set(SubstringLess(3)); - my_set.insert("aab"); - my_set.insert("abb"); - // We call upper_bound("aaa"). If this correctly uses the length 3 - // comparator, aaa < aab < abb, so we should get aab as the result. - // If it instead uses the default-constructed length 2 comparator, - // aa == aa < ab, so we'll get abb as our result. - SubstringSet::iterator it = my_set.upper_bound("aaa"); - ASSERT_TRUE(it != my_set.end()); - EXPECT_EQ("aab", *it); -} - - -TEST(Btree, IteratorIncrementBy) { - // Test that increment_by returns the same position as increment. - const int kSetSize = 2341; - btree_set<int32_t> my_set; - for (int i = 0; i < kSetSize; ++i) { - my_set.insert(i); - } - - { - // Simple increment vs. increment by. - btree_set<int32_t>::iterator a = my_set.begin(); - btree_set<int32_t>::iterator b = my_set.begin(); - a.increment(); - b.increment_by(1); - EXPECT_EQ(*a, *b); - } - - btree_set<int32_t>::iterator a = my_set.begin(); - for (int i = 1; i < kSetSize; ++i) { - ++a; - // increment_by - btree_set<int32_t>::iterator b = my_set.begin(); - b.increment_by(i); - EXPECT_EQ(*a, *b) << ": i=" << i; - } -} - -TEST(Btree, Comparison) { - const int kSetSize = 1201; - btree_set<int64_t> my_set; - for (int i = 0; i < kSetSize; ++i) { - my_set.insert(i); - } - btree_set<int64_t> my_set_copy(my_set); - EXPECT_TRUE(my_set_copy == my_set); - EXPECT_TRUE(my_set == my_set_copy); - EXPECT_FALSE(my_set_copy != my_set); - EXPECT_FALSE(my_set != my_set_copy); - - my_set.insert(kSetSize); - EXPECT_FALSE(my_set_copy == my_set); - EXPECT_FALSE(my_set == my_set_copy); - EXPECT_TRUE(my_set_copy != my_set); - EXPECT_TRUE(my_set != my_set_copy); - - my_set.erase(kSetSize - 1); - EXPECT_FALSE(my_set_copy == my_set); - EXPECT_FALSE(my_set == my_set_copy); - EXPECT_TRUE(my_set_copy != my_set); - EXPECT_TRUE(my_set != my_set_copy); - - btree_map<std::string, int64_t> my_map; - for (int i = 0; i < kSetSize; ++i) { - my_map[std::string(i, 'a')] = i; - } - btree_map<std::string, int64_t> my_map_copy(my_map); - EXPECT_TRUE(my_map_copy == my_map); - EXPECT_TRUE(my_map == my_map_copy); - EXPECT_FALSE(my_map_copy != my_map); - EXPECT_FALSE(my_map != my_map_copy); - - ++my_map_copy[std::string(7, 'a')]; - EXPECT_FALSE(my_map_copy == my_map); - EXPECT_FALSE(my_map == my_map_copy); - EXPECT_TRUE(my_map_copy != my_map); - EXPECT_TRUE(my_map != my_map_copy); - - my_map_copy = my_map; - my_map["hello"] = kSetSize; - EXPECT_FALSE(my_map_copy == my_map); - EXPECT_FALSE(my_map == my_map_copy); - EXPECT_TRUE(my_map_copy != my_map); - EXPECT_TRUE(my_map != my_map_copy); - - my_map.erase(std::string(kSetSize - 1, 'a')); - EXPECT_FALSE(my_map_copy == my_map); - EXPECT_FALSE(my_map == my_map_copy); - EXPECT_TRUE(my_map_copy != my_map); - EXPECT_TRUE(my_map != my_map_copy); -} - -TEST(Btree, RangeCtorSanity) { - typedef btree_set<int, std::less<int>, std::allocator<int>, 256> test_set; - typedef btree_map<int, int, std::less<int>, std::allocator<int>, 256> - test_map; - typedef btree_multiset<int, std::less<int>, std::allocator<int>, 256> - test_mset; - typedef btree_multimap<int, int, std::less<int>, std::allocator<int>, 256> - test_mmap; - std::vector<int> ivec; - ivec.push_back(1); - std::map<int, int> imap; - imap.insert(std::make_pair(1, 2)); - test_mset tmset(ivec.begin(), ivec.end()); - test_mmap tmmap(imap.begin(), imap.end()); - test_set tset(ivec.begin(), ivec.end()); - test_map tmap(imap.begin(), imap.end()); - EXPECT_EQ(1, tmset.size()); - EXPECT_EQ(1, tmmap.size()); - EXPECT_EQ(1, tset.size()); - EXPECT_EQ(1, tmap.size()); -} - -} // namespace -} // namespace btree diff --git a/cpp-btree/btree_test.h b/cpp-btree/btree_test.h deleted file mode 100644 index 413dc3c..0000000 --- a/cpp-btree/btree_test.h +++ /dev/null @@ -1,940 +0,0 @@ -// Copyright 2013 Google Inc. All Rights Reserved. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -#ifndef UTIL_BTREE_BTREE_TEST_H__ -#define UTIL_BTREE_BTREE_TEST_H__ - -#include <stdio.h> -#include <algorithm> -#include <functional> -#include <type_traits> -#include <iosfwd> -#include <map> -#include <set> -#include <sstream> -#include <string> -#include <utility> -#include <vector> - -#include "gtest/gtest.h" -#include "gflags/gflags.h" -#include "btree_container.h" - -DECLARE_int32(test_values); -DECLARE_int32(benchmark_values); - -namespace std { - -// Provide operator<< support for std::pair<T, U>. -template <typename T, typename U> -ostream& operator<<(ostream &os, const std::pair<T, U> &p) { - os << "(" << p.first << "," << p.second << ")"; - return os; -} - -// Provide pair equality testing that works as long as x.first is comparable to -// y.first and x.second is comparable to y.second. Needed in the test for -// comparing std::pair<T, U> to std::pair<const T, U>. -template <typename T, typename U, typename V, typename W> -bool operator==(const std::pair<T, U> &x, const std::pair<V, W> &y) { - return x.first == y.first && x.second == y.second; -} - -// Partial specialization of remove_const that propagates the removal through -// std::pair. -template <typename T, typename U> -struct remove_const<pair<T, U> > { - typedef pair<typename remove_const<T>::type, - typename remove_const<U>::type> type; -}; - -} // namespace std - -namespace btree { - -// Select the first member of a pair. -template <class _Pair> -struct select1st : public std::unary_function<_Pair, typename _Pair::first_type> { - const typename _Pair::first_type& operator()(const _Pair& __x) const { - return __x.first; - } -}; - -// Utility class to provide an accessor for a key given a value. The default -// behavior is to treat the value as a pair and return the first element. -template <typename K, typename V> -struct KeyOfValue { - typedef select1st<V> type; -}; - -template <typename T> -struct identity { - inline const T& operator()(const T& t) const { return t; } -}; - -// Partial specialization of KeyOfValue class for when the key and value are -// the same type such as in set<> and btree_set<>. -template <typename K> -struct KeyOfValue<K, K> { - typedef identity<K> type; -}; - -// Counts the number of occurances of "c" in a buffer. -inline ptrdiff_t strcount(const char* buf_begin, const char* buf_end, char c) { - if (buf_begin == NULL) - return 0; - if (buf_end <= buf_begin) - return 0; - ptrdiff_t num = 0; - for (const char* bp = buf_begin; bp != buf_end; bp++) { - if (*bp == c) - num++; - } - return num; -} - -// for when the string is not null-terminated. -inline ptrdiff_t strcount(const char* buf, size_t len, char c) { - return strcount(buf, buf + len, c); -} - -inline ptrdiff_t strcount(const std::string& buf, char c) { - return strcount(buf.c_str(), buf.size(), c); -} - -// The base class for a sorted associative container checker. TreeType is the -// container type to check and CheckerType is the container type to check -// against. TreeType is expected to be btree_{set,map,multiset,multimap} and -// CheckerType is expected to be {set,map,multiset,multimap}. -template <typename TreeType, typename CheckerType> -class base_checker { - typedef base_checker<TreeType, CheckerType> self_type; - - public: - typedef typename TreeType::key_type key_type; - typedef typename TreeType::value_type value_type; - typedef typename TreeType::key_compare key_compare; - typedef typename TreeType::pointer pointer; - typedef typename TreeType::const_pointer const_pointer; - typedef typename TreeType::reference reference; - typedef typename TreeType::const_reference const_reference; - typedef typename TreeType::size_type size_type; - typedef typename TreeType::difference_type difference_type; - typedef typename TreeType::iterator iterator; - typedef typename TreeType::const_iterator const_iterator; - typedef typename TreeType::reverse_iterator reverse_iterator; - typedef typename TreeType::const_reverse_iterator const_reverse_iterator; - - public: - // Default constructor. - base_checker() - : const_tree_(tree_) { - } - // Copy constructor. - base_checker(const self_type &x) - : tree_(x.tree_), - const_tree_(tree_), - checker_(x.checker_) { - } - // Range constructor. - template <typename InputIterator> - base_checker(InputIterator b, InputIterator e) - : tree_(b, e), - const_tree_(tree_), - checker_(b, e) { - } - - // Iterator routines. - iterator begin() { return tree_.begin(); } - const_iterator begin() const { return tree_.begin(); } - iterator end() { return tree_.end(); } - const_iterator end() const { return tree_.end(); } - reverse_iterator rbegin() { return tree_.rbegin(); } - const_reverse_iterator rbegin() const { return tree_.rbegin(); } - reverse_iterator rend() { return tree_.rend(); } - const_reverse_iterator rend() const { return tree_.rend(); } - - // Helper routines. - template <typename IterType, typename CheckerIterType> - IterType iter_check( - IterType tree_iter, CheckerIterType checker_iter) const { - if (tree_iter == tree_.end()) { - EXPECT_EQ(checker_iter, checker_.end()); - } else { - EXPECT_EQ(*tree_iter, *checker_iter); - } - return tree_iter; - } - template <typename IterType, typename CheckerIterType> - IterType riter_check( - IterType tree_iter, CheckerIterType checker_iter) const { - if (tree_iter == tree_.rend()) { - EXPECT_EQ(checker_iter, checker_.rend()); - } else { - EXPECT_EQ(*tree_iter, *checker_iter); - } - return tree_iter; - } - void value_check(const value_type &x) { - typename KeyOfValue<typename TreeType::key_type, - typename TreeType::value_type>::type key_of_value; - const key_type &key = key_of_value(x); - EXPECT_EQ(*find(key), x); - lower_bound(key); - upper_bound(key); - equal_range(key); - count(key); - } - void erase_check(const key_type &key) { - EXPECT_TRUE(tree_.find(key) == const_tree_.end()); - EXPECT_TRUE(const_tree_.find(key) == tree_.end()); - EXPECT_TRUE(tree_.equal_range(key).first == - const_tree_.equal_range(key).second); - } - - // Lookup routines. - iterator lower_bound(const key_type &key) { - return iter_check(tree_.lower_bound(key), checker_.lower_bound(key)); - } - const_iterator lower_bound(const key_type &key) const { - return iter_check(tree_.lower_bound(key), checker_.lower_bound(key)); - } - iterator upper_bound(const key_type &key) { - return iter_check(tree_.upper_bound(key), checker_.upper_bound(key)); - } - const_iterator upper_bound(const key_type &key) const { - return iter_check(tree_.upper_bound(key), checker_.upper_bound(key)); - } - std::pair<iterator,iterator> equal_range(const key_type &key) { - std::pair<typename CheckerType::iterator, - typename CheckerType::iterator> checker_res = - checker_.equal_range(key); - std::pair<iterator, iterator> tree_res = tree_.equal_range(key); - iter_check(tree_res.first, checker_res.first); - iter_check(tree_res.second, checker_res.second); - return tree_res; - } - std::pair<const_iterator,const_iterator> equal_range(const key_type &key) const { - std::pair<typename CheckerType::const_iterator, - typename CheckerType::const_iterator> checker_res = - checker_.equal_range(key); - std::pair<const_iterator, const_iterator> tree_res = tree_.equal_range(key); - iter_check(tree_res.first, checker_res.first); - iter_check(tree_res.second, checker_res.second); - return tree_res; - } - iterator find(const key_type &key) { - return iter_check(tree_.find(key), checker_.find(key)); - } - const_iterator find(const key_type &key) const { - return iter_check(tree_.find(key), checker_.find(key)); - } - size_type count(const key_type &key) const { - size_type res = checker_.count(key); - EXPECT_EQ(res, tree_.count(key)); - return res; - } - - // Assignment operator. - self_type& operator=(const self_type &x) { - tree_ = x.tree_; - checker_ = x.checker_; - return *this; - } - - // Deletion routines. - int erase(const key_type &key) { - int size = tree_.size(); - int res = checker_.erase(key); - EXPECT_EQ(res, tree_.count(key)); - EXPECT_EQ(res, tree_.erase(key)); - EXPECT_EQ(tree_.count(key), 0); - EXPECT_EQ(tree_.size(), size - res); - erase_check(key); - return res; - } - iterator erase(iterator iter) { - key_type key = iter.key(); - int size = tree_.size(); - int count = tree_.count(key); - typename CheckerType::iterator checker_iter = checker_.find(key); - for (iterator tmp(tree_.find(key)); tmp != iter; ++tmp) { - ++checker_iter; - } - typename CheckerType::iterator checker_next = checker_iter; - ++checker_next; - checker_.erase(checker_iter); - iter = tree_.erase(iter); - EXPECT_EQ(tree_.size(), checker_.size()); - EXPECT_EQ(tree_.size(), size - 1); - EXPECT_EQ(tree_.count(key), count - 1); - if (count == 1) { - erase_check(key); - } - return iter_check(iter, checker_next); - } - - void erase(iterator begin, iterator end) { - int size = tree_.size(); - int count = distance(begin, end); - typename CheckerType::iterator checker_begin = checker_.find(begin.key()); - for (iterator tmp(tree_.find(begin.key())); tmp != begin; ++tmp) { - ++checker_begin; - } - typename CheckerType::iterator checker_end = - end == tree_.end() ? checker_.end() : checker_.find(end.key()); - if (end != tree_.end()) { - for (iterator tmp(tree_.find(end.key())); tmp != end; ++tmp) { - ++checker_end; - } - } - checker_.erase(checker_begin, checker_end); - tree_.erase(begin, end); - EXPECT_EQ(tree_.size(), checker_.size()); - EXPECT_EQ(tree_.size(), size - count); - } - - // Utility routines. - void clear() { - tree_.clear(); - checker_.clear(); - } - void swap(self_type &x) { - tree_.swap(x.tree_); - checker_.swap(x.checker_); - } - - void verify() const { - tree_.verify(); - EXPECT_EQ(tree_.size(), checker_.size()); - - // Move through the forward iterators using increment. - typename CheckerType::const_iterator - checker_iter(checker_.begin()); - const_iterator tree_iter(tree_.begin()); - for (; tree_iter != tree_.end(); - ++tree_iter, ++checker_iter) { - EXPECT_EQ(*tree_iter, *checker_iter); - } - - // Move through the forward iterators using decrement. - for (int n = tree_.size() - 1; n >= 0; --n) { - iter_check(tree_iter, checker_iter); - --tree_iter; - --checker_iter; - } - EXPECT_TRUE(tree_iter == tree_.begin()); - EXPECT_TRUE(checker_iter == checker_.begin()); - - // Move through the reverse iterators using increment. - typename CheckerType::const_reverse_iterator - checker_riter(checker_.rbegin()); - const_reverse_iterator tree_riter(tree_.rbegin()); - for (; tree_riter != tree_.rend(); - ++tree_riter, ++checker_riter) { - EXPECT_EQ(*tree_riter, *checker_riter); - } - - // Move through the reverse iterators using decrement. - for (int n = tree_.size() - 1; n >= 0; --n) { - riter_check(tree_riter, checker_riter); - --tree_riter; - --checker_riter; - } - EXPECT_EQ(tree_riter, tree_.rbegin()); - EXPECT_EQ(checker_riter, checker_.rbegin()); - } - - // Access to the underlying btree. - const TreeType& tree() const { return tree_; } - - // Size routines. - size_type size() const { - EXPECT_EQ(tree_.size(), checker_.size()); - return tree_.size(); - } - size_type max_size() const { return tree_.max_size(); } - bool empty() const { - EXPECT_EQ(tree_.empty(), checker_.empty()); - return tree_.empty(); - } - size_type height() const { return tree_.height(); } - size_type internal_nodes() const { return tree_.internal_nodes(); } - size_type leaf_nodes() const { return tree_.leaf_nodes(); } - size_type nodes() const { return tree_.nodes(); } - size_type bytes_used() const { return tree_.bytes_used(); } - double fullness() const { return tree_.fullness(); } - double overhead() const { return tree_.overhead(); } - - protected: - TreeType tree_; - const TreeType &const_tree_; - CheckerType checker_; -}; - -// A checker for unique sorted associative containers. TreeType is expected to -// be btree_{set,map} and CheckerType is expected to be {set,map}. -template <typename TreeType, typename CheckerType> -class unique_checker : public base_checker<TreeType, CheckerType> { - typedef base_checker<TreeType, CheckerType> super_type; - typedef unique_checker<TreeType, CheckerType> self_type; - - public: - typedef typename super_type::iterator iterator; - typedef typename super_type::value_type value_type; - - public: - // Default constructor. - unique_checker() - : super_type() { - } - // Copy constructor. - unique_checker(const self_type &x) - : super_type(x) { - } - // Range constructor. - template <class InputIterator> - unique_checker(InputIterator b, InputIterator e) - : super_type(b, e) { - } - - // Insertion routines. - std::pair<iterator,bool> insert(const value_type &x) { - int size = this->tree_.size(); - std::pair<typename CheckerType::iterator,bool> checker_res = - this->checker_.insert(x); - std::pair<iterator,bool> tree_res = this->tree_.insert(x); - EXPECT_EQ(*tree_res.first, *checker_res.first); - EXPECT_EQ(tree_res.second, checker_res.second); - EXPECT_EQ(this->tree_.size(), this->checker_.size()); - EXPECT_EQ(this->tree_.size(), size + tree_res.second); - return tree_res; - } - iterator insert(iterator position, const value_type &x) { - int size = this->tree_.size(); - std::pair<typename CheckerType::iterator,bool> checker_res = - this->checker_.insert(x); - iterator tree_res = this->tree_.insert(position, x); - EXPECT_EQ(*tree_res, *checker_res.first); - EXPECT_EQ(this->tree_.size(), this->checker_.size()); - EXPECT_EQ(this->tree_.size(), size + checker_res.second); - return tree_res; - } - template <typename InputIterator> - void insert(InputIterator b, InputIterator e) { - for (; b != e; ++b) { - insert(*b); - } - } -}; - -// A checker for multiple sorted associative containers. TreeType is expected -// to be btree_{multiset,multimap} and CheckerType is expected to be -// {multiset,multimap}. -template <typename TreeType, typename CheckerType> -class multi_checker : public base_checker<TreeType, CheckerType> { - typedef base_checker<TreeType, CheckerType> super_type; - typedef multi_checker<TreeType, CheckerType> self_type; - - public: - typedef typename super_type::iterator iterator; - typedef typename super_type::value_type value_type; - - public: - // Default constructor. - multi_checker() - : super_type() { - } - // Copy constructor. - multi_checker(const self_type &x) - : super_type(x) { - } - // Range constructor. - template <class InputIterator> - multi_checker(InputIterator b, InputIterator e) - : super_type(b, e) { - } - - // Insertion routines. - iterator insert(const value_type &x) { - int size = this->tree_.size(); - typename CheckerType::iterator checker_res = this->checker_.insert(x); - iterator tree_res = this->tree_.insert(x); - EXPECT_EQ(*tree_res, *checker_res); - EXPECT_EQ(this->tree_.size(), this->checker_.size()); - EXPECT_EQ(this->tree_.size(), size + 1); - return tree_res; - } - iterator insert(iterator position, const value_type &x) { - int size = this->tree_.size(); - typename CheckerType::iterator checker_res = this->checker_.insert(x); - iterator tree_res = this->tree_.insert(position, x); - EXPECT_EQ(*tree_res, *checker_res); - EXPECT_EQ(this->tree_.size(), this->checker_.size()); - EXPECT_EQ(this->tree_.size(), size + 1); - return tree_res; - } - template <typename InputIterator> - void insert(InputIterator b, InputIterator e) { - for (; b != e; ++b) { - insert(*b); - } - } -}; - -char* GenerateDigits(char buf[16], int val, int maxval) { - EXPECT_LE(val, maxval); - int p = 15; - buf[p--] = 0; - while (maxval > 0) { - buf[p--] = '0' + (val % 10); - val /= 10; - maxval /= 10; - } - return buf + p + 1; -} - -template <typename K> -struct Generator { - int maxval; - Generator(int m) - : maxval(m) { - } - K operator()(int i) const { - EXPECT_LE(i, maxval); - return i; - } -}; - -template <> -struct Generator<std::string> { - int maxval; - Generator(int m) - : maxval(m) { - } - std::string operator()(int i) const { - char buf[16]; - return GenerateDigits(buf, i, maxval); - } -}; - -template <typename T, typename U> -struct Generator<std::pair<T, U> > { - Generator<typename std::remove_const<T>::type> tgen; - Generator<typename std::remove_const<U>::type> ugen; - - Generator(int m) - : tgen(m), - ugen(m) { - } - std::pair<T, U> operator()(int i) const { - return std::make_pair(tgen(i), ugen(i)); - } -}; - -// Generate values for our tests and benchmarks. Value range is [0, maxval]. -const std::vector<int>& GenerateNumbers(int n, int maxval) { - static std::vector<int> values; - static std::set<int> unique_values; - - if (values.size() < n) { - - for (int i = values.size(); i < n; i++) { - int value; - do { - value = rand() % (maxval + 1); - } while (unique_values.find(value) != unique_values.end()); - - values.push_back(value); - unique_values.insert(value); - } - } - - return values; -} - -// Generates values in the range -// [0, 4 * min(FLAGS_benchmark_values, FLAGS_test_values)] -template <typename V> -std::vector<V> GenerateValues(int n) { - int two_times_max = 2 * std::max(FLAGS_benchmark_values, FLAGS_test_values); - int four_times_max = 2 * two_times_max; - EXPECT_LE(n, two_times_max); - const std::vector<int> &nums = GenerateNumbers(n, four_times_max); - Generator<V> gen(four_times_max); - std::vector<V> vec; - - for (int i = 0; i < n; i++) { - vec.push_back(gen(nums[i])); - } - - return vec; -} - -template <typename T, typename V> -void DoTest(const char *name, T *b, const std::vector<V> &values) { - typename KeyOfValue<typename T::key_type, V>::type key_of_value; - - T &mutable_b = *b; - const T &const_b = *b; - - // Test insert. - for (int i = 0; i < values.size(); ++i) { - mutable_b.insert(values[i]); - mutable_b.value_check(values[i]); - } - assert(mutable_b.size() == values.size()); - - const_b.verify(); - printf(" %s fullness=%0.2f overhead=%0.2f bytes-per-value=%0.2f\n", - name, const_b.fullness(), const_b.overhead(), - double(const_b.bytes_used()) / const_b.size()); - - // Test copy constructor. - T b_copy(const_b); - EXPECT_EQ(b_copy.size(), const_b.size()); - EXPECT_LE(b_copy.height(), const_b.height()); - EXPECT_LE(b_copy.internal_nodes(), const_b.internal_nodes()); - EXPECT_LE(b_copy.leaf_nodes(), const_b.leaf_nodes()); - for (int i = 0; i < values.size(); ++i) { - EXPECT_EQ(*b_copy.find(key_of_value(values[i])), values[i]); - } - - // Test range constructor. - T b_range(const_b.begin(), const_b.end()); - EXPECT_EQ(b_range.size(), const_b.size()); - EXPECT_LE(b_range.height(), const_b.height()); - EXPECT_LE(b_range.internal_nodes(), const_b.internal_nodes()); - EXPECT_LE(b_range.leaf_nodes(), const_b.leaf_nodes()); - for (int i = 0; i < values.size(); ++i) { - EXPECT_EQ(*b_range.find(key_of_value(values[i])), values[i]); - } - - // Test range insertion for values that already exist. - b_range.insert(b_copy.begin(), b_copy.end()); - b_range.verify(); - - // Test range insertion for new values. - b_range.clear(); - b_range.insert(b_copy.begin(), b_copy.end()); - EXPECT_EQ(b_range.size(), b_copy.size()); - EXPECT_EQ(b_range.height(), b_copy.height()); - EXPECT_EQ(b_range.internal_nodes(), b_copy.internal_nodes()); - EXPECT_EQ(b_range.leaf_nodes(), b_copy.leaf_nodes()); - for (int i = 0; i < values.size(); ++i) { - EXPECT_EQ(*b_range.find(key_of_value(values[i])), values[i]); - } - - // Test assignment to self. Nothing should change. - b_range.operator=(b_range); - EXPECT_EQ(b_range.size(), b_copy.size()); - EXPECT_EQ(b_range.height(), b_copy.height()); - EXPECT_EQ(b_range.internal_nodes(), b_copy.internal_nodes()); - EXPECT_EQ(b_range.leaf_nodes(), b_copy.leaf_nodes()); - - // Test assignment of new values. - b_range.clear(); - b_range = b_copy; - EXPECT_EQ(b_range.size(), b_copy.size()); - EXPECT_EQ(b_range.height(), b_copy.height()); - EXPECT_EQ(b_range.internal_nodes(), b_copy.internal_nodes()); - EXPECT_EQ(b_range.leaf_nodes(), b_copy.leaf_nodes()); - - // Test swap. - b_range.clear(); - b_range.swap(b_copy); - EXPECT_EQ(b_copy.size(), 0); - EXPECT_EQ(b_range.size(), const_b.size()); - for (int i = 0; i < values.size(); ++i) { - EXPECT_EQ(*b_range.find(key_of_value(values[i])), values[i]); - } - b_range.swap(b_copy); - - // Test erase via values. - for (int i = 0; i < values.size(); ++i) { - mutable_b.erase(key_of_value(values[i])); - // Erasing a non-existent key should have no effect. - EXPECT_EQ(mutable_b.erase(key_of_value(values[i])), 0); - } - - const_b.verify(); - EXPECT_EQ(const_b.internal_nodes(), 0); - EXPECT_EQ(const_b.leaf_nodes(), 0); - EXPECT_EQ(const_b.size(), 0); - - // Test erase via iterators. - mutable_b = b_copy; - for (int i = 0; i < values.size(); ++i) { - mutable_b.erase(mutable_b.find(key_of_value(values[i]))); - } - - const_b.verify(); - EXPECT_EQ(const_b.internal_nodes(), 0); - EXPECT_EQ(const_b.leaf_nodes(), 0); - EXPECT_EQ(const_b.size(), 0); - - // Test insert with hint. - for (int i = 0; i < values.size(); i++) { - mutable_b.insert(mutable_b.upper_bound(key_of_value(values[i])), values[i]); - } - - const_b.verify(); - - // Test dumping of the btree to an ostream. There should be 1 line for each - // value. - std::stringstream strm; - strm << mutable_b.tree(); - EXPECT_EQ(mutable_b.size(), strcount(strm.str(), '\n')); - - // Test range erase. - mutable_b.erase(mutable_b.begin(), mutable_b.end()); - EXPECT_EQ(mutable_b.size(), 0); - const_b.verify(); - - // First half. - mutable_b = b_copy; - typename T::iterator mutable_iter_end = mutable_b.begin(); - for (int i = 0; i < values.size() / 2; ++i) ++mutable_iter_end; - mutable_b.erase(mutable_b.begin(), mutable_iter_end); - EXPECT_EQ(mutable_b.size(), values.size() - values.size() / 2); - const_b.verify(); - - // Second half. - mutable_b = b_copy; - typename T::iterator mutable_iter_begin = mutable_b.begin(); - for (int i = 0; i < values.size() / 2; ++i) ++mutable_iter_begin; - mutable_b.erase(mutable_iter_begin, mutable_b.end()); - EXPECT_EQ(mutable_b.size(), values.size() / 2); - const_b.verify(); - - // Second quarter. - mutable_b = b_copy; - mutable_iter_begin = mutable_b.begin(); - for (int i = 0; i < values.size() / 4; ++i) ++mutable_iter_begin; - mutable_iter_end = mutable_iter_begin; - for (int i = 0; i < values.size() / 4; ++i) ++mutable_iter_end; - mutable_b.erase(mutable_iter_begin, mutable_iter_end); - EXPECT_EQ(mutable_b.size(), values.size() - values.size() / 4); - const_b.verify(); - - mutable_b.clear(); -} - -template <typename T> -void ConstTest() { - typedef typename T::value_type value_type; - typename KeyOfValue<typename T::key_type, value_type>::type key_of_value; - - T mutable_b; - const T &const_b = mutable_b; - - // Insert a single value into the container and test looking it up. - value_type value = Generator<value_type>(2)(2); - mutable_b.insert(value); - EXPECT_TRUE(mutable_b.find(key_of_value(value)) != const_b.end()); - EXPECT_TRUE(const_b.find(key_of_value(value)) != mutable_b.end()); - EXPECT_EQ(*const_b.lower_bound(key_of_value(value)), value); - EXPECT_TRUE(const_b.upper_bound(key_of_value(value)) == const_b.end()); - EXPECT_EQ(*const_b.equal_range(key_of_value(value)).first, value); - - // We can only create a non-const iterator from a non-const container. - typename T::iterator mutable_iter(mutable_b.begin()); - EXPECT_TRUE(mutable_iter == const_b.begin()); - EXPECT_TRUE(mutable_iter != const_b.end()); - EXPECT_TRUE(const_b.begin() == mutable_iter); - EXPECT_TRUE(const_b.end() != mutable_iter); - typename T::reverse_iterator mutable_riter(mutable_b.rbegin()); - EXPECT_TRUE(mutable_riter == const_b.rbegin()); - EXPECT_TRUE(mutable_riter != const_b.rend()); - EXPECT_TRUE(const_b.rbegin() == mutable_riter); - EXPECT_TRUE(const_b.rend() != mutable_riter); - - // We can create a const iterator from a non-const iterator. - typename T::const_iterator const_iter(mutable_iter); - EXPECT_TRUE(const_iter == mutable_b.begin()); - EXPECT_TRUE(const_iter != mutable_b.end()); - EXPECT_TRUE(mutable_b.begin() == const_iter); - EXPECT_TRUE(mutable_b.end() != const_iter); - typename T::const_reverse_iterator const_riter(mutable_riter); - EXPECT_EQ(const_riter, mutable_b.rbegin()); - EXPECT_TRUE(const_riter != mutable_b.rend()); - EXPECT_EQ(mutable_b.rbegin(), const_riter); - EXPECT_TRUE(mutable_b.rend() != const_riter); - - // Make sure various methods can be invoked on a const container. - const_b.verify(); - EXPECT_FALSE(const_b.empty()); - EXPECT_EQ(const_b.size(), 1); - EXPECT_GT(const_b.max_size(), 0); - EXPECT_EQ(const_b.height(), 1); - EXPECT_EQ(const_b.count(key_of_value(value)), 1); - EXPECT_EQ(const_b.internal_nodes(), 0); - EXPECT_EQ(const_b.leaf_nodes(), 1); - EXPECT_EQ(const_b.nodes(), 1); - EXPECT_GT(const_b.bytes_used(), 0); - EXPECT_GT(const_b.fullness(), 0); - EXPECT_GT(const_b.overhead(), 0); -} - -template <typename T, typename C> -void BtreeTest() { - ConstTest<T>(); - - typedef typename std::remove_const<typename T::value_type>::type V; - std::vector<V> random_values = GenerateValues<V>(FLAGS_test_values); - - unique_checker<T, C> container; - - // Test key insertion/deletion in sorted order. - std::vector<V> sorted_values(random_values); - sort(sorted_values.begin(), sorted_values.end()); - DoTest("sorted: ", &container, sorted_values); - - // Test key insertion/deletion in reverse sorted order. - reverse(sorted_values.begin(), sorted_values.end()); - DoTest("rsorted: ", &container, sorted_values); - - // Test key insertion/deletion in random order. - DoTest("random: ", &container, random_values); -} - -template <typename T, typename C> -void BtreeMultiTest() { - ConstTest<T>(); - - typedef typename std::remove_const<typename T::value_type>::type V; - const std::vector<V>& random_values = GenerateValues<V>(FLAGS_test_values); - - multi_checker<T, C> container; - - // Test keys in sorted order. - std::vector<V> sorted_values(random_values); - sort(sorted_values.begin(), sorted_values.end()); - DoTest("sorted: ", &container, sorted_values); - - // Test keys in reverse sorted order. - reverse(sorted_values.begin(), sorted_values.end()); - DoTest("rsorted: ", &container, sorted_values); - - // Test keys in random order. - DoTest("random: ", &container, random_values); - - // Test keys in random order w/ duplicates. - std::vector<V> duplicate_values(random_values); - duplicate_values.insert( - duplicate_values.end(), random_values.begin(), random_values.end()); - DoTest("duplicates:", &container, duplicate_values); - - // Test all identical keys. - std::vector<V> identical_values(100); - fill(identical_values.begin(), identical_values.end(), Generator<V>(2)(2)); - DoTest("identical: ", &container, identical_values); -} - -template <typename T, typename Alloc = std::allocator<T> > -class TestAllocator : public Alloc { - public: - typedef typename Alloc::pointer pointer; - typedef typename Alloc::size_type size_type; - - TestAllocator() : bytes_used_(NULL) { } - TestAllocator(int64_t *bytes_used) : bytes_used_(bytes_used) { } - - // Constructor used for rebinding - template <class U> - TestAllocator(const TestAllocator<U>& x) - : Alloc(x), - bytes_used_(x.bytes_used()) { - } - - pointer allocate(size_type n, std::allocator<void>::const_pointer hint = 0) { - EXPECT_TRUE(bytes_used_ != NULL); - *bytes_used_ += n * sizeof(T); - return Alloc::allocate(n, hint); - } - - void deallocate(pointer p, size_type n) { - Alloc::deallocate(p, n); - EXPECT_TRUE(bytes_used_ != NULL); - *bytes_used_ -= n * sizeof(T); - } - - // Rebind allows an allocator<T> to be used for a different type - template <class U> struct rebind { - typedef TestAllocator<U, typename Alloc::template rebind<U>::other> other; - }; - - int64_t* bytes_used() const { return bytes_used_; } - - private: - int64_t *bytes_used_; -}; - -template <typename T> -void BtreeAllocatorTest() { - typedef typename T::value_type value_type; - - int64_t alloc1 = 0; - int64_t alloc2 = 0; - T b1(typename T::key_compare(), &alloc1); - T b2(typename T::key_compare(), &alloc2); - - // This should swap the allocators! - swap(b1, b2); - - for (int i = 0; i < 1000; i++) { - b1.insert(Generator<value_type>(1000)(i)); - } - - // We should have allocated out of alloc2! - EXPECT_LE(b1.bytes_used(), alloc2 + sizeof(b1)); - EXPECT_GT(alloc2, alloc1); -} - -template <typename T> -void BtreeMapTest() { - typedef typename T::value_type value_type; - typedef typename T::mapped_type mapped_type; - - mapped_type m = Generator<mapped_type>(0)(0); - (void) m; - - T b; - - // Verify we can insert using operator[]. - for (int i = 0; i < 1000; i++) { - value_type v = Generator<value_type>(1000)(i); - b[v.first] = v.second; - } - EXPECT_EQ(b.size(), 1000); - - // Test whether we can use the "->" operator on iterators and - // reverse_iterators. This stresses the btree_map_params::pair_pointer - // mechanism. - EXPECT_EQ(b.begin()->first, Generator<value_type>(1000)(0).first); - EXPECT_EQ(b.begin()->second, Generator<value_type>(1000)(0).second); - EXPECT_EQ(b.rbegin()->first, Generator<value_type>(1000)(999).first); - EXPECT_EQ(b.rbegin()->second, Generator<value_type>(1000)(999).second); -} - -template <typename T> -void BtreeMultiMapTest() { - typedef typename T::mapped_type mapped_type; - mapped_type m = Generator<mapped_type>(0)(0); - (void) m; -} - -} // namespace btree - -#endif // UTIL_BTREE_BTREE_TEST_H__ diff --git a/cpp-btree/btree_test_flags.cc b/cpp-btree/btree_test_flags.cc deleted file mode 100644 index bf608a9..0000000 --- a/cpp-btree/btree_test_flags.cc +++ /dev/null @@ -1,20 +0,0 @@ -// Copyright 2013 Google Inc. All Rights Reserved. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -#include "gflags/gflags.h" - -DEFINE_int32(test_values, 10000, - "The number of values to use for tests."); -DEFINE_int32(benchmark_values, 1000000, - "The number of values to use for benchmarks."); diff --git a/cpp-btree/safe_btree.h b/cpp-btree/safe_btree.h deleted file mode 100644 index 2d85c70..0000000 --- a/cpp-btree/safe_btree.h +++ /dev/null @@ -1,395 +0,0 @@ -// Copyright 2013 Google Inc. All Rights Reserved. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. -// -// A safe_btree<> wraps around a btree<> and removes the caveat that insertion -// and deletion invalidate iterators. A safe_btree<> maintains a generation -// number that is incremented on every mutation. A safe_btree<>::iterator keeps -// a pointer to the safe_btree<> it came from, the generation of the tree when -// it was last validated and the key the underlying btree<>::iterator points -// to. If an iterator is accessed and its generation differs from the tree -// generation it is revalidated. -// -// References and pointers returned by safe_btree iterators are not safe. -// -// See the incorrect usage examples mentioned in safe_btree_set.h and -// safe_btree_map.h. - -#ifndef UTIL_BTREE_SAFE_BTREE_H__ -#define UTIL_BTREE_SAFE_BTREE_H__ - -#include <stddef.h> -#include <iosfwd> -#include <utility> - -#include "btree.h" - -namespace btree { - -template <typename Tree, typename Iterator> -class safe_btree_iterator { - public: - typedef typename Iterator::key_type key_type; - typedef typename Iterator::value_type value_type; - typedef typename Iterator::size_type size_type; - typedef typename Iterator::difference_type difference_type; - typedef typename Iterator::pointer pointer; - typedef typename Iterator::reference reference; - typedef typename Iterator::const_pointer const_pointer; - typedef typename Iterator::const_reference const_reference; - typedef typename Iterator::iterator_category iterator_category; - typedef typename Tree::iterator iterator; - typedef typename Tree::const_iterator const_iterator; - typedef safe_btree_iterator<Tree, Iterator> self_type; - - void update() const { - if (iter_ != tree_->internal_btree()->end()) { - // A positive generation indicates a valid key. - generation_ = tree_->generation(); - key_ = iter_.key(); - } else { - // Use a negative generation to indicate iter_ points to end(). - generation_ = -tree_->generation(); - } - } - - public: - safe_btree_iterator() - : generation_(0), - key_(), - iter_(), - tree_(NULL) { - } - safe_btree_iterator(const iterator &x) - : generation_(x.generation()), - key_(x.key()), - iter_(x.iter()), - tree_(x.tree()) { - } - safe_btree_iterator(Tree *tree, const Iterator &iter) - : generation_(), - key_(), - iter_(iter), - tree_(tree) { - update(); - } - - Tree* tree() const { return tree_; } - int64_t generation() const { return generation_; } - - Iterator* mutable_iter() const { - if (generation_ != tree_->generation()) { - if (generation_ > 0) { - // This does the wrong thing for a multi{set,map}. If my iter was - // pointing to the 2nd of 2 values with the same key, then this will - // reset it to point to the first. This is why we don't provide a - // safe_btree_multi{set,map}. - iter_ = tree_->internal_btree()->lower_bound(key_); - update(); - } else if (-generation_ != tree_->generation()) { - iter_ = tree_->internal_btree()->end(); - generation_ = -tree_->generation(); - } - } - return &iter_; - } - const Iterator& iter() const { - return *mutable_iter(); - } - - // Equality/inequality operators. - bool operator==(const const_iterator &x) const { - return iter() == x.iter(); - } - bool operator!=(const const_iterator &x) const { - return iter() != x.iter(); - } - - // Accessors for the key/value the iterator is pointing at. - const key_type& key() const { - return key_; - } - // This reference value is potentially invalidated by any non-const - // method on the tree; it is NOT safe. - reference operator*() const { - assert(generation_ > 0); - return iter().operator*(); - } - // This pointer value is potentially invalidated by any non-const - // method on the tree; it is NOT safe. - pointer operator->() const { - assert(generation_ > 0); - return iter().operator->(); - } - - // Increment/decrement operators. - self_type& operator++() { - ++(*mutable_iter()); - update(); - return *this; - } - self_type& operator--() { - --(*mutable_iter()); - update(); - return *this; - } - self_type operator++(int) { - self_type tmp = *this; - ++*this; - return tmp; - } - self_type operator--(int) { - self_type tmp = *this; - --*this; - return tmp; - } - - private: - // The generation of the tree when "iter" was updated. - mutable int64_t generation_; - // The key the iterator points to. - mutable key_type key_; - // The underlying iterator. - mutable Iterator iter_; - // The tree the iterator is associated with. - Tree *tree_; -}; - -template <typename Params> -class safe_btree { - typedef safe_btree<Params> self_type; - - typedef btree<Params> btree_type; - typedef typename btree_type::iterator tree_iterator; - typedef typename btree_type::const_iterator tree_const_iterator; - - public: - typedef typename btree_type::params_type params_type; - typedef typename btree_type::key_type key_type; - typedef typename btree_type::data_type data_type; - typedef typename btree_type::mapped_type mapped_type; - typedef typename btree_type::value_type value_type; - typedef typename btree_type::key_compare key_compare; - typedef typename btree_type::allocator_type allocator_type; - typedef typename btree_type::pointer pointer; - typedef typename btree_type::const_pointer const_pointer; - typedef typename btree_type::reference reference; - typedef typename btree_type::const_reference const_reference; - typedef typename btree_type::size_type size_type; - typedef typename btree_type::difference_type difference_type; - typedef safe_btree_iterator<self_type, tree_iterator> iterator; - typedef safe_btree_iterator< - const self_type, tree_const_iterator> const_iterator; - typedef std::reverse_iterator<const_iterator> const_reverse_iterator; - typedef std::reverse_iterator<iterator> reverse_iterator; - - public: - // Default constructor. - safe_btree(const key_compare &comp, const allocator_type &alloc) - : tree_(comp, alloc), - generation_(1) { - } - - // Copy constructor. - safe_btree(const self_type &x) - : tree_(x.tree_), - generation_(1) { - } - - iterator begin() { - return iterator(this, tree_.begin()); - } - const_iterator begin() const { - return const_iterator(this, tree_.begin()); - } - iterator end() { - return iterator(this, tree_.end()); - } - const_iterator end() const { - return const_iterator(this, tree_.end()); - } - reverse_iterator rbegin() { - return reverse_iterator(end()); - } - const_reverse_iterator rbegin() const { - return const_reverse_iterator(end()); - } - reverse_iterator rend() { - return reverse_iterator(begin()); - } - const_reverse_iterator rend() const { - return const_reverse_iterator(begin()); - } - - // Lookup routines. - iterator lower_bound(const key_type &key) { - return iterator(this, tree_.lower_bound(key)); - } - const_iterator lower_bound(const key_type &key) const { - return const_iterator(this, tree_.lower_bound(key)); - } - iterator upper_bound(const key_type &key) { - return iterator(this, tree_.upper_bound(key)); - } - const_iterator upper_bound(const key_type &key) const { - return const_iterator(this, tree_.upper_bound(key)); - } - std::pair<iterator, iterator> equal_range(const key_type &key) { - std::pair<tree_iterator, tree_iterator> p = tree_.equal_range(key); - return std::make_pair(iterator(this, p.first), - iterator(this, p.second)); - } - std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const { - std::pair<tree_const_iterator, tree_const_iterator> p = tree_.equal_range(key); - return std::make_pair(const_iterator(this, p.first), - const_iterator(this, p.second)); - } - iterator find_unique(const key_type &key) { - return iterator(this, tree_.find_unique(key)); - } - const_iterator find_unique(const key_type &key) const { - return const_iterator(this, tree_.find_unique(key)); - } - iterator find_multi(const key_type &key) { - return iterator(this, tree_.find_multi(key)); - } - const_iterator find_multi(const key_type &key) const { - return const_iterator(this, tree_.find_multi(key)); - } - size_type count_unique(const key_type &key) const { - return tree_.count_unique(key); - } - size_type count_multi(const key_type &key) const { - return tree_.count_multi(key); - } - - // Insertion routines. - template <typename ValuePointer> - std::pair<iterator, bool> insert_unique(const key_type &key, ValuePointer value) { - std::pair<tree_iterator, bool> p = tree_.insert_unique(key, value); - generation_ += p.second; - return std::make_pair(iterator(this, p.first), p.second); - } - std::pair<iterator, bool> insert_unique(const value_type &v) { - std::pair<tree_iterator, bool> p = tree_.insert_unique(v); - generation_ += p.second; - return std::make_pair(iterator(this, p.first), p.second); - } - iterator insert_unique(iterator position, const value_type &v) { - tree_iterator tree_pos = position.iter(); - ++generation_; - return iterator(this, tree_.insert_unique(tree_pos, v)); - } - template <typename InputIterator> - void insert_unique(InputIterator b, InputIterator e) { - for (; b != e; ++b) { - insert_unique(*b); - } - } - iterator insert_multi(const value_type &v) { - ++generation_; - return iterator(this, tree_.insert_multi(v)); - } - iterator insert_multi(iterator position, const value_type &v) { - tree_iterator tree_pos = position.iter(); - ++generation_; - return iterator(this, tree_.insert_multi(tree_pos, v)); - } - template <typename InputIterator> - void insert_multi(InputIterator b, InputIterator e) { - for (; b != e; ++b) { - insert_multi(*b); - } - } - self_type& operator=(const self_type &x) { - if (&x == this) { - // Don't copy onto ourselves. - return *this; - } - ++generation_; - tree_ = x.tree_; - return *this; - } - - // Deletion routines. - void erase(const iterator &begin, const iterator &end) { - tree_.erase(begin.iter(), end.iter()); - ++generation_; - } - // Erase the specified iterator from the btree. The iterator must be valid - // (i.e. not equal to end()). Return an iterator pointing to the node after - // the one that was erased (or end() if none exists). - iterator erase(iterator iter) { - tree_iterator res = tree_.erase(iter.iter()); - ++generation_; - return iterator(this, res); - } - int erase_unique(const key_type &key) { - int res = tree_.erase_unique(key); - generation_ += res; - return res; - } - int erase_multi(const key_type &key) { - int res = tree_.erase_multi(key); - generation_ += res; - return res; - } - - // Access to the underlying btree. - btree_type* internal_btree() { return &tree_; } - const btree_type* internal_btree() const { return &tree_; } - - // Utility routines. - void clear() { - ++generation_; - tree_.clear(); - } - void swap(self_type &x) { - ++generation_; - ++x.generation_; - tree_.swap(x.tree_); - } - void dump(std::ostream &os) const { - tree_.dump(os); - } - void verify() const { - tree_.verify(); - } - int64_t generation() const { - return generation_; - } - key_compare key_comp() const { return tree_.key_comp(); } - - // Size routines. - size_type size() const { return tree_.size(); } - size_type max_size() const { return tree_.max_size(); } - bool empty() const { return tree_.empty(); } - size_type height() const { return tree_.height(); } - size_type internal_nodes() const { return tree_.internal_nodes(); } - size_type leaf_nodes() const { return tree_.leaf_nodes(); } - size_type nodes() const { return tree_.nodes(); } - size_type bytes_used() const { return tree_.bytes_used(); } - static double average_bytes_per_value() { - return btree_type::average_bytes_per_value(); - } - double fullness() const { return tree_.fullness(); } - double overhead() const { return tree_.overhead(); } - - private: - btree_type tree_; - int64_t generation_; -}; - -} // namespace btree - -#endif // UTIL_BTREE_SAFE_BTREE_H__ diff --git a/cpp-btree/safe_btree_map.h b/cpp-btree/safe_btree_map.h deleted file mode 100644 index a0668f1..0000000 --- a/cpp-btree/safe_btree_map.h +++ /dev/null @@ -1,89 +0,0 @@ -// Copyright 2013 Google Inc. All Rights Reserved. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. -// -// The safe_btree_map<> is like btree_map<> except that it removes the caveat -// about insertion and deletion invalidating existing iterators at a small cost -// in making iterators larger and slower. -// -// Revalidation occurs whenever an iterator is accessed. References -// and pointers returned by safe_btree_map<> iterators are not stable, -// they are potentially invalidated by any non-const method on the map. -// -// BEGIN INCORRECT EXAMPLE -// for (auto i = safe_map->begin(); i != safe_map->end(); ++i) { -// const T *value = &i->second; // DO NOT DO THIS -// [code that modifies safe_map and uses value]; -// } -// END INCORRECT EXAMPLE -#ifndef UTIL_BTREE_SAFE_BTREE_MAP_H__ -#define UTIL_BTREE_SAFE_BTREE_MAP_H__ - -#include <functional> -#include <memory> -#include <utility> - -#include "btree_container.h" -#include "btree_map.h" -#include "safe_btree.h" - -namespace btree { - -// The safe_btree_map class is needed mainly for its constructors. -template <typename Key, typename Value, - typename Compare = std::less<Key>, - typename Alloc = std::allocator<std::pair<const Key, Value> >, - int TargetNodeSize = 256> -class safe_btree_map : public btree_map_container< - safe_btree<btree_map_params<Key, Value, Compare, Alloc, TargetNodeSize> > > { - - typedef safe_btree_map<Key, Value, Compare, Alloc, TargetNodeSize> self_type; - typedef btree_map_params< - Key, Value, Compare, Alloc, TargetNodeSize> params_type; - typedef safe_btree<params_type> btree_type; - typedef btree_map_container<btree_type> super_type; - - public: - typedef typename btree_type::key_compare key_compare; - typedef typename btree_type::allocator_type allocator_type; - - public: - // Default constructor. - safe_btree_map(const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(comp, alloc) { - } - - // Copy constructor. - safe_btree_map(const self_type &x) - : super_type(x) { - } - - // Range constructor. - template <class InputIterator> - safe_btree_map(InputIterator b, InputIterator e, - const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(b, e, comp, alloc) { - } -}; - -template <typename K, typename V, typename C, typename A, int N> -inline void swap(safe_btree_map<K, V, C, A, N> &x, - safe_btree_map<K, V, C, A, N> &y) { - x.swap(y); -} - -} // namespace btree - -#endif // UTIL_BTREE_SAFE_BTREE_MAP_H__ diff --git a/cpp-btree/safe_btree_set.h b/cpp-btree/safe_btree_set.h deleted file mode 100644 index a6cd541..0000000 --- a/cpp-btree/safe_btree_set.h +++ /dev/null @@ -1,88 +0,0 @@ -// Copyright 2013 Google Inc. All Rights Reserved. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. -// -// The safe_btree_set<> is like btree_set<> except that it removes the caveat -// about insertion and deletion invalidating existing iterators at a small cost -// in making iterators larger and slower. -// -// Revalidation occurs whenever an iterator is accessed. References -// and pointers returned by safe_btree_map<> iterators are not stable, -// they are potentially invalidated by any non-const method on the set. -// -// BEGIN INCORRECT EXAMPLE -// for (auto i = safe_set->begin(); i != safe_set->end(); ++i) { -// const T &value = *i; // DO NOT DO THIS -// [code that modifies safe_set and uses value]; -// } -// END INCORRECT EXAMPLE - -#ifndef UTIL_BTREE_SAFE_BTREE_SET_H__ -#define UTIL_BTREE_SAFE_BTREE_SET_H__ - -#include <functional> -#include <memory> - -#include "btree_container.h" -#include "btree_set.h" -#include "safe_btree.h" - -namespace btree { - -// The safe_btree_set class is needed mainly for its constructors. -template <typename Key, - typename Compare = std::less<Key>, - typename Alloc = std::allocator<Key>, - int TargetNodeSize = 256> -class safe_btree_set : public btree_unique_container< - safe_btree<btree_set_params<Key, Compare, Alloc, TargetNodeSize> > > { - - typedef safe_btree_set<Key, Compare, Alloc, TargetNodeSize> self_type; - typedef btree_set_params<Key, Compare, Alloc, TargetNodeSize> params_type; - typedef safe_btree<params_type> btree_type; - typedef btree_unique_container<btree_type> super_type; - - public: - typedef typename btree_type::key_compare key_compare; - typedef typename btree_type::allocator_type allocator_type; - - public: - // Default constructor. - safe_btree_set(const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(comp, alloc) { - } - - // Copy constructor. - safe_btree_set(const self_type &x) - : super_type(x) { - } - - // Range constructor. - template <class InputIterator> - safe_btree_set(InputIterator b, InputIterator e, - const key_compare &comp = key_compare(), - const allocator_type &alloc = allocator_type()) - : super_type(b, e, comp, alloc) { - } -}; - -template <typename K, typename C, typename A, int N> -inline void swap(safe_btree_set<K, C, A, N> &x, - safe_btree_set<K, C, A, N> &y) { - x.swap(y); -} - -} // namespace btree - -#endif // UTIL_BTREE_SAFE_BTREE_SET_H__ diff --git a/cpp-btree/safe_btree_test.cc b/cpp-btree/safe_btree_test.cc deleted file mode 100644 index 0d77ae0..0000000 --- a/cpp-btree/safe_btree_test.cc +++ /dev/null @@ -1,116 +0,0 @@ -// Copyright 2013 Google Inc. All Rights Reserved. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -// TODO(pmattis): Add some tests that iterators are not invalidated by -// insertion and deletion. - -#include <functional> -#include <map> -#include <set> -#include <string> -#include <utility> - -#include "gtest/gtest.h" -#include "btree_test.h" -#include "safe_btree_map.h" -#include "safe_btree_set.h" - -class UnsafeArena; - -namespace btree { -namespace { - -template <typename K, int N> -void SetTest() { - typedef TestAllocator<K> TestAlloc; - BtreeTest<safe_btree_set<K, std::less<K>, std::allocator<K>, N>, std::set<K> >(); - BtreeAllocatorTest<safe_btree_set<K, std::less<K>, TestAlloc, N> >(); -} - -template <typename K, int N> -void MapTest() { - typedef TestAllocator<K> TestAlloc; - BtreeTest<safe_btree_map<K, K, std::less<K>, std::allocator<K>, N>, std::map<K, K> >(); - BtreeAllocatorTest<safe_btree_map<K, K, std::less<K>, TestAlloc, N> >(); - BtreeMapTest<safe_btree_map<K, K, std::less<K>, std::allocator<K>, N> >(); -} - -TEST(SafeBtree, set_int32_32) { SetTest<int32_t, 32>(); } -TEST(SafeBtree, set_int32_64) { SetTest<int32_t, 64>(); } -TEST(SafeBtree, set_int32_128) { SetTest<int32_t, 128>(); } -TEST(SafeBtree, set_int32_256) { SetTest<int32_t, 256>(); } -TEST(SafeBtree, set_int64_256) { SetTest<int64_t, 256>(); } -TEST(SafeBtree, set_string_256) { SetTest<std::string, 256>(); } -TEST(SafeBtree, set_pair_256) { SetTest<std::pair<int, int>, 256>(); } -TEST(SafeBtree, map_int32_256) { MapTest<int32_t, 256>(); } -TEST(SafeBtree, map_int64_256) { MapTest<int64_t, 256>(); } -TEST(SafeBtree, map_string_256) { MapTest<std::string, 256>(); } -TEST(SafeBtree, map_pair_256) { MapTest<std::pair<int, int>, 256>(); } - -TEST(SafeBtree, Comparison) { - const int kSetSize = 1201; - safe_btree_set<int64_t> my_set; - for (int i = 0; i < kSetSize; ++i) { - my_set.insert(i); - } - safe_btree_set<int64_t> my_set_copy(my_set); - EXPECT_TRUE(my_set_copy == my_set); - EXPECT_TRUE(my_set == my_set_copy); - EXPECT_FALSE(my_set_copy != my_set); - EXPECT_FALSE(my_set != my_set_copy); - - my_set.insert(kSetSize); - EXPECT_FALSE(my_set_copy == my_set); - EXPECT_FALSE(my_set == my_set_copy); - EXPECT_TRUE(my_set_copy != my_set); - EXPECT_TRUE(my_set != my_set_copy); - - my_set.erase(kSetSize - 1); - EXPECT_FALSE(my_set_copy == my_set); - EXPECT_FALSE(my_set == my_set_copy); - EXPECT_TRUE(my_set_copy != my_set); - EXPECT_TRUE(my_set != my_set_copy); - - safe_btree_map<std::string, int64_t> my_map; - for (int i = 0; i < kSetSize; ++i) { - my_map[std::string(i, 'a')] = i; - } - safe_btree_map<std::string, int64_t> my_map_copy(my_map); - EXPECT_TRUE(my_map_copy == my_map); - EXPECT_TRUE(my_map == my_map_copy); - EXPECT_FALSE(my_map_copy != my_map); - EXPECT_FALSE(my_map != my_map_copy); - - ++my_map_copy[std::string(7, 'a')]; - EXPECT_FALSE(my_map_copy == my_map); - EXPECT_FALSE(my_map == my_map_copy); - EXPECT_TRUE(my_map_copy != my_map); - EXPECT_TRUE(my_map != my_map_copy); - - my_map_copy = my_map; - my_map["hello"] = kSetSize; - EXPECT_FALSE(my_map_copy == my_map); - EXPECT_FALSE(my_map == my_map_copy); - EXPECT_TRUE(my_map_copy != my_map); - EXPECT_TRUE(my_map != my_map_copy); - - my_map.erase(std::string(kSetSize - 1, 'a')); - EXPECT_FALSE(my_map_copy == my_map); - EXPECT_FALSE(my_map == my_map_copy); - EXPECT_TRUE(my_map_copy != my_map); - EXPECT_TRUE(my_map != my_map_copy); -} - -} // namespace -} // namespace btree |