1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
5 -- ADA.CONTAINERS.INDEFINITE_HASHED_MAPS --
9 -- Copyright (C) 2004-2009, Free Software Foundation, Inc. --
11 -- This specification is derived from the Ada Reference Manual for use with --
12 -- GNAT. The copyright notice above, and the license provisions that follow --
13 -- apply solely to the contents of the part following the private keyword. --
15 -- GNAT is free software; you can redistribute it and/or modify it under --
16 -- terms of the GNU General Public License as published by the Free Soft- --
17 -- ware Foundation; either version 3, or (at your option) any later ver- --
18 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
19 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
20 -- or FITNESS FOR A PARTICULAR PURPOSE. --
22 -- As a special exception under Section 7 of GPL version 3, you are granted --
23 -- additional permissions described in the GCC Runtime Library Exception, --
24 -- version 3.1, as published by the Free Software Foundation. --
26 -- You should have received a copy of the GNU General Public License and --
27 -- a copy of the GCC Runtime Library Exception along with this program; --
28 -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
29 -- <http://www.gnu.org/licenses/>. --
31 -- This unit was originally developed by Matthew J Heaney. --
32 ------------------------------------------------------------------------------
34 private with Ada
.Containers
.Hash_Tables
;
35 private with Ada
.Streams
;
36 private with Ada
.Finalization
;
39 type Key_Type
(<>) is private;
40 type Element_Type
(<>) is private;
42 with function Hash
(Key
: Key_Type
) return Hash_Type
;
43 with function Equivalent_Keys
(Left
, Right
: Key_Type
) return Boolean;
44 with function "=" (Left
, Right
: Element_Type
) return Boolean is <>;
46 package Ada
.Containers
.Indefinite_Hashed_Maps
is
50 type Map
is tagged private;
51 pragma Preelaborable_Initialization
(Map
);
53 type Cursor
is private;
54 pragma Preelaborable_Initialization
(Cursor
);
56 Empty_Map
: constant Map
;
57 -- Map objects declared without an initialization expression are
58 -- initialized to the value Empty_Map.
60 No_Element
: constant Cursor
;
61 -- Cursor objects declared without an initialization expression are
62 -- initialized to the value No_Element.
64 overriding
function "=" (Left
, Right
: Map
) return Boolean;
65 -- For each key/element pair in Left, equality attempts to find the key in
66 -- Right; if a search fails the equality returns False. The search works by
67 -- calling Hash to find the bucket in the Right map that corresponds to the
68 -- Left key. If bucket is non-empty, then equality calls Equivalent_Keys
69 -- to compare the key (in Left) to the key of each node in the bucket (in
70 -- Right); if the keys are equivalent, then the equality test for this
71 -- key/element pair (in Left) completes by calling the element equality
72 -- operator to compare the element (in Left) to the element of the node
73 -- (in Right) whose key matched.
75 function Capacity
(Container
: Map
) return Count_Type
;
76 -- Returns the current capacity of the map. Capacity is the maximum length
77 -- before which rehashing in guaranteed not to occur.
79 procedure Reserve_Capacity
(Container
: in out Map
; Capacity
: Count_Type
);
80 -- Adjusts the current capacity, by allocating a new buckets array. If the
81 -- requested capacity is less than the current capacity, then the capacity
82 -- is contracted (to a value not less than the current length). If the
83 -- requested capacity is greater than the current capacity, then the
84 -- capacity is expanded (to a value not less than what is requested). In
85 -- either case, the nodes are rehashed from the old buckets array onto the
86 -- new buckets array (Hash is called once for each existing key in order to
87 -- compute the new index), and then the old buckets array is deallocated.
89 function Length
(Container
: Map
) return Count_Type
;
90 -- Returns the number of items in the map
92 function Is_Empty
(Container
: Map
) return Boolean;
93 -- Equivalent to Length (Container) = 0
95 procedure Clear
(Container
: in out Map
);
96 -- Removes all of the items from the map
98 function Key
(Position
: Cursor
) return Key_Type
;
99 -- Returns the key of the node designated by the cursor
101 function Element
(Position
: Cursor
) return Element_Type
;
102 -- Returns the element of the node designated by the cursor
104 procedure Replace_Element
105 (Container
: in out Map
;
107 New_Item
: Element_Type
);
108 -- Assigns the value New_Item to the element designated by the cursor
110 procedure Query_Element
112 Process
: not null access procedure (Key
: Key_Type
;
113 Element
: Element_Type
));
114 -- Calls Process with the key and element (both having only a constant
115 -- view) of the node designed by the cursor.
117 procedure Update_Element
118 (Container
: in out Map
;
120 Process
: not null access procedure (Key
: Key_Type
;
121 Element
: in out Element_Type
));
122 -- Calls Process with the key (with only a constant view) and element (with
123 -- a variable view) of the node designed by the cursor.
125 procedure Move
(Target
: in out Map
; Source
: in out Map
);
126 -- Clears Target (if it's not empty), and then moves (not copies) the
127 -- buckets array and nodes from Source to Target.
130 (Container
: in out Map
;
132 New_Item
: Element_Type
;
133 Position
: out Cursor
;
134 Inserted
: out Boolean);
135 -- Conditionally inserts New_Item into the map. If Key is already in the
136 -- map, then Inserted returns False and Position designates the node
137 -- containing the existing key/element pair (neither of which is modified).
138 -- If Key is not already in the map, the Inserted returns True and Position
139 -- designates the newly-inserted node container Key and New_Item. The
140 -- search for the key works as follows. Hash is called to determine Key's
141 -- bucket; if the bucket is non-empty, then Equivalent_Keys is called to
142 -- compare Key to each node in that bucket. If the bucket is empty, or
143 -- there were no matching keys in the bucket, the search "fails" and the
144 -- key/item pair is inserted in the map (and Inserted returns True);
145 -- otherwise, the search "succeeds" (and Inserted returns False).
148 (Container
: in out Map
;
150 New_Item
: Element_Type
);
151 -- Attempts to insert Key into the map, performing the usual search (which
152 -- involves calling both Hash and Equivalent_Keys); if the search succeeds
153 -- (because Key is already in the map), then it raises Constraint_Error.
154 -- (This version of Insert is similar to Replace, but having the opposite
155 -- exception behavior. It is intended for use when you want to assert that
156 -- Key is not already in the map.)
159 (Container
: in out Map
;
161 New_Item
: Element_Type
);
162 -- Attempts to insert Key into the map. If Key is already in the map, then
163 -- both the existing key and element are assigned the values of Key and
164 -- New_Item, respectively. (This version of Insert only raises an exception
165 -- if cursor tampering occurs. It is intended for use when you want to
166 -- insert the key/element pair in the map, and you don't care whether Key
167 -- is already present.)
170 (Container
: in out Map
;
172 New_Item
: Element_Type
);
173 -- Searches for Key in the map; if the search fails (because Key was not in
174 -- the map), then it raises Constraint_Error. Otherwise, both the existing
175 -- key and element are assigned the values of Key and New_Item rsp. (This
176 -- is similar to Insert, but with the opposite exception behavior. It is
177 -- intended for use when you want to assert that Key is already in the
180 procedure Exclude
(Container
: in out Map
; Key
: Key_Type
);
181 -- Searches for Key in the map, and if found, removes its node from the map
182 -- and then deallocates it. The search works as follows. The operation
183 -- calls Hash to determine the key's bucket; if the bucket is not empty, it
184 -- calls Equivalent_Keys to compare Key to each key in the bucket. (This is
185 -- the deletion analog of Include. It is intended for use when you want to
186 -- remove the item from the map, but don't care whether the key is already
189 procedure Delete
(Container
: in out Map
; Key
: Key_Type
);
190 -- Searches for Key in the map (which involves calling both Hash and
191 -- Equivalent_Keys). If the search fails, then the operation raises
192 -- Constraint_Error. Otherwise it removes the node from the map and then
193 -- deallocates it. (This is the deletion analog of non-conditional
194 -- Insert. It is intended for use when you want to assert that the item is
195 -- already in the map.)
197 procedure Delete
(Container
: in out Map
; Position
: in out Cursor
);
198 -- Removes the node designated by Position from the map, and then
199 -- deallocates the node. The operation calls Hash to determine the bucket,
200 -- and then compares Position to each node in the bucket until there's a
201 -- match (it does not call Equivalent_Keys).
203 function First
(Container
: Map
) return Cursor
;
204 -- Returns a cursor that designates the first non-empty bucket, by
205 -- searching from the beginning of the buckets array.
207 function Next
(Position
: Cursor
) return Cursor
;
208 -- Returns a cursor that designates the node that follows the current one
209 -- designated by Position. If Position designates the last node in its
210 -- bucket, the operation calls Hash to compute the index of this bucket,
211 -- and searches the buckets array for the first non-empty bucket, starting
212 -- from that index; otherwise, it simply follows the link to the next node
213 -- in the same bucket.
215 procedure Next
(Position
: in out Cursor
);
216 -- Equivalent to Position := Next (Position)
218 function Find
(Container
: Map
; Key
: Key_Type
) return Cursor
;
219 -- Searches for Key in the map. Find calls Hash to determine the key's
220 -- bucket; if the bucket is not empty, it calls Equivalent_Keys to compare
221 -- Key to each key in the bucket. If the search succeeds, Find returns a
222 -- cursor designating the matching node; otherwise, it returns No_Element.
224 function Contains
(Container
: Map
; Key
: Key_Type
) return Boolean;
225 -- Equivalent to Find (Container, Key) /= No_Element
227 function Element
(Container
: Map
; Key
: Key_Type
) return Element_Type
;
228 -- Equivalent to Element (Find (Container, Key))
230 function Has_Element
(Position
: Cursor
) return Boolean;
231 -- Equivalent to Position /= No_Element
233 function Equivalent_Keys
(Left
, Right
: Cursor
) return Boolean;
234 -- Returns the result of calling Equivalent_Keys with the keys of the nodes
235 -- designated by cursors Left and Right.
237 function Equivalent_Keys
(Left
: Cursor
; Right
: Key_Type
) return Boolean;
238 -- Returns the result of calling Equivalent_Keys with key of the node
239 -- designated by Left and key Right.
241 function Equivalent_Keys
(Left
: Key_Type
; Right
: Cursor
) return Boolean;
242 -- Returns the result of calling Equivalent_Keys with key Left and the node
243 -- designated by Right.
247 Process
: not null access procedure (Position
: Cursor
));
248 -- Calls Process for each node in the map
252 pragma Inline
(Length
);
253 pragma Inline
(Is_Empty
);
254 pragma Inline
(Clear
);
256 pragma Inline
(Element
);
257 pragma Inline
(Move
);
258 pragma Inline
(Contains
);
259 pragma Inline
(Capacity
);
260 pragma Inline
(Reserve_Capacity
);
261 pragma Inline
(Has_Element
);
262 pragma Inline
(Equivalent_Keys
);
263 pragma Inline
(Next
);
266 type Node_Access
is access Node_Type
;
268 type Key_Access
is access Key_Type
;
269 type Element_Access
is access Element_Type
;
271 type Node_Type
is limited record
273 Element
: Element_Access
;
278 new Hash_Tables
.Generic_Hash_Table_Types
(Node_Type
, Node_Access
);
280 type Map
is new Ada
.Finalization
.Controlled
with record
281 HT
: HT_Types
.Hash_Table_Type
;
285 use Ada
.Finalization
;
289 procedure Adjust
(Container
: in out Map
);
292 procedure Finalize
(Container
: in out Map
);
294 type Map_Access
is access constant Map
;
295 for Map_Access
'Storage_Size use 0;
297 type Cursor
is record
298 Container
: Map_Access
;
303 (Stream
: not null access Root_Stream_Type
'Class;
306 for Cursor
'Write use Write
;
309 (Stream
: not null access Root_Stream_Type
'Class;
312 for Cursor
'Read use Read
;
314 No_Element
: constant Cursor
:=
319 (Stream
: not null access Root_Stream_Type
'Class;
322 for Map
'Write use Write
;
325 (Stream
: not null access Root_Stream_Type
'Class;
326 Container
: out Map
);
328 for Map
'Read use Read
;
330 Empty_Map
: constant Map
:= (Controlled
with HT
=> (null, 0, 0, 0));
332 end Ada
.Containers
.Indefinite_Hashed_Maps
;