]>
Commit | Line | Data |
---|---|---|
4c2d6a70 AC |
1 | ------------------------------------------------------------------------------ |
2 | -- -- | |
3 | -- GNAT LIBRARY COMPONENTS -- | |
4 | -- -- | |
15f6d6e7 | 5 | -- ADA.CONTAINERS.INDEFINITE_HASHED_MAPS -- |
4c2d6a70 AC |
6 | -- -- |
7 | -- S p e c -- | |
8 | -- -- | |
748086b7 | 9 | -- Copyright (C) 2004-2009, 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 | ||
8236f027 MH |
34 | private with Ada.Containers.Hash_Tables; |
35 | private with Ada.Streams; | |
36 | private with Ada.Finalization; | |
4c2d6a70 AC |
37 | |
38 | generic | |
39 | type Key_Type (<>) is private; | |
40 | type Element_Type (<>) is private; | |
41 | ||
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 <>; | |
45 | ||
46 | package Ada.Containers.Indefinite_Hashed_Maps is | |
009186e0 | 47 | pragma Preelaborate; |
f97ccb3a | 48 | pragma Remote_Types; |
4c2d6a70 AC |
49 | |
50 | type Map is tagged private; | |
9b832db5 RD |
51 | pragma Preelaborable_Initialization (Map); |
52 | ||
4c2d6a70 | 53 | type Cursor is private; |
9b832db5 | 54 | pragma Preelaborable_Initialization (Cursor); |
4c2d6a70 AC |
55 | |
56 | Empty_Map : constant Map; | |
8236f027 MH |
57 | -- Map objects declared without an initialization expression are |
58 | -- initialized to the value Empty_Map. | |
59 | ||
4c2d6a70 | 60 | No_Element : constant Cursor; |
8236f027 MH |
61 | -- Cursor objects declared without an initialization expression are |
62 | -- initialized to the value No_Element. | |
4c2d6a70 | 63 | |
fa969310 | 64 | overriding function "=" (Left, Right : Map) return Boolean; |
8236f027 MH |
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. | |
4c2d6a70 | 74 | |
2368f04e | 75 | function Capacity (Container : Map) return Count_Type; |
8236f027 MH |
76 | -- Returns the current capacity of the map. Capacity is the maximum length |
77 | -- before which rehashing in guaranteed not to occur. | |
78 | ||
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 | |
8fc789c8 | 82 | -- is contracted (to a value not less than the current length). If the |
8236f027 MH |
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. | |
2368f04e | 88 | |
4c2d6a70 | 89 | function Length (Container : Map) return Count_Type; |
8236f027 | 90 | -- Returns the number of items in the map |
4c2d6a70 AC |
91 | |
92 | function Is_Empty (Container : Map) return Boolean; | |
8236f027 | 93 | -- Equivalent to Length (Container) = 0 |
4c2d6a70 AC |
94 | |
95 | procedure Clear (Container : in out Map); | |
8236f027 | 96 | -- Removes all of the items from the map |
4c2d6a70 | 97 | |
8704d4b3 | 98 | function Key (Position : Cursor) return Key_Type; |
8236f027 | 99 | -- Returns the key of the node designated by the cursor |
8704d4b3 | 100 | |
4c2d6a70 | 101 | function Element (Position : Cursor) return Element_Type; |
8236f027 | 102 | -- Returns the element of the node designated by the cursor |
4c2d6a70 | 103 | |
2368f04e MH |
104 | procedure Replace_Element |
105 | (Container : in out Map; | |
106 | Position : Cursor; | |
107 | New_Item : Element_Type); | |
8236f027 | 108 | -- Assigns the value New_Item to the element designated by the cursor |
2368f04e | 109 | |
4c2d6a70 AC |
110 | procedure Query_Element |
111 | (Position : Cursor; | |
112 | Process : not null access procedure (Key : Key_Type; | |
113 | Element : Element_Type)); | |
8236f027 MH |
114 | -- Calls Process with the key and element (both having only a constant |
115 | -- view) of the node designed by the cursor. | |
4c2d6a70 AC |
116 | |
117 | procedure Update_Element | |
2368f04e MH |
118 | (Container : in out Map; |
119 | Position : Cursor; | |
120 | Process : not null access procedure (Key : Key_Type; | |
8236f027 MH |
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. | |
4c2d6a70 | 124 | |
4c2d6a70 | 125 | procedure Move (Target : in out Map; Source : in out Map); |
8236f027 MH |
126 | -- Clears Target (if it's not empty), and then moves (not copies) the |
127 | -- buckets array and nodes from Source to Target. | |
4c2d6a70 AC |
128 | |
129 | procedure Insert | |
130 | (Container : in out Map; | |
131 | Key : Key_Type; | |
132 | New_Item : Element_Type; | |
133 | Position : out Cursor; | |
134 | Inserted : out Boolean); | |
8236f027 MH |
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). | |
4c2d6a70 AC |
146 | |
147 | procedure Insert | |
148 | (Container : in out Map; | |
149 | Key : Key_Type; | |
150 | New_Item : Element_Type); | |
8236f027 MH |
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.) | |
4c2d6a70 AC |
157 | |
158 | procedure Include | |
159 | (Container : in out Map; | |
160 | Key : Key_Type; | |
161 | New_Item : Element_Type); | |
8236f027 MH |
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.) | |
4c2d6a70 AC |
168 | |
169 | procedure Replace | |
170 | (Container : in out Map; | |
171 | Key : Key_Type; | |
172 | New_Item : Element_Type); | |
8236f027 MH |
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 | |
178 | -- map.) | |
4c2d6a70 | 179 | |
2368f04e | 180 | procedure Exclude (Container : in out Map; Key : Key_Type); |
8236f027 MH |
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 | |
187 | -- in the map.) | |
4c2d6a70 | 188 | |
2368f04e | 189 | procedure Delete (Container : in out Map; Key : Key_Type); |
8236f027 MH |
190 | -- Searches for Key in the map (which involves calling both Hash and |
191 | -- Equivalent_Keys). If the search fails, then the operation raises | |
8fc789c8 | 192 | -- Constraint_Error. Otherwise it removes the node from the map and then |
8236f027 MH |
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.) | |
4c2d6a70 | 196 | |
2368f04e | 197 | procedure Delete (Container : in out Map; Position : in out Cursor); |
8236f027 MH |
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). | |
4c2d6a70 | 202 | |
4c2d6a70 | 203 | function First (Container : Map) return Cursor; |
8236f027 MH |
204 | -- Returns a cursor that designates the first non-empty bucket, by |
205 | -- searching from the beginning of the buckets array. | |
4c2d6a70 AC |
206 | |
207 | function Next (Position : Cursor) return Cursor; | |
8236f027 MH |
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. | |
4c2d6a70 AC |
214 | |
215 | procedure Next (Position : in out Cursor); | |
8236f027 | 216 | -- Equivalent to Position := Next (Position) |
4c2d6a70 | 217 | |
2368f04e | 218 | function Find (Container : Map; Key : Key_Type) return Cursor; |
8236f027 MH |
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. | |
2368f04e MH |
223 | |
224 | function Contains (Container : Map; Key : Key_Type) return Boolean; | |
8236f027 | 225 | -- Equivalent to Find (Container, Key) /= No_Element |
2368f04e MH |
226 | |
227 | function Element (Container : Map; Key : Key_Type) return Element_Type; | |
8236f027 | 228 | -- Equivalent to Element (Find (Container, Key)) |
2368f04e | 229 | |
4c2d6a70 | 230 | function Has_Element (Position : Cursor) return Boolean; |
8236f027 | 231 | -- Equivalent to Position /= No_Element |
4c2d6a70 | 232 | |
2368f04e | 233 | function Equivalent_Keys (Left, Right : Cursor) return Boolean; |
8236f027 MH |
234 | -- Returns the result of calling Equivalent_Keys with the keys of the nodes |
235 | -- designated by cursors Left and Right. | |
4c2d6a70 | 236 | |
2368f04e | 237 | function Equivalent_Keys (Left : Cursor; Right : Key_Type) return Boolean; |
8236f027 MH |
238 | -- Returns the result of calling Equivalent_Keys with key of the node |
239 | -- designated by Left and key Right. | |
4c2d6a70 | 240 | |
2368f04e | 241 | function Equivalent_Keys (Left : Key_Type; Right : Cursor) return Boolean; |
8236f027 MH |
242 | -- Returns the result of calling Equivalent_Keys with key Left and the node |
243 | -- designated by Right. | |
4c2d6a70 AC |
244 | |
245 | procedure Iterate | |
246 | (Container : Map; | |
247 | Process : not null access procedure (Position : Cursor)); | |
8236f027 | 248 | -- Calls Process for each node in the map |
4c2d6a70 AC |
249 | |
250 | private | |
8704d4b3 MH |
251 | pragma Inline ("="); |
252 | pragma Inline (Length); | |
253 | pragma Inline (Is_Empty); | |
254 | pragma Inline (Clear); | |
255 | pragma Inline (Key); | |
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); | |
f97ccb3a | 263 | pragma Inline (Next); |
8704d4b3 | 264 | |
4c2d6a70 AC |
265 | type Node_Type; |
266 | type Node_Access is access Node_Type; | |
267 | ||
8704d4b3 MH |
268 | type Key_Access is access Key_Type; |
269 | type Element_Access is access Element_Type; | |
4c2d6a70 | 270 | |
8704d4b3 MH |
271 | type Node_Type is limited record |
272 | Key : Key_Access; | |
273 | Element : Element_Access; | |
274 | Next : Node_Access; | |
275 | end record; | |
276 | ||
3c25856a AC |
277 | package HT_Types is |
278 | new Hash_Tables.Generic_Hash_Table_Types (Node_Type, Node_Access); | |
8704d4b3 MH |
279 | |
280 | type Map is new Ada.Finalization.Controlled with record | |
281 | HT : HT_Types.Hash_Table_Type; | |
282 | end record; | |
4c2d6a70 | 283 | |
8704d4b3 MH |
284 | use HT_Types; |
285 | use Ada.Finalization; | |
2368f04e | 286 | use Ada.Streams; |
4c2d6a70 | 287 | |
8236f027 | 288 | overriding |
4c2d6a70 AC |
289 | procedure Adjust (Container : in out Map); |
290 | ||
8236f027 | 291 | overriding |
4c2d6a70 AC |
292 | procedure Finalize (Container : in out Map); |
293 | ||
294 | type Map_Access is access constant Map; | |
295 | for Map_Access'Storage_Size use 0; | |
296 | ||
3c25856a AC |
297 | type Cursor is record |
298 | Container : Map_Access; | |
299 | Node : Node_Access; | |
300 | end record; | |
4c2d6a70 | 301 | |
2368f04e | 302 | procedure Write |
d90e94c7 | 303 | (Stream : not null access Root_Stream_Type'Class; |
2368f04e MH |
304 | Item : Cursor); |
305 | ||
306 | for Cursor'Write use Write; | |
307 | ||
308 | procedure Read | |
d90e94c7 | 309 | (Stream : not null access Root_Stream_Type'Class; |
2368f04e MH |
310 | Item : out Cursor); |
311 | ||
312 | for Cursor'Read use Read; | |
313 | ||
4c2d6a70 AC |
314 | No_Element : constant Cursor := |
315 | (Container => null, | |
316 | Node => null); | |
317 | ||
4c2d6a70 | 318 | procedure Write |
d90e94c7 | 319 | (Stream : not null access Root_Stream_Type'Class; |
4c2d6a70 AC |
320 | Container : Map); |
321 | ||
322 | for Map'Write use Write; | |
323 | ||
324 | procedure Read | |
d90e94c7 | 325 | (Stream : not null access Root_Stream_Type'Class; |
4c2d6a70 AC |
326 | Container : out Map); |
327 | ||
328 | for Map'Read use Read; | |
329 | ||
8704d4b3 | 330 | Empty_Map : constant Map := (Controlled with HT => (null, 0, 0, 0)); |
4c2d6a70 AC |
331 | |
332 | end Ada.Containers.Indefinite_Hashed_Maps; |