Simple Useful Libraries: C++17/20 header-only dynamic bitset

dynamic_bitset

Actions Status Actions Status Build Status Build status codecov license

Simple Useful Libraries: C++17/20 header-only dynamic bitset

Requirements

To use this dynamic bitset, you will need a C++17 (or later) compliant compiler. If you use CMake and want to use the dynamic bitset as a subproject, you will need CMake 3.10 or later.

Usage sample

#include <sul/dynamic_bitset.hpp>
#include <iostream>
#include <random>

int main()
{
	// predefined bitset
	sul::dynamic_bitset<> bitset1(12, 0b0100010110111);
	std::cout << "bitset1     = " << bitset1 << std::endl;

	// random bitset
	std::minstd_rand rand(std::random_device{}());
	std::bernoulli_distribution dist;
	sul::dynamic_bitset<> bitset2;
	for(size_t i = 0; i < 12; ++i)
	{
		bitset2.push_back(dist(rand));
	}
	std::cout << "bitset2     = " << bitset2 << std::endl;

	std::cout << "common bits = " << (bitset1 & bitset2) << std::endl;
	return 0;
}

Possible output:

bitset1     = 100010110111
bitset2     = 001011011011
common bits = 000010010011

Test it on godbolt.org.

Optional dependency

Optionally, libpopcnt will be used to optimize the bits counting operations, if the header is available (__has_include(<libpopcnt.h>)) and DYNAMIC_BITSET_NO_LIBPOPCNT is not defined.

Integration

As it is a header-only library, the easiest way to integrate the sul::dynamic_bitset class in your project is to just copy the sul folder in your project sources. Optionally, if you also copy libpopcnt.h from libpopcnt, it will be used by default if it is available.

CMake integration

If you use CMake and want to use the dynamic bitset as a subproject, clone the repository (or add it as a git submodule) in a sub-folder of your project. Then, in your CMakeLists.txt add:

add_subdirectory(<path_to_dynamic_bitset_folder>)

It will define the dynamic_bitset target and the alias target sul::dynamic_bitset that you can use to add the folder containing dynamic_bitset.hpp to your project header folders. To do so, in your CMakeLists.txt add:

target_link_libraries(<your_project_target> PRIVATE sul::dynamic_bitset)

For example, a simple project with the repository as a git submodule in the extlibs folder, could have a CMakeLists.txt similar to this:

cmake_minimum_required(VERSION 3.10)
project(CoolProject LANGUAGES CXX)

add_executable(CoolProject main.cpp)
target_compile_features(CoolProject PRIVATE cxx_std_20)

add_subdirectory(extlibs/dynamic_bitset)
target_link_libraries(CoolProject PRIVATE sul::dynamic_bitset)

If you pulled the git submodule libpopcnt (in extlibs) and set the dynamic bitset CMake options DYNAMICBITSET_USE_LIBPOPCNT and DYNAMICBITSET_USE_LIBPOPCNT_SUBMODULE to ON(default values), the folder containing libpopcnt.h will also be added to the headers paths and libpopcnt will be used.

CMake options

Descriptions

  • DYNAMICBITSET_NO_NAMESPACE: Put the dynamic_bitset class in the global namespace instead of the sul namespace (not recommended)
  • DYNAMICBITSET_USE_LIBPOPCNT: Enable using libpopcnt for bits counting operations
  • DYNAMICBITSET_USE_LIBPOPCNT_SUBMODULE: Enable adding libpopcnt submodule to include paths (disable if your project already include libpopcnt)
  • DYNAMICBITSET_USE_STD_BITOPS: Enable using (if available) C++20 binary operations from the bit header
  • DYNAMICBITSET_USE_COMPILER_BUILTIN: Enable using (if available) compiler builtins (if using C++20 binary operations is disabled or not possible)
  • DYNAMICBITSET_BUILD_EXAMPLE: Enable building example for dynamic_bitset
  • DYNAMICBITSET_BUILD_TESTS: Enable building tests for dynamic_bitset
  • DYNAMICBITSET_BUILD_DOCS: Enable building documentation for dynamic_bitset
  • DYNAMICBITSET_FORMAT_TARGET: Enable generating a code formating target for dynamic_bitset
  • DYNAMICBITSET_HEADERS_TARGET_IDE: Enable generating a target with headers for ide for dynamic_bitset

Default values

