mavam / libbf Goto Github PK

View Code? Open in Web Editor NEW

352.0 352.0 89.0 2.52 MB

:dart: Bloom filters for C++11

Home Page: http://mavam.github.io/libbf

License: BSD 3-Clause "New" or "Revised" License

C++ 96.52% CMake 3.48%

bloom-filter synopsis

libbf's People

Contributors

Stargazers

Watchers

Forkers

sunilnandihalli lemonhall soumyabasu brianhou javarange languagefun czinsane simonzhangsm mborger claudiouzelac graydon meng-li zcourts scott-he emaxerrno kamikat ghais giacobenin mingliwu ychecourseproject enobayram edenzik nicolacdnll kuitycorp xiehuc caetanosauer fooc tangshiqiang ryderhwang christopherwilks wanyisunflower amallia amosbird ptuls 5cs enascimento redfieldcd adityapai2398 chineshboy hmyan90 litao91 jingnanjia thandirk rastaban beaulian feiyunwill yanghonggang ekg polymedia stmotw jervenbolleman kaizhang15 sunnyszy i-chaochen deiiiiii kramelec vishal2241 juno119 knl lrobidou guoxiangzhou talrasha xianglingzhang booknouse varchar-io zqyi unilang 5gapp jacyhust vbirds zhaoyf22 pongstorn-amd ishrahussain eddiewdy piusayowale qingzma artpaul yujie-cui dksan23 bkille gerhobbelt cyhwang1997 jingtao8a tnhlng tzphh

libbf's Issues

Incorrect header inclusion

Hello,

I have some trouble installing libbf. After doing:

./configure
make
make install

libbf is installed here:

> tree /usr/local/include/            
/usr/local/include/
├── bf
│   ├── all.hpp
│   ├── bitvector.hpp
│   ├── bloom_filter
│   │   ├── a2.hpp
│   │   ├── basic.hpp
│   │   ├── bitwise.hpp
│   │   ├── counting.hpp
│   │   └── stable.hpp
│   ├── bloom_filter.hpp
│   ├── counter_vector.hpp
│   ├── h3.hpp
│   ├── hash.hpp
│   ├── object.hpp
│   └── wrap.hpp

I cant find the file bf.h specified in the current readme.
In fact :

#include <bf.h>

int main(){
    bf::bloom_filter* h;
    return 0;
}

does not work, neither do :

#include <bf/bf.h>

int main(){
    bf::bloom_filter* h;
    return 0;
}

However,

#include <bf/all.hpp>

int main(){
    bf::bloom_filter* h;
    return 0;
}

does work, as specified in #32

1 - Should I open a merge request to update the readme ?

I have to install a project that uses libbf, and that project does:
#include <bf.h>
But it does not specify which version of libbf was used.

2 - Do you know if a previous version of libbf could be installed by including bf.h ? In such case, which version is it ?

I also used libbf in one of my project, and it worked great ! Thank you for your library.

Possible performance improvement by replacing % (modulo) with multiply + shift

This is described in http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/

(I'm looking for a fast Bloom filter implementation, and found your implementation uses modulo which is a bit slow.)

Possible performance issue when performing look-ups for non-existent entries

In the method 'basic_bloom_filter::lookup' digests are computed first then subsequently quantized and looked up in the filter.

https://github.com/mavam/libbf/blob/master/src/bf/bloom_filter/basic.cc#L60

Implementations typically for efficiency purposes will have the look-up perform a trivial exit on the first digest that encounters a miss - as computing the hash may cost more than the lookup itself.

This will probably only be a problem when there is a larger expectation for queries/look-ups of non-existent entries versus present/existent ones.

aux is a reserved file name on windows

Please consider renaming the aux directory, as that creates a folder that is comically difficult to delete on a windows machine.

from https://docs.microsoft.com/en-us/windows/desktop/FileIO/naming-a-file

Do not use the following reserved names for the name of a file:

CON, PRN, AUX, NUL, COM1, COM2, COM3, COM4, COM5, COM6, COM7, COM8, COM9, LPT1, LPT2, LPT3, LPT4, LPT5, LPT6, LPT7, LPT8, and LPT9. Also avoid these names followed immediately by an extension; for example, NUL.txt is not recommended. For more information, see Namespaces.

GCC: Version 10.0.1 "runtime_error’ is not a member of ‘std" in hash.cpp

During building with gcc 10.0.1

src/hash.cpp:14:16: error: ‘runtime_error’ is not a member of ‘std’
   14 |     throw std::runtime_error("object too large");
      |                ^~~~~~~~~~~~~

Fixed by adding the line

#include <stdexcept>

in hash.ccp.

I am not really sure that is really the correct thing.

pthread not required in ./configure

Getting this error during make after configure succeeded:

Linking CXX executable bf-test
CMakeFiles/bf-test.dir/tests.cpp.o: In function `caf::test::watchdog::start(int)':
tests.cpp:(.text+0x5cd2): undefined reference to `pthread_create'
collect2: error: ld returned 1 exit status

(Travis CI Ubuntu/Linaro 4.6.3-1ubuntu5 w/ g++4.9)

Failed Unit Test for Spectral_MI bloom filter.

#0  0x00007ffff6f9a445 in raise () from /lib/x86_64-linux-gnu/libc.so.6
#1  0x00007ffff6f9dbab in abort () from /lib/x86_64-linux-gnu/libc.so.6
#2  0x00007ffff6f9310e in ?? () from /lib/x86_64-linux-gnu/libc.so.6
#3  0x00007ffff6f931b2 in __assert_fail () from /lib/x86_64-linux-gnu/libc.so.6
#4  0x0000000000432dff in bf::fixed_width<unsigned char, std::allocator<unsigned char> >::increment (this=0x7fffffffd2b8, cell=6658256)
    at /home/soumya/libbf/src/store.h:81
#5  0x00000000004373de in bf::detail::spectral::minimum_increase<char [9], bf::core<bf::fixed_width<unsigned char, std::allocator<unsigned char> >, bf::default_hashing<bf::basic_hasher, bf::fixed_seed<42u> >, bf::no_partitioning> > (x=..., core=...)
    at /home/soumya/libbf/src/detail/spectral.h:90
#6  0x0000000000434785 in bf::spectral_mi<bf::core<bf::fixed_width<unsigned char, std::allocator<unsigned char> >, bf::default_hashing<bf::basic_hasher, bf::fixed_seed<42u> >, bf::no_partitioning> >::add<char [9]> (this=0x7fffffffd2b0, x=...)
    at /home/soumya/libbf/src/bloom_filter_spectral.h:27
#7  0x000000000042bd5b in spectral_mi_bloom_filter::test_method (
    this=0x7fffffffd32f) at /home/soumya/libbf/test/unit.cc:169
