1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
5 -- ADA.CONTAINERS.INDEFINITE_HASHED_MAPS --
9 -- Copyright (C) 2004-2011, 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
.Finalization
;
36 with Ada
.Streams
; use Ada
.Streams
;
37 with Ada
.Iterator_Interfaces
;
40 type Key_Type
(<>) is private;
41 type Element_Type
(<>) is private;
43 with function Hash
(Key
: Key_Type
) return Hash_Type
;
44 with function Equivalent_Keys
(Left
, Right
: Key_Type
) return Boolean;
45 with function "=" (Left
, Right
: Element_Type
) return Boolean is <>;
47 package Ada
.Containers
.Indefinite_Hashed_Maps
is
51 type Map
is tagged private with
52 Constant_Indexing
=> Constant_Reference
,
53 Variable_Indexing
=> Reference
,
54 Default_Iterator
=> Iterate
,
55 Iterator_Element
=> Element_Type
;
57 pragma Preelaborable_Initialization
(Map
);
59 type Cursor
is private;
60 pragma Preelaborable_Initialization
(Cursor
);
62 Empty_Map
: constant Map
;
63 -- Map objects declared without an initialization expression are
64 -- initialized to the value Empty_Map.
66 No_Element
: constant Cursor
;
67 -- Cursor objects declared without an initialization expression are
68 -- initialized to the value No_Element.
70 function Has_Element
(Position
: Cursor
) return Boolean;
71 -- Equivalent to Position /= No_Element
73 package Map_Iterator_Interfaces
is new
74 Ada
.Iterator_Interfaces
(Cursor
, Has_Element
);
76 overriding
function "=" (Left
, Right
: Map
) return Boolean;
77 -- For each key/element pair in Left, equality attempts to find the key in
78 -- Right; if a search fails the equality returns False. The search works by
79 -- calling Hash to find the bucket in the Right map that corresponds to the
80 -- Left key. If bucket is non-empty, then equality calls Equivalent_Keys
81 -- to compare the key (in Left) to the key of each node in the bucket (in
82 -- Right); if the keys are equivalent, then the equality test for this
83 -- key/element pair (in Left) completes by calling the element equality
84 -- operator to compare the element (in Left) to the element of the node
85 -- (in Right) whose key matched.
87 function Capacity
(Container
: Map
) return Count_Type
;
88 -- Returns the current capacity of the map. Capacity is the maximum length
89 -- before which rehashing in guaranteed not to occur.
91 procedure Reserve_Capacity
(Container
: in out Map
; Capacity
: Count_Type
);
92 -- Adjusts the current capacity, by allocating a new buckets array. If the
93 -- requested capacity is less than the current capacity, then the capacity
94 -- is contracted (to a value not less than the current length). If the
95 -- requested capacity is greater than the current capacity, then the
96 -- capacity is expanded (to a value not less than what is requested). In
97 -- either case, the nodes are rehashed from the old buckets array onto the
98 -- new buckets array (Hash is called once for each existing key in order to
99 -- compute the new index), and then the old buckets array is deallocated.
101 function Length
(Container
: Map
) return Count_Type
;
102 -- Returns the number of items in the map
104 function Is_Empty
(Container
: Map
) return Boolean;
105 -- Equivalent to Length (Container) = 0
107 procedure Clear
(Container
: in out Map
);
108 -- Removes all of the items from the map
110 function Key
(Position
: Cursor
) return Key_Type
;
111 -- Returns the key of the node designated by the cursor
113 function Element
(Position
: Cursor
) return Element_Type
;
114 -- Returns the element of the node designated by the cursor
116 procedure Replace_Element
117 (Container
: in out Map
;
119 New_Item
: Element_Type
);
120 -- Assigns the value New_Item to the element designated by the cursor
122 procedure Query_Element
124 Process
: not null access procedure (Key
: Key_Type
;
125 Element
: Element_Type
));
126 -- Calls Process with the key and element (both having only a constant
127 -- view) of the node designed by the cursor.
129 procedure Update_Element
130 (Container
: in out Map
;
132 Process
: not null access procedure (Key
: Key_Type
;
133 Element
: in out Element_Type
));
134 -- Calls Process with the key (with only a constant view) and element (with
135 -- a variable view) of the node designed by the cursor.
137 procedure Assign
(Target
: in out Map
; Source
: Map
);
139 function Copy
(Source
: Map
; Capacity
: Count_Type
:= 0) return Map
;
141 procedure Move
(Target
: in out Map
; Source
: in out Map
);
142 -- Clears Target (if it's not empty), and then moves (not copies) the
143 -- buckets array and nodes from Source to Target.
146 (Container
: in out Map
;
148 New_Item
: Element_Type
;
149 Position
: out Cursor
;
150 Inserted
: out Boolean);
151 -- Conditionally inserts New_Item into the map. If Key is already in the
152 -- map, then Inserted returns False and Position designates the node
153 -- containing the existing key/element pair (neither of which is modified).
154 -- If Key is not already in the map, the Inserted returns True and Position
155 -- designates the newly-inserted node container Key and New_Item. The
156 -- search for the key works as follows. Hash is called to determine Key's
157 -- bucket; if the bucket is non-empty, then Equivalent_Keys is called to
158 -- compare Key to each node in that bucket. If the bucket is empty, or
159 -- there were no matching keys in the bucket, the search "fails" and the
160 -- key/item pair is inserted in the map (and Inserted returns True);
161 -- otherwise, the search "succeeds" (and Inserted returns False).
164 (Container
: in out Map
;
166 New_Item
: Element_Type
);
167 -- Attempts to insert Key into the map, performing the usual search (which
168 -- involves calling both Hash and Equivalent_Keys); if the search succeeds
169 -- (because Key is already in the map), then it raises Constraint_Error.
170 -- (This version of Insert is similar to Replace, but having the opposite
171 -- exception behavior. It is intended for use when you want to assert that
172 -- Key is not already in the map.)
175 (Container
: in out Map
;
177 New_Item
: Element_Type
);
178 -- Attempts to insert Key into the map. If Key is already in the map, then
179 -- both the existing key and element are assigned the values of Key and
180 -- New_Item, respectively. (This version of Insert only raises an exception
181 -- if cursor tampering occurs. It is intended for use when you want to
182 -- insert the key/element pair in the map, and you don't care whether Key
183 -- is already present.)
186 (Container
: in out Map
;
188 New_Item
: Element_Type
);
189 -- Searches for Key in the map; if the search fails (because Key was not in
190 -- the map), then it raises Constraint_Error. Otherwise, both the existing
191 -- key and element are assigned the values of Key and New_Item rsp. (This
192 -- is similar to Insert, but with the opposite exception behavior. It is
193 -- intended for use when you want to assert that Key is already in the
196 procedure Exclude
(Container
: in out Map
; Key
: Key_Type
);
197 -- Searches for Key in the map, and if found, removes its node from the map
198 -- and then deallocates it. The search works as follows. The operation
199 -- calls Hash to determine the key's bucket; if the bucket is not empty, it
200 -- calls Equivalent_Keys to compare Key to each key in the bucket. (This is
201 -- the deletion analog of Include. It is intended for use when you want to
202 -- remove the item from the map, but don't care whether the key is already
205 procedure Delete
(Container
: in out Map
; Key
: Key_Type
);
206 -- Searches for Key in the map (which involves calling both Hash and
207 -- Equivalent_Keys). If the search fails, then the operation raises
208 -- Constraint_Error. Otherwise it removes the node from the map and then
209 -- deallocates it. (This is the deletion analog of non-conditional
210 -- Insert. It is intended for use when you want to assert that the item is
211 -- already in the map.)
213 procedure Delete
(Container
: in out Map
; Position
: in out Cursor
);
214 -- Removes the node designated by Position from the map, and then
215 -- deallocates the node. The operation calls Hash to determine the bucket,
216 -- and then compares Position to each node in the bucket until there's a
217 -- match (it does not call Equivalent_Keys).
219 function First
(Container
: Map
) return Cursor
;
220 -- Returns a cursor that designates the first non-empty bucket, by
221 -- searching from the beginning of the buckets array.
223 function Next
(Position
: Cursor
) return Cursor
;
224 -- Returns a cursor that designates the node that follows the current one
225 -- designated by Position. If Position designates the last node in its
226 -- bucket, the operation calls Hash to compute the index of this bucket,
227 -- and searches the buckets array for the first non-empty bucket, starting
228 -- from that index; otherwise, it simply follows the link to the next node
229 -- in the same bucket.
231 procedure Next
(Position
: in out Cursor
);
232 -- Equivalent to Position := Next (Position)
234 function Find
(Container
: Map
; Key
: Key_Type
) return Cursor
;
235 -- Searches for Key in the map. Find calls Hash to determine the key's
236 -- bucket; if the bucket is not empty, it calls Equivalent_Keys to compare
237 -- Key to each key in the bucket. If the search succeeds, Find returns a
238 -- cursor designating the matching node; otherwise, it returns No_Element.
240 function Contains
(Container
: Map
; Key
: Key_Type
) return Boolean;
241 -- Equivalent to Find (Container, Key) /= No_Element
243 function Element
(Container
: Map
; Key
: Key_Type
) return Element_Type
;
244 -- Equivalent to Element (Find (Container, Key))
246 function Equivalent_Keys
(Left
, Right
: Cursor
) return Boolean;
247 -- Returns the result of calling Equivalent_Keys with the keys of the nodes
248 -- designated by cursors Left and Right.
250 function Equivalent_Keys
(Left
: Cursor
; Right
: Key_Type
) return Boolean;
251 -- Returns the result of calling Equivalent_Keys with key of the node
252 -- designated by Left and key Right.
254 function Equivalent_Keys
(Left
: Key_Type
; Right
: Cursor
) return Boolean;
255 -- Returns the result of calling Equivalent_Keys with key Left and the node
256 -- designated by Right.
258 type Constant_Reference_Type
259 (Element
: not null access constant Element_Type
) is private
261 Implicit_Dereference
=> Element
;
264 (Stream
: not null access Root_Stream_Type
'Class;
265 Item
: Constant_Reference_Type
);
267 for Constant_Reference_Type
'Write use Write
;
270 (Stream
: not null access Root_Stream_Type
'Class;
271 Item
: out Constant_Reference_Type
);
273 for Constant_Reference_Type
'Read use Read
;
275 type Reference_Type
(Element
: not null access Element_Type
) is private
277 Implicit_Dereference
=> Element
;
280 (Stream
: not null access Root_Stream_Type
'Class;
281 Item
: Reference_Type
);
283 for Reference_Type
'Write use Write
;
286 (Stream
: not null access Root_Stream_Type
'Class;
287 Item
: out Reference_Type
);
289 for Reference_Type
'Read use Read
;
291 function Constant_Reference
293 Key
: Key_Type
) -- SHOULD BE ALIASED ???
294 return Constant_Reference_Type
;
298 Key
: Key_Type
) return Reference_Type
;
301 (Container
: aliased in out Map
;
302 Position
: Cursor
) return Reference_Type
;
306 Process
: not null access procedure (Position
: Cursor
));
307 -- Calls Process for each node in the map
309 function Iterate
(Container
: Map
)
310 return Map_Iterator_Interfaces
.Forward_Iterator
'class;
314 pragma Inline
(Length
);
315 pragma Inline
(Is_Empty
);
316 pragma Inline
(Clear
);
318 pragma Inline
(Element
);
319 pragma Inline
(Move
);
320 pragma Inline
(Contains
);
321 pragma Inline
(Capacity
);
322 pragma Inline
(Reserve_Capacity
);
323 pragma Inline
(Has_Element
);
324 pragma Inline
(Equivalent_Keys
);
325 pragma Inline
(Next
);
328 type Node_Access
is access Node_Type
;
330 type Key_Access
is access Key_Type
;
331 type Element_Access
is access Element_Type
;
333 type Node_Type
is limited record
335 Element
: Element_Access
;
340 new Hash_Tables
.Generic_Hash_Table_Types
(Node_Type
, Node_Access
);
342 type Map
is new Ada
.Finalization
.Controlled
with record
343 HT
: HT_Types
.Hash_Table_Type
;
347 use Ada
.Finalization
;
349 overriding
procedure Adjust
(Container
: in out Map
);
350 overriding
procedure Finalize
(Container
: in out Map
);
352 type Map_Access
is access all Map
;
353 for Map_Access
'Storage_Size use 0;
355 type Cursor
is record
356 Container
: Map_Access
;
361 (Stream
: not null access Root_Stream_Type
'Class;
364 for Cursor
'Write use Write
;
366 type Constant_Reference_Type
367 (Element
: not null access constant Element_Type
) is null record;
370 (Element
: not null access Element_Type
) is null record;
373 (Stream
: not null access Root_Stream_Type
'Class;
376 for Cursor
'Read use Read
;
378 No_Element
: constant Cursor
:=
383 (Stream
: not null access Root_Stream_Type
'Class;
386 for Map
'Write use Write
;
389 (Stream
: not null access Root_Stream_Type
'Class;
390 Container
: out Map
);
392 for Map
'Read use Read
;
394 Empty_Map
: constant Map
:= (Controlled
with HT
=> (null, 0, 0, 0));
396 end Ada
.Containers
.Indefinite_Hashed_Maps
;