
    <<HashTableImpl.mesa>>
    <<Copyright  1986 by Xerox Corporation.  All rights reserved.>>
        <<Adapted from HashTableImpl.mesa by Satterthwaite, March 21, 1986 4:27:51 pm PST>>
        <<Last Edited by Satterthwaite, May 13, 1986 11:42:56 am PDT>>

    DIRECTORY
        HashTable: TYPE USING [
            Key, Value, Table, OpsRec, EachValueAction, TableRec, Seq, SeqIndex, NodeList];

    HashTableImpl: CEDAR MONITOR LOCKS table USING table: Table
        EXPORTS HashTable = { 

    Key: TYPE = HashTable.Key;
    Value: TYPE = HashTable.Value;
    Table: TYPE = HashTable.Table;

    NodeList: TYPE = HashTable.NodeList;
    SeqIndex: TYPE = HashTable.SeqIndex;
<<Public operations>>
    Create: PUBLIC PROC[ops: HashTable.OpsRec, mod: SeqIndex_71] RETURNS[Table] =  {
        mod _ MAX[mod, minMod];
        RETURN[NEW [HashTable.TableRec _ [
            ops: ops,
            size: 0,
            sizeLimit: mod,
            inhibitCount: 0,
            data: NEW [HashTable.Seq[mod]]
            ]]]
        };

    minMod: SeqIndex = 2;

    GetSize: PUBLIC PROC[table: Table] RETURNS[INT] = {
        RETURN[table.size]};

    ComputeIndex: PROC[table: Table, key: Key] RETURNS[SeqIndex] = INLINE {
        RETURN[table.ops.HashFromKey[key] MOD table.data.max]};

    Fetch: PUBLIC ENTRY PROC[table: Table, key: Key] RETURNS[found: BOOL, value: Value] = {
        ENABLE UNWIND => NULL;
        hash: SeqIndex = ComputeIndex[table, key];
        FOR node: NodeList _ table.data[hash], node.rest WHILE node # NIL DO
            IF table.ops.EqualKeys[key, table.ops.GetKey[node.first]] THEN
                RETURN[TRUE, node.first];
            ENDLOOP;
        RETURN [FALSE, NIL]};

    Replace: PUBLIC ENTRY PROC[table: Table, key: Key, value: Value] RETURNS[BOOL] = {
        ENABLE UNWIND => NULL;
        hash: SeqIndex = ComputeIndex[table, key];
        FOR node: NodeList _ table.data[hash], node.rest WHILE node # NIL DO
            IF table.ops.EqualKeys[key, table.ops.GetKey[node.first]] THEN {
                node.first _ value; RETURN[TRUE]};
            ENDLOOP;
        RETURN[FALSE]};

    Store: PUBLIC ENTRY PROC[table: Table, key: Key, value: Value] RETURNS[BOOL] = {
        ENABLE UNWIND => NULL;
        hash: SeqIndex = ComputeIndex[table, key];
        FOR node: NodeList _ table.data[hash], node.rest WHILE node # NIL DO
            IF table.ops.EqualKeys[key, table.ops.GetKey[node.first]] THEN { 
                node.first _ value; RETURN [FALSE]};
            ENDLOOP;
        table.data[hash] _ CONS[first: value, rest: table.data[hash]];
        IF (table.size _ table.size + 1) > table.sizeLimit AND table.inhibitCount = 0 THEN
            ReHash[table];
        RETURN [TRUE]};

    Insert: PUBLIC ENTRY PROC[table: Table, key: Key, value: Value] RETURNS[BOOL] = {
        ENABLE UNWIND => NULL;
        hash: SeqIndex = ComputeIndex[table, key];
        FOR node: NodeList _ table.data[hash], node.rest WHILE node # NIL DO
            IF table.ops.EqualKeys[key, table.ops.GetKey[node.first]] THEN 
                RETURN[FALSE];
            ENDLOOP;
        table.data[hash] _ CONS[first: value, rest: table.data[hash]];
        IF (table.size _ table.size + 1) > table.sizeLimit AND table.inhibitCount = 0 THEN
            ReHash[table];
        RETURN[TRUE]};

    Delete: PUBLIC ENTRY PROC[table: Table, key: Key] RETURNS[BOOL] = {
        ENABLE UNWIND => NULL;
        hash: SeqIndex = ComputeIndex[table, key];
        lag: NodeList _ NIL;
        FOR node: NodeList _ table.data[hash], node.rest WHILE node # NIL DO
            IF table.ops.EqualKeys[key, table.ops.GetKey[node.first]] THEN {
                IF lag = NIL THEN table.data[hash] _ node.rest ELSE lag.rest _ node.rest;
                table.size _ table.size - 1;
                RETURN[TRUE]};
            lag _ node;
            ENDLOOP;
        RETURN[FALSE]};

    ForEach: PUBLIC PROC[table: Table, action: HashTable.EachValueAction]
          RETURNS[quit: BOOL] = {
        
            {ENABLE UNWIND => 
            head: NodeList _ NIL;
            index: CARDINAL _ table.data.max;
            DO
                [head, index] _ GetNext[table, head, index];
                IF head = NIL THEN {quit _ FALSE; EXIT};
                IF action[head.first] THEN {quit _ TRUE; EXIT};
                ENDLOOP;
            };
        

    
        table.inhibitCount _ table.inhibitCount + 
        WHILE table.inhibitCount = 0 AND table.size > table.sizeLimit DO ReHash[table] ENDLOOP};

    GetNext: ENTRY PROC[table: Table, head: NodeList, index: CARDINAL]
          RETURNS[NodeList, CARDINAL] = {
        ENABLE UNWIND => NULL;
        IF head # NIL THEN {
            head _ head.rest;
            IF head # NIL THEN RETURN[head, index]};
        WHILE index > 0 DO
            index _ index - 1;
            head _ table.data[index];
            IF head # NIL THEN RETURN[head, index];
            ENDLOOP;
        RETURN[NIL, 0]};

    Erase: PUBLIC ENTRY PROC[table: Table] = {
        FOR i: SeqIndex IN [0..table.data.max) DO table.data[i] _ NIL ENDLOOP;
        table.size _ 0};

    ReHash: INTERNAL PROC[table: Table] = {
        oldData: REF HashTable.Seq = table.data;
        newData: REF HashTable.Seq;
        seek: CARDINAL = table.data.max * 2;
        newPTI, newMod: CARDINAL _ 0;
        IF primeTable[PrimeTableSize-1] > SeqIndex.LAST THEN ERROR;
        FOR newPTI _ 0, newPTI+1 WHILE newPTI+1 < PrimeTableSize AND primeTable[newPTI] < seek DO NULL ENDLOOP;
        newMod _ primeTable[newPTI];
        IF newMod = table.data.max THEN {table.sizeLimit _ INT.LAST; RETURN};
        table.sizeLimit _ newMod;
        table.data _ newData _ NEW [HashTable.Seq[newMod]];
        FOR i: NAT IN [0 .. oldData.max) DO
            next: NodeList _ NIL;
            FOR cur: NodeList _ oldData[i], next WHILE cur # NIL DO
                hash: SeqIndex = ComputeIndex[table, table.ops.GetKey[cur.first]];
                next _ cur.rest;
                cur.rest _ newData[hash];
                newData[hash] _ cur;
                ENDLOOP;
            IF next # NIL THEN ERROR;
            ENDLOOP;
        table _ table};

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

    }.