Option Default value as top level project Default value as subdirectory
DYNAMICBITSET_NO_NAMESPACE OFF OFF
DYNAMICBITSET_USE_LIBPOPCNT ON ON
DYNAMICBITSET_USE_LIBPOPCNT_SUBMODULE ON ON
DYNAMICBITSET_USE_STD_BITOPS ON ON
DYNAMICBITSET_USE_COMPILER_BUILTIN ON ON
DYNAMICBITSET_BUILD_EXAMPLE ON OFF
DYNAMICBITSET_BUILD_TESTS ON OFF
DYNAMICBITSET_BUILD_DOCS ON OFF
DYNAMICBITSET_FORMAT_TARGET ON OFF
DYNAMICBITSET_HEADERS_TARGET_IDE ON OFF

Build tests, example, and documentation

The latest version of the documentation is available online here.

To build the tests, the example, and the documentation, git submodules are required, so don't forget to pull the submodules with the repository using --recursive:

$ git clone --recursive https://github.com/pinam45/dynamic_bitset.git

or if you have already cloned the repository:

$ git submodule update --init --recursive

The project uses CMake to build and define the options DYNAMICBITSET_BUILD_TESTS, DYNAMICBITSET_BUILD_EXAMPLE, and DYNAMICBITSET_BUILD_DOCS to enable the generation of the tests, example, and documentation targets, these option are enabled by default if the project is the master project (not included from another CMakeLists.txt with add_subdirectory).

Generating the documentation requires Doxygen 1.8.16 or later and is done by building the target dynamic_bitset_docs. For running the tests, build the dynamic_bitset_tests target and launch the tests using ctest.

See Running CMake and the ctest documentation for more information. On linux, a common way of doing this is:

$ mkdir cmake-build
$ cd cmake-build
$ cmake ..
$ cmake --build .
$ ctest --output-on-failure

On Windows, there is batch files available to configure a Visual Studio project in the ide folder.

License

dynamic_bitset is licensed under the MIT License:

