kunashu / cpp-btree Goto Github PK
View Code? Open in Web Editor NEWAutomatically exported from code.google.com/p/cpp-btree
License: Apache License 2.0
Automatically exported from code.google.com/p/cpp-btree
License: Apache License 2.0
What steps will reproduce the problem?
Using the library in my project. build it.
What is the expected output? What do you see instead?
Many strict-aliasing warnings issued at
reference btree_node::value(int i)
What version of the product are you using? On what operating system?
1.0.1,linux, gcc 4.5.1
Please provide any additional information below.
My solution:
Add a cast function:
template <typename To, typename From>
To reconst_cast(From& from) {
return reinterpret_cast<To>(from);
}
template <typename Params>
class btree_node {
...
reference value(int i) {
return reconst_cast<reference>(fields_.values[i]);
}
const_reference value(int i) const {
return reconst_cast<const_reference>(fields_.values[i]); }
See thr attachment.
Original issue reported on code.google.com by chen3feng
on 7 Apr 2013 at 4:05
Attachments:
[deleted issue]
btree_map and btree_set are both extremely useful. They beat STL
unordered/map/set both in insertion time, lookup time and space consumption so
it would be a very valuable addition.
Many people from industry are not happy with STL associative containers and
they usually create their own (see recent CppCon video
https://www.youtube.com/watch?v=rX0ItVEVjHc. Also famous paper from committee
member: http://lafstern.org/matt/col1.pdf)
Also consider changing the lookup interface along heterogeneous lookup proposal
(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3657.htm) when
available. There are too many std::string/QString/CString keys out there (see
one sad story here:
http://channel9.msdn.com/Shows/C9-GoingNative/GoingNative-29-Massive-Improvement
s-for-Browsing-in-Large-Codebases-)
Common google you can do it
Original issue reported on code.google.com by [email protected]
on 8 Oct 2014 at 11:25
What steps will reproduce the problem?
1. Compile using MSVC 2010
What is the expected output? What do you see instead?
Compilation should succeed.
What version of the product are you using? On what operating system?
Windows 7 + MSVC 2010 (SP1)
Please provide any additional information below.
Compile error:
btree.h(1401) : error C2064: term does not evaluate to a function taking 2
arguments
That is the
COMPILE_ASSERT(
sizeof(key_compare_checker(key_compare_helper()(key_type(), key_type()))) ==
sizeof(big_),
key_comparison_function_must_return_bool);
Original issue reported on code.google.com by [email protected]
on 4 Feb 2013 at 2:18
What steps will reproduce the problem?
1. Use MSVC 2010 to compile any file using btree.h
What is the expected output? What do you see instead?
Should compile, but fails because ssize_t is not known.
What version of the product are you using? On what operating system?
Windows 7 + MSVC 2010 (with matching SDK)
Please provide any additional information below.
Can be fixed by a patch to btree.h like:
#if defined(_MSC_VER)
#include <BaseTsd.h>
typedef SSIZE_T ssize_t;
#endif
This should work with MSVC versions >= 2010, older ones might not work anyway
because of missing C++11 support.
Other issues remain, will open separate issues here for them.
Original issue reported on code.google.com by [email protected]
on 4 Feb 2013 at 1:33
Fix:
--- cpp-btree-1.0.1/btree.h 2013-02-06 14:18:00.000000000 +0800
+++ cpp-btree-1.0.1-non-c++11/btree.h 2013-04-08 12:17:40.000000000 +0800
@@ -100,8 +100,10 @@
#ifndef UTIL_BTREE_BTREE_H__
#define UTIL_BTREE_BTREE_H__
#include <assert.h>
#include <stddef.h>
+#include <stdint.h>
#include <string.h>
#include <sys/types.h>
#include <algorithm>
Original issue reported on code.google.com by chen3feng
on 8 Apr 2013 at 5:04
What steps will reproduce the problem?
1. Compile and run a program like:
#undef NDEBUG
#include "btree_set.h"
#include <cassert>
int main (void) {
assert(false);
}
What is the expected output? What do you see instead?
The assertion should fail. Instead the assertion is skipped since btree.h has
defined NDEBUG to 1. Reversing the order of includes would paper over the issue.
Original issue reported on code.google.com by [email protected]
on 3 May 2013 at 10:36
All our code build with -Wsign-compare warning flags, the signed size() cause
too many unnecessary change, and is not compatible with STL convention。
Original issue reported on code.google.com by chen3feng
on 7 Apr 2013 at 3:46
What steps will reproduce the problem?
1. Compile on VC11 with std::string as KeyType
What is the expected output? What do you see instead?
No Errors/Warnings
What version of the product are you using? On what operating system?
VC11
Please provide any additional information below.
Diff to produce compilation with no errors/warnings. COMPILER_ASSERT removed
since it is outstanding issue.
121a122,126
> #if defined(_MSC_VER)
> #include <BaseTsd.h>
> typedef SSIZE_T ssize_t;
> #endif
>
526c531
< void set_position(int v) { fields_.position = v; }
---
> void set_position(int v) { fields_.position = (typename
base_fields::field_type)v; }
530c535
< void set_count(int v) { fields_.count = v; }
---
> void set_count(int v) { fields_.count = (typename
base_fields::field_type)v; }
577c582
< c->fields_.position = i;
---
> c->fields_.position = (typename base_fields::field_type)i;
690c695
< f->max_count = max_count;
---
> f->max_count = (typename base_fields::field_type)max_count;
693,695c698,700
< if (!NDEBUG) {
< memset(&f->values, 0, max_count * sizeof(value_type));
< }
---
> #ifndef NDEBUG
> memset(&f->values, 0, max_count * sizeof(value_type));
> #endif
701c706
< if (!NDEBUG) {
---
> #ifndef NDEBUG
703c708
< }
---
> #endif
863,864c868,869
< friend class btree_internal_locate_plain_compare;
< friend class btree_internal_locate_compare_to;
---
> friend struct btree_internal_locate_plain_compare;
> friend struct btree_internal_locate_compare_to;
1400a1406
> #ifndef _MSC_VER
1414a1421
> #endif
1924c1931
< int count = distance(begin, end);
---
> int count = (int)distance(begin, end);
Original issue reported on code.google.com by [email protected]
on 7 Mar 2013 at 5:10
What steps will reproduce the problem?
1.
2.
3.
What is the expected output? What do you see instead?
n file included from thirdparty/cpp-btree-1.0.1/btree_bench.cc:29:0:
thirdparty/cpp-btree-1.0.1/btree_test.h: In member function 'void
btree::base_checker<TreeType, CheckerType>::erase(btree::base_checker<TreeType,
CheckerType>::iterator, btree::base_checker<TreeType, CheckerType>::iterator)':
thirdparty/cpp-btree-1.0.1/btree_test.h:308:182: internal compiler error:
Segmentation fault
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.
What version of the product are you using? On what operating system?
Please provide any additional information below.
Original issue reported on code.google.com by chen3feng
on 7 Apr 2013 at 3:36
Point project to GitHub
Original issue reported on code.google.com by piperchester
on 23 Mar 2015 at 2:40
Attachments:
Line 435:
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());
}
...
}
Should just pass comparator instance "comp" instead.
Original issue reported on code.google.com by [email protected]
on 6 Apr 2015 at 6:47
What steps will reproduce the problem?
1. Compile with an old compiler like xlC v8.0.0
What is the expected output? What do you see instead?
it does not compile
What version of the product are you using? On what operating system?
- cpp-btree-1.0.1
- AIX 5.3
Please provide any additional information below.
So I made little hacks to make it work.
First is to define a homemade type_traits to support the cpp-btree.
I attach it to this issue type_traits_hm.
Secondly I moved the external definition of some btree's methods into the
declaration directly in the class.
That's all.
Subsidiary I made a little hack to have a safe_btree_multiset working.
I checked the performances with an homemade code. I also attach it.
Original issue reported on code.google.com by [email protected]
on 1 Mar 2013 at 9:41
Attachments:
What steps will reproduce the problem?
Compile using MSVC 2013
What is the expected output? What do you see instead?
Compilation failed!
What version of the product are you using? On what operating system?
Windows 7(64) + MSVC 2013
Please provide any additional information below.
Compile error:
btree.h(1401) : error C2118: Negative subscript
That is the
COMPILE_ASSERT(
sizeof(key_compare_checker(key_compare_helper()(key_type(), key_type()))) ==
sizeof(big_),
key_comparison_function_must_return_bool);
Original issue reported on code.google.com by [email protected]
on 22 Dec 2013 at 3:49
What steps will reproduce the problem?
1. Compile sources
2. Run included test
What is the expected output? What do you see instead?
The test will crash.
What version of the product are you using? On what operating system?
cpp-btree 1.0.1 on MacOS X 10.7.5 , i686-apple-darwin11-llvm-g++-4.2
Please provide any additional information below.
Similar crash will happen if I load with some values and call clear method or
assign empty btree to full btree.
Output of the debugger is:
This GDB was configured as "x86_64-apple-darwin"...Reading symbols for shared
libraries ...... done
(gdb) run
Starting program: /Users/voicegroup/Documents/prog/btree/bin/btree_test
Reading symbols for shared libraries +++++......................... done
Running main() from gtest_main.cc
[==========] Running 52 tests from 1 test case.
[----------] Global test environment set-up.
[----------] 52 tests from Btree
[ RUN ] Btree.set_int32_32
sorted: fullness=1.00 overhead=6.03 bytes-per-value=10.03
Program received signal EXC_BAD_ACCESS, Could not access memory.
Reason: KERN_INVALID_ADDRESS at address: 0x0000000000000080
btree::btree<btree::btree_set_params<int, std::less<int>, std::allocator<int>,
32> >::assign (this=0x7fff5fbff0a8, x=@0x7fff5fbff758) at btree_test.cc:1864
Line number 1864 out of range; btree_test.cc has 270 lines.
(gdb) bt
#0 btree::btree<btree::btree_set_params<int, std::less<int>,
std::allocator<int>, 32> >::assign (this=0x7fff5fbff0a8, x=@0x7fff5fbff758) at
btree_test.cc:1864
#1 0x0000000100072d06 in btree::base_checker<btree::btree_set<int,
std::less<int>, std::allocator<int>, 32>, std::set<int, std::less<int>,
std::allocator<int> > >::base_checker (this=0x7fff5fbff0a8, x=@0x7fff5fbff758)
at btree.h:1746
#2 0x00000001001d4549 in
btree::DoTest<btree::unique_checker<btree::btree_set<int, std::less<int>,
std::allocator<int>, 32>, std::set<int, std::less<int>, std::allocator<int> >
>, int> (name=0x7fff5fbff730 "???_?", b=0x7fff5fbff730, values=@0x7fff5fbff730)
at btree_test.h:412
#3 0x00000001003a2aba in btree::BtreeTest<btree::btree_set<int,
std::less<int>, std::allocator<int>, 32>, std::set<int, std::less<int>,
std::allocator<int> > > () at btree_test.h:810
#4 0x00000001000034b0 in TestBody (this=0x1004764f6) at btree_test.cc:27
#5 0x00000001006c7357 in
testing::internal::HandleSehExceptionsInMethodIfSupported<testing::Test, void>
() at /Users/voicegroup/Documents/prog/btree/gtest-1.7.0/src/gtest.cc:2114
#6 0x00000001006c7357 in
testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>
(object=0x100805960, location=0x1006d6233 "the test body") at gtest-all.cc:1864
#7 0x00000001006bdc48 in testing::Test::Run (this=0x100805960) at gtest.cc:2151
#8 0x00000001006bfe3a in testing::TestInfo::Run (this=0x7fff5fbff920) at
gtest.cc:2326
#9 0x00000001006bffd3 in testing::TestCase::Run (this=0x100801900) at
gtest.cc:2444
#10 0x00000001006bd267 in testing::internal::UnitTestImpl::RunAllTests
(this=0x100801600) at gtest.cc:4315
#11 0x00000001006c6ed7 in
testing::internal::HandleSehExceptionsInMethodIfSupported<testing::internal::Uni
tTestImpl, bool> () at
/Users/voicegroup/Documents/prog/btree/gtest-1.7.0/src/gtest.cc:2114
#12 0x00000001006c6ed7 in
testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTe
stImpl, bool> (object=0x100801600, location=0x1006d5f80 "auxiliary test code
(environments or event listeners)") at gtest-all.cc:1864
#13 0x00000001006bcee8 in testing::UnitTest::Run (this=0x1006e2680) at
gtest.cc:3929
#14 0x00000001006a4e24 in main (argc=1, argv=0x7fff5fbff758) at gtest_main.cc:37
Original issue reported on code.google.com by [email protected]
on 27 Sep 2013 at 10:17
Compiling with: clang version 3.3 (trunk 173428)
Original issue reported on code.google.com by [email protected]
on 8 Feb 2013 at 11:23
Attachments:
A bug report mentioned that performance really was better for them, for their
workload, with >= 256 values per node. So I did this, ...
Original issue reported on code.google.com by [email protected]
on 14 Dec 2011 at 6:27
The btree implementations are currently missing the C++11 STL interface methods
like `at`. As this data structure should conform to STL, it should conform to
the latest version of that library.
Original issue reported on code.google.com by [email protected]
on 28 Mar 2013 at 4:11
OCD apostrophe correction ("it's" == "it is").
Original issue reported on code.google.com by [email protected]
on 1 Feb 2013 at 7:49
Attachments:
Hi, All, I made some changes for old gcc:
* Add a btree_config.h
* Config type_traits according to whether c++11 is support and enabled by
compiler.
* Allow user define size_type to be size_t, which make the size() interface of
btree containers compatible with STL totally.
* Remove dependency of the __COUNTER__ macro in bench test, which was
introduced since gcc 4.3, make cpp-btree compile with older compiler.
Tested on gcc 4.1.2 & 4.7.2, w/ & w/o c++11 enabled.
Original issue reported on code.google.com by chen3feng
on 8 Apr 2013 at 5:00
Attachments:
Branch name:
Purpose of code changes on this branch:
Fixed a problem report.
When reviewing my code changes, please focus on:
FYI, mostly.
After the review, I'll merge this branch into:
/trunk
Original issue reported on code.google.com by [email protected]
on 13 Dec 2011 at 6:50
What steps will reproduce the problem?
auto range = duplicates.equal_range(query_ids_temp[i]);
for (auto it = range.first; it != range.second; ++it) {
std::vector<unsigned int>::iterator pos = std::find(deleted_queries.begin(), deleted_queries.end(), it->second);
if (pos != deleted_queries.end()) {
duplicates.erase(it);
deleted_queries.erase(pos);
} else {
query_ids.push_back(it->second);
}
}
The error seems to be the it->second
What is the expected output? What do you see instead?
In file included from ref_impl/../include/btree_map.h:31:0,
from ref_impl/core.cpp:48:
ref_impl/../include/btree.h: In instantiation of
‘btree::btree_node<Params>::reference btree::btree_node<Params>::value(int)
[with Params = btree::btree_map_params<unsigned int, unsigned int,
std::less<unsigned int>, std::allocator<std::pair<const unsigned int, unsigned
int> >, 256>; btree::btree_node<Params>::reference = std::pair<const unsigned
int, unsigned int>&]’:
ref_impl/../include/btree.h:809:33: required from
‘btree::btree_iterator<Node, Reference, Pointer>::pointer
btree::btree_iterator<Node, Reference, Pointer>::operator->() const [with Node
= btree::btree_node<btree::btree_map_params<unsigned int, unsigned int,
std::less<unsigned int>, std::allocator<std::pair<const unsigned int, unsigned
int> >, 256> >; Reference = std::pair<const unsigned int, unsigned int>&;
Pointer = std::pair<const unsigned int, unsigned int>*;
btree::btree_iterator<Node, Reference, Pointer>::pointer = std::pair<const
unsigned int, unsigned int>*]’
ref_impl/core.cpp:539:106: required from here
What version of the product are you using? On what operating system?
Version 1.0.1,
Ubuntu 12.04
Please provide any additional information below.
Original issue reported on code.google.com by [email protected]
on 21 Mar 2013 at 3:16
Simplified, thanks.
Original issue reported on code.google.com by [email protected]
on 14 Dec 2011 at 9:49
See summary. This is not required for ordinary std::set.
To reproduce:
$ cat bug.cpp
#include "btree_set.h"
#include <set>
class Foo {
int bar_;
public:
explicit Foo(int bar): bar_(bar) {}
};
int main(void) {
btree::btree_set<Foo> a;
std::set<Foo> b;
return 0;
}
$ clang++ bug.cpp -std=c++11 -stdlib=libc++
In file included from bug.cpp:1:
In file included from ./btree_set.h:27:
./btree.h:1402:55: error: no matching constructor for initialization of
'key_type' (aka 'Foo')
sizeof(key_compare_checker(key_compare_helper()(key_type(), key_type()))) ==
^
./btree.h:161:31: note: expanded from macro 'COMPILE_ASSERT'
typedef CompileAssert<(bool(expr))> msg[bool(expr) ? 1 : -1]
^
./btree_container.h:32:20: note: in instantiation of template class
'btree::btree<btree::btree_set_params<Foo, std::__1::less<Foo>,
std::__1::allocator<Foo>, 256>>' requested here
typedef typename Tree::params_type params_type;
^
./btree_container.h:147:39: note: in instantiation of template class
'btree::btree_container<btree::btree<btree::btree_set_params<Foo,
std::__1::less<Foo>, std::__1::allocator<Foo>, 256>>>' requested here
class btree_unique_container : public btree_container<Tree> {
^
./btree_set.h:37:26: note: in instantiation of template class
'btree::btree_unique_container<btree::btree<btree::btree_set_params<Foo,
std::__1::less<Foo>, std::__1::allocator<Foo>, 256>>>' requested here
class btree_set : public btree_unique_container<
^
bug.cpp:11:25: note: in instantiation of template class 'btree::btree_set<Foo,
std::__1::less<Foo>, std::__1::allocator<Foo>, 256>' requested here
btree::btree_set<Foo> a;
^
bug.cpp:7:12: note: candidate constructor not viable: requires 1 argument, but
0 were provided
explicit Foo(int bar): bar_(bar) {}
^
bug.cpp:4:7: note: candidate constructor (the implicit copy constructor) not
viable: requires 1 argument, but 0 were provided
class Foo {
^
bug.cpp:4:7: note: candidate constructor (the implicit move constructor) not
viable: requires 1 argument, but 0 were provided
1 error generated.
$ clang -v
Apple clang version 4.0 (tags/Apple/clang-421.0.60) (based on LLVM 3.1svn)
Target: x86_64-apple-darwin11.4.2
Thread model: posix
Original issue reported on code.google.com by [email protected]
on 14 Feb 2013 at 5:46
I study the code, and find the only C++11 feature used is <type_traits>.
For the lower version of gcc, <tr1/type_traits> can be use to instead.
Do the team have interesting to support pre-c++11 compilers?
Original issue reported on code.google.com by chen3feng
on 7 Apr 2013 at 4:13
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.