<commit_before>// Copyright (c) 2014, ultramailman
// This file is licensed under the MIT License.

#ifndef CHTABLE_H
#define CHTABLE_H
#include <vector>
#include <tuple>
namespace{
	bool isPrime(unsigned x)
	{
		if((x & 1) != 1) {
			return false;
		}
		char easy [] = {0, 1, 1, 1, 0, 1, 0, 1};
		if(x < sizeof easy) {
			return easy[x] != 0;
		}
		
		unsigned const half = x / 2;
		for(unsigned i = 3; i < half; i+=2){
			if(x % i == 0)
				return false;
		}
		return true;
	}
	unsigned nextPrime(unsigned const x)
	{
		unsigned n = x;
		if(n / 2 * 2 == n) {
			n++;
		}
		while(!isPrime(n)) {
			n += 2;
		}
		
		if(n >= x) {
			return n;
		} else {
			return -1;
		}
	}
}


namespace chtable{
	template <class K>
	struct Hash;

}
template <class K, class V>
struct Slot{
	unsigned present;
	K key;
	V val;
};

template <class K, class V>
class Chtable{
	unsigned count_;
	unsigned slots_;
	unsigned tables_;
	std::vector< Slot<K, V> > array_;
	chtable::Hash<K> uhash_;
	
	unsigned index(unsigned table, unsigned hash) const
	{
		return table * slots_ + hash;
	}
	
	unsigned totalSlots() const
	{
		return tables_ * slots_;
	}
	bool replace(K const & key, V val);
	bool insert(K & key, V & val);
public:
	Chtable( unsigned size , unsigned tableCount)
	:
		count_(0),
		
		slots_( nextPrime(size / tableCount + 1) ),
		tables_(tableCount),
		
		array_(totalSlots()),
		
		uhash_(tables_, slots_)
	{}
	
	Chtable() : Chtable(13, 2) {}

	std::tuple<V, bool> Get(K const & key) const;
	bool Set(K key, V val);
	bool Delete(K const & key);
	
};

//.......................... SEARCH ......................................
template<class K, class V>
std::tuple<V, bool> Chtable<K,V>::
Get(K const & key) const
{
	for(unsigned i = 0; i < tables_; i++) {
		unsigned hash = uhash_(i, key) % slots_;
		unsigned j = index(i, hash);
		auto const & slot = array_[j];
		if(slot.present and key == slot.key) {
			return std::make_tuple(slot.val, true);
		}
	}
	return std::make_tuple(V(), false);
}

//............................ INSERTION ..................................
template<class K, class V>
bool Chtable<K, V>::
replace(K const & key, V val)
{
	for(unsigned i = 0; i < tables_; i++) {
		unsigned hash = uhash_(i, key) % slots_;
		unsigned j = index(i, hash);
		auto & slot = array_[j];
		if(slot.present and key == slot.key) {
			slot.val = val;
			return true;
		}
	}
	return false;
}

template<class K, class V>
bool Chtable<K, V>::
insert(K & key, V & val)
{
	for(unsigned i = 0, timeout = tables_ * count_ + 1; timeout != 0; timeout--) {
		unsigned hash = uhash_(i, key) % slots_;
		unsigned j = index(i, hash);
		auto & slot = array_[j];
		std::swap(slot.key, key);
		std::swap(slot.val, val);
		
		if(slot.present) {
			i++;
			if(i == tables_) {
				i = 0;
			}
		} else {
			slot.present = true;
			count_++;
			return true;
		}
	}
	return false;
}
template<class K, class V>
bool Chtable<K, V>::
Set(K key, V val)
{
	if(replace(key, val)) {
		return true;
	}
	while(not insert(key, val)) {
		Chtable<K, V> bigger( nextPrime(totalSlots() * 2) , tables_);
		for(auto & slot : array_) {
			if(slot.present) {
				bigger.Set(slot.key, slot.val);
			}
		}
		std::swap(*this, bigger);
	}
	return true;
}

//................................... DELETION .......................
template<class K, class V>
bool Chtable<K, V>::
Delete(K const & key)
{
	for(unsigned i = 0; i < tables_; i++) {
		unsigned hash = uhash_(i, key) % slots_;
		unsigned j = index(i, hash);
		auto & slot = array_[j];
		if(slot.present and key == slot.key) {
			slot.present = false;
			slot.val = V();
			count_--;
			return true;
		}
	}
	return false;
}

#endif<commit_msg>added methods to query status of table<commit_after>// Copyright (c) 2014, ultramailman
// This file is licensed under the MIT License.

