implementation.clay

//
//  twohash/implementation/implementation.clay
//
//  Copyright (c) 2010 Marc Fauconneau
//
// Permission is hereby granted, free of charge, to any person or organization
// obtaining a copy of the software and accompanying documentation covered by
// this license (the "Software") to use, reproduce, display, distribute,
// execute, and transmit the Software, and to prepare derivative works of the
// Software, and to permit third-parties to whom the Software is furnished to
// do so, all subject to the following:
//
// The copyright notices in the Software and this entire statement, including
// the above license grant, this restriction and the following disclaimer,
// must be included in all copies of the Software, in whole or in part, and
// all derivative works of the Software, unless such copies or derivative
// works are solely in the form of machine-executable object code generated by
// a source language processor.
//
// 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, TITLE AND NON-INFRINGEMENT. IN NO EVENT
// SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
// FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.

//
// basic definitions
//

define EntryType;
define keyMatch?;
define entryHash;

record TwoHash[E]
(
    tables: Array[Table[Bucket[E]], 2],
    size: SizeT,
);

[E]
overload EntryType(#TwoHash[E]) = E;

[T]
TwoHash?(#T) = false;

[E]
overload TwoHash?(#TwoHash[E]) = true;

[E]
overload RegularRecord?(#TwoHash[E]) = false;

record Table[B]
(
    ptr: Pointer[B],
    ln2_size: Int,
);

[B]
overload RegularRecord?(#Table[B]) = false;

record Bucket[E]
(
    hashBytes: Array[Byte, 16],
    entries: Array[E, 16],
);

[E]
overload RegularRecord?(#Bucket[E]) = false;

//
// ctors
//

[E]
overload TwoHash[E]() 
{
    var tableA = Table[Bucket[E]](0);
    var tableB = Table[Bucket[E]](0);
    return TwoHash[E](array(move(tableA), move(tableB)), SizeT(0));
}

[B]
overload Table[B](ln2_size: Int) 
{
    var size = bitshl(1, ln2_size);
    var ptr = allocateRawMemoryAligned(B, size, 16);
    initializeMemory(ptr, ptr+size);
    return Table[B](ptr, ln2_size);
}

[E]
overload initialize(b: Bucket[E])
{
    for (x in b.hashBytes) x = 255uss;
}

//
// move semantics
//

[B]
inline overload moveUnsafe(src: Table[B]) --> returned: Table[B] {
    returned.ptr = src.ptr;
    returned.ln2_size = src.ln2_size;
}

[B]
inline overload resetUnsafe(t: Table[B]) {
    t.ptr = null(B);
    t.ln2_size = 0; // actually -infinity
}

//
// dtor
//

[E]
overload destroy(th: TwoHash[E]) 
{
    for (t in th.tables)
        destroy(t);
}

[B]
overload destroy(t: Table[B])
{
    if (not null?(t.ptr))
    {
        destroyMemory(t.ptr, t.ptr+size(t));
        freeRawMemoryAligned(t.ptr);
    }
}

[E]
overload destroy(b: Bucket[E])
{
    for (i in range(16))
    {
        if (b.hashBytes[i] != 255)
            destroy(b.entries[i]);
    }
}

//
// pEntryAt
//

[E, K]
pEntryAt(th: TwoHash[E], key: K) 
{
    var hash = splitHash(th, key);
    //println("meh", hash);
    for (i in range(2))
    {
        for (j in range(16))
        {
            if (th.tables[i][hash[i]].hashBytes[j] == hash[2])
            {
                ref entry = th.tables[i][hash[i]].entries[j];
                if (keyMatch?(entry, key))
                    return &entry;
            }
        }
    }
    return null(E);
}

//
// allocateEntryAt
//

[E, K]
allocateEntryAt(th: TwoHash[E], key: K, rvalue entry: E)
{
    assert(null?(pEntryAt(th, key)), "buggy allocation");
    
retry:
    var hash = splitHash(th, key);
    var entryCount = array(0,0);
    for (i in range(2))
    {
        for (k in range(16))
        {
            if (th.tables[i][hash[i]].hashBytes[k] != 255)
                entryCount[i] += 1;
        }
    }
    
    if (min(entryCount[0], entryCount[1]) == 16)
    {
        grow(th);
        //return allocateEntryAt(th, key, move(entry));
        goto retry;
    }
    
    var bi = 0;
    if (entryCount[1] < entryCount[0])
        bi = 1;
        
    th.size += 1;
    return allocateInBucket(th, th.tables[bi][hash[bi]], entry, hash[2]);
}

//
// freeEntry
//

[P]
overload inside(v, p: P) = (SizeT(p) >= SizeT(&v) and SizeT(p) < SizeT(&v+1));

[R, P when CallDefined?(begin, R)]
inside(range: R, p: P) = (SizeT(p) >= SizeT(begin(range)) and SizeT(p) < SizeT(end(range)));

[E]
freeEntry(th: TwoHash[E], pEntry: Pointer[E])
{
    var i = -1;
    if (inside(th.tables[0], pEntry)) i = 0;
    if (inside(th.tables[1], pEntry)) i = 1;
    assert(i>=0);

    var j = (SizeT(pEntry)-SizeT(&th.tables[i][0].entries[0])) \ TypeSize(Bucket[E]);
    var k = (SizeT(pEntry)-SizeT(&th.tables[i][j].entries[0])) \ TypeSize(E);
    assert(&th.tables[i][j].entries[k] == pEntry);

    th.tables[i][j].hashBytes[k] = 255uss;
    destroy(th.tables[i][j].entries[k]);
    th.size -= 1;
}

//
// TwoHashEntries
//

record TwoHashEntries[E, F]
(
    data: Pointer[TwoHash[E]],
    i: Int,
    j: Int,
    entryMask: Int,
);

record TwoHashEntry[E, F]
(
    entry: Pointer[E],
);

[E, F]
overload TwoHashEntries[E, F](th: TwoHash[E])
{
    var x = TwoHashEntries[E, F](&th, 0, 0, 0);
    refillMask(x);
    return x;
}

[E, F]
overload iterator(x: TwoHashEntries[E, F]) = x;

[E, F]
overload nextValue(x: TwoHashEntries[E, F])
{
    if (x.entryMask != 0) {
        var k = lowBit(x.entryMask);
        x.entryMask = x.entryMask - bitshl(1, k);
        ref e = x.data^.tables[x.i][x.j].entries[k];
        if (x.entryMask == 0)
        {
            nextBucket(x);
            refillMask(x);
        }
        return TwoHashEntry[E,F](&e);
    } else
        return TwoHashEntry[E,F]();
}

[E, F]
overload hasValue?(x: TwoHashEntry[E, F]) = not null?(x.entry);
[E, F]
overload getValue(x: TwoHashEntry[E, F]) = forward ..F(&x.entry);

[E, F]
nextBucket(x: TwoHashEntries[E, F])
{
    x.j += 1;
    if (x.j == size(x.data^.tables[x.i]))
    {
        x.i += 1;
        x.j = 0;
    }
}

[E, F]
refillMask(x: TwoHashEntries[E, F])
{
    ref th = x.data^;
    while(true)
    {
        if (x.i == 2) return;
        for (k in range(16))
        {
            if (th.tables[x.i][x.j].hashBytes[k] != 255uss)
                x.entryMask = bitor(x.entryMask, bitshl(1, k));
        }
        if (x.entryMask != 0) return;
        nextBucket(x);
    }
}

//
// Table misc
//

[B]
overload size(t: Table[B]) = bitshl(1, t.ln2_size);

[B]
overload index(t: Table[B], idx) = ref t.ptr[idx];

[B]
overload begin(t: Table[B]) = &t.ptr[0];

[B]
overload end(t: Table[B]) = begin(t) + size(t);

//
// hashing
//

largeHash(x) 
{
    var h = UInt64(hash(x));
    var e = bitshr(wrapMultiply(h, 0x70010101ul), 8);
    return wrapAdd(e, wrapBitshl(e, 32));
}

baseSplitHash(hash: UInt64)
{
    var lowHash = wrapCast(SizeT, bitand(hash, 127));
    var hash1 = wrapCast(SizeT, bitshr(hash, 8));
    var hash2 = wrapCast(SizeT, bitshr(hash, 32));
    return array(hash1, hash2, lowHash);
}

[E]
overload baseSplitHash(th: TwoHash[E], hash: UInt64)
{
    var sh = baseSplitHash(hash);
    
    sh[0] = bitand(sh[0], size(th.tables[0])-1);
    sh[1] = bitand(sh[1], size(th.tables[1])-1);
    return sh;
}

define splitHash;

[E, K]
overload splitHash(th: TwoHash[E], key: K) = baseSplitHash(th, largeHash(key));

[E]
overload splitHash(th: TwoHash[E], entry: E) = baseSplitHash(th, entryHash(entry));

//
// helpers
//

moveEntry(entry, th) = move(entry);

[E]
allocateInBucket(th, b: Bucket[E], entry: E, hashByte)
{
    for (k in range(16))
    {
        if (b.hashBytes[k] == 255)
        {
            b.hashBytes[k] = Byte(hashByte);
            var pEntry = &b.entries[k];
            pEntry^ <-- moveEntry(entry, th);
            return pEntry;
        }
    }

    assert(false, "shouldn't reach");
    return null(E);
}

[E]
grow(th: TwoHash[E])
{
    var i = 0;
    if (size(th.tables[0]) > size(th.tables[1]))
        i = 1;

    var oldTable = move(th.tables[i]);
    th.tables[i] = Table[Bucket[E]](oldTable.ln2_size+1);
    
    for (j in indexes(oldTable))
    {
        for (k in range(16))
        {
            if (oldTable[j].hashBytes[k] != 255)
            {
                ref entry = oldTable[j].entries[k];
                var hash = splitHash(th, entry);
                ref newBucket = th.tables[i][hash[i]];
                
                allocateInBucket(th, newBucket, entry, hash[2]);
            }
        }
    }
}

[E]
debugPrint(th: TwoHash[E])
{
    var showBuckets = false;
    
    var total_uses = 0;
    for (i in indexes(th.tables))
    {
        println("table", i,": ", size(th.tables[i]), " buckets");
        var table_uses = 0;
        for (j in indexes(th.tables[i]))
        {
            var uses = 0;
            if (showBuckets) print("bucket[", j,"].hashBytes = [");
            for (k in indexes(th.tables[i][j].hashBytes))
            {
                var v = th.tables[i][j].hashBytes[k];
                if (showBuckets and k != 15) print(v, ", ");
                if (showBuckets and k == 15) println(v, "]");
                if (v != 255) uses += 1;
            }
            var usage = Int( Double(uses)/(16) * 100 );
            if (showBuckets) println("bucket[", j,"] has ", usage, "% occupation");
            table_uses += uses;
            /*
            for (k, v in enumerated(th.tables[i][j].entries))
            {
                if (th.tables[i][j].hashBytes[k] == 255)
                    println("bucket[",j,"].entries[",k,"] = <empty>");
                else
                    println("bucket[",j,"].entries[",k,"] = ", v);
            }*/
        }
        var usage = Int( Double(table_uses)/(16 * size(th.tables[i])) * 100 );
        println("table", i," has ", usage, "% occupation");
        total_uses += table_uses;
    }
    var usage = Int( Double(total_uses)/( 16 * (size(th.tables[0]) + size(th.tables[1])) ) * 100 );
    println("hashtable has ", usage, "% occupation");
}

//
// misc
//

indexes(a) = range(size(a));

[I]
ilog2(n: I)
{
    for (b in reverse(range(TypeSize(I)*8)))
        if (bitand(bitshr(n, b), 1) == 1) return Int(b);
    return -1; // actually -infinity
}

lowBit(m) = ilog2(bitand(m, -m));