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-2009, 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 procedure Adjust (HT : in out Hash_Table_Type); 75 -- Used to implement controlled Adjust. It is assumed that HT has the value 76 -- of the bit-wise copy that immediately follows controlled Finalize. 77 -- Adjust first allocates a new buckets array for HT (having the same 78 -- length as the source), and then allocates a copy of each node of source. 79 80 procedure Finalize (HT : in out Hash_Table_Type); 81 -- Used to implement controlled Finalize. It first calls Clear to 82 -- deallocate any remaining nodes, and then deallocates the buckets array. 83 84 generic 85 with function Find 86 (HT : Hash_Table_Type; 87 Key : Node_Access) return Boolean; 88 function Generic_Equal 89 (L, R : Hash_Table_Type) return Boolean; 90 -- Used to implement hashed container equality. For each node in hash table 91 -- L, it calls Find to search for an equivalent item in hash table R. If 92 -- Find returns False for any node then Generic_Equal terminates 93 -- immediately and returns False. Otherwise if Find returns True for every 94 -- node then Generic_Equal returns True. 95 96 procedure Clear (HT : in out Hash_Table_Type); 97 -- Deallocates each node in hash table HT. (Note that it only deallocates 98 -- the nodes, not the buckets array.) Program_Error is raised if the hash 99 -- table is busy. 100 101 procedure Move (Target, Source : in out Hash_Table_Type); 102 -- Moves (not copies) the buckets array and nodes from Source to 103 -- Target. Program_Error is raised if Source is busy. The Target is first 104 -- cleared to deallocate its nodes (implying that Program_Error is also 105 -- raised if Target is busy). Source is empty following the move. 106 107 function Capacity (HT : Hash_Table_Type) return Count_Type; 108 -- Returns the length of the buckets array 109 110 procedure Reserve_Capacity 111 (HT : in out Hash_Table_Type; 112 N : Count_Type); 113 -- If N is greater than the current capacity, then it expands the buckets 114 -- array to at least the value N. If N is less than the current capacity, 115 -- then it contracts the buckets array. In either case existing nodes are 116 -- rehashed onto the new buckets array, and the old buckets array is 117 -- deallocated. Program_Error is raised if the hash table is busy. 118 119 procedure Delete_Node_Sans_Free 120 (HT : in out Hash_Table_Type; 121 X : Node_Access); 122 -- Removes node X from the hash table without deallocating the node 123 124 function First (HT : Hash_Table_Type) return Node_Access; 125 -- Returns the head of the list in the first (lowest-index) non-empty 126 -- bucket. 127 128 function Next 129 (HT : Hash_Table_Type; 130 Node : Node_Access) return Node_Access; 131 -- Returns the node that immediately follows Node. This corresponds to 132 -- either the next node in the same bucket, or (if Node is the last node in 133 -- its bucket) the head of the list in the first non-empty bucket that 134 -- follows. 135 136 generic 137 with procedure Process (Node : Node_Access); 138 procedure Generic_Iteration (HT : Hash_Table_Type); 139 -- Calls Process for each node in hash table HT 140 141 generic 142 use Ada.Streams; 143 with procedure Write 144 (Stream : not null access Root_Stream_Type'Class; 145 Node : Node_Access); 146 procedure Generic_Write 147 (Stream : not null access Root_Stream_Type'Class; 148 HT : Hash_Table_Type); 149 -- Used to implement the streaming attribute for hashed containers. It 150 -- calls Write for each node to write its value into Stream. 151 152 generic 153 use Ada.Streams; 154 with function New_Node (Stream : not null access Root_Stream_Type'Class) 155 return Node_Access; 156 procedure Generic_Read 157 (Stream : not null access Root_Stream_Type'Class; 158 HT : out Hash_Table_Type); 159 -- Used to implement the streaming attribute for hashed containers. It 160 -- first clears hash table HT, then populates the hash table by calling 161 -- New_Node for each item in Stream. 162 163 function New_Buckets (Length : Hash_Type) return Buckets_Access; 164 pragma Inline (New_Buckets); 165 -- Allocate a new Buckets_Type array with bounds 0..Length-1 166 167 procedure Free_Buckets (Buckets : in out Buckets_Access); 168 pragma Inline (Free_Buckets); 169 -- Unchecked_Deallocate Buckets 170 171 -- Note: New_Buckets and Free_Buckets are needed because Buckets_Access has 172 -- an empty pool. 173 174end Ada.Containers.Hash_Tables.Generic_Operations; 175