Postmodern immutable and persistent data structures for C++ — value semantics at scale

Overview
Github Actions Badge CodeCov Badge Sinusoidal Engineering badge

Logotype

immer is a library of persistent and immutable data structures written in C++. These enable whole new kinds of architectures for interactive and concurrent programs of striking simplicity, correctness, and performance.

This library has full months of pro bono research and development invested in it. This is just the first step in a long-term vision of making interactive and concurrent C++ programs easier to write. Put your logo here and help this project's long term sustainability by buying a sponsorship package: [email protected]

Example

#include <immer/vector.hpp>
int main()
{
    const auto v0 = immer::vector<int>{};
    const auto v1 = v0.push_back(13);
    assert(v0.size() == 0 && v1.size() == 1 && v1[0] == 13);

    const auto v2 = v1.set(0, 42);
    assert(v1[0] == 13 && v2[0] == 42);
}
For a complete example check Ewig, a simple didactic text-editor built with this library. You may also wanna check Lager, a Redux-like library for writting interactive software in C++ using a value-oriented design.

Why?

In the last few years, there has been a growing interest in immutable data structures, motivated by the horizontal scaling of our processing power and the ubiquity of highly interactive systems. Languages like Clojure and Scala provide them by default, and implementations for JavaScript like Mori and Immutable.js are widely used, specially in combination with modern UI frameworks like React.

Interactivity
Thanks to persistence and structural sharing, new values can be efficiently compared with old ones. This enables simpler ways of reasoning about change that sit at the core of modern interactive systems programming paradigms like reactive programming.
Concurrency
Passing immutable data structures by value does not need to copy any data. In the absence of mutation, data can be safely read from multiple concurrent processes, and enable concurrency patterns like share by communicating efficiently.
Parallelism
Some recent immutable data structures have interesting properties like O(log(n)) concatenation, which enable new kinds of parallelization algorithms.

Features

Idiomatic
This library doesn't pretend that it is written in Haskell. It leverages features from recent standards to provide an API that is both efficient and natural for a C++ developer.
Performant
You use C++ because you need this. Immer implements state of the art data structures with efficient cache utilization and have been proven production ready in other languages. It also includes our own improvements over that are only possible because of the C++'s ability to abstract over memory layout. We monitor the performance impact of every change by collecting benchmark results directly from CI.
Customizable
We leverage templates and policy-based design to build data-structures that can be adapted to work efficiently for various purposes and architectures, for example, by choosing among various memory management strategies. This turns immer into a good foundation to provide immutable data structures to higher level languages with a C runtime, like Python or Guile.

Dependencies

This library is written in C++14 and a compliant compiler is necessary. It is continuously tested with Clang 3.8 and GCC 6, but it might work with other compilers and versions.

No external library is necessary and there are no other requirements.

Usage

This is a header only library. You can just copy the immer subfolder somewhere in your include path.

If you are using the Nix package manager (we strongly recommend it) you can just:

nix-env -if https://github.com/arximboldi/immer/archive/master.tar.gz

Alternatively, you can use CMake to install the library in your system once you have manually cloned the repository:

mkdir -p build && cd build
cmake .. && sudo make install

Development

In order to develop the library, you will need to compile and run the examples, tests and benchmarks. These require some additional tools. The easiest way to install them is by using the Nix package manager. At the root of the repository just type:

nix-shell

This will download all required dependencies and create an isolated environment in which you can use these dependencies, without polluting your system.

Then you can proceed to generate a development project using CMake:

mkdir build && cd build
cmake ..

From then on, one may build and run all tests by doing:

make check

In order to build and run all benchmarks when running make check, run cmake again with the option -DCHECK_BENCHMARKS=1. The results of running the benchmarks will be saved to a folder reports/ in the project root.

License

This software is licensed under the Boost Software License 1.0.

Boost logo

The full text of the license is can be accessed via this link and is also included in the LICENSE file of this software package.

