1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
5 -- A D A . C O N T A I N E R S . H A S H E D _ M A P S --
9 -- Copyright (C) 2004-2018, 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 with Ada
.Iterator_Interfaces
;
36 private with Ada
.Containers
.Hash_Tables
;
37 private with Ada
.Finalization
;
38 private with Ada
.Streams
;
40 -- The language-defined generic package Containers.Hashed_Maps provides
41 -- private types Map and Cursor, and a set of operations for each type. A map
42 -- container allows an arbitrary type to be used as a key to find the element
43 -- associated with that key. A hashed map uses a hash function to organize the
46 -- A map contains pairs of keys and elements, called nodes. Map cursors
47 -- designate nodes, but also can be thought of as designating an element (the
48 -- element contained in the node) for consistency with the other containers.
49 -- There exists an equivalence relation on keys, whose definition is different
50 -- for hashed maps and ordered maps. A map never contains two or more nodes
51 -- with equivalent keys. The length of a map is the number of nodes it
54 -- Each nonempty map has two particular nodes called the first node and the
55 -- last node (which may be the same). Each node except for the last node has a
56 -- successor node. If there are no other intervening operations, starting with
57 -- the first node and repeatedly going to the successor node will visit each
58 -- node in the map exactly once until the last node is reached.
61 type Key_Type
is private;
62 type Element_Type
is private;
64 with function Hash
(Key
: Key_Type
) return Hash_Type
;
65 -- The actual function for the generic formal function Hash is expected to
66 -- return the same value each time it is called with a particular key
67 -- value. For any two equivalent key values, the actual for Hash is
68 -- expected to return the same value. If the actual for Hash behaves in
69 -- some other manner, the behavior of this package is unspecified. Which
70 -- subprograms of this package call Hash, and how many times they call it,
73 with function Equivalent_Keys
(Left
, Right
: Key_Type
) return Boolean;
74 -- The actual function for the generic formal function Equivalent_Keys on
75 -- Key_Type values is expected to return the same value each time it is
76 -- called with a particular pair of key values. It should define an
77 -- equivalence relationship, that is, be reflexive, symmetric, and
78 -- transitive. If the actual for Equivalent_Keys behaves in some other
79 -- manner, the behavior of this package is unspecified. Which subprograms
80 -- of this package call Equivalent_Keys, and how many times they call it,
83 with function "=" (Left
, Right
: Element_Type
) return Boolean is <>;
84 -- The actual function for the generic formal function "=" on Element_Type
85 -- values is expected to define a reflexive and symmetric relationship and
86 -- return the same result value each time it is called with a particular
87 -- pair of values. If it behaves in some other manner, the function "=" on
88 -- map values returns an unspecified value. The exact arguments and number
89 -- of calls of this generic formal function by the function "=" on map
90 -- values are unspecified.
91 package Ada
.Containers
.Hashed_Maps
is
92 pragma Annotate
(CodePeer
, Skip_Analysis
);
96 type Map
is tagged private
98 Constant_Indexing
=> Constant_Reference
,
99 Variable_Indexing
=> Reference
,
100 Default_Iterator
=> Iterate
,
101 Iterator_Element
=> Element_Type
;
103 pragma Preelaborable_Initialization
(Map
);
105 type Cursor
is private;
106 pragma Preelaborable_Initialization
(Cursor
);
108 Empty_Map
: constant Map
;
109 -- Map objects declared without an initialization expression are
110 -- initialized to the value Empty_Map.
112 No_Element
: constant Cursor
;
113 -- Cursor objects declared without an initialization expression are
114 -- initialized to the value No_Element.
116 function Has_Element
(Position
: Cursor
) return Boolean;
117 -- Returns True if Position designates an element, and returns False
120 package Map_Iterator_Interfaces
is new
121 Ada
.Iterator_Interfaces
(Cursor
, Has_Element
);
123 function "=" (Left
, Right
: Map
) return Boolean;
124 -- If Left and Right denote the same map object, then the function returns
125 -- True. If Left and Right have different lengths, then the function
126 -- returns False. Otherwise, for each key K in Left, the function returns
129 -- * a key equivalent to K is not present in Right; or
131 -- * the element associated with K in Left is not equal to the
132 -- element associated with K in Right (using the generic formal
133 -- equality operator for elements).
135 -- If the function has not returned a result after checking all of the
136 -- keys, it returns True. Any exception raised during evaluation of key
137 -- equivalence or element equality is propagated.
139 function Capacity
(Container
: Map
) return Count_Type
;
140 -- Returns the current capacity of the map. Capacity is the maximum length
141 -- before which rehashing in guaranteed not to occur.
143 procedure Reserve_Capacity
(Container
: in out Map
; Capacity
: Count_Type
);
144 -- Adjusts the current capacity, by allocating a new buckets array. If the
145 -- requested capacity is less than the current capacity, then the capacity
146 -- is contracted (to a value not less than the current length). If the
147 -- requested capacity is greater than the current capacity, then the
148 -- capacity is expanded (to a value not less than what is requested). In
149 -- either case, the nodes are rehashed from the old buckets array onto the
150 -- new buckets array (Hash is called once for each existing key in order to
151 -- compute the new index), and then the old buckets array is deallocated.
153 function Length
(Container
: Map
) return Count_Type
;
154 -- Returns the number of items in the map
156 function Is_Empty
(Container
: Map
) return Boolean;
157 -- Equivalent to Length (Container) = 0
159 procedure Clear
(Container
: in out Map
);
160 -- Removes all of the items from the map
162 function Key
(Position
: Cursor
) return Key_Type
;
163 -- Key returns the key component of the node designated by Position.
165 -- If Position equals No_Element, then Constraint_Error is propagated.
167 function Element
(Position
: Cursor
) return Element_Type
;
168 -- Element returns the element component of the node designated
171 -- If Position equals No_Element, then Constraint_Error is propagated.
173 procedure Replace_Element
174 (Container
: in out Map
;
176 New_Item
: Element_Type
);
177 -- Replace_Element assigns New_Item to the element of the node designated
180 -- If Position equals No_Element, then Constraint_Error is propagated; if
181 -- Position does not designate an element in Container, then Program_Error
184 procedure Query_Element
186 Process
: not null access
187 procedure (Key
: Key_Type
; Element
: Element_Type
));
188 -- Query_Element calls Process.all with the key and element from the node
189 -- designated by Position as the arguments.
191 -- If Position equals No_Element, then Constraint_Error is propagated.
193 -- Tampering with the elements of the map that contains the element
194 -- designated by Position is prohibited during the execution of the call on
195 -- Process.all. Any exception raised by Process.all is propagated.
197 procedure Update_Element
198 (Container
: in out Map
;
200 Process
: not null access
201 procedure (Key
: Key_Type
; Element
: in out Element_Type
));
202 -- Update_Element calls Process.all with the key and element from the node
203 -- designated by Position as the arguments.
205 -- If Position equals No_Element, then Constraint_Error is propagated; if
206 -- Position does not designate an element in Container, then Program_Error
209 -- Tampering with the elements of Container is prohibited during the
210 -- execution of the call on Process.all. Any exception raised by
211 -- Process.all is propagated.
213 type Constant_Reference_Type
214 (Element
: not null access constant Element_Type
) is private
216 Implicit_Dereference
=> Element
;
218 type Reference_Type
(Element
: not null access Element_Type
) is private
220 Implicit_Dereference
=> Element
;
222 function Constant_Reference
223 (Container
: aliased Map
;
224 Position
: Cursor
) return Constant_Reference_Type
;
225 pragma Inline
(Constant_Reference
);
226 -- This function (combined with the Constant_Indexing and
227 -- Implicit_Dereference aspects) provides a convenient way to gain read
228 -- access to an individual element of a map given a cursor.
229 -- Constant_Reference returns an object whose discriminant is an access
230 -- value that designates the element designated by Position.
232 -- If Position equals No_Element, then Constraint_Error is propagated; if
233 -- Position does not designate an element in Container, then Program_Error
236 -- Tampering with the elements of Container is prohibited
237 -- while the object returned by Constant_Reference exists and has not been
241 (Container
: aliased in out Map
;
242 Position
: Cursor
) return Reference_Type
;
243 pragma Inline
(Reference
);
244 -- This function (combined with the Variable_Indexing and
245 -- Implicit_Dereference aspects) provides a convenient way to gain read and
246 -- write access to an individual element of a map given a cursor.
247 -- Reference returns an object whose discriminant is an access value that
248 -- designates the element designated by Position.
250 -- If Position equals No_Element, then Constraint_Error is propagated; if
251 -- Position does not designate an element in Container, then Program_Error
254 -- Tampering with the elements of Container is prohibited while the object
255 -- returned by Reference exists and has not been finalized.
257 function Constant_Reference
258 (Container
: aliased Map
;
259 Key
: Key_Type
) return Constant_Reference_Type
;
260 pragma Inline
(Constant_Reference
);
261 -- Equivalent to Constant_Reference (Container, Find (Container, Key)).
264 (Container
: aliased in out Map
;
265 Key
: Key_Type
) return Reference_Type
;
266 pragma Inline
(Reference
);
267 -- Equivalent to Reference (Container, Find (Container, Key)).
269 procedure Assign
(Target
: in out Map
; Source
: Map
);
270 -- If Target denotes the same object as Source, the operation has no
271 -- effect. Otherwise, the key/element pairs of Source are copied to Target
272 -- as for an assignment_statement assigning Source to Target.
274 function Copy
(Source
: Map
; Capacity
: Count_Type
:= 0) return Map
;
276 procedure Move
(Target
: in out Map
; Source
: in out Map
);
277 -- If Target denotes the same object as Source, then the operation has no
278 -- effect. Otherwise, the operation is equivalent to Assign (Target,
279 -- Source) followed by Clear (Source).
282 (Container
: in out Map
;
284 New_Item
: Element_Type
;
285 Position
: out Cursor
;
286 Inserted
: out Boolean);
287 -- Insert checks if a node with a key equivalent to Key is already present
288 -- in Container. If a match is found, Inserted is set to False and Position
289 -- designates the element with the matching key. Otherwise, Insert
290 -- allocates a new node, initializes it to Key and New_Item, and adds it to
291 -- Container; Inserted is set to True and Position designates the
292 -- newly-inserted node. Any exception raised during allocation is
293 -- propagated and Container is not modified.
296 (Container
: in out Map
;
298 Position
: out Cursor
;
299 Inserted
: out Boolean);
300 -- Insert inserts Key into Container as per the five-parameter Insert, with
301 -- the difference that an element initialized by default (see 3.3.1) is
305 (Container
: in out Map
;
307 New_Item
: Element_Type
);
308 -- Insert inserts Key and New_Item into Container as per the five-parameter
309 -- Insert, with the difference that if a node with a key equivalent to Key
310 -- is already in the map, then Constraint_Error is propagated.
313 (Container
: in out Map
;
315 New_Item
: Element_Type
);
316 -- Include inserts Key and New_Item into Container as per the
317 -- five-parameter Insert, with the difference that if a node with a key
318 -- equivalent to Key is already in the map, then this operation assigns Key
319 -- and New_Item to the matching node. Any exception raised during
320 -- assignment is propagated.
323 (Container
: in out Map
;
325 New_Item
: Element_Type
);
326 -- Replace checks if a node with a key equivalent to Key is present in
327 -- Container. If a match is found, Replace assigns Key and New_Item to the
328 -- matching node; otherwise, Constraint_Error is propagated.
330 procedure Exclude
(Container
: in out Map
; Key
: Key_Type
);
331 -- Exclude checks if a node with a key equivalent to Key is present in
332 -- Container. If a match is found, Exclude removes the node from the map.
334 procedure Delete
(Container
: in out Map
; Key
: Key_Type
);
335 -- Delete checks if a node with a key equivalent to Key is present in
336 -- Container. If a match is found, Delete removes the node from the map;
337 -- otherwise, Constraint_Error is propagated.
339 procedure Delete
(Container
: in out Map
; Position
: in out Cursor
);
340 -- Delete removes the node designated by Position from the map. Position is
341 -- set to No_Element on return.
343 -- If Position equals No_Element, then Constraint_Error is propagated. If
344 -- Position does not designate an element in Container, then Program_Error
347 function First
(Container
: Map
) return Cursor
;
348 -- If Length (Container) = 0, then First returns No_Element. Otherwise,
349 -- First returns a cursor that designates the first node in Container.
351 function Next
(Position
: Cursor
) return Cursor
;
352 -- Returns a cursor that designates the successor of the node designated by
353 -- Position. If Position designates the last node, then No_Element is
354 -- returned. If Position equals No_Element, then No_Element is returned.
356 procedure Next
(Position
: in out Cursor
);
357 -- Equivalent to Position := Next (Position)
359 function Find
(Container
: Map
; Key
: Key_Type
) return Cursor
;
360 -- If Length (Container) equals 0, then Find returns No_Element.
361 -- Otherwise, Find checks if a node with a key equivalent to Key is present
362 -- in Container. If a match is found, a cursor designating the matching
363 -- node is returned; otherwise, No_Element is returned.
365 function Contains
(Container
: Map
; Key
: Key_Type
) return Boolean;
366 -- Equivalent to Find (Container, Key) /= No_Element.
368 function Element
(Container
: Map
; Key
: Key_Type
) return Element_Type
;
369 -- Equivalent to Element (Find (Container, Key))
371 function Equivalent_Keys
(Left
, Right
: Cursor
) return Boolean;
372 -- Returns the result of calling Equivalent_Keys with the keys of the nodes
373 -- designated by cursors Left and Right.
375 function Equivalent_Keys
(Left
: Cursor
; Right
: Key_Type
) return Boolean;
376 -- Returns the result of calling Equivalent_Keys with key of the node
377 -- designated by Left and key Right.
379 function Equivalent_Keys
(Left
: Key_Type
; Right
: Cursor
) return Boolean;
380 -- Returns the result of calling Equivalent_Keys with key Left and the node
381 -- designated by Right.
385 Process
: not null access procedure (Position
: Cursor
));
386 -- Iterate calls Process.all with a cursor that designates each node in
387 -- Container, starting with the first node and moving the cursor according
388 -- to the successor relation. Tampering with the cursors of Container is
389 -- prohibited during the execution of a call on Process.all. Any exception
390 -- raised by Process.all is propagated.
393 (Container
: Map
) return Map_Iterator_Interfaces
.Forward_Iterator
'Class;
397 pragma Inline
(Length
);
398 pragma Inline
(Is_Empty
);
399 pragma Inline
(Clear
);
401 pragma Inline
(Element
);
402 pragma Inline
(Move
);
403 pragma Inline
(Contains
);
404 pragma Inline
(Capacity
);
405 pragma Inline
(Reserve_Capacity
);
406 pragma Inline
(Has_Element
);
407 pragma Inline
(Equivalent_Keys
);
408 pragma Inline
(Next
);
411 type Node_Access
is access Node_Type
;
413 type Node_Type
is limited record
415 Element
: aliased Element_Type
;
420 new Hash_Tables
.Generic_Hash_Table_Types
(Node_Type
, Node_Access
);
422 type Map
is new Ada
.Finalization
.Controlled
with record
423 HT
: HT_Types
.Hash_Table_Type
;
426 overriding
procedure Adjust
(Container
: in out Map
);
428 overriding
procedure Finalize
(Container
: in out Map
);
430 use HT_Types
, HT_Types
.Implementation
;
431 use Ada
.Finalization
;
435 (Stream
: not null access Root_Stream_Type
'Class;
438 for Map
'Write use Write
;
441 (Stream
: not null access Root_Stream_Type
'Class;
442 Container
: out Map
);
444 for Map
'Read use Read
;
446 type Map_Access
is access all Map
;
447 for Map_Access
'Storage_Size use 0;
449 type Cursor
is record
450 Container
: Map_Access
;
451 -- Access to this cursor's container
454 -- Access to the node pointed to by this cursor
456 Position
: Hash_Type
:= Hash_Type
'Last;
457 -- Position of the node in the buckets of the container. If this is
458 -- equal to Hash_Type'Last, then it will not be used.
462 (Stream
: not null access Root_Stream_Type
'Class;
465 for Cursor
'Read use Read
;
468 (Stream
: not null access Root_Stream_Type
'Class;
471 for Cursor
'Write use Write
;
473 subtype Reference_Control_Type
is Implementation
.Reference_Control_Type
;
474 -- It is necessary to rename this here, so that the compiler can find it
476 type Constant_Reference_Type
477 (Element
: not null access constant Element_Type
) is
479 Control
: Reference_Control_Type
:=
480 raise Program_Error
with "uninitialized reference";
481 -- The RM says, "The default initialization of an object of
482 -- type Constant_Reference_Type or Reference_Type propagates
487 (Stream
: not null access Root_Stream_Type
'Class;
488 Item
: Constant_Reference_Type
);
490 for Constant_Reference_Type
'Write use Write
;
493 (Stream
: not null access Root_Stream_Type
'Class;
494 Item
: out Constant_Reference_Type
);
496 for Constant_Reference_Type
'Read use Read
;
499 (Element
: not null access Element_Type
) is
501 Control
: Reference_Control_Type
:=
502 raise Program_Error
with "uninitialized reference";
503 -- The RM says, "The default initialization of an object of
504 -- type Constant_Reference_Type or Reference_Type propagates
509 (Stream
: not null access Root_Stream_Type
'Class;
510 Item
: Reference_Type
);
512 for Reference_Type
'Write use Write
;
515 (Stream
: not null access Root_Stream_Type
'Class;
516 Item
: out Reference_Type
);
518 for Reference_Type
'Read use Read
;
520 -- Three operations are used to optimize in the expansion of "for ... of"
521 -- loops: the Next(Cursor) procedure in the visible part, and the following
522 -- Pseudo_Reference and Get_Element_Access functions. See Sem_Ch5 for
525 function Pseudo_Reference
526 (Container
: aliased Map
'Class) return Reference_Control_Type
;
527 pragma Inline
(Pseudo_Reference
);
528 -- Creates an object of type Reference_Control_Type pointing to the
529 -- container, and increments the Lock. Finalization of this object will
530 -- decrement the Lock.
532 type Element_Access
is access all Element_Type
with
535 function Get_Element_Access
536 (Position
: Cursor
) return not null Element_Access
;
537 -- Returns a pointer to the element designated by Position.
539 Empty_Map
: constant Map
:= (Controlled
with others => <>);
541 No_Element
: constant Cursor
:= (Container
=> null, Node
=> null,
542 Position
=> Hash_Type
'Last);
544 type Iterator
is new Limited_Controlled
and
545 Map_Iterator_Interfaces
.Forward_Iterator
with
547 Container
: Map_Access
;
549 with Disable_Controlled
=> not T_Check
;
551 overriding
procedure Finalize
(Object
: in out Iterator
);
553 overriding
function First
(Object
: Iterator
) return Cursor
;
555 overriding
function Next
557 Position
: Cursor
) return Cursor
;
559 end Ada
.Containers
.Hashed_Maps
;