111
|
1 ------------------------------------------------------------------------------
|
|
2 -- --
|
|
3 -- GNAT LIBRARY COMPONENTS --
|
|
4 -- --
|
|
5 -- A D A . C O N T A I N E R S . H A S H E D _ M A P S --
|
|
6 -- --
|
|
7 -- B o d y --
|
|
8 -- --
|
145
|
9 -- Copyright (C) 2004-2019, Free Software Foundation, Inc. --
|
111
|
10 -- --
|
|
11 -- GNAT is free software; you can redistribute it and/or modify it under --
|
|
12 -- terms of the GNU General Public License as published by the Free Soft- --
|
|
13 -- ware Foundation; either version 3, or (at your option) any later ver- --
|
|
14 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
|
|
15 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
|
|
16 -- or FITNESS FOR A PARTICULAR PURPOSE. --
|
|
17 -- --
|
|
18 -- As a special exception under Section 7 of GPL version 3, you are granted --
|
|
19 -- additional permissions described in the GCC Runtime Library Exception, --
|
|
20 -- version 3.1, as published by the Free Software Foundation. --
|
|
21 -- --
|
|
22 -- You should have received a copy of the GNU General Public License and --
|
|
23 -- a copy of the GCC Runtime Library Exception along with this program; --
|
|
24 -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
|
|
25 -- <http://www.gnu.org/licenses/>. --
|
|
26 -- --
|
|
27 -- This unit was originally developed by Matthew J Heaney. --
|
|
28 ------------------------------------------------------------------------------
|
|
29
|
|
30 with Ada.Unchecked_Deallocation;
|
|
31
|
|
32 with Ada.Containers.Hash_Tables.Generic_Operations;
|
|
33 pragma Elaborate_All (Ada.Containers.Hash_Tables.Generic_Operations);
|
|
34
|
|
35 with Ada.Containers.Hash_Tables.Generic_Keys;
|
|
36 pragma Elaborate_All (Ada.Containers.Hash_Tables.Generic_Keys);
|
|
37
|
|
38 with Ada.Containers.Helpers; use Ada.Containers.Helpers;
|
|
39
|
|
40 with System; use type System.Address;
|
|
41
|
|
42 package body Ada.Containers.Hashed_Maps is
|
|
43
|
|
44 pragma Warnings (Off, "variable ""Busy*"" is not referenced");
|
|
45 pragma Warnings (Off, "variable ""Lock*"" is not referenced");
|
|
46 -- See comment in Ada.Containers.Helpers
|
|
47
|
|
48 -----------------------
|
|
49 -- Local Subprograms --
|
|
50 -----------------------
|
|
51
|
|
52 function Copy_Node
|
|
53 (Source : Node_Access) return Node_Access;
|
|
54 pragma Inline (Copy_Node);
|
|
55
|
|
56 function Equivalent_Key_Node
|
|
57 (Key : Key_Type;
|
|
58 Node : Node_Access) return Boolean;
|
|
59 pragma Inline (Equivalent_Key_Node);
|
|
60
|
|
61 procedure Free (X : in out Node_Access);
|
|
62
|
|
63 function Find_Equal_Key
|
|
64 (R_HT : Hash_Table_Type;
|
|
65 L_Node : Node_Access) return Boolean;
|
|
66
|
|
67 function Hash_Node (Node : Node_Access) return Hash_Type;
|
|
68 pragma Inline (Hash_Node);
|
|
69
|
|
70 function Next (Node : Node_Access) return Node_Access;
|
|
71 pragma Inline (Next);
|
|
72
|
|
73 function Read_Node
|
|
74 (Stream : not null access Root_Stream_Type'Class) return Node_Access;
|
|
75 pragma Inline (Read_Node);
|
|
76
|
|
77 procedure Set_Next (Node : Node_Access; Next : Node_Access);
|
|
78 pragma Inline (Set_Next);
|
|
79
|
|
80 function Vet (Position : Cursor) return Boolean;
|
|
81
|
|
82 procedure Write_Node
|
|
83 (Stream : not null access Root_Stream_Type'Class;
|
|
84 Node : Node_Access);
|
|
85 pragma Inline (Write_Node);
|
|
86
|
|
87 --------------------------
|
|
88 -- Local Instantiations --
|
|
89 --------------------------
|
|
90
|
|
91 package HT_Ops is new Hash_Tables.Generic_Operations
|
|
92 (HT_Types => HT_Types,
|
|
93 Hash_Node => Hash_Node,
|
|
94 Next => Next,
|
|
95 Set_Next => Set_Next,
|
|
96 Copy_Node => Copy_Node,
|
|
97 Free => Free);
|
|
98
|
|
99 package Key_Ops is new Hash_Tables.Generic_Keys
|
|
100 (HT_Types => HT_Types,
|
|
101 Next => Next,
|
|
102 Set_Next => Set_Next,
|
|
103 Key_Type => Key_Type,
|
|
104 Hash => Hash,
|
|
105 Equivalent_Keys => Equivalent_Key_Node);
|
|
106
|
|
107 function Is_Equal is new HT_Ops.Generic_Equal (Find_Equal_Key);
|
|
108
|
|
109 procedure Read_Nodes is new HT_Ops.Generic_Read (Read_Node);
|
|
110 procedure Write_Nodes is new HT_Ops.Generic_Write (Write_Node);
|
|
111
|
|
112 ---------
|
|
113 -- "=" --
|
|
114 ---------
|
|
115
|
|
116 function "=" (Left, Right : Map) return Boolean is
|
|
117 begin
|
|
118 return Is_Equal (Left.HT, Right.HT);
|
|
119 end "=";
|
|
120
|
|
121 ------------
|
|
122 -- Adjust --
|
|
123 ------------
|
|
124
|
|
125 procedure Adjust (Container : in out Map) is
|
|
126 begin
|
|
127 HT_Ops.Adjust (Container.HT);
|
|
128 end Adjust;
|
|
129
|
|
130 ------------
|
|
131 -- Assign --
|
|
132 ------------
|
|
133
|
|
134 procedure Assign (Target : in out Map; Source : Map) is
|
|
135 procedure Insert_Item (Node : Node_Access);
|
|
136 pragma Inline (Insert_Item);
|
|
137
|
|
138 procedure Insert_Items is new HT_Ops.Generic_Iteration (Insert_Item);
|
|
139
|
|
140 -----------------
|
|
141 -- Insert_Item --
|
|
142 -----------------
|
|
143
|
|
144 procedure Insert_Item (Node : Node_Access) is
|
|
145 begin
|
|
146 Target.Insert (Key => Node.Key, New_Item => Node.Element);
|
|
147 end Insert_Item;
|
|
148
|
|
149 -- Start of processing for Assign
|
|
150
|
|
151 begin
|
|
152 if Target'Address = Source'Address then
|
|
153 return;
|
|
154 end if;
|
|
155
|
|
156 Target.Clear;
|
|
157
|
|
158 if Target.Capacity < Source.Length then
|
|
159 Target.Reserve_Capacity (Source.Length);
|
|
160 end if;
|
|
161
|
|
162 Insert_Items (Source.HT);
|
|
163 end Assign;
|
|
164
|
|
165 --------------
|
|
166 -- Capacity --
|
|
167 --------------
|
|
168
|
|
169 function Capacity (Container : Map) return Count_Type is
|
|
170 begin
|
|
171 return HT_Ops.Capacity (Container.HT);
|
|
172 end Capacity;
|
|
173
|
|
174 -----------
|
|
175 -- Clear --
|
|
176 -----------
|
|
177
|
|
178 procedure Clear (Container : in out Map) is
|
|
179 begin
|
|
180 HT_Ops.Clear (Container.HT);
|
|
181 end Clear;
|
|
182
|
|
183 ------------------------
|
|
184 -- Constant_Reference --
|
|
185 ------------------------
|
|
186
|
|
187 function Constant_Reference
|
|
188 (Container : aliased Map;
|
|
189 Position : Cursor) return Constant_Reference_Type
|
|
190 is
|
|
191 begin
|
|
192 if Checks and then Position.Container = null then
|
|
193 raise Constraint_Error with
|
|
194 "Position cursor has no element";
|
|
195 end if;
|
|
196
|
|
197 if Checks and then Position.Container /= Container'Unrestricted_Access
|
|
198 then
|
|
199 raise Program_Error with
|
|
200 "Position cursor designates wrong map";
|
|
201 end if;
|
|
202
|
|
203 pragma Assert
|
|
204 (Vet (Position),
|
|
205 "Position cursor in Constant_Reference is bad");
|
|
206
|
|
207 declare
|
|
208 HT : Hash_Table_Type renames Container'Unrestricted_Access.all.HT;
|
|
209 TC : constant Tamper_Counts_Access :=
|
|
210 HT.TC'Unrestricted_Access;
|
|
211 begin
|
|
212 return R : constant Constant_Reference_Type :=
|
|
213 (Element => Position.Node.Element'Access,
|
|
214 Control => (Controlled with TC))
|
|
215 do
|
145
|
216 Busy (TC.all);
|
111
|
217 end return;
|
|
218 end;
|
|
219 end Constant_Reference;
|
|
220
|
|
221 function Constant_Reference
|
|
222 (Container : aliased Map;
|
|
223 Key : Key_Type) return Constant_Reference_Type
|
|
224 is
|
|
225 HT : Hash_Table_Type renames Container'Unrestricted_Access.HT;
|
|
226 Node : constant Node_Access := Key_Ops.Find (HT, Key);
|
|
227
|
|
228 begin
|
|
229 if Checks and then Node = null then
|
|
230 raise Constraint_Error with "key not in map";
|
|
231 end if;
|
|
232
|
|
233 declare
|
|
234 TC : constant Tamper_Counts_Access :=
|
|
235 HT.TC'Unrestricted_Access;
|
|
236 begin
|
|
237 return R : constant Constant_Reference_Type :=
|
|
238 (Element => Node.Element'Access,
|
|
239 Control => (Controlled with TC))
|
|
240 do
|
145
|
241 Busy (TC.all);
|
111
|
242 end return;
|
|
243 end;
|
|
244 end Constant_Reference;
|
|
245
|
|
246 --------------
|
|
247 -- Contains --
|
|
248 --------------
|
|
249
|
|
250 function Contains (Container : Map; Key : Key_Type) return Boolean is
|
|
251 begin
|
|
252 return Find (Container, Key) /= No_Element;
|
|
253 end Contains;
|
|
254
|
|
255 ----------
|
|
256 -- Copy --
|
|
257 ----------
|
|
258
|
|
259 function Copy
|
|
260 (Source : Map;
|
|
261 Capacity : Count_Type := 0) return Map
|
|
262 is
|
|
263 C : Count_Type;
|
|
264
|
|
265 begin
|
|
266 if Capacity < Source.Length then
|
|
267 if Checks and then Capacity /= 0 then
|
|
268 raise Capacity_Error
|
|
269 with "Requested capacity is less than Source length";
|
|
270 end if;
|
|
271
|
|
272 C := Source.Length;
|
|
273 else
|
|
274 C := Capacity;
|
|
275 end if;
|
|
276
|
|
277 return Target : Map do
|
|
278 Target.Reserve_Capacity (C);
|
|
279 Target.Assign (Source);
|
|
280 end return;
|
|
281 end Copy;
|
|
282
|
|
283 ---------------
|
|
284 -- Copy_Node --
|
|
285 ---------------
|
|
286
|
|
287 function Copy_Node
|
|
288 (Source : Node_Access) return Node_Access
|
|
289 is
|
|
290 Target : constant Node_Access :=
|
|
291 new Node_Type'(Key => Source.Key,
|
|
292 Element => Source.Element,
|
|
293 Next => null);
|
|
294 begin
|
|
295 return Target;
|
|
296 end Copy_Node;
|
|
297
|
|
298 ------------
|
|
299 -- Delete --
|
|
300 ------------
|
|
301
|
|
302 procedure Delete (Container : in out Map; Key : Key_Type) is
|
|
303 X : Node_Access;
|
|
304
|
|
305 begin
|
|
306 Key_Ops.Delete_Key_Sans_Free (Container.HT, Key, X);
|
|
307
|
|
308 if Checks and then X = null then
|
|
309 raise Constraint_Error with "attempt to delete key not in map";
|
|
310 end if;
|
|
311
|
|
312 Free (X);
|
|
313 end Delete;
|
|
314
|
|
315 procedure Delete (Container : in out Map; Position : in out Cursor) is
|
|
316 begin
|
|
317 if Checks and then Position.Node = null then
|
|
318 raise Constraint_Error with
|
|
319 "Position cursor of Delete equals No_Element";
|
|
320 end if;
|
|
321
|
|
322 if Checks and then Position.Container /= Container'Unrestricted_Access
|
|
323 then
|
|
324 raise Program_Error with
|
|
325 "Position cursor of Delete designates wrong map";
|
|
326 end if;
|
|
327
|
|
328 TC_Check (Container.HT.TC);
|
|
329
|
|
330 pragma Assert (Vet (Position), "bad cursor in Delete");
|
|
331
|
|
332 HT_Ops.Delete_Node_Sans_Free (Container.HT, Position.Node);
|
|
333
|
|
334 Free (Position.Node);
|
|
335 Position.Container := null;
|
|
336 end Delete;
|
|
337
|
|
338 -------------
|
|
339 -- Element --
|
|
340 -------------
|
|
341
|
|
342 function Element (Container : Map; Key : Key_Type) return Element_Type is
|
|
343 HT : Hash_Table_Type renames Container'Unrestricted_Access.HT;
|
|
344 Node : constant Node_Access := Key_Ops.Find (HT, Key);
|
|
345
|
|
346 begin
|
|
347 if Checks and then Node = null then
|
|
348 raise Constraint_Error with
|
|
349 "no element available because key not in map";
|
|
350 end if;
|
|
351
|
|
352 return Node.Element;
|
|
353 end Element;
|
|
354
|
|
355 function Element (Position : Cursor) return Element_Type is
|
|
356 begin
|
|
357 if Checks and then Position.Node = null then
|
|
358 raise Constraint_Error with
|
|
359 "Position cursor of function Element equals No_Element";
|
|
360 end if;
|
|
361
|
|
362 pragma Assert (Vet (Position), "bad cursor in function Element");
|
|
363
|
|
364 return Position.Node.Element;
|
|
365 end Element;
|
|
366
|
|
367 -------------------------
|
|
368 -- Equivalent_Key_Node --
|
|
369 -------------------------
|
|
370
|
|
371 function Equivalent_Key_Node
|
|
372 (Key : Key_Type;
|
|
373 Node : Node_Access) return Boolean is
|
|
374 begin
|
|
375 return Equivalent_Keys (Key, Node.Key);
|
|
376 end Equivalent_Key_Node;
|
|
377
|
|
378 ---------------------
|
|
379 -- Equivalent_Keys --
|
|
380 ---------------------
|
|
381
|
|
382 function Equivalent_Keys (Left, Right : Cursor)
|
|
383 return Boolean is
|
|
384 begin
|
|
385 if Checks and then Left.Node = null then
|
|
386 raise Constraint_Error with
|
|
387 "Left cursor of Equivalent_Keys equals No_Element";
|
|
388 end if;
|
|
389
|
|
390 if Checks and then Right.Node = null then
|
|
391 raise Constraint_Error with
|
|
392 "Right cursor of Equivalent_Keys equals No_Element";
|
|
393 end if;
|
|
394
|
|
395 pragma Assert (Vet (Left), "Left cursor of Equivalent_Keys is bad");
|
|
396 pragma Assert (Vet (Right), "Right cursor of Equivalent_Keys is bad");
|
|
397
|
|
398 return Equivalent_Keys (Left.Node.Key, Right.Node.Key);
|
|
399 end Equivalent_Keys;
|
|
400
|
|
401 function Equivalent_Keys (Left : Cursor; Right : Key_Type) return Boolean is
|
|
402 begin
|
|
403 if Checks and then Left.Node = null then
|
|
404 raise Constraint_Error with
|
|
405 "Left cursor of Equivalent_Keys equals No_Element";
|
|
406 end if;
|
|
407
|
|
408 pragma Assert (Vet (Left), "Left cursor in Equivalent_Keys is bad");
|
|
409
|
|
410 return Equivalent_Keys (Left.Node.Key, Right);
|
|
411 end Equivalent_Keys;
|
|
412
|
|
413 function Equivalent_Keys (Left : Key_Type; Right : Cursor) return Boolean is
|
|
414 begin
|
|
415 if Checks and then Right.Node = null then
|
|
416 raise Constraint_Error with
|
|
417 "Right cursor of Equivalent_Keys equals No_Element";
|
|
418 end if;
|
|
419
|
|
420 pragma Assert (Vet (Right), "Right cursor of Equivalent_Keys is bad");
|
|
421
|
|
422 return Equivalent_Keys (Left, Right.Node.Key);
|
|
423 end Equivalent_Keys;
|
|
424
|
|
425 -------------
|
|
426 -- Exclude --
|
|
427 -------------
|
|
428
|
|
429 procedure Exclude (Container : in out Map; Key : Key_Type) is
|
|
430 X : Node_Access;
|
|
431 begin
|
|
432 Key_Ops.Delete_Key_Sans_Free (Container.HT, Key, X);
|
|
433 Free (X);
|
|
434 end Exclude;
|
|
435
|
|
436 --------------
|
|
437 -- Finalize --
|
|
438 --------------
|
|
439
|
|
440 procedure Finalize (Container : in out Map) is
|
|
441 begin
|
|
442 HT_Ops.Finalize (Container.HT);
|
|
443 end Finalize;
|
|
444
|
|
445 procedure Finalize (Object : in out Iterator) is
|
|
446 begin
|
|
447 if Object.Container /= null then
|
|
448 Unbusy (Object.Container.HT.TC);
|
|
449 end if;
|
|
450 end Finalize;
|
|
451
|
|
452 ----------
|
|
453 -- Find --
|
|
454 ----------
|
|
455
|
|
456 function Find (Container : Map; Key : Key_Type) return Cursor is
|
|
457 HT : Hash_Table_Type renames Container'Unrestricted_Access.HT;
|
|
458 Node : constant Node_Access := Key_Ops.Find (HT, Key);
|
|
459
|
|
460 begin
|
|
461 if Node = null then
|
|
462 return No_Element;
|
|
463 end if;
|
|
464
|
|
465 return Cursor'(Container'Unrestricted_Access, Node, Hash_Type'Last);
|
|
466 end Find;
|
|
467
|
|
468 --------------------
|
|
469 -- Find_Equal_Key --
|
|
470 --------------------
|
|
471
|
|
472 function Find_Equal_Key
|
|
473 (R_HT : Hash_Table_Type;
|
|
474 L_Node : Node_Access) return Boolean
|
|
475 is
|
|
476 R_Index : constant Hash_Type := Key_Ops.Index (R_HT, L_Node.Key);
|
|
477 R_Node : Node_Access := R_HT.Buckets (R_Index);
|
|
478
|
|
479 begin
|
|
480 while R_Node /= null loop
|
|
481 if Equivalent_Keys (L_Node.Key, R_Node.Key) then
|
|
482 return L_Node.Element = R_Node.Element;
|
|
483 end if;
|
|
484
|
|
485 R_Node := R_Node.Next;
|
|
486 end loop;
|
|
487
|
|
488 return False;
|
|
489 end Find_Equal_Key;
|
|
490
|
|
491 -----------
|
|
492 -- First --
|
|
493 -----------
|
|
494
|
|
495 function First (Container : Map) return Cursor is
|
|
496 Pos : Hash_Type;
|
|
497 Node : constant Node_Access := HT_Ops.First (Container.HT, Pos);
|
|
498 begin
|
|
499 if Node = null then
|
|
500 return No_Element;
|
|
501 end if;
|
|
502
|
|
503 return Cursor'(Container'Unrestricted_Access, Node, Pos);
|
|
504 end First;
|
|
505
|
|
506 function First (Object : Iterator) return Cursor is
|
|
507 begin
|
|
508 return Object.Container.First;
|
|
509 end First;
|
|
510
|
|
511 ----------
|
|
512 -- Free --
|
|
513 ----------
|
|
514
|
|
515 procedure Free (X : in out Node_Access) is
|
|
516 procedure Deallocate is
|
|
517 new Ada.Unchecked_Deallocation (Node_Type, Node_Access);
|
|
518 begin
|
|
519 if X /= null then
|
|
520 X.Next := X; -- detect mischief (in Vet)
|
|
521 Deallocate (X);
|
|
522 end if;
|
|
523 end Free;
|
|
524
|
|
525 ------------------------
|
|
526 -- Get_Element_Access --
|
|
527 ------------------------
|
|
528
|
|
529 function Get_Element_Access
|
|
530 (Position : Cursor) return not null Element_Access is
|
|
531 begin
|
|
532 return Position.Node.Element'Access;
|
|
533 end Get_Element_Access;
|
|
534
|
|
535 -----------------
|
|
536 -- Has_Element --
|
|
537 -----------------
|
|
538
|
|
539 function Has_Element (Position : Cursor) return Boolean is
|
|
540 begin
|
|
541 pragma Assert (Vet (Position), "bad cursor in Has_Element");
|
|
542 return Position.Node /= null;
|
|
543 end Has_Element;
|
|
544
|
|
545 ---------------
|
|
546 -- Hash_Node --
|
|
547 ---------------
|
|
548
|
|
549 function Hash_Node (Node : Node_Access) return Hash_Type is
|
|
550 begin
|
|
551 return Hash (Node.Key);
|
|
552 end Hash_Node;
|
|
553
|
|
554 -------------
|
|
555 -- Include --
|
|
556 -------------
|
|
557
|
|
558 procedure Include
|
|
559 (Container : in out Map;
|
|
560 Key : Key_Type;
|
|
561 New_Item : Element_Type)
|
|
562 is
|
|
563 Position : Cursor;
|
|
564 Inserted : Boolean;
|
|
565
|
|
566 begin
|
|
567 Insert (Container, Key, New_Item, Position, Inserted);
|
|
568
|
|
569 if not Inserted then
|
|
570 TE_Check (Container.HT.TC);
|
|
571
|
|
572 Position.Node.Key := Key;
|
|
573 Position.Node.Element := New_Item;
|
|
574 end if;
|
|
575 end Include;
|
|
576
|
|
577 ------------
|
|
578 -- Insert --
|
|
579 ------------
|
|
580
|
|
581 procedure Insert
|
|
582 (Container : in out Map;
|
|
583 Key : Key_Type;
|
|
584 Position : out Cursor;
|
|
585 Inserted : out Boolean)
|
|
586 is
|
|
587 function New_Node (Next : Node_Access) return Node_Access;
|
|
588 pragma Inline (New_Node);
|
|
589
|
|
590 procedure Local_Insert is
|
|
591 new Key_Ops.Generic_Conditional_Insert (New_Node);
|
|
592
|
|
593 --------------
|
|
594 -- New_Node --
|
|
595 --------------
|
|
596
|
|
597 function New_Node (Next : Node_Access) return Node_Access is
|
|
598 begin
|
|
599 return new Node_Type'(Key => Key,
|
|
600 Element => <>,
|
|
601 Next => Next);
|
|
602 end New_Node;
|
|
603
|
|
604 HT : Hash_Table_Type renames Container.HT;
|
|
605
|
|
606 -- Start of processing for Insert
|
|
607
|
|
608 begin
|
|
609 if HT_Ops.Capacity (HT) = 0 then
|
|
610 HT_Ops.Reserve_Capacity (HT, 1);
|
|
611 end if;
|
|
612
|
|
613 Local_Insert (HT, Key, Position.Node, Inserted);
|
|
614
|
|
615 if Inserted
|
|
616 and then HT.Length > HT_Ops.Capacity (HT)
|
|
617 then
|
|
618 HT_Ops.Reserve_Capacity (HT, HT.Length);
|
|
619 end if;
|
|
620
|
|
621 Position.Container := Container'Unrestricted_Access;
|
|
622 end Insert;
|
|
623
|
|
624 procedure Insert
|
|
625 (Container : in out Map;
|
|
626 Key : Key_Type;
|
|
627 New_Item : Element_Type;
|
|
628 Position : out Cursor;
|
|
629 Inserted : out Boolean)
|
|
630 is
|
|
631 function New_Node (Next : Node_Access) return Node_Access;
|
|
632 pragma Inline (New_Node);
|
|
633
|
|
634 procedure Local_Insert is
|
|
635 new Key_Ops.Generic_Conditional_Insert (New_Node);
|
|
636
|
|
637 --------------
|
|
638 -- New_Node --
|
|
639 --------------
|
|
640
|
|
641 function New_Node (Next : Node_Access) return Node_Access is
|
|
642 begin
|
|
643 return new Node_Type'(Key, New_Item, Next);
|
|
644 end New_Node;
|
|
645
|
|
646 HT : Hash_Table_Type renames Container.HT;
|
|
647
|
|
648 -- Start of processing for Insert
|
|
649
|
|
650 begin
|
|
651 if HT_Ops.Capacity (HT) = 0 then
|
|
652 HT_Ops.Reserve_Capacity (HT, 1);
|
|
653 end if;
|
|
654
|
|
655 Local_Insert (HT, Key, Position.Node, Inserted);
|
|
656
|
|
657 if Inserted
|
|
658 and then HT.Length > HT_Ops.Capacity (HT)
|
|
659 then
|
|
660 HT_Ops.Reserve_Capacity (HT, HT.Length);
|
|
661 end if;
|
|
662
|
|
663 Position.Container := Container'Unrestricted_Access;
|
|
664 end Insert;
|
|
665
|
|
666 procedure Insert
|
|
667 (Container : in out Map;
|
|
668 Key : Key_Type;
|
|
669 New_Item : Element_Type)
|
|
670 is
|
|
671 Position : Cursor;
|
|
672 pragma Unreferenced (Position);
|
|
673
|
|
674 Inserted : Boolean;
|
|
675
|
|
676 begin
|
|
677 Insert (Container, Key, New_Item, Position, Inserted);
|
|
678
|
|
679 if Checks and then not Inserted then
|
|
680 raise Constraint_Error with
|
|
681 "attempt to insert key already in map";
|
|
682 end if;
|
|
683 end Insert;
|
|
684
|
|
685 --------------
|
|
686 -- Is_Empty --
|
|
687 --------------
|
|
688
|
|
689 function Is_Empty (Container : Map) return Boolean is
|
|
690 begin
|
|
691 return Container.HT.Length = 0;
|
|
692 end Is_Empty;
|
|
693
|
|
694 -------------
|
|
695 -- Iterate --
|
|
696 -------------
|
|
697
|
|
698 procedure Iterate
|
|
699 (Container : Map;
|
|
700 Process : not null access procedure (Position : Cursor))
|
|
701 is
|
|
702 procedure Process_Node (Node : Node_Access; Position : Hash_Type);
|
|
703 pragma Inline (Process_Node);
|
|
704
|
|
705 procedure Local_Iterate is
|
|
706 new HT_Ops.Generic_Iteration_With_Position (Process_Node);
|
|
707
|
|
708 ------------------
|
|
709 -- Process_Node --
|
|
710 ------------------
|
|
711
|
|
712 procedure Process_Node (Node : Node_Access; Position : Hash_Type) is
|
|
713 begin
|
|
714 Process (Cursor'(Container'Unrestricted_Access, Node, Position));
|
|
715 end Process_Node;
|
|
716
|
|
717 Busy : With_Busy (Container.HT.TC'Unrestricted_Access);
|
|
718
|
|
719 -- Start of processing for Iterate
|
|
720
|
|
721 begin
|
|
722 Local_Iterate (Container.HT);
|
|
723 end Iterate;
|
|
724
|
|
725 function Iterate
|
|
726 (Container : Map) return Map_Iterator_Interfaces.Forward_Iterator'Class
|
|
727 is
|
|
728 begin
|
|
729 return It : constant Iterator :=
|
|
730 (Limited_Controlled with Container => Container'Unrestricted_Access)
|
|
731 do
|
|
732 Busy (Container.HT.TC'Unrestricted_Access.all);
|
|
733 end return;
|
|
734 end Iterate;
|
|
735
|
|
736 ---------
|
|
737 -- Key --
|
|
738 ---------
|
|
739
|
|
740 function Key (Position : Cursor) return Key_Type is
|
|
741 begin
|
|
742 if Checks and then Position.Node = null then
|
|
743 raise Constraint_Error with
|
|
744 "Position cursor of function Key equals No_Element";
|
|
745 end if;
|
|
746
|
|
747 pragma Assert (Vet (Position), "bad cursor in function Key");
|
|
748
|
|
749 return Position.Node.Key;
|
|
750 end Key;
|
|
751
|
|
752 ------------
|
|
753 -- Length --
|
|
754 ------------
|
|
755
|
|
756 function Length (Container : Map) return Count_Type is
|
|
757 begin
|
|
758 return Container.HT.Length;
|
|
759 end Length;
|
|
760
|
|
761 ----------
|
|
762 -- Move --
|
|
763 ----------
|
|
764
|
|
765 procedure Move
|
|
766 (Target : in out Map;
|
|
767 Source : in out Map)
|
|
768 is
|
|
769 begin
|
|
770 HT_Ops.Move (Target => Target.HT, Source => Source.HT);
|
|
771 end Move;
|
|
772
|
|
773 ----------
|
|
774 -- Next --
|
|
775 ----------
|
|
776
|
|
777 function Next (Node : Node_Access) return Node_Access is
|
|
778 begin
|
|
779 return Node.Next;
|
|
780 end Next;
|
|
781
|
|
782 function Next (Position : Cursor) return Cursor is
|
|
783 Node : Node_Access := null;
|
|
784
|
|
785 Pos : Hash_Type;
|
|
786 -- Position of cursor's element in the map buckets.
|
|
787 begin
|
|
788 if Position.Node = null then
|
|
789 return No_Element;
|
|
790 end if;
|
|
791
|
|
792 pragma Assert (Vet (Position), "bad cursor in function Next");
|
|
793
|
|
794 -- Initialize to current position, so that HT_Ops.Next can use it
|
|
795 Pos := Position.Position;
|
|
796
|
|
797 Node := HT_Ops.Next (Position.Container.HT, Position.Node, Pos);
|
|
798
|
|
799 if Node = null then
|
|
800 return No_Element;
|
|
801 else
|
|
802 return Cursor'(Position.Container, Node, Pos);
|
|
803 end if;
|
|
804 end Next;
|
|
805
|
|
806 procedure Next (Position : in out Cursor) is
|
|
807 begin
|
|
808 Position := Next (Position);
|
|
809 end Next;
|
|
810
|
|
811 function Next
|
|
812 (Object : Iterator;
|
|
813 Position : Cursor) return Cursor
|
|
814 is
|
|
815 begin
|
|
816 if Position.Container = null then
|
|
817 return No_Element;
|
|
818 end if;
|
|
819
|
|
820 if Checks and then Position.Container /= Object.Container then
|
|
821 raise Program_Error with
|
|
822 "Position cursor of Next designates wrong map";
|
|
823 end if;
|
|
824
|
|
825 return Next (Position);
|
|
826 end Next;
|
|
827
|
|
828 ----------------------
|
|
829 -- Pseudo_Reference --
|
|
830 ----------------------
|
|
831
|
|
832 function Pseudo_Reference
|
|
833 (Container : aliased Map'Class) return Reference_Control_Type
|
|
834 is
|
|
835 TC : constant Tamper_Counts_Access :=
|
|
836 Container.HT.TC'Unrestricted_Access;
|
|
837 begin
|
|
838 return R : constant Reference_Control_Type := (Controlled with TC) do
|
145
|
839 Busy (TC.all);
|
111
|
840 end return;
|
|
841 end Pseudo_Reference;
|
|
842
|
|
843 -------------------
|
|
844 -- Query_Element --
|
|
845 -------------------
|
|
846
|
|
847 procedure Query_Element
|
|
848 (Position : Cursor;
|
|
849 Process : not null access
|
|
850 procedure (Key : Key_Type; Element : Element_Type))
|
|
851 is
|
|
852 begin
|
|
853 if Checks and then Position.Node = null then
|
|
854 raise Constraint_Error with
|
|
855 "Position cursor of Query_Element equals No_Element";
|
|
856 end if;
|
|
857
|
|
858 pragma Assert (Vet (Position), "bad cursor in Query_Element");
|
|
859
|
|
860 declare
|
|
861 M : Map renames Position.Container.all;
|
|
862 HT : Hash_Table_Type renames M.HT'Unrestricted_Access.all;
|
|
863 Lock : With_Lock (HT.TC'Unrestricted_Access);
|
|
864 K : Key_Type renames Position.Node.Key;
|
|
865 E : Element_Type renames Position.Node.Element;
|
|
866 begin
|
|
867 Process (K, E);
|
|
868 end;
|
|
869 end Query_Element;
|
|
870
|
|
871 ----------
|
|
872 -- Read --
|
|
873 ----------
|
|
874
|
|
875 procedure Read
|
|
876 (Stream : not null access Root_Stream_Type'Class;
|
|
877 Container : out Map)
|
|
878 is
|
|
879 begin
|
|
880 Read_Nodes (Stream, Container.HT);
|
|
881 end Read;
|
|
882
|
|
883 procedure Read
|
|
884 (Stream : not null access Root_Stream_Type'Class;
|
|
885 Item : out Cursor)
|
|
886 is
|
|
887 begin
|
|
888 raise Program_Error with "attempt to stream map cursor";
|
|
889 end Read;
|
|
890
|
|
891 procedure Read
|
|
892 (Stream : not null access Root_Stream_Type'Class;
|
|
893 Item : out Reference_Type)
|
|
894 is
|
|
895 begin
|
|
896 raise Program_Error with "attempt to stream reference";
|
|
897 end Read;
|
|
898
|
|
899 procedure Read
|
|
900 (Stream : not null access Root_Stream_Type'Class;
|
|
901 Item : out Constant_Reference_Type)
|
|
902 is
|
|
903 begin
|
|
904 raise Program_Error with "attempt to stream reference";
|
|
905 end Read;
|
|
906
|
|
907 ---------------
|
|
908 -- Reference --
|
|
909 ---------------
|
|
910
|
|
911 function Reference
|
|
912 (Container : aliased in out Map;
|
|
913 Position : Cursor) return Reference_Type
|
|
914 is
|
|
915 begin
|
|
916 if Checks and then Position.Container = null then
|
|
917 raise Constraint_Error with
|
|
918 "Position cursor has no element";
|
|
919 end if;
|
|
920
|
|
921 if Checks and then Position.Container /= Container'Unrestricted_Access
|
|
922 then
|
|
923 raise Program_Error with
|
|
924 "Position cursor designates wrong map";
|
|
925 end if;
|
|
926
|
|
927 pragma Assert
|
|
928 (Vet (Position),
|
|
929 "Position cursor in function Reference is bad");
|
|
930
|
|
931 declare
|
|
932 HT : Hash_Table_Type renames Container'Unrestricted_Access.all.HT;
|
|
933 TC : constant Tamper_Counts_Access :=
|
|
934 HT.TC'Unrestricted_Access;
|
|
935 begin
|
|
936 return R : constant Reference_Type :=
|
|
937 (Element => Position.Node.Element'Access,
|
|
938 Control => (Controlled with TC))
|
|
939 do
|
145
|
940 Busy (TC.all);
|
111
|
941 end return;
|
|
942 end;
|
|
943 end Reference;
|
|
944
|
|
945 function Reference
|
|
946 (Container : aliased in out Map;
|
|
947 Key : Key_Type) return Reference_Type
|
|
948 is
|
|
949 HT : Hash_Table_Type renames Container.HT;
|
|
950 Node : constant Node_Access := Key_Ops.Find (HT, Key);
|
|
951
|
|
952 begin
|
|
953 if Checks and then Node = null then
|
|
954 raise Constraint_Error with "key not in map";
|
|
955 end if;
|
|
956
|
|
957 declare
|
|
958 TC : constant Tamper_Counts_Access :=
|
|
959 HT.TC'Unrestricted_Access;
|
|
960 begin
|
|
961 return R : constant Reference_Type :=
|
|
962 (Element => Node.Element'Access,
|
|
963 Control => (Controlled with TC))
|
|
964 do
|
145
|
965 Busy (TC.all);
|
111
|
966 end return;
|
|
967 end;
|
|
968 end Reference;
|
|
969
|
|
970 ---------------
|
|
971 -- Read_Node --
|
|
972 ---------------
|
|
973
|
|
974 function Read_Node
|
|
975 (Stream : not null access Root_Stream_Type'Class) return Node_Access
|
|
976 is
|
|
977 Node : Node_Access := new Node_Type;
|
|
978
|
|
979 begin
|
|
980 Key_Type'Read (Stream, Node.Key);
|
|
981 Element_Type'Read (Stream, Node.Element);
|
|
982 return Node;
|
|
983
|
|
984 exception
|
|
985 when others =>
|
|
986 Free (Node);
|
|
987 raise;
|
|
988 end Read_Node;
|
|
989
|
|
990 -------------
|
|
991 -- Replace --
|
|
992 -------------
|
|
993
|
|
994 procedure Replace
|
|
995 (Container : in out Map;
|
|
996 Key : Key_Type;
|
|
997 New_Item : Element_Type)
|
|
998 is
|
|
999 Node : constant Node_Access := Key_Ops.Find (Container.HT, Key);
|
|
1000
|
|
1001 begin
|
|
1002 if Checks and then Node = null then
|
|
1003 raise Constraint_Error with
|
|
1004 "attempt to replace key not in map";
|
|
1005 end if;
|
|
1006
|
|
1007 TE_Check (Container.HT.TC);
|
|
1008
|
|
1009 Node.Key := Key;
|
|
1010 Node.Element := New_Item;
|
|
1011 end Replace;
|
|
1012
|
|
1013 ---------------------
|
|
1014 -- Replace_Element --
|
|
1015 ---------------------
|
|
1016
|
|
1017 procedure Replace_Element
|
|
1018 (Container : in out Map;
|
|
1019 Position : Cursor;
|
|
1020 New_Item : Element_Type)
|
|
1021 is
|
|
1022 begin
|
|
1023 if Checks and then Position.Node = null then
|
|
1024 raise Constraint_Error with
|
|
1025 "Position cursor of Replace_Element equals No_Element";
|
|
1026 end if;
|
|
1027
|
|
1028 if Checks and then Position.Container /= Container'Unrestricted_Access
|
|
1029 then
|
|
1030 raise Program_Error with
|
|
1031 "Position cursor of Replace_Element designates wrong map";
|
|
1032 end if;
|
|
1033
|
|
1034 TE_Check (Position.Container.HT.TC);
|
|
1035
|
|
1036 pragma Assert (Vet (Position), "bad cursor in Replace_Element");
|
|
1037
|
|
1038 Position.Node.Element := New_Item;
|
|
1039 end Replace_Element;
|
|
1040
|
|
1041 ----------------------
|
|
1042 -- Reserve_Capacity --
|
|
1043 ----------------------
|
|
1044
|
|
1045 procedure Reserve_Capacity
|
|
1046 (Container : in out Map;
|
|
1047 Capacity : Count_Type)
|
|
1048 is
|
|
1049 begin
|
|
1050 HT_Ops.Reserve_Capacity (Container.HT, Capacity);
|
|
1051 end Reserve_Capacity;
|
|
1052
|
|
1053 --------------
|
|
1054 -- Set_Next --
|
|
1055 --------------
|
|
1056
|
|
1057 procedure Set_Next (Node : Node_Access; Next : Node_Access) is
|
|
1058 begin
|
|
1059 Node.Next := Next;
|
|
1060 end Set_Next;
|
|
1061
|
|
1062 --------------------
|
|
1063 -- Update_Element --
|
|
1064 --------------------
|
|
1065
|
|
1066 procedure Update_Element
|
|
1067 (Container : in out Map;
|
|
1068 Position : Cursor;
|
|
1069 Process : not null access procedure (Key : Key_Type;
|
|
1070 Element : in out Element_Type))
|
|
1071 is
|
|
1072 begin
|
|
1073 if Checks and then Position.Node = null then
|
|
1074 raise Constraint_Error with
|
|
1075 "Position cursor of Update_Element equals No_Element";
|
|
1076 end if;
|
|
1077
|
|
1078 if Checks and then Position.Container /= Container'Unrestricted_Access
|
|
1079 then
|
|
1080 raise Program_Error with
|
|
1081 "Position cursor of Update_Element designates wrong map";
|
|
1082 end if;
|
|
1083
|
|
1084 pragma Assert (Vet (Position), "bad cursor in Update_Element");
|
|
1085
|
|
1086 declare
|
|
1087 HT : Hash_Table_Type renames Container.HT;
|
|
1088 Lock : With_Lock (HT.TC'Unrestricted_Access);
|
|
1089 K : Key_Type renames Position.Node.Key;
|
|
1090 E : Element_Type renames Position.Node.Element;
|
|
1091 begin
|
|
1092 Process (K, E);
|
|
1093 end;
|
|
1094 end Update_Element;
|
|
1095
|
|
1096 ---------
|
|
1097 -- Vet --
|
|
1098 ---------
|
|
1099
|
|
1100 function Vet (Position : Cursor) return Boolean is
|
|
1101 begin
|
|
1102 if Position.Node = null then
|
|
1103 return Position.Container = null;
|
|
1104 end if;
|
|
1105
|
|
1106 if Position.Container = null then
|
|
1107 return False;
|
|
1108 end if;
|
|
1109
|
|
1110 if Position.Node.Next = Position.Node then
|
|
1111 return False;
|
|
1112 end if;
|
|
1113
|
|
1114 declare
|
|
1115 HT : Hash_Table_Type renames Position.Container.HT;
|
|
1116 X : Node_Access;
|
|
1117
|
|
1118 begin
|
|
1119 if HT.Length = 0 then
|
|
1120 return False;
|
|
1121 end if;
|
|
1122
|
|
1123 if HT.Buckets = null
|
|
1124 or else HT.Buckets'Length = 0
|
|
1125 then
|
|
1126 return False;
|
|
1127 end if;
|
|
1128
|
|
1129 X := HT.Buckets (Key_Ops.Checked_Index (HT, Position.Node.Key));
|
|
1130
|
|
1131 for J in 1 .. HT.Length loop
|
|
1132 if X = Position.Node then
|
|
1133 return True;
|
|
1134 end if;
|
|
1135
|
|
1136 if X = null then
|
|
1137 return False;
|
|
1138 end if;
|
|
1139
|
|
1140 if X = X.Next then -- to prevent unnecessary looping
|
|
1141 return False;
|
|
1142 end if;
|
|
1143
|
|
1144 X := X.Next;
|
|
1145 end loop;
|
|
1146
|
|
1147 return False;
|
|
1148 end;
|
|
1149 end Vet;
|
|
1150
|
|
1151 -----------
|
|
1152 -- Write --
|
|
1153 -----------
|
|
1154
|
|
1155 procedure Write
|
|
1156 (Stream : not null access Root_Stream_Type'Class;
|
|
1157 Container : Map)
|
|
1158 is
|
|
1159 begin
|
|
1160 Write_Nodes (Stream, Container.HT);
|
|
1161 end Write;
|
|
1162
|
|
1163 procedure Write
|
|
1164 (Stream : not null access Root_Stream_Type'Class;
|
|
1165 Item : Cursor)
|
|
1166 is
|
|
1167 begin
|
|
1168 raise Program_Error with "attempt to stream map cursor";
|
|
1169 end Write;
|
|
1170
|
|
1171 procedure Write
|
|
1172 (Stream : not null access Root_Stream_Type'Class;
|
|
1173 Item : Reference_Type)
|
|
1174 is
|
|
1175 begin
|
|
1176 raise Program_Error with "attempt to stream reference";
|
|
1177 end Write;
|
|
1178
|
|
1179 procedure Write
|
|
1180 (Stream : not null access Root_Stream_Type'Class;
|
|
1181 Item : Constant_Reference_Type)
|
|
1182 is
|
|
1183 begin
|
|
1184 raise Program_Error with "attempt to stream reference";
|
|
1185 end Write;
|
|
1186
|
|
1187 ----------------
|
|
1188 -- Write_Node --
|
|
1189 ----------------
|
|
1190
|
|
1191 procedure Write_Node
|
|
1192 (Stream : not null access Root_Stream_Type'Class;
|
|
1193 Node : Node_Access)
|
|
1194 is
|
|
1195 begin
|
|
1196 Key_Type'Write (Stream, Node.Key);
|
|
1197 Element_Type'Write (Stream, Node.Element);
|
|
1198 end Write_Node;
|
|
1199
|
|
1200 end Ada.Containers.Hashed_Maps;
|