G Programming Language
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 

98 lines
2.7 KiB

// map.g
// Theoretical hashmap implementation in the G programming language
// Copyright (C) 2021, Jakob Wakeling
// All rights reserved.
/*
This example is *very* unrefined and exists solely as a syntax experiment.
I am certain that this would be completely nonfunctional, as I have
dedicated to it only a few minutes.
*/
//package "map"
//module "map"
define LOAD_FACTOR 0.75;
/*
Hashmap struct where K is the key type, V is the value type, a is the array
of key-value pairs, al is the number of items in the array, and ac is the
array capacity.
The hashmap will resize itself when a load factor of 0.75 is reached. It
*will* also shadow values when a duplicate key is used. Entries *will* be
inserted using a robin hood hashing technique.
*/
map :: struct($K: type, $V: type) {
a :: struct { h: u64; k: K; v: V; }[];
al, ac: uint; cb: &proc(V);
}
/*
Initialise a map where K is the key type and V is the value type. The map is
initialised with a default capacity of 0 key-value pairs, and so a memory
allocation error is not possible.
*/
/*map.*/init :: proc($K: type, $V: type, cb: &proc(V) = null) -> map(K, V) {
return map(K, V){ [], 0, 0, cb };
}
/*
Deinitialise a map where m is a pointer to the map and M is the map
specialisation type (e.g. a map of string keys and values).
*/
/*map.*/free :: proc(m: &$M/map) {
free(m.a); m.a = null; m.al = 0; m.ac = 0;
}
/*
Insert a key-value pair into a map where m is a pointer to the map, k is the
key, and v is the value. The key-value types must match those of the map.
*/
/*map.*/insert :: proc(m: &map($K, $V), k: K, v: V) -> ErrorOr() {
if (m.ac == 0 || m.al >= (m.ac * LOAD_FACTOR)) { /* Resize the map. */ }
h := hash(k); index: uint = h % m.ac;
/* Find the next available empty bucket */
for (; m.a[index] /*is unset*/; index += 1) { if (index >= m.ac) { index = 0; } }
m.a[index] = { h, k, v };
return ErrorOr(); /* ??? */
}
/*
*/
/*map.*/lookup :: proc(m: &map($K, $V), k: K) -> ErrorOr(V) {
index: uint = hash(k) % m.ac;
for (start: uint = index; m.a[index].k != k; index += 1) {
if (index >= m.ac) { index = 0; }
/* This doesnt account for the start being at the array start */
if (index + 1 == start) { return Error(); /* ??? */ }
}
return ErrorOr(m.a[index].v); /* ??? */
}
/*
*/
/*map.*/remove :: proc(m: &map($K, $V), k: K) -> ErrorOr() {
index: uint = hash(k) % m.ac;
for (start: uint = index; m.a[index].k != k; index += 1) {
if (index >= m.ac) { index = 0; }
/* This doesnt account for the start being at the array start */
if (index + 1 == start) { return Error(); /* ??? */ }
}
return ErrorOr(); /* ??? */
}
/*
Override hash procedure for different variable types.
*/
/*map.*/hash :: proc -> u64 { hash_int, hash_flt, hash_str };