Commits

remusao committed 3a259ec

try to do it wihout the memoryPool, and with shared ptr. Random result on queens...

Comments (0)

Files changed (15)

 
 
 
-set(CMAKE_CXX_FLAGS_DEBUG "-std=c++11 -pg -g")
+set(CMAKE_CXX_FLAGS_DEBUG "-std=c++11 -pg -g -lboost_system")
 #set(CMAKE_CXX_FLAGS_DEBUG "-std=c++11 -Wall -W -Werror -pedantic -g")
-set(CMAKE_CXX_FLAGS "-std=c++11 -march=native -Ofast -findirect-inlining -funsafe-loop-optimizations -Wall -Wextra -pedantic")
+set(CMAKE_CXX_FLAGS "-std=c++11 -march=native -O3 -findirect-inlining -funsafe-loop-optimizations -Wall -Wextra -pedantic -fpermissive -lboost_system")
 
 #Defines subdirectory
 add_subdirectory(src/)

src/CMakeLists.txt

 
 add_subdirectory(bddLib)
 
+FIND_PACKAGE(Boost 1.40)
+INCLUDE_DIRECTORIES(${Boost_INCLUDE_DIR})
+
 # Add the binary and sources
 add_executable(
     bddMain
 )
 
 SET_TARGET_PROPERTIES(bdd PROPERTIES LINKER_LANGUAGE CXX)
-target_link_libraries(bddMain bdd)
-target_link_libraries(bddQueen bdd)
-target_link_libraries(graphColoration bdd)
-target_link_libraries(coloration4 bdd)
-target_link_libraries(bddKnights bdd)
+target_link_libraries(bddMain bdd ${Boost_LIBRARIES})
+target_link_libraries(bddQueen bdd ${Boost_LIBRARIES})
+target_link_libraries(graphColoration bdd ${Boost_LIBRARIES})
+target_link_libraries(coloration4 bdd ${Boost_LIBRARIES})
+target_link_libraries(bddKnights ${Boost_LIBRARIES} bdd)

src/bddLib/CMakeLists.txt

+
 add_library(bdd STATIC
     bdd.hh
     bdd.cc
     bddNode.hh
     bddUtils.hh
     bddUtils.cc
-    memoryManager.hh
     caching.hh
     caching.cc
+    RCPtr.hh
+    atomicCounter.hh
+    atomicCounter.cc
 )
+

src/bddLib/RCPtr.hh

+#ifndef RCPTR_HH_
+# define RCPTR_HH_
+
+# include "atomicCounter.hh"
+
+namespace Bdd
+{
+    template <typename T>
+    class RCPtr
+    {
+        public:
+            RCPtr();
+            RCPtr(T* elt);
+            RCPtr(RCPtr&& ptr);
+            RCPtr(const RCPtr&);
+            ~RCPtr();
+
+            RCPtr& operator= (RCPtr&& ptr);
+            RCPtr& operator= (const RCPtr&);
+
+            // Forbidden operators
+
+
+            bool operator== (const RCPtr&) const;
+            bool operator!= (const RCPtr&) const;
+            T* operator-> ();
+            T* operator-> () const;
+            operator bool () const;
+
+            T* get() const;
+            void duplicate() const;
+            bool release() const;
+            int getReferenceCount() const;
+
+        private:
+            T* elt_;
+            //mutable AtomicCounter* counter_;
+            mutable int* counter_;
+    };
+    //
+    // inlines
+    //
+    //
+    template <typename T>
+    inline
+    RCPtr<T>::RCPtr()
+        : elt_(nullptr),
+          counter_(nullptr)
+    {
+    }
+
+    template <typename T>
+    inline
+    RCPtr<T>::RCPtr(const RCPtr<T>& ptr)
+        : elt_(ptr.elt_),
+          counter_(ptr.counter_)
+    {
+        if (ptr.counter_ != nullptr)
+            ++(*counter_);
+    }
+
+    template <typename T>
+    inline
+    RCPtr<T>::RCPtr(T* elt)
+        : elt_(elt),
+          counter_(new int(1))
+    {
+    }
+
+    template <typename T>
+    inline
+    RCPtr<T>::RCPtr(RCPtr&& ptr)
+        : elt_(std::move(ptr.elt_)),
+          counter_(std::move(ptr.counter_))
+    {
+    }
+
+    template <typename T>
+    inline
+    RCPtr<T>::~RCPtr()
+    {
+        release();
+    }
+
+    template <typename T>
+    inline RCPtr<T>&
+    RCPtr<T>::operator= (const RCPtr<T>& ptr)
+    {
+        this->elt_ = ptr.elt_;
+        this->counter_ = ptr.counter_;
+        if (this->counter_ != nullptr)
+            ++(*this->counter_);
+
+        return *this;
+    }
+
+    template <typename T>
+    inline RCPtr<T>&
+    RCPtr<T>::operator= (RCPtr<T>&& ptr)
+    {
+        this->elt_ = std::move(ptr.elt_);
+        this->counter_ = std::move(ptr.counter_);
+
+        return *this;
+    }
+
+    template <typename T>
+    inline
+    RCPtr<T>::operator bool () const
+    {
+        return elt_ != nullptr;
+    }
+
+    template <typename T>
+    inline T*
+    RCPtr<T>::operator-> () const
+    {
+        return elt_;
+    }
+
+    template <typename T>
+    inline T*
+    RCPtr<T>::operator-> ()
+    {
+        return elt_;
+    }
+
+    template <typename T>
+    inline bool
+    RCPtr<T>::operator== (const RCPtr& p) const
+    {
+        return elt_ == p.elt_;
+    }
+
+    template <typename T>
+    inline bool
+    RCPtr<T>::operator!= (const RCPtr& p) const
+    {
+        return elt_ != p.elt_;
+    }
+
+    template <typename T>
+    inline int
+    RCPtr<T>::getReferenceCount() const
+    {
+        return *counter_;
+    }
+
+    template <typename T>
+    inline T*
+    RCPtr<T>::get() const
+    {
+        return elt_;
+    }
+
+    template <typename T>
+    inline void
+    RCPtr<T>::duplicate() const
+    {
+        if (counter_)
+            ++(*counter_);
+    }
+
+    template <typename T>
+    inline bool
+    RCPtr<T>::release() const
+    {
+        // Test if 0 and free in the memory pool ?
+        if (counter_ != nullptr)
+            return --(*counter_) <= 0;
+        return false;
+    }
+}
+
+#endif // !RCPTR_HH_