Copyright © 2019 Maxime Pinard

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Comments
  • Binary (assignment) operations should not require the same `size()`

    Binary (assignment) operations should not require the same `size()`

    Binary (assignment) operations require the same size() of their operands (example). While this makes the implementation easy it enforces additional boilerplate code if the user wants to use differently-sized sets.

    The implementation will still be easy as the resulting bit set will either have the smaller or the larger of both size()s:

    In case of assignment operators I would expect the LHS operand to expand its size() to fit the RHS if required. Of course, the loops must only iterate to the minimum of both sizes.

    In case of binary operators it should be sufficient to swap LHS and RHS in order to avoid additional reallocations.

  • Atomic operations

    Atomic operations

    Hi, I want to use this library in an openmp program. Since different threads can set bits in a same block, I wonder how I can set a bit atomically without using a mutex?

  • Compatibility with fmt

    Compatibility with fmt

    I wonder if we can make sul::dynamic_bitset compatible with fmt (https://fmt.dev/latest/index.html, https://hackingcpp.com/cpp/libs/fmt.html). To do so, I think the missing is the begin/end accessing directly one bit with an iterator class (not for blocks) and an constructor with std::initializer_list< bool >. https://hackingcpp.com/cpp/libs/fmt.html#panel-fold68a

    Any thought on that?

  • push_back_block

    push_back_block

    To simplify serialization with json I use on my side a push_back_block:

    constexpr void dynamic_bitset<Block, Allocator>::push_back_block(Block blockValue)
    {
    	m_blocks.push_back(blockValue);
    }
    

    Binary serialization used .data(); for json 'for each block' save an uint32 or uint64 based on internal blocktype

  • Missing .data() for binary serialization

    Missing .data() for binary serialization

    Very cool,

    I'm using it on my side with minor modification:

    constexpr std::byte* data()
    {
    	return reinterpret_cast<std::byte*>(&m_blocks[0]);
    }
    constexpr std::byte const* data() const
    {
    	return reinterpret_cast<std::byte const*>(&m_blocks[0]);
    }
    

    Which is on my side convenient for binary serialization.

  • gdb segmentation fault

    gdb segmentation fault

    When debugging code that uses dynamic_bitset with gdb I get a segmentation fault when I try to print a bitset.

    (gdb) print bitset[0]
    $1 = {m_block = @0xd, m_mask = 93825020145982}
    (gdb) print bitset
    $2 = {Segmentation fault 
    

    Also, how should I read the output of the first print?

  • performance?

    performance?

    The following is a comparison of different bitset implementations: https://cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf. It would be interesting to see a similar comparison with this library.

A simple single header 64 and 32 bit hash function using only add, sub, ror, and xor.
A simple single header 64 and 32 bit hash function using only add, sub, ror, and xor.

K-HASH A simple single header 64 bit hash function using only add, sub, ror, and xor. This a just general-purpose hash function for like making hash m

Jul 31, 2022
Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -l9wada

Lib9wada Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -l9wada Usage Compile the library with mak

Sep 12, 2022
Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -l9wada

LibC+ Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -lC+ Better than C, not as much as c++ Usage

Sep 12, 2022
A collection of basic data structures syntaxes, useful for competitive coding and placement exams
A collection of basic data structures syntaxes, useful for competitive coding and placement exams

Data-Structures A collection of basic data structures syntaxes, useful for competitive coding and placement exams 1. Array 2. Matrix 3. Linked List Si

Aug 8, 2021
Useful Algorithm in C

useful-algorithm Useful Algorithm in C Content Number System (Dec, Bin, Hex) Searching Algorithms (Linear, Bin, Jump, ...) Sort Algorithms (Quick, Mer

Mar 18, 2022
I have created this one to help myself keep my own learning record, anyways it will be great if someone finds it useful or One will modify my codes.

CPP-DSA I have created this one to help myself keep my own learning record, anyways it will be great if someone finds it useful or One will modify my

Dec 23, 2021
BladeBit - Fast Chia (XCH) RAM-only k32-only Plotter

BladeBit Chia Plotter A fast RAM-only, k32-only, Chia plotter. Requirements 416 GiB of RAM are required to run it, plus a few more megabytes for stack

Sep 15, 2022
Easy to use, header only, macro generated, generic and type-safe Data Structures in C
Easy to use, header only, macro generated, generic and type-safe Data Structures in C

C Macro Collections Easy to use, header only, macro generated, generic and type-safe Data Structures in C. Table of Contents Installation Contributing

Sep 21, 2022
nanoplan is a header-only C++11 library for search-based robot planning.
nanoplan is a header-only C++11 library for search-based robot planning.

nanoplan is a header-only C++11 library for search-based robot planning. The primary design goals are correctness, ease-of-use, and efficiency (in tha

May 17, 2022
a header-only, constexpr alternative to gperf for C++14 users

Frozen Header-only library that provides 0 cost initialization for immutable containers, fixed-size containers, and various algorithms. Frozen provide

Sep 15, 2022
A family of header-only, very fast and memory-friendly hashmap and btree containers.
A family of header-only, very fast and memory-friendly hashmap and btree containers.

The Parallel Hashmap Overview This repository aims to provide a set of excellent hash map implementations, as well as a btree alternative to std::map

Sep 21, 2022
C++14 header only result monad implementation

constexpr Either <S, E> C++14 header only result monad implementation. Features constexpr support 0 dependencies single header Status in development T

Oct 7, 2021
ring-span lite - A C++yy-like ring_span type for C++98, C++11 and later in a single-file header-only library

ring-span lite: A circular buffer view for C++98 and later Contents Example usage In a nutshell Dependencies Installation Synopsis Reported to work wi

Aug 23, 2022
Header-only compile time key-value map written in C++20.

C++ Static Map Header-only compile time key-value map written in C++20. Getting Started Simply add the files in your source and #include "@dir/Static_

Oct 19, 2021
Multi-Purpose Header-Only C Data Structures

USAGE These header files are meant to be a simple means of using datastructures in a C project. They are universally useable with any other C datatype

Jul 15, 2022
Step is a C++17, header-only library of STL-like algorithms and data structures
Step is a C++17, header-only library of STL-like algorithms and data structures

Step is a C++17, header-only library of STL-like algorithms and data structures. Installation git clone --depth 1 https://github.com/storm-ptr/step.gi

Sep 1, 2022
R :package: and header-only C++ library for geospatial space-division based compression and encoding
R :package: and header-only C++ library for geospatial space-division based compression and encoding

spress spress provides utilities for encoding and compressing geospatial objects, such as sf objects. Installation This package requires C++11 for com

Dec 9, 2021
R :package: and header-only C++ library for geospatial space-division based compression and encoding
R :package: and header-only C++ library for geospatial space-division based compression and encoding

spress spress provides utilities for encoding and compressing geospatial objects, such as sf objects. Installation This package requires C++11 for com

Dec 9, 2021
A collection of libraries, data structures, and more that I have created to make coding in C less painful.

ctools A collection of libraries, data structures, and more that I have created to make coding in C less painful. Data structures There are many data

Nov 27, 2021