-- FILE: HashImpl.mesa
-- Last edited by Ousterhout, May 10, 1983 10:53 am
-- Barth, February 14, 1986 3:21:36 pm PST

DIRECTORY
    Hash,
    Basics,
    IO,
    Rope;

HashImpl: CEDAR PROGRAM
IMPORTS 
    Basics,
    IO,
    Rope
EXPORTS
    Hash =

BEGIN OPEN Hash;

-- The following constant gives the ratio of entries to buckets at which
-- we decide that a hash table is too full and rebuild it with a larger size.

rebuildLimit: INT = 3;


NewTable: PUBLIC PROC[nBuckets: INT ← 16]
    RETURNS [table: Table] =
    
    BEGIN
    size: INT ← 16;
    
    table ← NEW[TableRec];
    
    -- Round the size up to the next power of two.
    
    table.hashDivide ← 128*128;
    table.hashDivide ← table.hashDivide*128*8;
    table.hashMask ← 17B;
    WHILE (size < nBuckets) DO
        size ← size*2;
        table.hashMask ← table.hashMask*2 + 1;
        table.hashDivide ← table.hashDivide/2;
        ENDLOOP;
           
    table.nEntries ← 0;
    table.buckets ← NEW[Buckets[size]];
    table.firstEntry ← NIL;
    RETURN [table];
    END; 