src/bddLib/atomicCounter.cc

+#include "atomicCounter.hh"
+
+namespace Bdd
+{
+    AtomicCounter::AtomicCounter()
+        : counter_(ATOMIC_VAR_INIT(0))
+    {
+    }
+
+    AtomicCounter::AtomicCounter(const AtomicCounter& init)
+        : counter_(ATOMIC_VAR_INIT(std::atomic_load(&init.counter_)))
+    {
+    }
+
+
+    AtomicCounter::AtomicCounter(AtomicCounter::ValueType init)
+        : counter_(ATOMIC_VAR_INIT(init))
+    {
+    }
+
+    AtomicCounter::~AtomicCounter()
+    {
+    }
+}

src/bddLib/atomicCounter.hh

+#ifndef ATOMICcounter__HH_
+# define ATOMICcounter__HH_
+
+# include <atomic>
+
+namespace Bdd
+{
+    class AtomicCounter
+    {
+        public:
+            // Type of the counter
+            typedef int ValueType;
+
+            /// Creates a new AtomicCounter and initializes it to zero.
+            AtomicCounter();
+
+            /// Creates a new AtomicCounter and initializes it with
+            /// the given value.
+            explicit AtomicCounter(ValueType initialValue);
+
+            /// Creates the counter by copying another one.
+            AtomicCounter(const AtomicCounter& counter);
+
+            /// Destroys the AtomicCounter.
+            ~AtomicCounter();
+
+            /// Assigns the value of another AtomicCounter.
+            AtomicCounter& operator= (const AtomicCounter& counter);
+
+            /// Assigns a value to the counter.
+            AtomicCounter& operator= (ValueType value);
+
+            /// Returns the value of the counter.
+            operator ValueType () const;
+
+            /// Returns the value of the counter.
+            ValueType value() const;
+
+            /// Increments the counter and returns the result.
+            ValueType operator++ (); // prefix
+
+            /// Increments the counter and returns the previous value.
+            ValueType operator++ (int) = delete; // postfix
+
+            /// Decrements the counter and returns the result.
+            ValueType operator-- (); // prefix
+
+            /// Decrements the counter and returns the previous value.
+            ValueType operator-- (int) = delete; // postfix
+
+            /// Returns true if the counter is zero, false otherwise.
+            bool operator! () const;
+
+        private:
+            std::atomic<int> counter_;
+    };
+
+    inline
+    AtomicCounter&
+    AtomicCounter::operator= (const AtomicCounter& counter)
+    {
+        counter_ = ATOMIC_VAR_INIT(std::atomic_load(&counter.counter_));
+        return *this;
+    }
+
+    inline
+    AtomicCounter::operator AtomicCounter::ValueType () const
+    {
+        return counter_;
+    }
+
+
+    inline AtomicCounter::ValueType
+    AtomicCounter::value() const
+    {
+        return counter_;
+    }
+
+
+    inline AtomicCounter::ValueType
+    AtomicCounter::operator++ () // prefix
+    {
+        // return __sync_add_and_fetch(&counter_, 1);
+        return std::atomic_fetch_add(&counter_, 1);
+    }
+
+
+    inline AtomicCounter::ValueType
+    AtomicCounter::operator-- () // prefix
+    {
+        //return __sync_sub_and_fetch(&counter_, 1);
+        return std::atomic_fetch_sub(&counter_, 1);
+    }
+
+
+    inline bool
+    AtomicCounter::operator! () const
+    {
+        return counter_ == 0;
+    }
+
+}
+#endif // !ATOMICcounter__HH_

src/bddLib/bdd.cc

     {
     }
 
-    Bdd::Bdd(BddNode* root) noexcept
+    Bdd::Bdd(RCPtr<BddNode>&& root) noexcept
+        : root_(std::move(root))
+    {
+    }
+
+    Bdd::Bdd(const RCPtr<BddNode>& root) noexcept
         : root_(root)
     {
     }
     }
 
     // Init the memory manager
