------------------------------------------------------------------------------
|
------------------------------------------------------------------------------
|
-- --
|
-- --
|
-- GNAT RUN-TIME COMPONENTS --
|
-- GNAT RUN-TIME COMPONENTS --
|
-- --
|
-- --
|
-- S Y S T E M . H T A B L E --
|
-- S Y S T E M . H T A B L E --
|
-- --
|
-- --
|
-- B o d y --
|
-- B o d y --
|
-- --
|
-- --
|
-- Copyright (C) 1995-2009, AdaCore --
|
-- Copyright (C) 1995-2009, AdaCore --
|
-- --
|
-- --
|
-- GNAT is free software; you can redistribute it and/or modify it under --
|
-- GNAT is free software; you can redistribute it and/or modify it under --
|
-- terms of the GNU General Public License as published by the Free Soft- --
|
-- terms of the GNU General Public License as published by the Free Soft- --
|
-- ware Foundation; either version 2, or (at your option) any later ver- --
|
-- ware Foundation; either version 2, or (at your option) any later ver- --
|
-- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
|
-- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
|
-- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
|
-- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
|
-- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License --
|
-- 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 --
|
-- for more details. You should have received a copy of the GNU General --
|
-- Public License distributed with GNAT; see file COPYING. If not, write --
|
-- Public License distributed with GNAT; see file COPYING. If not, write --
|
-- to the Free Software Foundation, 51 Franklin Street, Fifth Floor, --
|
-- to the Free Software Foundation, 51 Franklin Street, Fifth Floor, --
|
-- Boston, MA 02110-1301, USA. --
|
-- Boston, MA 02110-1301, USA. --
|
-- --
|
-- --
|
-- As a special exception, if other files instantiate generics from this --
|
-- As a special exception, if other files instantiate generics from this --
|
-- unit, or you link this unit with other files to produce an executable, --
|
-- unit, or you link this unit with other files to produce an executable, --
|
-- this unit does not by itself cause the resulting executable to be --
|
-- this unit does not by itself cause the resulting executable to be --
|
-- covered by the GNU General Public License. This exception does not --
|
-- covered by the GNU General Public License. This exception does not --
|
-- however invalidate any other reasons why the executable file might be --
|
-- however invalidate any other reasons why the executable file might be --
|
-- covered by the GNU Public License. --
|
-- covered by the GNU Public License. --
|
-- --
|
-- --
|
-- GNAT was originally developed by the GNAT team at New York University. --
|
-- GNAT was originally developed by the GNAT team at New York University. --
|
-- Extensive contributions were provided by Ada Core Technologies Inc. --
|
-- Extensive contributions were provided by Ada Core Technologies Inc. --
|
-- --
|
-- --
|
------------------------------------------------------------------------------
|
------------------------------------------------------------------------------
|
|
|
pragma Compiler_Unit;
|
pragma Compiler_Unit;
|
|
|
with Ada.Unchecked_Deallocation;
|
with Ada.Unchecked_Deallocation;
|
with System.String_Hash;
|
with System.String_Hash;
|
|
|
package body System.HTable is
|
package body System.HTable is
|
|
|
-------------------
|
-------------------
|
-- Static_HTable --
|
-- Static_HTable --
|
-------------------
|
-------------------
|
|
|
package body Static_HTable is
|
package body Static_HTable is
|
|
|
Table : array (Header_Num) of Elmt_Ptr;
|
Table : array (Header_Num) of Elmt_Ptr;
|
|
|
Iterator_Index : Header_Num;
|
Iterator_Index : Header_Num;
|
Iterator_Ptr : Elmt_Ptr;
|
Iterator_Ptr : Elmt_Ptr;
|
Iterator_Started : Boolean := False;
|
Iterator_Started : Boolean := False;
|
|
|
function Get_Non_Null return Elmt_Ptr;
|
function Get_Non_Null return Elmt_Ptr;
|
-- Returns Null_Ptr if Iterator_Started is false or the Table is empty.
|
-- Returns Null_Ptr if Iterator_Started is false or the Table is empty.
|
-- Returns Iterator_Ptr if non null, or the next non null element in
|
-- Returns Iterator_Ptr if non null, or the next non null element in
|
-- table if any.
|
-- table if any.
|
|
|
---------
|
---------
|
-- Get --
|
-- Get --
|
---------
|
---------
|
|
|
function Get (K : Key) return Elmt_Ptr is
|
function Get (K : Key) return Elmt_Ptr is
|
Elmt : Elmt_Ptr;
|
Elmt : Elmt_Ptr;
|
|
|
begin
|
begin
|
Elmt := Table (Hash (K));
|
Elmt := Table (Hash (K));
|
|
|
loop
|
loop
|
if Elmt = Null_Ptr then
|
if Elmt = Null_Ptr then
|
return Null_Ptr;
|
return Null_Ptr;
|
|
|
elsif Equal (Get_Key (Elmt), K) then
|
elsif Equal (Get_Key (Elmt), K) then
|
return Elmt;
|
return Elmt;
|
|
|
else
|
else
|
Elmt := Next (Elmt);
|
Elmt := Next (Elmt);
|
end if;
|
end if;
|
end loop;
|
end loop;
|
end Get;
|
end Get;
|
|
|
---------------
|
---------------
|
-- Get_First --
|
-- Get_First --
|
---------------
|
---------------
|
|
|
function Get_First return Elmt_Ptr is
|
function Get_First return Elmt_Ptr is
|
begin
|
begin
|
Iterator_Started := True;
|
Iterator_Started := True;
|
Iterator_Index := Table'First;
|
Iterator_Index := Table'First;
|
Iterator_Ptr := Table (Iterator_Index);
|
Iterator_Ptr := Table (Iterator_Index);
|
return Get_Non_Null;
|
return Get_Non_Null;
|
end Get_First;
|
end Get_First;
|
|
|
--------------
|
--------------
|
-- Get_Next --
|
-- Get_Next --
|
--------------
|
--------------
|
|
|
function Get_Next return Elmt_Ptr is
|
function Get_Next return Elmt_Ptr is
|
begin
|
begin
|
if not Iterator_Started then
|
if not Iterator_Started then
|
return Null_Ptr;
|
return Null_Ptr;
|
end if;
|
end if;
|
|
|
Iterator_Ptr := Next (Iterator_Ptr);
|
Iterator_Ptr := Next (Iterator_Ptr);
|
return Get_Non_Null;
|
return Get_Non_Null;
|
end Get_Next;
|
end Get_Next;
|
|
|
------------------
|
------------------
|
-- Get_Non_Null --
|
-- Get_Non_Null --
|
------------------
|
------------------
|
|
|
function Get_Non_Null return Elmt_Ptr is
|
function Get_Non_Null return Elmt_Ptr is
|
begin
|
begin
|
while Iterator_Ptr = Null_Ptr loop
|
while Iterator_Ptr = Null_Ptr loop
|
if Iterator_Index = Table'Last then
|
if Iterator_Index = Table'Last then
|
Iterator_Started := False;
|
Iterator_Started := False;
|
return Null_Ptr;
|
return Null_Ptr;
|
end if;
|
end if;
|
|
|
Iterator_Index := Iterator_Index + 1;
|
Iterator_Index := Iterator_Index + 1;
|
Iterator_Ptr := Table (Iterator_Index);
|
Iterator_Ptr := Table (Iterator_Index);
|
end loop;
|
end loop;
|
|
|
return Iterator_Ptr;
|
return Iterator_Ptr;
|
end Get_Non_Null;
|
end Get_Non_Null;
|
|
|
------------
|
------------
|
-- Remove --
|
-- Remove --
|
------------
|
------------
|
|
|
procedure Remove (K : Key) is
|
procedure Remove (K : Key) is
|
Index : constant Header_Num := Hash (K);
|
Index : constant Header_Num := Hash (K);
|
Elmt : Elmt_Ptr;
|
Elmt : Elmt_Ptr;
|
Next_Elmt : Elmt_Ptr;
|
Next_Elmt : Elmt_Ptr;
|
|
|
begin
|
begin
|
Elmt := Table (Index);
|
Elmt := Table (Index);
|
|
|
if Elmt = Null_Ptr then
|
if Elmt = Null_Ptr then
|
return;
|
return;
|
|
|
elsif Equal (Get_Key (Elmt), K) then
|
elsif Equal (Get_Key (Elmt), K) then
|
Table (Index) := Next (Elmt);
|
Table (Index) := Next (Elmt);
|
|
|
else
|
else
|
loop
|
loop
|
Next_Elmt := Next (Elmt);
|
Next_Elmt := Next (Elmt);
|
|
|
if Next_Elmt = Null_Ptr then
|
if Next_Elmt = Null_Ptr then
|
return;
|
return;
|
|
|
elsif Equal (Get_Key (Next_Elmt), K) then
|
elsif Equal (Get_Key (Next_Elmt), K) then
|
Set_Next (Elmt, Next (Next_Elmt));
|
Set_Next (Elmt, Next (Next_Elmt));
|
return;
|
return;
|
|
|
else
|
else
|
Elmt := Next_Elmt;
|
Elmt := Next_Elmt;
|
end if;
|
end if;
|
end loop;
|
end loop;
|
end if;
|
end if;
|
end Remove;
|
end Remove;
|
|
|
-----------
|
-----------
|
-- Reset --
|
-- Reset --
|
-----------
|
-----------
|
|
|
procedure Reset is
|
procedure Reset is
|
begin
|
begin
|
for J in Table'Range loop
|
for J in Table'Range loop
|
Table (J) := Null_Ptr;
|
Table (J) := Null_Ptr;
|
end loop;
|
end loop;
|
end Reset;
|
end Reset;
|
|
|
---------
|
---------
|
-- Set --
|
-- Set --
|
---------
|
---------
|
|
|
procedure Set (E : Elmt_Ptr) is
|
procedure Set (E : Elmt_Ptr) is
|
Index : Header_Num;
|
Index : Header_Num;
|
|
|
begin
|
begin
|
Index := Hash (Get_Key (E));
|
Index := Hash (Get_Key (E));
|
Set_Next (E, Table (Index));
|
Set_Next (E, Table (Index));
|
Table (Index) := E;
|
Table (Index) := E;
|
end Set;
|
end Set;
|
|
|
end Static_HTable;
|
end Static_HTable;
|
|
|
-------------------
|
-------------------
|
-- Simple_HTable --
|
-- Simple_HTable --
|
-------------------
|
-------------------
|
|
|
package body Simple_HTable is
|
package body Simple_HTable is
|
|
|
type Element_Wrapper;
|
type Element_Wrapper;
|
type Elmt_Ptr is access all Element_Wrapper;
|
type Elmt_Ptr is access all Element_Wrapper;
|
type Element_Wrapper is record
|
type Element_Wrapper is record
|
K : Key;
|
K : Key;
|
E : Element;
|
E : Element;
|
Next : Elmt_Ptr;
|
Next : Elmt_Ptr;
|
end record;
|
end record;
|
|
|
procedure Free is new
|
procedure Free is new
|
Ada.Unchecked_Deallocation (Element_Wrapper, Elmt_Ptr);
|
Ada.Unchecked_Deallocation (Element_Wrapper, Elmt_Ptr);
|
|
|
procedure Set_Next (E : Elmt_Ptr; Next : Elmt_Ptr);
|
procedure Set_Next (E : Elmt_Ptr; Next : Elmt_Ptr);
|
function Next (E : Elmt_Ptr) return Elmt_Ptr;
|
function Next (E : Elmt_Ptr) return Elmt_Ptr;
|
function Get_Key (E : Elmt_Ptr) return Key;
|
function Get_Key (E : Elmt_Ptr) return Key;
|
|
|
package Tab is new Static_HTable (
|
package Tab is new Static_HTable (
|
Header_Num => Header_Num,
|
Header_Num => Header_Num,
|
Element => Element_Wrapper,
|
Element => Element_Wrapper,
|
Elmt_Ptr => Elmt_Ptr,
|
Elmt_Ptr => Elmt_Ptr,
|
Null_Ptr => null,
|
Null_Ptr => null,
|
Set_Next => Set_Next,
|
Set_Next => Set_Next,
|
Next => Next,
|
Next => Next,
|
Key => Key,
|
Key => Key,
|
Get_Key => Get_Key,
|
Get_Key => Get_Key,
|
Hash => Hash,
|
Hash => Hash,
|
Equal => Equal);
|
Equal => Equal);
|
|
|
---------
|
---------
|
-- Get --
|
-- Get --
|
---------
|
---------
|
|
|
function Get (K : Key) return Element is
|
function Get (K : Key) return Element is
|
Tmp : constant Elmt_Ptr := Tab.Get (K);
|
Tmp : constant Elmt_Ptr := Tab.Get (K);
|
begin
|
begin
|
if Tmp = null then
|
if Tmp = null then
|
return No_Element;
|
return No_Element;
|
else
|
else
|
return Tmp.E;
|
return Tmp.E;
|
end if;
|
end if;
|
end Get;
|
end Get;
|
|
|
---------------
|
---------------
|
-- Get_First --
|
-- Get_First --
|
---------------
|
---------------
|
|
|
function Get_First return Element is
|
function Get_First return Element is
|
Tmp : constant Elmt_Ptr := Tab.Get_First;
|
Tmp : constant Elmt_Ptr := Tab.Get_First;
|
begin
|
begin
|
if Tmp = null then
|
if Tmp = null then
|
return No_Element;
|
return No_Element;
|
else
|
else
|
return Tmp.E;
|
return Tmp.E;
|
end if;
|
end if;
|
end Get_First;
|
end Get_First;
|
|
|
-------------
|
-------------
|
-- Get_Key --
|
-- Get_Key --
|
-------------
|
-------------
|
|
|
function Get_Key (E : Elmt_Ptr) return Key is
|
function Get_Key (E : Elmt_Ptr) return Key is
|
begin
|
begin
|
return E.K;
|
return E.K;
|
end Get_Key;
|
end Get_Key;
|
|
|
--------------
|
--------------
|
-- Get_Next --
|
-- Get_Next --
|
--------------
|
--------------
|
|
|
function Get_Next return Element is
|
function Get_Next return Element is
|
Tmp : constant Elmt_Ptr := Tab.Get_Next;
|
Tmp : constant Elmt_Ptr := Tab.Get_Next;
|
begin
|
begin
|
if Tmp = null then
|
if Tmp = null then
|
return No_Element;
|
return No_Element;
|
else
|
else
|
return Tmp.E;
|
return Tmp.E;
|
end if;
|
end if;
|
end Get_Next;
|
end Get_Next;
|
|
|
----------
|
----------
|
-- Next --
|
-- Next --
|
----------
|
----------
|
|
|
function Next (E : Elmt_Ptr) return Elmt_Ptr is
|
function Next (E : Elmt_Ptr) return Elmt_Ptr is
|
begin
|
begin
|
return E.Next;
|
return E.Next;
|
end Next;
|
end Next;
|
|
|
------------
|
------------
|
-- Remove --
|
-- Remove --
|
------------
|
------------
|
|
|
procedure Remove (K : Key) is
|
procedure Remove (K : Key) is
|
Tmp : Elmt_Ptr;
|
Tmp : Elmt_Ptr;
|
|
|
begin
|
begin
|
Tmp := Tab.Get (K);
|
Tmp := Tab.Get (K);
|
|
|
if Tmp /= null then
|
if Tmp /= null then
|
Tab.Remove (K);
|
Tab.Remove (K);
|
Free (Tmp);
|
Free (Tmp);
|
end if;
|
end if;
|
end Remove;
|
end Remove;
|
|
|
-----------
|
-----------
|
-- Reset --
|
-- Reset --
|
-----------
|
-----------
|
|
|
procedure Reset is
|
procedure Reset is
|
E1, E2 : Elmt_Ptr;
|
E1, E2 : Elmt_Ptr;
|
|
|
begin
|
begin
|
E1 := Tab.Get_First;
|
E1 := Tab.Get_First;
|
while E1 /= null loop
|
while E1 /= null loop
|
E2 := Tab.Get_Next;
|
E2 := Tab.Get_Next;
|
Free (E1);
|
Free (E1);
|
E1 := E2;
|
E1 := E2;
|
end loop;
|
end loop;
|
|
|
Tab.Reset;
|
Tab.Reset;
|
end Reset;
|
end Reset;
|
|
|
---------
|
---------
|
-- Set --
|
-- Set --
|
---------
|
---------
|
|
|
procedure Set (K : Key; E : Element) is
|
procedure Set (K : Key; E : Element) is
|
Tmp : constant Elmt_Ptr := Tab.Get (K);
|
Tmp : constant Elmt_Ptr := Tab.Get (K);
|
begin
|
begin
|
if Tmp = null then
|
if Tmp = null then
|
Tab.Set (new Element_Wrapper'(K, E, null));
|
Tab.Set (new Element_Wrapper'(K, E, null));
|
else
|
else
|
Tmp.E := E;
|
Tmp.E := E;
|
end if;
|
end if;
|
end Set;
|
end Set;
|
|
|
--------------
|
--------------
|
-- Set_Next --
|
-- Set_Next --
|
--------------
|
--------------
|
|
|
procedure Set_Next (E : Elmt_Ptr; Next : Elmt_Ptr) is
|
procedure Set_Next (E : Elmt_Ptr; Next : Elmt_Ptr) is
|
begin
|
begin
|
E.Next := Next;
|
E.Next := Next;
|
end Set_Next;
|
end Set_Next;
|
end Simple_HTable;
|
end Simple_HTable;
|
|
|
----------
|
----------
|
-- Hash --
|
-- Hash --
|
----------
|
----------
|
|
|
function Hash (Key : String) return Header_Num is
|
function Hash (Key : String) return Header_Num is
|
type Uns is mod 2 ** 32;
|
type Uns is mod 2 ** 32;
|
|
|
function Hash_Fun is
|
function Hash_Fun is
|
new System.String_Hash.Hash (Character, String, Uns);
|
new System.String_Hash.Hash (Character, String, Uns);
|
|
|
begin
|
begin
|
return Header_Num'First +
|
return Header_Num'First +
|
Header_Num'Base (Hash_Fun (Key) mod Header_Num'Range_Length);
|
Header_Num'Base (Hash_Fun (Key) mod Header_Num'Range_Length);
|
end Hash;
|
end Hash;
|
|
|
end System.HTable;
|
end System.HTable;
|
|
|