#8  0x000000000042bcdb in spectral_mi_bloom_filter_invoker ()
    at /home/soumya/libbf/test/unit.cc:165
#9  0x0000000000443906 in boost::unit_test::ut_detail::invoker<boost::unit_test::ut_detail::unused>::invoke<void (*)()> (this=0x7fffffffd38f, 
    f=@0x654c28: 0x42bcc7 <spectral_mi_bloom_filter_invoker()>)
    at /usr/include/boost/test/utils/callback.hpp:56
#10 0x00000000004437a0 in boost::unit_test::ut_detail::callback0_impl_t<boost::unit_test::ut_detail::unused, void (*)()>::invoke (this=0x654c20)
    at /usr/include/boost/test/utils/callback.hpp:89
#11 0x00007ffff7b9b2f1 in operator() (this=<optimized out>)
    at ./boost/test/utils/callback.hpp:118
#12 operator() (this=<optimized out>) at ./boost/test/impl/unit_test_monitor.ipp:41
#13 invoke<boost::unit_test::{anonymous}::zero_return_wrapper_t<boost::unit_test::callback0<> > > (f=..., this=<optimized out>) at ./boost/test/utils/callback.hpp:42
#14 boost::unit_test::ut_detail::callback0_impl_t<int, boost::unit_test::{anonymous}::zero_return_wrapper_t<boost::unit_test::callback0<boost::unit_test::ut_detail::unused> > >::invoke(void) (this=<optimized out>) at ./boost/test/utils/callback.hpp:89
#15 0x00007ffff7b7f4fe in operator() (this=0x7fffffffdec0)
    at ./boost/test/utils/callback.hpp:118
#16 do_invoke<boost::scoped_ptr<boost::detail::translate_exception_base>, boost::unit_test::callback0<int> > (F=..., tr=...)
    at ./boost/test/impl/execution_monitor.ipp:281
#17 boost::execution_monitor::catch_signals (this=0x7ffff7dd8980, F=...)
    at ./boost/test/impl/execution_monitor.ipp:885
#18 0x00007ffff7b7fdfb in boost::execution_monitor::execute (this=0x7ffff7dd8980, 
    F=...) at ./boost/test/impl/execution_monitor.ipp:1211
#19 0x00007ffff7b9b3eb in boost::unit_test::unit_test_monitor_t::execute_and_translate (this=0x7ffff7dd8980, tc=...) at ./boost/test/impl/unit_test_monitor.ipp:69
#20 0x00007ffff7b868a1 in boost::unit_test::framework_impl::visit (
    this=0x7ffff7dd88c0, tc=...) at ./boost/test/impl/framework.ipp:156
#21 0x00007ffff7bb8993 in boost::unit_test::traverse_test_tree (suite=..., V=...)
    at ./boost/test/impl/unit_test_suite.ipp:207
#22 0x00007ffff7b81fd1 in boost::unit_test::framework::run (id=1, 
    continue_test=<optimized out>) at ./boost/test/impl/framework.ipp:442
#23 0x00007ffff7b9a82f in boost::unit_test::unit_test_main (
    init_func=<optimized out>, argc=<optimized out>, argv=<optimized out>)
    at ./boost/test/impl/unit_test_main.ipp:185
#24 0x00000000004252ce in main (argc=1, argv=0x7fffffffe298)
    at /usr/include/boost/test/unit_test.hpp:59

This is the backtrace for the failed spectral_mi bloom filter test on my operating system (Ubuntu 12.04). Let me know if you need any more information.

Wrapping for Python 3

Hi,
First of all, thanks for the great work!

Have you considered making a Python wrapper around the library? If not, would you mind if I paraphrase (and reference) your code and package it in a separate python module? The dependency on threading would need to be removed as well as C++11, I suppose.

Error while building on windows using MSVC

On Windows, this package requires #include in bitvector.cpp to properly call std::min.

I've created a pull request to fix this: #47

Path with space

Hi!
if you clone the project in a directory where there is a space in the name
you have an error when you type:
CXX=g++ ./configure --prefix=/usr/local/lib/

so you should clone to another directory

make error

How can I sovle this problem?
CXX=g++ version 4.73
boost version 1.43

Remove dependency on Threads

Currently, threads are only used for testing framework (and not testing cases themselves). IMO, it's better to shift responsibility for running tests in parallel to the testing environment (make test -j8) and decouple it from the testing code.

Following a previous issue, #34:

I would also prefer a simple solution that doesn't require Threads. I've written a small unit test framework for CAF. With minor modifications, it's probably a reasonable drop-in replacement.

Is there a reason not to use something more common/standard like https://github.com/catchorg/Catch2? Catch2 is header-only and can be included directly into the repository so it adds no extra installation steps.

N3980: a more flexible way of hashing

The next version should have a more flexible way of hashing according to N3980, which @mavam started in topic/n3980.

This issue will help us discussing about it.

make test failure

root@ubuntu:/bloom_filter_lib/libbf# ./configure
Build Directory : build
Source Directory: /root/bloom_filter_lib/libbf
-- Looking for include file pthread.h
-- Looking for include file pthread.h - found
-- Looking for pthread_create
-- Looking for pthread_create - not found
-- Looking for pthread_create in pthreads
-- Looking for pthread_create in pthreads - not found
-- Looking for pthread_create in pthread
-- Looking for pthread_create in pthread - found
-- Found Threads: TRUE
-- Configuring done
-- Generating done
-- Build files have been written to: /root/bloom_filter_lib/libbf/build
root@ubuntu:/bloom_filter_lib/libbf# make && make test
make[1]: Entering directory /root/bloom_filter_lib/libbf/build' make[2]: Entering directory /root/bloom_filter_lib/libbf/build'
make[3]: Entering directory /root/bloom_filter_lib/libbf/build' Scanning dependencies of target libbf make[3]: Leaving directory /root/bloom_filter_lib/libbf/build'
[ 72%] Built target libbf
make[3]: Entering directory /root/bloom_filter_lib/libbf/build' make[3]: Leaving directory /root/bloom_filter_lib/libbf/build'
[ 81%] Built target bf-test
make[3]: Entering directory /root/bloom_filter_lib/libbf/build' make[3]: Leaving directory /root/bloom_filter_lib/libbf/build'
[100%] Built target bf
make[2]: Leaving directory /root/bloom_filter_lib/libbf/build' make[1]: Leaving directory /root/bloom_filter_lib/libbf/build'
make[1]: Entering directory `/root/bloom_filter_lib/libbf/build'
Running tests...
Test project /root/bloom_filter_lib/libbf/build
Start 1: unit
Could not find executable /root/bloom_filter_lib/libbf/build/test/bf-test
Looked in the following places:
/root/bloom_filter_lib/libbf/build/test/bf-test
/root/bloom_filter_lib/libbf/build/test/bf-test
/root/bloom_filter_lib/libbf/build/test/Release/bf-test
/root/bloom_filter_lib/libbf/build/test/Release/bf-test
/root/bloom_filter_lib/libbf/build/test/Debug/bf-test
/root/bloom_filter_lib/libbf/build/test/Debug/bf-test
/root/bloom_filter_lib/libbf/build/test/MinSizeRel/bf-test
/root/bloom_filter_lib/libbf/build/test/MinSizeRel/bf-test
/root/bloom_filter_lib/libbf/build/test/RelWithDebInfo/bf-test
/root/bloom_filter_lib/libbf/build/test/RelWithDebInfo/bf-test
/root/bloom_filter_lib/libbf/build/test/Deployment/bf-test
/root/bloom_filter_lib/libbf/build/test/Deployment/bf-test
/root/bloom_filter_lib/libbf/build/test/Development/bf-test
/root/bloom_filter_lib/libbf/build/test/Development/bf-test
root/bloom_filter_lib/libbf/build/test/bf-test
root/bloom_filter_lib/libbf/build/test/bf-test
root/bloom_filter_lib/libbf/build/test/Release/bf-test
root/bloom_filter_lib/libbf/build/test/Release/bf-test
root/bloom_filter_lib/libbf/build/test/Debug/bf-test
root/bloom_filter_lib/libbf/build/test/Debug/bf-test
root/bloom_filter_lib/libbf/build/test/MinSizeRel/bf-test
root/bloom_filter_lib/libbf/build/test/MinSizeRel/bf-test
root/bloom_filter_lib/libbf/build/test/RelWithDebInfo/bf-test
root/bloom_filter_lib/libbf/build/test/RelWithDebInfo/bf-test
root/bloom_filter_lib/libbf/build/test/Deployment/bf-test
root/bloom_filter_lib/libbf/build/test/Deployment/bf-test
root/bloom_filter_lib/libbf/build/test/Development/bf-test
root/bloom_filter_lib/libbf/build/test/Development/bf-test
Unable to find executable: /root/bloom_filter_lib/libbf/build/test/bf-test
1/1 Test #1: unit .............................***Not Run 0.00 sec

0% tests passed, 1 tests failed out of 1

Total Test time (real) = 0.00 sec

The following tests FAILED:
1 - unit (Not Run)
Errors while running CTest
make[1]: *** [test] Error 8
make[1]: Leaving directory `/root/bloom_filter_lib/libbf/build'
make: *** [test] Error 2
root@ubuntu:~/bloom_filter_lib/libbf#

Conan package

Hi,
Have you considered making a conan package?

If not, would you mind if we make one? In that case, could you please bump the version to 1.0.0 so that we can pin it down?

Thanks!

bits.size % digests.size() assert error make this library not friendly.

When using bloom library, the false positive possibility and the capacity is use-defined. however, this library make the choices of this two variables not easy. The library will output a assertion error if bits.size % digests.size() is not zero. Maybe a recommendation for how to choosing this two value is necessary.

Export the filter

First of all nice and well designed library!

I am looking to add a export() method.
From my test looks like is enough to just move

bits_.data()
and
num_bits_

For this "test" I have just moved as public
bitvector bits_;
and
size_type num_bits_;
std::vector<block_type> bits_;

If is ok I will prepare a patch to add serialize / unserialize function.
They will be something like

std::string serialize();

bool unserialize(std::string raw)

The result "string" will be nothing more than sizeof(size_type) byte for the num_bits_ and all the remaining the content of bits_.data().

Eventually a checksum can be added, there is no need to have a base64 version, I don't think someone is going to copy paste a filter.

How can I add raw bytes, or non-null terminated strings?

Something like:

bf.add(64,buf);

where buf is something like char*, and 64 is the number of bytes pointed to by buf.

make test failure!

First, I add enable_language(C) to CMakeLists.txt to solve the problem as follow:

Build Directory : build
Source Directory: /root/libbf
-- Looking for include file pthread.h
CMake Error at /usr/share/cmake-2.8/Modules/CheckIncludeFiles.cmake:58 (try_compile):
  Unknown extension ".c" for file

    /root/libbf/build/CMakeFiles/CMakeTmp/CheckIncludeFiles.c

  try_compile() works only for enabled languages.  Currently these are:

    CXX

  See project() command to enable other languages.
