cetium/cpp-btree

Automatically exported from code.google.com/p/cpp-btree

cpp-btree's Issues

Warnings/Compile Errors Generated on VC11

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

COMPILE_ASSERT problem

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

COMPILE_ASSERT problem

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

Patch to support pre-c++11 compiler

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:

• cpp-btree-1.0.1-non-c++11.patch

Suppress compiler warning

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:

• fmt.diff

btree requires key to be Default Constructibe

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

Please consider proposing btree to C++17

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

Does not compile Ubuntu

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

Code review request

Simplified, thanks.

Original issue reported on code.google.com by [email protected] on 14 Dec 2011 at 9:49

Doesn't compile on Windows & Visual Studio, missing ssize_t

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

Missing the include of <stdint.h> in btree.h

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

Patch for /README

Point project to GitHub

Original issue reported on code.google.com by piperchester on 23 Mar 2015 at 2:40

Attachments:

• README.patch

Support C++11 STL interface

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

Can cpp-btree support the compilers without C++11?

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

Why the size_type is ssize_t but not size_t?

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

Code review request

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

Patch for /btree_map.h

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:

• btree_map.h.patch

NDEBUG defined in btree.h

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

Typo in the comparator constructor code

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

[deleted issue]

[deleted issue]

Building failure with gcc 4.5.1

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

compilation on non-c++2011 & safe_btree_multiset : done

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:

• type_traits_hm
• btree.h
• safe_btree_multiset.h
• curve.JPG

Code review request

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

Many strict-aliasing warnings

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:

• btree.h.diff

Crash on test

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