docs/hazmat/primitives/padding.rst


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

.. hazmat::

Symmetric Padding
=================

.. module:: cryptography.hazmat.primitives.padding

Padding is a way to take data that may or may not be a multiple of the block
size for a cipher and extend it out so that it is. This is required for many
block cipher modes as they require the data to be encrypted to be an exact
multiple of the block size.


.. class:: PKCS7(block_size)

    PKCS7 padding is a generalization of PKCS5 padding (also known as standard
    padding). PKCS7 padding works by appending ``N`` bytes with the value of
    ``chr(N)``, where ``N`` is the number of bytes required to make the final
    block of data the same size as the block size. A simple example of padding
    is:

    .. doctest::

        >>> from cryptography.hazmat.primitives import padding
        >>> padder = padding.PKCS7(128).padder()
        >>> padded_data = padder.update(b"11111111111111112222222222")
        >>> padded_data
        b'1111111111111111'
        >>> padded_data += padder.finalize()
        >>> padded_data
        b'11111111111111112222222222\x06\x06\x06\x06\x06\x06'
        >>> unpadder = padding.PKCS7(128).unpadder()
        >>> data = unpadder.update(padded_data)
        >>> data
        b'1111111111111111'
        >>> data + unpadder.finalize()
        b'11111111111111112222222222'

    :param block_size: The size of the block in :term:`bits` that the data is
        being padded to.
    :raises ValueError: Raised if block size is not a multiple of 8 or is not
        between 0 and 2040 inclusive.

    .. method:: padder()

        :returns: A padding
            :class:`~cryptography.hazmat.primitives.padding.PaddingContext`
            instance.

    .. method:: unpadder()

        :returns: An unpadding
            :class:`~cryptography.hazmat.primitives.padding.PaddingContext`
            instance.


.. class:: ANSIX923(block_size)

    .. versionadded:: 1.3

    `ANSI X.923`_ padding works by appending ``N-1`` bytes with the value of
    ``0`` and a last byte with the value of ``chr(N)``, where ``N`` is the
    number of bytes required to make the final block of data the same size as
    the block size. A simple example of padding is:

    .. doctest::

        >>> padder = padding.ANSIX923(128).padder()
        >>> padded_data = padder.update(b"11111111111111112222222222")
        >>> padded_data
        b'1111111111111111'
        >>> padded_data += padder.finalize()
        >>> padded_data
        b'11111111111111112222222222\x00\x00\x00\x00\x00\x06'
        >>> unpadder = padding.ANSIX923(128).unpadder()
        >>> data = unpadder.update(padded_data)
        >>> data
        b'1111111111111111'
        >>> data + unpadder.finalize()
        b'11111111111111112222222222'

    :param block_size: The size of the block in :term:`bits` that the data is
        being padded to.
    :raises ValueError: Raised if block size is not a multiple of 8 or is not
        between 0 and 2040 inclusive.

    .. method:: padder()

        :returns: A padding
            :class:`~cryptography.hazmat.primitives.padding.PaddingContext`
            instance.

    .. method:: unpadder()

        :returns: An unpadding
            :class:`~cryptography.hazmat.primitives.padding.PaddingContext`
            instance.


.. class:: PaddingContext

    When calling ``padder()`` or ``unpadder()`` the result will conform to the
    ``PaddingContext`` interface. You can then call ``update(data)`` with data
    until you have fed everything into the context. Once that is done call
    ``finalize()`` to finish the operation and obtain the remainder of the
    data.

    .. method:: update(data)

        :param bytes data: The data you wish to pass into the context.
        :return bytes: Returns the data that was padded or unpadded.
        :raises TypeError: Raised if data is not bytes.
        :raises cryptography.exceptions.AlreadyFinalized: See :meth:`finalize`.
        :raises TypeError: This exception is raised if ``data`` is not ``bytes``.

    .. method:: finalize()

        Finalize the current context and return the rest of the data.

        After ``finalize`` has been called this object can no longer be used;
        :meth:`update` and :meth:`finalize` will raise an
        :class:`~cryptography.exceptions.AlreadyFinalized` exception.

        :return bytes: Returns the remainder of the data.
        :raises TypeError: Raised if data is not bytes.
        :raises ValueError: When trying to remove padding from incorrectly
                            padded data.

.. _`ANSI X.923`: https://en.wikipedia.org/wiki/Padding_%28cryptography%29#ANSI_X.923
// This is free and unencumbered software released into the public domain.
//
// Anyone is free to copy, modify, publish, use, compile, sell, or
// distribute this software, either in source code form or as a compiled
// binary, for any purpose, commercial or non-commercial, and by any
// means.

