--- /dev/null
+//$$CDS-header$$
+
+#ifndef CDSLIB_INTRUSIVE_DETAILS_MULTILEVEL_HASHSET_BASE_H
+#define CDSLIB_INTRUSIVE_DETAILS_MULTILEVEL_HASHSET_BASE_H
+
+#include <memory.h> // memcmp
+#include <type_traits>
+#include <cds/intrusive/details/base.h>
+#include <cds/opt/compare.h>
+#include <cds/algo/atomic.h>
+#include <cds/details/marked_ptr.h>
+#include <cds/urcu/options.h>
+
+namespace cds { namespace intrusive {
+
+ /// MultiLevelHashSet ordered list related definitions
+ /** @ingroup cds_intrusive_helper
+ */
+ namespace multilevel_hashset {
+
+ /// Hash accessor option
+ /**
+ @copydetails traits::hash_accessor
+ */
+ template <typename Accessor>
+ struct hash_accessor {
+ //@cond
+ template <typename Base> struct pack: public Base
+ {
+ typedef Accessor hash_accessor;
+ };
+ //@endcond
+ };
+
+ /// Head node allocator option
+ /**
+ @copydetails traits::head_node_allocator
+ */
+ template <typename Accessor>
+ struct head_node_allocator {
+ //@cond
+ template <typename Base> struct pack: public Base
+ {
+ typedef Accessor head_node_allocator;
+ };
+ //@endcond
+ };
+
+ /// Array node allocator option
+ /**
+ @copydetails traits::array_node_allocator
+ */
+ template <typename Accessor>
+ struct array_node_allocator {
+ //@cond
+ template <typename Base> struct pack: public Base
+ {
+ typedef Accessor array_node_allocator;
+ };
+ //@endcond
+ };
+
+ /// \p MultiLevelHashSet internal statistics
+ template <typename EventCounter = cds::atomicity::event_counter>
+ struct stat {
+ typedef EventCounter event_counter ; ///< Event counter type
+ };
+
+ /// \p MultiLevelHashSet empty internal statistics
+ struct empty_stat {
+ };
+
+ /// MultiLevelHashSet traits
+ struct traits
+ {
+ /// Mandatory functor to get hash value from data node
+ /**
+ It is most-important feature of \p MultiLevelHashSet.
+ That functor must return a reference to fixed-sized hash value of data node.
+ The return value of that functor specifies the type of hash value.
+
+ Example:
+ \code
+ typedef uint8_t hash_type[32]; // 256-bit hash type
+ struct foo {
+ hash_type hash; // 256-bit hash value
+ // ... other fields
+ };
+
+ struct foo_hash_functor {
+ hash_type const& operator()( foo const& d ) const
+ {
+ return d.hash;
+ }
+ };
+ \endcode
+ */
+ typedef opt::none hash_accessor;
+
+ /// Disposer for removing data nodes
+ typedef opt::v::empty_disposer disposer;
+
+ /// Hash comparing functor
+ /**
+ No default functor is provided.
+ If the option is not specified, the \p less option is used.
+ */
+ typedef opt::none compare;
+
+ /// Specifies binary predicate used for hash compare.
+ /**
+ If the option is not specified, \p memcmp() -like bit-wise hash comparator is used
+ because the hash value is treated as fixed-sized bit-string.
+ */
+ typedef opt::none less;
+
+ /// Item counter
+ /**
+ The item counting is an important part of \p MultiLevelHashSet algorithm:
+ the \p empty() member function depends on correct item counting.
+ Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
+
+ Default is \p atomicity::item_counter.
+ */
+ typedef cds::atomicity::item_counter item_counter;
+
+ /// Head node allocator
+ /**
+ Allocator for head node. That allocator uses only in the set's constructor for allocating
+ main head array and in the destructor for destroying the head array.
+ Default is \ref CDS_DEFAULT_ALLOCATOR
+ */
+ typedef CDS_DEFAULT_ALLOCATOR head_node_allocator;
+
+ /// Array node allocator
+ /**
+ Allocator for array nodes. That allocator is used for creating \p arrayNode when the set grows.
+ The size of each array node is fixed.
+ Default is \ref CDS_DEFAULT_ALLOCATOR
+ */
+ typedef CDS_DEFAULT_ALLOCATOR array_node_allocator;
+
+ /// C++ memory ordering model
+ /**
+ Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
+ or \p opt::v::sequential_consistent (sequentially consisnent memory model).
+ */
+ typedef opt::v::relaxed_ordering memory_model;
+
+ /// Back-off strategy
+ typedef cds::backoff::Default back_off;
+
+ /// Internal statistics
+ /**
+ By default, internal statistics is disabled (\p multilevel_hashset::empty_stat).
+ Use \p multilevel_hashset::stat to enable it.
+ */
+ typedef empty_stat stat;
+
+ /// RCU deadlock checking policy (only for \ref cds_intrusive_MultilevelHashSet_rcu "RCU-based MultilevelHashSet")
+ /**
+ List of available policy see \p opt::rcu_check_deadlock
+ */
+ typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
+ };
+
+ /// Metafunction converting option list to \p multilevel_hashset::traits
+ /**
+ Supported \p Options are:
+ - \p multilevel_hashset::hash_accessor - mandatory option, hash accessor functor.
+ @copydetails traits::hash_accessor
+ - \p multilevel_hashset::head_node_allocator - head node allocator.
+ @copydetails traits::head_node_allocator
+ - \p multilevel_hashset::array_node_allocator - array node allocator.
+ @copydetails traits::array_node_allocator
+ - \p opt::compare - hash comparison functor. No default functor is provided.
+ If the option is not specified, the \p opt::less is used.
+ - \p opt::less - specifies binary predicate used for hash comparison.
+ If the option is not specified, \p memcmp() -like bit-wise hash comparator is used
+ because the hash value is treated as fixed-sized bit-string.
+ - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
+ - \p opt::disposer - the functor used for disposing removed data node. Default is \p opt::v::empty_disposer. Due the nature
+ of GC schema the disposer may be called asynchronously.
+ - \p opt::item_counter - the type of item counting feature.
+ The item counting is an important part of \p MultiLevelHashSet algorithm:
+ the \p empty() member function depends on correct item counting.
+ Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
+ Default is \p atomicity::item_counter.
+ - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
+ or \p opt::v::sequential_consistent (sequentially consisnent memory model).
+ - \p opt::stat - internal statistics. By default, it is disabled (\p multilevel_hashset::empty_stat).
+ To enable it use \p multilevel_hashset::stat
+ - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MultilevelHashSet_rcu "RCU-based MultilevelHashSet"
+ Default is \p opt::v::rcu_throw_deadlock
+ */
+ template <typename... Options>
+ struct make_traits
+ {
+# ifdef CDS_DOXYGEN_INVOKED
+ typedef implementation_defined type ; ///< Metafunction result
+# else
+ typedef typename cds::opt::make_options<
+ typename cds::opt::find_type_traits< traits, Options... >::type
+ ,Options...
+ >::type type;
+# endif
+ };
+
+ /// Bit-wise memcmp-based comparator for hash value \p T
+ template <typename T>
+ struct bitwise_compare
+ {
+ int operator()( T const& lhs, T const& rhs ) const
+ {
+ return memcmp( &lhs, &rhs, sizeof(T));
+ }
+ };
+
+ } // namespace multilevel_hashset
+
+ //@cond
+ // Forward declaration
+ template < class GC, typename T, class Traits = multilevel_hashset::traits >
+ class MultiLevelHashSet;
+ //@endcond
+
+}} // namespace cds::intrusive
+
+#endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_MULTILEVEL_HASHSET_BASE_H
--- /dev/null
+//$$CDS-header$$
+
+#ifndef CDSLIB_INTRUSIVE_IMPL_MULTILEVEL_HASHSET_H
+#define CDSLIB_INTRUSIVE_IMPL_MULTILEVEL_HASHSET_H
+
+#include <cds/intrusive/details/multilevel_hashset_base.h>
+#include <cds/details/allocator.h>
+
+namespace cds { namespace intrusive {
+ /// Intrusive hash set based on multi-level array
+ /** @ingroup cds_intrusive_map
+ @anchor cds_intrusive_MultilevelHashSet_hp
+
+ Source:
+ - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
+ Wait-free Extensible Hash Maps"
+
+ [From the paper] The hardest problem encountered while developing a parallel hash map is how to perform
+ a global resize, the process of redistributing the elements in a hash map that occurs when adding new
+ buckets. The negative impact of blocking synchronization is multiplied during a global resize, because all
+ threads will be forced to wait on the thread that is performing the involved process of resizing the hash map
+ and redistributing the elements. \p %MultilevelHashSet implementation avoids global resizes through new array
+ allocation. By allowing concurrent expansion this structure is free from the overhead of an explicit resize,
+ which facilitates concurrent operations.
+
+ The presented design includes dynamic hashing, the use of sub-arrays within the hash map data structure;
+ which, in combination with <b>perfect hashing</b>, means that each element has a unique final, as well as current, position.
+ It is important to note that the perfect hash function required by our hash map is trivial to realize as
+ any hash function that permutes the bits of the key is suitable. This is possible because of our approach
+ to the hash function; we require that it produces hash values that are equal in size to that of the key.
+ We know that if we expand the hash map a fixed number of times there can be no collision as duplicate keys
+ are not provided for in the standard semantics of a hash map.
+
+ \p %MultiLevelHashSet is a multi-level array whitch has a structure similar to a tree:
+ @image html multilevel_hashset.png
+ The multi-level array differs from a tree in that each position on the tree could hold an array of nodes or a single node.
+ A position that holds a single node is a \p dataNode which holds the hash value of a key and the value that is associated\r
+ with that key; it is a simple struct holding two variables. A \p dataNode in the multi-level array could be marked.\r
+ A \p markedDataNode refers to a pointer to a \p dataNode that has been bitmarked at the least significant bit (LSB)\r
+ of the pointer to the node. This signifies that this \p dataNode is contended. An expansion must occur at this node;\r
+ any thread that sees this \p markedDataNode will try to replace it with an \p arrayNode; which is a position that holds\r
+ an array of nodes. The pointer to an \p arrayNode is differentiated from that of a pointer to a \p dataNode by a bitmark\r
+ on the second-least significant bit.\r
+\r
+ \p %MultiLevelHashSet multi-level array is similar to a tree in that we keep a pointer to the root, which is a memory array\r
+ called \p head. The length of the \p head memory array is unique, whereas every other \p arrayNode has a uniform length;\r
+ a normal \p arrayNode has a fixed power-of-two length equal to the binary logarithm of a variable called \p arrayLength.\r
+ The maximum depth of the tree, \p maxDepth, is the maximum number of pointers that must be followed to reach any node.\r
+ We define \p currentDepth as the number of memory arrays that we need to traverse to reach the \p arrayNode on which\r
+ we need to operate; this is initially one, because of \p head.\r
+\r
+ That approach to the structure of the hash map uses an extensible hashing scheme; <b> the hash value is treated as a bit\r
+ string</b> and rehash incrementally.\r
+\r
+ @note Two important things you should keep in mind when you're using \p %MultiLevelHashSet:\r
+ - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %MultiLevelHashSet.\r
+ Instead, for the strings you should use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,\r
+ <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a> \r
+ or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which\r
+ converts variable-length strings to fixed-length bit-strings, and use that hash as a key in \p %MultiLevelHashSet.\r
+ - \p %MultiLevelHashSet uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,\r
+ have identical hash then you cannot insert both that keys in the set. \p %MultiLevelHashSet does not maintain the key,\r
+ it maintains its fized-size hash value.\r
+\r
+\r
+ There are several specializations of \p %MultiLevelHashSet for each \p GC. You should include:
+ - <tt><cds/intrusive/multilevel_hashset_hp.h></tt> for \p gc::HP garbage collector
+ - <tt><cds/intrusive/multilevel_hashset_dhp.h></tt> for \p gc::DHP garbage collector
+ - <tt><cds/intrusive/multilevel_hashset_nogc.h></tt> for \ref cds_intrusive_MultiLevelHashSet_nogc for append-only set
+ - <tt><cds/intrusive/multilevel_hashset_rcu.h></tt> for \ref cds_intrusive_MultiLevelHashSet_rcu "RCU type"
+ */
+ template <
+ class GC
+ ,typename T
+#ifdef CDS_DOXYGEN_INVOKED
+ ,typename Traits = multilevel_hashset::traits
+#else
+ ,typename Traits
+#endif
+ >
+ class MultiLevelHashSet
+ {
+ public:
+ typedef GC gc; ///< Garbage collector
+ typedef T value_type; ///< type of value stored in the set
+ typedef Traits traits; ///< Traits template parameter, see \p multilevel_hashset::traits
+
+ typedef typename traits::hash_accessor hash_accessor; ///< Hash accessor functor
+ static_assert(!std::is_same< hash_accessor, cds::opt::none >::value, "hash_accessor functor must be specified" );
+
+ /// Hash type
+ typedef typename std::decay<
+ typename std::remove_reference<
+ decltype( hash_accessor()( std::declval<T>()) )
+ >::type
+ >::type hash_type;
+ static_assert( !std::is_pointer<hash_type>, "hash_accessor should return a reference to hash value" );
+
+ typedef typename traits::disposer disposer; ///< data node disposer
+
+# ifdef CDS_DOXYGEN_INVOKED
+ typedef implementation_defined hash_comparator ; ///< hash compare functor based on opt::compare and opt::less option setter
+# else
+ typedef typename cds::opt::details::make_comparator_from<
+ hash_type,
+ traits,
+ multilevel_hashset::bitwise_compare< hash_type >
+ >::type hash_comparator;
+# endif
+
+ typedef typename traits::item_counter item_counter; ///< Item counter type
+ typedef typename traits::head_node_allocator head_node_allocator; ///< Head node allocator
+ typedef typename traits::array_node_allocator array_node_allocator; ///< Array node allocator
+ typedef typename traits::memory_model memory_model; ///< Memory model
+ typedef typename traits::back_off back_off; ///< Backoff strategy
+ typedef typename traits::stat stat; ///< Internal statistics type
+
+ typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
+
+ protected:
+ //@cond
+ enum cell_flags {
+ logically_deleted = 1, ///< the cell (data node) is logically deleted
+ array_converting = 2, ///< the cell is converting from data node to an array node
+ array_node = 4 ///< the cell is a pointer to an array node
+ };
+ typedef cds::details::marked_ptr< value_type, 7 > node_ptr;
+ typedef atomics::atomic< node_ptr * > atomic_node_ptr;
+
+ typedef cds::details::Allocator< atomic_node_ptr, head_node_allocator > cxx_head_node_allocator;
+ typedef cds::details::Allocator< atomic_node_ptr, array_node_allocator > cxx_array_node_allocator;
+
+ struct metrics {
+ size_t head_node_size; // power-of-two
+ size_t head_node_size_log; // log2( head_node_size )
+ size_t array_node_size; // power-of-two
+ size_t array_node_size_log;// log2( array_node_size )
+ };
+ //@endcond
+
+ private:
+ //@cond
+ metrics const m_Metrics; ///< Metrics
+ atomic_node_ptr * m_Head; ///< Head array
+ item_counter m_ItemCounter; ///< Item counter
+ stat m_Stat; ///< Internal statistics
+ //@endcond
+
+ public:
+ /// Creates empty set
+ /**
+ @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 8.
+ @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
+
+ Equation for \p head_bits and \p array_bits:
+ \code
+ sizeof(hash_type) * 8 == head_bits + N * array_bits
+ \endcode
+ where \p N is multi-level array depth.
+ */
+ MultiLevelHashSet( size_t head_bits = 8, size_t array_bits = 4 )
+ : m_Metrics(make_metrics( head_bits, array_bits ))
+ , m_Head( cxx_head_node_allocator().NewArray( m_Metrics.head_node_size, nullptr ))
+ {}
+
+ /// Destructs the set and frees all data
+ ~MultiLevelHashSet()
+ {
+ destroy_tree();
+ cxx_head_node_allocator().Delete( m_Head, m_Metrics.head_node_size );
+ }
+
+ /// Inserts new node
+ /**
+ The function inserts \p val in the set if it does not contain
+ an item with that hash.
+
+ Returns \p true if \p val is placed into the set, \p false otherwise.
+ */
+ bool insert( value_type& val )
+ {
+ }
+
+ /// Inserts new node
+ /**
+ This function is intended for derived non-intrusive containers.
+
+ The function allows to split creating of new item into two part:
+ - create item with key only
+ - insert new item into the set
+ - if inserting is success, calls \p f functor to initialize value-field of \p val.
+
+ The functor signature is:
+ \code
+ void func( value_type& val );
+ \endcode
+ where \p val is the item inserted.
+
+ The user-defined functor is called only if the inserting is success.
+
+ @warning See \ref cds_intrusive_item_creating "insert item troubleshooting".
+ */
+ template <typename Func>
+ bool insert( value_type& val, Func f )
+ {
+ }
+
+ /// Updates the node
+ /**
+ The operation performs inserting or changing data with lock-free manner.
+
+ If the item \p val not found in the set, then \p val is inserted into the set iff \p bInsert is \p true.
+ Otherwise, the functor \p func is called with item found, \p bInsert argument is ignored.
+
+ The functor signature is:
+ \code
+ void func( bool bNew, value_type& item, value_type& val );
+ \endcode
+ with arguments:
+ - \p bNew - \p true if the item has been inserted, \p false otherwise
+ - \p item - the item in the set (new or existing)
+ - \p val - argument \p val passed into the \p update function
+ If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
+ refers to the same thing.
+
+ The functor may change non-key fields of the \p item.
+
+ Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
+ \p second is \p true if new item has been added or \p false if the set contains that hash.
+
+ @warning See \ref cds_intrusive_item_creating "insert item troubleshooting".
+ */
+ template <typename Func>
+ std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
+ {
+ }
+
+ /// Unlinks the item \p val from the set
+ /**
+ The function searches the item \p val in the set and unlink it
+ if it is found and its address is equal to <tt>&val</tt>.
+
+ The function returns \p true if success and \p false otherwise.
+ */
+ bool unlink( value_type& val )
+ {
+ }
+
+ /// Deletes the item from the set
+ /**
+ The function searches \p hash in the set,
+ unlinks the item found, and returns \p true.
+ If that item is not found the function returns \p false.
+
+ The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
+
+ */
+ bool erase( hash_type const& hash )
+ {
+ if ( bucket( key ).erase( key )) {
+ --m_ItemCounter;
+ return true;
+ }
+ return false;
+ }
+
+ /// Deletes the item from the set
+ /**
+ The function searches \p hash in the set,
+ call \p f functor with item found, and unlinks it from the set.
+ The \ref disposer specified in \p Traits is called
+ by garbage collector \p GC asynchronously.
+
+ The \p Func interface is
+ \code
+ struct functor {
+ void operator()( value_type const& item );
+ };
+ \endcode
+
+ If \p hash is not found the function returns \p false.
+ */
+ template <typename Func>
+ bool erase( hash_type const& hash, Func f )
+ {
+ }
+
+ /// Extracts the item with specified \p hash
+ /**
+ The function searches \p hash in the set,
+ unlinks it from the set, and returns an guarded pointer to the item extracted.
+ If \p hash is not found the function returns an empty guarded pointer.
+
+ The \p disposer specified in \p Traits class' template parameter is called automatically
+ by garbage collector \p GC when returned \ref guarded_ptr object to be destroyed or released.
+ @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
+
+ Usage:
+ \code
+ typedef cds::intrusive::MultiLevelHashSet< your_template_args > my_set;
+ my_set theSet;
+ // ...
+ {
+ my_set::guarded_ptr gp( theSet.extract( 5 ));
+ if ( gp ) {
+ // Deal with gp
+ // ...
+ }
+ // Destructor of gp releases internal HP guard
+ }
+ \endcode
+ */
+ guarded_ptr extract( hash_type const& hash )
+ {
+ }
+
+ /// Finds an item by it's \p hash
+ /**
+ The function searches the item by \p hash and calls the functor \p f for item found.
+ The interface of \p Func functor is:
+ \code
+ struct functor {
+ void operator()( value_type& item );
+ };
+ \endcode
+ where \p item is the item found.
+
+ The functor may change non-key fields of \p item. Note that the functor is only guarantee
+ that \p item cannot be disposed during the functor is executing.
+ The functor does not serialize simultaneous access to the set's \p item. If such access is
+ possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
+
+ The function returns \p true if \p hash is found, \p false otherwise.
+ */
+ template <typename Func>
+ bool find( hash_type& hash, Func f )
+ {
+ }
+ //@cond
+ template <typename Func>
+ bool find( hash_type const& hash, Func f )
+ {
+ }
+ //@endcond
+
+ /// Finds an item by it's \p hash
+ /**
+ The function searches the item by its \p hash
+ and returns \p true if it is found, or \p false otherwise.
+ */
+ bool find( hash_type const& hash )
+ {
+ }
+
+ /// Finds an item by it's \p hash and returns the item found
+ /**
+ The function searches the item by its \p hash
+ and returns the guarded pointer to the item found.
+ If \p hash is not found the function returns an empty \p guarded_ptr.
+
+ @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
+
+ Usage:
+ \code
+ typedef cds::intrusive::MultiLevelHashSet< your_template_params > my_set;
+ my_set theSet;
+ // ...
+ {
+ my_set::guarded_ptr gp( theSet.get( 5 ));
+ if ( theSet.get( 5 )) {
+ // Deal with gp
+ //...
+ }
+ // Destructor of guarded_ptr releases internal HP guard
+ }
+ \endcode
+ */
+ guarded_ptr get( hash_type const& hash )
+ {
+ }
+
+ /// Clears the set (non-atomic)
+ /**
+ The function unlink all items from the set.
+ The function is not atomic. It removes all data nodes and then resets the item counter to zero.
+ If there are a thread that performs insertion while \p %clear() is working the result is undefined in general case:
+ \p empty() may return \p true but the set may contain item(s).
+ Therefore, \p %clear() may be used only for debugging purposes.
+
+ For each item the \p disposer is called after unlinking.
+ */
+ void clear()
+ {
+ }
+
+ /// Checks if the set is empty
+ /**
+ Emptiness is checked by item counting: if item count is zero then the set is empty.
+ Thus, the correct item counting feature is an important part of the set implementation.
+ */
+ bool empty() const
+ {
+ return size() == 0;
+ }
+
+ /// Returns item count in the set
+ size_t size() const
+ {
+ return m_ItemCounter;
+ }
+
+ /// Returns const reference to internal statistics
+ stat const& statistics() const
+ {
+ return m_Stat;
+ }
+
+ /// Returns the size of head node
+ size_t head_size() const
+ {
+ return m_Metrics.head_node_size;
+ }
+
+ /// Returns the size of the array node
+ size_t array_node_size() const
+ {
+ return m_Metrics.array_node_size;
+ }
+
+ private:
+ //@cond
+ static metrics make_metrics( size_t head_bits, size_t array_bits )
+ {
+ size_t const hash_bits = sizeof( hash_type ) * 8;
+
+ if ( array_bits < 2 )
+ array_bits = 2;
+ if ( head_bits < 8 )
+ head_bits = 8;
+ if ( head_bits > hash_bits )
+ head_bits = hash_bits;
+ if ( (hash_bits - head_bits) % array_bits != 0 )
+ head_bits += (hash_bits - head_bits) % array_bits;
+
+ assert( (hash_bits - head_bits) % array_bits == 0 );
+
+ metrics m;
+ m.head_node_size_log = head_bits;
+ m.head_node_size = 1 << head_bits;
+ m.array_node_size_log = array_bits;
+ m.array_node_size = 1 << array_bits;
+ return m;
+ }
+
+ template <typename T>
+ static bool check_node_alignment( T * p )
+ {
+ return (reinterpret_cast<uintptr_t>(p) & node_ptr::bitmask) == 0;
+ }
+
+ void destroy_tree()
+ {
+ // The function is not thread-safe. For use in dtor only
+ // Remove data node
+ clear();
+
+ //TODO: free all array nodes
+ }
+ //@endcond
+ };
+}} // namespace cds::intrusive
+
+#endif // #ifndef CDSLIB_INTRUSIVE_IMPL_MULTILEVEL_HASHSET_H
projects / libcds.git / commitdiff