1------------------------------------------------------------------------------ 2-- -- 3-- GNAT LIBRARY COMPONENTS -- 4-- -- 5-- ADA.CONTAINERS.HASH_TABLES.GENERIC_OPERATIONS -- 6-- -- 7-- S p e c -- 8-- -- 9-- Copyright (C) 2004-2013, 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-- Hash_Table_Type is used to implement hashed containers. This package 31-- declares hash-table operations that do not depend on keys. 32 33with Ada.Streams; 34 35generic 36 37 with package HT_Types is 38 new Generic_Hash_Table_Types (<>); 39 40 use HT_Types; 41 42 with function Hash_Node (Node : Node_Access) return Hash_Type; 43 44 with function Next (Node : Node_Access) return Node_Access; 45 46 with procedure Set_Next 47 (Node : Node_Access; 48 Next : Node_Access); 49 50 with function Copy_Node (Source : Node_Access) return Node_Access; 51 52 with procedure Free (X : in out Node_Access); 53 54package Ada.Containers.Hash_Tables.Generic_Operations is 55 pragma Preelaborate; 56 57 procedure Free_Hash_Table (Buckets : in out Buckets_Access); 58 -- First frees the nodes in all non-null buckets of Buckets, and then frees 59 -- the Buckets array itself. 60 61 function Index 62 (Buckets : Buckets_Type; 63 Node : Node_Access) return Hash_Type; 64 pragma Inline (Index); 65 -- Uses the hash value of Node to compute its Buckets array index 66 67 function Index 68 (Hash_Table : Hash_Table_Type; 69 Node : Node_Access) return Hash_Type; 70 pragma Inline (Index); 71 -- Uses the hash value of Node to compute its Hash_Table buckets array 72 -- index. 73 74 function Checked_Index 75 (Hash_Table : aliased in out Hash_Table_Type; 76 Buckets : Buckets_Type; 77 Node : Node_Access) return Hash_Type; 78 -- Calls Index, but also locks and unlocks the container, per AI05-0022, in 79 -- order to detect element tampering by the generic actual Hash function. 80 81 function Checked_Index 82 (Hash_Table : aliased in out Hash_Table_Type; 83 Node : Node_Access) return Hash_Type; 84 -- Calls Checked_Index using Hash_Table's buckets array. 85 86 procedure Adjust (HT : in out Hash_Table_Type); 87 -- Used to implement controlled Adjust. It is assumed that HT has the value 88 -- of the bit-wise copy that immediately follows controlled Finalize. 89 -- Adjust first allocates a new buckets array for HT (having the same 90 -- length as the source), and then allocates a copy of each node of source. 91 92 procedure Finalize (HT : in out Hash_Table_Type); 93 -- Used to implement controlled Finalize. It first calls Clear to 94 -- deallocate any remaining nodes, and then deallocates the buckets array. 95 96 generic 97 with function Find 98 (HT : Hash_Table_Type; 99 Key : Node_Access) return Boolean; 100 function Generic_Equal 101 (L, R : Hash_Table_Type) return Boolean; 102 -- Used to implement hashed container equality. For each node in hash table 103 -- L, it calls Find to search for an equivalent item in hash table R. If 104 -- Find returns False for any node then Generic_Equal terminates 105 -- immediately and returns False. Otherwise if Find returns True for every 106 -- node then Generic_Equal returns True. 107 108 procedure Clear (HT : in out Hash_Table_Type); 109 -- Deallocates each node in hash table HT. (Note that it only deallocates 110 -- the nodes, not the buckets array.) Program_Error is raised if the hash 111 -- table is busy. 112 113 procedure Move (Target, Source : in out Hash_Table_Type); 114 -- Moves (not copies) the buckets array and nodes from Source to 115 -- Target. Program_Error is raised if Source is busy. The Target is first 116 -- cleared to deallocate its nodes (implying that Program_Error is also 117 -- raised if Target is busy). Source is empty following the move. 118 119 function Capacity (HT : Hash_Table_Type) return Count_Type; 120 -- Returns the length of the buckets array 121 122 procedure Reserve_Capacity 123 (HT : in out Hash_Table_Type; 124 N : Count_Type); 125 -- If N is greater than the current capacity, then it expands the buckets 126 -- array to at least the value N. If N is less than the current capacity, 127 -- then it contracts the buckets array. In either case existing nodes are 128 -- rehashed onto the new buckets array, and the old buckets array is 129 -- deallocated. Program_Error is raised if the hash table is busy. 130 131 procedure Delete_Node_Sans_Free 132 (HT : in out Hash_Table_Type; 133 X : Node_Access); 134 -- Removes node X from the hash table without deallocating the node 135 136 function First (HT : Hash_Table_Type) return Node_Access; 137 -- Returns the head of the list in the first (lowest-index) non-empty 138 -- bucket. 139 140 function Next 141 (HT : aliased in out Hash_Table_Type; 142 Node : Node_Access) return Node_Access; 143 -- Returns the node that immediately follows Node. This corresponds to 144 -- either the next node in the same bucket, or (if Node is the last node in 145 -- its bucket) the head of the list in the first non-empty bucket that 146 -- follows. 147 148 generic 149 with procedure Process (Node : Node_Access); 150 procedure Generic_Iteration (HT : Hash_Table_Type); 151 -- Calls Process for each node in hash table HT 152 153 generic 154 use Ada.Streams; 155 with procedure Write 156 (Stream : not null access Root_Stream_Type'Class; 157 Node : Node_Access); 158 procedure Generic_Write 159 (Stream : not null access Root_Stream_Type'Class; 160 HT : Hash_Table_Type); 161 -- Used to implement the streaming attribute for hashed containers. It 162 -- calls Write for each node to write its value into Stream. 163 164 generic 165 use Ada.Streams; 166 with function New_Node (Stream : not null access Root_Stream_Type'Class) 167 return Node_Access; 168 procedure Generic_Read 169 (Stream : not null access Root_Stream_Type'Class; 170 HT : out Hash_Table_Type); 171 -- Used to implement the streaming attribute for hashed containers. It 172 -- first clears hash table HT, then populates the hash table by calling 173 -- New_Node for each item in Stream. 174 175 function New_Buckets (Length : Hash_Type) return Buckets_Access; 176 pragma Inline (New_Buckets); 177 -- Allocate a new Buckets_Type array with bounds 0..Length-1 178 179 procedure Free_Buckets (Buckets : in out Buckets_Access); 180 pragma Inline (Free_Buckets); 181 -- Unchecked_Deallocate Buckets 182 183 -- Note: New_Buckets and Free_Buckets are needed because Buckets_Access has 184 -- an empty pool. 185 186end Ada.Containers.Hash_Tables.Generic_Operations; 187