// -------------------------------------------------------
// Written by Clifford Wolf <clifford@clifford.at> in 2014
// -------------------------------------------------------

#ifndef HASHLIB_H
#define HASHLIB_H

#include <stdexcept>
#include <algorithm>
#include <string>
#include <vector>

namespace hashlib {

const int hashtable_size_trigger = 2;
const int hashtable_size_factor = 3;

// The XOR version of DJB2
inline unsigned int mkhash(unsigned int a, unsigned int b) {
	return ((a << 5) + a) ^ b;
}

// traditionally 5381 is used as starting value for the djb2 hash
const unsigned int mkhash_init = 5381;

// The ADD version of DJB2
// (use this version for cache locality in b)
inline unsigned int mkhash_add(unsigned int a, unsigned int b) {
	return ((a << 5) + a) + b;
}

inline unsigned int mkhash_xorshift(unsigned int a) {
	if (sizeof(a) == 4) {
		a ^= a << 13;
		a ^= a >> 17;
		a ^= a << 5;
	} else if (sizeof(a) == 8) {
		a ^= a << 13;
		a ^= a >> 7;
		a ^= a << 17;
	} else
		throw std::runtime_error("mkhash_xorshift() only implemented for 32 bit and 64 bit ints");
	return a;
}

template<typename T> struct hash_ops {
	static inline bool cmp(const T &a, const T &b) {
		return a == b;
	}
	static inline unsigned int hash(const T &a) {
		return a.hash();
	}
};

struct hash_int_ops {
	template<typename T>
	static inline bool cmp(T a, T b) {
		return a == b;
	}
};

template<> struct hash_ops<int32_t> : hash_int_ops
{
	static inline unsigned int hash(int32_t a) {
		return a;
	}
};
template<> struct hash_ops<int64_t> : hash_int_ops
{
	static inline unsigned int hash(int64_t a) {
		return mkhash((unsigned int)(a), (unsigned int)(a >> 32));
	}
};

template<> struct hash_ops<std::string> {
	static inline bool cmp(const std::string &a, const std::string &b) {
		return a == b;
	}
	static inline unsigned int hash(const std::string &a) {
		unsigned int v = 0;
		for (auto c : a)
			v = mkhash(v, c);
		return v;
	}
};

template<typename P, typename Q> struct hash_ops<std::pair<P, Q>> {
	static inline bool cmp(std::pair<P, Q> a, std::pair<P, Q> b) {
		return a == b;
	}
	static inline unsigned int hash(std::pair<P, Q> a) {
		return mkhash(hash_ops<P>::hash(a.first), hash_ops<Q>::hash(a.second));
	}
};

template<typename... T> struct hash_ops<std::tuple<T...>> {
	static inline bool cmp(std::tuple<T...> a, std::tuple<T...> b) {
		return a == b;
	}
	template<size_t I = 0>
	static inline typename std::enable_if<I == sizeof...(T), unsigned int>::type hash(std::tuple<T...>) {
		return mkhash_init;
	}
	template<size_t I = 0>
	static inline typename std::enable_if<I != sizeof...(T), unsigned int>::type hash(std::tuple<T...> a) {
		typedef hash_ops<typename std::tuple_element<I, std::tuple<T...>>::type> element_ops_t;
		return mkhash(hash<I+1>(a), element_ops_t::hash(std::get<I>(a)));
	}
};

template<typename T> struct hash_ops<std::vector<T>> {
	static inline bool cmp(std::vector<T> a, std::vector<T> b) {
		return a == b;
	}
	static inline unsigned int hash(std::vector<T> a) {
		unsigned int h = mkhash_init;
		for (auto k : a)
			h = mkhash(h, hash_ops<T>::hash(k));
		return h;
	}
};

struct hash_cstr_ops {
	static inline bool cmp(const char *a, const char *b) {
		for (int i = 0; a[i] || b[i]; i++)
			if (a[i] != b[i])
				return false;
		return true;
	}
	static inline unsigned int hash(const char *a) {
		unsigned int hash = mkhash_init;
		while (*a)
			hash = mkhash(hash, *(a++));
		return hash;
	}
};

struct hash_ptr_ops {
	static inline bool cmp(const void *a, const void *b) {
		return a == b;
	}
	static inline unsigned int hash(const void *a) {
		return (uintptr_t)a;
	}
};

struct hash_obj_ops {
	static inline bool cmp(const void *a, const void *b) {
		return a == b;
	}
	template<typename T>
	static inline unsigned int hash(const T *a) {
		return a ? a->hash() : 0;
	}
};

template<typename T>
inline unsigned int mkhash(const T &v) {
	return hash_ops<T>().hash(v);
}

inline int hashtable_size(int min_size)
{
	static std::vector<int> zero_and_some_primes = {
		0, 23, 29, 37, 47, 59, 79, 101, 127, 163, 211, 269, 337, 431, 541, 677,
		853, 1069, 1361, 1709, 2137, 2677, 3347, 4201, 5261, 6577, 8231, 10289,
		12889, 16127, 20161, 25219, 31531, 39419, 49277, 61603, 77017, 96281,
		120371, 150473, 188107, 235159, 293957, 367453, 459317, 574157, 717697,
		897133, 1121423, 1401791, 1752239, 2190299, 2737937, 3422429, 4278037,
		5347553, 6684443, 8355563, 10444457, 13055587, 16319519, 20399411,
		25499291, 31874149, 39842687, 49803361, 62254207, 77817767, 97272239,
		121590311, 151987889, 189984863, 237481091, 296851369, 371064217
	};

	for (auto p : zero_and_some_primes)
		if (p >= min_size) return p;

	if (sizeof(int) == 4)
		throw std::length_error("hash table exceeded maximum size. use a ILP64 abi for larger tables.");

	for (auto p : zero_and_some_primes)
		if (100129 * p > min_size) return 100129 * p;

	throw std::length_error("hash table exceeded maximum size.");
}

template<typename K, typename T, typename OPS = hash_ops<K>> class dict;
template<typename K, int offset = 0, typename OPS = hash_ops<K>> class idict;
template<typename K, typename OPS = hash_ops<K>> class pool;
template<typename K, typename OPS = hash_ops<K>> class mfp;

template<typename K, typename T, typename OPS>
class dict
{
	struct entry_t
	{
		std::pair<K, T> udata;
		int next;

