Map/dictionary data structure
=============================

Requirements
------------

* Fast in the common case
* Safe against Denial-of-Service
* Must support arena allocation

Key interface
-------------

In order to support the cases above, it is necessary for objects to have
a hash (for fast lookup) and a comparison function (for Denial-of-Service
protection in case of hash collisions).

    type Key<T> = struct {
        slot T key
    }

    type ComparisonResult = closed enum {
        lower  = -1
        equal  =  0
        higher =  1
    }

    func Key<T>.hash() -> uint     # or should it be uint64 ?
    func Key<T>.compare_to(Key<T> other) -> ComparisonResult

Other languages like Zig use a context parameter to support different
types of keys without RTTI (run-time type information).

But it would be really nice to avoid this for common key types:

* String
* Integer
* Reference


Data structure
--------------

    meta-data -> buckets -> one AVL tree per bucket

When the buckets array needs to grow, it will have to be copied to a new
space. But the old space can be re-used for tree nodes!

Public structure:
TODO: add support for inaccessible/private struct fields to SLUL.

    type Map<K,V> = struct {
        private var usize
        private var ref
    }

    # How to to iteration?
    #   - have an array in the iterator for the stack?
    #   - have a next-pointer in each node?
    #
    #type MapIterator<K,V> = struct {
    #    private ref
    #    private ref
    #    private usize
    #}


Private structures (probably can't be implemented in SLUL):
    
    type Map<K,V> = struct {
        var usize num_elems
        "union {"
            # if num_elems == 1
            var ref MapNode<K,V> single_node
            # if num_elems >= 2
            var ref var MapNode<K,V>[round_up_to_pow2(num_elems)] buckets
        "}"
    }

    type MapNode<K,V> = struct {
        var AvlRankDelta avl_rankdelta
        var uint8 tag
        uint hash
        slot K key
        var slot V value
    }

    type AvlRankDelta = enum {
        minus = -1
        zero  =  0
        plus  =  1
    }

Private iterator structure

    type MapIterator<K,V> = struct {
        # TODO
    }


Map client interface
--------------------

TODO: are lifetime specifications needed?
TODO: nullable type parameters?
TODO: decide on / implement var(this) or var_this syntax. only allow var(this), i.e. not other variants? and only in method returns and in parameters?
TODO: aliasing?

    func Map<K,V>.contains(slot K key) -> boolean
    func Map<K,V>.find(slot K key) -> ?ref var(this) MapNode<K,V>
    func Map<K,V>.must_find(arena, slot K key) -> slot V   # throws if absent
    func Map<K,V>.iterator(arena) -> MapIterator<K,V>
        lifetime return <= this

    func var Map<K,V>.put(slot K key, slot V value) -> ?ref var(this) MapNode<K,V>
    func var Map<K,V>.put_if_absent(slot K key, slot V value) -> boolean

    # FIXME how can MapNode work with serialized maps?
    func MapNode<K,V>.get_key() -> var(this) slot K
    func MapNode<K,V>.get_value() -> var(this) slot V
    func var MapNode<K,V>.set_value(slot V) -> slot V
    func MapNode<K,V>.get_tag() -> uint8
    func var MapNode<K,V>.set_tag(uint8 tag)