Call Stack (most recent call first):
  /usr/share/cmake-2.8/Modules/FindThreads.cmake:39 (CHECK_INCLUDE_FILES)
  CMakeLists.txt:54 (find_package)


-- Looking for include file pthread.h - not found
-- Could NOT find Threads (missing:  Threads_FOUND) 
CMake Error at CMakeLists.txt:56 (message):
  Could not find system threading libraries


-- Configuring incomplete, errors occurred!
See also "/root/libbf/build/CMakeFiles/CMakeOutput.log".
See also "/root/libbf/build/CMakeFiles/CMakeError.log".

Second, I run make after ./configure
Then make test, but the error comes up:

make[1]: Entering directory `/root/libbf/build'
Running tests...
Test project /root/libbf/build
    Start 1: unit
1/1 Test #1: unit .............................***Failed    0.48 sec

0% tests passed, 1 tests failed out of 1

Total Test time (real) =   0.48 sec

The following tests FAILED:
      1 - unit (Failed)
Errors while running CTest
make[1]: *** [test] Error 8
make[1]: Leaving directory `/root/libbf/build'
make: *** [test] Error 2

My enviroment: gcc version 4.9.2,cmake version 2.8.12.2 and ubuntu 14.04

How can I fix it?
Thank you!

Failed Unit Tests

Running ./build/test/unit:

Running 11 test cases...
/Users/Soumya/College/ICSI/libbf/test/unit.cc:142: error in "basic_bloom_filter_counting": check b.count("corge") == 4 failed [3 != 4]
/Users/Soumya/College/ICSI/libbf/test/unit.cc:154: error in "stable_bloom_filter": check to_string(b) == "1101110011" failed [1110010001 != 1101110011]

*** 2 failures detected in test suite "Bloom filter unit test"

Running ./build/test/bf -h

bf(10761) malloc: *** error for object 0x10d2bbb60: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6

Segmentation fault when running in thread

I'm trying to use libbf in a multithreaded environment and it fails with a segmentation fault. I've managed to reproduce it in a minimalistic example with docker environment, here it is:

with_thread.cpp

#include "bf/bloom_filter/basic.hpp"
#include <iostream>
#include <thread>

void foo() {
  const bf::hasher h = bf::make_hasher(5, 0, true);
  const auto digests = h(bf::wrap(0));
  for (const auto &val : digests)
    std::cout << val << std::endl;
}

int main()
{
  std::cout << "foo() in main" << std::endl;
  foo();

  std::cout << "foo() in thread" << std::endl;
  std::thread first(foo);
  first.join();

  std::cout << "test completed" << std::endl;

  return 0;
}

Dockerfile

FROM alpine:3.11

COPY with_thread.cpp .

RUN apk update && apk add --no-cache nano mc g++ gdb valgrind git

RUN git clone https://github.com/mavam/libbf.git

