ikod / ikod-containers

some standard containers, safe, nogc

ikod-containers

You can find generated docs for containers on githubio or on dpldocs.

HashMap

Differences from D associated arrays:

1. HashMap itself is a struct and a value (not a reference), so any assignment map2 = map1 will copy all the data from map1 to map2.
2. HashMap has a deprecated "in" operator. Since a pointer to the value in a table is highly unsafe (as the location of the stored value can change upon mutation), use fetch to test the key existence and fetch its value in a single API call intead of in.
3. Any method from get family returns a value stored in a table, and never - a pointer. It is safe.

Advantages:

1. Faster speed, as it does not allocate on every insert and has optimized storage layout.
2. It inherits @nogc and @safe properties from key and value types, so it can be used in @safe and @nogc code. Note: opIndex can throw exception so it's not @nogc in any case (use fetch or get with default value if you need @nogc)
3. Provides a stable iteration over the container (you can modify/delete table items while iterating over it).

You cah find HashMap API docs here

code sample

import std.range;
import std.algorithm;
import ikod.containers.hashmap;

static string[] words =
[
        "hello", "this", "simple", "example", "should", "succeed", "or", "it",
        "should", "fail"
];

void main() @safe @nogc
{
    HashMap!(string, int) counter;
    // count words, simplest and fastest way
    foreach (word; words) {
        counter[word] = counter.getOrAdd(word, 0) + 1; // getOrAdd() return the value from the table or add it to the table
    }
    assert(counter.fetch("hello").ok);          // fetch() is a replacement to "in": you get "ok" if the key exists in the table
    assert(counter.fetch("hello").value == 1);  // and the value itself
    debug assert(counter["hello"] == 1);        // opIndex is not @nogc
    debug assert(counter["should"] == 2);       // opIndex is not @nogc
    assert(counter.contains("hello"));          // checks the key existence
    assert(counter.length == words.length - 1); // because "should" counts only once
    // iterators
    assert(counter.byKey.count == counter.byValue.count);
    assert(words.all!(w => counter.contains(w))); // all words in table
    assert(counter.byValue.sum == words.length); // sum of counters must equal to the number of words
}

UnrolledList

From Wikipedia, the free encyclopedia [*]

In computer programming, an unrolled linked list is a variation on the linked list which stores multiple elements in each node. It can dramatically increase cache performance, while decreasing the memory overhead associated with storing list metadata such as references. It is related to the B-tree.

Advantages:

• Fast, cache-friendly.
• @nogc, @safe.
• Sane iterators (unstable and stable iterators are supported).

See docs here

code sample

import std.algorithm: equal;
import std.range: iota;

import ikod.containers.unrolledlist: UnrolledList;

void main() @safe @nogc
{
    UnrolledList!int l;
    // add items
    foreach(i; 2..50)
    {
        l.pushBack(i); // push back
    }
    l.pushFront(0); // push front
    l.insert(1,1);  // insert value at arbitrary position
    // get items
    assert(l.front == 0);
    assert(l.back == 49);
    auto v = l.get(25); // get value at some position. Same as l[25] but @nogc
    assert(v.ok);
    assert(v.value == 25);
    // iterators/ranges
    auto r = l.unstableRange();
    assert(equal(r, iota(50)));
}

ikod-containers's Issues

ikod.containers.hashmap.HashMap does not behave as expected for `const(char)[]` keys

#!/usr/bin/env dub
/+dub.sdl:
dependency "ikod-containers" version="~>0.0.20"
+/
void main()
{
    import ikod.containers.hashmap;

    HashMap!(const(char)[], size_t) map;
    const(char)[] key = "key";
    const(char)[] dupKey = key.dup;
    map[dupKey] = 1;
    assert(map[dupKey] == 1); // passes
    assert(key == dupKey); // passes
    assert(map[key] == 1); // fails: key not found
}

Put https://ikod.github.io/ikod-containers/ikod.containers.html on the README and/or github about

Put https://ikod.github.io/ikod-containers/ikod.containers.html on the README and/or github about

Does UnrolledList support work-stealing?

I am thinking of improving the task distribution performance of worker threads, hopefully in the form of work stealing.