-    void initBdd(std::size_t nbVars, std::size_t poolSize) noexcept
+    void initBdd(std::size_t nbVars) noexcept
     {
-        // init the memory manager
-        Caching::g_mm = initMM<BddNode>(poolSize);
-        Caching::__node2id.max_load_factor(0.8);
-
-        // true and false nodes are the first nodes
-        // allocated with the memory manager. Their
-        // respective values are set in the setNbVar
-        // function (later)
-        Caching::trueNode = newNode(Caching::g_mm);
-        Caching::falseNode = newNode(Caching::g_mm);
-
-        setVarNum(nbVars);
+        // Init true and false bdd
+        BddNode* t = (BddNode*)Caching::memoryPool.malloc();
+        t->var = nbVars + 1;
+        Caching::__trueNode = RCPtr<BddNode>(t);
+
+        BddNode* f = (BddNode*)Caching::memoryPool.malloc();
+        f->var = nbVars + 2;
+        Caching::__falseNode = RCPtr<BddNode>(f);
+
+        // Init unique table
+        // Caching::__node2id.max_load_factor(0.8);
+        Caching::__node2id.set_empty_key(RCPtr<BddNode>());
+
+        // Init vars
+        Caching::__variables.clear();
+        Caching::__variables.resize(nbVars);
+
+        for (std::size_t i = 0; i < nbVars; ++i)
+            Caching::__variables[i] = i;
     }
 
     void releaseBdd() noexcept
     {
-        release(Caching::g_mm);
+        Caching::memoryPool.purge_memory();
     }
 
+    RCPtr<BddNode>&
+    Bdd::getRoot() noexcept
+    {
+        return root_;
+    }
 