Comments
  • added type traits, algorithms, and additional constructors

    added type traits, algorithms, and additional constructors

    Summary of changes: The following classes were modified to accomodate iterator sentinel pairs: immer::vector, immer::flex_vector, immer::array, immer::detail::with_capacity, immer::detail::no_capacity, and immer::detail::node. To this end, a new file was added, immer/detail/type_traits.hpp, providing metaprograms extending the facilities provided by the standard library type_traits header, along with several functions to the immer/algorithm.hpp header.

    opened by apmccartney 25
  • Segmentation fault with recursive types

    Segmentation fault with recursive types

    I found what appears to be a memory corruption issue with recursive types using box. Below is a minimal reproducer which seg-faults on my machine. I am on clang, MacOS 10.14, and -std=c++14.

    #include "immer/vector.hpp"
    #include "immer/box.hpp"
    
    
    
    
    //=============================================================================
    struct my_type
    {
        using container_t = immer::vector<immer::box<my_type>>;
        using func_t = std::function<int(int)>;
    
        int ival;
        double dval;
        func_t func;
        container_t children;
    };
    
    
    
    
    //=============================================================================
    int main()
    {
        my_type::container_t items = {my_type()};
        return 0;
    }
    
    
    opened by jzrake 22
  • Add support for VS 2017

    Add support for VS 2017

    I tried compilation of the latest master with VS2017, but I get a compile error:

    inline constexpr auto clz_(unsigned int x) { return __builtin_clz(x); }
    immer/detail/util.hpp(82): error C3861: '__builtin_clz': identifier not found
    

    Can you please add support for VS 2017?

    enhancement help wanted 
    opened by acki-m 20
  • Persistent Maps

    Persistent Maps

    Hi,

    I'm playing with immer for a project at the minute, but i also need immutable maps. I'm considering porting either Clojure's HAMTs or the CHAMP variant. Did you have any plans in this direction or could you give me a little advice on how to go about porting it into the infrastructure you've laid down?

    Thanks

    enhancement 
    opened by jjl 16
  • Optional disabling of exceptions

    Optional disabling of exceptions

    Our use of immer requires that we disable exceptions. As not supporting exceptions is a common situation in C++ codebases I'm filing this issue to propose integrating that change into immer.

    Our modification follows the same pattern that LibC++ uses: if exceptions are enabled, use them, otherwise, if an out-of-range or an allocation fails, log a message and abort.

    We added this snippet to immer/immer/config.hpp:

    #if __has_feature(cxx_exceptions)
    #define IMMER_THROW_BAD_ALLOC(msg) throw std::bad_alloc{msg}
    #define IMMER_THROW_OUT_OF_RANGE(msg) throw std::out_of_range{msg}
    #define IMMER_TRY try
    #define IMMER_CATCH_ALL catch (...)
    #define IMMER_RETHROW throw
    #else
    #define IMMER_NO_EXCEPTIONS
    #define IMMER_THROW_BAD_ALLOC(msg) fprintf(stderr, "%s", msg); abort()
    #define IMMER_THROW_OUT_OF_RANGE(msg) fprintf(stderr, "%s", msg); abort()
    #define IMMER_TRY
    #define IMMER_CATCH_ALL if (false)
    #define IMMER_RETHROW
    #endif
    

    And then replaced all exception handling code with the appropriate macros.

    Would it be OK to send a pull request with these modifications?

    opened by chuim 11
  • compile error with clang-9

    compile error with clang-9

    Tried to compile with clang-9 and got the following errors:

    immer/immer/detail/rbts/rbtree.hpp:13:
    /home/username/tmp/immer/immer/detail/rbts/operations.hpp:1092:28: error: chosen constructor is explicit in copy-initialization
                        return { pos.shift(), newn, ts, tail };
                               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    /home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
            return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                            ^
    /home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        { return impl_.take(elems); }
                       ^
    /home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
            auto v2 = v1.take(3);
                         ^
    /usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
            constexpr tuple(_UElements&&... __elements)
                      ^
    In file included from /home/username/tmp/immer/example/vector/vector.cpp:9:
    In file included from /home/username/tmp/immer/immer/vector.hpp:11:
    In file included from /home/username/tmp/immer/immer/detail/rbts/rbtree.hpp:13:
    /home/username/tmp/immer/immer/detail/rbts/operations.hpp:1120:16: error: chosen constructor is explicit in copy-initialization
            return { 0, nullptr, new_tail_size, new_tail };
                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    /home/username/tmp/immer/immer/detail/rbts/position.hpp:201:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_leaf<immer::detail::rbts::full_leaf_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
            return Visitor::visit_leaf(*this, std::forward<Args>(args)...);
                            ^
    /home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
            return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                            ^
    /home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        { return impl_.take(elems); }
                       ^
    /home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
            auto v2 = v1.take(3);
                         ^
    /usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
            constexpr tuple(_UElements&&... __elements)
                      ^
    In file included from /home/username/tmp/immer/example/vector/vector.cpp:9:
    In file included from /home/username/tmp/immer/immer/vector.hpp:11:
    In file included from /home/username/tmp/immer/immer/detail/rbts/rbtree.hpp:13:
    /home/username/tmp/immer/immer/detail/rbts/operations.hpp:1092:28: error: chosen constructor is explicit in copy-initialization
                        return { pos.shift(), newn, ts, tail };
                               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    /home/username/tmp/immer/immer/detail/rbts/position.hpp:1288:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::full_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
            return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                            ^
    /home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
            return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                            ^
    /home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        { return impl_.take(elems); }
                       ^
    /home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
            auto v2 = v1.take(3);
                         ^
    /usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
            constexpr tuple(_UElements&&... __elements)
                      ^
    In file included from /home/username/tmp/immer/example/vector/vector.cpp:9:
    In file included from /home/username/tmp/immer/immer/vector.hpp:11:
    In file included from /home/username/tmp/immer/immer/detail/rbts/rbtree.hpp:13:
    /home/username/tmp/immer/immer/detail/rbts/operations.hpp:1120:16: error: chosen constructor is explicit in copy-initialization
            return { 0, nullptr, new_tail_size, new_tail };
                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    /home/username/tmp/immer/immer/detail/rbts/position.hpp:108:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_leaf<immer::detail::rbts::leaf_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
            return Visitor::visit_leaf(*this, std::forward<Args>(args)...);
                            ^
    /home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
            return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                            ^
    /home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        { return impl_.take(elems); }
                       ^
    /home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
            auto v2 = v1.take(3);
                         ^
    /usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
            constexpr tuple(_UElements&&... __elements)
                      ^
    In file included from /home/username/tmp/immer/example/vector/vector.cpp:9:
    In file included from /home/username/tmp/immer/immer/vector.hpp:11:
    In file included from /home/username/tmp/immer/immer/detail/rbts/rbtree.hpp:13:
    /home/username/tmp/immer/immer/detail/rbts/operations.hpp:1092:28: error: chosen constructor is explicit in copy-initialization
                        return { pos.shift(), newn, ts, tail };
                               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    /home/username/tmp/immer/immer/detail/rbts/position.hpp:297:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
            return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                            ^
    /home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
            return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                            ^
    /home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        { return impl_.take(elems); }
                       ^
    /home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
            auto v2 = v1.take(3);
                         ^
    /usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
            constexpr tuple(_UElements&&... __elements)
                      ^
    In file included from /home/username/tmp/immer/example/vector/vector.cpp:9:
    In file included from /home/username/tmp/immer/immer/vector.hpp:11:
    In file included from /home/username/tmp/immer/immer/detail/rbts/rbtree.hpp:13:
    /home/username/tmp/immer/immer/detail/rbts/operations.hpp:1120:16: error: chosen constructor is explicit in copy-initialization
            return { 0, nullptr, new_tail_size, new_tail };
                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    /home/username/tmp/immer/immer/detail/rbts/position.hpp:201:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, false>::visit_leaf<immer::detail::rbts::full_leaf_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
            return Visitor::visit_leaf(*this, std::forward<Args>(args)...);
                            ^
    /home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
            return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                            ^
    /home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        { return impl_.take(elems); }
                       ^
    /home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
            auto v2 = v1.take(3);
                         ^
    /usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
            constexpr tuple(_UElements&&... __elements)
                      ^
    In file included from /home/username/tmp/immer/example/vector/vector.cpp:9:
    In file included from /home/username/tmp/immer/immer/vector.hpp:11:
    In file included from /home/username/tmp/immer/immer/detail/rbts/rbtree.hpp:13:
    /home/username/tmp/immer/immer/detail/rbts/operations.hpp:1092:28: error: chosen constructor is explicit in copy-initialization
                        return { pos.shift(), newn, ts, tail };
                               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    /home/username/tmp/immer/immer/detail/rbts/position.hpp:1288:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, false>::visit_regular<immer::detail::rbts::full_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
            return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                            ^
    /home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
            return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                            ^
    /home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        { return impl_.take(elems); }
                       ^
    /home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
            auto v2 = v1.take(3);
                         ^
    /usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
            constexpr tuple(_UElements&&... __elements)
                      ^
    In file included from /home/username/tmp/immer/example/vector/vector.cpp:9:
    In file included from /home/username/tmp/immer/immer/vector.hpp:11:
    In file included from /home/username/tmp/immer/immer/detail/rbts/rbtree.hpp:13:
    /home/username/tmp/immer/immer/detail/rbts/operations.hpp:1120:16: error: chosen constructor is explicit in copy-initialization
            return { 0, nullptr, new_tail_size, new_tail };
                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    /home/username/tmp/immer/immer/detail/rbts/position.hpp:108:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, false>::visit_leaf<immer::detail::rbts::leaf_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
            return Visitor::visit_leaf(*this, std::forward<Args>(args)...);
                            ^
    /home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
            return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                            ^
    /home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        { return impl_.take(elems); }
                       ^
    /home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
            auto v2 = v1.take(3);
                         ^
    /usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
            constexpr tuple(_UElements&&... __elements)
                      ^
    In file included from /home/username/tmp/immer/example/vector/vector.cpp:9:
    In file included from /home/username/tmp/immer/immer/vector.hpp:11:
    In file included from /home/username/tmp/immer/immer/detail/rbts/rbtree.hpp:13:
    /home/username/tmp/immer/immer/detail/rbts/operations.hpp:1092:28: error: chosen constructor is explicit in copy-initialization
                        return { pos.shift(), newn, ts, tail };
                               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    /home/username/tmp/immer/immer/detail/rbts/position.hpp:297:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, false>::visit_regular<immer::detail::rbts::regular_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
            return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                            ^
    /home/username/tmp/immer/immer/detail/rbts/position.hpp:945:25: note: in instantiation of function template specialization 'immer::detail::rbts::slice_right_visitor<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>, true>::visit_regular<immer::detail::rbts::regular_sub_pos<immer::detail::rbts::node<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6> > &>' requested here
            return Visitor::visit_regular(*this, std::forward<Args>(args)...);
                            ^
    /home/username/tmp/immer/immer/vector.hpp:293:20: note: in instantiation of member function 'immer::detail::rbts::rbtree<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
        { return impl_.take(elems); }
                       ^
    /home/username/tmp/immer/example/vector/vector.cpp:49:22: note: in instantiation of member function 'immer::vector<int, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024>, immer::refcount_policy, immer::no_transience_policy, false, true>, 5, 6>::take' requested here
            auto v2 = v1.take(3);
                         ^
    /usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: explicit constructor declared here
            constexpr tuple(_UElements&&... __elements)
                      ^
    
    
    
    opened by catskul 11
  • Use smaller ints for bitmap_t if applicable

    Use smaller ints for bitmap_t if applicable

    Hi, a small pr from me as was discussed earlier.

    I was fighting with integer promotion for some time and the only solution I found so far is to use casts for non-const expressions. Otherwise we get popcount() overload ambiguity...

    Please take a look and probably you could suggest a better solution for that :)

    opened by fedormatantsev 11
  • Add diffing algorithm to maps

    Add diffing algorithm to maps

    This is the implementation of a diff algorithm for immer::map. It compares two immer::map instances and calls respective lambda functions when keys were added or removed or when the value of a key changed. When data is shared among the two maps, the algorithm will not need to compare shared subtrees of the map. We plan to use this for an undo feature.

    The diff algorithm has following signature: ̂map::diff(map const& other, AddedFn&& added, ChangedFn&& changed, RemovedFn&& Removed) where the lambdas have the signature:

    void AddedFn(std::pair<Key, Value> const& added_entry)
    void ChangedFn(std::pair<Key, Value> const& old_item, std::pair<Key, Value> const& new_data)
    void RemovedFn(std::pair<Key, Value> const& removed_entry)
    

    Usage:

    immer::map<int, int> old_snapshot; // initialize somehow
    immer::map<int, int> new_snapshot = old_snapshot.set(1,2); // change somehow
    old_snapshot.diff(
      new_snapshot,
      [](auto const& added){ std::cout << "added key " << added.first << std::endl; },
      [](auto const& old, auto const& new){
        std::cout << "changed key " << old.first << " from " << old.second << " to " << new.second << std::endl; },
      [](auto const& removed){ std::cout << "removed key " << removed.first << std::endl; }
      );
    

    This signature works for our usecase, however we are happy for further input and would like to help to upstream this feature.

    This partially addresses: #120

    opened by mvtec-richter 10
  • Map B=6 support.

    Map B=6 support.

    I still have to refine the implementation, but the idea is clear. I have some issues with building tests, will continue tomorrow.

    Looking forward for the review :)

    opened by fedormatantsev 10
  • Fix exit-time destructor warning

    Fix exit-time destructor warning

    This snippet from immer/immer/detail/hamts/champ.hpp causes an exit-time destructor warning from clang:

        static const champ& empty()
        {
            static const champ empty_{
                node_t::make_inner_n(0),
                0,
            };
            return empty_;
        }
    

    I'll create a pull request to suggest addressing it similarly to what's discussed in this stack-overflow question.

    opened by chuim 9
  • macOS: Crash on start when enabling Optimizations

    macOS: Crash on start when enabling Optimizations

    I get a crash on startup, if (and only if) Link-Time Optimization (LLVM_LTO = YES) or optimisations (-O1 or higher) are on:

    bildschirmfoto 2018-04-10 um 13 42 16

    I'm using Xcode 9.3 on macOS 10.13.2. I suspect the problem might actually be outside of immer, but have you run into this before?

    opened by martinfinke 9
  • `flex_vector` nothrow move constructible/assignable

    `flex_vector` nothrow move constructible/assignable

    This is a result of https://github.com/arximboldi/immer/issues/244.

    This is just an idea how one could make the move constructor and assignment operator noexcept. I used aligned_storage to statically reserve some memory for the nodes.

    However, while I type this description I noticed a problem: I'm not familiar with the mechanism the frees memory. There is nothing that prevents the code from attempting to free the statically allocated buffers. A possible solution would be to keep the ref count always above 0.

    opened by maierlars 1
  • `noexcept` move constructors for `flex_vector`

    `noexcept` move constructors for `flex_vector`

    I looked into making the move constructor (and move-assignment) for flex_vector noexcept. This is something people (at least myself) want to ensure exception safety. Generally you want you types to be nothrow move constructible.

    It turns out to be not that trivial: it allocates nodes. This is similar to what the MSVC implementation of std::unordered_map does and it caused me a lot of pain in the past. At least the swap operation is de facto noexcept, but not marked as such.

    I propose two solutions:

    1. do not allocate anything unless necessary. This would introduce some special cases, where nullptr to head and tail node would indicate an empty flex_vector.
    2. This is similar to libstdc++ does for std::unordered_map: store the end nodes within the object itself. This would require to replace the end-nodes with the new end-nodes during a move operation.

    I prefer approach 1. Any ideas or opinions? Maybe there is a good reason to not have flex_vectors move constructor and assignment noexcept.

    opened by maierlars 5
  • immer::map can no longer be used with std::views/std::ranges

    immer::map can no longer be used with std::views/std::ranges

    I noticed since champ_iterator() = default; was removed, immer::map no longer satisfies the constraint std::ranges::range, which prevents usage with views, e.g. for(const auto &v : map | std::views::values).

    The issue is with std::ranges::end(), but oddly, std::end() compiles fine. I'm not sure if this is a difference in the standard or a compiler issue.

    For reference, I'm compiling on MSVC v19.34.31935 (latest version at present time).

    I'm happy to submit a PR to reintroduce the default constructor but wanted to check if this is wanted/the right way to go about it.

    opened by jon-smith 1
  • flex_vector does not respect type alignment requirements

    flex_vector does not respect type alignment requirements

    Essentially, flex_vector can (always?) allocates objects at addresses that do not align with the type's alignment requirements. I uncovered this while using Eigen with immer, which causes some nasty segfaults when there are alignment violations on vectorized types.

    I added a repro case here: https://github.com/sissow2/immer/commit/9d295b829c37dbabdb96b4f703ba56492734e76c . The sanity check with std::vector passes always, while the immer::flex_vector variant always fails :

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    flex_vector-alignment is a Catch v2.13.7 host application.
    Run with -? for options
    
    -------------------------------------------------------------------------------
    direct alignment
    -------------------------------------------------------------------------------
    /home/sissow2/projects/immer/test/flex_vector/alignment.cpp:32
    ...............................................................................
    
    ... snip ...
    
    /home/sissow2/projects/immer/test/flex_vector/alignment.cpp:41: FAILED:
      CHECK( v[i].is_aligned() )
    with expansion:
      false
    
    ===============================================================================
    test cases: 2 | 1 passed | 1 failed
    assertions: 8 | 4 passed | 4 failed
    
    

    This might be related to https://github.com/arximboldi/immer/issues/228, but the reporter's repro case is for a non-vectorized type so I'm not sure it's the same issue.

    I might be able to create a PR with a fix, but wondering if you have any ideas before I dive into it.

    Also: I'm really liking this library! This and lager have been making my life so much easier. Also thanks for providing a nix-shell environment, it made creating this repro case a breeze.

    opened by sissow2 5
  • Add vcpkg installation instructions

    Add vcpkg installation instructions

    immer is available as a port in vcpkg, a C++ library manager that simplifies installation for immerand other project dependencies. Documenting the install process here will help users get started by providing a single set of commands to build immer, ready to be included in their projects.

    We also test whether our library ports build in various configurations (dynamic, static) on various platforms (OSX, Linux, Windows: x86, x64, UWP, ARM) to keep a wide coverage for users.

    I'm a maintainer for vcpkg, and here is what the port script looks like. We try to keep the library maintained as close as possible to the original library.

    opened by Adela0814 0
  • Eigen Types + variant + holds_alternative<> + immer::flex_vector segfault in opt builds.

    Eigen Types + variant + holds_alternative<> + immer::flex_vector segfault in opt builds.

    Using types like Eigen::Vector3d in structs in variants in flex vectors cause a crash in immer when I

    a variant like:

    struct a_t{
            Eigen::Vector3d position;
    };
    struct b_t{
            double x;
    };
    using nifty_variant = std::variant<a_t, b_t>;
    

    and I try and filter out some of these structs with:

    
    template<typename T>
    inline auto filter(const immer::flex_vector<nifty_variant>& buf) {
        immer::flex_vector<T> out{};
        immer::for_each(buf.begin(), buf.end(), [&out](auto a) {
            if (std::holds_alternative<T>(a)) {
                out = move(out).push_back(std::get<T>(a));
            }
        });
        return out;
    }
    
    

    I get segfaults in opt builds, but not in debug builds like:

    #0  0x0000000000476478 in immer::detail::rbts::rrbtree< nifty_variant, immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap, 1024ul>, immer::refcount_policy, immer::spinlock_policy, immer::no_transience_policy, false, true>, 5u, 1u>::push_back_mut(immer::no_transience_policy::apply<immer::free_list_heap_policy<immer::cpp_heap, 1024ul> >::type::edit, nifty_variant) ()
    
    opened by asa 1
