From e857941acd16e3a678296b26e34b4bf330d5239c Mon Sep 17 00:00:00 2001
From: Tristan Gingold <tgingold@free.fr>
Date: Sat, 27 Apr 2019 10:14:26 +0200
Subject: vhdl: supports VHPIDIRECT in mcode backend.

src: add hash.ad[sb], interning.ad[sb]
Automatically link with vhpidirect libraries.
---
 src/interning.adb | 140 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 140 insertions(+)
 create mode 100644 src/interning.adb

(limited to 'src/interning.adb')

diff --git a/src/interning.adb b/src/interning.adb
new file mode 100644
index 000000000..66aedf903
--- /dev/null
+++ b/src/interning.adb
@@ -0,0 +1,140 @@
+--  Type interning - set of unique objects.
+--  Copyright (C) 2019 Tristan Gingold
+--
+--  GHDL is free software; you can redistribute it and/or modify it under
+--  the terms of the GNU General Public License as published by the Free
+--  Software Foundation; either version 2, or (at your option) any later
+--  version.
+--
+--  GHDL is distributed in the hope that it will be useful, but WITHOUT ANY
+--  WARRANTY; without even the implied warranty of MERCHANTABILITY or
+--  FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+--  for more details.
+--
+--  You should have received a copy of the GNU General Public License
+--  along with GHDL; see the file COPYING.  If not, write to the Free
+--  Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+--  02111-1307, USA.
+
+with Ada.Unchecked_Deallocation;
+with Dyn_Tables;
+
+package body Interning is
+   type Element_Wrapper is record
+      Hash : Hash_Value_Type;
+      Next : Index_Type;
+      Obj  : Object_Type;
+   end record;
+
+   package Wrapper_Tables is new Dyn_Tables
+     (Table_Index_Type => Index_Type,
+      Table_Component_Type => Element_Wrapper,
+      Table_Low_Bound => No_Index + 1,
+      Table_Initial => 128);
+
+   type Hash_Array is array (Hash_Value_Type range <>) of Index_Type;
+   type Hash_Array_Acc is access Hash_Array;
+
+   Initial_Size : constant Hash_Value_Type := 1024;
+
+   Size : Hash_Value_Type;
+   Hash_Table : Hash_Array_Acc;
+   Els : Wrapper_Tables.Instance;
+
+   procedure Deallocate is new Ada.Unchecked_Deallocation
+     (Hash_Array, Hash_Array_Acc);
+
+   procedure Init is
+   begin
+      Size := Initial_Size;
+      Hash_Table := new Hash_Array'(0 .. Initial_Size - 1 => No_Index);
+      Wrapper_Tables.Init (Els);
+      pragma Assert (Wrapper_Tables.Last (Els) = No_Index);
+   end Init;
+
+   --  Expand the hash table (double the size).
+   procedure Expand
+   is
+      Old_Hash_Table : Hash_Array_Acc;
+      Idx : Index_Type;
+   begin
+      Old_Hash_Table := Hash_Table;
+      Size := Size * 2;
+      Hash_Table := new Hash_Array'(0 .. Size - 1 => No_Index);
+
+      --  Rehash.
+      for I in Old_Hash_Table'Range loop
+         Idx := Old_Hash_Table (I);
+         while Idx /= No_Index loop
+            --  Note: collisions are put in reverse order.
+            declare
+               Ent : Element_Wrapper renames Els.Table (Idx);
+               Hash_Index : constant Hash_Value_Type :=
+                 Ent.Hash and (Size - 1);
+               Next_Idx : constant Index_Type := Ent.Next;
+            begin
+               Ent.Next := Hash_Table (Hash_Index);
+               Hash_Table (Hash_Index) := Idx;
+               Idx := Next_Idx;
+            end;
+         end loop;
+      end loop;
+
+      Deallocate (Old_Hash_Table);
+   end Expand;
+
+   function Get (Params : Params_Type) return Object_Type
+   is
+      Hash_Value : Hash_Value_Type;
+      Hash_Index : Hash_Value_Type;
+      Idx : Index_Type;
+      Res : Object_Type;
+   begin
+      --  Check if the package was initialized.
+      pragma Assert (Hash_Table /= null);
+
+      Hash_Value := Hash (Params);
+      Hash_Index := Hash_Value and (Size - 1);
+
+      Idx := Hash_Table (Hash_Index);
+      while Idx /= No_Index loop
+         declare
+            E : Element_Wrapper renames Els.Table (Idx);
+         begin
+            if E.Hash = Hash_Value and then Equal (E.Obj, Params) then
+               return E.Obj;
+            end if;
+            Idx := E.Next;
+         end;
+      end loop;
+
+      --  Maybe expand the table.
+      if Hash_Value_Type (Wrapper_Tables.Last (Els)) > 2 * Size then
+         Expand;
+
+         --  Recompute hash index.
+         Hash_Index := Hash_Value and (Size - 1);
+      end if;
+
+      Res := Build (Params);
+
+      --  Insert.
+      Wrapper_Tables.Append (Els,
+                             (Hash => Hash_Value,
+                              Next => Hash_Table (Hash_Index),
+                              Obj => Res));
+      Hash_Table (Hash_Index) := Wrapper_Tables.Last (Els);
+      return Res;
+   end Get;
+
+   function Last_Index return Index_Type is
+   begin
+      return Wrapper_Tables.Last (Els);
+   end Last_Index;
+
+   function Get_By_Index (Index : Index_Type) return Object_Type is
+   begin
+      pragma Assert (Index <= Wrapper_Tables.Last (Els));
+      return Els.Table (Index).Obj;
+   end Get_By_Index;
+end Interning;
-- 
cgit v1.2.3