#include "AutoDefs.h"
#include "AutoHashTable.h"
#include "AutoRange.h"
namespace Auto {
bool HashTable::rehash(Range **ranges, usword_t length) {
Range **cursor = ranges;
Range **near_end = cursor + (length & ~3);
Range **end = cursor + length;
while (cursor < near_end) {
Range *range0 = cursor[0];
Range *range1 = cursor[1];
Range *range2 = cursor[2];
Range *range3 = cursor[3];
cursor += 4;
if (range0 && !insert(range0)) return false;
if (range1 && !insert(range1)) return false;
if (range2 && !insert(range2)) return false;
if (range3 && !insert(range3)) return false;
}
while (cursor < end) {
Range *range = *cursor++;
if (range && !insert(range)) return false;
}
return true;
}
void HashTable::grow() {
Range **old_ranges = _ranges;
usword_t old_length = 1 << _length_log2;
_length_log2 = old_ranges ? _length_log2 + 1 : initial_size_log2;
_ranges = (Range **)aux_calloc(1 << _length_log2, sizeof(Range **));
if (old_ranges) {
while (!rehash(old_ranges, old_length)) {
aux_free(_ranges);
_length_log2++;
_ranges = (Range **)aux_calloc(1 << _length_log2, sizeof(Range **));
}
aux_free(old_ranges);
}
}
Range **HashTable::find_slot(void *address) {
if (!_ranges) return NULL;
const usword_t h = hash(address);
Range **slot = _ranges + h;
for (unsigned depth = 0; depth < maximum_depth; depth++, slot = next(slot)) {
Range *old_member = *slot;
if (!old_member || old_member->address() == address) return slot;
if (h != hash(old_member->address())) return NULL;
}
return NULL;
}
void HashTable::initialize() {
_length_log2 = 0;
_ranges = NULL;
}
void HashTable::dispose() {
if (_ranges) aux_free(_ranges);
_length_log2 = 0;
_ranges = NULL;
}
bool HashTable::insert(Range *range) {
Range **slot = find_slot(range->address());
if (slot) {
*slot = range;
}
return slot != NULL;
}
void HashTable::add(Range *range) {
if (!range || !range->address()) return;
while (!insert(range)) grow();
}
void HashTable::remove(Range *range) {
void *address = range->address();
Range **slot = find_slot(address);
if (slot && (*slot)->address() == address) {
const usword_t h = hash(address);
for (Range **next_slot = next(slot); true; next_slot = next(next_slot)) {
Range *old_member = *next_slot;
if (!old_member || h != hash(old_member->address())) {
*slot = NULL;
break;
}
*slot = *next_slot;
slot = next_slot;
}
}
}
};