Releases(v0.8.0)
  • v0.8.0(Nov 24, 2022)

    Change log

    • New table data-structure
    • Transients for map, set and map (thanks to Meta for sponsoring this work!)
    • New structural-sharing aware diff method for map, set and map (thanks @mvtec-richter for that!)
    • New update_if_exists method for map and set
    • New identity method on all data-structures
    • Various bug-fixes and performance improvements
    Source code(tar.gz)
    Source code(zip)
Owner
Juanpe Bolívar
Postmodern C++, value-oriented design, interactive software, open-source strategy, functional programming, music tech.
Juanpe Bolívar
Multi-Scale Geometric Consistency Guided and Planar Prior Assisted Multi-View Stereo

ACMMP [News] The code for ACMH is released!!! [News] The code for ACMM is released!!! [News] The code for ACMP is released!!! About This repository co

Qingshan Xu 96 Jan 7, 2023
Repository of problems and solutions of labsheets used for Data Structures and Algorithms (CS F211) in Semester 2, 2020-21 at BITS Pilani - Hyderabad Campus.

CS F211 Data Structures and Algorithms (BITS Pilani - Hyderabad Campus) This repository contains the problems, solution approaches & explanations and

Rohit Dwivedula 27 Oct 31, 2022
Algo-Tree is a collection of Algorithms and data structures which are fundamentals to efficient code and good software design

