
    <<ValueHashTablesImpl.Mesa>>
        <<Last tweaked by Mike Spreitzer on December 15, 1987 10:44:00 am PST>>

    DIRECTORY AbSets, BiRels, SetBasics, ValueHashTables;

    ValueHashTablesImpl: CEDAR MONITOR
        LOCKS ht USING ht: HashTable
        IMPORTS AbSets, BiRels
        EXPORTS ValueHashTables
        =

    BEGIN OPEN SetBasics, Sets:AbSets, Sets, BiRels, ValueHashTables;

    Destroyed: ERROR = CODE;

    HashTable: TYPE ~ REF HashTablePrivate;
    HashTablePrivate: PUBLIC TYPE ~ MONITORED RECORD [
        space: Space,
        size, sizeLimit, inhibitCount: INT _ 0,
        destroyed: BOOL _ FALSE,
        seq: REF Seq
        ];

    SeqIndex: TYPE = NAT;
    Seq: TYPE = RECORD [nodes: SEQUENCE max: SeqIndex OF Node];
    Node: TYPE ~ LOP;

    ComputeIndex: PROC [ht: HashTable, key: Value] RETURNS [SeqIndex] = INLINE {
        RETURN [ht.space.Hash[ht.space.data, key] MOD ht.seq.max];
        };

    Create: PUBLIC PROC [space: Space] RETURNS [ht: HashTable] ~ {
        ht _ NEW [HashTablePrivate _ [
            space: space,
            sizeLimit: initSize,
            seq: NEW [Seq[initSize]]
            ]];
        };

    Size: PUBLIC ENTRY PROC [ht: HashTable] RETURNS [INT] = {
        ENABLE UNWIND => NULL;
        IF ht.destroyed THEN RETURN WITH ERROR Destroyed;
        RETURN [ht.size];
        };

    Map: PUBLIC PROC [ht: HashTable, arg: Value] RETURNS [mv: MaybeValue _ noMaybe] ~ {
        Decide: PROC [old: MaybeValue] RETURNS [MaybeValue] ~ {RETURN [mv _ old]};
        IF ht # Update[ht, arg, Decide] THEN ERROR;
        RETURN};

    Store: PUBLIC  PROC [ht: HashTable, arg, res: Value] RETURNS [same: HashTable] ~ {
        Decide: PROC [old: MaybeValue] RETURNS [MaybeValue] ~ {RETURN [[TRUE, res]]};
        same _ Update[ht, arg, Decide];
        };

    Delete: PUBLIC  PROC [ht: HashTable, arg: Value] RETURNS [had: BOOL _ FALSE] ~ {
        Decide: PROC [old: MaybeValue] RETURNS [MaybeValue] ~ {had _ old.found; RETURN [noMaybe]};
        IF ht # Update[ht, arg, Decide] THEN ERROR;
        };

    Update: PUBLIC ENTRY PROC [ht: HashTable, arg: Value, Decide: Decider] RETURNS [same: HashTable] ~ {
        ENABLE UNWIND => NULL;
        index: SeqIndex ~ ComputeIndex[ht, arg];
        prev: Node _ NIL;
        same _ ht;
        FOR node: Node _ ht.seq[index], node.rest WHILE node # NIL DO
            IF arg=node.first[left] OR ht.space.Equal[ht.space.data, arg, node.first[left]] THEN {
                new: MaybeValue ~ Decide[[TRUE, node.first[right]]];
                IF new.found THEN node.first[right] _ new.it
                ELSE {
                    IF prev=NIL THEN ht.seq[index] _ node.rest ELSE prev.rest _ node.rest;
                    ht.size _ ht.size - 1;
                    };
                RETURN;
                };
            prev _ node;
            ENDLOOP;
        {new: MaybeValue ~ Decide[noMaybe];
        IF new.found THEN {
            ht.seq[index] _ CONS[[arg, new.it], ht.seq[index]];
            IF (ht.size _ ht.size + 1) > ht.sizeLimit AND ht.inhibitCount = 0 THEN same _ ReHash[ht];
            };
        }};

    Scan: PUBLIC PROC [ht: HashTable, Test: Tester] RETURNS [same: HashTable, mp: MaybePair _ noMaybePair] = {
        Inhibit: ENTRY PROC [ht: HashTable] ~ {
            ENABLE UNWIND => NULL;
            ht.inhibitCount _ ht.inhibitCount + 1;
            };
        Release: ENTRY PROC [ht: HashTable] ~ {
            ENABLE UNWIND => NULL;
            same _ ht;
            same.inhibitCount _ same.inhibitCount - 1;
            IF same.inhibitCount#0 THEN RETURN;
            WHILE same.size > same.sizeLimit DO same _ ReHash[same] ENDLOOP;
            };
        IF ht.destroyed THEN RETURN WITH ERROR Destroyed;
        Inhibit[ht];
        {ENABLE UNWIND => Release[ht];
        node: Node _ NIL;
        index: CARDINAL _ 0;
        DO
            [node, index] _ GetNext[ht, node, index];
            IF node = NIL THEN EXIT;
            IF Test[node.first] THEN {mp _ [TRUE, node.first]; EXIT};
            ENDLOOP;
        };
        Release[ht];
        RETURN};

    GetNext: ENTRY PROC [ht: HashTable, node: Node, index: CARDINAL] RETURNS [Node, CARDINAL] = {
        ENABLE UNWIND => NULL;
        IF node = NIL
            THEN index _ ht.seq.max
            ELSE {
                node _ node.rest;
                IF node # NIL THEN RETURN [node, index];
                };
        WHILE index > 0 DO
            index _ index - 1;
            node _ ht.seq[index];
            IF node # NIL THEN RETURN [node, index];
            ENDLOOP;
        RETURN [NIL, 0];
        };

    ReHash: INTERNAL PROC [old: HashTable] RETURNS [new: HashTable] = {
        oldSeq: REF Seq = old.seq;
        newSeq: REF Seq;
        seek: CARDINAL = oldSeq.max * 2;
        newPTI: CARDINAL _ 0;
        newMod: CARDINAL _ highPrime;
        IF seek >= highPrime
            THEN newPTI _ PrimeTableSize-1
            ELSE DO
                newMod _ primeTable[newPTI];
                IF newMod >= seek THEN EXIT;
                newPTI _ newPTI+1;
                ENDLOOP;
        IF newMod = oldSeq.max THEN {old.sizeLimit _ LAST[INT]; RETURN [old]};
        new _ NEW [HashTablePrivate _ [
            space: old.space,
            size: old.size,
            sizeLimit: newMod,
            seq: newSeq _ NEW [Seq[newMod]]
            ]];
        FOR i: SeqIndex IN [0 .. oldSeq.max) DO
            next: Node _ NIL;
            FOR cur: Node _ oldSeq[i], next WHILE cur # NIL DO
                index: SeqIndex _ ComputeIndex[new, cur.first[left]];
                next _ cur.rest;
                cur.rest _ newSeq[index];
                newSeq[index] _ cur;
                ENDLOOP;
            IF next # NIL THEN ERROR;
            ENDLOOP;
        };

    PrimeTableSize: NAT = 14;
        highPrime: CARDINAL[0..LAST[SeqIndex]] = 32749;
        initSize: NAT ~ 5;
    primeTable: ARRAY [0 .. PrimeTableSize) OF CARDINAL = [
        00002,  00005,  00011,  00023,  00053,  00113,  00251,  00509,  01019,  02039,  04079,  08179,  16369,  highPrime];
    END.