I use libcds and they have an implementation of the Michael Hash map list and the Split list.
Based on the information that I collected from the document, here's how I implemented them:
includes:
#include <cds/map/michael_hash_map.h> #include <cds/map/split_ordered_list.h> using namespace cds;
code:
class TestDs { public: virtual bool containsKey(int key)=0; virtual int get(int key)=0; virtual int put(int key, int value)=0; virtual int remove(int key)=0; virtual int size()=0; virtual const char* name()=0; virtual void print()=0; virtual void shutdown()=0; };
code:
class Michael: public TestDs{ private: cds::map::MichaelHashMap<int,int,cds::map::pair_traits <int, int>, cds::map::type_traits, CDS_DEFAULT_ALLOCATOR> _ds; public: Michael(const Configuration& config) : _ds(config.initial_count,config.load_factor) { } bool containsKey(int key) { return (_ds.find(key)!=0); } int get(int key) { return _ds.find(key); } int put(int key, int value) { return _ds.insert(key,value); } int remove(int key) { return _ds.erase(key); } int size() { return _ds.size(); } const char* name() { return "Micheal"; } void print() {} void shutdown() {} };
AND:
class CDSSplit: public TestDs{ private: cds::map::SplitOrderedList<int,int,cds::map::pair_traits<int,int> ,cds::map::split_list::type_traits,CDS_DEFAULT_ALLOCATOR> _ds; public: CDSSplit(const Configuration& config) : _ds(config.initial_count, config.load_factor) { } bool containsKey(int key) { return (_ds.find(key)!=0); } int get(int key) { return _ds.find(key); } int put(int key, int value) { return _ds.insert(key,value); } int remove(int key) { return _ds.erase(key); } int size() { return _ds.size(); } const char* name() { return "CDSSPlit"; } void print() {} void shutdown() {} };
I run the structures by calling:
TestDs* _gTestDs1 = new Michael(_gConfiguration); TestDs* _gTestDs2 = new CDSSplit(_gConfiguration);
However, I get segmentation errors when CDSSplit is triggered or when Michael performs the first insertion.
The library is installed perfectly without warning, and I use other hash tables. I do not get any errors.
Thanks for any help
(Also posted with less detail on the discussion page for the library, but there doesn't seem to be much presence there, will post a message if something is posted there)
Compile flags: -std=c++0x -O3 -msse2 -m32 -DNDEBUG -DINTEL -g -D_REENTRANT -lrt -pthread -fno-strict-aliasing -l cds -l tbb -lllalloc
GDB Output:
Program received signal SIGSEGV, Segmentation fault. cds::ordered_list::details::michael_list::implementation<cds::gc::hzp_gc, cds::ordered_list::details::michael_list::adapter<cds::gc::hzp_gc, int, int, cds::map::pair_traits<int, int>, cds::ordered_list::type_traits, std::allocator<int> >, std::allocator<int> >::insert (this=0xafd42028, refHead=..., pNode=0x8440060) at /usr/include/cds/ordered_list/details/michael_list_hpgen.h:457 457 position pos( gc_base_class::getGC() ) ; (gdb) backtrace