LIBRARY IEEE;
USE IEEE.std_logic_1164.ALL;

-------------------------------------------------------------------------

PACKAGE AssociativePackage IS    

  CONSTANT DataSize : INTEGER := 16;
  CONSTANT HashConstant : INTEGER := 4;

  SUBTYPE DataType IS std_logic_vector (DataSize-1 DOWNTO 0);
  
  TYPE DataNode;
  TYPE DataNodePtr IS ACCESS DataNode;
  TYPE DataNode IS RECORD
    data   : DataType;
    link   : DataNodePtr;   
  END RECORD;
 
  TYPE TableType IS ARRAY (NATURAL RANGE <>) OF DataNodePtr; 

  PROCEDURE AssociativeSearch (VARIABLE table_t : IN TableType; wanted : IN DataType; place : OUT DataNodePtr);
  PROCEDURE Add2Table (table : INOUT TableType; DataAdded : IN DataType);
   
END AssociativePackage;

--------------------------------------------------------------------------

PACKAGE BODY AssociativePackage IS                                    

--------------------------------------------------------------------------

 FUNCTION std_logic2int (stdin : IN std_logic_vector) RETURN INTEGER IS

    VARIABLE result : INTEGER;

  BEGIN

    result := 0;

    FOR i IN stdin'RIGHT TO stdin'LEFT LOOP
      IF stdin(i) = '1' THEN
        result := result + 2**(i-stdin'RIGHT);
      END IF;
    END LOOP;

    RETURN result;

  END std_logic2int;

---------------------------------------------------------------------------

  FUNCTION hash (DataIn : IN std_logic_vector) RETURN INTEGER IS
  BEGIN                  
    RETURN (std_logic2int(DataIn) MOD HashConstant); 
  END hash;                      

---------------------------------------------------------------------------

  PROCEDURE thenext (VARIABLE ptr : IN DataNodePtr; output : OUT DataNodePtr) IS
  BEGIN   
    output := ptr.link;
  END thenext;

---------------------------------------------------------------------------

  PROCEDURE AssociativeSearch (VARIABLE table_t : IN TableType; wanted : IN DataType; place : OUT DataNodePtr) IS
    VARIABLE i : INTEGER;
    VARIABLE temp : DataNodePtr;          
  --  Variable justfortest : TableType(table_t'range);
    VARIABLE found : BOOLEAN := FALSE;
  BEGIN       
  --  justfortest := table_t;
    i := hash(wanted);
    temp := table_t(i);
    WHILE NOT found LOOP
      IF temp.data /= wanted THEN
        thenext(temp, temp);
        IF temp=NULL THEN  
          -- the item is not found
          EXIT;
        END IF;
      ELSE            
        found := TRUE;
      END IF;
    END LOOP;
    place := temp;
  END AssociativeSearch;

----------------------------------------------------------------------------  

  PROCEDURE Add2Table (table : INOUT TableType; DataAdded : IN DataType) IS
    VARIABLE i : INTEGER;
    VARIABLE temp : DataNodePtr;
  BEGIN                  
    i := hash(DataAdded);
    temp := table(i);
    table(i) := NEW DataNode;
    table(i).link := temp;
  END Add2Table;

END AssociativePackage;