		entry_t() { }
		entry_t(const std::pair<K, T> &udata, int next) : udata(udata), next(next) { }
		entry_t(std::pair<K, T> &&udata, int next) : udata(std::move(udata)), next(next) { }
	};

	std::vector<int> hashtable;
	std::vector<entry_t> entries;
	OPS ops;

#ifdef NDEBUG
	static inline void do_assert(bool) { }
#else
	static inline void do_assert(bool cond) {
		if (!cond) throw std::runtime_error("dict<> assert failed.");
	}
#endif

	int do_hash(const K &key) const
	{
		unsigned int hash = 0;
		if (!hashtable.empty())
			hash = ops.hash(key) % (unsigned int)(hashtable.size());
		return hash;
	}

	void do_rehash()
	{
		hashtable.clear();
		hashtable.resize(hashtable_size(entries.capacity() * hashtable_size_factor), -1);

		for (int i = 0; i < int(entries.size()); i++) {
			do_assert(-1 <= entries[i].next && entries[i].next < int(entries.size()));
			int hash = do_hash(entries[i].udata.first);
			entries[i].next = hashtable[hash];
			hashtable[hash] = i;
		}
	}

	int do_erase(int index, int hash)
	{
		do_assert(index < int(entries.size()));
		if (hashtable.empty() || index < 0)
			return 0;

		int k = hashtable[hash];
		do_assert(0 <= k && k < int(entries.size()));

		if (k == index) {
			hashtable[hash] = entries[index].next;
		} else {
			while (entries[k].next != index) {
				k = entries[k].next;
				do_assert(0 <= k && k < int(entries.size()));
			}
			entries[k].next = entries[index].next;
		}

		int back_idx = entries.size()-1;

		if (index != back_idx)
		{
			int back_hash = do_hash(entries[back_idx].udata.first);

			k = hashtable[back_hash];
			do_assert(0 <= k && k < int(entries.size()));

			if (k == back_idx) {
				hashtable[back_hash] = index;
			} else {
				while (entries[k].next != back_idx) {
					k = entries[k].next;
					do_assert(0 <= k && k < int(entries.size()));
				}
				entries[k].next = index;
			}

			entries[index] = std::move(entries[back_idx]);
		}

		entries.pop_back();

		if (entries.empty())
			hashtable.clear();

		return 1;
	}

