------------------------------------------------------------------------------
--                     XML/Ada - An XML suite for Ada95                     --
--                                                                          --
--                     Copyright (C) 2004-2012, AdaCore                     --
--                                                                          --
-- This library is free software;  you can redistribute it and/or modify it --
-- under terms of the  GNU General Public License  as published by the Free --
-- Software  Foundation;  either version 3,  or (at your  option) any later --
-- version. This library is distributed in the hope that it will be useful, --
-- but WITHOUT ANY WARRANTY;  without even the implied warranty of MERCHAN- --
-- TABILITY or FITNESS FOR A PARTICULAR PURPOSE.                            --
--                                                                          --
--                                                                          --
--                                                                          --
--                                                                          --
--                                                                          --
-- You should have received a copy of the GNU General Public License and    --
-- a copy of the GCC Runtime Library Exception along with this program;     --
-- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
-- <http://www.gnu.org/licenses/>.                                          --
--                                                                          --
------------------------------------------------------------------------------

pragma ada_05;

with Interfaces;

generic
   type element is private;
   --  The type of element to be stored

   Empty_Element : element;

   with procedure Free (Elmt : in out element) is null;
   --  Free the memory used by Elmt

   type key (<>) is limited private;
   with function Get_Key (E : element) return key;
   with function Hash (F : key) return Interfaces.Unsigned_32;
   with function Equal (F1, F2 : key) return Boolean;

package Sax.HTable is

   type htable (Size : Interfaces.Unsigned_32) is private;
   type element_ptr is access all element;

   procedure Reset (Hash_Table : in out htable);
   --  Resets the hash table by freeing all the elements

   procedure Set (Hash_Table : in out htable; E : element);
   procedure Set_With_Hash
     (Hash_Table : in out htable;
      E          :        element;
      Hashed     :        Interfaces.Unsigned_32);
   --  Insert the element pointer in the HTable.
   --  The second version is useful if you want to add an element only if it
   --  doesn't exist yet in the table (so a [Get] followed by a [Set], since
   --  you can then compute the hash only once).

   function Get (Hash_Table : htable; K : key) return element;
   function Get_Ptr (Hash_Table : htable; K : key) return element_ptr;
   function Get_Ptr_With_Hash
     (Hash_Table : htable;
      K          : key;
      Hashed     : Interfaces.Unsigned_32) return element_ptr;
   --  Returns the latest inserted element pointer with the given Key
   --  or Empty_Element if none.

   procedure Remove (Hash_Table : in out htable; K : key);
   --  Removes the latest inserted element pointer associated with the
   --  given key if any, does nothing if none.

   generic
      with function Preserve (Elem : element) return Boolean;
   procedure Remove_All (Hash_Table : in out htable);
   --  Remove all elements for which [Preserve] returns False

   type iterator is private;
   No_Iterator : constant iterator;

   function First (Hash_Table : htable) return iterator;
   --  Return the first element in the table
   --  There is no guarantee that 2 calls to this function will return the same
   --  element.

   procedure Next (Hash_Table : htable; Iter : in out iterator);
   --  Move to the next element in the htash table, that hasn't been returned
   --  yet. All the elements in the table will eventually be visited if there
   --  is no call to Set since the call to First.
   --  Iter is set to No_Iterator if there is no more element in the table.

   function Current (Iter : iterator) return element;
   --  Return the element pointed to by Iter

private

   type htable_item;
   type item_ptr is access htable_item;
   type htable_item is record
      Elem : aliased element;
      Next : item_ptr;
   end record;

   type first_item is record
      Elem : aliased element;
      Next : item_ptr;
      Set  : Boolean := False;
   end record;

   type item_array is array (Interfaces.Unsigned_32 range <>) of first_item;
   --  The first element is not an Item_Ptr to save one call to malloc for each
   --  first key in buckets.

   type htable (Size : Interfaces.Unsigned_32) is record
      Table : item_array (1 .. Size);
   end record;

   type iterator is record
      Index : Interfaces.Unsigned_32;
      Elem  : element_ptr;
      Item  : item_ptr;
   end record;

   No_Iterator : constant iterator :=
     (Interfaces.Unsigned_32'last, null, null);
end Sax.HTable;