MODULE HashText;

(***************************************************************************)
(*                      Copyright (C) Olivetti 1989                        *)
(*                          All Rights reserved                            *)
(*                                                                         *)
(* Use and copy of this software and preparation of derivative works based *)
(* upon this software are permitted to any person, provided this same      *)
(* copyright notice and the following Olivetti warranty disclaimer are     *) 
(* included in any copy of the software or any modification thereof or     *)
(* derivative work therefrom made by any person.                           *)
(*                                                                         *)
(* This software is made available AS IS and Olivetti disclaims all        *)
(* warranties with respect to this software, whether expressed or implied  *)
(* under any law, including all implied warranties of merchantibility and  *)
(* fitness for any purpose. In no event shall Olivetti be liable for any   *)
(* damages whatsoever resulting from loss of use, data or profits or       *)
(* otherwise arising out of or in connection with the use or performance   *)
(* of this software.                                                       *)
(***************************************************************************)

(*
  This version uses a table of linked lists (chained overflow).
  The computed hash val of linked lists (chained overflow).
  The computed hash val identifies a table entry which is the
  head of one of the linked lists. An object entered in the hashtable
  is identified by the address of the record element in the list.
*)

IMPORT Text, CharType, Thread;
IMPORT TextExtras;


REVEAL
  Id = BRANDED OBJECT
    next: Id;
    t: Text.T;
    val: REFANY;
  END;

  Table = Thread.Mutex BRANDED OBJECT
    size: CARDINAL;
    caseInsensitive: BOOLEAN := FALSE;
    ids: REF ARRAY OF Id := NIL;
    generation := FIRST(INTEGER);
  END;


CONST
  DefaultSize = 4096;


PROCEDURE New(s: CARDINAL := 0): Table RAISES {} =
  VAR  
    ht := NEW(Table);
  BEGIN
    IF s = 0 THEN s := DefaultSize END;
    ht.size := s;
    ht.ids := NEW(REF ARRAY OF Id, s);
    FOR i := 0 TO LAST(ht.ids^) DO ht.ids[i] := NIL END;
    RETURN ht;
  END New;


PROCEDURE CINew(s: CARDINAL): Table RAISES {} =
  VAR
    ht := New(s);
  BEGIN
    ht.caseInsensitive := TRUE;
    RETURN ht;
  END CINew;


PROCEDURE HashVal(t: Text.T;  caseInsensitive: BOOLEAN): CARDINAL RAISES {}=
  VAR  
    pos, sum, sumOfSums, length: CARDINAL;
    ch: CHAR;       
  BEGIN
    pos := 0; sum := 0; sumOfSums := 0;
    length := Text.Length(t);
    WHILE pos < length DO
      ch := Text.GetChar(t, pos); INC(pos);
      IF caseInsensitive THEN ch := CharType.ToLower(ch) END;
      INC(sum, ORD(ch));  INC(sumOfSums, sum);
    END;
    RETURN sumOfSums;
  END HashVal;


PROCEDURE Find(
    t: Text.T;
    list: Id;
    caseInsensitive: BOOLEAN;
    VAR h: Id)
    : BOOLEAN
    RAISES {}=
  BEGIN
    WHILE list # NIL DO
      IF caseInsensitive THEN
        IF TextExtras.CIEqual(t, list.t) THEN h := list; RETURN TRUE END;
      ELSE
        IF Text.Equal(t, list.t) THEN h := list; RETURN TRUE END;
      END;
      list := list.next;
    END;
    RETURN FALSE;
  END Find;

PROCEDURE Enter(ht: Table; t: Text.T; VAR h: Id): BOOLEAN RAISES {} =
  BEGIN
    WITH start = ht.ids[HashVal(t, ht.caseInsensitive) MOD ht.size] DO
      IF Find(t, start, ht.caseInsensitive, h) THEN
        RETURN FALSE;
      ELSE
        INC(ht.generation);
        h := NEW(Id, t := t, next := start);
        start := h;
        RETURN TRUE;
      END;
    END;
  END Enter;


PROCEDURE Lookup(ht: Table; t: Text.T; VAR h: Id): BOOLEAN RAISES {} =
  BEGIN
    WITH start = ht.ids[HashVal(t, ht.caseInsensitive) MOD ht.size] DO
      RETURN Find(t, start, ht.caseInsensitive, h);
    END;
  END Lookup;


<*INLINE*> PROCEDURE Associate(ht: Table; h: Id; w: REFANY) RAISES {} =
  BEGIN
    h.val := w;
  END Associate;


<*INLINE*> PROCEDURE Value(ht: Table; h: Id): REFANY RAISES {} =
  BEGIN
    RETURN h.val;
  END Value;


<*INLINE*> PROCEDURE Key(ht: Table; h: Id): Text.T RAISES {} =
  BEGIN
    RETURN h.t;
  END Key;


PROCEDURE Remove(ht: Table; h: Id) RAISES {}=
  BEGIN
    INC(ht.generation);
    WITH start = ht.ids[HashVal(h.t, ht.caseInsensitive) MOD ht.size] DO
      IF start = h THEN
        start := h.next;
      ELSE
        VAR
          prev := start;
        BEGIN
          LOOP
            VAR
              search := prev.next;
            BEGIN
              IF search = h THEN prev.next := search.next; EXIT END;
              prev := search;
            END;
          END;
        END;
      END;
    END;
  END Remove;


(* Iterator *)

REVEAL
  Iter = BRANDED OBJECT
    table: Table;
    index: CARDINAL := 0;
    id: Id;
    generation: INTEGER;
  END;


PROCEDURE NewIterator(table: Table): Iter RAISES {} =
  BEGIN
    RETURN NEW(Iter,
        table := table,
        id := table.ids[0],
        generation := table.generation);
  END NewIterator;


PROCEDURE Next(
    iter: Iter;
    VAR (*out*) key: TEXT;
    VAR (*out*) val: REFANY)
    : BOOLEAN
    RAISES {Broken} =
  VAR
    table := iter.table;
  BEGIN
    IF iter.generation # table.generation THEN RAISE Broken END;
    WITH id = iter.id DO
      IF id = NIL THEN
        WITH index = iter.index, ids = table.ids, last = LAST(ids^) DO
          REPEAT 
            IF index >= last THEN RETURN FALSE END;
            INC(index);
            id := ids[index];
          UNTIL id # NIL;
        END;
      END;
      key := id.t;
      val := id.val;
      id := id.next;
      RETURN TRUE;
    END;
  END Next;


BEGIN
END HashText.