1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
5 -- ADA.CONTAINERS.HASH_TABLES.GENERIC_OPERATIONS --
9 -- Copyright (C) 2004-2008, Free Software Foundation, Inc. --
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 2, 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. See the GNU General Public License --
17 -- for more details. You should have received a copy of the GNU General --
18 -- Public License distributed with GNAT; see file COPYING. If not, write --
19 -- to the Free Software Foundation, 51 Franklin Street, Fifth Floor, --
20 -- Boston, MA 02110-1301, USA. --
22 -- As a special exception, if other files instantiate generics from this --
23 -- unit, or you link this unit with other files to produce an executable, --
24 -- this unit does not by itself cause the resulting executable to be --
25 -- covered by the GNU General Public License. This exception does not --
26 -- however invalidate any other reasons why the executable file might be --
27 -- covered by the GNU Public License. --
29 -- This unit was originally developed by Matthew J Heaney. --
30 ------------------------------------------------------------------------------
32 -- Hash_Table_Type is used to implement hashed containers. This package
33 -- declares hash-table operations that do not depend on keys.
39 with package HT_Types
is
40 new Generic_Hash_Table_Types
(<>);
44 with function Hash_Node
(Node
: Node_Access
) return Hash_Type
;
46 with function Next
(Node
: Node_Access
) return Node_Access
;
48 with procedure Set_Next
52 with function Copy_Node
(Source
: Node_Access
) return Node_Access
;
54 with procedure Free
(X
: in out Node_Access
);
56 package Ada
.Containers
.Hash_Tables
.Generic_Operations
is
59 procedure Free_Hash_Table
(Buckets
: in out Buckets_Access
);
60 -- First frees the nodes in all non-null buckets of Buckets, and then frees
61 -- the Buckets array itself.
64 (Buckets
: Buckets_Type
;
65 Node
: Node_Access
) return Hash_Type
;
66 pragma Inline
(Index
);
67 -- Uses the hash value of Node to compute its Buckets array index
70 (Hash_Table
: Hash_Table_Type
;
71 Node
: Node_Access
) return Hash_Type
;
72 pragma Inline
(Index
);
73 -- Uses the hash value of Node to compute its Hash_Table buckets array
76 procedure Adjust
(HT
: in out Hash_Table_Type
);
77 -- Used to implement controlled Adjust. It is assumed that HT has the value
78 -- of the bit-wise copy that immediately follows controlled Finalize.
79 -- Adjust first allocates a new buckets array for HT (having the same
80 -- length as the source), and then allocates a copy of each node of source.
82 procedure Finalize
(HT
: in out Hash_Table_Type
);
83 -- Used to implement controlled Finalize. It first calls Clear to
84 -- deallocate any remaining nodes, and then deallocates the buckets array.
88 (HT
: Hash_Table_Type
;
89 Key
: Node_Access
) return Boolean;
90 function Generic_Equal
91 (L
, R
: Hash_Table_Type
) return Boolean;
92 -- Used to implement hashed container equality. For each node in hash table
93 -- L, it calls Find to search for an equivalent item in hash table R. If
94 -- Find returns False for any node then Generic_Equal terminates
95 -- immediately and returns False. Otherwise if Find returns True for every
96 -- node then Generic_Equal returns True.
98 procedure Clear
(HT
: in out Hash_Table_Type
);
99 -- Deallocates each node in hash table HT. (Note that it only deallocates
100 -- the nodes, not the buckets array.) Program_Error is raised if the hash
103 procedure Move
(Target
, Source
: in out Hash_Table_Type
);
104 -- Moves (not copies) the buckets array and nodes from Source to
105 -- Target. Program_Error is raised if Source is busy. The Target is first
106 -- cleared to deallocate its nodes (implying that Program_Error is also
107 -- raised if Target is busy). Source is empty following the move.
109 function Capacity
(HT
: Hash_Table_Type
) return Count_Type
;
110 -- Returns the length of the buckets array
112 procedure Reserve_Capacity
113 (HT
: in out Hash_Table_Type
;
115 -- If N is greater than the current capacity, then it expands the buckets
116 -- array to at least the value N. If N is less than the current capacity,
117 -- then it contracts the buckets array. In either case existing nodes are
118 -- rehashed onto the new buckets array, and the old buckets array is
119 -- deallocated. Program_Error is raised if the hash table is busy.
121 procedure Delete_Node_Sans_Free
122 (HT
: in out Hash_Table_Type
;
124 -- Removes node X from the hash table without deallocating the node
126 function First
(HT
: Hash_Table_Type
) return Node_Access
;
127 -- Returns the head of the list in the first (lowest-index) non-empty
131 (HT
: Hash_Table_Type
;
132 Node
: Node_Access
) return Node_Access
;
133 -- Returns the node that immediately follows Node. This corresponds to
134 -- either the next node in the same bucket, or (if Node is the last node in
135 -- its bucket) the head of the list in the first non-empty bucket that
139 with procedure Process
(Node
: Node_Access
);
140 procedure Generic_Iteration
(HT
: Hash_Table_Type
);
141 -- Calls Process for each node in hash table HT
146 (Stream
: not null access Root_Stream_Type
'Class;
148 procedure Generic_Write
149 (Stream
: not null access Root_Stream_Type
'Class;
150 HT
: Hash_Table_Type
);
151 -- Used to implement the streaming attribute for hashed containers. It
152 -- calls Write for each node to write its value into Stream.
156 with function New_Node
(Stream
: not null access Root_Stream_Type
'Class)
158 procedure Generic_Read
159 (Stream
: not null access Root_Stream_Type
'Class;
160 HT
: out Hash_Table_Type
);
161 -- Used to implement the streaming attribute for hashed containers. It
162 -- first clears hash table HT, then populates the hash table by calling
163 -- New_Node for each item in Stream.
165 function New_Buckets
(Length
: Hash_Type
) return Buckets_Access
;
166 pragma Inline
(New_Buckets
);
167 -- Allocate a new Buckets_Type array with bounds 0..Length-1
169 procedure Free_Buckets
(Buckets
: in out Buckets_Access
);
170 pragma Inline
(Free_Buckets
);
171 -- Unchecked_Deallocate Buckets
173 -- Note: New_Buckets and Free_Buckets are needed because Buckets_Access has
176 end Ada
.Containers
.Hash_Tables
.Generic_Operations
;