hash_set.h

#pragma once
#include "vector.h"
#include "hash_function.h"
#include "bucket_iterator.h"
#include "allocator.h"
#include "template_tools.h"
#include "functional.h"
namespace stingray_plugin_foundation {
// Implementation of set using the same technique as HashMap.
//  see HashMap
template <class K, class HASH = default_hash<K>, class EQUAL = equal_to >
class HashSet
{
public:
    ALLOCATOR_AWARE;
    typedef K key_type;
    typedef HASH key_hash;
    typedef EQUAL key_equal;
    typedef HashSet<K, HASH, EQUAL> this_type;
    typedef ConstBucketIterator<this_type, key_type> const_iterator;
    typedef BucketIterator<this_type, key_type> iterator;
    enum {END_OF_LIST = 0x7fffffff, UNUSED = 0xfffffffe, END_OF_FREELIST = 0xffffffff};
    HashSet(Allocator &a);
    HashSet(unsigned buckets, unsigned spill, Allocator &a);
    HashSet(const HashSet<K,HASH,EQUAL> &o);
    ~HashSet();
    void operator=(const HashSet<K,HASH,EQUAL> &o);
    void reserve(unsigned size);
    void swap(HashSet<K,HASH,EQUAL> &o);
    Allocator & allocator() const;
    unsigned size() const;
    bool empty() const;
    template <class KEY_EQ> bool has(const KEY_EQ &k) const;
    void clear();
    template <class KEY_EQ> void insert(const KEY_EQ &k);
    template <class KEY_EQ> void erase(const KEY_EQ &k);
    void rehash(unsigned new_buckets);
    const_iterator begin() const;
    const_iterator end() const;
    unsigned num_buckets() const;
    bool bucket_valid(unsigned i) const;
    const key_type &bucket_value(unsigned i) const;
    key_type &bucket_value(unsigned i);
    template <class STREAM> void serialize(STREAM &stream);
private:
    template <class KEY_EQ> unsigned find_or_fail(const KEY_EQ &k) const;
    template <class KEY_EQ> unsigned find_or_make(const KEY_EQ &k);
    template <class KEY_EQ> void find_and_erase(const KEY_EQ &k);
    bool full() const;
    void grow();
    template <class KEY_EQ> unsigned hash(const KEY_EQ &k) const;
    unsigned allocate_spill();
    void free_spill(unsigned i);
    void clear_freelist();
    void allocate_data(unsigned count);
    void construct(key_type &p, const Int2Type<true> &) { new (&p) key_type(_allocator); }
    void construct(key_type &p, const Int2Type<false> &) { new (&p) key_type(); }
    void destruct(key_type &p) { p.~key_type(); }
    struct Data {
        Data() : size(), marker(), key() {}
        unsigned size;
        unsigned *marker;
        key_type *key;
    };
    key_hash        _hash;
    key_equal       _equal;
    Data            _data;
    unsigned        _used;
    unsigned        _buckets;
    unsigned        _spill_unused;
    unsigned        _spill_freelist;
    Allocator       &_allocator;
};
} // namespace stingray_plugin_foundation
#include "hash_set.inl"