File : hashtree.ads


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

--                         ADAGIO - ADALID - AENEA.                         --

--                                                                          --

--                            Copyright (C) 2003                            --

--                                 A. Mosteo.                               --

--                                                                          --

--  Authors: A. Mosteo. (adagio@mosteo.com)                                 --

--                                                                          --

--  If you have any questions in regard to this software, please address    --

--  them to the above email.                                                --

--                                                                          --

--  This program 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 of the License, or (at   --

--  your option) any later version.                                         --

--                                                                          --

--  This program 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 this library; if not, write to the Free Software Foundation, --

--  Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.          --

--                                                                          --

--  You are not allowed to use any part of this code to develop a program   --

--  whose output would be used to harass or prosecute other users of the    --

--  networks Adagio connects with. All data collected with Adagio or a tool --

--  containing Adagio code about other network users must remain            --

--  confidential and cannot be made public by any mean, nor be used to      --

--  harass or legally prosecute these users.                                --

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

--  $Id: hashtree.ads,v 1.5 2004/01/21 21:05:44 Jano Exp $


-- Generic computation of trees of hashes.

-- Can be used to implement for example Tiger trees.


with Acf.Types;
use  Acf.Types;

with Ada.Finalization;
with Ada.Streams;
use  Ada.Streams;
use  Ada;

generic
   type Hash_type is private;               -- A final hash.

   type Hash_context is limited private;    -- A hash state holding type.

   -- Initialize a hashing operation:

   with procedure Begin_inner_hash (Context : in out Hash_context);
   -- Finalize a hashing operation:

   with function  End_inner_hash (Context : in Hash_context) return Hash_type;
   -- Add data to hash:

   with procedure Update_inner_hash (
      Context : in out Hash_context;
      Bytes   : in     Byte_array);
   -- Prefix actions for a leaf hash:

   with procedure Start_leaf_hash (Context : in out Hash_context);
   -- Prefix actions for an intermediate hash:

   with procedure Start_intermediate_hash  (Context : in out Hash_context);
   -- Prefix actions for a root hash:

   with procedure Start_root_hash (Context : in out Hash_context);
   -- Converter for hashes:

   with function  To_byte_array (Hash : in Hash_type) return Byte_array;
package HashTree is 

   Default_leaf_size : constant := 1024;

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

   -- Object                                                             --

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

   -- A full HashTree:

   type Object is limited private;

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

   -- Hash_start                                                         --

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

   -- Use these procedures to iteratively build a tree.

   -- An object can be reused.

   procedure Hash_start (
      This      : in out Object; 
      Size      : in     Natural;  -- Of the data to hash

      Leaf_size : in     Natural  := Default_leaf_size;
      Keep      : in     Positive := 10);

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

   -- Hash_update                                                        --

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

   -- Feed some bytes to the tree under construction.

   procedure Hash_update (
      This : in out Object; Bytes : in Acf.Types.Byte_array);

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

   -- Hash_end                                                           --

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

   -- Completes the building of the tree.

   procedure Hash_end (This : in out Object);

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

   -- Root_hash                                                          --

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

   -- Get the root hash:

   function Root_hash (This : in Object) return Hash_type;

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

   -- Hash_as_base32                                                     --

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

   -- Convert a hash to Base32:

   function Hash_as_base32 (Hash : in Hash_type) return String;

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

   -- Get_bytes                                                          --

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

   -- Get the first N levels of tree bytes in breadth first order:

   -- If it has less levels, returns entire tree.

   -- If less levels have been kept, raises Constraint_error.

   function Get_bytes (This : in Object; Levels : in Positive) 
      return Byte_array;

private

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

   -- Types                                                              --

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

   type Coords_type is record
      Row : Positive;
      Col : Positive;
   end record;

   type Node_type;
   type Node_access is access all Node_type;
   type Node_type is record
      Coords      : Coords_type; -- Location in the tree

      Hash        : Hash_type;   -- This node hash

   end record;
   pragma Pack (Node_type);

   type Node_matrix is array (Positive range <>) of Node_access;
   type Node_matrix_access is access all Node_matrix;

   type Object is new Finalization.Limited_controlled with record
      Leaf_size       : Natural := Default_leaf_size;
      Size            : Natural := 0;       -- Of the full data.

      Nodes           : Node_matrix_access; -- Nodes.

      Keep            : Positive;           -- Levels to keep.

      Levels          : Positive;           -- Levels it has.


      -- Temporal things

      Context         : Hash_context;
      Block_remaining : Natural := 0;
      Actual          : Node_access;
   end record;

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

   -- Mix_nodes --

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

   -- Computes the combination of two nodes.

   procedure Mix_nodes (This : in out Object; Left, Right : in Coords_type);

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

   -- Promote_node --

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

   -- Promotes a node which has no sibling to combine with.

   procedure Promote_node (This : in out Object; Left : access Node_type);

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

   -- Destroy                                                            --

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

   -- Disposes all memory used by a tree.

   procedure Destroy (This : in out Object);

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

   -- Finalize                                                           --

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

   procedure Finalize (This : in out Object);

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

   -- Pow2                                                               --

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

   -- Computes quickly a power of 2

   function Pow2 (N : in Natural) return Positive;
   pragma Inline (Pow2);

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

   -- Is_even                                                            --

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

   -- Says if a number is even:

   function Is_even (N : in Natural) return Boolean;

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

   -- Navigation functions                                               --

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

   -- Get the index to a node:

   function Node_at (Coords : in Coords_type)
      return Positive;
   pragma Inline (Node_at);
   -- Get the node:

   function Node_at (This : in Object; Coords : in Coords_type)
      return Node_access;
   pragma Inline (Node_at);
   -- Get parent coordinates:

   function Parent_of (Coords : in Coords_type) return Coords_type;
   pragma Inline (Parent_of);
   -- Get parent node:

   function Parent_of (This : in Object; Node : access Node_type) 
      return Node_access;
   pragma Inline (Parent_of);
   -- Get left child coordinates:

   function Left_child (Coords : in Coords_type) return Coords_type;
   pragma Inline (Left_child);
   -- Get left child node:

   function Left_child (This : in Object; Node : access Node_type)
      return Node_access;
   pragma Inline (Left_child);
   -- Right counterparts

   function Right_child (Coords : in Coords_type) return Coords_type;
   pragma Inline (Right_child);
   function Right_child (This : in Object; Node : access Node_type)
      return Node_access;
   pragma Inline (Right_child);

end HashTree;