]>
Commit | Line | Data |
---|---|---|
4c2d6a70 AC |
1 | ------------------------------------------------------------------------------ |
2 | -- -- | |
3 | -- GNAT LIBRARY COMPONENTS -- | |
4 | -- -- | |
8704d4b3 | 5 | -- A D A . C O N T A I N E R S . H A S H E D _ M A P S -- |
4c2d6a70 AC |
6 | -- -- |
7 | -- S p e c -- | |
8 | -- -- | |
4b490c1e | 9 | -- Copyright (C) 2004-2020, Free Software Foundation, Inc. -- |
4c2d6a70 AC |
10 | -- -- |
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. -- | |
14 | -- -- | |
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- -- | |
748086b7 | 17 | -- ware Foundation; either version 3, or (at your option) any later ver- -- |
4c2d6a70 AC |
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 -- | |
748086b7 JJ |
20 | -- or FITNESS FOR A PARTICULAR PURPOSE. -- |
21 | -- -- | |
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. -- | |
25 | -- -- | |
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/>. -- | |
4c2d6a70 AC |
30 | -- -- |
31 | -- This unit was originally developed by Matthew J Heaney. -- | |
32 | ------------------------------------------------------------------------------ | |
33 | ||
3c24c853 MH |
34 | with Ada.Iterator_Interfaces; |
35 | ||
8236f027 | 36 | private with Ada.Containers.Hash_Tables; |
8236f027 | 37 | private with Ada.Finalization; |
3c24c853 | 38 | private with Ada.Streams; |
4c2d6a70 | 39 | |
0347c01b RA |
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 | |
44 | -- keys. | |
45 | -- | |
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 | |
52 | -- contains. | |
53 | -- | |
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. | |
59 | ||
4c2d6a70 AC |
60 | generic |
61 | type Key_Type is private; | |
4c2d6a70 AC |
62 | type Element_Type is private; |
63 | ||
64 | with function Hash (Key : Key_Type) return Hash_Type; | |
0347c01b RA |
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, | |
71 | -- is unspecified. | |
72 | ||
4c2d6a70 | 73 | with function Equivalent_Keys (Left, Right : Key_Type) return Boolean; |
0347c01b RA |
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, | |
81 | -- is unspecified. | |
4c2d6a70 | 82 | |
0347c01b RA |
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. | |
4c2d6a70 | 91 | package Ada.Containers.Hashed_Maps is |
6031f544 | 92 | pragma Annotate (CodePeer, Skip_Analysis); |
009186e0 | 93 | pragma Preelaborate; |
f97ccb3a | 94 | pragma Remote_Types; |
4c2d6a70 | 95 | |
3e24afaa AC |
96 | type Map is tagged private |
97 | with | |
98 | Constant_Indexing => Constant_Reference, | |
99 | Variable_Indexing => Reference, | |
100 | Default_Iterator => Iterate, | |
101 | Iterator_Element => Element_Type; | |
102 | ||
9b832db5 | 103 | pragma Preelaborable_Initialization (Map); |
4c2d6a70 AC |
104 | |
105 | type Cursor is private; | |
9b832db5 | 106 | pragma Preelaborable_Initialization (Cursor); |
4c2d6a70 AC |
107 | |
108 | Empty_Map : constant Map; | |
8236f027 MH |
109 | -- Map objects declared without an initialization expression are |
110 | -- initialized to the value Empty_Map. | |
4c2d6a70 AC |
111 | |
112 | No_Element : constant Cursor; | |
8236f027 MH |
113 | -- Cursor objects declared without an initialization expression are |
114 | -- initialized to the value No_Element. | |
4c2d6a70 | 115 | |
3e24afaa | 116 | function Has_Element (Position : Cursor) return Boolean; |
0347c01b RA |
117 | -- Returns True if Position designates an element, and returns False |
118 | -- otherwise. | |
3e24afaa AC |
119 | |
120 | package Map_Iterator_Interfaces is new | |
121 | Ada.Iterator_Interfaces (Cursor, Has_Element); | |
122 | ||
4c2d6a70 | 123 | function "=" (Left, Right : Map) return Boolean; |
0347c01b RA |
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 | |
127 | -- False if: | |
128 | -- | |
129 | -- * a key equivalent to K is not present in Right; or | |
130 | -- | |
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). | |
134 | -- | |
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. | |
4c2d6a70 | 138 | |
2368f04e | 139 | function Capacity (Container : Map) return Count_Type; |
8236f027 MH |
140 | -- Returns the current capacity of the map. Capacity is the maximum length |
141 | -- before which rehashing in guaranteed not to occur. | |
142 | ||
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 | |
8fc789c8 | 146 | -- is contracted (to a value not less than the current length). If the |
8236f027 MH |
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. | |
2368f04e | 152 | |
4c2d6a70 | 153 | function Length (Container : Map) return Count_Type; |
8236f027 | 154 | -- Returns the number of items in the map |
4c2d6a70 AC |
155 | |
156 | function Is_Empty (Container : Map) return Boolean; | |
8236f027 | 157 | -- Equivalent to Length (Container) = 0 |
4c2d6a70 AC |
158 | |
159 | procedure Clear (Container : in out Map); | |
8236f027 | 160 | -- Removes all of the items from the map |
4c2d6a70 | 161 | |
8704d4b3 | 162 | function Key (Position : Cursor) return Key_Type; |
0347c01b RA |
163 | -- Key returns the key component of the node designated by Position. |
164 | -- | |
165 | -- If Position equals No_Element, then Constraint_Error is propagated. | |
8704d4b3 MH |
166 | |
167 | function Element (Position : Cursor) return Element_Type; | |
0347c01b RA |
168 | -- Element returns the element component of the node designated |
169 | -- by Position. | |
170 | -- | |
171 | -- If Position equals No_Element, then Constraint_Error is propagated. | |
4c2d6a70 | 172 | |
2368f04e MH |
173 | procedure Replace_Element |
174 | (Container : in out Map; | |
175 | Position : Cursor; | |
176 | New_Item : Element_Type); | |
0347c01b RA |
177 | -- Replace_Element assigns New_Item to the element of the node designated |
178 | -- by Position. | |
179 | -- | |
180 | -- If Position equals No_Element, then Constraint_Error is propagated; if | |
181 | -- Position does not designate an element in Container, then Program_Error | |
182 | -- is propagated. | |
2368f04e | 183 | |
4c2d6a70 AC |
184 | procedure Query_Element |
185 | (Position : Cursor; | |
186 | Process : not null access | |
187 | procedure (Key : Key_Type; Element : Element_Type)); | |
0347c01b RA |
188 | -- Query_Element calls Process.all with the key and element from the node |
189 | -- designated by Position as the arguments. | |
190 | -- | |
191 | -- If Position equals No_Element, then Constraint_Error is propagated. | |
192 | -- | |
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. | |
4c2d6a70 AC |
196 | |
197 | procedure Update_Element | |
2368f04e MH |
198 | (Container : in out Map; |
199 | Position : Cursor; | |
200 | Process : not null access | |
8236f027 | 201 | procedure (Key : Key_Type; Element : in out Element_Type)); |
0347c01b RA |
202 | -- Update_Element calls Process.all with the key and element from the node |
203 | -- designated by Position as the arguments. | |
204 | -- | |
205 | -- If Position equals No_Element, then Constraint_Error is propagated; if | |
206 | -- Position does not designate an element in Container, then Program_Error | |
207 | -- is propagated. | |
208 | -- | |
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. | |
4c2d6a70 | 212 | |
c9423ca3 AC |
213 | type Constant_Reference_Type |
214 | (Element : not null access constant Element_Type) is private | |
215 | with | |
216 | Implicit_Dereference => Element; | |
217 | ||
c9423ca3 AC |
218 | type Reference_Type (Element : not null access Element_Type) is private |
219 | with | |
220 | Implicit_Dereference => Element; | |
221 | ||
c9423ca3 AC |
222 | function Constant_Reference |
223 | (Container : aliased Map; | |
224 | Position : Cursor) return Constant_Reference_Type; | |
794b9b72 | 225 | pragma Inline (Constant_Reference); |
0347c01b RA |
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. | |
231 | -- | |
232 | -- If Position equals No_Element, then Constraint_Error is propagated; if | |
233 | -- Position does not designate an element in Container, then Program_Error | |
234 | -- is propagated. | |
235 | -- | |
236 | -- Tampering with the elements of Container is prohibited | |
237 | -- while the object returned by Constant_Reference exists and has not been | |
238 | -- finalized. | |
c9423ca3 AC |
239 | |
240 | function Reference | |
241 | (Container : aliased in out Map; | |
242 | Position : Cursor) return Reference_Type; | |
794b9b72 | 243 | pragma Inline (Reference); |
0347c01b RA |
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. | |
249 | -- | |
250 | -- If Position equals No_Element, then Constraint_Error is propagated; if | |
251 | -- Position does not designate an element in Container, then Program_Error | |
252 | -- is propagated. | |
253 | -- | |
254 | -- Tampering with the elements of Container is prohibited while the object | |
255 | -- returned by Reference exists and has not been finalized. | |
c9423ca3 AC |
256 | |
257 | function Constant_Reference | |
258 | (Container : aliased Map; | |
259 | Key : Key_Type) return Constant_Reference_Type; | |
794b9b72 | 260 | pragma Inline (Constant_Reference); |
0347c01b | 261 | -- Equivalent to Constant_Reference (Container, Find (Container, Key)). |
c9423ca3 AC |
262 | |
263 | function Reference | |
264 | (Container : aliased in out Map; | |
265 | Key : Key_Type) return Reference_Type; | |
794b9b72 | 266 | pragma Inline (Reference); |
0347c01b | 267 | -- Equivalent to Reference (Container, Find (Container, Key)). |
c9423ca3 | 268 | |
a31945d7 | 269 | procedure Assign (Target : in out Map; Source : Map); |
0347c01b RA |
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. | |
a31945d7 AC |
273 | |
274 | function Copy (Source : Map; Capacity : Count_Type := 0) return Map; | |
275 | ||
4c2d6a70 | 276 | procedure Move (Target : in out Map; Source : in out Map); |
0347c01b RA |
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). | |
4c2d6a70 AC |
280 | |
281 | procedure Insert | |
282 | (Container : in out Map; | |
283 | Key : Key_Type; | |
284 | New_Item : Element_Type; | |
285 | Position : out Cursor; | |
286 | Inserted : out Boolean); | |
0347c01b RA |
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. | |
4c2d6a70 AC |
294 | |
295 | procedure Insert | |
296 | (Container : in out Map; | |
297 | Key : Key_Type; | |
8704d4b3 MH |
298 | Position : out Cursor; |
299 | Inserted : out Boolean); | |
0347c01b RA |
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 | |
302 | -- inserted. | |
4c2d6a70 | 303 | |
8704d4b3 | 304 | procedure Insert |
4c2d6a70 AC |
305 | (Container : in out Map; |
306 | Key : Key_Type; | |
307 | New_Item : Element_Type); | |
0347c01b RA |
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. | |
4c2d6a70 | 311 | |
8704d4b3 | 312 | procedure Include |
4c2d6a70 AC |
313 | (Container : in out Map; |
314 | Key : Key_Type; | |
315 | New_Item : Element_Type); | |
0347c01b RA |
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. | |
4c2d6a70 | 321 | |
8704d4b3 | 322 | procedure Replace |
4c2d6a70 AC |
323 | (Container : in out Map; |
324 | Key : Key_Type; | |
8704d4b3 | 325 | New_Item : Element_Type); |
0347c01b RA |
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. | |
4c2d6a70 | 329 | |
8704d4b3 | 330 | procedure Exclude (Container : in out Map; Key : Key_Type); |
0347c01b RA |
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. | |
8704d4b3 | 333 | |
2368f04e | 334 | procedure Delete (Container : in out Map; Key : Key_Type); |
0347c01b RA |
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. | |
4c2d6a70 | 338 | |
2368f04e | 339 | procedure Delete (Container : in out Map; Position : in out Cursor); |
0347c01b RA |
340 | -- Delete removes the node designated by Position from the map. Position is |
341 | -- set to No_Element on return. | |
342 | -- | |
343 | -- If Position equals No_Element, then Constraint_Error is propagated. If | |
344 | -- Position does not designate an element in Container, then Program_Error | |
345 | -- is propagated. | |
4c2d6a70 | 346 | |
4c2d6a70 | 347 | function First (Container : Map) return Cursor; |
0347c01b RA |
348 | -- If Length (Container) = 0, then First returns No_Element. Otherwise, |
349 | -- First returns a cursor that designates the first node in Container. | |
4c2d6a70 AC |
350 | |
351 | function Next (Position : Cursor) return Cursor; | |
0347c01b RA |
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. | |
4c2d6a70 AC |
355 | |
356 | procedure Next (Position : in out Cursor); | |
8236f027 | 357 | -- Equivalent to Position := Next (Position) |
4c2d6a70 | 358 | |
2368f04e | 359 | function Find (Container : Map; Key : Key_Type) return Cursor; |
0347c01b RA |
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. | |
2368f04e MH |
364 | |
365 | function Contains (Container : Map; Key : Key_Type) return Boolean; | |
0347c01b | 366 | -- Equivalent to Find (Container, Key) /= No_Element. |
2368f04e MH |
367 | |
368 | function Element (Container : Map; Key : Key_Type) return Element_Type; | |
8236f027 | 369 | -- Equivalent to Element (Find (Container, Key)) |
2368f04e | 370 | |
4c2d6a70 | 371 | function Equivalent_Keys (Left, Right : Cursor) return Boolean; |
8236f027 MH |
372 | -- Returns the result of calling Equivalent_Keys with the keys of the nodes |
373 | -- designated by cursors Left and Right. | |
4c2d6a70 AC |
374 | |
375 | function Equivalent_Keys (Left : Cursor; Right : Key_Type) return Boolean; | |
8236f027 MH |
376 | -- Returns the result of calling Equivalent_Keys with key of the node |
377 | -- designated by Left and key Right. | |
4c2d6a70 AC |
378 | |
379 | function Equivalent_Keys (Left : Key_Type; Right : Cursor) return Boolean; | |
8236f027 MH |
380 | -- Returns the result of calling Equivalent_Keys with key Left and the node |
381 | -- designated by Right. | |
4c2d6a70 AC |
382 | |
383 | procedure Iterate | |
384 | (Container : Map; | |
385 | Process : not null access procedure (Position : Cursor)); | |
0347c01b RA |
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. | |
4c2d6a70 | 391 | |
b5bf3335 | 392 | function Iterate |
ee935273 | 393 | (Container : Map) return Map_Iterator_Interfaces.Forward_Iterator'Class; |
3e24afaa | 394 | |
4c2d6a70 | 395 | private |
8704d4b3 MH |
396 | pragma Inline ("="); |
397 | pragma Inline (Length); | |
398 | pragma Inline (Is_Empty); | |
399 | pragma Inline (Clear); | |
400 | pragma Inline (Key); | |
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); | |
f97ccb3a | 408 | pragma Inline (Next); |
4c2d6a70 AC |
409 | |
410 | type Node_Type; | |
411 | type Node_Access is access Node_Type; | |
412 | ||
8704d4b3 MH |
413 | type Node_Type is limited record |
414 | Key : Key_Type; | |
c9423ca3 | 415 | Element : aliased Element_Type; |
8704d4b3 MH |
416 | Next : Node_Access; |
417 | end record; | |
4c2d6a70 | 418 | |
3c25856a AC |
419 | package HT_Types is |
420 | new Hash_Tables.Generic_Hash_Table_Types (Node_Type, Node_Access); | |
4c2d6a70 | 421 | |
8704d4b3 MH |
422 | type Map is new Ada.Finalization.Controlled with record |
423 | HT : HT_Types.Hash_Table_Type; | |
424 | end record; | |
425 | ||
607d0635 | 426 | overriding procedure Adjust (Container : in out Map); |
4c2d6a70 | 427 | |
607d0635 | 428 | overriding procedure Finalize (Container : in out Map); |
4c2d6a70 | 429 | |
14f73211 | 430 | use HT_Types, HT_Types.Implementation; |
3c24c853 MH |
431 | use Ada.Finalization; |
432 | use Ada.Streams; | |
433 | ||
4c2d6a70 | 434 | procedure Write |
d90e94c7 | 435 | (Stream : not null access Root_Stream_Type'Class; |
4c2d6a70 AC |
436 | Container : Map); |
437 | ||
438 | for Map'Write use Write; | |
439 | ||
440 | procedure Read | |
d90e94c7 | 441 | (Stream : not null access Root_Stream_Type'Class; |
4c2d6a70 AC |
442 | Container : out Map); |
443 | ||
444 | for Map'Read use Read; | |
445 | ||
ef992452 | 446 | type Map_Access is access all Map; |
4c2d6a70 AC |
447 | for Map_Access'Storage_Size use 0; |
448 | ||
3c25856a AC |
449 | type Cursor is record |
450 | Container : Map_Access; | |
f8159014 AC |
451 | -- Access to this cursor's container |
452 | ||
3c25856a | 453 | Node : Node_Access; |
f8159014 AC |
454 | -- Access to the node pointed to by this cursor |
455 | ||
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. | |
3c25856a | 459 | end record; |
4c2d6a70 | 460 | |
3c24c853 MH |
461 | procedure Read |
462 | (Stream : not null access Root_Stream_Type'Class; | |
463 | Item : out Cursor); | |
464 | ||
465 | for Cursor'Read use Read; | |
466 | ||
467 | procedure Write | |
468 | (Stream : not null access Root_Stream_Type'Class; | |
469 | Item : Cursor); | |
470 | ||
471 | for Cursor'Write use Write; | |
472 | ||
14f73211 BD |
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 | |
794b9b72 | 475 | |
3e24afaa | 476 | type Constant_Reference_Type |
db222ead | 477 | (Element : not null access constant Element_Type) is |
794b9b72 | 478 | record |
db222ead AC |
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 | |
483 | -- Program_Error." | |
794b9b72 | 484 | end record; |
2368f04e | 485 | |
3c24c853 MH |
486 | procedure Write |
487 | (Stream : not null access Root_Stream_Type'Class; | |
488 | Item : Constant_Reference_Type); | |
489 | ||
490 | for Constant_Reference_Type'Write use Write; | |
491 | ||
492 | procedure Read | |
493 | (Stream : not null access Root_Stream_Type'Class; | |
494 | Item : out Constant_Reference_Type); | |
495 | ||
496 | for Constant_Reference_Type'Read use Read; | |
497 | ||
3e24afaa | 498 | type Reference_Type |
db222ead | 499 | (Element : not null access Element_Type) is |
794b9b72 | 500 | record |
db222ead AC |
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 | |
505 | -- Program_Error." | |
794b9b72 | 506 | end record; |
7cdc672b | 507 | |
3c24c853 MH |
508 | procedure Write |
509 | (Stream : not null access Root_Stream_Type'Class; | |
510 | Item : Reference_Type); | |
511 | ||
512 | for Reference_Type'Write use Write; | |
513 | ||
514 | procedure Read | |
515 | (Stream : not null access Root_Stream_Type'Class; | |
516 | Item : out Reference_Type); | |
517 | ||
518 | for Reference_Type'Read use Read; | |
519 | ||
ee935273 AC |
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 | |
523 | -- details. | |
524 | ||
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. | |
531 | ||
14f73211 BD |
532 | type Element_Access is access all Element_Type with |
533 | Storage_Size => 0; | |
ee935273 AC |
534 | |
535 | function Get_Element_Access | |
536 | (Position : Cursor) return not null Element_Access; | |
537 | -- Returns a pointer to the element designated by Position. | |
538 | ||
14f73211 | 539 | Empty_Map : constant Map := (Controlled with others => <>); |
7d2e68b3 | 540 | |
f8159014 AC |
541 | No_Element : constant Cursor := (Container => null, Node => null, |
542 | Position => Hash_Type'Last); | |
4c2d6a70 | 543 | |
e2441021 AC |
544 | type Iterator is new Limited_Controlled and |
545 | Map_Iterator_Interfaces.Forward_Iterator with | |
546 | record | |
547 | Container : Map_Access; | |
14f73211 BD |
548 | end record |
549 | with Disable_Controlled => not T_Check; | |
e2441021 AC |
550 | |
551 | overriding procedure Finalize (Object : in out Iterator); | |
552 | ||
553 | overriding function First (Object : Iterator) return Cursor; | |
554 | ||
555 | overriding function Next | |
556 | (Object : Iterator; | |
557 | Position : Cursor) return Cursor; | |
558 | ||
4c2d6a70 | 559 | end Ada.Containers.Hashed_Maps; |