Ayende Rahien ayende

## free2.c
int compare_ptrs(const void* a, const void* b) {
	hash_bucket_t* x = *(hash_bucket_t**)a;
	hash_bucket_t* y = *(hash_bucket_t**)b;

	ptrdiff_t diff = x - y;
	if (diff)
		return diff > 0 ? 1 : -1;
	return 0;
}

## free1.c
void hash_table_free(hash_ctx_t* ctx) {
	for (size_t i = 0; i < ctx->dir->number_of_buckets; i++)
	{
		ctx->release_page(ctx->dir->buckets[i]);
	}
	ctx->release_page(ctx->dir);
	ctx->dir = NULL;
}

## compact.c
static void _hash_table_compact_pages(hash_ctx_t* ctx, uint64_t key, uint32_t bucket_idx) {
	if (ctx->dir->number_of_buckets <= 2)
		return; // can't compact if we have just 2 pages
	hash_bucket_t* left = ctx->dir->buckets[bucket_idx];
	uint32_t sibling_idx = bucket_idx ^ ((uint64_t)1 << (left->depth - 1));
	hash_bucket_t* right = ctx->dir->buckets[sibling_idx];
	if (_get_bucket_size(right) + _get_bucket_size(left) > HASH_BUCKET_PAGE_SIZE_MERGE_LIMIT)
		return; // too big for compaction, we'll try again later

	hash_bucket_t* merged = _create_hash_bucket(ctx);

## policy.c
if (p->bytes_used == 0) {
	if (!_hash_table_overflow_merge(ctx, b, cur_piece_idx)) {
		_hash_table_compact_pages(ctx, key, bucket_idx);
	}
}

## merge.c
void hash_table_overflow_merge(hash_ctx_t* ctx, hash_bucket_t* b, uint32_t piece_idx) {
	size_t max_overflow = 0;
	for (size_t j = 0; j < NUMBER_OF_HASH_BUCKET_PIECES; j++) {
		if (!b->pieces[(piece_idx + j) % NUMBER_OF_HASH_BUCKET_PIECES].overflowed) {
			break;
		}
		max_overflow++;
	}

	bool has_overflow = false;

## shift.overflow.c
if (p->bytes_used == 0) {
	size_t max_overflow = 0;
	for (size_t j = 0; j < MAX_CHAIN_LENGTH; j++) {
		if (b->pieces[(piece_idx + i + j) % NUMBER_OF_HASH_BUCKET_PIECES].overflowed)
			max_overflow++;
	}
	// we scan keys as far as possible first, to move them closer to their ideal location
	for (size_t j = max_overflow - 1; j >= 0; j--)
	{
		hash_bucket_piece_t* cur = &b->pieces[(piece_idx + i + j) % NUMBER_OF_HASH_BUCKET_PIECES];

## del1.c
bool hash_table_delete(hash_ctx_t* ctx, uint64_t key, hash_old_value_t* old_value) {
	uint32_t bucket_idx = hash_table_bucket_number(ctx, key);
	hash_bucket_t* b = ctx->dir->buckets[bucket_idx];
	uint32_t piece_idx = key % NUMBER_OF_HASH_BUCKET_PIECES;

	ctx->dir->version++;

	if (old_value)
		old_value->exists = false;

## it.and.modify.c
uint64_t k, v;
hash_iteration_state_t state;
hash_table_iterate_init(&ctx, &state);
while (hash_table_iterate_next(&state, &k, &v)) {
	hash_table_put(&ctx, k, v + 1);
	printf("%llu = %llu\n", k, v);
}

## hash_table_iterate.c
void hash_table_iterate_init(hash_ctx_t* ctx, hash_iteration_state_t* state) {
	memset(state, 0, sizeof(hash_iteration_state_t));
	state->dir = ctx->dir;
}

bool hash_table_iterate_next(hash_iteration_state_t* state, uint64_t* key, uint64_t* value) {
	while (true) {

		if (state->current_bucket_idx >= state->dir->number_of_buckets)
			return false;

## iterating.c
uint64_t k, v;
hash_iteration_state_t state;
hash_table_iterate_init(&ctx, &state);
while (hash_table_iterate_next(&state, &k, &v)) {
	printf("%llu = %llu\n", k, v);
}