hash_map.h

///////////////////////////////////////////////////////////////////////////////
//                                                                             
//  Copyright (C) 2008-2012  Artyom Beilis (Tonkikh) <artyomtnk@yahoo.com>     
//                                                                             
//  See accompanying file COPYING.TXT file for licensing details.
//
///////////////////////////////////////////////////////////////////////////////
#ifndef CPPCMS_IMPL_HASH_MAP_H
#define CPPCMS_IMPL_HASH_MAP_H

#include <new>
#include <functional>
#include <vector>
#include <utility>
#include <assert.h>

#include <cppcms/cstdint.h>
#include <booster/iterator/iterator_facade.h>
namespace cppcms {
namespace impl {
	
struct string_hash {
public:
	typedef uint32_t state_type;
	static const state_type initial_state = 0;
	static state_type update_state(state_type value,char c)
	{
		value = (value << 4) + static_cast<unsigned char>(c);
		uint32_t high = (value & 0xF0000000U);
		if(high!=0)
		value = (value ^ (high >> 24)) ^ high;
		return value;
	}

	template<typename T>
	size_t operator()(T const &v) const
	{
		state_type st = initial_state;
		for(typename T::const_iterator p=v.begin();p!=v.end();++p) {
			st = update_state(st,*p);
		}
		return st;
	}
};
	
namespace details {

struct are_equal {
	template<typename T1,typename T2>
	bool operator()(T1 const &v1,T2 const &v2) const
	{
		return v1==v2;
	}
};


template<typename T>
class intrusive_list
{
public:
	intrusive_list() : begin(0), end(0)
	{
	}

	void push_back(T *p)
	{
		p->next = 0;
		p->prev = end;
		if(end)
			end->next = p;
		end = p;

		if(begin == 0)
			begin = p;
	}
	void push_front(T *p)
	{
		p->next = begin;
		p->prev = 0;
		if(begin)
			begin->prev = p;
		begin = p;
		if(end == 0)
			end = p;
	}
	void erase(T *p)
	{
		if(p->prev) {
			p->prev->next = p->next;
		}
		if(p->next) {
			p->next->prev = p->prev;
		}
		if(begin == p)
			begin = p->next;
		if(end == p)
			end = p->prev;
		p->next = p->prev = 0;
	}

	void insert_after(T *p,T *after_me)
	{
		if(!after_me->next) {
			push_back(p);
			return;
		}
		p->prev = after_me;
		p->next = after_me->next;
		if(after_me->next)
			after_me->next->prev = p;
		after_me->next = p;
	}
	void insert_before(T *p,T *before_me)
	{
		if(!before_me->prev) {
			push_front(p);
			return;
		}
		p->next = before_me;
		p->prev = before_me->prev;
		if(before_me->prev)
			before_me->prev->next = p;
		before_me->prev = p;
	}
	void swap(intrusive_list &other)
	{
		std::swap(other.begin,begin);
		std::swap(other.end,end);
	}

	T *begin,*end;
};


template<	typename Key,
		typename Value,
		typename Hash,
		typename Equals=are_equal,
		typename Alloc= std::allocator<std::pair<Key,Value> >
		>
class basic_map
{
public:
	
	basic_map() : size_(0)
	{
	}
	
	~basic_map()
	{
		clear();
	}

	typedef std::pair<const Key,Value> value_type;

	struct container {
		container() : val(), next(0),prev(0) {}
		container(value_type const &v) : val(v), next(0),prev(0) {}
		value_type val;
		size_t hash;
		container *next;
		container *prev;
	};

	typedef container *iterator;
	typedef typename Alloc::template rebind<container>::other container_alloc;

	typedef std::pair<iterator,iterator> range_type;
	typedef typename Alloc::template rebind<range_type>::other vec_allocator;

	iterator erase(iterator p)
	{
		if(p==0)
			return 0;
		range_type &r = get(p->val.first);
		if(r.first == r.second) {
			assert(p == r.first);
			r.first = r.second = 0;
		}
		else if(r.first == p)
			r.first = p->next;
		else if(r.second == p)
			r.second = p->prev;
		iterator next = p->next;
		list_.erase(p);
		size_ --;
		destroy(p);
		return next;
	}
	size_t size() const
	{
		return size_;
	}

	template<typename Kt>
	iterator find(Kt const &k)
	{
		if(hash_.empty())
			return 0;
		range_type &range=get(k);
		return find_in_range(range,k);
	}


	std::pair<iterator,bool> insert(value_type const &entry)
	{
		std::pair<iterator,bool> r(iterator(),false);
		rehash_if_needed();
		range_type &range=get(entry.first);
		iterator p = find_in_range(range,entry.first);
		if(p) {
			r.first = p;
			return r;
		}
		p = allocate(entry);
		if(range.second == 0) {
			list_.push_back(p);
			range.first = range.second = p;
		}
		else {
			list_.insert_after(p,range.second);
			range.second = p;
		}

		r.first = p;
		r.second  = true;
		size_ ++;
		return r;
	}

