#include "PointerHash.h"
#include "Configuration.h"
#include <assert.h>
namespace Auto {
inline uintptr_t PointerHash::hash(void *pointer) const {
return uintptr_t(pointer) >> allocate_quantum_small_log2;
}
void PointerHash::add(void *pointer, uint32_t flags) {
insert(pointer, flags);
if (_count*3 > _capacity*2) {
grow(_capacity * 2); } else if ((_count + _removed + 8) >= _capacity) {
rehash(0x0); }
}
void PointerHash::insert(void *pointer, uint32_t flags) {
uintptr_t h = hash(pointer);
uint32_t index = h & _capacityMask; uint32_t run_length = 0;
vm_address_t probe;
while (validPointer(probe = _pointers[index])) {
if (pointerValue(probe) == pointer) return; index++;
run_length++;
if (index == _capacity)
index = 0;
}
if (probe == (vm_address_t)RemovedEntry)
--_removed;
_pointers[index] = (vm_address_t)pointer | flags;
_count++;
if (index < _firstOccupiedSlot)
_firstOccupiedSlot = index;
if (index > _lastOccupiedSlot)
_lastOccupiedSlot = index;
if (run_length > _maxRunLength)
_maxRunLength = run_length;
}
int32_t PointerHash::slotIndex(void *pointer) const
{
if (_count > 0) {
uintptr_t h = hash(pointer);
const uint32_t kCapacityMask = _capacityMask, kMaxRunLength = _maxRunLength;
uint32_t i = h & kCapacityMask;
uint32_t run = 0;
while (vm_address_t probe = _pointers[i]) {
if (pointerValue(probe) == pointer)
return i;
if (run >= kMaxRunLength)
break;
run++;
i = (i + 1) & kCapacityMask;
}
}
return -1;
}
void PointerHash::remove(uint32_t slot)
{
if (slot < _capacity) {
uint32_t index = slot;
if (_maxRunLength == 0 || _pointers[(index + 1) & _capacityMask] == 0) {
++_removed;
do {
--_removed;
_pointers[index] = NULL;
index = (index == 0 ? _capacity - 1 : index - 1);
} while (_pointers[index] == (vm_address_t)RemovedEntry);
} else {
_pointers[slot] = (vm_address_t)RemovedEntry;
++_removed;
}
_count--;
}
}
void PointerHash::remove(void *pointer)
{
int32_t index = slotIndex(pointer);
if (index != -1) {
remove(index);
}
}
void PointerHash::grow(uint32_t newCapacity, uint32_t flagMask)
{
vm_address_t mask = ~(FlagsMask & flagMask);
vm_address_t *old_pointers = _pointers;
uint32_t old_capacity = _capacity;
uint32_t old_count = _count;
uint32_t i = _firstOccupiedSlot;
if (newCapacity > 0 && newCapacity < MinCapacity)
newCapacity = MinCapacity;
if (_capacity != newCapacity) {
_capacity = newCapacity;
assert(is_power_of_2(_capacity));
_capacityMask = _capacity - 1; _count = 0;
_removed = 0;
_firstOccupiedSlot = _capacity;
_lastOccupiedSlot = 0;
_maxRunLength = 0;
_pointers = NULL;
if (newCapacity > 0) {
_pointers = (vm_address_t *)aux_calloc(_capacity, sizeof(void *));
if (old_count > 0) {
uint32_t rehashed = 0;
while (i<old_capacity && rehashed < old_count) {
if (validPointer(old_pointers[i])) {
insert(pointerValue(old_pointers[i]), flagsValue(old_pointers[i]) & mask);
rehashed++;
}
i++;
}
}
}
if (old_pointers)
aux_free(old_pointers);
}
}
void PointerHash::rehash(uint32_t flagMask)
{
vm_address_t mask = ~(FlagsMask & flagMask);
if (_maxRunLength > 0 || flagMask) {
if (_count > 0) {
uint32_t start = _capacity;
for (uint32_t i = 0; i < _capacity; i++) {
if (_pointers[i] == 0) {
start = i;
break;
}
}
if (start == _capacity) {
grow(_capacity * 2, flagMask);
return;
}
_count = 0;
_removed = 0;
_firstOccupiedSlot = _capacity;
_lastOccupiedSlot = 0;
_maxRunLength = 0;
for (uint32_t i = start; i < _capacity; i++) {
vm_address_t pointer = _pointers[i];
_pointers[i] = 0;
if (validPointer(pointer))
insert(pointerValue(pointer), flagsValue(pointer) & mask);
}
for (uint32_t i = 0; i < start; i++) {
vm_address_t pointer = _pointers[i];
_pointers[i] = 0;
if (validPointer(pointer))
insert(pointerValue(pointer), flagsValue(pointer) & mask);
}
} else {
bzero(_pointers, _capacity * sizeof(void *));
}
}
}
void PointerHash::compact(uint32_t flagMask) {
if (_capacity > PreferredCapacity && (_count * 3) < PreferredCapacity)
grow(PreferredCapacity, flagMask);
else
rehash(flagMask);
}
void PointerHash::clearFlags() {
for (uint32_t i = _firstOccupiedSlot; i <= _lastOccupiedSlot; ++i) {
_pointers[i] &= ~FlagsMask;
}
}
}