annotate gcc/ada/libgnat/g-sets.ads @ 131:84e7813d76e9

gcc-8.2
author mir3636
date Thu, 25 Oct 2018 07:37:49 +0900
parents
children 1830386684a0
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
131
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
1 ------------------------------------------------------------------------------
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
2 -- --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
3 -- GNAT RUN-TIME COMPONENTS --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
4 -- --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
5 -- G N A T . S E T S --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
6 -- --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
7 -- S p e c --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
8 -- --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
9 -- Copyright (C) 2018, AdaCore --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
10 -- --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
11 -- GNAT is free software; you can redistribute it and/or modify it under --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
12 -- terms of the GNU General Public License as published by the Free Soft- --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
13 -- ware Foundation; either version 3, or (at your option) any later ver- --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
14 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
15 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
16 -- or FITNESS FOR A PARTICULAR PURPOSE. --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
17 -- --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
18 -- As a special exception under Section 7 of GPL version 3, you are granted --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
19 -- additional permissions described in the GCC Runtime Library Exception, --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
20 -- version 3.1, as published by the Free Software Foundation. --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
21 -- --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
22 -- You should have received a copy of the GNU General Public License and --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
23 -- a copy of the GCC Runtime Library Exception along with this program; --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
24 -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
25 -- <http://www.gnu.org/licenses/>. --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
26 -- --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
27 -- GNAT was originally developed by the GNAT team at New York University. --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
28 -- Extensive contributions were provided by Ada Core Technologies Inc. --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
29 -- --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
30 ------------------------------------------------------------------------------
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
31
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
32 pragma Compiler_Unit_Warning;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
33
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
34 with GNAT.Dynamic_HTables; use GNAT.Dynamic_HTables;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
35
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
36 package GNAT.Sets is
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
37
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
38 --------------------
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
39 -- Membership_Set --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
40 --------------------
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
41
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
42 -- The following package offers a membership set abstraction with the
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
43 -- following characteristics:
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
44 --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
45 -- * Creation of multiple instances, of different sizes.
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
46 -- * Iterable elements.
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
47 --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
48 -- The following use pattern must be employed with this set:
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
49 --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
50 -- Set : Instance := Create (<some size>);
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
51 --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
52 -- <various operations>
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
53 --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
54 -- Destroy (Set);
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
55 --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
56 -- The destruction of the set reclaims all storage occupied by it.
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
57
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
58 generic
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
59 type Element_Type is private;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
60
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
61 with function "="
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
62 (Left : Element_Type;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
63 Right : Element_Type) return Boolean;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
64
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
65 with function Hash (Key : Element_Type) return Bucket_Range_Type;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
66 -- Map an arbitrary key into the range of buckets
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
67
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
68 package Membership_Set is
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
69
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
70 --------------------
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
71 -- Set operations --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
72 --------------------
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
73
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
74 -- The following type denotes a membership set handle. Each instance
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
75 -- must be created using routine Create.
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
76
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
77 type Instance is private;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
78 Nil : constant Instance;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
79
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
80 function Contains (S : Instance; Elem : Element_Type) return Boolean;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
81 -- Determine whether membership set S contains element Elem
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
82
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
83 function Create (Initial_Size : Positive) return Instance;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
84 -- Create a new membership set with bucket capacity Initial_Size. This
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
85 -- routine must be called at the start of the membership set's lifetime.
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
86
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
87 procedure Delete (S : Instance; Elem : Element_Type);
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
88 -- Delete element Elem from membership set S. The routine has no effect
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
89 -- if the element is not present in the membership set. This action will
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
90 -- raise Iterated if the membership set has outstanding iterators.
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
91
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
92 procedure Destroy (S : in out Instance);
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
93 -- Destroy the contents of membership set S, rendering it unusable. This
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
94 -- routine must be called at the end of the membership set's lifetime.
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
95 -- This action will raise Iterated if the hash table has outstanding
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
96 -- iterators.
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
97
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
98 procedure Insert (S : Instance; Elem : Element_Type);
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
99 -- Insert element Elem in membership set S. The routine has no effect
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
100 -- if the element is already present in the membership set. This action
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
101 -- will raise Iterated if the membership set has outstanding iterators.
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
102
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
103 function Is_Empty (S : Instance) return Boolean;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
104 -- Determine whether set S is empty
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
105
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
106 function Size (S : Instance) return Natural;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
107 -- Obtain the number of elements in membership set S
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
108
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
109 -------------------------
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
110 -- Iterator operations --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
111 -------------------------
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
112
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
113 -- The following type represents an element iterator. An iterator locks
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
114 -- all mutation operations, and unlocks them once it is exhausted. The
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
115 -- iterator must be used with the following pattern:
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
116 --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
117 -- Iter := Iterate (My_Set);
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
118 -- while Has_Next (Iter) loop
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
119 -- Next (Iter, Element);
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
120 -- end loop;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
121 --
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
122 -- It is possible to advance the iterator by using Next only, however
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
123 -- this risks raising Iterator_Exhausted.
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
124
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
125 type Iterator is private;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
126
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
127 function Iterate (S : Instance) return Iterator;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
128 -- Obtain an iterator over the elements of membership set S. This action
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
129 -- locks all mutation functionality of the associated membership set.
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
130
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
131 function Has_Next (Iter : Iterator) return Boolean;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
132 -- Determine whether iterator Iter has more keys to examine. If the
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
133 -- iterator has been exhausted, restore all mutation functionality of
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
134 -- the associated membership set.
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
135
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
136 procedure Next (Iter : in out Iterator; Elem : out Element_Type);
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
137 -- Return the current element referenced by iterator Iter and advance
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
138 -- to the next available element. If the iterator has been exhausted
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
139 -- and further attempts are made to advance it, this routine restores
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
140 -- mutation functionality of the associated membership set, and then
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
141 -- raises Iterator_Exhausted.
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
142
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
143 private
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
144 package Hashed_Set is new Dynamic_HTable
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
145 (Key_Type => Element_Type,
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
146 Value_Type => Boolean,
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
147 No_Value => False,
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
148 Expansion_Threshold => 1.5,
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
149 Expansion_Factor => 2,
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
150 Compression_Threshold => 0.3,
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
151 Compression_Factor => 2,
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
152 "=" => "=",
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
153 Hash => Hash);
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
154
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
155 type Instance is new Hashed_Set.Instance;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
156 Nil : constant Instance := Instance (Hashed_Set.Nil);
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
157
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
158 type Iterator is new Hashed_Set.Iterator;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
159 end Membership_Set;
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
160
84e7813d76e9 gcc-8.2
mir3636
parents:
diff changeset
161 end GNAT.Sets;