	int do_lookup(const K &key, int &hash) const
	{
		if (hashtable.empty())
			return -1;

		if (entries.size() * hashtable_size_trigger > hashtable.size()) {
			((dict*)this)->do_rehash();
			hash = do_hash(key);
		}

		int index = hashtable[hash];

		while (index >= 0 && !ops.cmp(entries[index].udata.first, key)) {
			index = entries[index].next;
			do_assert(-1 <= index && index < int(entries.size()));
		}

		return index;
	}

	int do_insert(const K &key, int &hash)
	{
		if (hashtable.empty()) {
			entries.push_back(entry_t(std::pair<K, T>(key, T()), -1));
			do_rehash();
			hash = do_hash(key);
		} else {
			entries.push_back(entry_t(std::pair<K, T>(key, T()), hashtable[hash]));
			hashtable[hash] = entries.size() - 1;
		}
		return entries.size() - 1;
	}

	int do_insert(const std::pair<K, T> &value, int &hash)
	{
		if (hashtable.empty()) {
			entries.push_back(entry_t(value, -1));
			do_rehash();
			hash = do_hash(value.first);
		} else {
			entries.push_back(entry_t(value, hashtable[hash]));
			hashtable[hash] = entries.size() - 1;
		}
		return entries.size() - 1;
	}

public:
	class const_iterator : public std::iterator<std::forward_iterator_tag, std::pair<K, T>>
	{
		friend class dict;
	protected:
		const dict *ptr;
		int index;
		const_iterator(const dict *ptr, int index) : ptr(ptr), index(index) { }
	public:
		const_iterator() { }
		const_iterator operator++() { index--; return *this; }
		bool operator<(const const_iterator &other) const { return index > other.index; }
		bool operator==(const const_iterator &other) const { return index == other.index; }
		bool operator!=(const const_iterator &other) const { return index != other.index; }
		const std::pair<K, T> &operator*() const { return ptr->entries[index].udata; }
		const std::pair<K, T> *operator->() const { return &ptr->entries[index].udata; }
	};

	class iterator : public std::iterator<std::forward_iterator_tag, std::pair<K, T>>
	{
		friend class dict;
	protected:
		dict *ptr;
		int index;
		iterator(dict *ptr, int index) : ptr(ptr), index(index) { }
	public:
		iterator() { }
		iterator operator++() { index--; return *this; }
		bool operator<(const iterator &other) const { return index > other.index; }
		bool operator==(const iterator &other) const { return index == other.index; }
		bool operator!=(const iterator &other) const { return index != other.index; }
		std::pair<K, T> &operator*() { return ptr->entries[index].udata; }
		std::pair<K, T> *operator->() { return &ptr->entries[index].udata; }
		const std::pair<K, T> &operator*() const { return ptr->entries[index].udata; }
		const std::pair<K, T> *operator->() const { return &ptr->entries[index].udata; }
		operator const_iterator() const { return const_iterator(ptr, index); }
	};

	dict()
	{
	}

	dict(const dict &other)
	{
		entries = other.entries;
		do_rehash();
	}

	dict(dict &&other)
	{
		swap(other);
	}

	dict &operator=(const dict &other) {
		entries = other.entries;
		do_rehash();
		return *this;
	}

	dict &operator=(dict &&other) {
		clear();
		swap(other);
		return *this;
	}

	dict(const std::initializer_list<std::pair<K, T>> &list)
	{
		for (auto &it : list)
			insert(it);
	}

	template<class InputIterator>
	dict(InputIterator first, InputIterator last)
	{
		insert(first, last);
	}

	template<class InputIterator>
	void insert(InputIterator first, InputIterator last)
	{
		for (; first != last; ++first)
			insert(*first);
	}

	std::pair<iterator, bool> insert(const K &key)
	{
		int hash = do_hash(key);
		int i = do_lookup(key, hash);
		if (i >= 0)
			return std::pair<iterator, bool>(iterator(this, i), false);
		i = do_insert(key, hash);
		return std::pair<iterator, bool>(iterator(this, i), true);
	}

	std::pair<iterator, bool> insert(const std::pair<K, T> &value)
	{
		int hash = do_hash(value.first);
		int i = do_lookup(value.first, hash);
		if (i >= 0)
			return std::pair<iterator, bool>(iterator(this, i), false);
		i = do_insert(value, hash);
		return std::pair<iterator, bool>(iterator(this, i), true);
	}

	int erase(const K &key)
	{
		int hash = do_hash(key);
		int index = do_lookup(key, hash);
		return do_erase(index, hash);
	}

	iterator erase(iterator it)
	{
		int hash = do_hash(it->first);
		do_erase(it.index, hash);
		return ++it;
	}

