1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
5 -- ADA.CONTAINERS.INDEFINITE_HASHED_SETS --
9 -- Copyright (C) 2004-2007, Free Software Foundation, Inc. --
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 2, 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. See the GNU General Public License --
17 -- for more details. You should have received a copy of the GNU General --
18 -- Public License distributed with GNAT; see file COPYING. If not, write --
19 -- to the Free Software Foundation, 51 Franklin Street, Fifth Floor, --
20 -- Boston, MA 02110-1301, USA. --
22 -- As a special exception, if other files instantiate generics from this --
23 -- unit, or you link this unit with other files to produce an executable, --
24 -- this unit does not by itself cause the resulting executable to be --
25 -- covered by the GNU General Public License. This exception does not --
26 -- however invalidate any other reasons why the executable file might be --
27 -- covered by the GNU Public License. --
29 -- This unit has originally being developed by Matthew J Heaney. --
30 ------------------------------------------------------------------------------
32 with Ada
.Unchecked_Deallocation
;
34 with Ada
.Containers
.Hash_Tables
.Generic_Operations
;
35 pragma Elaborate_All
(Ada
.Containers
.Hash_Tables
.Generic_Operations
);
37 with Ada
.Containers
.Hash_Tables
.Generic_Keys
;
38 pragma Elaborate_All
(Ada
.Containers
.Hash_Tables
.Generic_Keys
);
40 with Ada
.Containers
.Prime_Numbers
;
42 with System
; use type System
.Address
;
44 package body Ada
.Containers
.Indefinite_Hashed_Sets
is
46 -----------------------
47 -- Local Subprograms --
48 -----------------------
50 procedure Assign
(Node
: Node_Access
; Item
: Element_Type
);
51 pragma Inline
(Assign
);
53 function Copy_Node
(Source
: Node_Access
) return Node_Access
;
54 pragma Inline
(Copy_Node
);
56 function Equivalent_Keys
58 Node
: Node_Access
) return Boolean;
59 pragma Inline
(Equivalent_Keys
);
61 function Find_Equal_Key
62 (R_HT
: Hash_Table_Type
;
63 L_Node
: Node_Access
) return Boolean;
65 function Find_Equivalent_Key
66 (R_HT
: Hash_Table_Type
;
67 L_Node
: Node_Access
) return Boolean;
69 procedure Free
(X
: in out Node_Access
);
71 function Hash_Node
(Node
: Node_Access
) return Hash_Type
;
72 pragma Inline
(Hash_Node
);
75 (HT
: in out Hash_Table_Type
;
76 New_Item
: Element_Type
;
77 Node
: out Node_Access
;
78 Inserted
: out Boolean);
80 function Is_In
(HT
: Hash_Table_Type
; Key
: Node_Access
) return Boolean;
81 pragma Inline
(Is_In
);
83 function Next
(Node
: Node_Access
) return Node_Access
;
86 function Read_Node
(Stream
: not null access Root_Stream_Type
'Class)
88 pragma Inline
(Read_Node
);
90 procedure Set_Next
(Node
: Node_Access
; Next
: Node_Access
);
91 pragma Inline
(Set_Next
);
93 function Vet
(Position
: Cursor
) return Boolean;
96 (Stream
: not null access Root_Stream_Type
'Class;
98 pragma Inline
(Write_Node
);
100 --------------------------
101 -- Local Instantiations --
102 --------------------------
104 procedure Free_Element
is
105 new Ada
.Unchecked_Deallocation
(Element_Type
, Element_Access
);
108 new Hash_Tables
.Generic_Operations
109 (HT_Types
=> HT_Types
,
110 Hash_Node
=> Hash_Node
,
112 Set_Next
=> Set_Next
,
113 Copy_Node
=> Copy_Node
,
116 package Element_Keys
is
117 new Hash_Tables
.Generic_Keys
118 (HT_Types
=> HT_Types
,
120 Set_Next
=> Set_Next
,
121 Key_Type
=> Element_Type
,
123 Equivalent_Keys
=> Equivalent_Keys
);
126 new HT_Ops
.Generic_Equal
(Find_Equal_Key
);
128 function Is_Equivalent
is
129 new HT_Ops
.Generic_Equal
(Find_Equivalent_Key
);
131 procedure Read_Nodes
is
132 new HT_Ops
.Generic_Read
(Read_Node
);
134 procedure Replace_Element
is
135 new Element_Keys
.Generic_Replace_Element
(Hash_Node
, Assign
);
137 procedure Write_Nodes
is
138 new HT_Ops
.Generic_Write
(Write_Node
);
144 function "=" (Left
, Right
: Set
) return Boolean is
146 return Is_Equal
(Left
.HT
, Right
.HT
);
153 procedure Adjust
(Container
: in out Set
) is
155 HT_Ops
.Adjust
(Container
.HT
);
162 procedure Assign
(Node
: Node_Access
; Item
: Element_Type
) is
163 X
: Element_Access
:= Node
.Element
;
165 Node
.Element
:= new Element_Type
'(Item);
173 function Capacity (Container : Set) return Count_Type is
175 return HT_Ops.Capacity (Container.HT);
182 procedure Clear (Container : in out Set) is
184 HT_Ops.Clear (Container.HT);
191 function Contains (Container : Set; Item : Element_Type) return Boolean is
193 return Find (Container, Item) /= No_Element;
200 function Copy_Node (Source : Node_Access) return Node_Access is
201 E : Element_Access := new Element_Type'(Source
.Element
.all);
203 return new Node_Type
'(Element => E, Next => null);
215 (Container : in out Set;
221 Element_Keys.Delete_Key_Sans_Free (Container.HT, Item, X);
224 raise Constraint_Error with "attempt to delete element not in set";
231 (Container : in out Set;
232 Position : in out Cursor)
235 if Position.Node = null then
236 raise Constraint_Error with "Position cursor equals No_Element";
239 if Position.Node.Element = null then
240 raise Program_Error with "Position cursor is bad";
243 if Position.Container /= Container'Unrestricted_Access then
244 raise Program_Error with "Position cursor designates wrong set";
247 if Container.HT.Busy > 0 then
248 raise Program_Error with
249 "attempt to tamper with elements (set is busy)";
252 pragma Assert (Vet (Position), "Position cursor is bad");
254 HT_Ops.Delete_Node_Sans_Free (Container.HT, Position.Node);
256 Free (Position.Node);
257 Position.Container := null;
265 (Target : in out Set;
268 Tgt_Node : Node_Access;
271 if Target'Address = Source'Address then
276 if Source.HT.Length = 0 then
280 if Target.HT.Busy > 0 then
281 raise Program_Error with
282 "attempt to tamper with elements (set is busy)";
285 if Source.HT.Length < Target.HT.Length then
287 Src_Node : Node_Access;
290 Src_Node := HT_Ops.First (Source.HT);
291 while Src_Node /= null loop
292 Tgt_Node := Element_Keys.Find (Target.HT, Src_Node.Element.all);
294 if Tgt_Node /= null then
295 HT_Ops.Delete_Node_Sans_Free (Target.HT, Tgt_Node);
299 Src_Node := HT_Ops.Next (Source.HT, Src_Node);
304 Tgt_Node := HT_Ops.First (Target.HT);
305 while Tgt_Node /= null loop
306 if Is_In (Source.HT, Tgt_Node) then
308 X : Node_Access := Tgt_Node;
310 Tgt_Node := HT_Ops.Next (Target.HT, Tgt_Node);
311 HT_Ops.Delete_Node_Sans_Free (Target.HT, X);
316 Tgt_Node := HT_Ops.Next (Target.HT, Tgt_Node);
322 function Difference (Left, Right : Set) return Set is
323 Buckets : HT_Types.Buckets_Access;
327 if Left'Address = Right'Address then
331 if Left.Length = 0 then
335 if Right.Length = 0 then
340 Size : constant Hash_Type := Prime_Numbers.To_Prime (Left.Length);
342 Buckets := HT_Ops.New_Buckets (Length => Size);
347 Iterate_Left : declare
348 procedure Process (L_Node : Node_Access);
351 new HT_Ops.Generic_Iteration (Process);
357 procedure Process (L_Node : Node_Access) is
359 if not Is_In (Right.HT, L_Node) then
361 Src : Element_Type renames L_Node.Element.all;
362 Indx : constant Hash_Type := Hash (Src) mod Buckets'Length;
363 Bucket : Node_Access renames Buckets (Indx);
364 Tgt : Element_Access := new Element_Type'(Src
);
366 Bucket
:= new Node_Type
'(Tgt, Bucket);
373 Length := Length + 1;
377 -- Start of processing for Iterate_Left
383 HT_Ops.Free_Hash_Table (Buckets);
387 return (Controlled with HT => (Buckets, Length, 0, 0));
394 function Element (Position : Cursor) return Element_Type is
396 if Position.Node = null then
397 raise Constraint_Error with "Position cursor of equals No_Element";
400 if Position.Node.Element = null then -- handle dangling reference
401 raise Program_Error with "Position cursor is bad";
404 pragma Assert (Vet (Position), "bad cursor in function Element");
406 return Position.Node.Element.all;
409 ---------------------
410 -- Equivalent_Sets --
411 ---------------------
413 function Equivalent_Sets (Left, Right : Set) return Boolean is
415 return Is_Equivalent (Left.HT, Right.HT);
418 -------------------------
419 -- Equivalent_Elements --
420 -------------------------
422 function Equivalent_Elements (Left, Right : Cursor)
425 if Left.Node = null then
426 raise Constraint_Error with
427 "Left cursor of Equivalent_Elements equals No_Element";
430 if Right.Node = null then
431 raise Constraint_Error with
432 "Right cursor of Equivalent_Elements equals No_Element";
435 if Left.Node.Element = null then
436 raise Program_Error with
437 "Left cursor of Equivalent_Elements is bad";
440 if Right.Node.Element = null then
441 raise Program_Error with
442 "Right cursor of Equivalent_Elements is bad";
445 pragma Assert (Vet (Left), "bad Left cursor in Equivalent_Elements");
446 pragma Assert (Vet (Right), "bad Right cursor in Equivalent_Elements");
448 return Equivalent_Elements
449 (Left.Node.Element.all,
450 Right.Node.Element.all);
451 end Equivalent_Elements;
453 function Equivalent_Elements (Left : Cursor; Right : Element_Type)
456 if Left.Node = null then
457 raise Constraint_Error with
458 "Left cursor of Equivalent_Elements equals No_Element";
461 if Left.Node.Element = null then
462 raise Program_Error with
463 "Left cursor of Equivalent_Elements is bad";
466 pragma Assert (Vet (Left), "bad Left cursor in Equivalent_Elements");
468 return Equivalent_Elements (Left.Node.Element.all, Right);
469 end Equivalent_Elements;
471 function Equivalent_Elements (Left : Element_Type; Right : Cursor)
474 if Right.Node = null then
475 raise Constraint_Error with
476 "Right cursor of Equivalent_Elements equals No_Element";
479 if Right.Node.Element = null then
480 raise Program_Error with
481 "Right cursor of Equivalent_Elements is bad";
484 pragma Assert (Vet (Right), "bad Right cursor in Equivalent_Elements");
486 return Equivalent_Elements (Left, Right.Node.Element.all);
487 end Equivalent_Elements;
489 ---------------------
490 -- Equivalent_Keys --
491 ---------------------
493 function Equivalent_Keys (Key : Element_Type; Node : Node_Access)
496 return Equivalent_Elements (Key, Node.Element.all);
504 (Container : in out Set;
509 Element_Keys.Delete_Key_Sans_Free (Container.HT, Item, X);
517 procedure Finalize (Container : in out Set) is
519 HT_Ops.Finalize (Container.HT);
528 Item : Element_Type) return Cursor
530 Node : constant Node_Access := Element_Keys.Find (Container.HT, Item);
537 return Cursor'(Container
'Unrestricted_Access, Node
);
544 function Find_Equal_Key
545 (R_HT
: Hash_Table_Type
;
546 L_Node
: Node_Access
) return Boolean
548 R_Index
: constant Hash_Type
:=
549 Element_Keys
.Index
(R_HT
, L_Node
.Element
.all);
551 R_Node
: Node_Access
:= R_HT
.Buckets
(R_Index
);
555 if R_Node
= null then
559 if L_Node
.Element
.all = R_Node
.Element
.all then
563 R_Node
:= Next
(R_Node
);
567 -------------------------
568 -- Find_Equivalent_Key --
569 -------------------------
571 function Find_Equivalent_Key
572 (R_HT
: Hash_Table_Type
;
573 L_Node
: Node_Access
) return Boolean
575 R_Index
: constant Hash_Type
:=
576 Element_Keys
.Index
(R_HT
, L_Node
.Element
.all);
578 R_Node
: Node_Access
:= R_HT
.Buckets
(R_Index
);
582 if R_Node
= null then
586 if Equivalent_Elements
(L_Node
.Element
.all, R_Node
.Element
.all) then
590 R_Node
:= Next
(R_Node
);
592 end Find_Equivalent_Key
;
598 function First
(Container
: Set
) return Cursor
is
599 Node
: constant Node_Access
:= HT_Ops
.First
(Container
.HT
);
606 return Cursor
'(Container'Unrestricted_Access, Node);
613 procedure Free (X : in out Node_Access) is
614 procedure Deallocate is
615 new Ada.Unchecked_Deallocation (Node_Type, Node_Access);
622 X.Next := X; -- detect mischief (in Vet)
625 Free_Element (X.Element);
640 function Has_Element (Position : Cursor) return Boolean is
642 pragma Assert (Vet (Position), "bad cursor in Has_Element");
643 return Position.Node /= null;
650 function Hash_Node (Node : Node_Access) return Hash_Type is
652 return Hash (Node.Element.all);
660 (Container : in out Set;
661 New_Item : Element_Type)
669 Insert (Container, New_Item, Position, Inserted);
672 if Container.HT.Lock > 0 then
673 raise Program_Error with
674 "attempt to tamper with cursors (set is locked)";
677 X := Position.Node.Element;
679 Position.Node.Element := new Element_Type'(New_Item
);
690 (Container
: in out Set
;
691 New_Item
: Element_Type
;
692 Position
: out Cursor
;
693 Inserted
: out Boolean)
696 Insert
(Container
.HT
, New_Item
, Position
.Node
, Inserted
);
697 Position
.Container
:= Container
'Unchecked_Access;
701 (Container
: in out Set
;
702 New_Item
: Element_Type
)
705 pragma Unreferenced
(Position
);
710 Insert
(Container
, New_Item
, Position
, Inserted
);
713 raise Constraint_Error
with
714 "attempt to insert element already in set";
719 (HT
: in out Hash_Table_Type
;
720 New_Item
: Element_Type
;
721 Node
: out Node_Access
;
722 Inserted
: out Boolean)
724 function New_Node
(Next
: Node_Access
) return Node_Access
;
725 pragma Inline
(New_Node
);
727 procedure Local_Insert
is
728 new Element_Keys
.Generic_Conditional_Insert
(New_Node
);
734 function New_Node
(Next
: Node_Access
) return Node_Access
is
735 Element
: Element_Access
:= new Element_Type
'(New_Item);
738 return new Node_Type'(Element
, Next
);
741 Free_Element
(Element
);
745 -- Start of processing for Insert
748 if HT_Ops
.Capacity
(HT
) = 0 then
749 HT_Ops
.Reserve_Capacity
(HT
, 1);
752 Local_Insert
(HT
, New_Item
, Node
, Inserted
);
755 and then HT
.Length
> HT_Ops
.Capacity
(HT
)
757 HT_Ops
.Reserve_Capacity
(HT
, HT
.Length
);
765 procedure Intersection
766 (Target
: in out Set
;
769 Tgt_Node
: Node_Access
;
772 if Target
'Address = Source
'Address then
776 if Source
.Length
= 0 then
781 if Target
.HT
.Busy
> 0 then
782 raise Program_Error
with
783 "attempt to tamper with elements (set is busy)";
786 Tgt_Node
:= HT_Ops
.First
(Target
.HT
);
787 while Tgt_Node
/= null loop
788 if Is_In
(Source
.HT
, Tgt_Node
) then
789 Tgt_Node
:= HT_Ops
.Next
(Target
.HT
, Tgt_Node
);
793 X
: Node_Access
:= Tgt_Node
;
795 Tgt_Node
:= HT_Ops
.Next
(Target
.HT
, Tgt_Node
);
796 HT_Ops
.Delete_Node_Sans_Free
(Target
.HT
, X
);
803 function Intersection
(Left
, Right
: Set
) return Set
is
804 Buckets
: HT_Types
.Buckets_Access
;
808 if Left
'Address = Right
'Address then
812 Length
:= Count_Type
'Min (Left
.Length
, Right
.Length
);
819 Size
: constant Hash_Type
:= Prime_Numbers
.To_Prime
(Length
);
821 Buckets
:= HT_Ops
.New_Buckets
(Length
=> Size
);
826 Iterate_Left
: declare
827 procedure Process
(L_Node
: Node_Access
);
830 new HT_Ops
.Generic_Iteration
(Process
);
836 procedure Process
(L_Node
: Node_Access
) is
838 if Is_In
(Right
.HT
, L_Node
) then
840 Src
: Element_Type
renames L_Node
.Element
.all;
842 Indx
: constant Hash_Type
:= Hash
(Src
) mod Buckets
'Length;
844 Bucket
: Node_Access
renames Buckets
(Indx
);
846 Tgt
: Element_Access
:= new Element_Type
'(Src);
849 Bucket := new Node_Type'(Tgt
, Bucket
);
856 Length
:= Length
+ 1;
860 -- Start of processing for Iterate_Left
866 HT_Ops
.Free_Hash_Table
(Buckets
);
870 return (Controlled
with HT
=> (Buckets
, Length
, 0, 0));
877 function Is_Empty
(Container
: Set
) return Boolean is
879 return Container
.HT
.Length
= 0;
886 function Is_In
(HT
: Hash_Table_Type
; Key
: Node_Access
) return Boolean is
888 return Element_Keys
.Find
(HT
, Key
.Element
.all) /= null;
897 Of_Set
: Set
) return Boolean
899 Subset_Node
: Node_Access
;
902 if Subset
'Address = Of_Set
'Address then
906 if Subset
.Length
> Of_Set
.Length
then
910 Subset_Node
:= HT_Ops
.First
(Subset
.HT
);
911 while Subset_Node
/= null loop
912 if not Is_In
(Of_Set
.HT
, Subset_Node
) then
916 Subset_Node
:= HT_Ops
.Next
(Subset
.HT
, Subset_Node
);
928 Process
: not null access procedure (Position
: Cursor
))
930 procedure Process_Node
(Node
: Node_Access
);
931 pragma Inline
(Process_Node
);
934 new HT_Ops
.Generic_Iteration
(Process_Node
);
940 procedure Process_Node
(Node
: Node_Access
) is
942 Process
(Cursor
'(Container'Unrestricted_Access, Node));
945 B : Natural renames Container'Unrestricted_Access.HT.Busy;
947 -- Start of processing for Iterate
953 Iterate (Container.HT);
967 function Length (Container : Set) return Count_Type is
969 return Container.HT.Length;
976 procedure Move (Target : in out Set; Source : in out Set) is
978 HT_Ops.Move (Target => Target.HT, Source => Source.HT);
985 function Next (Node : Node_Access) return Node_Access is
990 function Next (Position : Cursor) return Cursor is
992 if Position.Node = null then
996 if Position.Node.Element = null then
997 raise Program_Error with "bad cursor in Next";
1000 pragma Assert (Vet (Position), "bad cursor in Next");
1003 HT : Hash_Table_Type renames Position.Container.HT;
1004 Node : constant Node_Access := HT_Ops.Next (HT, Position.Node);
1011 return Cursor'(Position
.Container
, Node
);
1015 procedure Next
(Position
: in out Cursor
) is
1017 Position
:= Next
(Position
);
1024 function Overlap
(Left
, Right
: Set
) return Boolean is
1025 Left_Node
: Node_Access
;
1028 if Right
.Length
= 0 then
1032 if Left
'Address = Right
'Address then
1036 Left_Node
:= HT_Ops
.First
(Left
.HT
);
1037 while Left_Node
/= null loop
1038 if Is_In
(Right
.HT
, Left_Node
) then
1042 Left_Node
:= HT_Ops
.Next
(Left
.HT
, Left_Node
);
1052 procedure Query_Element
1054 Process
: not null access procedure (Element
: Element_Type
))
1057 if Position
.Node
= null then
1058 raise Constraint_Error
with
1059 "Position cursor of Query_Element equals No_Element";
1062 if Position
.Node
.Element
= null then
1063 raise Program_Error
with "bad cursor in Query_Element";
1066 pragma Assert
(Vet
(Position
), "bad cursor in Query_Element");
1069 HT
: Hash_Table_Type
renames
1070 Position
.Container
'Unrestricted_Access.all.HT
;
1072 B
: Natural renames HT
.Busy
;
1073 L
: Natural renames HT
.Lock
;
1080 Process
(Position
.Node
.Element
.all);
1098 (Stream
: not null access Root_Stream_Type
'Class;
1099 Container
: out Set
)
1102 Read_Nodes
(Stream
, Container
.HT
);
1106 (Stream
: not null access Root_Stream_Type
'Class;
1110 raise Program_Error
with "attempt to stream set cursor";
1118 (Stream
: not null access Root_Stream_Type
'Class) return Node_Access
1120 X
: Element_Access
:= new Element_Type
'(Element_Type'Input (Stream));
1123 return new Node_Type'(X
, null);
1135 (Container
: in out Set
;
1136 New_Item
: Element_Type
)
1138 Node
: constant Node_Access
:=
1139 Element_Keys
.Find
(Container
.HT
, New_Item
);
1142 pragma Warnings
(Off
, X
);
1146 raise Constraint_Error
with
1147 "attempt to replace element not in set";
1150 if Container
.HT
.Lock
> 0 then
1151 raise Program_Error
with
1152 "attempt to tamper with cursors (set is locked)";
1157 Node
.Element
:= new Element_Type
'(New_Item);
1162 ---------------------
1163 -- Replace_Element --
1164 ---------------------
1166 procedure Replace_Element
1167 (Container : in out Set;
1169 New_Item : Element_Type)
1172 if Position.Node = null then
1173 raise Constraint_Error with "Position cursor equals No_Element";
1176 if Position.Node.Element = null then
1177 raise Program_Error with "bad cursor in Replace_Element";
1180 if Position.Container /= Container'Unrestricted_Access then
1181 raise Program_Error with
1182 "Position cursor designates wrong set";
1185 pragma Assert (Vet (Position), "bad cursor in Replace_Element");
1187 Replace_Element (Container.HT, Position.Node, New_Item);
1188 end Replace_Element;
1190 ----------------------
1191 -- Reserve_Capacity --
1192 ----------------------
1194 procedure Reserve_Capacity
1195 (Container : in out Set;
1196 Capacity : Count_Type)
1199 HT_Ops.Reserve_Capacity (Container.HT, Capacity);
1200 end Reserve_Capacity;
1206 procedure Set_Next (Node : Node_Access; Next : Node_Access) is
1211 --------------------------
1212 -- Symmetric_Difference --
1213 --------------------------
1215 procedure Symmetric_Difference
1216 (Target : in out Set;
1220 if Target'Address = Source'Address then
1225 if Target.HT.Busy > 0 then
1226 raise Program_Error with
1227 "attempt to tamper with elements (set is busy)";
1231 N : constant Count_Type := Target.Length + Source.Length;
1233 if N > HT_Ops.Capacity (Target.HT) then
1234 HT_Ops.Reserve_Capacity (Target.HT, N);
1238 if Target.Length = 0 then
1239 Iterate_Source_When_Empty_Target : declare
1240 procedure Process (Src_Node : Node_Access);
1242 procedure Iterate is
1243 new HT_Ops.Generic_Iteration (Process);
1249 procedure Process (Src_Node : Node_Access) is
1250 E : Element_Type renames Src_Node.Element.all;
1251 B : Buckets_Type renames Target.HT.Buckets.all;
1252 J : constant Hash_Type := Hash (E) mod B'Length;
1253 N : Count_Type renames Target.HT.Length;
1257 X : Element_Access := new Element_Type'(E
);
1259 B
(J
) := new Node_Type
'(X, B (J));
1269 -- Start of processing for Iterate_Source_When_Empty_Target
1272 Iterate (Source.HT);
1273 end Iterate_Source_When_Empty_Target;
1276 Iterate_Source : declare
1277 procedure Process (Src_Node : Node_Access);
1279 procedure Iterate is
1280 new HT_Ops.Generic_Iteration (Process);
1286 procedure Process (Src_Node : Node_Access) is
1287 E : Element_Type renames Src_Node.Element.all;
1288 B : Buckets_Type renames Target.HT.Buckets.all;
1289 J : constant Hash_Type := Hash (E) mod B'Length;
1290 N : Count_Type renames Target.HT.Length;
1293 if B (J) = null then
1295 X : Element_Access := new Element_Type'(E
);
1297 B
(J
) := new Node_Type
'(X, null);
1306 elsif Equivalent_Elements (E, B (J).Element.all) then
1308 X : Node_Access := B (J);
1310 B (J) := B (J).Next;
1317 Prev : Node_Access := B (J);
1318 Curr : Node_Access := Prev.Next;
1321 while Curr /= null loop
1322 if Equivalent_Elements (E, Curr.Element.all) then
1323 Prev.Next := Curr.Next;
1334 X : Element_Access := new Element_Type'(E
);
1336 B
(J
) := new Node_Type
'(X, B (J));
1348 -- Start of processing for Iterate_Source
1351 Iterate (Source.HT);
1354 end Symmetric_Difference;
1356 function Symmetric_Difference (Left, Right : Set) return Set is
1357 Buckets : HT_Types.Buckets_Access;
1358 Length : Count_Type;
1361 if Left'Address = Right'Address then
1365 if Right.Length = 0 then
1369 if Left.Length = 0 then
1374 Size : constant Hash_Type :=
1375 Prime_Numbers.To_Prime (Left.Length + Right.Length);
1377 Buckets := HT_Ops.New_Buckets (Length => Size);
1382 Iterate_Left : declare
1383 procedure Process (L_Node : Node_Access);
1385 procedure Iterate is
1386 new HT_Ops.Generic_Iteration (Process);
1392 procedure Process (L_Node : Node_Access) is
1394 if not Is_In (Right.HT, L_Node) then
1396 E : Element_Type renames L_Node.Element.all;
1397 J : constant Hash_Type := Hash (E) mod Buckets'Length;
1401 X : Element_Access := new Element_Type'(E
);
1403 Buckets
(J
) := new Node_Type
'(X, Buckets (J));
1410 Length := Length + 1;
1415 -- Start of processing for Iterate_Left
1421 HT_Ops.Free_Hash_Table (Buckets);
1425 Iterate_Right : declare
1426 procedure Process (R_Node : Node_Access);
1428 procedure Iterate is
1429 new HT_Ops.Generic_Iteration (Process);
1435 procedure Process (R_Node : Node_Access) is
1437 if not Is_In (Left.HT, R_Node) then
1439 E : Element_Type renames R_Node.Element.all;
1440 J : constant Hash_Type := Hash (E) mod Buckets'Length;
1444 X : Element_Access := new Element_Type'(E
);
1446 Buckets
(J
) := new Node_Type
'(X, Buckets (J));
1453 Length := Length + 1;
1458 -- Start of processing for Iterate_Right
1464 HT_Ops.Free_Hash_Table (Buckets);
1468 return (Controlled with HT => (Buckets, Length, 0, 0));
1469 end Symmetric_Difference;
1475 function To_Set (New_Item : Element_Type) return Set is
1476 HT : Hash_Table_Type;
1480 pragma Unreferenced (Node, Inserted);
1483 Insert (HT, New_Item, Node, Inserted);
1484 return Set'(Controlled
with HT
);
1492 (Target
: in out Set
;
1495 procedure Process
(Src_Node
: Node_Access
);
1497 procedure Iterate
is
1498 new HT_Ops
.Generic_Iteration
(Process
);
1504 procedure Process
(Src_Node
: Node_Access
) is
1505 Src
: Element_Type
renames Src_Node
.Element
.all;
1507 function New_Node
(Next
: Node_Access
) return Node_Access
;
1508 pragma Inline
(New_Node
);
1511 new Element_Keys
.Generic_Conditional_Insert
(New_Node
);
1517 function New_Node
(Next
: Node_Access
) return Node_Access
is
1518 Tgt
: Element_Access
:= new Element_Type
'(Src);
1521 return new Node_Type'(Tgt
, Next
);
1528 Tgt_Node
: Node_Access
;
1530 pragma Unreferenced
(Tgt_Node
, Success
);
1532 -- Start of processing for Process
1535 Insert
(Target
.HT
, Src
, Tgt_Node
, Success
);
1538 -- Start of processing for Union
1541 if Target
'Address = Source
'Address then
1545 if Target
.HT
.Busy
> 0 then
1546 raise Program_Error
with
1547 "attempt to tamper with elements (set is busy)";
1551 N
: constant Count_Type
:= Target
.Length
+ Source
.Length
;
1553 if N
> HT_Ops
.Capacity
(Target
.HT
) then
1554 HT_Ops
.Reserve_Capacity
(Target
.HT
, N
);
1558 Iterate
(Source
.HT
);
1561 function Union
(Left
, Right
: Set
) return Set
is
1562 Buckets
: HT_Types
.Buckets_Access
;
1563 Length
: Count_Type
;
1566 if Left
'Address = Right
'Address then
1570 if Right
.Length
= 0 then
1574 if Left
.Length
= 0 then
1579 Size
: constant Hash_Type
:=
1580 Prime_Numbers
.To_Prime
(Left
.Length
+ Right
.Length
);
1582 Buckets
:= HT_Ops
.New_Buckets
(Length
=> Size
);
1585 Iterate_Left
: declare
1586 procedure Process
(L_Node
: Node_Access
);
1588 procedure Iterate
is
1589 new HT_Ops
.Generic_Iteration
(Process
);
1595 procedure Process
(L_Node
: Node_Access
) is
1596 Src
: Element_Type
renames L_Node
.Element
.all;
1598 J
: constant Hash_Type
:= Hash
(Src
) mod Buckets
'Length;
1600 Bucket
: Node_Access
renames Buckets
(J
);
1602 Tgt
: Element_Access
:= new Element_Type
'(Src);
1605 Bucket := new Node_Type'(Tgt
, Bucket
);
1612 -- Start of processing for Process
1618 HT_Ops
.Free_Hash_Table
(Buckets
);
1622 Length
:= Left
.Length
;
1624 Iterate_Right
: declare
1625 procedure Process
(Src_Node
: Node_Access
);
1627 procedure Iterate
is
1628 new HT_Ops
.Generic_Iteration
(Process
);
1634 procedure Process
(Src_Node
: Node_Access
) is
1635 Src
: Element_Type
renames Src_Node
.Element
.all;
1636 Idx
: constant Hash_Type
:= Hash
(Src
) mod Buckets
'Length;
1638 Tgt_Node
: Node_Access
:= Buckets
(Idx
);
1641 while Tgt_Node
/= null loop
1642 if Equivalent_Elements
(Src
, Tgt_Node
.Element
.all) then
1645 Tgt_Node
:= Next
(Tgt_Node
);
1649 Tgt
: Element_Access
:= new Element_Type
'(Src);
1651 Buckets (Idx) := new Node_Type'(Tgt
, Buckets
(Idx
));
1658 Length
:= Length
+ 1;
1661 -- Start of processing for Iterate_Right
1667 HT_Ops
.Free_Hash_Table
(Buckets
);
1671 return (Controlled
with HT
=> (Buckets
, Length
, 0, 0));
1678 function Vet
(Position
: Cursor
) return Boolean is
1680 if Position
.Node
= null then
1681 return Position
.Container
= null;
1684 if Position
.Container
= null then
1688 if Position
.Node
.Next
= Position
.Node
then
1692 if Position
.Node
.Element
= null then
1697 HT
: Hash_Table_Type
renames Position
.Container
.HT
;
1701 if HT
.Length
= 0 then
1705 if HT
.Buckets
= null
1706 or else HT
.Buckets
'Length = 0
1711 X
:= HT
.Buckets
(Element_Keys
.Index
(HT
, Position
.Node
.Element
.all));
1713 for J
in 1 .. HT
.Length
loop
1714 if X
= Position
.Node
then
1722 if X
= X
.Next
then -- to prevent unnecessary looping
1738 (Stream
: not null access Root_Stream_Type
'Class;
1742 Write_Nodes
(Stream
, Container
.HT
);
1746 (Stream
: not null access Root_Stream_Type
'Class;
1750 raise Program_Error
with "attempt to stream set cursor";
1757 procedure Write_Node
1758 (Stream
: not null access Root_Stream_Type
'Class;
1762 Element_Type
'Output (Stream
, Node
.Element
.all);
1765 package body Generic_Keys
is
1767 -----------------------
1768 -- Local Subprograms --
1769 -----------------------
1771 function Equivalent_Key_Node
1773 Node
: Node_Access
) return Boolean;
1774 pragma Inline
(Equivalent_Key_Node
);
1776 --------------------------
1777 -- Local Instantiations --
1778 --------------------------
1781 new Hash_Tables
.Generic_Keys
1782 (HT_Types
=> HT_Types
,
1784 Set_Next
=> Set_Next
,
1785 Key_Type
=> Key_Type
,
1787 Equivalent_Keys
=> Equivalent_Key_Node
);
1795 Key
: Key_Type
) return Boolean
1798 return Find
(Container
, Key
) /= No_Element
;
1806 (Container
: in out Set
;
1812 Key_Keys
.Delete_Key_Sans_Free
(Container
.HT
, Key
, X
);
1815 raise Constraint_Error
with "key not in map";
1827 Key
: Key_Type
) return Element_Type
1829 Node
: constant Node_Access
:= Key_Keys
.Find
(Container
.HT
, Key
);
1833 raise Constraint_Error
with "key not in map";
1836 return Node
.Element
.all;
1839 -------------------------
1840 -- Equivalent_Key_Node --
1841 -------------------------
1843 function Equivalent_Key_Node
1845 Node
: Node_Access
) return Boolean is
1847 return Equivalent_Keys
(Key
, Generic_Keys
.Key
(Node
.Element
.all));
1848 end Equivalent_Key_Node
;
1855 (Container
: in out Set
;
1860 Key_Keys
.Delete_Key_Sans_Free
(Container
.HT
, Key
, X
);
1870 Key
: Key_Type
) return Cursor
1872 Node
: constant Node_Access
:= Key_Keys
.Find
(Container
.HT
, Key
);
1879 return Cursor
'(Container'Unrestricted_Access, Node);
1886 function Key (Position : Cursor) return Key_Type is
1888 if Position.Node = null then
1889 raise Constraint_Error with
1890 "Position cursor equals No_Element";
1893 if Position.Node.Element = null then
1894 raise Program_Error with "Position cursor is bad";
1897 pragma Assert (Vet (Position), "bad cursor in function Key");
1899 return Key (Position.Node.Element.all);
1907 (Container : in out Set;
1909 New_Item : Element_Type)
1911 Node : constant Node_Access :=
1912 Key_Keys.Find (Container.HT, Key);
1916 raise Constraint_Error with
1917 "attempt to replace key not in set";
1920 Replace_Element (Container.HT, Node, New_Item);
1923 procedure Update_Element_Preserving_Key
1924 (Container : in out Set;
1926 Process : not null access
1927 procedure (Element : in out Element_Type))
1929 HT : Hash_Table_Type renames Container.HT;
1933 if Position.Node = null then
1934 raise Constraint_Error with
1935 "Position cursor equals No_Element";
1938 if Position.Node.Element = null
1939 or else Position.Node.Next = Position.Node
1941 raise Program_Error with "Position cursor is bad";
1944 if Position.Container /= Container'Unrestricted_Access then
1945 raise Program_Error with
1946 "Position cursor designates wrong set";
1949 if HT.Buckets = null
1950 or else HT.Buckets'Length = 0
1951 or else HT.Length = 0
1953 raise Program_Error with "Position cursor is bad (set is empty)";
1958 "bad cursor in Update_Element_Preserving_Key");
1960 Indx := HT_Ops.Index (HT, Position.Node);
1963 E : Element_Type renames Position.Node.Element.all;
1964 K : constant Key_Type := Key (E);
1966 B : Natural renames HT.Busy;
1967 L : Natural renames HT.Lock;
1985 if Equivalent_Keys (K, Key (E)) then
1986 pragma Assert (Hash (K) = Hash (E));
1991 if HT.Buckets (Indx) = Position.Node then
1992 HT.Buckets (Indx) := Position.Node.Next;
1996 Prev : Node_Access := HT.Buckets (Indx);
1999 while Prev.Next /= Position.Node loop
2003 raise Program_Error with
2004 "Position cursor is bad (node not found)";
2008 Prev.Next := Position.Node.Next;
2012 HT.Length := HT.Length - 1;
2015 X : Node_Access := Position.Node;
2021 raise Program_Error with "key was modified";
2022 end Update_Element_Preserving_Key;
2026 end Ada.Containers.Indefinite_Hashed_Sets;