text: #ifndef __nark_fast_hash_strmap2__
  #define __nark_fast_hash_strmap2__
  
  #include <string>
  
  #include <nark/config.hpp>
  #include "hash_common.hpp"
  #include  <boost/version.hpp>
  #if BOOST_VERSION < 103301
  # include <boost/limits.hpp>
  # include <boost/detail/limits.hpp>
  #else
  # include <boost/detail/endian.hpp>
  #endif
  #if !defined(BOOST_BIG_ENDIAN) && !defined(BOOST_LITTLE_ENDIAN)
      #error must define byte endian
  #endif
  #include <nark/util/byte_swap_impl.hpp>
  #include <nark/parallel_lib.hpp>
  #include <nark/fstring.hpp>
  
  // http://software.intel.com/en-us/articles/memcpy-performance
  //  This link mentioned memcpy may be optimized by hardware, Whether aligned or unaligned:
  //    hardware implementations which automatically switch into wide move modes
  //    would be more attractive than software support
  #define HSM_ENABLE_MY_memcpy
  
  namespace nark {
  	template<class LinkTp>
  	struct KeyIndexWithPrefix_tt {
  		LinkTp offset;
  		LinkTp length;
  		LinkTp prefix; // string prefix, for optimize CPU Cache
  		LinkTp idx; // index to pNodes
  	};
  
  	template<class LinkTp, class LinkT2, class Value>
  	struct NodeWithPrefix_tt {
  		LinkTp offset;
  		LinkTp length;
  		LinkT2 prefix; // string prefix, for optimize CPU Cache
  		Value  value;
  	};
  } // namespace nark
  
  namespace std {
  	template<class LinkTp>
  	inline void swap(nark::KeyIndexWithPrefix_tt<LinkTp>& x,
  					 nark::KeyIndexWithPrefix_tt<LinkTp>& y)
  	{
  		std::swap(x.offset, y.offset);
  		std::swap(x.length, y.length);
  		std::swap(x.prefix, y.prefix);
  		std::swap(x.idx, y.idx);
  	}
  	template<class LinkTp, class LinkT2, class Value>
  	inline void swap(nark::NodeWithPrefix_tt<LinkTp, LinkT2, Value>& x,
  					 nark::NodeWithPrefix_tt<LinkTp, LinkT2, Value>& y)
  	{
  		std::swap(x.offset, y.offset);
  		std::swap(x.length, y.length);
  		std::swap(x.prefix, y.prefix);
  		std::swap(x.value, y.value);
  	//	boost::swap(x.value, y.value); // Arguments Dependent Lookup
  	}
  } // namespace std
  
  namespace nark {
  
  struct fstring_hash_equal
    : hash_and_equal<fstring, fstring_func::hash, fstring_func::equal> {};
  struct fstring_hash_equal_align
    : hash_and_equal<fstring, fstring_func::hash_align, fstring_func::equal_align> {};
  struct fstring_hash_equal_unalign
    : hash_and_equal<fstring, fstring_func::hash_unalign, fstring_func::equal_unalign> {};
  
  struct ByteWiseKeyCompare {
  	const char* ps;
  	template<class TWithPrefix>
  	bool operator()(const TWithPrefix& x, const TWithPrefix& y) const {
  		enum { prefix_len = sizeof(x.prefix) };
  		if (x.prefix < y.prefix) return true;
  		if (y.prefix < x.prefix) return false;
  		if (x.length <= prefix_len || y.length <= prefix_len)
  				return x.length < y.length;
  		fstring sx(ps+LOAD_OFFSET(x.offset)+prefix_len, x.length-prefix_len);
  		fstring sy(ps+LOAD_OFFSET(y.offset)+prefix_len, y.length-prefix_len);
  		return fstring_func::IF_SP_ALIGN(less_align, less_unalign)()(sx, sy);
  	}
  	ByteWiseKeyCompare(const char* ps) : ps(ps) {}
  };
  
  // LinkTp is also offset-type
  template<class LinkTp, class Value, class ValuePlace>
  struct hash_strmap_node;
  template<class LinkTp, class Value>
  struct hash_strmap_node<LinkTp, Value, ValueOut> {
  	LinkTp offset; // offset to string pool
  	LinkTp link;   // link
  };
  template<class LinkTp, class Value>
  struct hash_strmap_node<LinkTp, Value, ValueInline> {
  	LinkTp offset; // offset to string pool
  	LinkTp link;   // link
  	Value  value;
  };
  
  //
  // hash_strmap<> hset; // just a set, can be used as a string pool
  //
  template< class Value = ValueOut // ValueOut means empty value, just like a set
  		, class HashFunc = fstring_func::IF_SP_ALIGN(hash_align, hash)
  		, class KeyEqual = fstring_func::IF_SP_ALIGN(equal_align, equal)
  		, class ValuePlace = typename boost::mpl::if_c<
  					!boost::is_empty<Value>::value && // ValueInline should be non-empty
  					sizeof(Value) % sizeof(intptr_t) == 0 && sizeof(Value) <= 32
  				, ValueInline
  				, ValueOut // If Value is empty, ValueOut will not use memory
  			>::type
  		, class CopyStrategy = FastCopy
  		, class LinkTp = unsigned int // could be unsigned short for small map
  		, class HashTp = HSM_HashTp
  		>
  class hash_strmap : dummy_bucket<LinkTp>
  {
  protected:
  	struct ValueRaw {
  		char block[sizeof(Value)];
  	};
  	typedef hash_strmap_node<LinkTp, Value, ValuePlace> Node;
  
  	using dummy_bucket<LinkTp>::tail;
  	using dummy_bucket<LinkTp>::delmark; // tail-1
  	using dummy_bucket<LinkTp>::maxlink; // tail-2, all link must < maxlink
  	static const size_t maxoffset =	tail * size_t(sizeof(LinkTp) < sizeof(size_t) ? SP_ALIGN : 1);
  	static const intptr_t hash_cache_disabled = 8; // good if compiler aggressive optimize
  
  	Node*   pNodes;
  	LinkTp  nNodes;   // hard limit is maxlink, even in 64bit platform
  	LinkTp  maxNodes; // hard limit is maxlink
  	LinkTp  maxload;  // hard limit is maxlink, guard for calling rehash
  	LinkTp  nDeleted;
  	HashTp* pHash;   // array of cached hash value
  
  	LinkTp* bucket;  // index to pNodes
  	size_t  nBucket; // could be larger up to 4G-1 when size_t is 32 bits
                       // and more when size_t is 64 bits
  
  	char*    strpool;
  	size_t   lenpool;
  	size_t   maxpool;  // hard limit is maxoffset
  	size_t   freepool; // free pool size
  
  	Value*   values;   // when value out
  
      struct FreeLink {
          LinkTp  next;
      };
  	struct FreeList {
  		LinkTp  head;
  		LinkTp  llen; ///< list length
          size_t  freq;
          FreeList() : head(tail), llen(0), freq(0) {}
  	};
  	ptrdiff_t fastleng;
  	FreeList* fastlist;
      FreeList  hugelist;
  	static const ptrdiff_t freelist_disabled = -1;
  
  	double   load_factor;
  	enum sort_type {
  		en_unsorted,
  		en_sort_by_key,
  		en_sort_by_val
  	} sort_flag;
  
  	HashFunc hash;
  	KeyEqual equal;
  
      template<class T>
      T* t_malloc(size_t count) {
          return (T*)malloc(sizeof(T) * count);
      }
      template<class T>
      T* t_realloc(T* p, size_t count) {
          return (T*)realloc(p, sizeof(T) * count);
      }
  
      void init() {
  		pNodes = NULL;
  		nNodes = 0;
  		maxNodes = 0;
  		maxload = 0;
  		nDeleted = 0;
  		pHash = NULL; // default enabled
  
  		bucket = const_cast<LinkTp*>(&tail); // false start
  		nBucket = 1;
  
  		strpool = NULL;
  		lenpool = 0;
  		maxpool = 0;
  		freepool = 0;
  
  		values = NULL;
  		fastleng = freelist_disabled;
  		fastlist = NULL;
          hugelist = FreeList();
  
  		load_factor = 0.3;
  		sort_flag = en_unsorted;
  
  //		enable_freelist(256);
  	}
  
  	Value& nth_value(size_t nth, ValueInline) const { return pNodes[nth].value; }
  	Value& nth_value(size_t nth, ValueOut   ) const { return values[nth]; }
  	Value& nth_value(size_t nth) const { return nth_value(nth, ValuePlace()); }
  
  	Value& nth_value(Node* pn, Value*, size_t nth, ValueInline) const { return pn[nth].value; }
  	Value& nth_value(Node*, Value* pv, size_t nth, ValueOut   ) const { return pv[nth]; }
  	Value& nth_value(Node* pn, Value* pv, size_t nth) const {
          return nth_value(pn, pv, nth, ValuePlace());
      }
  
  public:
  	static size_t extralen(const char* ps, size_t End) { return ps[End-1] + 1; }
  	size_t extralen(size_t End) const { return strpool[End-1] + 1; }
  
  private:
  	void move_value_on_raw(Node*, Node*, Value* vdest, Value* vsrc, ValueOut) {
  		CopyStrategy::move_cons(vdest, *vsrc);
  	}
  	void move_value_on_raw(Node* dest, Node* src, Value*, Value*, ValueInline) {
  		CopyStrategy::move_cons(&dest->value, src->value);
  	}
      void move_value_on_raw(Node* dest, Node* src, Value* vdest, Value* vsrc) {
          move_value_on_raw(dest, src, vdest, vsrc, ValuePlace());
      }
  
  	size_t allnodes_size(size_t n) const {
  		// guard offset used for compute strlen of pNodes[nNodes-1]
  		// guard link   used for speedup next_i
  		size_t s = sizeof(Node) * n + sizeof(pNodes->offset) + sizeof(pNodes->link);
  		return (s + 15) & (size_t)ptrdiff_t(~15); // align to 16
  	}
  
  	void reserve_nodes_impl(size_t cap, SafeCopy, ValueInline) {
  		Node* pn = (Node*)malloc(allnodes_size(cap));
  		if (NULL == pn) throw std::bad_alloc();
  		if (pNodes) {
  			Node* oldpn = pNodes;
  			if (nDeleted) {
  				for (size_t i = 0, n = nNodes; i < n; ++i) {
                      pn[i].offset = oldpn[i].offset;
                      pn[i].link = oldpn[i].link;
  					if (delmark != oldpn[i].link)
                          CopyStrategy::move_cons(&pn[i].value, oldpn[i].value);
                  }
  			} else {
  				for (size_t i = 0, n = nNodes; i < n; ++i) {
                      pn[i].offset = oldpn[i].offset;
                      pn[i].link = oldpn[i].link;
                      CopyStrategy::move_cons(&pn[i].value, oldpn[i].value);
                  }
  			}
  			free(oldpn);
  		}
  		pn[nNodes].offset = SAVE_OFFSET(lenpool);
  		pn[nNodes].link = tail; // guard for next_i
  		pNodes = pn;
  	}
  	void reserve_nodes_impl(size_t cap, SafeCopy, ValueOut) {
  		Node* pn = (Node*)realloc(pNodes, allnodes_size(cap));
  		if (NULL == pn) throw std::bad_alloc();
  		if (!is_value_empty) {
  			Value* pv = (Value*)malloc(sizeof(Value) * cap);
  			if (NULL == pv) throw std::bad_alloc();
  			if (values) {
  				Value* oldpv = values;
  				if (nDeleted) {
  					for (size_t i = 0, n = nNodes; i < n; ++i)
  						if (delmark != pn[i].link)
                              CopyStrategy::move_cons(pv+i, oldpv[i]);
  				} else {
  					for (size_t i = 0, n = nNodes; i < n; ++i)
                          CopyStrategy::move_cons(pv+i, oldpv[i]);
  				}
  				free(oldpv);
  			}
  			values = pv;
  		}
  		if (NULL == pNodes) {
  			pn[0].offset = 0;
  			pn[0].link = tail; // guard for next_i
  		}
  		pNodes = pn;
  	}
  	// This is the normal case:
  	void reserve_nodes_impl(size_t cap, FastCopy, ValueInline) {
  		Node* pn = (Node*)realloc(pNodes, allnodes_size(cap));
  		if (NULL == pn) throw std::bad_alloc();
  		if (NULL == pNodes) {
  			pn[0].offset = 0;
  			pn[0].link = tail; // guard for next_i
  		}
  		pNodes = pn;
  	}
  	void reserve_nodes_impl(size_t cap, FastCopy, ValueOut) {
  		Node* pn = (Node*)realloc(pNodes, allnodes_size(cap));
  		if (NULL == pn) throw std::bad_alloc();
  		if (!is_value_empty) {
  			Value* pv = (Value*)realloc(values, sizeof(Value) * cap);
  			if (NULL == pv) {
  				pNodes = pn; // maxNodes unchanged
  				throw std::bad_alloc();
  			}
  			values = pv;
  		}
  		if (NULL == pNodes) {
  			pn[0].offset = 0;
  			pn[0].link = tail; // guard for next_i
  		}
  		pNodes = pn;
  	}
  
  	void relink_impl(bool bFillHash) {
  		assert(0 == nDeleted);
          assert(0 == freepool);
  		LinkTp* pb = bucket;
  		Node*   pn = pNodes;
  		size_t  nb = nBucket;
  
  		// (LinkTp)tail is just used for coerce tail be passed by value
  		// otherwise, tail is passed by reference, this cause g++ link error
  		std::fill_n(pb, nb, (LinkTp)tail);
  
  		if (intptr_t(pHash) == hash_cache_disabled) {
  			for (size_t j = 0, n = nNodes; j < n; ++j) {
  				size_t ib = size_t(hash(key(j)) % nb);
  				pn[j].link = pb[ib];
  				pb[ib] = LinkTp(j);
  			}
  		}
  		else if (bFillHash) {
  			HashTp* ph = pHash;
  			for (size_t j = 0, n = nNodes; j < n; ++j) {
                  HashTp hh = hash(key(j));
  				size_t ib = size_t(hh % nb);
  				pn[j].link = pb[ib];
                  ph[j] = hh;
  				pb[ib] = LinkTp(j);
  			}
  		}
          else {
  			const HashTp* ph = pHash;
  			for (size_t j = 0, n = nNodes; j < n; ++j) {
  				size_t ib = size_t(ph[j] % nb);
  				pn[j].link = pb[ib];
  				pb[ib] = LinkTp(j);
  			}
          }
  	}
  
  	void relink() { relink_impl(false); }
  	void relink_fill() { relink_impl(true); }
  
  	void destroy() {
          if (fastlist)
              free(fastlist);
  		if (pNodes) {
  			if (!boost::has_trivial_destructor<Value>::value) {
  				for (size_t i = nNodes; i > 0; --i)
  					if (pNodes[i-1].link != delmark)
  						nth_value(i-1).~Value();
  			}
  			free(pNodes);
  		}
  		if (pHash && intptr_t(pHash) != hash_cache_disabled)
  			free(pHash);
  		if (bucket && &tail != bucket)
  			free(bucket);
  		if (strpool)
  			free(strpool);
  		if (ValuePlace::is_value_out && !is_value_empty && values)
  			free(values);
  	}
  
  public:
  	class iterator {
  	public:
  		typedef Value		  mapped_type;
  		typedef hash_strmap*  OwnerPtr;
  	#define ClassIterator iterator
  	#include "hash_strmap_iterator.hpp"
  	};
  	class const_iterator {
  	public:
  		const_iterator(const iterator& y)
  		  : owner(y.get_owner()), index(y.get_index()) {}
  		typedef const Value         mapped_type;
  		typedef const hash_strmap*  OwnerPtr;
  	#define ClassIterator const_iterator
  	#include "hash_strmap_iterator.hpp"
  	};
  
  	typedef std::reverse_iterator<iterator> reverse_iterator;
  	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  
  	typedef typename iterator::difference_type difference_type;
  	typedef typename iterator::size_type  size_type;
  	typedef typename iterator::value_type value_type;
  	typedef typename iterator::reference  reference;
  
  	typedef const fstring key_type;
  	typedef Value mapped_type;
  
  	static const bool is_value_empty = boost::is_empty<Value>::value;
  	typedef boost::mpl::bool_< // CPU cache line is often 64
  		(ValuePlace::is_value_out && !is_value_empty) || (sizeof(Node) > 64)
  	> sort_by_index;
  	typedef boost::mpl::false_ sort_by_index_no;
  	typedef boost::mpl::true_  sort_by_index_yes;
  
  public:
  	explicit hash_strmap(HashFunc hashfn = HashFunc(), KeyEqual equalfn = KeyEqual())
  	  : hash(hashfn), equal(equalfn) {
  		init();
  	}
  	explicit hash_strmap(size_t cap, HashFunc hashfn = HashFunc(), KeyEqual equalfn = KeyEqual())
  	  : hash(hashfn), equal(equalfn) {
  		init();
  		rehash(cap);
  	}
  	hash_strmap(const hash_strmap& y)
  	  : hash(y.hash), equal(y.equal) {
  		pNodes = NULL;
  		nNodes = freelist_disabled==y.fastleng ? y.nNodes-y.nDeleted : y.nNodes;
  		maxNodes = y.nNodes;
  		maxload = y.maxload;
  		nBucket = y.nBucket;
  		nDeleted = 0;
  		pHash = NULL;
  
  		strpool = NULL;
  		lenpool = y.lenpool;
  		maxpool = y.lenpool;
  		freepool = y.freepool;
  
  		load_factor = y.load_factor;
  		sort_flag = y.sort_flag;
  		values = NULL;
  		fastleng = y.fastleng;
  		fastlist = NULL;
  		hugelist = y.hugelist;
  
  		if (0 == nNodes) { // empty
  			nBucket = 1;
  			maxload = 0;
  			bucket  = const_cast<LinkTp*>(&tail);
  			if (intptr_t(y.pHash) == hash_cache_disabled)
  				pHash = (HashTp*)(hash_cache_disabled);
  			return; // not need to do deep copy
  		}
  		bucket = (LinkTp*)malloc(sizeof(LinkTp) * y.nBucket);
  		if (NULL == bucket) {
  			throw std::bad_alloc();
  		}
  		pNodes = (Node*)malloc(allnodes_size(nNodes));
  		if (NULL == pNodes) {
  			free(bucket);
  			init(); // reset to safe state
  			throw std::bad_alloc();
  		}
  		if (intptr_t(y.pHash) == hash_cache_disabled) {
  			pHash = (HashTp*)(hash_cache_disabled);
  		}
  		else {
  			pHash = (HashTp*)malloc(sizeof(HashTp) * nNodes);
  			if (NULL == pHash) {
  				free(pNodes);
  				free(bucket);
  				init(); // reset to safe state
  				throw std::bad_alloc();
  			}
  		}
  		strpool = (char*)malloc(y.lenpool);
  		if (NULL == strpool) {
  			if (intptr_t(pHash) != hash_cache_disabled) free(pHash);
  			free(pNodes);
  			free(bucket);
  			init(); // reset to safe state
  			throw std::bad_alloc();
  		}
  		if (ValuePlace::is_value_out &&	!is_value_empty) {
  			values = (Value*)malloc(sizeof(Value) * nNodes);
  			if (NULL == values) {
  				if (intptr_t(pHash) != hash_cache_disabled) free(pHash);
  				free(strpool);
  				free(pNodes);
  				free(bucket);
  				init(); // reset to safe state
  				throw std::bad_alloc();
  			}
  		}
  		if (freelist_disabled != fastleng) {
  			fastlist = (FreeList*)malloc(sizeof(FreeList) * fastleng);
  			if (NULL == fastlist) {
  				if (NULL != values) free(values);
  				if (intptr_t(pHash) != hash_cache_disabled) free(pHash);
  				free(strpool);
  				free(pNodes);
  				free(bucket);
  				init(); // reset to safe state
  				throw std::bad_alloc();
  			}
  			memcpy(fastlist, y.fastlist, sizeof(FreeList) * fastleng);
  		}
  		if (0 == y.nDeleted || freelist_disabled != fastleng) {
  			if (intptr_t(pHash) != hash_cache_disabled)
  				memcpy(pHash, y.pHash, sizeof(HashTp) * nNodes);
  			memcpy(strpool, y.strpool, sizeof(char) * lenpool);
  			memcpy(bucket , y.bucket , sizeof(LinkTp) * nBucket);
  			if (0 == y.nDeleted || CopyStrategy::is_fast_copy) {
  				std::uninitialized_copy(y.pNodes, y.pNodes + nNodes, pNodes);
  				if (ValuePlace::is_value_out &&	!is_value_empty)
  					std::uninitialized_copy(y.values, y.values + nNodes, values);
  			}
  			else {
  				for (size_t i = 0, n = y.nNodes; i < n; ++i) {
  					pNodes[i].offset = y.pNodes[i].offset;
  					pNodes[i].link = y.pNodes[i].link;
  					if (delmark != y.pNodes[i].link)
  						   new(&nth_value(i))Value(y.nth_value(i));
  				}
  			}
  			pNodes[nNodes].offset = SAVE_OFFSET(lenpool);
  			pNodes[nNodes].link = tail;
  			return;
  		}
  		size_t j = 0;
  		// could compiler don't generate code the try ... catch if
  		// it would not throw exceptions by static analysis?
  		try {
  			const Node* ypn = y.pNodes;
  			size_t n = y.nNodes;
  			size_t loffset = 0;
  			for (size_t i = 0; i < n; ++i) {
  				if (ypn[i].link != delmark) {
  					pNodes[j].offset = SAVE_OFFSET(loffset);
  					if (intptr_t(pHash) != hash_cache_disabled)
  						pHash[j] = y.pHash[i];
  					new(&nth_value(j))Value(y.nth_value(i));
  					size_t beg2 = LOAD_OFFSET(ypn[i+0].offset);
  					size_t end2 = LOAD_OFFSET(ypn[i+1].offset);
  					size_t len2 = end2 - beg2;
  					memcpy(strpool + loffset, y.strpool + beg2, len2);
  					loffset += len2;
  					++j;
  				}
  			}
  			assert(j == nNodes);
  			pNodes[j].offset = SAVE_OFFSET(loffset);
  			pNodes[j].link = tail;
  			lenpool = loffset;
  			relink();
  		}
  		catch (...) {
  			if (!boost::has_trivial_destructor<Value>::value) {
  				while (j > 0) // roll back
  					nth_value(j-1).~Value(), --j;
  			}
  			if (ValuePlace::is_value_out && !is_value_empty) {
  				assert(NULL != values);
  				free(values);
  			}
  			free(bucket);
  			free(pNodes);
  			free(strpool);
  			init(); // reset to safe state
  			throw;
  		}
  	}
  	hash_strmap& operator=(const hash_strmap& y) {
  		if (this != &y) {
  		#if 1 // prefer performance, std::map is in this manner
  		// this is exception-safe but lose old content of *this on exception
  			this->destroy();
  			new(this)hash_strmap(y);
  		#else // exception-safe, but take more peak memory
  			hash_strmap(y).swap(*this);
  		#endif
  		}
  		return *this;
  	}
  	~hash_strmap() { destroy(); }
  
  	void swap(hash_strmap& y) {
  		std::swap(pNodes  , y.pNodes);
  		std::swap(nNodes  , y.nNodes);
  		std::swap(maxNodes, y.maxNodes);
  		std::swap(maxload , y.maxload);
  		std::swap(nDeleted, y.nDeleted);
  		std::swap(pHash   , y.pHash);
  
  		std::swap(nBucket , y.nBucket);
  		std::swap(bucket  , y.bucket);
  
  		std::swap(strpool , y.strpool);
  		std::swap(lenpool , y.lenpool);
  		std::swap(maxpool , y.maxpool);
  		std::swap(freepool, y.freepool);
  
          std::swap(values  , y.values);
          std::swap(fastleng, y.fastleng);
          std::swap(fastlist, y.fastlist);
          std::swap(hugelist, y.hugelist);
  
  		std::swap(load_factor, y.load_factor);
  		std::swap(sort_flag, y.sort_flag);
  		std::swap(hash     , y.hash);
  		std::swap(equal    , y.equal);
  	}
  
  	fstring whole_strpool() const { return fstring(strpool, lenpool); }
  
  	void clear() {
  		destroy();
  		init();
  	}
  
  	// erase all key-values, but keep memory, don't free
  	void erase_all() {
  		if (nDeleted && fastlist) {
  			assert(freelist_disabled != fastleng);
  			std::fill_n(fastlist, fastleng, FreeList());
  			hugelist = FreeList();
  		}
  		if (!boost::has_trivial_destructor<Value>::value) {
  			if (nDeleted) {
  				for (size_t i = 0; i < nNodes; ++i)
  					if (delmark != pNodes[i].link)
  						nth_value(i).~Value();
  			} else {
  				for (size_t i = 0; i < nNodes; ++i)
  					nth_value(i).~Value();
  			}
  		}
  		if (nNodes) {
  			assert(const_cast<LinkTp*>(&tail) != bucket);
  			std::fill_n(bucket, nBucket, (LinkTp)tail);
  		}
  		nNodes = 0;
  		lenpool = 0;
  	}
  
  	void shrink_to_fit() {
  		// before calling this function,
  		//   the class-invariant(pHash/pLink relation) may not satisfied
  		//   such as in this->erase_if..
  		if (nDeleted)
  			revoke_deleted_no_relink();
  		if (0 == nNodes) {
  			clear();
  			return;
  		}
  		if (maxpool != lenpool) {
  			strpool = (char*)realloc(strpool, lenpool); // never fail
  			maxpool = lenpool;
  		}
  		reserve_nodes(nNodes);
  		if (NULL != bucket)
  			rehash(size_t(nNodes / load_factor + 1));
  	}
  
  	// very risky, you must know what you are doing
  	void risk_steal_key_val_and_clear(char** pool, Value** vals) {
  		BOOST_STATIC_ASSERT(ValuePlace::is_value_out); // must be ValueOut
  		assert(pNodes);
  		::free(pNodes);
  		if (bucket && bucket != &tail)
  			::free(bucket);
  		if (pHash && intptr_t(pHash) != hash_cache_disabled)
  			::free(pHash);
  		*pool = strpool;
  		*vals = values;
  		init();
  	}
  
  	// Keep required memory for iteration, free all other memory
  	// after calling this function, just iteration function could be called
  	void risk_disable_hash() {
  		shrink_to_fit();
  		// just keep strpool + data + pNodes
  		if (bucket) {
  			if (bucket != &tail)
  				::free(bucket);
  			bucket = NULL;
  		}
  	//	disable_hash_cache(); // ? OR:
  		if (intptr_t(pHash) == hash_cache_disabled)
  		{}
  		else if (NULL != pHash)
  			::free(pHash), pHash = NULL;
  	//	if (pLink) // has no pLink
  	//		::free(pLink), pLink = NULL;
  	}
  
  	void risk_enable_hash() {
  		if (NULL == bucket)
  			bucket = &tail;
  		if (NULL == pHash) {
  			pHash = hash_cache_disabled;
  			enable_hash_cache();
  		}
  		rehash(nNodes/load_factor);
  	}
  
  	void rehash(size_t newBucketSize) {
  		newBucketSize = __hsm_stl_next_prime(newBucketSize);
  		if (newBucketSize != nBucket) {
  			// shrink or enlarge
  			if (bucket != &tail) {
  				free(bucket);
  			}
  			bucket = (LinkTp*)malloc(sizeof(LinkTp) * newBucketSize);
  			if (NULL == bucket) { // how to handle?
  				assert(0); // immediately fail on debug mode
  				clear();
  				throw std::runtime_error("rehash failed, unrecoverable");
  			//	throw std::runtime_error("rehash failed");
  			}
  			nBucket = newBucketSize;
  			relink();
  			using namespace std;
  			maxload = LinkTp(min<double>(newBucketSize*load_factor, maxlink));
  		}
  	}
  //	void resize(size_t n) { rehash(n); }
  
  	// with rehash
  	void reserve(size_t cap) {
  		assert(cap >= nNodes);
  		if (cap < nNodes)
  			throw std::runtime_error(
  		"hash_strmap::reserve(cap), cap is less than nNodes"
  				);
  		if (cap > maxlink)
  			cap = maxlink;
  		reserve_nodes(cap);
  		rehash(size_t(cap / load_factor + 1));
  	}
  
  	// with rehash
  	void reserve(size_t cap, size_t poolcap) {
  		assert(cap >= nNodes);
  		if (cap < nNodes)
  			throw std::runtime_error(
  		"hash_strmap::reserve(cap,poolcap), cap is less than nNodes"
  			);
  		if (poolcap < lenpool)
  			throw std::runtime_error(
  		"hash_strmap::reserve(cap,poolcap), poolcap is less than lenpool"
  			);
  // commented, because strpool realloc is cheap, Value realloc may expense,
  // reserve more Value space may get benefit
  //		if (poolcap < IF_SP_ALIGN(LOAD_OFFSET(1), 2) * cap)
  //			throw std::logic_error(
  //"hash_strmap::reserve(cap,poolcap), poolcap is less than cap expected"
  //			);
  		if (cap > maxlink)
  			cap = maxlink;
  		reserve_strpool(poolcap);
  		reserve_nodes(cap);
  		rehash(size_t(cap / load_factor + 1));
  	}
  
  	// just enlarge/shrink strpool
  	void reserve_strpool(size_t poolcap) {
  		assert(poolcap >= lenpool);
  		if (poolcap < lenpool)
  			throw std::runtime_error(
  		"hash_strmap::reserve_strpool(poolcap), poolcap is less than lenpool"
  			);
  		char* ps = (char*)realloc(strpool, poolcap);
  		if (NULL == ps)
  			throw std::bad_alloc();
  		strpool = ps;
  		maxpool = poolcap;
  	}
  
  	// without rehash
  	void reserve_nodes(size_t cap) {
  		assert(cap >= nNodes);
  		if (cap < nNodes)
  			throw std::runtime_error(
  		"hash_strmap::reserve_nodes(cap), cap is less than nNodes"
  			);
  		if (freelist_disabled == fastleng)
  			revoke_deleted();
  		if (cap > maxlink)
  			cap = maxlink;
  		if (cap != (size_t)maxNodes) {
  			if (intptr_t(pHash) != hash_cache_disabled) {
  				HashTp* ph = (HashTp*)realloc(pHash, sizeof(HashTp) * cap);
  				if (NULL == ph)
  					throw std::bad_alloc();
  				pHash = ph;
  			}
  			reserve_nodes_impl(cap, CopyStrategy(), ValuePlace());
  			maxNodes = LinkTp(cap);
  		}
  	}
  
  	void set_load_factor(double fact) {
  		if (fact >= 0.999) {
  			throw std::logic_error("load factor must <= 0.999");
  		}
  		load_factor = fact;
  		using namespace std;
  		maxload = &tail == bucket ? 0
  				: LinkTp(min<double>(nBucket * fact, maxlink));
  	}
  	double get_load_factor() const { return load_factor; }
  
  	HashTp hash_value(size_t i) const {
  		assert(i < nNodes);
  		if (intptr_t(pHash) == hash_cache_disabled)
  			return hash(key(i));
  		else
  			return pHash[i];
  	}
  
  	bool is_hash_cached() const {
  		return intptr_t(pHash) != hash_cache_disabled;
  	}
  
  	void enable_hash_cache() {
  		if (intptr_t(pHash) == hash_cache_disabled) {
  			if (0 == maxNodes) {
  				pHash = NULL;
  			}
  			else {
  				HashTp* ph = (HashTp*)malloc(sizeof(HashTp) * maxNodes);
  				if (NULL == ph) {
  					throw std::bad_alloc();
  				}
  				size_t  n = nNodes;
  				Node*  pn = pNodes;
  				if (0 == nDeleted) {
  					for (size_t i = 0; i < n; ++i)
  						ph[i] = hash(key(i));
  				}
  				else {
  					for (size_t i = 0; i < n; ++i)
  						if (delmark != pn[i].link)
  							ph[i] = hash(key(i));
  				}
  				pHash = ph;
  			}
  		}
  		assert(NULL != pHash || 0 == maxNodes);
  	}
  
  	void disable_hash_cache() {
  		if (intptr_t(pHash) == hash_cache_disabled)
  			return;
  		if (pHash)
  			free(pHash);
  		pHash = (HashTp*)(hash_cache_disabled);
  	}
  
  	size_t total_key_size() const { return lenpool; }
  	bool    empty() const { return nNodes== nDeleted; }
  	size_t   size() const { return nNodes - nDeleted; }
  	size_t  end_i() const { return nNodes; }
  	size_t  beg_i() const {
  	//	return next_i(intptr_t(-1)); assertion will fail in next_i
  	//	because size_t is unsigned, so write the code below
  	//	this code produce same result as next_i(intptr_t(-1))
  	   	const Node* pn = pNodes;
  		if (NULL == pn) return 0;
  	   	size_t i = 0;
  	   	while (delmark == pn[i].link)
  			++i;
  		return i;
  	}
  	size_t rbeg_i() const { return nDeleted == nNodes ? 0 : nNodes; }
  	size_t rend_i() const { return 0; }
  	size_t delcnt() const { return nDeleted; }
  
  	std::pair<size_t, bool> insert_i(const std::pair<fstring, Value>& kv) {
  		return insert_i(kv.first, kv.second);
  	}
  
  	Value& operator[](const fstring key) {
  		std::pair<size_t, bool> ib = insert_i(key, Value());
  		return nth_value(ib.first, ValuePlace());
  	}
  #if 1
  	const Value& operator[](const fstring key) const {
  		const size_t i = find_i(key);
  		if (i == nNodes) {
  			std::string msg;
  			msg.append("hash_strmap::operator[] const: key=\"");
  			msg.append(key.p, key.n);
  			msg.append("\" doesn't exist");
  			throw std::logic_error(msg);
  		}
  		return nth_value(i, ValuePlace());
  	}
  #endif
  	const Value& val(size_t idx) const {
  		HSM_SANITY(nNodes >= 1);
  		assert(idx < nNodes);
  		return nth_value(idx, ValuePlace());
  	}
  	Value& val(size_t idx) {
  		HSM_SANITY(nNodes >= 1);
  		assert(idx < nNodes);
  		return nth_value(idx, ValuePlace());
  	}
  
  	const Value& end_val(size_t idxEnd) const {
  		HSM_SANITY(nNodes >= 1);
  		assert(idxEnd <= nNodes);
  		size_t idx = nNodes - idxEnd;
  		return nth_value(idx, ValuePlace());
  	}
  	Value& end_val(size_t idxEnd) {
  		HSM_SANITY(nNodes >= 1);
  		assert(idxEnd <= nNodes);
  		size_t idx = nNodes - idxEnd;
  		return nth_value(idx, ValuePlace());
  	}
  
  	      iterator  begin()       { return       iterator(this, beg_i()); }
  	const_iterator  begin() const { return const_iterator(this, beg_i()); }
  	const_iterator cbegin() const { return const_iterator(this, beg_i()); }
  
  	      iterator  end()       { return       iterator(this, nNodes); }
  	const_iterator  end() const { return const_iterator(this, nNodes); }
  	const_iterator cend() const { return const_iterator(this, nNodes); }
  
  	      reverse_iterator  rbegin()       { return       reverse_iterator(end()); }
  	const_reverse_iterator  rbegin() const { return const_reverse_iterator(end()); }
  	const_reverse_iterator crbegin() const { return const_reverse_iterator(end()); }
  
  	      reverse_iterator  rend()       { return       reverse_iterator(begin()); }
  	const_reverse_iterator  rend() const { return const_reverse_iterator(begin()); }
  	const_reverse_iterator crend() const { return const_reverse_iterator(begin()); }
  
  	std::pair<iterator, bool>
  	insert(const std::pair<const fstring, Value>& kv) {
  		std::pair<size_t, bool> ib = insert_i(kv);
  		return std::pair<iterator, bool>(iterator(this, ib.first), ib.second);
  	}
  	      iterator find(fstring key)       { return       iterator(this, find_i(key)); }
  	const_iterator find(fstring key) const { return const_iterator(this, find_i(key)); }
  	      iterator find(const char* key, size_t len)       { return find(fstring(key, len)); }
  	const_iterator find(const char* key, size_t len) const { return find(fstring(key, len)); }
  
  	// return erased element count
  	size_t erase(const fstring key) {
  		assert(key.n >= 0);
  		HashTp h = hash(key);
  		size_t i = size_t(h % nBucket);
  		for (LinkTp p = bucket[i]; tail != p; p = pNodes[p].link) {
  			HSM_SANITY(p < nNodes);
  			const Node* y = &pNodes[p];
  			HSM_SANITY(y[0].offset < y[1].offset);
  			HSM_SANITY(y[1].offset <= SAVE_OFFSET(maxpool));
  		// doesn't need to compare cached hash value, it almost always true
  			size_t ybeg = LOAD_OFFSET(y[0].offset);
  			size_t yend = LOAD_OFFSET(y[1].offset);
  			size_t ylen = yend - ybeg - extralen(yend);
  			if (equal(key, fstring(strpool + ybeg, ylen))) {
  				erase_i_impl(p, h);
  				return 1;
  			}
  		}
  		return 0;
  	}
  
  	void erase(iterator iter) {
  		assert(iter.get_owner() == this);
  		assert(iter.get_index() < nNodes);
  		erase_i(iter.get_index());
  	}
  
  private:
  	template<class Predictor>
  	size_t erase_if_kv_impl(Predictor pred) {
  		assert(intptr_t(pHash) == hash_cache_disabled || NULL != pHash);
  		HashTp*ph = pHash;
  		Value* pv = values;
  		Node*  pn = pNodes;
  		char*  ps = strpool;
  		size_t  n = nNodes;
  		size_t  i = 0;
  		size_t  loffset;
  		if (0 == nDeleted) {
  			for (; i < n; ++i) {
  				HSM_SANITY(pn[i+0].offset < pn[i+1].offset);
  				HSM_SANITY(pn[i+1].offset <= SAVE_OFFSET(maxpool));
  				const size_t  mybeg = LOAD_OFFSET(pn[i+0].offset);
  				const size_t  myend = LOAD_OFFSET(pn[i+1].offset);
  				const size_t  mylen = myend - mybeg;
  				const size_t  extra = extralen(myend);
  				const fstring mykey(ps + mybeg, mylen-extra);
  				Value& myval = nth_value(pn, pv, i); // non-const
  				if (pred(mykey, myval))
  					goto DoErase1;
  			}
  			return 0;
  		DoErase1:
  			nth_value(pn, pv, i).~Value();
  			loffset = LOAD_OFFSET(pn[i].offset); // begin of first deleted
  			for (size_t j = i+1; j < n; ++j) {
  				HSM_SANITY(pn[j+0].offset < pn[j+1].offset);
  				HSM_SANITY(pn[j+1].offset <= SAVE_OFFSET(maxpool));
  				const size_t  mybeg = LOAD_OFFSET(pn[j+0].offset);
  				const size_t  myend = LOAD_OFFSET(pn[j+1].offset);
  				const size_t  mylen = myend - mybeg;
  				const size_t  extra = extralen(myend);
  				const fstring mykey(ps + mybeg, mylen-extra);
  				Value& myval = nth_value(pn, pv, j); // non-const
  				if (pred(mykey, myval))
  					nth_value(pn, pv, j).~Value(); // destruct
  				else {
  					pn[i].offset = SAVE_OFFSET(loffset);
  					move_value_on_raw(pn+i, pn+j, pv+i, pv+j);
  					memcpy(ps + loffset, ps + mybeg, mylen);
  					if (intptr_t(ph) != hash_cache_disabled)
  						ph[i] = ph[j];
  					loffset += mylen;
  					++i;
  				}
  			}
  		}
  		else { // 0 != nDeleted
  			for (; i < n; ++i) {
  				HSM_SANITY(pn[i+0].offset < pn[i+1].offset);
  				HSM_SANITY(pn[i+1].offset <= SAVE_OFFSET(maxpool));
  				const size_t  mybeg = LOAD_OFFSET(pn[i+0].offset);
  				const size_t  myend = LOAD_OFFSET(pn[i+1].offset);
  				const size_t  mylen = myend - mybeg;
  				const size_t  extra = extralen(myend);
  				const fstring mykey(ps + mybeg, mylen-extra);
  				Value& myval = nth_value(pn, pv, i); // non-const
  				if (delmark == pn[i].link || pred(mykey, myval))
  					goto DoErase2;
  			}
  			return 0;
  		DoErase2:
  			nth_value(pn, pv, i).~Value();
  			loffset = LOAD_OFFSET(pn[i].offset); // begin of first deleted
  			for (size_t j = i+1; j < n; ++j) {
  				HSM_SANITY(pn[j+0].offset < pn[j+1].offset);
  				HSM_SANITY(pn[j+1].offset <= SAVE_OFFSET(maxpool));
  				const size_t  mybeg = LOAD_OFFSET(pn[j+0].offset);
  				const size_t  myend = LOAD_OFFSET(pn[j+1].offset);
  				const size_t  mylen = myend - mybeg;
  				const size_t  extra = extralen(myend);
  				const fstring mykey(ps + mybeg, mylen-extra);
  				Value& myval = nth_value(pn, pv, j); // non-const
  				if (delmark == pn[j].link)
  				{} // do nothing
  				else if (pred(mykey, myval))
  					nth_value(pn, pv, j).~Value(); // destruct
  				else {
  					pn[i].offset = SAVE_OFFSET(loffset);
  					move_value_on_raw(pn+i, pn+j, pv+i, pv+j);
  					memcpy(ps + loffset, ps + mybeg, mylen);
  					if (intptr_t(ph) != hash_cache_disabled)
  						ph[i] = ph[j];
  					loffset += mylen;
  					++i;
  				}
  			}
  		}
  		size_t nDeleted0 = nDeleted;
  		lenpool = loffset;
  		nNodes = LinkTp(i);
  		pn[i].offset = SAVE_OFFSET(loffset);
  		pn[i].link = tail; // guard for next_i
  		nDeleted = 0;
  		freepool = 0;
  		return n - nDeleted0 - i;
  	}
  public:
  	template<class Predictor>
  	size_t erase_if_kv(Predictor pred) {
  		if (fastleng == freelist_disabled) {
  			size_t nErased = erase_if_kv_impl(pred);
  			if (nNodes * 3/2 <= maxNodes)
  				shrink_to_fit();
  			else
  				relink();
  			return nErased;
  		} else
  			return keepid_erase_if_kv(pred);
  	}
  	template<class Predictor>
  	size_t shrink_after_erase_if_kv(Predictor pred) {
  		size_t nErased = erase_if_kv_impl(pred);
  		shrink_to_fit();
  		return nErased;
  	}
  	template<class Predictor>
  	size_t no_shrink_after_erase_if_kv(Predictor pred) {
  		size_t nErased = erase_if_kv_impl(pred);
  		relink();
  		return nErased;
  	}
  private:
  	template<class Predictor>
  	struct PPairToKV {
  		bool operator()(const fstring& k, Value& v) {
  			value_type kv(k, v);
  			return pred(kv);
  		}
  		PPairToKV(Predictor pred_) : pred(pred_) {}
  		Predictor pred;
  	};
  public:
  	template<class Predictor>
  	size_t erase_if(Predictor pred) {
  		return erase_if_kv(PPairToKV<Predictor>(pred));
  	}
  	template<class Predictor>
  	size_t shrink_after_erase_if(Predictor pred) {
  		return shrink_after_erase_if_kv(PPairToKV<Predictor>(pred));
  	}
  	template<class Predictor>
  	size_t no_shrink_after_erase_if(Predictor pred) {
  		return no_shrink_after_erase_if_kv(PPairToKV<Predictor>(pred));
  	}
  
  	template<class Predictor>
  	size_t keepid_erase_if_kv(Predictor pred) {
  		assert(freelist_disabled != fastleng);
  		assert(intptr_t(pHash) == hash_cache_disabled || NULL != pHash);
  		const HashTp* ph = pHash;
  		const char*   ps = strpool;
  		const LinkTp   n = nNodes;
  		const size_t  nb = nBucket;
  		Value* pv = values;
  		Node*  pn = pNodes;
  		LinkTp nErased = 0;
  		for (LinkTp i = 0; i < n; ++i) {
  			HSM_SANITY(pn[i+0].offset < pn[i+1].offset);
  			HSM_SANITY(pn[i+1].offset <= SAVE_OFFSET(maxpool));
  			const size_t  mybeg = LOAD_OFFSET(pn[i+0].offset);
  			const size_t  myend = LOAD_OFFSET(pn[i+1].offset);
  			const size_t  mylen = myend - mybeg;
  			const size_t  extra = extralen(myend);
  			const fstring mykey(ps + mybeg, mylen-extra);
  			Value& myval = nth_value(pn, pv, i); // non-const
  			if (delmark != pn[i].link && pred(mykey, myval)) {
  				HashTp hh = intptr_t(ph) == hash_cache_disabled ? hash(mykey) : ph[i];
  				size_t ib = size_t(hh % nb);
  				HSM_SANITY(tail != bucket[ib]);
  				LinkTp* p = &bucket[ib];
  				while (i != *p) {
  					p = &pn[*p].link;
  					HSM_SANITY(*p < n);
  				}
  				*p = pNodes[i].link; // delete the node from link list
  				pn[i].link = delmark; // set deletion mark
  				myval.~Value();
  				put_to_freelist(i);
  				nErased++;
  				freepool += mylen;
  			}
  		}
  		nDeleted += nErased;
  		return nErased;
  	}
  	template<class Predictor>
  	size_t keepid_erase_if(Predictor pred) {
  		return keepid_erase_if_kv(PPairToKV<Predictor>(pred));
  	}
  
  private:
  	void revoke_deleted_no_relink() throw() {
          assert(freelist_disabled == fastleng);
  		assert(nDeleted > 0);
  		ptrdiff_t n = nNodes;
  		char*  ps = strpool;
  		Node*  pn = pNodes;
  		Value* pv = values;
  		HashTp*ph = pHash;
  		ptrdiff_t idx1 = 0;
  		for (; idx1 < n; ++idx1) {
  			if (pn[idx1].link == delmark)
  				break; // first deleted
  		}
  		size_t loffset = LOAD_OFFSET(pn[idx1].offset); // begin of first deleted
  		for (ptrdiff_t idx2 = idx1 + 1; idx2 < n; ++idx2) {
  			if (pn[idx2].link != delmark) { // is not deleted
  				// string copy should be as fast as possible
  			#if SP_ALIGN != 1 && defined(HSM_ENABLE_MY_memcpy)
  				size_t beg2 = pn[idx2+0].offset;
  				size_t end2 = pn[idx2+1].offset;
  				size_t len2 = end2 - beg2; // count by align_type
  				HSM_SANITY(len2 > 0);
  				align_type* dst = (align_type*)(ps + loffset);
  				align_type* src = (align_type*)(ps + LOAD_OFFSET(beg2));
  				while (len2--) *dst++ = *src++;
  				len2 = LOAD_OFFSET(end2 - beg2);
  			#else
  				size_t beg2 = LOAD_OFFSET(pn[idx2+0].offset);
  				size_t end2 = LOAD_OFFSET(pn[idx2+1].offset);
  				size_t len2 = end2 - beg2;
  				memcpy(ps + loffset, ps + beg2, len2);
  			#endif
  				pn[idx1].offset = SAVE_OFFSET(loffset);
  				move_value_on_raw(pn+idx1, pn+idx2, pv+idx1, pv+idx2);
  				if (intptr_t(ph) != hash_cache_disabled)
  					ph[idx1] = ph[idx2];
  			   	loffset += len2;
  				++idx1;
  			}
  		}
  		assert(loffset + freepool == lenpool);
  		assert(nNodes  - nDeleted == (LinkTp)idx1);
  		lenpool = loffset;
  		pn[idx1].offset = SAVE_OFFSET(loffset);
  		pn[idx1].link = tail; // guard for next_i
  
  		nNodes -= nDeleted;
  		nDeleted = 0;
  		freepool = 0;
  	}
  
  public:
  	void revoke_deleted() {
          assert(freelist_disabled == fastleng);
  		if (freelist_disabled != fastleng) {
  			throw std::logic_error("hash_strmap::revoke_deleted: freelist is enabled");
  		}
  		if (nDeleted) {
  			revoke_deleted_no_relink();
  			relink();
  		}
  	}
  
  	size_t next_i(size_t idx) const {
  		assert(idx < nNodes);
  		Node* pn = pNodes;
  	#if 0
  		// don't use pn[nNodes].link guard
  		size_t n = nNodes;
  		do ++idx;
  		while (idx < n && pn[idx].link == delmark);
  	#else
  		// pn[nNodes].link is the guard
  		do ++idx;
  		while (pn[idx].link == delmark);
  	#endif
  		assert(idx <= nNodes);
  		return idx;
  	}
  
  	/**
  	A valid reverse iteration by prev_i should be:
  	<code>
  	for (size_t i = fm.rbeg_i(), re = fm.rend_i(); i != re;) {
  		i = fm.prev_i(i);
  		cout << fm.key(i) << ',' << fm.val(i) << endl;
  	}
  	// or by reverse_iterator:
  	// reverse_iterator need 2 prev_i call per iteration
  	for (auto i = fm.rbegin(); i != fm.rend(); ++i) {
  		// using i
  	}
  	</code>
  	*/
  	size_t prev_i(size_t idx) const {
  		assert(idx >  0); // not the begin
  		assert(idx <= nNodes);
  		Node* pn = pNodes;
  	#if defined(_DEBUG) || !defined(NDEBUG)
  		size_t n = nNodes;
  		do --idx; // no guard for prev_i, if idx rolled from 0, the loop ended
  		while (idx < n && pn[idx].link == delmark);
  
  		// if these 2 assert fail,
  		//    it should caused by iterate over begin when pNodes[0] is deleted
  		assert(idx < nNodes);
  		assert(pn[idx].link != delmark);
  	#else
  		// no extra guard is need for prev_i
  		// if pn[0] was deleted, a valid caller should not make idx less than 0
  		// because valid caller will not past beg_i() by calling prev_i
  		do --idx;
  		while (pn[idx].link == delmark);
  	#endif
  		return idx;
  	}
  
  	std::pair<size_t, bool>
  	insert_i(const fstring key, const Value& val = Value()) {
  		assert(key.n >= 0);
  		size_t n = nNodes; // compiler is easier to track local var
  		HashTp h = hash(key);
  		size_t i = size_t(h % nBucket);
  		for (LinkTp p = bucket[i]; tail != p; p = pNodes[p].link) {
  			HSM_SANITY(p < n);
  			const Node* y = &pNodes[p];
  			HSM_SANITY(y[0].offset < y[1].offset);
  			HSM_SANITY(y[1].offset <= SAVE_OFFSET(maxpool));
  		// doesn't need to compare cached hash value, it almost always true
  			size_t ybeg = LOAD_OFFSET(y[0].offset);
  			size_t yend = LOAD_OFFSET(y[1].offset);
  			size_t ylen = yend - ybeg - extralen(yend);
  		   	if (equal(key, fstring(strpool + ybeg, ylen)))
  				return std::make_pair(p, false);
  		}
  		if (nark_unlikely(n >= maxload)) {
  			rehash(nBucket + 1);
  			i = h % nBucket;
  		}
  		HSM_SANITY(n <= maxNodes);
  		size_t real_len = fstring_func::align_to(key.n+1);
          size_t slot = alloc_slot(real_len);
          size_t xbeg = LOAD_OFFSET(pNodes[slot+0].offset);
          size_t xend = LOAD_OFFSET(pNodes[slot+1].offset);
          assert(xend - xbeg == real_len);
          assert(slot < nNodes);
  		((align_type*)(strpool + xend))[-1] = 0; // pad 0
  		strpool[xend-1] = (char)(real_len - key.n - 1); // extra-1
  		memcpy(strpool + xbeg, key.p, key.n);
  		new(&nth_value(slot))Value(val);
  		pNodes[slot].link = bucket[i]; // newer at head
  		bucket[i] = LinkTp(slot); // new head of i'th bucket
  		if (intptr_t(pHash) != hash_cache_disabled) {
  			assert(NULL != pHash);
  			pHash[slot] = h;
  		}
  		sort_flag = en_unsorted;
  		return std::make_pair(slot, true);
  	}
  
  	size_t find_i(const char* key, size_t len) const { return find_i(fstring(key, len)); }
  	size_t find_i(const fstring key) const {
  		assert(key.n >= 0);
  		size_t n = nNodes; // compiler is easier to track local var
  		HashTp h = hash(key);
  		size_t i = size_t(h % nBucket);
  		for (LinkTp p = bucket[i]; tail != p; p = pNodes[p].link) {
  			HSM_SANITY(p < n);
  			const Node* y = &pNodes[p];
  			HSM_SANITY(y[0].offset < y[1].offset);
  			HSM_SANITY(y[1].offset <= SAVE_OFFSET(maxpool));
  		// doesn't need to compare cached hash value, it almost always true
  			size_t ybeg = LOAD_OFFSET(y[0].offset);
  			size_t yend = LOAD_OFFSET(y[1].offset);
  			size_t ylen = yend - ybeg - extralen(yend);
  		   	if (equal(key, fstring(strpool + ybeg, ylen)))
  				return p;
  		}
  		return n; // not found
  	}
  
  	size_t count(const fstring key) const {
  		assert(key.n >= 0);
  		return find_i(key) == nNodes ? 0 : 1;
  	}
  	// return value is same with count(key), but type is different
  	// this function is not stl standard, but more meaningful for app
  	bool exists(const fstring key) const {
  		assert(key.n >= 0);
  		return find_i(key) != nNodes;
  	}
  
  private:
      void put_to_freelist(LinkTp slot) {
  		size_t mybeg = pNodes[slot+0].offset;
  		size_t myend = pNodes[slot+1].offset;
          ptrdiff_t fastIdx = myend - mybeg - 1;
  		mybeg = LOAD_OFFSET(mybeg);
  		myend = LOAD_OFFSET(myend);
          FreeLink& fl = (FreeLink&)(strpool[mybeg]);
          FreeList& li = fastIdx < fastleng ? fastlist[fastIdx] : hugelist;
          fl.next = li.head;
          li.head = slot;
          li.freq++;
          li.llen++;
      }
  
      LinkTp alloc_slot(size_t real_len) {
  		assert(real_len % SP_ALIGN == 0);
          if (freelist_disabled != fastleng) {
              ptrdiff_t fastIdx = SAVE_OFFSET(real_len - 1);
              if (fastIdx < fastleng) {
                  LinkTp slot = fastlist[fastIdx].head;
  				if (tail != slot) {
  					size_t mybeg = LOAD_OFFSET(pNodes[slot+0].offset);
                  #if defined(_DEBUG) || !defined(NDEBUG)
  				    size_t myend = LOAD_OFFSET(pNodes[slot+1].offset);
                      assert(myend - mybeg == real_len);
                  #endif
  					fastlist[fastIdx].llen--;
  					fastlist[fastIdx].head = ((FreeLink&)strpool[mybeg]).next;
                      assert(freepool >= real_len);
                      assert(nDeleted >= 1);
                      freepool -= real_len;
                      nDeleted--;
  					return slot;
  				}
              } else {
                  LinkTp* curp = &hugelist.head;
                  LinkTp  curr;
                  while ((curr = *curp) != tail) {
                      size_t mybeg = LOAD_OFFSET(pNodes[curr+0].offset);
                      size_t myend = LOAD_OFFSET(pNodes[curr+1].offset);
                      LinkTp* next = &((FreeLink&)strpool[mybeg]).next;
                      if (myend - mybeg == real_len) {
                          *curp = *next;
                          hugelist.llen--;
                          assert(freepool >= real_len);
                          assert(nDeleted >= 1);
                          freepool -= real_len;
                          nDeleted--;
                          return curr;
                      }
                      curp = next;
                  }
              }
          }
          // make new slot
  		if (nark_unlikely(nNodes == maxNodes)) {
  			if (nark_unlikely(maxlink == nNodes)) {
  				throw std::runtime_error("nNodes reaches maxlink");
  			}
  			reserve_nodes(0 == nNodes ? 1 : 2*nNodes);
  		}
  		if (nark_unlikely(lenpool + real_len > maxpool)) {
  			using namespace std; // for std::max
  			if (lenpool + real_len > maxoffset) {
  				throw std::runtime_error("strpool is exceeding maxoffset");
  			}
  			if (freelist_disabled == fastleng && freepool >= max(maxpool/4, real_len))
  				revoke_deleted();
  			else { // if lenpool is random, expansion scale is about 1.6
                  size_t expect = __hsm_align_pow2((lenpool + real_len)*5/4);
  				size_t newmax = min(expect, (size_t)maxoffset);
  				char*  newpch = (char*)realloc(strpool, newmax);
  				if (NULL == newpch) {
  					if (freelist_disabled == fastleng && freepool >= real_len)
  						revoke_deleted();
  					else
  						throw std::bad_alloc();
  				} else {
  					maxpool = newmax;
  					strpool = newpch;
  				}
  			}
  		}
          lenpool += real_len;
  		pNodes[nNodes+1].offset = SAVE_OFFSET(lenpool);
  		pNodes[nNodes+1].link = tail; // guard for next_i
          return nNodes++;
      }
  
  	void erase_i_impl(const LinkTp idx, const HashTp h) {
  		size_t const i = size_t(h % nBucket);
  		HSM_SANITY(tail != bucket[i]);
  		LinkTp* p = &bucket[i];
  		while (idx != *p) {
  			p = &pNodes[*p].link;
  			HSM_SANITY(*p < nNodes);
  		}
  		*p = pNodes[idx].link; // delete the node from link list
  		pNodes[idx].link = delmark; // set deletion mark
  		nth_value(idx).~Value(); // destroy
  		size_t mybeg = LOAD_OFFSET(pNodes[idx+0].offset);
  		size_t myend = LOAD_OFFSET(pNodes[idx+1].offset);
  		size_t mylen = myend - mybeg;
  		if (nNodes-1 == idx) {
  			nNodes--;
  			pNodes[idx].link = tail; // guard for next_i
  			assert(lenpool >= mylen);
  			lenpool = mybeg;
  			return;
  		}
  		freepool += mylen;
  		++nDeleted;
          if (freelist_disabled == fastleng) {
      		if (nDeleted >= nNodes/2)
      			revoke_deleted();
      	//	relaxed: allow for key sorted and POD value sorted
          //	if (!boost::has_trivial_destructor<Value>::value && en_sort_by_val == sort_flag)
          //    	sort_flag = en_unsorted;
          } else
              put_to_freelist(idx);
  	}
  
  public:
  	void erase_i(const size_t idx) {
  		HSM_SANITY(nNodes >= 1);
  		assert(idx < nNodes);
  		assert(pNodes[idx].link != delmark); // must has not deleted
  		assert(intptr_t(pHash) == hash_cache_disabled || NULL != pHash);
  		HashTp h = intptr_t(pHash) == hash_cache_disabled ? hash(key(idx)) : pHash[idx];
  		erase_i_impl(LinkTp(idx), h);
  	}
  
      void enable_freelist(ptrdiff_t maxKeyLen = 1024) {
  		assert(maxKeyLen > 0);
          assert(maxKeyLen < 32*1024);
          ptrdiff_t newlistLen = SAVE_OFFSET(maxKeyLen + SP_ALIGN - 1);
          FreeList* newlist = fastlist;
          const Node* pn = pNodes;
          char* ps = strpool;
          if (newlistLen < fastleng) {
              // move separated free slots to hugelist
              for (ptrdiff_t  i =  newlistLen; i < fastleng; ++i) {
                  LinkTp* pcurr = &newlist[i].head;
                  LinkTp  ihead =  newlist[i].head;
                  if (tail != ihead) {
                      assert(newlist[i].llen > 0);
                      do {
                          size_t mybeg = LOAD_OFFSET(pn[*pcurr].offset);
                          pcurr = &((FreeLink&)ps[mybeg]).next;
                      } while (tail != *pcurr);
                      *pcurr = hugelist.head;
                      hugelist.head  = ihead;
                      hugelist.freq += newlist[i].freq;
                      hugelist.llen += newlist[i].llen;
                  }
              }
              fastleng = newlistLen;
          }
          newlist = t_realloc(newlist, newlistLen);
          if (NULL == newlist) throw std::bad_alloc();
  		fastlist = newlist;
          if (freelist_disabled == fastleng) {
              std::fill_n(newlist, newlistLen, FreeList());
              if (nDeleted) {
                  for (LinkTp i = 0; i < nNodes; ++i) {
                      if (delmark == pn[i].link)
                          put_to_freelist(i);
                  }
              }
          }
          else if (fastleng < newlistLen) {
              std::fill(newlist + fastleng, newlist + newlistLen, FreeList());
              // move slots from hugelist to fastlist
              LinkTp *pprev = &hugelist.head, curr = hugelist.head;
              while (tail != curr) {
                  ptrdiff_t iFast = pn[curr+1].offset - pn[curr].offset - 1;
                  FreeLink& rCurr = (FreeLink&)ps[LOAD_OFFSET(pn[curr].offset)];
                  LinkTp next = rCurr.next;
                  if (iFast < newlistLen) {
                      // put curr slot to iFast
                      FreeList& rFast = newlist[iFast];
                      rCurr.next = rFast.head;
                      rFast.head = curr;
                      rFast.freq++;
                      rFast.llen++;
                      hugelist.freq--;
                      hugelist.llen--;
                      *pprev = next; // delete curr from hugelist
                  } else
                      pprev = &rCurr.next; // keep track, only non-deleted
                  curr = next;
              }
          }
          fastleng = newlistLen;
      }
  
      void disable_freelist() {
  		assert((NULL != fastlist && freelist_disabled != fastleng) ||
  			   (NULL == fastlist && freelist_disabled == fastleng)
  			  );
  		if (fastlist) {
  			free(fastlist);
  			fastlist = NULL;
  		}
          fastleng = freelist_disabled;
          hugelist = FreeList();
      }
  
  	bool is_deleted(size_t idx) const {
  		assert(nNodes >= 1);
  		assert(idx < nNodes);
  		return pNodes[idx].link == delmark;
  	}
  
  	const char* key_c_str(size_t idx) const {
  		HSM_SANITY(nNodes >= 1);
  		assert(idx < nNodes);
  		size_t mybeg = LOAD_OFFSET(pNodes[idx+0].offset);
  		HSM_SANITY(mybeg < lenpool);
  		return strpool + mybeg;
  	}
  	size_t key_len(size_t idx) const {
  		HSM_SANITY(nNodes >= 1);
  		assert(idx < nNodes);
  		size_t mybeg = LOAD_OFFSET(pNodes[idx+0].offset);
  		size_t myend = LOAD_OFFSET(pNodes[idx+1].offset);
  		size_t extra = extralen(myend);
  		size_t mylen = myend - mybeg - extra;
  		HSM_SANITY(mybeg < myend);
  		HSM_SANITY(myend <= lenpool);
  		return mylen;
  	}
  	size_t key_offset(size_t idx) const {
  		HSM_SANITY(nNodes >= 1);
  		assert(idx < nNodes);
  		size_t mybeg = LOAD_OFFSET(pNodes[idx+0].offset);
  		HSM_SANITY(mybeg < lenpool);
  		return mybeg;
  	}
  	size_t key_offset_raw(size_t idx) const {
  	#if !defined(NDEBUG)
  		HSM_SANITY(nNodes >= 1);
  		assert(idx < nNodes);
  		size_t mybeg = LOAD_OFFSET(pNodes[idx+0].offset);
  		HSM_SANITY(mybeg < lenpool);
  	#endif
  		return pNodes[idx+0].offset;
  	}
  	fstring key(size_t idx) const {
  		HSM_SANITY(nNodes >= 1);
  		assert(idx < nNodes);
  		size_t mybeg = LOAD_OFFSET(pNodes[idx+0].offset);
  		size_t myend = LOAD_OFFSET(pNodes[idx+1].offset);
  		size_t extra = extralen(myend);
  		size_t mylen = myend - mybeg - extra;
  		HSM_SANITY(mybeg < myend);
  		HSM_SANITY(myend <= lenpool);
  		return fstring(strpool + mybeg, mylen);
  	}
  
  	fstring end_key(size_t idxEnd) const {
  		HSM_SANITY(nNodes >= 1);
  		assert(idxEnd <= nNodes);
  		size_t idx = nNodes - idxEnd;
  		size_t mybeg = LOAD_OFFSET(pNodes[idx+0].offset);
  		size_t myend = LOAD_OFFSET(pNodes[idx+1].offset);
  		size_t extra = extralen(myend);
  		size_t mylen = myend - mybeg - extra;
  		HSM_SANITY(mybeg < myend);
  		HSM_SANITY(myend <= lenpool);
  		return fstring(strpool + mybeg, mylen);
  	}
  
  private:
  	template<class KeyValue, class Func>
  	void for_each_impl(Func f) const {
  		Node* pn = pNodes;
  		char* ps = strpool;
  		if (nDeleted) {
  			for (size_t i = 0, n = nNodes; i < n; ++i) {
  				// need check deletion mark
  				if (pn[i].link != delmark) {
  					const size_t mybeg = LOAD_OFFSET(pn[i+0].offset);
  					const size_t myend = LOAD_OFFSET(pn[i+1].offset);
  					const size_t extra = extralen(ps, myend);
  					const size_t mylen = myend - mybeg - extra;
  					HSM_SANITY(mybeg < myend);
  					HSM_SANITY(myend <= lenpool);
  					KeyValue kv(fstring(ps + mybeg, mylen)
  							, nth_value(i, ValuePlace()));
  					f(kv);
  				}
  			}
  		}
  	   	else { // need not to check deletion mark
  			for (size_t i = 0, n = nNodes; i < n; ++i) {
  				const size_t mybeg = LOAD_OFFSET(pn[i+0].offset);
  				const size_t myend = LOAD_OFFSET(pn[i+1].offset);
  				const size_t extra = extralen(ps, myend);
  				const size_t mylen = myend - mybeg - extra;
  				HSM_SANITY(mybeg < myend);
  				HSM_SANITY(myend <= lenpool);
  				KeyValue kv(fstring(ps + mybeg, mylen)
  						, nth_value(i, ValuePlace()));
  				f(kv);
  			}
  		}
  	}
  public:
  	template<class Func>
  	void for_each(Func f) const {
  		for_each_impl<typename const_iterator::value_type, Func>(f);
  	}
  	template<class Func>
  	void for_each(Func f) {
  		for_each_impl<typename iterator::value_type, Func>(f);
  	}
  
  // Sorting and Binary search support:
  private:
  	struct KeyIndex {
  		// use this struct instead of just a 'int' index to pNodes could
  		// saved 1 indirect memory access to pNodes[*], friendly to CPU cache
  		LinkTp offset;
  		LinkTp length;
  		LinkTp idx; // index to pNodes
  	};
  	template<class KeyCompare>
  	struct SortKeyCompare : KeyCompare {
  		const char* ps;
  		bool operator()(const KeyIndex& x, const KeyIndex& y) const {
  			fstring sx(ps + LOAD_OFFSET(x.offset), x.length);
  			fstring sy(ps + LOAD_OFFSET(y.offset), y.length);
  			return KeyCompare::operator()(sx, sy);
  		}
  		bool operator()(const Node& x, const Node& y) const {
  			fstring sx(ps + LOAD_OFFSET(x.offset), x.link); // link is length
  			fstring sy(ps + LOAD_OFFSET(y.offset), y.link);
  			return KeyCompare::operator()(sx, sy);
  		}
  		SortKeyCompare(KeyCompare cmp, const char* ps) : KeyCompare(cmp), ps(ps) {}
  	};
  
  	void save_strlen_to_link() {
  		Node* pn = pNodes;
  		char* ps = strpool;
  		for (size_t i = 0, n = nNodes; i < n; ++i) {
  			const size_t mybeg = LOAD_OFFSET(pn[i+0].offset);
  			const size_t myend = LOAD_OFFSET(pn[i+1].offset);
  			const size_t extra = extralen(ps, myend);
  			const size_t mylen = myend - mybeg - extra;
  			HSM_SANITY(extra <= SP_ALIGN);
  			HSM_SANITY(mybeg <  myend);
  			HSM_SANITY(myend <= lenpool);
  			pn[i].link = LinkTp(mylen); // 'link' save the strlen
  		}
  	}
  
  	KeyIndex* buildindex() {
  		KeyIndex* index = (KeyIndex*)malloc(sizeof(KeyIndex) * nNodes);
  		if (NULL == index) {
  			throw std::bad_alloc();
  		}
  		Node* pn = pNodes;
  		char* ps = strpool;
  		for (size_t i = 0, n = nNodes; i < n; ++i) {
  			const size_t mybeg = LOAD_OFFSET(pn[i+0].offset);
  			const size_t myend = LOAD_OFFSET(pn[i+1].offset);
  			const size_t extra = extralen(ps, myend);
  			const size_t mylen = myend - mybeg - extra;
  			HSM_SANITY(extra <= SP_ALIGN);
  			HSM_SANITY(mybeg <  myend);
  			HSM_SANITY(myend <= lenpool);
  			index[i].offset = SAVE_OFFSET(mybeg);
  			index[i].length = pn[i].link = LinkTp(mylen);
  			index[i].idx = LinkTp(i);
  		}
  		return index;
  	}
  
  	LinkTp* buildindex_by_int() {
  		LinkTp* p = (LinkTp*)malloc(sizeof(LinkTp) * nNodes);
  		if (NULL == p) {
  			throw std::bad_alloc();
  		}
  		for (size_t i = 0, n = nNodes; i < n; ++i)
  			p[i] = i;
  		return p;
  	}
  
   // template Arg  HasHashCache this will enable compile time optimization
   	template<bool HasHashCache>
  	void rearrange_nodes_by_int_impl(LinkTp* index) {
  		Node* pn = pNodes;
  		Value* pv = values;
  		HashTp*ph = pHash;
  		for (size_t i = 0, n = nNodes; i < n; ++i) { // Rearrange
  			if (index[i] != i) {
  				LinkTp curr, next = index[i];
  				LinkTp tmpoffset = pn[next].offset;
  				LinkTp tmplink   = pn[next].link; // link saved strlen
  				HashTp tmphash   = 0; // avoid warning
  				char   tmpvalue[sizeof(Value)];
                  if (HasHashCache)
                      tmphash = ph[next];
  				CopyStrategy::move_cons((Value*)tmpvalue, nth_value(next));
  				do {
  					assert(next < n);
  					curr = next;
  					next = index[next];
  					pn[curr].offset = pn[next].offset;
  					pn[curr].link   = pn[next].link;
  					move_value_on_raw(pn+curr, pn+next, pv+curr, pv+next);
  					index[curr] = curr;
  					if (HasHashCache)
  						ph[curr] = ph[next];
  				} while (next != i);
  #if defined(__GNUC__) && __GNUC__*1000 + __GNUC_MINOR__ >= 4006
  		#pragma GCC diagnostic push
  		#pragma GCC diagnostic ignored "-Wstrict-aliasing"
  #endif
  				CopyStrategy::move_cons(&nth_value(i), *reinterpret_cast<Value*>(tmpvalue));
  #if defined(__GNUC__) && __GNUC__*1000 + __GNUC_MINOR__ >= 4006
  		#pragma GCC diagnostic pop
  #endif
  				pn[i].offset = tmpoffset;
  				pn[i].link   = tmplink;
                  if (HasHashCache)
  					ph[i] = tmphash;
  				index[i] = LinkTp(i);
  			}
  		}
  		free(index);
  	}
  	void rearrange_nodes_by_int(LinkTp* index) {
  		if (intptr_t(pHash) == hash_cache_disabled || NULL == pHash)
  			rearrange_nodes_by_int_impl<false>(index); // "index" will be free'ed
  		else
  			rearrange_nodes_by_int_impl<true >(index); // "index" will be free'ed
  	}
  
  	template<class IndexType>
  	LinkTp* copy_idx_to_LinkTp_array(IndexType* index) {
  		// copy idx to LinkTp array, small array has benefit of CPU cache
  		// in rearrange_nodes_by_int
  		LinkTp* pi = reinterpret_cast<LinkTp*>(index);
  		for (size_t i = 0, n = nNodes; i < n; ++i)
  			pi[i] = index[i].idx;
  		return pi;
  	}
  
  	template<class IndexType>
  	void rearrange_nodes(IndexType* index) {
  		LinkTp* pi = copy_idx_to_LinkTp_array(index);
  		rearrange_nodes_by_int(pi); // pi == index will be free'ed
  	}
  
  	void rearrange_strpool() {
  		char* s2 = (char*)malloc(lenpool);
  		if (NULL == s2) {
  			throw std::bad_alloc();
  		}
  		size_t loffset = 0;
  		char* ps = strpool;
  		Node* pn = pNodes;
  		for (size_t i = 0, n = nNodes; i < n; ++i) {
  			size_t len = pn[i].link; // Node::link saved string length
  			len = fstring_func::align_to(len + 1);
  			// could be optimized as aligned copy?
  			memcpy(s2 + loffset, ps + LOAD_OFFSET(pn[i].offset), len);
  			pn[i].offset = SAVE_OFFSET(loffset);
  			loffset += len;
  		}
  		assert(loffset == lenpool);
  		free(strpool);
  		strpool = s2;
  		maxpool = lenpool;
  	}
  
  	template<class KeyCompare>
  	void sort_by_key_impl(const KeyCompare& comp, sort_by_index_yes) {
  		KeyIndex* index = buildindex();
  		nark_parallel_sort(index, index + nNodes, SortKeyCompare<KeyCompare>(comp, strpool));
  		rearrange_nodes(index);
  	}
  	template<class KeyCompare>
  	void sort_by_key_impl(const KeyCompare& comp, sort_by_index_no) {
  		save_strlen_to_link();
  		nark_parallel_sort(pNodes, pNodes + nNodes, SortKeyCompare<KeyCompare>(comp, strpool));
  	}
  
  	typedef typename bytes2uint<(sizeof(LinkTp)*2<SP_ALIGN)?sizeof(LinkTp)*2:SP_ALIGN>::type LinkT2;
  	typedef KeyIndexWithPrefix_tt<LinkTp>            KeyIndexWithPrefix;
  	typedef     NodeWithPrefix_tt<LinkTp, LinkT2, Value> NodeWithPrefix;
  
  	KeyIndexWithPrefix*	sort_by_key_prefix_o(sort_by_index_yes, bool DoRearrange) {
  		KeyIndexWithPrefix* index = t_malloc<KeyIndexWithPrefix>(nNodes);
  		if (NULL == index) {
  			throw std::bad_alloc();
  		}
  		Node* pn = pNodes;
  		char* ps = strpool;
  		for (size_t i = 0, n = nNodes; i < n; ++i) {
  			const size_t mybeg = LOAD_OFFSET(pn[i+0].offset);
  			const size_t myend = LOAD_OFFSET(pn[i+1].offset);
  			const size_t extra = extralen(ps, myend);
  			const size_t mylen = myend - mybeg - extra;
  			HSM_SANITY(extra <= SP_ALIGN);
  			HSM_SANITY(mybeg <  myend);
  			HSM_SANITY(myend <= lenpool);
  			index[i].offset = SAVE_OFFSET(mybeg);
  			index[i].length = pn[i].link = LinkTp(mylen);
  			if (mylen >= sizeof(index[i].prefix))
  				memcpy(&index[i].prefix, ps + mybeg, sizeof(index[i].prefix));
  			else {
  				index[i].prefix = 0;
  				memcpy(&index[i].prefix, ps + mybeg, mylen);
  			}
  #if defined(BOOST_LITTLE_ENDIAN)
  			index[i].prefix = nark::byte_swap(index[i].prefix);
  #endif
  			index[i].idx = LinkTp(i);
  		}
  		nark_parallel_sort(index, index + nNodes, ByteWiseKeyCompare(strpool));
  		if (DoRearrange) {
  			rearrange_nodes(index); // "index" will be free'ed
  			return NULL;
  		}
  		return index;
  	}
  	void sort_by_key_prefix_o(sort_by_index_no, bool DoRearrange) {
  		assert(DoRearrange); (void)DoRearrange;
  		NodeWithPrefix* pnp;
  		Node* pn;
  		if (boost::is_same<CopyStrategy, FastCopy>::value) {
  			pnp = (NodeWithPrefix*)realloc(pNodes, sizeof(NodeWithPrefix)*nNodes);
  			pn = (Node*)pnp;
  		} else {
  			pnp = (NodeWithPrefix*)malloc(sizeof(NodeWithPrefix)*nNodes);
  			pn = pNodes;
  		}
  		if (NULL == pnp) { // fallback to slower version
  			sort_by_key_impl(fstring_func::IF_SP_ALIGN(less_align, less_unalign)(), sort_by_index_no());
  			return;
  		}
  		char* ps = strpool;
  		// backward copy to pnp because it is inplace copy small to big
  		for (ptrdiff_t i = nNodes-1; i >= 0; --i) {
  			const size_t mybeg = LOAD_OFFSET(pn[i+0].offset);
  			const size_t myend = LOAD_OFFSET(pn[i+1].offset);
  			const size_t extra = extralen(ps, myend);
  			const size_t mylen = myend - mybeg - extra;
  			HSM_SANITY(extra <= SP_ALIGN);
  			HSM_SANITY(mybeg <  myend);
  			HSM_SANITY(myend <= lenpool);
  			// TODO: &pnp[0].value may overlap with &pn[0].value, now just support FastCopy
  			CopyStrategy::move_cons_backward(&pnp[i].value, pn[i].value);
  			if (mylen >= sizeof(pnp[i].prefix))
  				memcpy(&pnp[i].prefix, ps + mybeg, sizeof(pnp[i].prefix));
  			else {
  				pnp[i].prefix = 0;
  				memcpy(&pnp[i].prefix, ps + mybeg, mylen);
  			}
  #if defined(BOOST_LITTLE_ENDIAN)
  			pnp[i].prefix = nark::byte_swap(pnp[i].prefix);
  #endif
  			pnp[i].length = LinkTp(mylen);
  			pnp[i].offset = SAVE_OFFSET(mybeg);
  		}
  		nark_parallel_sort(pnp, pnp + nNodes, ByteWiseKeyCompare(strpool));
  		for (size_t i = 0; i < nNodes; ++i) {
  			pn[i].offset = pnp[i].offset;
  			pn[i].link = pnp[i].length;
  			CopyStrategy::move_cons_forward(&pn[i].value, pnp[i].value);
  		}
  		pn[nNodes].offset = SAVE_OFFSET(lenpool);
  		pn[nNodes].link = tail;
  		if (boost::is_same<CopyStrategy, FastCopy>::value) {
  			pNodes = pn;
  			pn = (Node*)realloc(pn, allnodes_size(maxNodes));
  			if (NULL == pn) throw std::bad_alloc();
  			pNodes = pn;
  		} else
  			free(pnp); // malloc'ed
  	}
  
  public:
  	template<class KeyCompare>
  	void sort(const KeyCompare& comp) {
  		ptrdiff_t old_fastleng = fastleng;
  		LinkTp realdeleted = nDeleted;
  		if (nDeleted) {
  			if (freelist_disabled != old_fastleng)
  				disable_freelist();
  			revoke_deleted_no_relink();
  		}
  		if (nNodes >= 2) {
  			sort_by_key_impl(comp, sort_by_index());
  			rearrange_strpool(); // must after rearrange_nodes
  			if (bucket) // is hash disabled?
  				relink_fill();
  		}
  		if (realdeleted && freelist_disabled != old_fastleng)
  			enable_freelist(old_fastleng);
  		sort_flag = en_sort_by_key;
  	}
  	void sort_slow() { sort(fstring_func::IF_SP_ALIGN(less_align, less_unalign)()); return; }
  	void sort_fast() { // with_prefix_optimization
  		ptrdiff_t old_fastleng = fastleng;
  		LinkTp realdeleted = nDeleted;
  		if (nDeleted) {
  			if (freelist_disabled != old_fastleng)
  				disable_freelist();
  			revoke_deleted_no_relink();
  		}
  		if (nNodes >= 2) {
  			const bool DoRearrange = true;
  			sort_by_key_prefix_o(sort_by_index(), DoRearrange);
  			rearrange_strpool(); // must after rearrange_nodes
  			if (bucket) // is hash disabled?
  				relink_fill();
  		}
  		if (realdeleted && freelist_disabled != old_fastleng)
  			enable_freelist(old_fastleng);
  		sort_flag = en_sort_by_key;
     	}
  
  	///@note returned pointer should be freed by the caller
  	LinkTp* get_sorted_index_fast() const {
  		assert(0 == nDeleted);
  		KeyIndexWithPrefix* idx0;
  	   	LinkTp* idx1;
  		const bool DoRearrange = false;
  		idx0 = sort_by_key_prefix_o(sort_by_index_yes(), DoRearrange);
  		idx1 = copy_idx_to_LinkTp_array(idx0);
  		idx1 = (LinkTp*)realloc(idx1, sizeof(LinkTp) * nNodes); // shrink
  		assert(NULL != idx1);
  		return idx1;
  	}
  
  	///@note length of *buf must >= this->end_i()+1, or NULL
  	void get_offsets(LinkTp** ppbuf) const {
  		if (NULL == *ppbuf)
  			*ppbuf = (LinkTp)malloc(sizeof(LinkTp)*(nNodes+1));
  		const Node* pn = pNodes;
  		LinkTp* buf = *ppbuf;
  		for (size_t i = 0, n = nNodes+1; i < n; ++i)
  			buf[i] = pn[i].offset;
  	}
  
  	size_t lower_bound(const fstring key) const {
  		return lower_bound(key, fstring_func::IF_SP_ALIGN(Less, less_unalign)());
  	}
  	size_t upper_bound(const fstring key) const {
  		return upper_bound(key, fstring_func::IF_SP_ALIGN(Less, less_unalign)());
  	}
  
  	template<class KeyCompare>
  	size_t lower_bound(const fstring key, const KeyCompare& comp) const {
  		assert(en_sort_by_key == sort_flag);
  		const Node* pn = &pNodes[0];
  		const char* ps = strpool;
  		size_t lo = 0, hi = nNodes;
  		while (lo < hi) {
  			size_t mid = lo + (hi - lo) / 2; // avoid overflow
  			size_t beg = LOAD_OFFSET(pn[mid+0].offset);
  			size_t End = LOAD_OFFSET(pn[mid+1].offset);
  			size_t len = End - beg - extralen(ps, End);
  			const fstring smid(ps + beg, len);
  			if (comp(smid, key))
  				lo = mid + 1;
  			else
  				hi = mid;
  		}
  		return lo;
  	}
  
  	template<class KeyCompare>
  	size_t upper_bound(const fstring key, const KeyCompare& comp) const {
  		assert(en_sort_by_key == sort_flag);
  		const Node* pn = &pNodes[0];
  		const char* ps = strpool;
  		size_t lo = 0, hi = nNodes;
  		while (lo < hi) {
  			size_t mid = lo + (hi - lo) / 2; // avoid overflow
  			size_t beg = LOAD_OFFSET(pn[mid+0].offset);
  			size_t End = LOAD_OFFSET(pn[mid+1].offset);
  			size_t len = End - beg - extralen(ps, End);
  			const fstring smid(ps + beg, len);
  			if (!comp(key, smid)) // smid <= key
  				lo = mid + 1;
  			else
  				hi = mid;
  		}
  		return lo;
  	}
  
  	/// can be used to find common prefix ranges
  	/// param: comp3 3-way compare, like strcmp
  	template<class KeyPrefixCompare3>
  	std::pair<size_t, size_t>
  	equal_range3(const fstring key, const KeyPrefixCompare3& comp3) const {
  		assert(en_sort_by_key == sort_flag);
  		const Node* pn = &pNodes[0];
  		const char* ps = strpool;
  		size_t lo = 0, hi = nNodes;
  		size_t mid0 = hi;
  		while (lo < hi) {
  			mid0 = lo + (hi - lo) / 2; // avoid overflow
  			size_t beg = LOAD_OFFSET(pn[mid0+0].offset);
  			size_t End = LOAD_OFFSET(pn[mid0+1].offset);
  			size_t len = End - beg - extralen(ps, End);
  			const fstring smid0(ps + beg, len);
  			int ret = comp3(smid0, key);
  			if (ret < 0)
  				lo = mid0 + 1;
  			else if (ret > 0)
  				hi = mid0;
  			else
  				break;
  		}
  		size_t loH = mid0;
  		while (lo < loH) {
  			size_t mid = lo + (loH - lo) / 2; // avoid overflow
  			size_t beg = LOAD_OFFSET(pn[mid+0].offset);
  			size_t End = LOAD_OFFSET(pn[mid+1].offset);
  			size_t len = End - beg - extralen(ps, End);
  			const fstring smid(ps + beg, len);
  			int ret = comp3(smid, key);
  			if (ret < 0) // lower_bound
  				lo = mid + 1;
  			else
  				loH = mid;
  		}
  		size_t hiL = mid0;
  		while (hiL < hi) {
  			size_t mid = hiL + (hi - hiL) / 2; // avoid overflow
  			size_t beg = LOAD_OFFSET(pn[mid+0].offset);
  			size_t End = LOAD_OFFSET(pn[mid+1].offset);
  			size_t len = End - beg - extralen(ps, End);
  			const fstring smid(ps + beg, len);
  			int ret = comp3(smid, key);
  			if (ret <= 0) // upper_bound
  				hiL = mid + 1;
  			else
  				hi = mid;
  		}
  		return std::pair<size_t, size_t>(lo, hi);
  	}
  	std::pair<size_t, size_t>
  	equal_range3(const char* prefix, size_t prefixlen) const {
  		return equal_range3(fstring(prefix, prefixlen), fstring_func::prefix_compare3(prefixlen));
  	}
  
  // sort and binary search by value...
  private:
  	template<class CompareValue>
  	struct SortCompareValueInline : CompareValue {
  		bool operator()(const Node& x, const Node& y) const {
  			return CompareValue::operator()(x.value, y.value);
  		}
  		SortCompareValueInline(CompareValue cmp) : CompareValue(cmp) {}
  	};
  	template<class CompareValue>
  	struct SortCompareValueInlineByIndex : CompareValue {
  		const Node* pn;
  		bool operator()(const size_t x, const size_t y) const {
  			return CompareValue::operator()(pn[x].value, pn[y].value);
  		}
  		SortCompareValueInlineByIndex(CompareValue cmp, const Node* pn) : CompareValue(cmp), pn(pn) {}
  	};
  	template<class CompareValue>
  	struct SortCompareValueOut : CompareValue {
  		const Value* pv;
  		bool operator()(const size_t x, const size_t y) const {
  			return CompareValue::operator()(pv[x], pv[y]);
  		}
  		SortCompareValueOut(CompareValue cmp, const Value* pv) : CompareValue(cmp), pv(pv) {}
  	};
  
  	template<class ValueCompare>
  	void sort_by_value_impl(ValueCompare comp, ValueInline, sort_by_index_yes) {
  		LinkTp* index = NULL;
  		try { index = buildindex_by_int(); } catch (const std::bad_alloc&) {}
  		if (index) {
  			nark_parallel_sort(index, index + nNodes, SortCompareValueInlineByIndex<ValueCompare>(comp, pNodes));
  			rearrange_nodes_by_int(index); // index will be free'ed
  			rearrange_strpool(); // must after rearrange_nodes
  			if (bucket) // is hash disabled?
  				relink();
  		}
  		else // alloc fail, fall back to in-place sort
  			sort_by_value_impl(comp, ValueInline(), sort_by_index_no());
  	}
  	template<class ValueCompare>
  	void sort_by_value_impl(ValueCompare comp, ValueInline, sort_by_index_no) {
  		nark_parallel_sort(pNodes, pNodes + nNodes, SortCompareValueInline<ValueCompare>(comp));
  		rearrange_strpool(); // must after rearrange_nodes
  		if (bucket) // is hash disabled?
  			relink_fill();
  	}
  	template<class ValueCompare>
  	void sort_by_value_impl(ValueCompare comp, ValueOut, sort_by_index_yes) {
  		LinkTp* index = buildindex_by_int();
  		Value* pv = values;
  		nark_parallel_sort(index, index + nNodes, SortCompareValueOut<ValueCompare>(comp, pv));
  		rearrange_nodes_by_int(index); // index will be free'ed
  		rearrange_strpool(); // must after rearrange_nodes
  		if (bucket) // is hash disabled?
  			relink();
  	}
  
  	template<class KeyOfValue, class Compare>
  	struct FindCompareValueInline : Compare {
  		bool operator()(const KeyOfValue& x, const Node& y) const {
  			return Compare::operator()(x, y.value);
  		}
  		bool operator()(const Node& x, const KeyOfValue& y) const {
  			return Compare::operator()(x.value, y);
  		}
  		bool operator()(const Node& x, const Node& y) const {
  			// in debug mode, vc will check order of sequence when binary search,
  			// so this function is required for this purpose
  			return Compare::operator()(x.value, y.value);
  		}
  		FindCompareValueInline(Compare comp) : Compare(comp) {}
  	};
  
  	template<class KeyOfValue, class Compare>
  	size_t lower_bound_by_value_impl(KeyOfValue kov, Compare comp, ValueOut) const {
  		const Value* pv = values;
  		return std::lower_bound(pv, pv + nNodes, kov, comp) - pv;
  	}
  	template<class KeyOfValue, class Compare>
  	size_t upper_bound_by_value_impl(KeyOfValue kov, Compare comp, ValueOut) const {
  		const Value* pv = values;
  		return std::upper_bound(pv, pv + nNodes, kov, comp) - pv;
  	}
  	template<class KeyOfValue, class Compare>
  	size_t lower_bound_by_value_impl(KeyOfValue kov, Compare comp, ValueInline) const {
  		const Node* pn = pNodes;
  		return std::lower_bound(pn, pn + nNodes, kov, FindCompareValueInline<KeyOfValue, Compare>(comp)) - pn;
  	}
  	template<class KeyOfValue, class Compare>
  	size_t upper_bound_by_value_impl(KeyOfValue kov, Compare comp, ValueInline) const {
  		const Node* pn = pNodes;
  		return std::upper_bound(pn, pn + nNodes, kov, FindCompareValueInline<KeyOfValue, Compare>(comp)) - pn;
  	}
  
  	template<class KeyOfValue, class Compare>
  	std::pair<size_t, size_t>
  	equal_range_by_value_impl(KeyOfValue kov, Compare comp, ValueOut) const {
  		const Value* pv = values;
  		std::pair<const Value*, const Value*> ii = std::equal_range(pv, pv + nNodes, kov, comp);
  		return std::pair<size_t, size_t>(ii.first - pv, ii.second - pv);
  	}
  	template<class KeyOfValue, class Compare>
  	std::pair<size_t, size_t>
  	equal_range_by_value_impl(KeyOfValue kov, Compare comp, ValueInline) const {
  		const Node* pn = pNodes;
  		std::pair<const Node*, const Node*> ii =
  		std::equal_range(pn, pn + nNodes, kov, FindCompareValueInline<KeyOfValue, Compare>(comp));
  		return std::pair<size_t, size_t>(ii.first - pn, ii.second - pn);
  	}
  public:
  	template<class ValueCompare>
  	void sort_by_value(ValueCompare comp) {
  		BOOST_STATIC_ASSERT(!is_value_empty);
  		ptrdiff_t old_fastleng = fastleng;
  		if (nDeleted) {
  			if (freelist_disabled != old_fastleng)
  				disable_freelist();
  			revoke_deleted_no_relink();
  		}
  		if (nNodes >= 2) {
  			save_strlen_to_link();
  			sort_by_value_impl(comp, ValuePlace(), sort_by_index());
  		}
  		if (freelist_disabled != old_fastleng)
  			enable_freelist(old_fastleng);
  		sort_flag = en_sort_by_val;
  	}
  	void sort_by_value() {
  		BOOST_STATIC_ASSERT(!is_value_empty);
  		sort_by_value(std::less<Value>());
  	}
  	template<class KeyOfValue, class Compare>
  	size_t lower_bound_by_value(const KeyOfValue& kov, Compare comp) const {
  		assert(en_sort_by_val == sort_flag);
  		return lower_bound_by_value_impl(kov, comp, ValuePlace());
  	}
  	template<class KeyOfValue, class Compare>
  	size_t upper_bound_by_value(const KeyOfValue& kov, Compare comp) const {
  		assert(en_sort_by_val == sort_flag);
  		return upper_bound_by_value_impl(kov, comp, ValuePlace());
  	}
  	template<class KeyOfValue, class Compare>
  	std::pair<size_t, size_t>
  	equal_range_by_value(const KeyOfValue& kov, Compare comp) const {
  		assert(en_sort_by_val == sort_flag);
  		return equal_range_by_value_impl(kov, comp, ValuePlace());
  	}
  
  	size_t lower_bound_by_value(const Value& val) const {
  		assert(en_sort_by_val == sort_flag);
  		return lower_bound_by_value_impl(val, std::less<Value>(), ValuePlace());
  	}
  	size_t upper_bound_by_value(const Value& val) const {
  		assert(en_sort_by_val == sort_flag);
  		return upper_bound_by_value_impl(val, std::less<Value>(), ValuePlace());
  	}
  	std::pair<size_t, size_t>
  	equal_range_by_value(const Value& val) const {
  		assert(en_sort_by_val == sort_flag);
  		return equal_range_by_value_impl(val, std::less<Value>(), ValuePlace());
  	}
  
  // sort by composite key-value, code is somewhat longer, but simple
  // k3v2 : first 3-way key compare, second 2-way val compare
  // v2k2 : first 2-way val compare, second 2-way key compare
  //
  private:
  // key first, value second, 3-way key compare
  	template<class KeyCmp3, class ValCmp2>
  	struct cmp_by_index_ValueOut_k3v2 { // such as case insensitive compare
  		bool operator()(const KeyIndex& x, const KeyIndex& y) const {
  			const fstring sx(ps + LOAD_OFFSET(x.offset), x.length);
  			const fstring sy(ps + LOAD_OFFSET(y.offset), y.length);
  			int ret = kc(sx, sy);
  			if (ret != 0)
  				return ret < 0;
  			return vc(pv[x.idx], pv[y.idx]);
  		}
  		cmp_by_index_ValueOut_k3v2(const char* ps, const Value* pv, KeyCmp3 kc, ValCmp2 vc)
  			: ps(ps), pv(pv), kc(kc), vc(vc) {}
  		const char*  ps;
  		const Value* pv;
  		KeyCmp3      kc;
  		ValCmp2      vc;
  	};
  	template<class KeyCmp3, class ValCmp2>
  	struct cmp_by_index_ValueInline_k3v2 {
  		bool operator()(const KeyIndex& x, const KeyIndex& y) const {
  			const fstring sx(ps + LOAD_OFFSET(x.offset), x.length);
  			const fstring sy(ps + LOAD_OFFSET(y.offset), y.length);
  			int ret = kc(sx, sy);
  			if (ret != 0)
  				return ret < 0;
  			return pn[x.idx].value < pn[y.idx].value;
  		}
  		cmp_by_index_ValueInline_k3v2(const char* ps, const Node* pn, KeyCmp3 kc, ValCmp2 vc)
  			: ps(ps), pn(pn), kc(kc), vc(vc) {}
  		const char* ps;
  		const Node* pn;
  		KeyCmp3     kc;
  		ValCmp2     vc;
  	};
  	template<class KeyCmp3, class ValCmp2>
  	struct cmp_ValueInline_k3v2 {
  		bool operator()(const Node& x, const Node& y) const {
  			fstring sx(ps + LOAD_OFFSET(x.offset), x.link); // link is length
  			fstring sy(ps + LOAD_OFFSET(y.offset), y.link);
  			int ret = kc(sx, sy);
  			if (ret != 0)
  				return ret < 0;
  			return vc(x.value, y.value);
  		}
  		cmp_ValueInline_k3v2(const char* ps, KeyCmp3 kc, ValCmp2 vc)
  			: ps(ps), kc(kc), vc(vc) {}
  		const char* ps;
  		KeyCmp3     kc;
  		ValCmp2     vc;
  	};
  	template<class KeyCmp3, class ValCmp2>
  	void sort_k3v2_(KeyCmp3 kc, ValCmp2 vc, sort_by_index_yes, ValueOut) {
  		KeyIndex* index = buildindex();
  		nark_parallel_sort(index, index + nNodes,
  			cmp_by_index_ValueOut_k3v2<KeyCmp3, ValCmp2>(strpool, values, kc, vc));
  		rearrange_nodes(index);
  		rearrange_strpool(); // must after rearrange_nodes
  		if (bucket) // is hash disabled?
  			relink();
  	}
  	template<class KeyCmp3, class ValCmp2>
  	void sort_k3v2_(KeyCmp3 kc, ValCmp2 vc, sort_by_index_yes, ValueInline) {
  		KeyIndex* index = buildindex();
  		nark_parallel_sort(index, index + nNodes,
  			cmp_by_index_ValueInline_k3v2<KeyCmp3, ValCmp2>(strpool, pNodes, kc, vc));
  		rearrange_nodes(index);
  		rearrange_strpool(); // must after rearrange_nodes
  		if (bucket) // is hash disabled?
  			relink();
  	}
  	template<class KeyCmp3, class ValCmp2>
  	void sort_k3v2_(KeyCmp3 kc, ValCmp2 vc,	sort_by_index_no, ValueInline) {
  		save_strlen_to_link();
  		nark_parallel_sort(pNodes, pNodes + nNodes, cmp_ValueInline_k3v2<KeyCmp3, ValCmp2>(strpool, kc, vc));
  		rearrange_strpool(); // must after rearrange_nodes
  		if (bucket) // is hash disabled?
  			relink_fill();
  	}
  public:
  	template<class KeyCmp3, class ValCmp2>
  	void sort_k3v2(KeyCmp3 kc, ValCmp2 vc) {
  		BOOST_STATIC_ASSERT(!is_value_empty);
  		if (nDeleted)
  			revoke_deleted_no_relink();
  		if (nNodes >= 2) {
  			sort_k3v2_(kc, vc, sort_by_index(), ValuePlace());
  		}
  		sort_flag = en_sort_by_key;
  	}
  
  private:
  // value first, key second, 2-way key compare, 2-way value compare
  	template<class KeyCmp2, class ValCmp2>
  	struct cmp_by_index_ValueOut_v2k2 {
  		bool operator()(const KeyIndex& x, const KeyIndex& y) const {
  			const Value& vx = pv[x.idx];
  			const Value& vy = pv[y.idx];
  			if (vc(vx, vy))
  				return true;
  			else if (vc(vy, vx))
  				return false;
  			else {
  				const fstring sx(ps + LOAD_OFFSET(x.offset), x.length);
  				const fstring sy(ps + LOAD_OFFSET(y.offset), y.length);
  				return kc(sx, sy);
  			}
  		}
  		cmp_by_index_ValueOut_v2k2(const char* ps, const Value* pv, KeyCmp2 kc, ValCmp2 vc)
  			: ps(ps), pv(pv), kc(kc), vc(vc) {}
  		const char*  ps;
  		const Value* pv;
  		KeyCmp2      kc;
  		ValCmp2      vc;
  	};
  	template<class KeyCmp2, class ValCmp2>
  	struct cmp_by_index_ValueInline_v2k2 {
  		bool operator()(const KeyIndex& x, const KeyIndex& y) const {
  			const Value& vx = pn[x.idx].value;
  			const Value& vy = pn[y.idx].value;
  			if (vc(vx, vy))
  				return true;
  			else if (vc(vy, vx))
  				return false;
  			else {
  				const fstring sx(ps + LOAD_OFFSET(x.offset), x.length);
  				const fstring sy(ps + LOAD_OFFSET(y.offset), y.length);
  				return kc(sx, sy);
  			}
  		}
  		cmp_by_index_ValueInline_v2k2(const char* ps, const Node* pn, KeyCmp2 kc, ValCmp2 vc)
  			: ps(ps), pn(pn), kc(kc), vc(vc) {}
  		const char* ps;
  		const Node* pn;
  		KeyCmp2     kc;
  		ValCmp2     vc;
  	};
  	template<class KeyCmp2, class ValCmp2>
  	struct cmp_ValueInline_v2k2 {
  		bool operator()(const Node& x, const Node& y) const {
  			if (vc(x.value, y.value))
  				return true;
  			else if (vc(y.value, x.value))
  				return false;
  			else {
  				const fstring sx(ps + LOAD_OFFSET(x.offset), x.link);
  				const fstring sy(ps + LOAD_OFFSET(y.offset), y.link);
  				return kc(sx, sy);
  			}
  		}
  		cmp_ValueInline_v2k2(const char* ps, KeyCmp2 kc, ValCmp2 vc)
  			: ps(ps), kc(kc), vc(vc) {}
  		const char* ps;
  		KeyCmp2     kc;
  		ValCmp2     vc;
  	};
  	template<class KeyCmp2, class ValCmp2>
  	void sort_v2k2_(KeyCmp2 kc, ValCmp2 vc, sort_by_index_yes, ValueOut) {
  		KeyIndex* index = buildindex();
  		nark_parallel_sort(index, index + nNodes,
  			cmp_by_index_ValueOut_v2k2<KeyCmp2, ValCmp2>(strpool, values, kc, vc));
  		rearrange_nodes(index);
  		rearrange_strpool(); // must after rearrange_nodes
  		if (bucket) // is hash disabled?
  			relink();
  	}
  	template<class KeyCmp2, class ValCmp2>
  	void sort_v2k2_(KeyCmp2 kc, ValCmp2 vc, sort_by_index_yes, ValueInline) {
  		KeyIndex* index = NULL;
  		try { index = buildindex(); } catch (const std::bad_alloc&) {}
  		if (index) {
  			nark_parallel_sort(index, index + nNodes,
  				cmp_by_index_ValueInline_v2k2<KeyCmp2, ValCmp2>(strpool, pNodes, kc, vc));
  			rearrange_nodes(index);
  			rearrange_strpool(); // must after rearrange_nodes
  			if (bucket) // is hash disabled?
  				relink();
  		}
  		else // alloc fail, fall back to in-place sort
  			sort_v2k2_(kc, vc, sort_by_index_no(), ValueInline());
  	}
  	template<class KeyCmp2, class ValCmp2>
  	void sort_v2k2_(KeyCmp2 kc, ValCmp2 vc,	sort_by_index_no, ValueInline) {
  		save_strlen_to_link();
  		nark_parallel_sort(pNodes, pNodes + nNodes, cmp_ValueInline_v2k2<KeyCmp2, ValCmp2>(strpool, kc, vc));
  		rearrange_strpool(); // must after rearrange_nodes
  		if (bucket) // is hash disabled?
  			relink_fill();
  	}
  public:
  	template<class KeyCmp2, class ValCmp2>
  	void sort_v2k2(ValCmp2 vc, KeyCmp2 kc) {
  		BOOST_STATIC_ASSERT(!is_value_empty);
  		if (nDeleted)
  			revoke_deleted_no_relink();
  		if (nNodes >= 2) {
  			sort_v2k2_(kc, vc, sort_by_index(), ValuePlace());
  		}
  		sort_flag = en_sort_by_val;
  	}
  	template<class ValCmp2>
  	void sort_v2k2(ValCmp2 vc) {
  		sort_v2k2(vc, fstring_func::IF_SP_ALIGN(less_align, less_unalign)());
  	}
  	void sort_v2k2() {
  		sort_v2k2(std::less<Value>(), fstring_func::IF_SP_ALIGN(less_align, less_unalign)());
  	}
  
  	template<class IntVec>
  	void bucket_histogram(IntVec& hist) const {
  		for (size_t i = 0, n = nBucket; i < n; ++i) {
  			size_t listlen = 0;
  			for (LinkTp j = bucket[i]; j != tail; j = pNodes[j].link)
  				++listlen;
  			if (hist.size() <= listlen)
  				hist.resize(listlen+1);
  			hist[listlen]++;
  		}
  	}
  
  	size_t bucket_size() const { return nBucket; }
  
  	template<class OtherHashStrMap>
  	size_t intersection_size(const OtherHashStrMap& y) const {
  		size_t num = 0;
  		if (0 == this->delcnt() && 0 == y.delcnt()) {
  			if (y.end_i() < this->end_i()) {
  				for (size_t i = 0; i < y.end_i(); ++i)
  					if (this->exists(y.key(i))) num++;
  			} else {
  				for (size_t i = 0; i < nNodes; ++i)
  					if (y.exists(this->key(i))) num++;
  			}
  		} else {
  			if (y.size() < this->size()) {
  				for (size_t i = y.beg_i(); i < y.end_i(); i = y.next_i(i))
  					if (this->exists(y.key(i))) num++;
  			} else {
  				for (size_t i = beg_i(); i < end_i(); i = next_i(i))
  					if (y.exists(this->key(i))) num++;
  			}
  		}
  		return num;
  	}
  	template<class OtherHashStrMap>
  	size_t union_size(const OtherHashStrMap& y) const {
  		return this->size() + y.size() - intersection_size(y);
  	}
  
  	template<class DataIO>
  	void dio_load_fast(DataIO& dio) {
  		typename DataIO::my_var_uint64_t Size;
  		typename DataIO::my_var_uint64_t StrPoolSize;
  		dio >> Size;
  		dio >> StrPoolSize;
  		dio >> load_factor;
  		dio.load_is_undefined_for_hash_strmap();
  	}
  	template<class DataIO>
  	void dio_save_fast(DataIO& dio) const {
  		dio.load_is_undefined_for_hash_strmap();
  	}
  
  	// compatible format (compatible to std::map/std::vector ...)
  	template<class DataIO>
  	void dio_load(DataIO& dio) {
  		typename DataIO::my_var_uint64_t Size;
  		clear();
  		dio >> Size;
  		this->reserve(Size.t);
  		std::string key;
  		Value       val;
  		for (size_t i = 0, n = Size.t; i < n; ++i) {
  			dio >> key;
  			dio >> val;
  			this->insert_i(key, val);
  		}
  	}
  	template<class DataIO>
  	void dio_save(DataIO& dio) const {
  		dio << typename DataIO::my_var_uint64_t(this->size());
  		if (this->nDeleted) {
  			for (size_t i = 0, n = this->end_i(); i < n; ++i) {
  				if (!this->is_deleted(i)) {
  					dio << this->key(i);
  					dio << this->val(i);
  				}
  			}
  		} else {
  			for (size_t i = 0, n = this->end_i(); i < n; ++i) {
  				dio << this->key(i);
  				dio << this->val(i);
  			}
  		}
  	}
  
  	template<class DataIO>
  	friend void DataIO_loadObject(DataIO& dio, hash_strmap& self) {
  		self.dio_load(dio);
  	}
  	template<class DataIO>
  	friend void DataIO_saveObject(DataIO& dio, const hash_strmap& self) {
  		self.dio_save(dio);
  	}
  };
  
  template< class Value
  		, class HashFunc = fstring_func::IF_SP_ALIGN( hash_align,  hash)
  		, class KeyEqual = fstring_func::IF_SP_ALIGN(equal_align, equal)
  		, class Deleter = HSM_DefaultDeleter
  		, class LinkTp = unsigned int // could be unsigned short for small map
  		>
  class hash_strmap_p : public nark_ptr_hash_map
  	< hash_strmap<Value*, HashFunc, KeyEqual, ValueInline, FastCopy, LinkTp>, Value*, Deleter>
  {};
  
  // replace all "std::unordered_map" as fast_hash_strmap in your source code
  // which Key is std::string, you will get the advantage of hash_strmap
  // if you don't want to use hash_strmap, just define the macro:
  #ifdef DONT_USE_NARK_fast_hash_strmap
  	#define fast_hash_strmap std::unordered_map
  #else
  template< class Key // dummy for compatible with unordered_map<string,Value>
  		, class Value
  		, class KeyHash = fstring_func::IF_SP_ALIGN(hash_align, hash)
  		, class KeyEqual = fstring_func::IF_SP_ALIGN(equal_align, equal)
  		, class ValuePlace = typename boost::mpl::if_c<
  					!boost::is_empty<Value>::value && // ValueInline should be non-empty
  					sizeof(Value) % sizeof(intptr_t) == 0 && sizeof(Value) <= 32
  				, ValueInline
  				, ValueOut // If Value is empty, ValueOut will not use memory
  			>::type
  		, class CopyStrategy = FastCopy
  		, class LinkTp = unsigned int // could be unsigned short for small map
  		, class HashTp = HSM_HashTp
  		>
  class fast_hash_strmap : public
  	hash_strmap<Value,KeyHash,KeyEqual,ValuePlace,CopyStrategy,LinkTp,HashTp>
  {
  	typedef
  	hash_strmap<Value,KeyHash,KeyEqual,ValuePlace,CopyStrategy,LinkTp,HashTp>
  	super;
  	BOOST_STATIC_ASSERT((boost::is_same<Key, std::string>::value));
  public:
  	explicit
  	fast_hash_strmap(KeyHash hash = KeyHash(), KeyEqual eq = KeyEqual())
  	  : super(hash, eq) {}
  	explicit
  	fast_hash_strmap(size_t cap, KeyHash hash=KeyHash(), KeyEqual eq=KeyEqual())
  	  : super(cap, hash, eq) {}
  
  	template<class DataIO>
  	friend void DataIO_loadObject(DataIO& dio, fast_hash_strmap& self) {
  		self.dio_load(dio);
  	}
  	template<class DataIO>
  	friend void DataIO_saveObject(DataIO& dio, const fast_hash_strmap& self) {
  		self.dio_save(dio);
  	}
  };
  #endif
  
  } // namespace nark
  
  ///////////////////////////////////////////////////////////////////////////////
  
  namespace std { // for std::swap
  
  template< class Value
  		, class HashFunc
  		, class KeyEqual
  		, class ValuePlace
  		, class CopyStrategy
  		, class LinkTp
  		, class HashTp
  		>
  void
  swap(nark::hash_strmap<Value, HashFunc, KeyEqual, ValuePlace, CopyStrategy, LinkTp, HashTp> &x,
  	 nark::hash_strmap<Value, HashFunc, KeyEqual, ValuePlace, CopyStrategy, LinkTp, HashTp> &y)
  {
  	x.swap(y);
  }
  
  template< class Key
  		, class Value
  		, class HashFunc
  		, class KeyEqual
  		, class ValuePlace
  		, class CopyStrategy
  		, class LinkTp
  		, class HashTp
  		>
  void
  swap(nark::fast_hash_strmap<Key, Value, HashFunc, KeyEqual, ValuePlace, CopyStrategy, LinkTp, HashTp> &x,
  	 nark::fast_hash_strmap<Key, Value, HashFunc, KeyEqual, ValuePlace, CopyStrategy, LinkTp, HashTp> &y)
  {
  	x.swap(y);
  }
  
  } // namespace std
  
  #endif // __nark_fast_hash_strmap2__
  
  