Algo-Tree is a collection of Algorithms and data structures which are fundamentals to efficient code and good software design. Creating and designing excellent algorithms is required for being an exemplary programmer. It contains solutions in various languages such as C++, Python and Java.

DSC-Banasthali 53 Oct 4, 2022
Templates, algorithms and data structures implemented and collected for programming contests.

Templates, algorithms and data structures implemented and collected for programming contests.

Shahjalal Shohag 2k Jan 2, 2023
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_

null 1 Oct 19, 2021
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

Leonardo Vencovsky 347 Jan 8, 2023
🔗 Common Data Structures and Algorithms

?? Data Structures and Algorithms This library provides common data structures. It will also provide some data structures which needed in render or ga

Recep Aslantas 45 Dec 10, 2022
A collecton of generic reference counted data structures, tools to create compatible C style classes, and demo applications

The Offbrand library is a collection of reference counted generic data structures written in C for C. The library includes bash scripts to assist in t

Tyler Heck 82 Dec 10, 2022
An assortment of commonly used algorithms and data structures implemented with C++.

Algorithms-And-Data-Structures This repo contains C++ implementations of common algorithms and data structures, grouped by topics. The list will be sp

Tony Sheng 23 Nov 9, 2021
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

Lprogrammers Lm9awdine 53 Nov 21, 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

