144 lines
3.2 KiB
C++
144 lines
3.2 KiB
C++
#pragma once
|
|
|
|
//hashset
|
|
//
|
|
//search: O(1) average; O(n) worst
|
|
//insert: O(1) average; O(n) worst
|
|
//remove: O(1) average; O(n) worst
|
|
//
|
|
//requirements:
|
|
// auto T::hash() const -> u32;
|
|
// auto T::operator==(const T&) const -> bool;
|
|
|
|
namespace nall {
|
|
|
|
template<typename T>
|
|
struct hashset {
|
|
hashset() = default;
|
|
hashset(u32 length) : length(bit::round(length)) {}
|
|
hashset(const hashset& source) { operator=(source); }
|
|
hashset(hashset&& source) { operator=(std::move(source)); }
|
|
~hashset() { reset(); }
|
|
|
|
auto operator=(const hashset& source) -> hashset& {
|
|
if(this == &source) return *this;
|
|
reset();
|
|
if(source.pool) {
|
|
for(u32 n : range(source.length)) {
|
|
if(source.pool[n]) insert(*source.pool[n]);
|
|
}
|
|
}
|
|
return *this;
|
|
}
|
|
|
|
auto operator=(hashset&& source) -> hashset& {
|
|
if(this == &source) return *this;
|
|
reset();
|
|
pool = source.pool;
|
|
length = source.length;
|
|
count = source.count;
|
|
source.pool = nullptr;
|
|
source.length = 8;
|
|
source.count = 0;
|
|
return *this;
|
|
}
|
|
|
|
explicit operator bool() const { return count; }
|
|
auto capacity() const -> u32 { return length; }
|
|
auto size() const -> u32 { return count; }
|
|
|
|
auto reset() -> void {
|
|
if(pool) {
|
|
for(u32 n : range(length)) {
|
|
if(pool[n]) {
|
|
delete pool[n];
|
|
pool[n] = nullptr;
|
|
}
|
|
}
|
|
delete[] pool;
|
|
pool = nullptr;
|
|
}
|
|
length = 8;
|
|
count = 0;
|
|
}
|
|
|
|
auto reserve(u32 size) -> void {
|
|
if(length >= size) return;
|
|
|
|
//ensure all items will fit into pool (with <= 50% load) and amortize growth
|
|
size = bit::round(max(size, count << 1));
|
|
T** copy = new T*[size]();
|
|
|
|
if(pool) {
|
|
for(u32 n : range(length)) {
|
|
if(pool[n]) {
|
|
u32 hash = (*pool[n]).hash() & (size - 1);
|
|
while(copy[hash]) if(++hash >= size) hash = 0;
|
|
copy[hash] = pool[n];
|
|
pool[n] = nullptr;
|
|
}
|
|
}
|
|
}
|
|
|
|
delete[] pool;
|
|
pool = copy;
|
|
length = size;
|
|
}
|
|
|
|
auto find(const T& value) -> maybe<T&> {
|
|
if(!pool) return nothing;
|
|
|
|
u32 hash = value.hash() & (length - 1);
|
|
while(pool[hash]) {
|
|
if(value == *pool[hash]) return *pool[hash];
|
|
if(++hash >= length) hash = 0;
|
|
}
|
|
|
|
return nothing;
|
|
}
|
|
|
|
auto insert(const T& value) -> maybe<T&> {
|
|
if(!pool) pool = new T*[length]();
|
|
|
|
//double pool size when load is >= 50%
|
|
if(count >= (length >> 1)) reserve(length << 1);
|
|
|
|
u32 hash = value.hash() & (length - 1);
|
|
while(pool[hash]) {
|
|
if(value == *pool[hash]) return nothing;
|
|
if(++hash >= length) hash = 0;
|
|
}
|
|
count++;
|
|
pool[hash] = new T(value);
|
|
|
|
return *pool[hash];
|
|
}
|
|
|
|
#if 0
|
|
//does not work! todo: implement tombstones or rehashing to fill gaps.
|
|
auto remove(const T& value) -> bool {
|
|
if(!pool) return false;
|
|
|
|
u32 hash = value.hash() & (length - 1);
|
|
while(pool[hash]) {
|
|
if(value == *pool[hash]) {
|
|
delete pool[hash];
|
|
pool[hash] = nullptr;
|
|
count--;
|
|
return true;
|
|
}
|
|
if(++hash >= length) hash = 0;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
#endif
|
|
|
|
protected:
|
|
T** pool = nullptr;
|
|
u32 length = 8; //length of pool
|
|
u32 count = 0; //number of objects inside of the pool
|
|
};
|
|
|
|
}
|