#ifndef CHTABLE_H
#define CHTABLE_H
#include <vector>
#include <tuple>
namespace{
	bool isPrime(unsigned x)
	{
		if((x & 1) != 1) {
			return false;
		}
		char easy [] = {0, 1, 1, 1, 0, 1, 0, 1};
		if(x < sizeof easy) {
			return easy[x] != 0;
		}
		
		unsigned const half = x / 2;
		for(unsigned i = 3; i < half; i+=2){
			if(x % i == 0)
				return false;
		}
		return true;
	}
	unsigned nextPrime(unsigned const x)
	{
		unsigned n = x;
		if(n / 2 * 2 == n) {
			n++;
		}
		while(!isPrime(n)) {
			n += 2;
		}
		
		if(n >= x) {
			return n;
		} else {
			return -1;
		}
	}
}


namespace chtable{
	template <class K>
	struct Hash;

}
template <class K, class V>
struct Slot{
	unsigned present;
	K key;
	V val;
};

template <class K, class V>
class Chtable{
	unsigned count_;
	unsigned slots_;
	unsigned tables_;
	std::vector< Slot<K, V> > array_;
	chtable::Hash<K> uhash_;
	
	unsigned index(unsigned table, unsigned hash) const
	{
		return table * slots_ + hash;
	}
	
	bool replace(K const & key, V val);
	bool insert(K & key, V & val);
public:
	Chtable( unsigned size , unsigned tableCount)
	:
		count_(0),
		
		slots_( nextPrime(size / tableCount + 1) ),
		tables_(tableCount),
		
		array_(capacity()),
		
		uhash_(tables_, slots_)
	{}
	
	Chtable() : Chtable(13, 2) {}

	unsigned count() const { return count_; }
	unsigned capacity() const { return tables_ * slots_; }
	std::tuple<V, bool> Get(K const & key) const;
	bool Set(K key, V val);
	bool Delete(K const & key);
	
};

//.......................... SEARCH ......................................
template<class K, class V>
std::tuple<V, bool> Chtable<K,V>::
Get(K const & key) const
{
	for(unsigned i = 0; i < tables_; i++) {
		unsigned hash = uhash_(i, key) % slots_;
		unsigned j = index(i, hash);
		auto const & slot = array_[j];
		if(slot.present and key == slot.key) {
			return std::make_tuple(slot.val, true);
		}
	}
	return std::make_tuple(V(), false);
}

//............................ INSERTION ..................................
template<class K, class V>
bool Chtable<K, V>::
replace(K const & key, V val)
{
	for(unsigned i = 0; i < tables_; i++) {
		unsigned hash = uhash_(i, key) % slots_;
		unsigned j = index(i, hash);
		auto & slot = array_[j];
		if(slot.present and key == slot.key) {
			slot.val = val;
			return true;
		}
	}
	return false;
}

template<class K, class V>
bool Chtable<K, V>::
insert(K & key, V & val)
{
	for(unsigned i = 0, timeout = tables_ * count_ + 1; timeout != 0; timeout--) {
		unsigned hash = uhash_(i, key) % slots_;
		unsigned j = index(i, hash);
		auto & slot = array_[j];
		std::swap(slot.key, key);
		std::swap(slot.val, val);
		
		if(slot.present) {
			i++;
			if(i == tables_) {
				i = 0;
			}
		} else {
			slot.present = true;
			count_++;
			return true;
		}
	}
	return false;
}
template<class K, class V>
bool Chtable<K, V>::
Set(K key, V val)
{
	if(replace(key, val)) {
		return true;
	}
	while(not insert(key, val)) {
		Chtable<K, V> bigger( nextPrime(capacity() * 2) , tables_);
		for(auto & slot : array_) {
			if(slot.present) {
				bigger.Set(slot.key, slot.val);
			}
		}
		std::swap(*this, bigger);
	}
	return true;
}

//................................... DELETION .......................
template<class K, class V>
bool Chtable<K, V>::
Delete(K const & key)
{
	for(unsigned i = 0; i < tables_; i++) {
		unsigned hash = uhash_(i, key) % slots_;
		unsigned j = index(i, hash);
		auto & slot = array_[j];
		if(slot.present and key == slot.key) {
			slot.present = false;
			slot.val = V();
			count_--;
			return true;
		}
	}
	return false;
}

#endif
{'fraction_non_alphanumeric': 0.20546641283655154, 'fraction_numerical': 0.009790590155017678, 'mean_word_length': 2.5309649543927026, 'pattern_counts': {'":': 0, '<': 55, '<?xml version=': 0, '>': 47, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1496193', 'n_tokens_mistral': 3067, 'n_tokens_neox': 2727, 'n_words': 800}