<<>>
    <<IntToIntTabImpl.mesa>>
        <<Copyright Ó 1987, 1988, 1990, 1991 by Xerox Corporation.  All rights reserved.>>
        <<Adapted from similar package by Christian Jacobi, May 13, 1987 10:43:20 am PDT>>
        <<Christian Jacobi, July 19, 1990 12:43 pm PDT>>

    DIRECTORY 
        IntToIntTab;

    IntToIntTabImpl: CEDAR MONITOR LOCKS table USING table: Table
        EXPORTS IntToIntTab = 
    BEGIN 
        OPEN IntToIntTab;

        Impl: TYPE ~ REF IntToIntTabImplRep;
        IntToIntTabImplRep: PUBLIC TYPE = RECORD [
            size, sizeLimit, inhibitCount: INT,
            data: REF Seq
            ];

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

        Node: TYPE = REF NodeRep;
        NodeRep: TYPE = RECORD [key: Key, val: Val, next: Node];

        minMod: SeqIndex = 2;

    Create: PUBLIC PROC [mod: SeqIndex Ź 17] RETURNS [Table] =  {
        seqLen: SeqIndex ~ MAX[mod, minMod];
        impl: Impl ~ NEW [IntToIntTabImplRep Ź [
            size: 0, sizeLimit: seqLen, inhibitCount: 0,
            data: NEW [Seq[seqLen]]
            ]];
        RETURN [NEW [IntToIntTabRep Ź [impl: impl]]];
        };

    GetSize: PUBLIC ENTRY PROC [table: Table] RETURNS [INT] = {
        <<ENABLE UNWIND => NULL;>>
        impl: Impl ~ table.impl;
        RETURN [impl.size];
        };

    Nicefy: PROC [key: INT32] RETURNS [CARD32] = INLINE {
    <<--for 32 bit machine CARD32 is good operand for MOD operation>>
        RETURN [ LOOPHOLE[key] ]
        };

    ComputeIndex: PROC [impl: Impl, key: Key] RETURNS [index: SeqIndex] = INLINE {
        index Ź Nicefy[key] MOD impl.data.max;
        };

    Fetch: PUBLIC ENTRY PROC [table: Table, key: Key] RETURNS [found: BOOL, val: Val] = {
        <<ENABLE UNWIND => NULL;>>
        impl: Impl ~ table.impl;
        hash: SeqIndex Ź ComputeIndex[impl, key];
        node: Node Ź impl.data[hash];
        WHILE node # NIL DO
            IF key=node.key THEN RETURN [TRUE, node.val];
            node Ź node.next;
            ENDLOOP;
        RETURN [FALSE, -1];
        };

    Replace: PUBLIC ENTRY PROC [table: Table, key: Key, val: Val] RETURNS [BOOL] = {
        <<ENABLE UNWIND => NULL;>>
        impl: Impl ~ table.impl;
        hash: SeqIndex Ź ComputeIndex[impl, key];
        node: Node Ź impl.data[hash];
        WHILE node # NIL DO
            IF key=node.key THEN {node.val Ź val; RETURN [TRUE]};
            node Ź node.next;
            ENDLOOP;
        RETURN [FALSE];
        };

    Store: PUBLIC ENTRY PROC [table: Table, key: Key, val: Val] RETURNS [BOOL] = {
        <<ENABLE UNWIND => NULL;>>
        impl: Impl ~ table.impl;
        hash: SeqIndex Ź ComputeIndex[impl, key];
        node: Node Ź impl.data[hash];
        WHILE node # NIL DO
            IF key=node.key THEN {node.val Ź val; RETURN [FALSE]};
            node Ź node.next;
            ENDLOOP;
        impl.data[hash] Ź NEW[NodeRep Ź [key: key, val: val, next: impl.data[hash]]];
        IF (impl.size Ź impl.size + 1) > impl.sizeLimit AND impl.inhibitCount = 0 THEN ReHash[impl];
        RETURN [TRUE];
        };

    Insert: PUBLIC ENTRY PROC [table: Table, key: Key, val: Val] RETURNS [BOOL] = {
        ENABLE UNWIND => NULL;
        impl: Impl ~ table.impl;
        hash: SeqIndex Ź ComputeIndex[impl, key];
        node: Node Ź impl.data[hash];
        WHILE node # NIL DO
            IF key=node.key THEN RETURN [FALSE];
            node Ź node.next;
            ENDLOOP;
        impl.data[hash] Ź NEW[NodeRep Ź [key: key, val: val, next: impl.data[hash]]];
        IF (impl.size Ź impl.size + 1) > impl.sizeLimit AND impl.inhibitCount = 0 THEN ReHash[impl];
        RETURN [TRUE];
        };

    Delete: PUBLIC ENTRY PROC [table: Table, key: Key] RETURNS [BOOL] = {
        <<ENABLE UNWIND => NULL;>>
        impl: Impl ~ table.impl;
        hash: SeqIndex Ź ComputeIndex[impl, key];
        node: Node Ź impl.data[hash];
        lag: Node Ź NIL;
        WHILE node # NIL DO
            IF key=node.key THEN {
                IF lag = NIL THEN impl.data[hash] Ź node.next ELSE lag.next Ź node.next;
                impl.size Ź impl.size - 1;
                RETURN [TRUE];
                };
            lag Ź node;
            node Ź node.next;
            ENDLOOP;
        RETURN [FALSE];
        };

    Erase: PUBLIC ENTRY PROC [table: Table] = {
        <<ENABLE UNWIND => NULL;>>
        impl: Impl ~ table.impl;
        FOR i: SeqIndex IN [0..impl.data.max) DO impl.data[i] Ź NIL ENDLOOP;
        impl.size Ź 0;
        };

    Pairs: PUBLIC PROC [table: Table, action: EachPairAction] RETURNS [quit: BOOL] = {
        Inhibit: ENTRY PROC [table: Table] ~ {
            <<ENABLE UNWIND => NULL;>>
            impl: Impl ~ table.impl;
            impl.inhibitCount Ź impl.inhibitCount + 1;
            };
        Release: ENTRY PROC [table: Table] ~ {
            <<ENABLE UNWIND => NULL;>>
            impl: Impl ~ table.impl;
            impl.inhibitCount Ź impl.inhibitCount - 1;
            IF impl.inhibitCount#0 THEN RETURN;
            WHILE impl.size > impl.sizeLimit DO ReHash[impl] ENDLOOP;
            };
        Enumerate: PROC [table: Table, action: EachPairAction] RETURNS [quit: BOOL Ź FALSE] ~ {
            node: Node Ź NIL;
            index: CARDINAL Ź 0;
            DO
                [node, index] Ź GetNext[table, node, index];
                IF node = NIL THEN EXIT;
                IF action[node.key, node.val] THEN RETURN [TRUE];
                ENDLOOP;
            };
        Inhibit[table];
        quit Ź Enumerate[table, action ! UNWIND => Release[table]];
        Release[table];
        };

    GetNext: ENTRY PROC [table: Table, node: Node, index: CARDINAL] RETURNS [Node, CARDINAL] = {
        <<ENABLE UNWIND => NULL;>>
        impl: Impl ~ table.impl;
        IF node = NIL
            THEN index Ź impl.data.max
            ELSE {
                node Ź node.next;
                IF node # NIL THEN RETURN [node, index];
                };
        WHILE index > 0 DO
            index Ź index - 1;
            node Ź impl.data[index];
            IF node # NIL THEN RETURN [node, index];
            ENDLOOP;
        RETURN [NIL, 0];
        };

    Update: PUBLIC ENTRY PROC [table: Table, key: Key, action: UpdateAction] = {
        ENABLE UNWIND => NULL; --necessary: calls client procedure
        IF action # NIL THEN {
            impl: Impl ~ table.impl;
            index: SeqIndex Ź ComputeIndex[impl, key];
            head: Node Ź impl.data[index];
            node: Node Ź head;
            lag: Node Ź NIL;
            op: UpdateOperation Ź none;
            val: Val;
            WHILE node # NIL DO
                next: Node Ź node.next;
                IF key=node.key THEN {
                    [op, val] Ź action[TRUE, node.val];
                    SELECT op FROM
                        delete => IF lag = NIL THEN impl.data[index] Ź next ELSE lag.next Ź next;
                        store => node.val Ź val;
                        ENDCASE;
                    RETURN;
                    };
                lag Ź node;
                node Ź next;
                ENDLOOP;
            [op, val] Ź action[FALSE, -1];
            SELECT op FROM
                store => {
                    impl.data[index] Ź NEW[NodeRep Ź [key: key, val: val, next: head]];
                    IF (impl.size Ź impl.size + 1) > impl.sizeLimit AND impl.inhibitCount = 0 THEN
                        ReHash[impl];
                    };
                ENDCASE;
            };
        };

    Copy: PUBLIC ENTRY PROC [table: Table] RETURNS [Table] = {
        <<ENABLE UNWIND => NULL;>>
        impl: Impl = table.impl;
        oldData: REF Seq = impl.data;
        max: CARDINAL = oldData.max;
        newImpl: Impl = NEW[IntToIntTabImplRep Ź impl­];
        newData: REF Seq = NEW[Seq[max]];  -- note, all buckets initially NIL
        newImpl.data Ź newData;
        FOR i: NAT IN [0..max) DO
            oldChain: Node Ź oldData[i];
            IF oldChain # NIL THEN {
                newTail: Node Ź NIL;
                WHILE oldChain # NIL DO
                    new: Node Ź NEW[NodeRep Ź [key: oldChain.key, val: oldChain.val, next: NIL]];
                    IF newTail = NIL THEN newData[i] Ź new ELSE newTail.next Ź new;
                    newTail Ź new;
                    oldChain Ź oldChain.next;
                    ENDLOOP;
                };
            ENDLOOP;
        RETURN [NEW[IntToIntTabRep Ź [impl: newImpl]]];
        };
        <<>>
    ReHash: INTERNAL PROC [impl: Impl] = {
        oldData: REF Seq = impl.data;
        newData: REF Seq;
        seek: CARDINAL = impl.data.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 = impl.data.max THEN {impl.sizeLimit Ź LAST[INT]; RETURN};
        impl.sizeLimit Ź newMod;
        impl.data Ź newData Ź NEW[Seq[newMod]];
        FOR i: SeqIndex IN [0 .. oldData.max) DO
            next: Node Ź NIL;
            FOR cur: Node Ź oldData[i], next WHILE cur # NIL DO
                hash: SeqIndex Ź ComputeIndex[impl, cur.key];
                next Ź cur.next;
                cur.next Ź newData[hash];
                newData[hash] Ź cur;
                ENDLOOP;
            IF next # NIL THEN ERROR;
            ENDLOOP;
        };

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