-
-    BddNode*
+    const RCPtr<BddNode>&
     Bdd::getRoot() const noexcept
     {
         return root_;
     Bdd
     Bdd::operator!() const noexcept
     {
-        static auto op = [this](const BddNode* n, const BddNode*) -> BddNode*
+        static auto op = [this](const RCPtr<BddNode>& n, const RCPtr<BddNode>&)
         {
             return isFalseBdd(n) ? getTrueBdd() : getFalseBdd();
         };
     Bdd
     Bdd::operator||(const Bdd& bdd) const noexcept
     {
-        // http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51494
-        static auto op = [this](const BddNode* n1, const BddNode* n2) -> BddNode*
+        static auto op = [this](const RCPtr<BddNode>& n1, const RCPtr<BddNode>& n2)
         {
             return ((isTrueBdd(n1) || isTrueBdd(n2)) ? getTrueBdd() : getFalseBdd());
         };
     Bdd
     Bdd::operator&&(const Bdd& bdd) const noexcept
     {
-        // http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51494
-        static auto op = [this](const BddNode* n1, const BddNode* n2) -> BddNode*
+        static auto op = [this](const RCPtr<BddNode>& n1, const RCPtr<BddNode>& n2)
         {
             return ((isTrueBdd(n1) && isTrueBdd(n2)) ? getTrueBdd() : getFalseBdd());
         };
     Bdd
     Bdd::operator^(const Bdd& bdd) const noexcept
     {
-        // http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51494
-        static auto op = [this](const BddNode* n1, const BddNode* n2) -> BddNode*
+        static auto op = [this](const RCPtr<BddNode>& n1, const RCPtr<BddNode>& n2)
         {
             return (isTrueBdd(n1) && isTrueBdd(n2)) || (isFalseBdd(n1) && isFalseBdd(n2)) ? getFalseBdd() : getTrueBdd();
         };
     Bdd
     Bdd::implyNot(const Bdd& bdd) const noexcept
     {
-        static auto op = [this](const BddNode* n1, const BddNode* n2) -> BddNode*
+        static auto op = [this](const RCPtr<BddNode>& n1, const RCPtr<BddNode>& n2)
         {
             return ((isFalseBdd(n1) || isFalseBdd(n2)) ? getTrueBdd() : getFalseBdd());
         };
     Bdd
     Bdd::imply(const Bdd& bdd) const noexcept
     {
-        static auto op = [this](const BddNode* n1, const BddNode* n2) -> BddNode*
+        static auto op = [this](const RCPtr<BddNode>& n1, const RCPtr<BddNode>& n2)
         {
             return ((isFalseBdd(n1) || isTrueBdd(n2)) ? getTrueBdd() : getFalseBdd());
         };
 
     namespace
     {
-        void print_op(const BddNode* n) noexcept
+        void print_op(const RCPtr<BddNode>& n) noexcept
         {
             if (isLeaf(n))
                 return;
     Bdd::any_sat () const noexcept
     {
         decltype(any_sat()) res;
-        BddNode* cursor = this->root_;
-        std::vector<BddNode*> node_stack;
+        RCPtr<BddNode> cursor = this->root_;
+        std::vector<RCPtr<BddNode>> node_stack;
         node_stack.push_back (cursor);
 
         while (!node_stack.empty())
           if (res.size() > 0)
             res.pop_back();
 
-          BddNode* true_node = getTrueNode(cursor);
-          BddNode* false_node = getFalseNode(cursor);
+          RCPtr<BddNode> true_node = getTrueNode(cursor);
+          RCPtr<BddNode> false_node = getFalseNode(cursor);
 
           if (isTrueBdd(true_node))
             break;
     Bdd::all_sat() const noexcept
     {
         decltype(all_sat()) res_total;
-        BddNode* cursor = this->root_;
-        std::vector<BddNode*> node_stack;
+        RCPtr<BddNode> cursor = this->root_;
+        std::vector<RCPtr<BddNode>> node_stack;
         node_stack.push_back (cursor);
         std::vector<std::pair<unsigned, bool>> res;
 
           if (res.size() > 0)
             res.pop_back();
 
-          BddNode* true_node = getTrueNode(cursor);
-          BddNode* false_node = getFalseNode(cursor);
+          RCPtr<BddNode> true_node = getTrueNode(cursor);
+          RCPtr<BddNode> false_node = getFalseNode(cursor);
 
           if (isTrueBdd(true_node))
           {
     unsigned
     Bdd::sat() const noexcept
     {
-        BddNode* cursor = this->root_;
-        std::vector<BddNode*> node_stack;
+        RCPtr<BddNode> cursor = this->root_;
+        std::vector<RCPtr<BddNode>> node_stack;
         node_stack.push_back (cursor);
         unsigned total = 0;
-        std::vector<std::pair<unsigned, bool>> res;
 
         while (!node_stack.empty())
         {
           cursor = node_stack.back();
           node_stack.pop_back();
 
-          if (res.size() > 0)
-            res.pop_back();
 
-          BddNode* true_node = getTrueNode(cursor);
-          BddNode* false_node = getFalseNode(cursor);
+          RCPtr<BddNode> true_node = getTrueNode(cursor);
+          RCPtr<BddNode> false_node = getFalseNode(cursor);
 
           if (isTrueBdd(true_node))
           {
             ++total;
             continue;
           }
-
           else if (true_node && !isFalseBdd(true_node))
           {
-            std::pair<unsigned, bool> pair;
-            res.push_back(
-                std::pair<unsigned, bool>(getVarNode(true_node),
-                                           true));
             node_stack.push_back(true_node);
           }
 
             ++total;
             continue;
           }
-
           else if (false_node && !isFalseBdd(false_node))
           {
-            res.push_back(
-                std::pair<unsigned, bool>(getVarNode(false_node),
-                false));
             node_stack.push_back(false_node);
           }
         }

src/bddLib/bdd.hh

 
 # include "bddNode.hh"
 # include "bddUtils.hh"
-# include "memoryManager.hh"
+# include "RCPtr.hh"
 
 namespace Bdd
 {
     {
         public:
             Bdd() noexcept;
-            Bdd(struct BddNode* root) noexcept;
+            Bdd(const RCPtr<BddNode>& root) noexcept;
+            Bdd(RCPtr<BddNode>&& root) noexcept;
             ~Bdd() noexcept;
 
-            // Return the unique nodes on true and false
-            // static struct BddNode* getTrueBdd() noexcept;
-            // static struct BddNode* getFalseBdd() noexcept;
 
-            struct BddNode* getRoot() const noexcept;
+            const RCPtr<BddNode>& getRoot() const noexcept;
+            RCPtr<BddNode>& getRoot() noexcept;
 
             Bdd operator!() const noexcept;
             Bdd operator||(const Bdd& bdd) const noexcept;
 
         private:
 
-            struct BddNode* root_; // Root of this BDD
+            RCPtr<BddNode> root_; // Root of this BDD
     };
 
-    void initBdd(std::size_t nbVars, std::size_t poolSize = 134217728) noexcept;
+    void initBdd(std::size_t nbVars) noexcept;
     void releaseBdd() noexcept;
 
-    inline Bdd bdd_ithvar(std::size_t variable) noexcept
+    // Return the unique nodes on true and false
+    // RCPtr<BddNode>& getTrueBdd() noexcept;
+    // RCPtr<BddNode>& getFalseBdd() noexcept;
+
+    inline Bdd
+    bdd_ithvar(std::size_t variable) noexcept
     {
         return Bdd(bdd_ithvarnode(variable));
     }
 
-    inline Bdd bdd_not_ithvar(std::size_t variable) noexcept
+    inline Bdd
+    bdd_not_ithvar(std::size_t variable) noexcept
     {
         return Bdd(bdd_not_ithvarnode(variable));
     }

src/bddLib/bddNode.hh

 # define BDDNODE_HH
 
 # include <cstddef>
+# include "RCPtr.hh"
 # include "caching.hh"
 
 namespace Bdd
     struct BddNode
     {
         // Attributes
-        unsigned var : 10;
-        std::size_t false_ptr : 27;
-        std::size_t true_ptr : 27;
-    } __attribute__ ((packed));
+        unsigned var;
+        RCPtr<struct BddNode> false_ptr;
+        RCPtr<struct BddNode> true_ptr;
+    };
 
 
-    inline struct BddNode*
-    createNode(const BddNode& node) noexcept
+    inline RCPtr<BddNode>
+    createNode(unsigned var, const RCPtr<BddNode>& f, const RCPtr<BddNode> t) noexcept
     {
-        struct BddNode* n = newNode(Caching::g_mm);
-        *n = node;
+        BddNode* node = (BddNode*)Caching::memoryPool.malloc();
+        node->var = var;
+        node->false_ptr = f;
+        node->true_ptr = t;
 
-        return n;
+        return RCPtr<BddNode>(node);
     }
 
-
-    inline struct BddNode*
-    createNode(unsigned var, std::size_t f, std::size_t t) noexcept
-    {
-        struct BddNode* n = newNode(Caching::g_mm);
-        *n = BddNode{var, f, t};
-
-        return n;
-    }
-
-
-    inline struct BddNode*
-    createNode(unsigned var, struct BddNode* f, struct BddNode* t) noexcept
-    {
-        return createNode(var, getOffset<BddNode>(Caching::g_mm, f), getOffset(Caching::g_mm, t));
-    }
-
-
-    inline struct BddNode*
-    getFalseNode(const struct BddNode* node) noexcept
+    inline BddNode*
+    getFalseNode(const RCPtr<BddNode>& node) noexcept
     {
-        return getBddNode<BddNode>(Caching::g_mm, node->false_ptr);
+        return node->false_ptr.get();
     }
 
-
-    inline struct BddNode*
-    getFalseNode(std::size_t node) noexcept
+    inline BddNode*
+    getTrueNode(const RCPtr<BddNode>& node) noexcept
     {
-        return getBddNode<BddNode>(Caching::g_mm, getBddNode(Caching::g_mm, node)->false_ptr);
+        return node->true_ptr.get();
     }
 
-
-    inline struct BddNode*
-    getTrueNode(const struct BddNode* node) noexcept
-    {
-        return getBddNode<BddNode>(Caching::g_mm, node->true_ptr);
-    }
-
-
-    inline struct BddNode*
-    getTrueNode(std::size_t node) noexcept
-    {
-        return getBddNode<BddNode>(Caching::g_mm, getBddNode(Caching::g_mm, node)->true_ptr);
-    }
-
-
     inline unsigned
-    getVarNode(const struct BddNode* node) noexcept
+    getVarNode(const RCPtr<BddNode>& node) noexcept
     {
         return node->var;
     }
 
-
-    inline unsigned
-    getVarNode(std::size_t node) noexcept
-    {
-        return getBddNode<BddNode>(Caching::g_mm, node)->var;
-    }
-
-
-    inline std::size_t
-    magicCast(const struct BddNode* n) noexcept
+    inline RCPtr<BddNode>&
+    getTrueBdd() noexcept
     {
-        return (n != 0 ? *(std::size_t*)(n) : 0);
+        return Caching::__trueNode;
     }
 
-
-    inline void
-    assign(unsigned i, struct BddNode* n) noexcept
+    inline RCPtr<BddNode>&
+    getFalseBdd() noexcept
     {
-        if (n != 0)
-            *(unsigned*)n = i;
+        return Caching::__falseNode;
     }
 }
 

src/bddLib/bddUtils.cc

 #include <queue>
+#include <boost/functional/hash.hpp>
+#include <iostream>
+#include <assert.h>
 #include "bddUtils.hh"
 #include "bdd.hh"
-#include "memoryManager.hh"
 #include "caching.hh"
 
-#include <iostream>
 
 namespace Bdd
 {
     bool
-    isLeaf(const BddNode* node) noexcept
+    isLeaf(const RCPtr<BddNode>& node) noexcept
     {
-        return (getVarNode(node) >= Caching::__variables.size());
+        return (node->var) > Caching::__variables.size();
     }
 
     bool
-    isTrueBdd(const BddNode* node) noexcept
+    isTrueBdd(const RCPtr<BddNode>& node) noexcept
     {
-        return getVarNode(node) == getVarNode(Caching::trueNode);
+        return node == getTrueBdd();
     }
 
     bool
-    isFalseBdd(const BddNode* node) noexcept
+    isFalseBdd(const RCPtr<BddNode>& node) noexcept
     {
-        return getVarNode(node) == getVarNode(Caching::falseNode);
+        return node == getFalseBdd();
     }
 
 
-    BddNode*
-    makeNode(unsigned id, BddNode* false_ptr, BddNode* true_ptr) noexcept
+    RCPtr<BddNode>
+    makeNode(unsigned id, const RCPtr<BddNode>& f, const RCPtr<BddNode>& t) noexcept
     {
-        BddNode* res = nullptr;
+        RCPtr<BddNode> res;
 
-        if (true_ptr != false_ptr)
+        if (t != f)
         {
-            // The node is its hash value. So with the union
-            // we get the size_t representation of the node
-            // (its size if 8 bytes so it's ok)
-            union
-            {
-                std::size_t hash;
-                struct BddNode node;
-            };
-            node = {id, getOffset(Caching::g_mm, false_ptr), getOffset(Caching::g_mm, true_ptr)};
-
+            std::size_t hash = 0;
+            boost::hash_combine(hash, id);
+            boost::hash_combine(hash, f.get());
+            boost::hash_combine(hash, t.get());
 
             // Check if the newly created node isn't in the cache already
             auto it = Caching::__node2id.find(hash);
             if (it == Caching::__node2id.end())
             {
                 // Create a new node and add it to the hash table
-                BddNode* newNode = createNode(node);
-                Caching::__node2id[hash] = newNode;
-                res = newNode;
+                res = RCPtr<BddNode>(createNode(id, f, t));
+                Caching::__node2id[hash] = res;
             }
             else
                 res = it->second;
         }
         else
-            res = false_ptr;
+            res = f;
 
         return res;
     }
     // Anonymous namespace to hide implementation
     namespace
     {
-        BddNode*
+        RCPtr<BddNode>
         app(
-            std::unordered_map<std::size_t, BddNode*>& cache,
-            const std::function<BddNode* (const BddNode*, const BddNode*)>& op,
-            const BddNode* n1,
-            const BddNode* n2) noexcept
+            UniqueHashMap& cache,
+            const std::function<RCPtr<BddNode> (const RCPtr<BddNode>&, const RCPtr<BddNode>&)>& op,
+            const RCPtr<BddNode>& n1,
+            const RCPtr<BddNode>& n2) noexcept
         {
-            BddNode* res = nullptr;
+            RCPtr<BddNode> res;
 
             if (isLeaf(n1) && isLeaf(n2))
                 res = op(n1, n2);
             else
             {
-                std::size_t hash =
-                     ((std::size_t)(getOffset(Caching::g_mm, n1)) << 32)
-                    | (std::size_t)(getOffset(Caching::g_mm, n2));
+                std::size_t hash = 0;
+                boost::hash_combine(hash, n1.get());
+                boost::hash_combine(hash, n2.get());
+
                 auto it = cache.find(hash);
 
                 if (it != cache.end())
                 else if (getVarNode(n1) == getVarNode(n2))
                 {
                     res = makeNode(getVarNode(n1),
-                            app(cache, op, getFalseNode(n1), getFalseNode(n2)),
-                            app(cache, op, getTrueNode(n1), getTrueNode(n2)));
+                            app(cache, op, n1->false_ptr, n2->false_ptr),
+                            app(cache, op, n1->true_ptr, n2->true_ptr));
                     cache[hash] = res;
                 }
                 else if (getVarNode(n1) < getVarNode(n2))
                 {
                     res = makeNode(getVarNode(n1),
-                            app(cache, op, getFalseNode(n1), n2),
-                            app(cache, op, getTrueNode(n1), n2));
+                            app(cache, op, n1->false_ptr, n2),
+                            app(cache, op, n1->true_ptr, n2));
                     cache[hash] = res;
                 }
                 else
                 {
                     res = makeNode(getVarNode(n2),
-                            app(cache, op, n1, getFalseNode(n2)),
-                            app(cache, op, n1, getTrueNode(n2)));
+                            app(cache, op, n1, n2->false_ptr),
+                            app(cache, op, n1, n2->true_ptr));
                     cache[hash] = res;
                 }
             }
             return res;
         }
 
-        BddNode*
+        RCPtr<BddNode>
         restr(
-            BddNode*  n,
-            std::size_t     var,
-            const BddNode*   value) noexcept
+            const RCPtr<BddNode>&   n,
+            std::size_t             var,
+            const RCPtr<BddNode>&   value) noexcept
         {
             if (getVarNode(n) > var)
                  return n;
             else if (getVarNode(n) < var)
                 return makeNode(getVarNode(n),
-                        restr(getFalseNode(n), var, value),
-                        restr(getTrueNode(n), var, value));
+                        restr(n->false_ptr, var, value),
+                        restr(n->true_ptr, var, value));
             else if (getVarNode(n) == var && isFalseBdd(value))
-                return getFalseNode(n);
+                return n->false_ptr;
             else //getVarNde(n) == var && value == Bdd::getTrueNode(n)
-                return getTrueNode(n);
+                return n->true_ptr;
         }
 
         void
         dfs(
-            const std::function<void (BddNode*)>& op,
-            BddNode* node) noexcept
+            const std::function<void (const RCPtr<BddNode>&)>& op,
+            const RCPtr<BddNode>& node) noexcept
         {
             op(node);
 
             if (isLeaf(node))
                 return;
 
-            dfs(op, getFalseNode(node));
-            dfs(op, getTrueNode(node));
+            dfs(op, node->false_ptr);
+            dfs(op, node->true_ptr);
         }
 
         void
         bfs(
-            const std::function<void (BddNode*)>& op,
-            BddNode* node) noexcept
+            const std::function<void (RCPtr<BddNode>&)>& op,
+            const RCPtr<BddNode>& node) noexcept
         {
-            std::queue<BddNode*> queue;
+            std::queue<RCPtr<BddNode>> queue;
 
             queue.push(node);
             queue.push(nullptr);
 
             while (!queue.empty())
             {
-                BddNode* n = queue.front();
+                RCPtr<BddNode> n = queue.front();
                 queue.pop();
 
                 if (n != nullptr)
 
         void
         dfs_modify(
-            const std::function<BddNode* (BddNode*)>& op,
-            BddNode* node) noexcept
+            const std::function<RCPtr<BddNode> (RCPtr<BddNode>&)>& op,
+            RCPtr<BddNode>& node) noexcept
         {
             node = op(node);
 
             if (isLeaf(node))
                 return;
 
-            dfs_modify(op, getFalseNode(node));
-            dfs_modify(op, getTrueNode(node));
+            dfs_modify(op, node->false_ptr);
+            dfs_modify(op, node->true_ptr);
         }
 
         void
         bfs_modify(
-            const std::function<BddNode* (BddNode*)>& op,
-            BddNode* node) noexcept
+            const std::function<RCPtr<BddNode> (RCPtr<BddNode>&)>& op,
+            RCPtr<BddNode>& node) noexcept
         {
-            std::queue<BddNode*> queue;
+            std::queue<RCPtr<BddNode>> queue;
 
             queue.push(node);
             queue.push(nullptr);
 
             while (!queue.empty())
             {
-                BddNode* n = queue.front();
+                RCPtr<BddNode> n = queue.front();
                 queue.pop();
 
                 if (n != nullptr)
                     queue.push(nullptr);
             }
         }
+
     }
 
     void
     BreadthFirstSearch(
-        const std::function<void (const BddNode*)>& op,
+        const std::function<void (const RCPtr<BddNode>&)>& op,
         const Bdd& bdd) noexcept
     {
         bfs(op, bdd.getRoot());
 
     void
     DepthFirstSearch(
-        const std::function<void (const BddNode*)>& op,
+        const std::function<void (const RCPtr<BddNode>&)>& op,
         const Bdd& bdd) noexcept
     {
         dfs(op, bdd.getRoot());
 
     void
     bfs_ModifyBdd(
-        const std::function<BddNode* (BddNode*)>& op,
+        const std::function<RCPtr<BddNode> (RCPtr<BddNode>&)>& op,
         Bdd& bdd) noexcept
     {
         bfs_modify(op, bdd.getRoot());
 
     void
     dfs_ModifyBdd(
-        const std::function<BddNode* (BddNode*)>& op,
+        const std::function<RCPtr<BddNode> (RCPtr<BddNode>&)>& op,
         Bdd& bdd) noexcept
     {
         dfs_modify(op, bdd.getRoot());
 
     Bdd
     apply(
-        const std::function<BddNode* (const BddNode*, const BddNode*)>& op,
+        const std::function<RCPtr<BddNode> (const RCPtr<BddNode>&, const RCPtr<BddNode>&)>& op,
         const Bdd& bdd1,
         const Bdd& bdd2) noexcept
     {
-        std::unordered_map<std::size_t, BddNode*> cache;
+        UniqueHashMap cache(1000);
+        cache.set_empty_key(RCPtr<BddNode>());
         return Bdd(app(cache, op, bdd1.getRoot(), bdd2.getRoot()));
     }
 
     Restrict(
         const Bdd&      n,
         std::size_t     var,
-        BddNode*  value) noexcept
+        const RCPtr<BddNode>&  value) noexcept
     {
         return Bdd(restr(n.getRoot(), var, value));
     }
-
-    void
-    setVarNum(std::size_t nbVar) noexcept
-    {
-        // Init the structure that stores the variables
-        Caching::__variables.clear();
-        Caching::__variables.resize(nbVar);
-
-        // Init True and False nodes
-        Caching::falseNode->var = nbVar + 1;
-        Caching::trueNode->var = nbVar;
-
-        for (std::size_t i = 0; i < nbVar; ++i)
-            Caching::__variables[i] = i;
-    }
 }

src/bddLib/bddUtils.hh

     class Bdd;
 
     /// Check if node is either True or False
-    bool isLeaf(const BddNode* node) noexcept;
-    bool isFalseBdd(const BddNode* node) noexcept;
-    bool isTrueBdd(const BddNode* node) noexcept;
+    bool isLeaf(const RCPtr<BddNode>& node) noexcept;
+    bool isFalseBdd(const RCPtr<BddNode>& node) noexcept;
+    bool isTrueBdd(const RCPtr<BddNode>& node) noexcept;
 
     /// Create a new node from (id, false_ptr, true_ptr) but ensure the unicity
     /// of the node by checking if it already exists in a hash table :
     /// 1) If it already exists, we juste return the existing node
     /// 2) If it doesn't exist, we create a new node, add it to the hash table
     /// and return it.
-    BddNode* makeNode(unsigned id, BddNode* false_ptr, BddNode* true_ptr) noexcept;
+    RCPtr<BddNode>
+    makeNode(unsigned id, const RCPtr<BddNode>& f, const RCPtr<BddNode>& t) noexcept;
 
     /// @brief bdd1 `op` bdd2
     /// The structure cache is used to store operations already performed.
     Bdd apply(
-        const std::function<BddNode* (const BddNode*, const BddNode*)>& op,
+        const std::function<RCPtr<BddNode> (const RCPtr<BddNode>&, const RCPtr<BddNode>&)>& op,
         const Bdd& bdd1,
         const Bdd& bdd2) noexcept;
 
     void BreadthFirstSearch(
-        const std::function<void (const BddNode*)>& op,
+        const std::function<void (const RCPtr<BddNode>&)>& op,
         const Bdd& bdd) noexcept;
 
     void DepthFirstSearch(
-        const std::function<void (const BddNode*)>& op,
+        const std::function<void (const RCPtr<BddNode>&)>& op,
         const Bdd& bdd) noexcept;
 
     void bfs_ModifyBdd(
-        const std::function<BddNode* (BddNode*)>& op,
+        const std::function<RCPtr<BddNode> (RCPtr<BddNode>)>& op,
         Bdd& bdd) noexcept;
 
     void dfs_ModifyBdd(
-        const std::function<BddNode* (BddNode*)>& op,
+        const std::function<RCPtr<BddNode> (RCPtr<BddNode>&)>& op,
         Bdd& bdd) noexcept;
 
     Bdd Restrict(
-        const Bdd&      n,
-        std::size_t     var,
-        BddNode*  value) noexcept;
+        const Bdd&       n,
+        std::size_t      var,
+        const RCPtr<BddNode>&  value) noexcept;
 
-    void setVarNum(std::size_t nbVar) noexcept;
-
-    inline BddNode*
+    inline RCPtr<BddNode>
     bdd_ithvarnode(std::size_t variable) noexcept
     {
         return makeNode(Caching::__variables[variable], getFalseBdd(), getTrueBdd());
     }
 
-    inline BddNode*
+    inline RCPtr<BddNode>
     bdd_not_ithvarnode(std::size_t variable) noexcept
     {
         return makeNode(Caching::__variables[variable], getTrueBdd(), getFalseBdd());

src/bddLib/caching.cc

+
 #include "caching.hh"
 #include "bddNode.hh"
 
 namespace Bdd
 {
-//    std::unordered_map<std::size_t, struct BddNode*> Caching::__node2id;
+    boost::pool<> Caching::memoryPool(sizeof (BddNode));
+
     UniqueHashMap Caching::__node2id(200000);
     std::vector<std::size_t> Caching::__variables;
-    struct BddNode* Caching::trueNode{nullptr};
-    struct BddNode* Caching::falseNode{nullptr};
-    MemoryManager<BddNode> Caching::g_mm;
+
+    RCPtr<BddNode> Caching::__falseNode{nullptr};
+    RCPtr<BddNode> Caching::__trueNode{nullptr};
 }

src/bddLib/caching.hh

 #ifndef CACHING_HH_
 # define CACHING_HH_
 
+# include <boost/pool/pool.hpp>
+# include <google/dense_hash_map>
 # include <unordered_map>
 # include <vector>
-# include "memoryManager.hh"
-
+# include "RCPtr.hh"
 
 namespace Bdd
 {
     // Forward declaration
     struct BddNode;
 
-    typedef std::unordered_map<std::size_t, BddNode*> UniqueHashMap;
+    struct MyPoolTag { };
+
+    //typedef std::unordered_map<std::size_t, RCPtr<BddNode>> UniqueHashMap;
+    typedef google::dense_hash_map<std::size_t, RCPtr<BddNode>> UniqueHashMap;
 
     // Global caching structures
     // Hashtable :
     {
         public:
 
-        static UniqueHashMap __node2id; // 2)
+        // typedef boost::singleton_pool<MyPoolTag, sizeof (BddNode)> memoryPool;
 
+        static boost::pool<> memoryPool;
+
+        static UniqueHashMap __node2id; // 2)
         // Vector used to store the global order on variables
         static std::vector<std::size_t> __variables;
 
-        // Unique true and false nodes
-        static struct BddNode* trueNode;
-        static struct BddNode* falseNode;
-
-        // Memory manager
-        static MemoryManager<BddNode> g_mm;
+        static RCPtr<BddNode> __falseNode;
+        static RCPtr<BddNode> __trueNode;
     };
-
-    // Do not use this method to test if a node is True
-    inline BddNode*
-    getTrueBdd() noexcept
-    {
-        return Caching::trueNode;
-    }
-
-    // Do not use this method to test if a node is False
-    inline BddNode*
-    getFalseBdd() noexcept
-    {
-        return Caching::falseNode;
-    }
 }
 
 #endif

src/bddLib/memoryManager.hh

-#ifndef MEMORY_MANAGER_HH_
-# define MEMORY_MANAGER_HH_
-
-#include <cstdlib>
-#include <cstring>
-#include <iostream>
-#include <cassert>
-
-
-namespace Bdd
-{
-    // Forward declaration
-    template<class T>
-    struct MemoryManager
-    {
-        std::size_t offset; // offset to look the the next free emplacement
-        std::size_t nbNodes; // number of nodes stored
-        std::size_t size; // size of the memory pool
-        T* memory; // pointer on memory pool
-    };
-
-
-    // ini the structure of the memory manager
-    template<class T>
-    inline MemoryManager<T> initMM(std::size_t size) noexcept
-    {
-        std::cout << "Allocating pool of size " << size << " (" << sizeof (T) * size << ")" << std::endl;
-        MemoryManager<T> mm{
-            (std::size_t)-1,
-            0,
-            size,
-            (T*)malloc(size * sizeof (T))
-        };
-        mm.memory = (T*)memset(mm.memory, 0, size * sizeof (T));
-        return mm;
-    }
-
-    // Free the memory manager
-    template<class T>
-    inline void release(MemoryManager<T>& mm) noexcept
-    {
-        if (mm.memory != nullptr)
-        {
-            free(mm.memory);
-            mm.memory = nullptr;
-        }
-    }
-
-    // allocate a new node in the memory pool
-    template<class T>
-    struct BddNode* newNode(MemoryManager<T>& mm) noexcept
-    {
-      // If full, increase the size of the pool
-      if (mm.nbNodes >= mm.size)
-      {
-        std::cout << "Out of memory" << std::endl;
-        assert(0);
-      }
-
-      ++mm.nbNodes;
-      // return the absolute pointer
-      return (T*)(mm.memory + (++mm.offset));
-    }
-
-
-    // Get the pointer associated with this offset in the memory pool
-    template<class T>
-    inline T* getBddNode(MemoryManager<T>& mm, unsigned offset) noexcept
-    {
-        return (T*)(mm.memory + offset);
-    }
-    // Get the offset of the given pointer
-    template<class T>
-    inline std::size_t getOffset(MemoryManager<T>& mm, const T* node) noexcept
-    {
-        return (std::size_t)(node - mm.memory);
-    }
-
-}
-
-#endif
   }
 
   nb_queens = atoi(argv[1]);
-
-  if (nb_queens <= 8)
-    Bdd::initBdd(nb_queens * nb_queens, 2097152);
-  else
-    Bdd::initBdd(nb_queens * nb_queens);
+  Bdd::initBdd(nb_queens * nb_queens);
 
   cells = new Bdd::Bdd*[nb_queens];
   for (int line = 0; line < nb_queens; ++line)