77 lines
1.6 KiB
Plaintext
77 lines
1.6 KiB
Plaintext
/*
|
|
* SIOaLpDhFt: Statically-allocated, Interleaved KV values, Open-addressing, Linear probing, Dynamic hash, Flag tombstones
|
|
*/
|
|
|
|
record KVPair[K, V] {
|
|
K key;
|
|
V value;
|
|
}
|
|
|
|
record MapSIOaLpDhFt[K, V, S; capacity] {
|
|
S(K*)* hash;
|
|
KVPair[capacity] data;
|
|
u8[capacity] occupied;
|
|
}
|
|
|
|
MapSIOaLpDhFt_add: [K, V, S; capacity]u1(MapSIOaLpDhFt[K, V, S; capacity]* this, K* key, V* value) -> {
|
|
S start = this.hash(key);
|
|
start = start & (capacity - 1);
|
|
|
|
S index = start;
|
|
loop {
|
|
KVPair[K, V]* pair = &this.data[index];
|
|
if(pair.key == *key || this.occupied[index] == 0) {
|
|
pair.key = *key;
|
|
pair.value = *value;
|
|
this.occupied[index] = 1;
|
|
return 1;
|
|
}
|
|
index = (index + 1) & (capacity - 1);
|
|
if(index == start) {
|
|
return 0;
|
|
}
|
|
}
|
|
};
|
|
|
|
MapSIOaLpDhFt_get: [K, V, S; capacity]V*(MapSIOaLpDhFt[K, V, S; capacity]* this, K* key) -> {
|
|
S start = this.hash(key);
|
|
start = start & (capacity - 1);
|
|
|
|
S index = start;
|
|
loop {
|
|
KVPair[K, V]* pair = &this.data[index];
|
|
if(pair.key == *key) {
|
|
if(this.occupied[index] == 0) {
|
|
return 0;
|
|
}
|
|
return &pair.value;
|
|
}
|
|
index = (index + 1) & (capacity - 1);
|
|
if(index == start) {
|
|
return 0;
|
|
}
|
|
}
|
|
};
|
|
|
|
zero_hash: ugpr(ugpr* val) -> {
|
|
return 0;
|
|
};
|
|
|
|
@instantiate MapSIOaLpDhFt_add[ugpr, ugpr, ugpr; 32];
|
|
@instantiate MapSIOaLpDhFt_get[ugpr, ugpr, ugpr; 32];
|
|
|
|
main: u0() -> {
|
|
map.hash = &zero_hash;
|
|
|
|
MapSIOaLpDhFt_get[ugpr, ugpr, ugpr; 32](&map, &test_key);
|
|
MapSIOaLpDhFt_add[ugpr, ugpr, ugpr; 32](&map, &test_key, &test_value);
|
|
MapSIOaLpDhFt_get[ugpr, ugpr, ugpr; 32](&map, &test_key);
|
|
};
|
|
|
|
loop {}
|
|
|
|
@section(".data");
|
|
MapSIOaLpDhFt[ugpr, ugpr, ugpr; 32] map:;
|
|
|
|
ugpr test_value: 10;
|
|
ugpr test_key: 5; |