Last active
June 21, 2023 16:20
-
-
Save ibuclaw/2f777916bb63c5df5b5858cdc1333cbe to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
module container.linkedaa; | |
pragma(inline, true): | |
struct LinkedAssociativeArray(Key, Value) | |
{ | |
// Initialize a LinkedAssociativeArray with an AssociativeArray. | |
// For supporting `aa = [key1:value1, key2:value2, ...]` syntax. | |
this(AssociativeArray!(Key, Value) aa) pure nothrow | |
{ | |
dangerouslyReconstructAA(this, aa); | |
} | |
// ditto | |
auto opAssign(AssociativeArray!(Key, Value) aa) pure nothrow | |
{ | |
dangerouslyReconstructAA(this, aa); | |
} | |
// Lookup `key` in the associative array and return its value. | |
// For supporting `aa[key]` syntax. | |
ref opIndex(Key key) pure nothrow | |
{ | |
return this.impl[key].value; | |
} | |
// Lookup `key` in the associative array and assign it a new `value`. | |
// For supporting `aa[key] = value` syntax. | |
auto opIndexAssign(Value value, const Key key) pure nothrow | |
{ | |
this.impl[key] = this.addEntry(key, value); | |
return value; | |
} | |
// Return a pointer to the value corresponding to the given key. | |
// For supporting `key in aa` syntax. | |
inout(Value)* opBinaryRight(string op : "in")(Key key) inout pure nothrow @nogc | |
{ | |
if (auto p = key in this.impl) | |
return &(*p).value; | |
return null; | |
} | |
// Foreach over all values. | |
// For supporting `foreach (value; aa) { ... }` syntax. | |
int opApply(scope int delegate(ref Value) dg) | |
{ | |
for (auto e = this.root; e !is null; e = e.next) | |
{ | |
if (auto result = dg(e.value)) | |
return result; | |
} | |
return 0; | |
} | |
// Foreach over all key-value pairs. | |
// For supporting `foreach (key, value; aa) { ... }` syntax. | |
int opApply(scope int delegate(const ref Key, ref Value) dg) | |
{ | |
for (auto e = this.root; e !is null; e = e.next) | |
{ | |
if (auto result = dg(e.key, e.value)) | |
return result; | |
} | |
return 0; | |
} | |
// Reverse foreach over all values. | |
// Note: This is impossible with native associative arrays, neat! | |
// For supporting `foreach_reverse (value; aa) { ... }` syntax. | |
int opApplyReverse(scope int delegate(ref Value) dg) | |
{ | |
if (this.root is null) | |
return 0; | |
for (auto e = this.root.prev; e !is this.root; e = e.prev) | |
{ | |
if (auto result = dg(e.value)) | |
return result; | |
} | |
return dg(this.root.value); | |
} | |
// Reverse foreach over all key-value pairs. | |
// Note: This is impossible with native associative arrays, neat! | |
// For supporting `foreach_reverse (key, value; aa) { ... }` syntax. | |
int opApplyReverse(scope int delegate(const ref Key, ref Value) dg) | |
{ | |
if (this.root is null) | |
return 0; | |
for (auto e = this.root.prev; e !is this.root; e = e.prev) | |
{ | |
if (auto result = dg(e.key, e.value)) | |
return result; | |
} | |
return dg(this.root.key, this.root.value); | |
} | |
// Returns the number of entries n the associative array. | |
// For supporting `aa.length` syntax. | |
size_t length()() pure nothrow @nogc @safe | |
{ | |
return this.impl.length; | |
} | |
// Removes `key` from the associative array and returns `true`. | |
// If the key does not exist, this does nothing and return `false`. | |
// For supporting `aa.remove(key)` syntax. | |
bool remove()(Key key) pure nothrow @nogc @safe | |
{ | |
return this.removeEntry(key); | |
} | |
// Internally, `Value[Key]` is stored in a `Value[LinkedEntry(Key, Value)*]` | |
// associative array, so that we can continue to benefit from O(log N) | |
// complexity of a native associative array. | |
private AssociativeArray!(Key, LinkedEntry!(Key, Value)*) impl; | |
// The oldest entry to begin iteration at. | |
private LinkedEntry!(Key, Value)* root; | |
} | |
@safe unittest | |
{ | |
LinkedAssociativeArray!(string, int) aa = ["c": 3, "a": 1, "b": 2]; | |
assert(aa.impl !is null); | |
assert(aa.root !is null); | |
assert(aa.root.next !is null); | |
assert(aa.root.prev !is null); | |
assert(aa.root.prev.next is null); | |
assert(aa.root.prev.prev is aa.root.next); | |
// ??? It passes, but is this reliable? | |
//assert(aa.keys == ["c", "a", "b"]); | |
//assert(aa.values == [3, 1, 2]); | |
aa = ["e": 5, "d": 4]; | |
assert(aa.impl !is null); | |
assert(aa.root !is null); | |
assert(aa.root.next !is null); | |
assert(aa.root.prev !is null); | |
assert(aa.root.prev.next is null); | |
assert(aa.root.prev.prev is aa.root); | |
// ??? It passes, but is this reliable? | |
//assert(aa.keys == ["e", "d"]); | |
//assert(aa.values == [5, 4]); | |
} | |
@safe unittest | |
{ | |
LinkedAssociativeArray!(string, int) aa = [ | |
"1":2, "3":4, "5":6, "7":8, "9":10, | |
"11":12, "13":14, "15":16, "17":18, | |
"19":20, "21":22, "23":24, "25":26, | |
]; | |
assert(aa.length == 13); | |
// ??? It passes, but is this reliable? | |
//assert(aa.keys == ["1","3","5","7","9","11","13","15","17","19","21","23","25"]); | |
//assert(aa.values == [2,4,6,8,10,12,14,16,18,20,22,24,26]); | |
int[string] bb = [ | |
"1":2, "3":4, "5":6, "7":8, "9":10, | |
"19":20, "21":22, "23":24, "25":26, | |
"11":12, "13":14, "15":16, "17":18, | |
]; | |
assert(bb["23"] == 24); | |
aa = bb; | |
assert(bb["23"] == 24); | |
assert(aa.length == 13); | |
// ??? It passes, but is this reliable? | |
//assert(aa.keys == ["1","3","5","7","9","19","21","23","25","11","13","15","17"]); | |
//assert(aa.values == [2,4,6,8,10,20,22,24,26,12,14,16,18]); | |
} | |
@safe unittest | |
{ | |
LinkedAssociativeArray!(string, int) aa; | |
aa["one"] = 1; | |
assert(aa["one"] == 1); | |
auto value = aa["two"] = 2; | |
assert(value == 2); | |
assert(aa.keys == ["one", "two"]); | |
assert(aa.values == [1, 2]); | |
} | |
@safe unittest | |
{ | |
LinkedAssociativeArray!(string, int) aa; | |
assert("one" !in aa); | |
aa["one"] = 1; | |
assert("one" in aa); | |
assert("two" !in aa); | |
} | |
@safe unittest | |
{ | |
LinkedAssociativeArray!(uint, uint) aa; | |
foreach (uint i; 0 .. 20) | |
aa[i] = i; | |
uint index = 0; | |
for (auto e = aa.root; e !is null; e = e.next, index++) | |
{ | |
assert(e.key == index); | |
assert(e.value == index); | |
} | |
} | |
@system unittest | |
{ | |
LinkedAssociativeArray!(uint, uint) aa; | |
foreach (uint i; 0 .. 20) | |
aa[i] = i; | |
uint index = 0; | |
foreach (v; aa) | |
{ | |
assert(v == index++); | |
} | |
index = 0; | |
foreach (k, v; aa) | |
{ | |
assert(k == v); | |
assert(v == index++); | |
} | |
} | |
@system unittest | |
{ | |
LinkedAssociativeArray!(uint, uint) aa; | |
foreach (uint i; 0 .. 20) | |
aa[i] = i; | |
uint index = 20; | |
foreach_reverse (v; aa) | |
{ | |
assert(v == --index); | |
} | |
index = 20; | |
foreach_reverse (k, v; aa) | |
{ | |
assert(k == v); | |
assert(v == --index); | |
} | |
} | |
@safe unittest | |
{ | |
LinkedAssociativeArray!(uint, uint) aa; | |
assert(aa.length == 0); | |
foreach (uint i; 1 .. 21) | |
{ | |
aa[i] = i; | |
assert(aa.length == i); | |
} | |
} | |
@safe unittest | |
{ | |
LinkedAssociativeArray!(uint, uint) aa; | |
foreach (uint i; 0 .. 10) | |
aa[i] = i; | |
assert(aa.length == 10); | |
assert(aa.root.key == 0); | |
assert(aa.root.prev.key == 9); | |
assert(aa.remove(10) == false); | |
assert(aa.length == 10); | |
assert(aa.root.key == 0); | |
assert(aa.root.prev.key == 9); | |
assert(aa.remove(9) == true); | |
assert(aa.length == 9); | |
assert(aa.root.key == 0); | |
assert(aa.root.prev.key == 8); | |
assert(aa.remove(3) == true); | |
assert(aa.length == 8); | |
assert(aa.root.key == 0); | |
assert(aa.root.prev.key == 8); | |
assert(aa.remove(0) == true); | |
assert(aa.length == 7); | |
assert(aa.root.key == 1); | |
assert(aa.root.prev.key == 8); | |
assert(aa.keys == [1,2,4,5,6,7,8]); | |
assert(aa.values == [1,2,4,5,6,7,8]); | |
} | |
/////////////////////////////////////////////////////////////////////////////// | |
// LinkedAssociativeArray standard runtime functions. | |
/////////////////////////////////////////////////////////////////////////////// | |
// Returns `true` if there are no entries in this associative array. | |
// See also `bool std.range.primitives.empty`. | |
@property bool empty(T : LinkedAssociativeArray!(K, V), K, V)(T aa) | |
{ | |
return aa.root is null; | |
} | |
@safe unittest | |
{ | |
LinkedAssociativeArray!(string, uint) aa; | |
assert(aa.empty); | |
aa["zero"] = 0; | |
assert(!aa.empty); | |
} | |
// Construct a range iterating over an associative array by key-value tuples. | |
// See also `auto std.array.byPair`. | |
auto byPair(T : LinkedAssociativeArray!(K, V), K, V)(T aa) | |
{ | |
import std.algorithm.iteration : map; | |
import std.typecons : tuple; | |
return aa.byKeyValue | |
.map!(pair => tuple!("key", "value")(pair.key, pair.value)); | |
} | |
@safe pure nothrow unittest | |
{ | |
import std.algorithm.sorting : sort; | |
import std.typecons : tuple, Tuple; | |
LinkedAssociativeArray!(string, int) aa = ["a": 1, "b": 2, "c": 3]; | |
Tuple!(string, int)[] pairs; | |
// Iteration over key/value pairs. | |
foreach (pair; aa.byPair) | |
{ | |
if (pair.key == "b") | |
pairs ~= tuple("B", pair.value); | |
else | |
pairs ~= pair; | |
} | |
assert(pairs == [ | |
tuple("a", 1), | |
tuple("B", 2), | |
tuple("c", 3) | |
]); | |
} | |
/////////////////////////////////////////////////////////////////////////////// | |
// LinkedAssociativeArray core runtime functions. | |
/////////////////////////////////////////////////////////////////////////////// | |
// Returns a forward range which will iterate over the keys. | |
// See also `auto object.byKey`. | |
auto byKey(T : LinkedAssociativeArray!(K, V), K, V)(T aa) pure nothrow @nogc @safe | |
{ | |
return aa.byKeyValueImpl!(Iterate.byKey)(); | |
} | |
// ditto | |
auto byKey(T : LinkedAssociativeArray!(K, V), K, V)(T* aa) pure nothrow @nogc | |
{ | |
return (*aa).byKey(); | |
} | |
@safe unittest | |
{ | |
LinkedAssociativeArray!(int, string) aa = [1: "v1", 2: "v2"]; | |
int sum; | |
foreach (v; aa.byKey) | |
sum += v; | |
assert(sum == 3); | |
} | |
// Returns a forward range which will iterate over the key-value pairs | |
// See also `auto object.byKeyValue`. | |
auto byKeyValue(T : LinkedAssociativeArray!(K, V), K, V)(T aa) pure nothrow @nogc @safe | |
{ | |
return aa.byKeyValueImpl!(Iterate.byKeyValue)(); | |
} | |
// ditto | |
auto byKeyValue(T : LinkedAssociativeArray!(K, V), K, V)(T* aa) pure nothrow @nogc | |
{ | |
return (*aa).byKeyValue(); | |
} | |
@safe unittest | |
{ | |
LinkedAssociativeArray!(string, int) aa = ["k1": 1, "k2": 2]; | |
int sum; | |
foreach (e; aa.byKeyValue) | |
{ | |
assert(e.key[1] == e.value + '0'); | |
sum += e.value; | |
} | |
assert(sum == 3); | |
} | |
// Returns a forward range which will iterate over the values | |
// See also `auto object.byValue`. | |
auto byValue(T : LinkedAssociativeArray!(K, V), K, V)(T aa) pure nothrow @nogc @safe | |
{ | |
return aa.byKeyValueImpl!(Iterate.byValue)(); | |
} | |
// ditto | |
auto byValue(T : LinkedAssociativeArray!(K, V), K, V)(T* aa) pure nothrow @nogc | |
{ | |
return (*aa).byValue(); | |
} | |
@safe unittest | |
{ | |
LinkedAssociativeArray!(string, int) aa = ["k1": 1, "k2": 2]; | |
int sum; | |
foreach (v; aa.byValue) | |
sum += v; | |
assert(sum == 3); | |
} | |
// Removes all remaining keys and values from the associative array. | |
// See also `void object.clear`. | |
void clear(T : LinkedAssociativeArray!(K, V), K, V)(T aa) | |
{ | |
// O(1) complexity. | |
object.clear(aa.impl); | |
aa.root = null; | |
} | |
// ditto | |
void clear(T : LinkedAssociativeArray!(K, V), K, V)(T* aa) | |
{ | |
(*aa).clear(); | |
} | |
@system unittest | |
{ | |
LinkedAssociativeArray!(string, int) aa = ["k1": 2]; | |
assert("k1" in aa); | |
aa.clear; | |
assert("k1" !in aa); | |
} | |
// Creates a newly allocated associative array containing a copy of the originals contents. | |
// See also `V[K] object.dup`. | |
T dup(T : LinkedAssociativeArray!(K, V), K, V)(T aa) | |
{ | |
// This seems more reasonable than forwarding .dup, as we don't want | |
// the internal LinkedEntry to have more than one reference. | |
T copy; | |
// O(n) complexity, but then so is `object.dup`. | |
for (auto e = aa.root; e !is null; e = e.next) | |
{ | |
// TODO: ??? handle calling __xpostblit on copied value? | |
copy.impl[e.key] = copy.addEntry(e.key, e.value); | |
} | |
return copy; | |
} | |
// ditto | |
T dup(T : LinkedAssociativeArray!(K, V), K, V)(T* aa) | |
{ | |
return (*aa).dup; | |
} | |
@safe unittest | |
{ | |
LinkedAssociativeArray!(string, int) aa = ["k1": 2]; | |
auto a2 = aa.dup; | |
aa["k2"] = 3; | |
assert("k2" !in a2); | |
} | |
// Looks up `key`; if it exists returns corresponding value else evaluates and | |
// returns `defaultValue`. See also `inout(V) object.get`. | |
inout(V) get(K, V)(LinkedAssociativeArray!(K, V) aa, K key, lazy inout(V) defaultValue) | |
{ | |
auto p = key in aa; | |
return p ? *p : defaultValue; | |
} | |
// ditto | |
inout(V) get(K, V)(LinkedAssociativeArray!(K, V)* aa, K key, lazy inout(V) defaultValue) | |
{ | |
return (*aa).get(key, defaultValue); | |
} | |
@safe unittest | |
{ | |
LinkedAssociativeArray!(string, int) aa = ["k1": 1]; | |
assert(aa.get("k1", 0) == 1); | |
assert(aa.get("k2", 0) == 0); | |
} | |
// Returns a newly allocated dynamic array containing a copy of all keys. | |
// See also `Key[] object.keys`. | |
@property K[] keys(T : LinkedAssociativeArray!(K, V), K, V)(T aa) | |
{ | |
// Note: Not using `impl.keys()` to retain insertion order. | |
K[] res; | |
res.length = aa.impl.length; | |
size_t idx = 0; | |
// O(n) complexity, but then so is `object.keys`. | |
// TODO: ??? handle calling __xpostblit on copied keys? | |
for (auto e = aa.root; e !is null; e = e.next) | |
res[idx++] = e.key; | |
return res; | |
} | |
// ditto | |
@property K[] keys(T : LinkedAssociativeArray!(K, V), K, V)(T* aa) | |
{ | |
return (*aa).keys; | |
} | |
@safe unittest | |
{ | |
LinkedAssociativeArray!(int, string) aa = [1: "v1", 2: "v2"]; | |
int sum; | |
foreach (k; aa.keys) | |
sum += k; | |
assert(sum == 3); | |
} | |
@safe unittest | |
{ | |
static struct S | |
{ | |
string str; | |
LinkedAssociativeArray!(string, void[]) dict; | |
alias dict this; | |
} | |
auto s = S("a"); | |
assert(s.keys.length == 0); | |
} | |
@safe unittest | |
{ | |
@safe static struct Key | |
{ | |
string str; | |
this(this) @safe {} | |
} | |
LinkedAssociativeArray!(Key, string) aa; | |
static assert(__traits(compiles, { | |
void test() @safe { | |
const _ = aa.keys; | |
} | |
})); | |
} | |
@safe unittest | |
{ | |
static struct Key | |
{ | |
string str; | |
this(this) @system {} | |
} | |
LinkedAssociativeArray!(Key, string) aa; | |
static assert(!__traits(compiles, { | |
void test() @safe { | |
const _ = aa.keys; | |
} | |
})); | |
} | |
// Reorganizes the associative array in place so that lookups are more efficient. | |
// See also `T object.rehash`. | |
T rehash(T : LinkedAssociativeArray!(K, V), K, V)(T aa) | |
{ | |
object.rehash(aa.impl); | |
return aa; | |
} | |
// ditto | |
T rehash(T : LinkedAssociativeArray!(K, V), K, V)(T* aa) | |
{ | |
object.rehash(aa.impl); | |
return *aa; | |
} | |
// Looks up `key`; if it exists returns corresponding value else evaluates | |
// `value`, adds it to the associative array, and returns it. | |
// See also `V object.require`. | |
ref V require(K, V)(ref LinkedAssociativeArray!(K, V) aa, K key, lazy V value = V.init) | |
{ | |
return object.require(aa.impl, key, aa.addEntry(key, value)).value; | |
} | |
@safe unittest | |
{ | |
LinkedAssociativeArray!(string, int) aa = ["k1": 1]; | |
assert(aa.require("k1", 0) == 1); | |
assert(aa.require("k2", 0) == 0); | |
assert(aa["k2"] == 0); | |
} | |
// Looks up `key`; calls `create` if `key` doesn't exist in the associative | |
// array, otherwise `update`. See also `object.update`. | |
void update(K, V, C, U)(ref LinkedAssociativeArray!(K, V) aa, K key, scope C create, scope U update) | |
if (is(typeof(create()) : V) && | |
(is(typeof(update(aa[key])) : V) || is(typeof(update(aa[key])) == void))) | |
{ | |
return object.update(aa.impl, key, | |
() { | |
return aa.addEntry(key, create()); | |
}, | |
(ref LinkedEntry!(K, V)* v) { | |
static if (is(typeof(update(v.value)) == void)) | |
update(v.value); | |
else | |
v.value = update(v.value); | |
}); | |
} | |
@safe unittest | |
{ | |
LinkedAssociativeArray!(string, int) aa; | |
// create | |
aa.update("key", | |
() => 1, | |
(int) {} // not executed | |
); | |
assert(aa["key"] == 1); | |
// update value by ref | |
aa.update("key", | |
() => 0, // not executed | |
(ref int v) { | |
v += 1; | |
}); | |
assert(aa["key"] == 2); | |
// update from return value | |
aa.update("key", | |
() => 0, // not executed | |
(int v) => v * 2 | |
); | |
assert(aa["key"] == 4); | |
// 'update' without changing value | |
aa.update("key", | |
() => 0, // not executed | |
(int) { | |
// do something else | |
}); | |
assert(aa["key"] == 4); | |
} | |
@safe unittest | |
{ | |
static struct S | |
{ | |
int x; | |
@nogc nothrow pure: | |
this(this) @system {} | |
@safe const: | |
// stubs | |
bool opEquals(S rhs) { assert(0); } | |
size_t toHash() { assert(0); } | |
} | |
LinkedAssociativeArray!(string, int) aai; | |
static assert(is(typeof(() @safe { aai.require("a", 1234); }))); | |
static assert(is(typeof(() @safe { aai.update("a", { return 1234; }, (ref int x) { x++; return x; }); }))); | |
LinkedAssociativeArray!(string, S) aas; | |
static assert(is(typeof(() { aas.require("a", S(1234)); }))); | |
static assert(is(typeof(() { aas.update("a", { return S(1234); }, (ref S s) { s.x++; return s; }); }))); | |
static assert(!is(typeof(() @safe { aas.update("a", { return S(1234); }, (ref S s) { s.x++; return s; }); }))); | |
LinkedAssociativeArray!(S, int) aais; | |
static assert(is(typeof(() { aais.require(S(1234), 1234); }))); | |
static assert(is(typeof(() { aais.update(S(1234), { return 1234; }, (ref int x) { x++; return x; }); }))); | |
static assert(!is(typeof(() @safe { aais.require(S(1234), 1234); }))); | |
static assert(!is(typeof(() @safe { aais.update(S(1234), { return 1234; }, (ref int x) { x++; return x; }); }))); | |
} | |
@safe unittest | |
{ | |
struct S0 | |
{ | |
int opCall(ref int v) | |
{ | |
return v + 1; | |
} | |
} | |
struct S1 | |
{ | |
int opCall()() | |
{ | |
return -2; | |
} | |
T opCall(T)(ref T v) | |
{ | |
return v + 1; | |
} | |
} | |
LinkedAssociativeArray!(string, int) a = ["2" : 1]; | |
a.update("2", () => -1, S0.init); | |
assert(a["2"] == 2); | |
a.update("0", () => -1, S0.init); | |
assert(a["0"] == -1); | |
a.update("2", S1.init, S1.init); | |
assert(a["2"] == 3); | |
a.update("1", S1.init, S1.init); | |
assert(a["1"] == -2); | |
} | |
@system unittest | |
{ | |
LinkedAssociativeArray!(string, int) aa; | |
foreach (n; 0 .. 2) | |
aa.update("k1", { | |
return 7; | |
}, (ref int v) { | |
return v + 3; | |
}); | |
assert(aa["k1"] == 10); | |
} | |
// Returns a newly allocated dynamic array containing a copy of all values. | |
// See also `object.values`. | |
@property V[] values(T : LinkedAssociativeArray!(K, V), K, V)(T aa) | |
{ | |
// Note: Not using `impl.values()` because it would return an array of LinkedEntry*. | |
V[] res; | |
res.length = aa.impl.length; | |
size_t idx = 0; | |
// O(n) complexity, but then so is `object.values`. | |
// TODO: ??? handle calling __xpostblit on copied values? | |
for (auto e = aa.root; e !is null; e = e.next) | |
res[idx++] = e.value; | |
return res; | |
} | |
// ditto | |
@property V[] values(T : LinkedAssociativeArray!(K, V), K, V)(T* aa) | |
{ | |
return (*aa).values; | |
} | |
@safe unittest | |
{ | |
LinkedAssociativeArray!(string, int) aa = ["k1": 1, "k2": 2]; | |
int sum; | |
foreach (e; aa.values) | |
sum += e; | |
assert(sum == 3); | |
} | |
@safe unittest | |
{ | |
static struct S | |
{ | |
string str; | |
LinkedAssociativeArray!(string, void[]) dict; | |
alias dict this; | |
} | |
auto s = S("a"); | |
assert(s.values.length == 0); | |
} | |
@safe unittest | |
{ | |
@safe static struct Value | |
{ | |
string str; | |
this(this) @safe {} | |
} | |
LinkedAssociativeArray!(string, Value) aa; | |
static assert(__traits(compiles, { | |
void test() @safe { | |
const _ = aa.values; | |
} | |
})); | |
} | |
@safe unittest | |
{ | |
static struct Value | |
{ | |
string str; | |
this(this) @system {} | |
} | |
LinkedAssociativeArray!(string, Value) aa; | |
static assert(!__traits(compiles, { | |
void test() @safe { | |
const _ = aa.values; | |
} | |
})); | |
} | |
/////////////////////////////////////////////////////////////////////////////// | |
// LinkedAssociativeArray implementation. | |
/////////////////////////////////////////////////////////////////////////////// | |
private: | |
enum Iterate { byKey, byValue, byKeyValue } | |
// Generic forward range implementation for byKey/Value/KeyValue. | |
// See also `object.byKey`, `object.byKeyValue`, `object.byValue`. | |
auto byKeyValueImpl(Iterate type, K, V)(ref LinkedAssociativeArray!(K, V) aa) | |
{ | |
static struct Result | |
{ | |
private LinkedEntry!(K, V)* entry; | |
pure nothrow @nogc@safe: | |
@property bool empty() { return this.entry is null; } | |
static if (type == Iterate.byKey) | |
@property ref front() { return this.entry.key; } | |
static if (type == Iterate.byValue) | |
@property ref front() { return this.entry.value; } | |
static if (type == Iterate.byKeyValue) | |
@property auto front() | |
{ | |
static struct Pair | |
{ | |
private K* keyp; | |
private V* valuep; | |
@property ref key() inout { return *this.keyp; } | |
@property ref value() inout { return *this.valuep; } | |
} | |
return Pair(&this.entry.key, &this.entry.value); | |
} | |
void popFront() { this.entry = this.entry.next; } | |
@property Result save() { return this; } | |
} | |
return Result(aa.root); | |
} | |
// Represents an entry in the internal associative array. | |
// Holds a single key-value pair and the double-linked | |
// insertion order list. | |
struct LinkedEntry(Key, Value) | |
{ | |
private Key key; | |
private Value value; | |
// The predecessor in the iteration list. | |
private LinkedEntry* prev = null; | |
// The successor in the iteration list. | |
private LinkedEntry* next = null; | |
} | |
// Helper which creates and links a new entry. | |
auto addEntry(K, V)(ref LinkedAssociativeArray!(K, V) aa, K key, V value) pure nothrow | |
{ | |
auto e = new LinkedEntry!(K, V)(key, value); | |
if (aa.root is null) | |
{ | |
aa.root = e; | |
e.prev = e; | |
} | |
else | |
{ | |
e.prev = aa.root.prev; | |
e.prev.next = e; | |
aa.root.prev = e; | |
} | |
return e; | |
} | |
// Helper which removes and unlinks an existing entry. | |
bool removeEntry(K, V)(ref LinkedAssociativeArray!(K, V) aa, K key) pure nothrow @nogc @safe | |
{ | |
auto p = key in aa.impl; | |
if (p is null) | |
return false; | |
// Keep the doubly-linked list in order. | |
auto e = *p; | |
if (e == aa.root) | |
{ | |
aa.root = e.next; | |
if (e.next !is null) | |
e.next.prev = e.prev; | |
} | |
else if (e.next is null) | |
{ | |
e.prev.next = null; | |
aa.root.prev = e.prev; | |
} | |
else | |
{ | |
e.prev.next = e.next; | |
e.next.prev = e.prev; | |
} | |
aa.impl.remove(key); | |
return true; | |
} | |
version (GNU) | |
{ | |
version (GNU_StackGrowsDown) | |
version = HeapGrowsUp; | |
} | |
else | |
{ | |
version = HeapGrowsUp; | |
} | |
// Helper (questionable) which creates a linked associative array from a | |
// D native associative array literal. | |
// Laughably @trusted, but we *promise* that we are accessing the internal | |
// druntime AA ABI in the correct way (even though we shouldn't!). | |
void dangerouslyReconstructAA(K, V)(ref LinkedAssociativeArray!(K, V) aa, V[K] from) pure nothrow @trusted | |
{ | |
// !!! WONTFIX: We can't possibly know the order of keys and values given as | |
// there is no way to overload the AA literals assignments in D. | |
// The best assumption we can make is that the memory order of entries | |
// is the order that they key[] and value[] arrays were passed to the | |
// _d_assocarrayLiteral runtime function. | |
static struct DRuntimeAABucket | |
{ | |
size_t hash; | |
union Entry | |
{ | |
struct KeyValue | |
{ | |
K key; | |
V value; | |
} | |
KeyValue* keyvalue; | |
size_t addr; | |
} | |
Entry entry; | |
} | |
if (aa.root !is null) | |
aa = aa.init; | |
// This is why I've called this "dangerously". | |
auto buckets = **cast(DRuntimeAABucket[]**)&from; | |
// Copy all entries to a new area, so we don't overwrite the original. | |
auto entries = new DRuntimeAABucket.Entry[buckets.length]; | |
size_t nentries = 0; | |
// Simple (naive?) inlined in-place merge sort by memory address. | |
// Should be O(N log N) time complexity, O(1) space complexity. | |
// Probably more as we need to fix-up the address before and after | |
// calling the sort function. | |
size_t baseAddr = -1; | |
size_t maxAddr = 0; | |
foreach (b; buckets) | |
{ | |
if (b.entry.keyvalue !is null) | |
{ | |
entries[nentries++] = b.entry; | |
if (b.entry.addr < baseAddr) | |
baseAddr = b.entry.addr; | |
if (maxAddr < b.entry.addr) | |
maxAddr = b.entry.addr + 1; | |
} | |
} | |
if (nentries == 0) | |
return; | |
immutable maxOffset = maxAddr - baseAddr; | |
void mergeSort(size_t start, size_t end) | |
{ | |
if (start < end) | |
{ | |
size_t mid = start + (end - start) / 2; | |
mergeSort(start, mid); | |
mergeSort(mid + 1, end); | |
size_t i = start; | |
size_t j = mid + 1; | |
size_t k = start; | |
// Encode the address offset so that both values are stored at `entries[i]`. | |
// `entries[i] % max` will give the original value of `entries[i]`, and | |
// `entries[i] / max` will give the new value. | |
while (i <= mid && j <= end) | |
{ | |
if (entries[i].addr % maxOffset <= entries[j].addr % maxOffset) | |
entries[k++].addr += (entries[i++].addr % maxOffset) * maxOffset; | |
else | |
entries[k++].addr += (entries[j++].addr % maxOffset) * maxOffset; | |
} | |
while (i <= mid) | |
entries[k++].addr += (entries[i++].addr % maxOffset) * maxOffset; | |
while (j <= end) | |
entries[k++].addr += (entries[j++].addr % maxOffset) * maxOffset; | |
// Finally compute the actual values for all elements. | |
foreach (idx; start .. end + 1) | |
entries[idx].addr /= maxOffset; | |
} | |
} | |
// Adjust all entry addresses by the minimum address found, to avoid overflowing. | |
foreach (i; 0 .. nentries) | |
entries[i].addr -= baseAddr; | |
mergeSort(0, nentries - 1); | |
foreach (i; 0 .. nentries) | |
entries[i].addr += baseAddr; | |
// Now add all key-value pairs in memory order. | |
version (HeapGrowsUp) | |
{ | |
foreach (i; 0 .. nentries) | |
aa[entries[i].keyvalue.key] = entries[i].keyvalue.value; | |
} | |
else | |
{ | |
foreach_reverse (i; 0 .. nentries) | |
aa[entries[i].keyvalue.key] = entries[i].keyvalue.value; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment