HashTable implementation in Vala

hash-table.vala

/* This is free and unencumbered software released into the public domain.
 *
 * Anyone is free to copy, modify, publish, use, compile, sell, or distribute
 * this software, either in source code form or as a compiled binary, for any
 * purpose, commercial or non-commercial, and by any means.
 *
 * In jurisdictions that recognize copyright laws, the author or authors of this
 * software dedicate any and all copyright interest in the software to the public
 * domain. We make this dedication for the benefit of the public at large and to
 * the detriment of our heirs and successors. We intend this dedication to be an
 * overt act of relinquishment in perpetuity of all present and future rights to
 * this software under copyright law.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 * For more information, please refer to <http://unlicense.org/>
 */

[Compact (opaque = true)]
class HashTableEntry<T> {
    public string? key { get; private set; }
    public T @value { get; owned set; }
    public HashTableEntry<T>? next { get; owned set; }

    public HashTableEntry (string? key, owned T @value) {
        this.key = key;
        this.@value = (owned) @value;
    }

    ~HashTableEntry () {
        /* Due to the fact that generic compact classes never receive a
         * destroy_func, Vala doesn't know how to free the strong generic
         * references, and leaves them unfreed. We need to manually write the
         * code to free them, if we don't want to have memleaks in our program.
         *
         * Note that I'm using a simple g_free() here, since I'm not going to
         * deal with anything more complex than an int. If you need to free
         * something more complex, then you might want to add an extra method to
         * receive a destroy_func, and use it here. */
        if (@value != null)
            delete (void*) @value;
    }
}

[Compact (opaque = true)]
class HashTableIterator<T> {
    private unowned HashTable<T> _table;
    private unowned HashTableEntry<T>? _current;
    private uint _index;

    public HashTableIterator (HashTable<T> table) {
        _table = table;
    }

    public unowned HashTableEntry<T> @get () {
        return _current;
    }

    public bool next () {
        if (_current?.next != null) {
            _current = _current.next;
            return true;
        }

        while (_index < _table.entries.length) {
            uint i = _index;
            _index++;

            if (_table.entries[i] != null) {
                _current = _table.entries[i];
                return true;
            }
        }

        return false;
    }
}

[Compact (opaque = true)]
class HashTable<T> {
    internal HashTableEntry<T>?[] entries = new HashTableEntry<T>?[20];

    public uint size { get; private set; }

    private uint str_hash (string? str) {
        if (str == null)
            return 0;

        return GLib.str_hash (str);
    }

    public unowned T @get (string? key) {
        uint hash = str_hash (key);
        uint index = hash % entries.length;

        if (entries[index] != null) {
            unowned HashTableEntry<T>? temp = entries[index];

            while (key != temp.key && temp.next != null)
                temp = temp.next;

            return temp.@value;
        }

        return null;
    }

    private void grow_if_needed () {
        if (size < entries.length * 0.6)
            return;

        print ("Threshold crossed, resizing internal array...\n");
        entries.resize (entries.length * 2);
    }

    public void @set (string key, owned T @value) {
        grow_if_needed ();

        uint hash = str_hash (key);
        uint index = hash % entries.length;

        if (entries[index] == null) {
            print ("Key not found, creating new entry...\n");

            entries[index] = new HashTableEntry<T> (key, (owned) @value);
            size++;

            return;
        }

        unowned HashTableEntry<T>? temp = entries[index];
        while (true) {
            if (key == temp.key) {
                print ("Key found, setting new value...\n");
                temp.@value = (owned) @value;

                return;
            }

            if (temp.next == null)
                break;

            temp = temp.next;
        }

        print ("Collision! Creating new linked entry...\n");

        temp.next = new HashTableEntry<T> (key, (owned) @value);
        size++;
    }

    public HashTableIterator<T> iterator () {
        return new HashTableIterator<T> (this);
    }
}

void main () {
    var table = new HashTable<int?> ();

    for (var i = 0; i < 50; i++) {
        string key = Uuid.string_random ();
        table[key] = i;
    }

    foreach (unowned HashTableEntry<int?> entry in table)
        print ("Key: %s, Value: %i\n", entry.key, entry.@value);

    print ("\nSize: %u\n", table.size);
}