1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
5 -- A D A . C O N T A I N E R S . --
6 -- H A S H _ T A B L E S . G E N E R I C _ O P E R A T I O N S --
10 -- Copyright (C) 2004-2007, Free Software Foundation, Inc. --
12 -- GNAT is free software; you can redistribute it and/or modify it under --
13 -- terms of the GNU General Public License as published by the Free Soft- --
14 -- ware Foundation; either version 2, or (at your option) any later ver- --
15 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
16 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
17 -- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License --
18 -- for more details. You should have received a copy of the GNU General --
19 -- Public License distributed with GNAT; see file COPYING. If not, write --
20 -- to the Free Software Foundation, 51 Franklin Street, Fifth Floor, --
21 -- Boston, MA 02110-1301, USA. --
23 -- As a special exception, if other files instantiate generics from this --
24 -- unit, or you link this unit with other files to produce an executable, --
25 -- this unit does not by itself cause the resulting executable to be --
26 -- covered by the GNU General Public License. This exception does not --
27 -- however invalidate any other reasons why the executable file might be --
28 -- covered by the GNU Public License. --
30 -- This unit was originally developed by Matthew J Heaney. --
31 ------------------------------------------------------------------------------
33 -- Hash_Table_Type is used to implement hashed containers. This package
34 -- declares hash-table operations that do not depend on keys.
40 with package HT_Types
is
41 new Generic_Hash_Table_Types
(<>);
45 with function Hash_Node
(Node
: Node_Access
) return Hash_Type
;
47 with function Next
(Node
: Node_Access
) return Node_Access
;
49 with procedure Set_Next
53 with function Copy_Node
(Source
: Node_Access
) return Node_Access
;
55 with procedure Free
(X
: in out Node_Access
);
57 package Ada
.Containers
.Hash_Tables
.Generic_Operations
is
60 procedure Free_Hash_Table
(Buckets
: in out Buckets_Access
);
61 -- First frees the nodes in all non-null buckets of Buckets, and then frees
62 -- the Buckets array itself.
65 (Buckets
: Buckets_Type
;
66 Node
: Node_Access
) return Hash_Type
;
67 pragma Inline
(Index
);
68 -- Uses the hash value of Node to compute its Buckets array index
71 (Hash_Table
: Hash_Table_Type
;
72 Node
: Node_Access
) return Hash_Type
;
73 pragma Inline
(Index
);
74 -- Uses the hash value of Node to compute its Hash_Table buckets array
77 procedure Adjust
(HT
: in out Hash_Table_Type
);
78 -- Used to implement controlled Adjust. It is assumed that HT has the value
79 -- of the bit-wise copy that immediately follows controlled Finalize.
80 -- Adjust first allocates a new buckets array for HT (having the same
81 -- length as the source), and then allocates a copy of each node of source.
83 procedure Finalize
(HT
: in out Hash_Table_Type
);
84 -- Used to implement controlled Finalize. It first calls Clear to
85 -- deallocate any remaining nodes, and then deallocates the buckets array.
89 (HT
: Hash_Table_Type
;
90 Key
: Node_Access
) return Boolean;
91 function Generic_Equal
92 (L
, R
: Hash_Table_Type
) return Boolean;
93 -- Used to implement hashed container equality. For each node in hash table
94 -- L, it calls Find to search for an equivalent item in hash table R. If
95 -- Find returns False for any node then Generic_Equal terminates
96 -- immediately and returns False. Otherwise if Find returns True for every
97 -- node then Generic_Equal returns True.
99 procedure Clear
(HT
: in out Hash_Table_Type
);
100 -- Deallocates each node in hash table HT. (Note that it only deallocates
101 -- the nodes, not the buckets array.) Program_Error is raised if the hash
104 procedure Move
(Target
, Source
: in out Hash_Table_Type
);
105 -- Moves (not copies) the buckets array and nodes from Source to
106 -- Target. Program_Error is raised if Source is busy. The Target is first
107 -- cleared to deallocate its nodes (implying that Program_Error is also
108 -- raised if Target is busy). Source is empty following the move.
110 function Capacity
(HT
: Hash_Table_Type
) return Count_Type
;
111 -- Returns the length of the buckets array
113 procedure Reserve_Capacity
114 (HT
: in out Hash_Table_Type
;
116 -- If N is greater than the current capacity, then it expands the buckets
117 -- array to at least the value N. If N is less than the current capacity,
118 -- then it contracts the buckets array. In either case existing nodes are
119 -- rehashed onto the new buckets array, and the old buckets array is
120 -- deallocated. Program_Error is raised if the hash table is busy.
122 procedure Delete_Node_Sans_Free
123 (HT
: in out Hash_Table_Type
;
125 -- Removes node X from the hash table without deallocating the node
127 function First
(HT
: Hash_Table_Type
) return Node_Access
;
128 -- Returns the head of the list in the first (lowest-index) non-empty
132 (HT
: Hash_Table_Type
;
133 Node
: Node_Access
) return Node_Access
;
134 -- Returns the node that immediately follows Node. This corresponds to
135 -- either the next node in the same bucket, or (if Node is the last node in
136 -- its bucket) the head of the list in the first non-empty bucket that
140 with procedure Process
(Node
: Node_Access
);
141 procedure Generic_Iteration
(HT
: Hash_Table_Type
);
142 -- Calls Process for each node in hash table HT
147 (Stream
: not null access Root_Stream_Type
'Class;
149 procedure Generic_Write
150 (Stream
: not null access Root_Stream_Type
'Class;
151 HT
: Hash_Table_Type
);
152 -- Used to implement the streaming attribute for hashed containers. It
153 -- calls Write for each node to write its value into Stream.
157 with function New_Node
(Stream
: not null access Root_Stream_Type
'Class)
159 procedure Generic_Read
160 (Stream
: not null access Root_Stream_Type
'Class;
161 HT
: out Hash_Table_Type
);
162 -- Used to implement the streaming attribute for hashed containers. It
163 -- first clears hash table HT, then populates the hash table by calling
164 -- New_Node for each item in Stream.
166 function New_Buckets
(Length
: Hash_Type
) return Buckets_Access
;
167 pragma Inline
(New_Buckets
);
168 -- Allocate a new Buckets_Type array with bounds 0..Length-1.
170 procedure Free_Buckets
(Buckets
: in out Buckets_Access
);
171 pragma Inline
(Free_Buckets
);
172 -- Unchecked_Deallocate Buckets.
174 -- Note: New_Buckets and Free_Buckets are needed because Buckets_Access has
177 end Ada
.Containers
.Hash_Tables
.Generic_Operations
;