Hash: PROC[table: Table, name: Rope.ROPE]
    RETURNS [CARDINAL] =
    
    -- This is a private procedure to compute a hash table bucket
    -- index based on a rope.
    
    BEGIN
    i: INT ← 0;
    val: INT;
    
    FOR j: INT IN [0..Rope.Length[name]) DO
        i ← (10*i) + (Rope.Fetch[name, j] - '0);
        ENDLOOP;
    
    val ← ((i*1103515245) + 12345) / table.hashDivide;
    RETURN [Basics.BITAND[table.hashMask, Basics.LowHalf[val]]];
    END;


Find: PUBLIC PROC[table: Table, name: Rope.ROPE]
    RETURNS [entry: Entry] =
    
    BEGIN
    index: CARDINAL ← Hash[table, name];
    
    -- See if the entry is already in the table.
    
    entry ← table.buckets[index];
    WHILE entry # NIL DO
        IF Rope.Equal[name, entry.name] THEN RETURN [entry];
        entry ← entry.nextInBucket;
        ENDLOOP;
    
    -- The entry wasn't found.  Before allocating a new entry,
    -- see if we're overloading the buckets.  If so, then make a 
    -- bigger table.
    
    IF table.nEntries > (rebuildLimit*table.buckets.length) THEN
        BEGIN
        Rebuild[table];
        index ← Hash[table, name];
        END;
    
    entry ← NEW[EntryRec];
    entry.name ← name;
    entry.clientData ← NIL;
    entry.nextInBucket ← table.buckets[index];
    table.buckets[index] ← entry;
    table.nEntries ← table.nEntries + 1;
    entry.nextOverall ← table.firstEntry;
    table.firstEntry ← entry;
    RETURN [entry];
    END;


Rebuild: PROC[table: Table] =
 
    -- This is a private procedure that rebuilds a hash table, making it
    -- four times larger than it used to be.
    
    BEGIN
    old: REF Buckets ← table.buckets;
    entry, next: Entry;
    index: CARDINAL;
    
    table.buckets ← NEW[Buckets[4*old.length]];
    table.hashDivide ← table.hashDivide/4;
    table.hashMask ← (table.hashMask * 4) + 3;
    FOR i:CARDINAL IN [0..old.length) DO
        entry ← old[i];
        WHILE (entry # NIL) DO
            next ← entry.nextInBucket;
            index ← Hash[table, entry.name];
            entry.nextInBucket ← table.buckets[index];
            table.buckets[index] ← entry;
            entry ← next;
            ENDLOOP;
        ENDLOOP;
    END;


Enumerate: PUBLIC PROC[table: Table, pattern: Rope.ROPE, proc: EnumProc,
    clientData: REF ANY ← NIL, errorStream: IO.STREAM ← NIL] =
    
    BEGIN
    prefix: Rope.ROPE ← NIL;
    postfix: Rope.ROPE ← NIL;
    length: INT ← Rope.Length[pattern];
    pos, next, last: INT;
    oldPos: INT ← 0;
    c: CHARACTER;
    gotRange: BOOLEAN ← FALSE;
    gotAny: BOOLEAN ← TRUE;
    gotStar: BOOLEAN ← FALSE;
    entry: Entry;
    stream: IO.STREAM;
    
    -- Check for the star that means we do pattern matching.
    
    IF length > 0 THEN
        BEGIN
        IF Rope.Fetch[pattern, 0] = '* THEN
            BEGIN
            pattern ← Rope.Substr[pattern, 1, length-1];
            length ← length-1;
            gotStar ← TRUE;
            END;
        END;
        
    -- Strip off the prefix (everything in the string up to the "<").
    
    WHILE TRUE DO
        pos ← Rope.SkipTo[pattern, oldPos, "\\<"];
        prefix ← Rope.Concat[prefix, Rope.Substr[pattern, oldPos, pos-oldPos]];
        oldPos ← pos + 1;
        IF pos = length THEN EXIT;
        IF pos >= length-1 THEN
            BEGIN
            IF errorStream # NIL THEN
                IO.PutF[errorStream, "Can't end pattern with \"%c\".\n",
                    IO.char[Rope.Fetch[pattern, length-1]]];
            RETURN;
            END;
        c ← Rope.Fetch[pattern, pos];
        IF c = '< THEN EXIT;
        oldPos ← pos+2;
        prefix ← Rope.Concat[prefix, Rope.Substr[pattern, pos+1, 1]];
        ENDLOOP;
    
    -- Grab up the range.
    
    IF pos < length THEN
        BEGIN
        pos ← Rope.SkipTo[pattern, oldPos, ">"];
        IF pos < length THEN
            BEGIN
            ENABLE ANY =>
                BEGIN
                IF errorStream # NIL THEN
                    IO.PutRope[errorStream, "Syntax error in range specifier.\n"];
                GOTO quit;
                END;
                
            stream ← IO.RIS[Rope.Substr[pattern, oldPos, pos-oldPos]];
            next ← IO.GetInt[stream];
            IF IO.GetChar[stream] # ': THEN
                BEGIN
                IF errorStream # NIL THEN
                    IO.PutRope[errorStream, "Missing \":\" in range.\n"];
                RETURN;
                END;
            last ← IO.GetInt[stream];
            gotRange ← TRUE;
            END
        ELSE
            BEGIN
            IF errorStream # NIL THEN
                IO.PutRope[errorStream, "Missing \">\" in range.\n"];
            RETURN;
            END;
        oldPos ← pos+1;
    
        -- Grab up the postfix (everything in the string after the ">").
        -- Be sure to ignore any backslashes.
    
        WHILE TRUE DO
            pos ← Rope.SkipTo[pattern, oldPos, "\\"];
            postfix ← Rope.Concat[postfix, Rope.Substr[pattern, oldPos, pos-oldPos]];
            IF pos = length THEN EXIT;
            IF pos >= length-1 THEN
                BEGIN
                IF errorStream # NIL THEN
                     IO.PutRope[errorStream, "Can't end pattern in \"\\\"\n."];
                RETURN;
                END;
            postfix ← Rope.Concat[postfix, Rope.Substr[pattern, pos+1, 1]];
            oldPos ← pos+2;
            ENDLOOP;
        END;
        
    WHILE gotAny DO
        
        -- First of all, generate a pattern to test.
        
        IF gotRange THEN
           BEGIN
           pattern ← IO.PutFR["%s%d%s", IO.rope[prefix],
               IO.int[next], IO.rope[postfix]];
           IF next > last THEN next ← next-1
           ELSE IF next < last THEN next ← next+1
           ELSE gotAny ← FALSE;
           END
       ELSE
           BEGIN
           gotAny ← FALSE;
           pattern ← prefix;
           END;
           
       -- Now either look it up or test it against all entries in the table.
       
       IF gotStar THEN
           BEGIN
           entry ← table.firstEntry;
           WHILE entry # NIL DO
               IF (length=0 OR (Rope.Find[entry.name, pattern, 0] >= 0)) AND (entry.clientData # NIL)
                   THEN proc[entry, clientData];
               entry ← entry.nextOverall;
               ENDLOOP;
           END
       ELSE
           BEGIN
           entry ← Find[table, pattern];
           IF entry.clientData # NIL THEN proc[entry, clientData]
           ELSE IF errorStream # NIL THEN
               IO.PutF[errorStream, "%s isn't in table.\n",
                   IO.rope[pattern]];
           END;
       ENDLOOP;
   RETURN;
   EXITS
       quit => RETURN;
   END;


Stats: PUBLIC PROC[table: Table, stream: IO.STREAM] =

    BEGIN
    count: ARRAY[0..10) OF INT;
    overflow: INT ← 0;
    max: INT ← 0;
    j: INT;
    entry: Entry;
    
    FOR i:CARDINAL IN [0..10) DO count[i] ← 0 ENDLOOP;
    FOR i:CARDINAL IN [0..table.buckets.length) DO
        j ← 0;
        entry ← table.buckets[i];
        WHILE entry # NIL DO
            j ← j+1;
            entry ← entry.nextInBucket;
            ENDLOOP;
        IF j < 10 THEN count[j] ← count[j] + 1
        ELSE overflow ← overflow + 1;
        IF j > max THEN max ← j;
        ENDLOOP;
    
    FOR i:CARDINAL IN [0..10) DO
        IO.PutF[stream, "Number of buckets with %d entries: %d.\n",
            IO.int[i], IO.int[count[i]]];
        ENDLOOP;
    IO.PutF[stream, "Number of buckets with > 9 entries: %d.\n",
        IO.int[overflow]];
    IO.PutF[stream, "Largest bucket has %d entries.\n", IO.int[max]];
    END;
    
END.