RUN g++ with_thread.cpp -o with_thread -g libbf/src/*.cpp libbf/src/bloom_filter/*.cpp -I libbf

SHELL ["/bin/ash", "-c"]

Steps to reproduce

docker build --pull -f Dockerfile -t libbf_alpine .
docker run -it --rm libbf_alpine:latest /bin/ash
./with_thread

Result

foo() in main
0
0
0
0
0
foo() in thread
Segmentation fault

gdb backtrace

#0  0x00005586502aaac7 in bf::make_hasher (k=<error reading variable: Cannot access memory at address 0x7fad73d917e0>,
    seed=<error reading variable: Cannot access memory at address 0x7fad73d917d8>,
    double_hashing=<error reading variable: Cannot access memory at address 0x7fad73d917d4>) at libbf/src/hash.cpp:42
#1  0x00005586502a43ff in foo () at with_thread.cpp:6
#2  0x00005586502a5326 in std::__invoke_impl<void, void (*)()> (__f=@0x7fad73f62ae8: 0x5586502a43c9 <foo()>) at /usr/include/c++/9.2.0/bits/invoke.h:60
#3  0x00005586502a52ca in std::__invoke<void (*)()> (__fn=@0x7fad73f62ae8: 0x5586502a43c9 <foo()>) at /usr/include/c++/9.2.0/bits/invoke.h:95
#4  0x00005586502a5268 in std::thread::_Invoker<std::tuple<void (*)()> >::_M_invoke<0ul> (this=0x7fad73f62ae8) at /usr/include/c++/9.2.0/thread:244
#5  0x00005586502a5229 in std::thread::_Invoker<std::tuple<void (*)()> >::operator() (this=0x7fad73f62ae8) at /usr/include/c++/9.2.0/thread:251
#6  0x00005586502a51fe in std::thread::_State_impl<std::thread::_Invoker<std::tuple<void (*)()> > >::_M_run (this=0x7fad73f62ae0) at /usr/include/c++/9.2.0/thread:195
#7  0x00007fad73ea8045 in ?? () from /usr/lib/libstdc++.so.6
#8  0x00007fad73fb433e in ?? () from /lib/ld-musl-x86_64.so.1
#9  0x0000000000000000 in ?? ()

valgrind output

==45== Memcheck, a memory error detector
==45== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==45== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==45== Command: ./with_thread
==45==
foo() in main
0
0
0
0
0
foo() in thread
==45==
==45== Process terminating with default action of signal 11 (SIGSEGV)
==45==  Bad permissions for mapped region at address 0x4E567E8
==45==    at 0x110AC7: bf::make_hasher(unsigned long, unsigned long, bool) (hash.cpp:42)
==45==
==45== Process terminating with default action of signal 11 (SIGSEGV)
==45==  Bad permissions for mapped region at address 0x4E567A0
==45==    at 0x489613F: _vgnU_freeres (vg_preloaded.c:83)
==45==
==45== HEAP SUMMARY:
==45==     in use at exit: 74,027 bytes in 10 blocks
==45==   total heap usage: 15 allocs, 5 frees, 221,651 bytes allocated
==45==
==45== LEAK SUMMARY:
==45==    definitely lost: 0 bytes in 0 blocks
==45==    indirectly lost: 0 bytes in 0 blocks
==45==      possibly lost: 0 bytes in 0 blocks
==45==    still reachable: 74,027 bytes in 10 blocks
==45==         suppressed: 0 bytes in 0 blocks
==45== Rerun with --leak-check=full to see details of leaked memory
==45==
==45== For lists of detected and suppressed errors, rerun with: -s
==45== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

MSVC not supported?

Hi.
When I try to install it using MSVC compiler on windows it says: "Your C++ compiler does not support C++11."

Installation error

Command entered: ./configure --prefix=.
Output:

-- The CXX compiler identification is Clang 4.1.0
-- Check for working CXX compiler: /usr/bin/c++
-- Check for working CXX compiler: /usr/bin/c++ -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Boost version: 1.52.0
-- Found the following Boost libraries:
--   program_options
--   thread
--   system
--   unit_test_framework
-- Configuring done
-- Generating done
-- Build files have been written to: /Users/Soumya/College/ICSI/libbf/build

Command: make -j 4
Output:

Scanning dependencies of target bf
Scanning dependencies of target unit
[ 25%] Building CXX object test/CMakeFiles/unit.dir/unit.cc.o
[ 50%] [ 75%] [100%] Building CXX object test/CMakeFiles/bf.dir/bf.cc.o
Building CXX object test/CMakeFiles/bf.dir/configuration.cc.o
Building CXX object test/CMakeFiles/bf.dir/metrics.cc.o
In file included from /Users/Soumya/College/ICSI/libbf/test/configuration.cc:4:
In file included from /usr/local/include/boost/thread/thread.hpp:17:
In file included from /usr/local/include/boost/thread/pthread/thread_data.hpp:11:
In file included from /usr/local/include/boost/thread/locks.hpp:18:
In file included from /usr/local/include/boost/chrono/time_point.hpp:33:
/usr/local/include/boost/chrono/duration.hpp:353:49: error: constexpr function never produces a constant expression
        static BOOST_CHRONO_LIB_CONSTEXPR float lowest() BOOST_CHRONO_LIB_NOEXCEPT_OR_THROW
                                                ^
/usr/local/include/boost/chrono/duration.hpp:355:21: note: non-constexpr function 'max' cannot be used in a constant expression
            return -(std::numeric_limits<float>::max) ();
                    ^
/usr/bin/../lib/c++/v1/limits:443:43: note: declared here
    _LIBCPP_INLINE_VISIBILITY static type max() _NOEXCEPT {return __base::max();}
                                          ^
In file included from /Users/Soumya/College/ICSI/libbf/test/configuration.cc:4:
In file included from /usr/local/include/boost/thread/thread.hpp:17:
In file included from /usr/local/include/boost/thread/pthread/thread_data.hpp:11:
In file included from /usr/local/include/boost/thread/locks.hpp:18:
In file included from /usr/local/include/boost/chrono/time_point.hpp:33:
/usr/local/include/boost/chrono/duration.hpp:361:50: error: constexpr function never produces a constant expression
        static BOOST_CHRONO_LIB_CONSTEXPR double lowest() BOOST_CHRONO_LIB_NOEXCEPT_OR_THROW
                                                 ^
/usr/local/include/boost/chrono/duration.hpp:363:21: note: non-constexpr function 'max' cannot be used in a constant expression
            return -(std::numeric_limits<double>::max) ();
                    ^
/usr/bin/../lib/c++/v1/limits:443:43: note: declared here
    _LIBCPP_INLINE_VISIBILITY static type max() _NOEXCEPT {return __base::max();}
                                          ^
In file included from /Users/Soumya/College/ICSI/libbf/test/configuration.cc:4:
In file included from /usr/local/include/boost/thread/thread.hpp:17:
In file included from /usr/local/include/boost/thread/pthread/thread_data.hpp:11:
In file included from /usr/local/include/boost/thread/locks.hpp:18:
In file included from /usr/local/include/boost/chrono/time_point.hpp:33:
/usr/local/include/boost/chrono/duration.hpp:369:55: error: constexpr function never produces a constant expression
        static BOOST_CHRONO_LIB_CONSTEXPR long double lowest() BOOST_CHRONO_LIB_NOEXCEPT_OR_THROW
                                                      ^
/usr/local/include/boost/chrono/duration.hpp:371:21: note: non-constexpr function 'max' cannot be used in a constant expression
            return -(std::numeric_limits<long double>::max)();
                    ^
/usr/bin/../lib/c++/v1/limits:443:43: note: declared here
    _LIBCPP_INLINE_VISIBILITY static type max() _NOEXCEPT {return __base::max();}
                                          ^
3 errors generated.
make[3]: *** [test/CMakeFiles/bf.dir/configuration.cc.o] Error 1
make[3]: *** Waiting for unfinished jobs....
Linking CXX executable unit
[100%] Built target unit
make[2]: *** [test/CMakeFiles/bf.dir/all] Error 2
make[1]: *** [all] Error 2
make: *** [all] Error 2

There is an error when I use the CBF

Hi Matthias,
there is an error, when I use CBF in the test program in #7,btw,the previous test program using basic bf still works well now, and other bfs except CBF and spectral bf all can be used.
I tried 2 times to define a CBF:

bf::basic_bloom_filter b(0.8, 100,4);
bf::basic_bloom_filter b(make_hasher(3), 100,4);

Anyway, there is an error here as the following:

kevin@kevin--dc5850:~$ g++ -std=c++11 -I /usr/local/include/ -L /usr/local/lib  bftest.cc -o bftest.out -lbf
bftest.cc: In function ‘int main()’:
bftest.cc:6:42: error: no matching function for call to ‘bf::counting_bloom_filter::counting_bloom_filter(double, int, int)’
   bf::counting_bloom_filter b(0.8, 100, 4);
                                          ^
bftest.cc:6:42: note: candidate is:
In file included from /usr/local/include/bf.h:7:0,
                 from bftest.cc:2:
/usr/local/include/bf/bloom_filter/counting.h:24:3: note: bf::counting_bloom_filter::counting_bloom_filter(bf::hasher, size_t, size_t)
   counting_bloom_filter(hasher h, size_t cells, size_t width);
   ^
/usr/local/include/bf/bloom_filter/counting.h:24:3: note:   no known conversion for argument 1 from ‘double’ to ‘bf::hasher {aka std::function<std::vector<unsigned int>(const bf::object&)>}’

kevin@kevin--dc5850:~$ g++ -std=c++11 -I /usr/local/include/ -L /usr/local/lib  bftest.cc -o bftest.out -lbf
bftest.cc: In function ‘int main()’:
bftest.cc:6:41: error: ‘make_hasher’ was not declared in this scope
bf::basic_bloom_filter b(make_hasher(3), 100);
                                       ^
bftest.cc:6:41: note: suggested alternative:
In file included from /usr/local/include/bf/bloom_filter/basic.h:7:0,
                 from /usr/local/include/bf/bloom_filter/a2.h:4,
                 from /usr/local/include/bf.h:4,
                 from bftest.cc:2:
/usr/local/include/bf/hash.h:72:8: note:   ‘bf::make_hasher’
hasher make_hasher(size_t k, size_t seed = 0, bool double_hashing = false);
    ^

How can I use the counting bf here? Thanks

error about the largest size of entity added into bf

Hi Matthias,
when I use libbf in my own program about name lookup, I get a error about the largest size of entity added into bf.

terminate called after throwing an instance of 'std::runtime_error'
what(): object too large
Aborted (core dumped)

I checked my code, the reason for this error is about the size of entity(the length of the string) added into bf, when adding a long name(URI) into bf, this error will come up. How large entity can I add into bf here? How can I solve this problem? Any advice? Thanks.

latest tag release

any plan for a tag release latest codes ? thx.

Installation Error

$ clang++ -v
clang version 3.3
Target: x86_64-apple-darwin12.4.0
Thread model: posix

$ ./configure --prefix=.. --with-boost=..
-- The CXX compiler identification is Clang 3.3.0
-- Check for working CXX compiler: /usr/local/bin/clang++
-- Check for working CXX compiler: /usr/local/bin/clang++ -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Boost version: 1.53.0
-- Found the following Boost libraries:
--   unit_test_framework
-- Configuring done
-- Generating done
-- Build files have been written to: /Users/Soumya/College/Research/ICSI/libbf/build

$ make
Scanning dependencies of target libbf
[  8%] Building CXX object src/bf/CMakeFiles/libbf.dir/bitvector.cc.o
[ 16%] Building CXX object src/bf/CMakeFiles/libbf.dir/counter_vector.cc.o
/Users/Soumya/College/Research/ICSI/libbf/src/bf/counter_vector.cc:46:52: warning: 
      unused parameter 'value' [-Wunused-parameter]
bool counter_vector::decrement(size_t cell, size_t value)
                                                   ^
1 warning generated.
[ 25%] Building CXX object src/bf/CMakeFiles/libbf.dir/hash.cc.o
In file included from /Users/Soumya/College/Research/ICSI/libbf/src/bf/hash.cc:1:
In file included from /Users/Soumya/College/Research/ICSI/libbf/src/bf/hash.h:5:
/Users/Soumya/College/Research/ICSI/libbf/src/bf/h3.h:17:27: error: constexpr
      variable 'byte_range' must be initialized by a constant expression
  constexpr static size_t byte_range =
                          ^
/Users/Soumya/College/Research/ICSI/libbf/src/bf/hash.h:29:28: note: in
      instantiation of template class 'bf::h3<unsigned long, 36>' requested
      here
  h3<size_t, max_obj_size> h3_;
                           ^
/Users/Soumya/College/Research/ICSI/libbf/src/bf/h3.h:18:5: note: 
      non-constexpr function 'max' cannot be used in a constant expression
    std::numeric_limits<unsigned char>::max() + 1;
    ^
/usr/include/c++/v1/limits:435:43: note: declared here
    _LIBCPP_INLINE_VISIBILITY static type max() throw() {return __base::max();}
                                          ^
In file included from /Users/Soumya/College/Research/ICSI/libbf/src/bf/hash.cc:1:
In file included from /Users/Soumya/College/Research/ICSI/libbf/src/bf/hash.h:5:
/Users/Soumya/College/Research/ICSI/libbf/src/bf/h3.h:63:5: error: fields must
      have a constant size: 'variable length array in structure' extension will
      never be supported
  T bytes_[N][byte_range];
    ^
In file included from /Users/Soumya/College/Research/ICSI/libbf/src/bf/hash.cc:1:
In file included from /Users/Soumya/College/Research/ICSI/libbf/src/bf/hash.h:4:
In file included from /usr/include/c++/v1/functional:471:
/usr/include/c++/v1/memory:1729:55: error: no member named 'value' in
      'std::__1::is_empty<bf::default_hash_function>'
                                bool = is_empty<_T1>::value,
                                       ~~~~~~~~~~~~~~~^
/usr/include/c++/v1/memory:1748:44: note: in instantiation of default argument
      for '__libcpp_compressed_pair_switch<bf::default_hash_function,
      std::__1::allocator<bf::default_hash_function>, false>' required here
  ...class _T2, unsigned = __libcpp_compressed_pair_switch<_T1, _T2>::value>
                           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/v1/memory:1921:13: note: in instantiation of default argument
      for '__libcpp_compressed_pair_imp<bf::default_hash_function,
      std::__1::allocator<bf::default_hash_function> >' required here
    typedef __libcpp_compressed_pair_imp<_T1, _T2> base;
            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/v1/functional:997:35: note: in instantiation of template class
      'std::__1::__compressed_pair<bf::default_hash_function,
      std::__1::allocator<bf::default_hash_function> >' requested here
    __compressed_pair<_F, _Alloc> __f_;
                                  ^
/usr/include/c++/v1/functional:1253:13: note: in instantiation of template
      class 'std::__1::__function::__func<bf::default_hash_function,
      std::__1::allocator<bf::default_hash_function>, unsigned long
      (const bf::object &)>' requested here
        if (sizeof(_FF) <= sizeof(__buf_))
            ^
/Users/Soumya/College/Research/ICSI/libbf/src/bf/hash.cc:60:29: note: in
      instantiation of function template specialization
      'std::__1::function<unsigned long (const bf::object
      &)>::function<bf::default_hash_function>' requested here
    return double_hasher(k, std::move(h1), std::move(h2));
                            ^
In file included from /Users/Soumya/College/Research/ICSI/libbf/src/bf/hash.cc:1:
In file included from /Users/Soumya/College/Research/ICSI/libbf/src/bf/hash.h:4:
In file included from /usr/include/c++/v1/functional:471:
/usr/include/c++/v1/memory:1937:31: error: multiple overloads of
      '__compressed_pair' instantiate to the same signature 'void
      (_T1_param, _T2_param)'
    _LIBCPP_INLINE_VISIBILITY __compressed_pair(_T1_param __t1, _T2_param __t2)
                              ^
/usr/include/c++/v1/functional:997:35: note: in instantiation of template class
      'std::__1::__compressed_pair<bf::default_hash_function,
      std::__1::allocator<bf::default_hash_function> >' requested here
    __compressed_pair<_F, _Alloc> __f_;
                                  ^
/usr/include/c++/v1/functional:1253:13: note: in instantiation of template
      class 'std::__1::__function::__func<bf::default_hash_function,
      std::__1::allocator<bf::default_hash_function>, unsigned long
      (const bf::object &)>' requested here
        if (sizeof(_FF) <= sizeof(__buf_))
            ^
/Users/Soumya/College/Research/ICSI/libbf/src/bf/hash.cc:60:29: note: in
      instantiation of function template specialization
      'std::__1::function<unsigned long (const bf::object
      &)>::function<bf::default_hash_function>' requested here
    return double_hasher(k, std::move(h1), std::move(h2));
                            ^
/usr/include/c++/v1/memory:1933:40: note: previous declaration is here
    _LIBCPP_INLINE_VISIBILITY explicit __compressed_pair(_T1_param __t1...
                                       ^
In file included from /Users/Soumya/College/Research/ICSI/libbf/src/bf/hash.cc:1:
In file included from /Users/Soumya/College/Research/ICSI/libbf/src/bf/hash.h:4:
/usr/include/c++/v1/functional:1354:5: error: no matching conversion for
      functional-style cast from 'bf::default_hash_function' to
      'std::__1::function<unsigned long (const bf::object &)>'
    function(_STD::forward<_F>(__f)).swap(*this);
    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/Soumya/College/Research/ICSI/libbf/src/bf/hash.cc:66:14: note: in
      instantiation of function template specialization
      'std::__1::function<unsigned long (const bf::object
      &)>::operator=<bf::default_hash_function>' requested here
      fns[i] = default_hash_function(prng());
             ^
/usr/include/c++/v1/functional:1116:5: note: candidate constructor not viable:
      no known conversion from 'bf::default_hash_function' to 'nullptr_t' for
      1st argument
    function(nullptr_t) : __f_(0) {}
    ^
/usr/include/c++/v1/functional:1117:5: note: candidate constructor not viable:
      no known conversion from 'bf::default_hash_function' to 'const
      std::__1::function<unsigned long (const bf::object &)>' for 1st argument
    function(const function&);
    ^
/usr/include/c++/v1/functional:1118:5: note: candidate constructor not viable:
      no known conversion from 'bf::default_hash_function' to
      'std::__1::function<unsigned long (const bf::object &)>' for 1st argument
    function(function&&);
    ^
/usr/include/c++/v1/functional:1120:7: note: candidate template ignored:
      substitution failure [with _F = bf::default_hash_function]
      function(_F,
      ^
/usr/include/c++/v1/functional:1125:7: note: candidate constructor template not
      viable: requires 2 arguments, but 1 was provided
      function(allocator_arg_t, const _Alloc&) : __f_(0) {}
      ^
/usr/include/c++/v1/functional:1128:7: note: candidate constructor template not
      viable: requires 3 arguments, but 1 was provided
      function(allocator_arg_t, const _Alloc&, nullptr_t) : __f_(0) {}
      ^
/usr/include/c++/v1/functional:1130:7: note: candidate constructor template not
      viable: requires 3 arguments, but 1 was provided
      function(allocator_arg_t, const _Alloc&, const function&);
      ^
/usr/include/c++/v1/functional:1132:7: note: candidate constructor template not
      viable: requires 3 arguments, but 1 was provided
      function(allocator_arg_t, const _Alloc&, function&&);
      ^
/usr/include/c++/v1/functional:1134:7: note: candidate constructor template not
      viable: requires at least 3 arguments, but 1 was provided
      function(allocator_arg_t, const _Alloc& __a, _F __f,
      ^
/usr/include/c++/v1/functional:1114:5: note: candidate constructor not viable:
      requires 0 arguments, but 1 was provided
    function() : __f_(0) {}
    ^
5 errors generated.
make[3]: *** [src/bf/CMakeFiles/libbf.dir/hash.cc.o] Error 1
make[2]: *** [src/bf/CMakeFiles/libbf.dir/all] Error 2
make[1]: *** [all] Error 2
make: *** [all] Error 2

how to install the code in os x?

hello
i have install it in /usr/local/include, but i can not find the bf.h, i am sure the include path is correct, could you give me some help.
thanks!

Correction about counting bf.

Should we decrement count if one of bits are equal to zero?

make test failure

$ ./configure --prefix=/home/dbanschikov/libs/ --with-boost=/home/dbanschikov/libs/boost_1_59_0/include
Build Directory : build
Source Directory: /home/dbanschikov/git/libbf
-- Boost version: 1.59.0
-- Found the following Boost libraries:
--   unit_test_framework
-- Configuring done
-- Generating done
-- Build files have been written to: /home/dbanschikov/git/libbf/build
dbanschikov@dbanschikov:~/git/libbf$ make && make test
make[1]: Entering directory `/home/dbanschikov/git/libbf/build'
make[2]: Entering directory `/home/dbanschikov/git/libbf/build'
make[3]: Entering directory `/home/dbanschikov/git/libbf/build'
make[3]: Leaving directory `/home/dbanschikov/git/libbf/build'
make[3]: Entering directory `/home/dbanschikov/git/libbf/build'
[  9%] Building CXX object src/bf/CMakeFiles/libbf.dir/bitvector.cc.o
[ 18%] Building CXX object src/bf/CMakeFiles/libbf.dir/counter_vector.cc.o
[ 27%] Building CXX object src/bf/CMakeFiles/libbf.dir/hash.cc.o
[ 36%] Building CXX object src/bf/CMakeFiles/libbf.dir/bloom_filter/a2.cc.o
[ 45%] Building CXX object src/bf/CMakeFiles/libbf.dir/bloom_filter/basic.cc.o
[ 54%] Building CXX object src/bf/CMakeFiles/libbf.dir/bloom_filter/bitwise.cc.o
[ 63%] Building CXX object src/bf/CMakeFiles/libbf.dir/bloom_filter/counting.cc.o
[ 72%] Building CXX object src/bf/CMakeFiles/libbf.dir/bloom_filter/stable.cc.o
Linking CXX shared library libbf.so
make[3]: Leaving directory `/home/dbanschikov/git/libbf/build'
[ 72%] Built target libbf
make[3]: Entering directory `/home/dbanschikov/git/libbf/build'
make[3]: Leaving directory `/home/dbanschikov/git/libbf/build'
make[3]: Entering directory `/home/dbanschikov/git/libbf/build'
[ 81%] Building CXX object test/CMakeFiles/unit.dir/unit.cc.o
Linking CXX executable unit
make[3]: Leaving directory `/home/dbanschikov/git/libbf/build'
[ 81%] Built target unit
make[3]: Entering directory `/home/dbanschikov/git/libbf/build'
make[3]: Leaving directory `/home/dbanschikov/git/libbf/build'
make[3]: Entering directory `/home/dbanschikov/git/libbf/build'
[ 90%] Building CXX object test/bf/CMakeFiles/bf.dir/bf.cc.o
[100%] Building CXX object test/bf/CMakeFiles/bf.dir/configuration.cc.o
Linking CXX executable bf
make[3]: Leaving directory `/home/dbanschikov/git/libbf/build'
[100%] Built target bf
make[2]: Leaving directory `/home/dbanschikov/git/libbf/build'
make[1]: Leaving directory `/home/dbanschikov/git/libbf/build'
make[1]: Entering directory `/home/dbanschikov/git/libbf/build'
make[2]: Entering directory `/home/dbanschikov/git/libbf/build'
make[3]: Entering directory `/home/dbanschikov/git/libbf/build'
make[4]: Entering directory `/home/dbanschikov/git/libbf/build'
make[4]: Leaving directory `/home/dbanschikov/git/libbf/build'
[ 88%] Built target libbf
make[4]: Entering directory `/home/dbanschikov/git/libbf/build'
make[4]: Leaving directory `/home/dbanschikov/git/libbf/build'
[100%] Built target unit
make[4]: Entering directory `/home/dbanschikov/git/libbf/build'
make[4]: Leaving directory `/home/dbanschikov/git/libbf/build'
make[4]: Entering directory `/home/dbanschikov/git/libbf/build'
Running 13 test cases...
/home/dbanschikov/git/libbf/test/unit.cc(331): error: in "bloom_filter_stable": check bf.lookup("one fish") == 0 has failed [1 != 0]
/home/dbanschikov/git/libbf/test/unit.cc(332): error: in "bloom_filter_stable": check bf.lookup("two fish") == 2 has failed [3 != 2]
/home/dbanschikov/git/libbf/test/unit.cc(333): error: in "bloom_filter_stable": check bf.lookup("red fish") == 3 has failed [2 != 3]
/home/dbanschikov/git/libbf/test/unit.cc(334): error: in "bloom_filter_stable": check bf.lookup("blue fish") == 3 has failed [2 != 3]

*** 4 failures are detected in the test module "Bloom filter unit test"
make[4]: *** [test/CMakeFiles/test] Error 201
make[4]: Leaving directory `/home/dbanschikov/git/libbf/build'
make[3]: *** [test/CMakeFiles/test.dir/all] Error 2
make[3]: Leaving directory `/home/dbanschikov/git/libbf/build'
make[2]: *** [test/CMakeFiles/test.dir/rule] Error 2
make[2]: Leaving directory `/home/dbanschikov/git/libbf/build'
make[1]: *** [test] Error 2
make[1]: Leaving directory `/home/dbanschikov/git/libbf/build'
make: *** [test] Error 2

Avoid assert failure on bits_.size() % digests.size()

In my test using very large number (around 100M record) happens to have say
required_cells = 500.000
optimal_k = 7

So i just change required_cells to 500.003...
(required_cells += required_cells%optimal_k)

I have done some testing and seems that the property of the filter are kept also from what I understood from the underlying math there will be no problem at all, just a "waste" of 3 bit...

I do not have the code with me, if you think is a safe move I`ll send it.
Bye