Skip to content

Instantly share code, notes, and snippets.

Ayende Rahien ayende

Block or report user

Report or block ayende

Hide content and notifications from this user.

Learn more about blocking users

Contact Support about this user’s behavior.

Learn more about reporting abuse

Report abuse
View GitHub Profile
View 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;
}
View 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;
}
View 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);
View 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);
}
}
View 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;
View 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];
View 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;
View 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);
}
View 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;
View 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);
}
You can’t perform that action at this time.