	int count(const K &key) const
	{
		int hash = do_hash(key);
		int i = do_lookup(key, hash);
		return i < 0 ? 0 : 1;
	}

	int count(const K &key, const_iterator it) const
	{
		int hash = do_hash(key);
		int i = do_lookup(key, hash);
		return i < 0 || i > it.index ? 0 : 1;
	}

	iterator find(const K &key)
	{
		int hash = do_hash(key);
		int i = do_lookup(key, hash);
		if (i < 0)
			return end();
		return iterator(this, i);
	}

	const_iterator find(const K &key) const
	{
		int hash = do_hash(key);
		int i = do_lookup(key, hash);
		if (i < 0)
			return end();
		return const_iterator(this, i);
	}

	T& at(const K &key)
	{
		int hash = do_hash(key);
		int i = do_lookup(key, hash);
		if (i < 0)
			throw std::out_of_range("dict::at()");
		return entries[i].udata.second;
	}

	const T& at(const K &key) const
	{
		int hash = do_hash(key);
		int i = do_lookup(key, hash);
		if (i < 0)
			throw std::out_of_range("dict::at()");
		return entries[i].udata.second;
	}

	T at(const K &key, const T &defval) const
	{
		int hash = do_hash(key);
		int i = do_lookup(key, hash);
		if (i < 0)
			return defval;
		return entries[i].udata.second;
	}

	T& operator[](const K &key)
	{
		int hash = do_hash(key);
		int i = do_lookup(key, hash);
		if (i < 0)
			i = do_insert(std::pair<K, T>(key, T()), hash);
		return entries[i].udata.second;
	}

	template<typename Compare = std::less<K>>
	void sort(Compare comp = Compare())
	{
		std::sort(entries.begin(), entries.end(), [comp](const entry_t &a, const entry_t &b){ return comp(b.udata.first, a.udata.first); });
		do_rehash();
	}

	void swap(dict &other)
	{
		hashtable.swap(other.hashtable);
		entries.swap(other.entries);
	}

	bool operator==(const dict &other) const {
		if (size() != other.size())
			return false;
		for (auto &it : entries) {
			auto oit = other.find(it.udata.first);
			if (oit == other.end() || !(oit->second == it.udata.second))
				return false;
		}
		return true;
	}

	bool operator!=(const dict &other) const {
		return !operator==(other);
	}

	void reserve(size_t n) { entries.reserve(n); }
	size_t size() const { return entries.size(); }
	bool empty() const { return entries.empty(); }
	void clear() { hashtable.clear(); entries.clear(); }

	iterator begin() { return iterator(this, int(entries.size())-1); }
	iterator end() { return iterator(nullptr, -1); }

	const_iterator begin() const { return const_iterator(this, int(entries.size())-1); }
	const_iterator end() const { return const_iterator(nullptr, -1); }
};

template<typename K, typename OPS>
class pool
{
	template<typename, int, typename> friend class idict;

protected:
	struct entry_t
	{
		K udata;
		int next;

		entry_t() { }
		entry_t(const K &udata, int next) : udata(udata), next(next) { }
	};

	std::vector<int> hashtable;
	std::vector<entry_t> entries;
	OPS ops;

#ifdef NDEBUG
	static inline void do_assert(bool) { }
#else
	static inline void do_assert(bool cond) {
		if (!cond) throw std::runtime_error("pool<> assert failed.");
	}
#endif

	int do_hash(const K &key) const
	{
		unsigned int hash = 0;
		if (!hashtable.empty())
			hash = ops.hash(key) % (unsigned int)(hashtable.size());
		return hash;
	}

	void do_rehash()
	{
		hashtable.clear();
		hashtable.resize(hashtable_size(entries.capacity() * hashtable_size_factor), -1);

		for (int i = 0; i < int(entries.size()); i++) {
			do_assert(-1 <= entries[i].next && entries[i].next < int(entries.size()));
			int hash = do_hash(entries[i].udata);
			entries[i].next = hashtable[hash];
			hashtable[hash] = i;
		}
	}

