1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
5 -- ADA.CONTAINERS.HASHED_MAPS --
9 -- Copyright (C) 2004 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 2, 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. See the GNU General Public License --
21 -- for more details. You should have received a copy of the GNU General --
22 -- Public License distributed with GNAT; see file COPYING. If not, write --
23 -- to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, --
24 -- MA 02111-1307, USA. --
26 -- As a special exception, if other files instantiate generics from this --
27 -- unit, or you link this unit with other files to produce an executable, --
28 -- this unit does not by itself cause the resulting executable to be --
29 -- covered by the GNU General Public License. This exception does not --
30 -- however invalidate any other reasons why the executable file might be --
31 -- covered by the GNU Public License. --
33 -- This unit was originally developed by Matthew J Heaney. --
34 ------------------------------------------------------------------------------
36 with Ada.Unchecked_Deallocation;
38 with Ada.Containers.Hash_Tables.Generic_Operations;
39 pragma Elaborate_All (Ada.Containers.Hash_Tables.Generic_Operations);
41 with Ada.Containers.Hash_Tables.Generic_Keys;
42 pragma Elaborate_All (Ada.Containers.Hash_Tables.Generic_Keys);
44 package body Ada.Containers.Hashed_Maps is
46 type Node_Type is limited record
48 Element : Element_Type;
52 -----------------------
53 -- Local Subprograms --
54 -----------------------
57 (Source : Node_Access) return Node_Access;
58 pragma Inline (Copy_Node);
60 function Equivalent_Keys
62 Node : Node_Access) return Boolean;
63 pragma Inline (Equivalent_Keys);
65 function Find_Equal_Key
67 L_Node : Node_Access) return Boolean;
69 function Hash_Node (Node : Node_Access) return Hash_Type;
70 pragma Inline (Hash_Node);
72 function Next (Node : Node_Access) return Node_Access;
76 (Stream : access Root_Stream_Type'Class) return Node_Access;
77 pragma Inline (Read_Node);
79 procedure Set_Next (Node : Node_Access; Next : Node_Access);
80 pragma Inline (Set_Next);
83 (Stream : access Root_Stream_Type'Class;
85 pragma Inline (Write_Node);
87 --------------------------
88 -- Local Instantiations --
89 --------------------------
92 new Ada.Unchecked_Deallocation (Node_Type, Node_Access);
95 new Hash_Tables.Generic_Operations
96 (HT_Types => HT_Types,
97 Hash_Table_Type => Map,
99 Hash_Node => Hash_Node,
101 Set_Next => Set_Next,
102 Copy_Node => Copy_Node,
106 new Hash_Tables.Generic_Keys
107 (HT_Types => HT_Types,
111 Set_Next => Set_Next,
112 Key_Type => Key_Type,
114 Equivalent_Keys => Equivalent_Keys);
116 function Is_Equal is new HT_Ops.Generic_Equal (Find_Equal_Key);
118 procedure Read_Nodes is new HT_Ops.Generic_Read (Read_Node);
119 procedure Write_Nodes is new HT_Ops.Generic_Write (Write_Node);
125 function "=" (Left, Right : Map) return Boolean renames Is_Equal;
131 procedure Adjust (Container : in out Map) renames HT_Ops.Adjust;
137 function Capacity (Container : Map) return Count_Type
138 renames HT_Ops.Capacity;
144 procedure Clear (Container : in out Map) renames HT_Ops.Clear;
150 function Contains (Container : Map; Key : Key_Type) return Boolean is
152 return Find (Container, Key) /= No_Element;
160 (Source : Node_Access) return Node_Access
162 Target : constant Node_Access :=
163 new Node_Type'(Key => Source.Key,
164 Element => Source.Element,
174 procedure Delete (Container : in out Map; Key : Key_Type) is
178 Key_Ops.Delete_Key_Sans_Free (Container, Key, X);
181 raise Constraint_Error;
187 procedure Delete (Container : in out Map; Position : in out Cursor) is
189 if Position = No_Element then
193 if Position.Container /= Map_Access'(Container'Unchecked_Access) then
197 HT_Ops.Delete_Node_Sans_Free (Container, Position.Node);
198 Free (Position.Node);
200 Position.Container := null;
207 function Element (Container : Map; Key : Key_Type) return Element_Type is
208 C : constant Cursor := Find (Container, Key);
210 return C.Node.Element;
213 function Element (Position : Cursor) return Element_Type is
215 return Position.Node.Element;
218 ---------------------
219 -- Equivalent_Keys --
220 ---------------------
222 function Equivalent_Keys
224 Node : Node_Access) return Boolean is
226 return Equivalent_Keys (Key, Node.Key);
229 ---------------------
230 -- Equivalent_Keys --
231 ---------------------
233 function Equivalent_Keys (Left, Right : Cursor)
236 return Equivalent_Keys (Left.Node.Key, Right.Node.Key);
239 function Equivalent_Keys (Left : Cursor; Right : Key_Type) return Boolean is
241 return Equivalent_Keys (Left.Node.Key, Right);
244 function Equivalent_Keys (Left : Key_Type; Right : Cursor) return Boolean is
246 return Equivalent_Keys (Left, Right.Node.Key);
253 procedure Exclude (Container : in out Map; Key : Key_Type) is
256 Key_Ops.Delete_Key_Sans_Free (Container, Key, X);
264 procedure Finalize (Container : in out Map) renames HT_Ops.Finalize;
270 function Find (Container : Map; Key : Key_Type) return Cursor is
271 Node : constant Node_Access := Key_Ops.Find (Container, Key);
278 return Cursor'(Container'Unchecked_Access, Node);
285 function Find_Equal_Key
287 L_Node : Node_Access) return Boolean
289 R_Index : constant Hash_Type := Key_Ops.Index (R_Map, L_Node.Key);
290 R_Node : Node_Access := R_Map.Buckets (R_Index);
293 while R_Node /= null loop
294 if Equivalent_Keys (L_Node.Key, R_Node.Key) then
295 return L_Node.Element = R_Node.Element;
298 R_Node := R_Node.Next;
308 function First (Container : Map) return Cursor is
309 Node : constant Node_Access := HT_Ops.First (Container);
316 return Cursor'(Container'Unchecked_Access, Node);
323 function Has_Element (Position : Cursor) return Boolean is
325 return Position /= No_Element;
332 function Hash_Node (Node : Node_Access) return Hash_Type is
334 return Hash (Node.Key);
342 (Container : in out Map;
344 New_Item : Element_Type)
350 Insert (Container, Key, New_Item, Position, Inserted);
353 Position.Node.Key := Key;
354 Position.Node.Element := New_Item;
363 (Container : in out Map;
365 Position : out Cursor;
366 Inserted : out Boolean)
368 function New_Node (Next : Node_Access) return Node_Access;
369 pragma Inline (New_Node);
371 procedure Local_Insert is
372 new Key_Ops.Generic_Conditional_Insert (New_Node);
378 function New_Node (Next : Node_Access) return Node_Access is
379 Node : Node_Access := new Node_Type; -- Ada 2005 aggregate possible?
393 -- Start of processing for Insert
396 HT_Ops.Ensure_Capacity (Container, Container.Length + 1);
397 Local_Insert (Container, Key, Position.Node, Inserted);
398 Position.Container := Container'Unchecked_Access;
402 (Container : in out Map;
404 New_Item : Element_Type;
405 Position : out Cursor;
406 Inserted : out Boolean)
408 function New_Node (Next : Node_Access) return Node_Access;
409 pragma Inline (New_Node);
411 procedure Local_Insert is
412 new Key_Ops.Generic_Conditional_Insert (New_Node);
418 function New_Node (Next : Node_Access) return Node_Access is
419 Node : constant Node_Access := new Node_Type'(Key, New_Item, Next);
424 -- Start of processing for Insert
427 HT_Ops.Ensure_Capacity (Container, Container.Length + 1);
428 Local_Insert (Container, Key, Position.Node, Inserted);
429 Position.Container := Container'Unchecked_Access;
433 (Container : in out Map;
435 New_Item : Element_Type)
441 Insert (Container, Key, New_Item, Position, Inserted);
444 raise Constraint_Error;
452 function Is_Empty (Container : Map) return Boolean is
454 return Container.Length = 0;
463 Process : not null access procedure (Position : Cursor))
465 procedure Process_Node (Node : Node_Access);
466 pragma Inline (Process_Node);
468 procedure Local_Iterate is new HT_Ops.Generic_Iteration (Process_Node);
474 procedure Process_Node (Node : Node_Access) is
476 Process (Cursor'(Container'Unchecked_Access, Node));
479 -- Start of processing for Iterate
482 Local_Iterate (Container);
489 function Key (Position : Cursor) return Key_Type is
491 return Position.Node.Key;
498 function Length (Container : Map) return Count_Type is
500 return Container.Length;
508 (Target : in out Map;
509 Source : in out Map) renames HT_Ops.Move;
515 function Next (Node : Node_Access) return Node_Access is
520 function Next (Position : Cursor) return Cursor is
522 if Position = No_Element then
527 M : Map renames Position.Container.all;
528 Node : constant Node_Access := HT_Ops.Next (M, Position.Node);
535 return Cursor'(Position.Container, Node);
539 procedure Next (Position : in out Cursor) is
541 Position := Next (Position);
548 procedure Query_Element
550 Process : not null access procedure (Element : Element_Type))
553 Process (Position.Node.Key, Position.Node.Element);
561 (Stream : access Root_Stream_Type'Class;
562 Container : out Map) renames Read_Nodes;
569 (Stream : access Root_Stream_Type'Class) return Node_Access
571 Node : Node_Access := new Node_Type;
574 Key_Type'Read (Stream, Node.Key);
575 Element_Type'Read (Stream, Node.Element);
589 (Container : in out Map;
591 New_Item : Element_Type)
593 Node : constant Node_Access := Key_Ops.Find (Container, Key);
597 raise Constraint_Error;
601 Node.Element := New_Item;
604 ---------------------
605 -- Replace_Element --
606 ---------------------
608 procedure Replace_Element (Position : Cursor; By : Element_Type) is
610 Position.Node.Element := By;
613 ----------------------
614 -- Reserve_Capacity --
615 ----------------------
617 procedure Reserve_Capacity
618 (Container : in out Map;
619 Capacity : Count_Type) renames HT_Ops.Ensure_Capacity;
625 procedure Set_Next (Node : Node_Access; Next : Node_Access) is
634 procedure Update_Element
636 Process : not null access procedure (Element : in out Element_Type))
639 Process (Position.Node.Key, Position.Node.Element);
647 (Stream : access Root_Stream_Type'Class;
648 Container : Map) renames Write_Nodes;
655 (Stream : access Root_Stream_Type'Class;
659 Key_Type'Write (Stream, Node.Key);
660 Element_Type'Write (Stream, Node.Element);
663 end Ada.Containers.Hashed_Maps;