gcc/ada/libgnat/a-crbltr.ads

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT LIBRARY COMPONENTS                          --
   4 --                                                                          --
   5 --       A D A . C O N T A I N E R S . R E D _ B L A C K _ T R E E S        --
   6 --                                                                          --
   7 --                                 S p e c                                  --
   8 --                                                                          --
   9 --          Copyright (C) 2004-2017, Free Software Foundation, Inc.         --
  10 --                                                                          --
  11 -- GNAT is free software;  you can  redistribute it  and/or modify it under --
  12 -- terms of the  GNU General Public License as published  by the Free Soft- --
  13 -- ware  Foundation;  either version 3,  or (at your option) any later ver- --
  14 -- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
  15 -- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
  16 -- or FITNESS FOR A PARTICULAR PURPOSE.                                     --
  17 --                                                                          --
  18 -- As a special exception under Section 7 of GPL version 3, you are granted --
  19 -- additional permissions described in the GCC Runtime Library Exception,   --
  20 -- version 3.1, as published by the Free Software Foundation.               --
  21 --                                                                          --
  22 -- You should have received a copy of the GNU General Public License and    --
  23 -- a copy of the GCC Runtime Library Exception along with this program;     --
  24 -- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
  25 -- <http://www.gnu.org/licenses/>.                                          --
  26 --                                                                          --
  27 -- This unit was originally developed by Matthew J Heaney.                  --
  28 ------------------------------------------------------------------------------
  29
  30 --  This package declares the tree type used to implement ordered containers
  31
  32 with Ada.Containers.Helpers;
  33
  34 package Ada.Containers.Red_Black_Trees is
  35    pragma Pure;
  36
  37    type Color_Type is (Red, Black);
  38
  39    generic
  40       type Node_Type (<>) is limited private;
  41       type Node_Access is access Node_Type;
  42    package Generic_Tree_Types is
  43
  44       type Tree_Type is tagged record
  45          First  : Node_Access := null;
  46          Last   : Node_Access := null;
  47          Root   : Node_Access := null;
  48          Length : Count_Type := 0;
  49          TC     : aliased Helpers.Tamper_Counts;
  50       end record;
  51
  52       package Implementation is new Helpers.Generic_Implementation;
  53    end Generic_Tree_Types;
  54
  55    generic
  56       type Node_Type is private;
  57    package Generic_Bounded_Tree_Types is
  58       type Nodes_Type is array (Count_Type range <>) of Node_Type;
  59
  60       --  Note that objects of type Tree_Type are logically initialized (in the
  61       --  sense that representation invariants of type are satisfied by dint of
  62       --  default initialization), even without the Nodes component also having
  63       --  its own initialization expression. We only initializae the Nodes
  64       --  component here in order to prevent spurious compiler warnings about
  65       --  the container object not being fully initialized.
  66
  67       type Tree_Type (Capacity : Count_Type) is tagged record
  68          First  : Count_Type := 0;
  69          Last   : Count_Type := 0;
  70          Root   : Count_Type := 0;
  71          Length : Count_Type := 0;
  72          TC     : aliased Helpers.Tamper_Counts;
  73          Free   : Count_Type'Base := -1;
  74          Nodes  : Nodes_Type (1 .. Capacity) := (others => <>);
  75       end record;
  76
  77       package Implementation is new Helpers.Generic_Implementation;
  78    end Generic_Bounded_Tree_Types;
  79
  80 end Ada.Containers.Red_Black_Trees;