BnademOverflow 53 Nov 21, 2022
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

MAINAK CHAUDHURI 2 Aug 8, 2021
The aim of this repository is to make it a one final stop for revision for technical interviews involving data structures and algorithms .

Hey ??‍♂️ This repository is meant for data structures and algorithms . I will be updating this often and will include all the data structures importa

Prakhar Rai 51 Sep 29, 2022
This is a beginner-friendly project aiming to build a problem-set on different data structures and algorithms in different programming languages.

DSAready Overview This is a beginner-friendly project that aims to create a problem-set for various Data Structures and Algorithms. Being a programmer

Riddhi Jain 13 Aug 17, 2022
Explore the world of Data Structures and Algorithm

Hey Everyone! ?? DSA- PlayYard is the first open source project of Lets Grow More Community. It is the perfect place to start with or to test your DSA

LetsGrowMore 20 Oct 9, 2022
Implementation of various data structures and algorithms.

Data Structures and Algorithms A place where you can find and learn the copious number of algorithms in an efficient manner. This repository covers va

Google DSC, GVP Chapter 15 Jul 24, 2022
Data Structures and Algorithms implemented in C++

OpenOcto - Data Structures and Algorithms Data Structures and Algorithms implemented in C++ Code here directly using Gitpod! Everthing done in C++ All

null 5 Dec 27, 2022
Data structures and algorithms course, winter 2021/22

Data Structures and Algorithms 2021/22 Repository for the "Data structures and algorithms" course for the 2021/22 academic year. Structure lectures --

Atanas Semerdzhiev 18 Dec 28, 2022
A repository by Codechef@MUST for data structures and algorithms

DSA Overview The main goal of this project is to promote open-source, allowing anyone who wants to contribute. This repository would be focused on var

null 20 Sep 3, 2022