	int do_erase(int index, int hash)
	{
		do_assert(index < int(entries.size()));
		if (hashtable.empty() || index < 0)
			return 0;

		int k = hashtable[hash];
		if (k == index) {
			hashtable[hash] = entries[index].next;
		} else {
			while (entries[k].next != index) {
				k = entries[k].next;
				do_assert(0 <= k && k < int(entries.size()));
			}
			entries[k].next = entries[index].next;
		}

		int back_idx = entries.size()-1;

		if (index != back_idx)
		{
			int back_hash = do_hash(entries[back_idx].udata);

			k = hashtable[back_hash];
			if (k == back_idx) {
				hashtable[back_hash] = index;
			} else {
				while (entries[k].next != back_idx) {
					k = entries[k].next;
					do_assert(0 <= k && k < int(entries.size()));
				}
				entries[k].next = index;
			}

			entries[index] = std::move(entries[back_idx]);
		}

		entries.pop_back();

		if (entries.empty())
			hashtable.clear();

		return 1;
	}

	int do_lookup(const K &key, int &hash) const
	{
		if (hashtable.empty())
			return -1;

		if (entries.size() * hashtable_size_trigger > hashtable.size()) {
			((pool*)this)->do_rehash();
			hash = do_hash(key);
		}

		int index = hashtable[hash];

		while (index >= 0 && !ops.cmp(entries[index].udata, key)) {
			index = entries[index].next;
			do_assert(-1 <= index && index < int(entries.size()));
		}

		return index;
	}

	int do_insert(const K &value, int &hash)
	{
		if (hashtable.empty()) {
			entries.push_back(entry_t(value, -1));
			do_rehash();
			hash = do_hash(value);
		} else {
			entries.push_back(entry_t(value, hashtable[hash]));
			hashtable[hash] = entries.size() - 1;
		}
		return entries.size() - 1;
	}

public:
	class const_iterator : public std::iterator<std::forward_iterator_tag, K>
	{
		friend class pool;
	protected:
		const pool *ptr;
		int index;
		const_iterator(const pool *ptr, int index) : ptr(ptr), index(index) { }
	public:
		const_iterator() { }
		const_iterator operator++() { index--; return *this; }
		bool operator==(const const_iterator &other) const { return index == other.index; }
		bool operator!=(const const_iterator &other) const { return index != other.index; }
		const K &operator*() const { return ptr->entries[index].udata; }
		const K *operator->() const { return &ptr->entries[index].udata; }
	};

	class iterator : public std::iterator<std::forward_iterator_tag, K>
	{
		friend class pool;
	protected:
		pool *ptr;
		int index;
		iterator(pool *ptr, int index) : ptr(ptr), index(index) { }
	public:
		iterator() { }
		iterator operator++() { index--; return *this; }
		bool operator==(const iterator &other) const { return index == other.index; }
		bool operator!=(const iterator &other) const { return index != other.index; }
		K &operator*() { return ptr->entries[index].udata; }
		K *operator->() { return &ptr->entries[index].udata; }
		const K &operator*() const { return ptr->entries[index].udata; }
		const K *operator->() const { return &ptr->entries[index].udata; }
		operator const_iterator() const { return const_iterator(ptr, index); }
	};

	pool()
	{
	}

	pool(const pool &other)
	{
		entries = other.entries;
		do_rehash();
	}

	pool(pool &&other)
	{
		swap(other);
	}

	pool &operator=(const pool &other) {
		entries = other.entries;
		do_rehash();
		return *this;
	}

	pool &operator=(pool &&other) {
		clear();
		swap(other);
		return *this;
	}

	pool(const std::initializer_list<K> &list)
	{
		for (auto &it : list)
			insert(it);
	}

	template<class InputIterator>
	pool(InputIterator first, InputIterator last)
	{
		insert(first, last);
	}

	template<class InputIterator>
	void insert(InputIterator first, InputIterator last)
	{
		for (; first != last; ++first)
			insert(*first);
	}

	std::pair<iterator, bool> insert(const K &value)
	{
		int hash = do_hash(value);
		int i = do_lookup(value, hash);
		if (i >= 0)
			return std::pair<iterator, bool>(iterator(this, i), false);
		i = do_insert(value, hash);
		return std::pair<iterator, bool>(iterator(this, i), true);
	}

	int erase(const K &key)
	{
		int hash = do_hash(key);
		int index = do_lookup(key, hash);
		return do_erase(index, hash);
	}

	iterator erase(iterator it)
	{
		int hash = do_hash(*it);
		do_erase(it.index, hash);
		return ++it;
	}

	int count(const K &key) const
	{
		int hash = do_hash(key);
		int i = do_lookup(key, hash);
		return i < 0 ? 0 : 1;
	}

	int count(const K &key, const_iterator it) const
	{
		int hash = do_hash(key);
		int i = do_lookup(key, hash);
		return i < 0 || i > it.index ? 0 : 1;
	}