	void clear()
	{
		iterator p=list_.begin;
		if(size_ / 4 >= hash_.size()) {
			for(size_t i=0;i<hash_.size();i++) {
				hash_[i].first = 0;
				hash_[i].second = 0;
			}
			while(p) {
				iterator del = p;
				p=p->next;
				del->prev = 0;
				del->next = 0;
				destroy(del);
			}
		}
		else {
			while(p) {
				iterator del = p;
				p=p->next;
				del->prev = 0;
				del->next = 0;
				range_type &r=get(del->val.first);
				r.first = r.second = 0;
				destroy(del);
			}
		}
		list_.begin = list_.end = 0;
		size_ = 0;
	}

	iterator begin()
	{
		return list_.begin;
	}
	iterator end()
	{
		return 0;
	}

#ifdef TEST_MAP
	void check()
	{
		size_t count = 0;
		for(iterator p=list_.begin;p!=0;p=p->next,count++) {
			range_type &r = get(p->val.first);
			if(r.first == r.second) {
				TEST(r.first==p);
			}
			bool found = false;
			iterator p2;
			for(p2=r.first;p2!=r.second;p2=p2->next) {
				if(p2 == p) {
					found = true;
					break;
				}
			}
			if(!found)
				TEST(p2 == p);
			if(p->next == 0) {
				TEST(p == list_.end);
			}
		}
		TEST(size_ == count);
		count = 0;
		for(size_t i=0;i<hash_.size();i++) {
			for(iterator p=hash_[i].first;p;p=p->next) {
				count++;
				Hash h;
				TEST(h(p->val.first) % hash_.size() == i);
				if(p==hash_[i].second)
					break;
			}
		}
		TEST(size_ == count);
	}
#endif
	void rehash(size_t new_size)
	{
		basic_map tmp;
		tmp.hash_.resize(new_size,range_type(iterator(),iterator()));
		while(list_.begin) {
			iterator p=list_.begin;
			list_.erase(p);
			range_type &r = tmp.get(p->val.first);
			if(r.first == 0) {
				tmp.list_.push_back(p);
				r.first = r.second = p;
			}
			else {
				tmp.list_.insert_after(p,r.second);
				r.second = p;
			}
		}
		list_.swap(tmp.list_);
		hash_.swap(tmp.hash_);
		tmp.hash_.clear();
	}


private:
	template<typename Kt>
	iterator find_in_range(range_type &r,Kt const &k)
	{
		for(iterator p=r.first;p!=0;p=p->next) {
			Equals compare;
			if(compare(p->val.first,k)) {
				return p;
			}
			if(p==r.second)
				return 0;
		}
		return 0;
	}
	template<typename Kt>
	range_type &get(Kt const &k)
	{
		Hash hf;
		size_t h = hf(k) % hash_.size();
		return hash_[h];
	}

	size_t next_size()
	{
		return (1+size_)*2;
	}
	void rehash_if_needed()
	{
		size_t table_size = hash_.size();
		if(size_ + 1 >= table_size) {
			rehash(next_size());
		}
	}

	iterator allocate(value_type const &v)
	{
		container_alloc al;
		iterator p = al.allocate(1);
		try {
			new (p) container(v);
		}
		catch(...) {
			al.deallocate(p,1);
			throw;
		}
		return p;
	}
	iterator allocate()
	{
		container_alloc al;
		iterator p = al.allocate(1);
		try {
			new (p) container();
		}
		catch(...) {
			al.deallocate(p);
			throw;
		}
		return p;
	}

	void destroy(iterator p)
	{
		container_alloc al;
		p->~container();
		al.deallocate(p,1);
	}

	std::vector<range_type, vec_allocator>  hash_;
	intrusive_list<container> list_;
	size_t size_;
};


} // details

template<	typename Key,
		typename Value,
		typename Hash,
		typename Equals = details::are_equal,
		typename Alloc= std::allocator<std::pair<Key,Value> > >
class hash_map {
	typedef details::basic_map<Key,Value,Hash,Equals,Alloc> impl_type;
	typedef typename impl_type::iterator impl_iterator;
public:
	typedef std::pair<const Key,Value> value_type;

#ifdef TEST_MAP
        void check()
        {
            impl_.check();
        }
#endif

	void rehash(size_t n)
	{
		impl_.rehash(n);
	}

        ~hash_map()
        {
        	clear();
        }

	class iterator :
		public booster::iterator_facade<
				iterator,
				value_type,
				booster::bidirectional_traversal_tag>
	{
	public:
		iterator(typename impl_type::iterator p = 0) : p_(p) {}

		value_type &dereference() const
		{
			return p_->val;
		}
		void increment()
		{
			p_=p_->next;
		}
		void decrement()
		{
			p_=p_->prev;
		}
		bool equal(iterator const &other) const
		{
			return p_==other.p_;
		}
	private:
		friend class hash_map;
		typename impl_type::iterator p_;
	};

	iterator begin()
	{
		return iterator(impl_.begin());
	}
	iterator end()
	{
		return iterator(0);
	}

	template<typename Kt>
	iterator find(Kt const &k)
	{
		return iterator(impl_.find(k));
	}

	std::pair<iterator,bool> insert(value_type const &v)
	{
		std::pair<impl_iterator,bool> r = impl_.insert(v);
		return std::pair<iterator,bool>(iterator(r.first),r.second);
	}
	iterator erase(iterator p)
	{
		return iterator(impl_.erase(p.p_));
	}
	void clear()
	{
		impl_.clear();
	}
	
	size_t size() const
	{
            return impl_.size();
        }

private:
	impl_type impl_;
};




} // impl
} // cppcms


#endif