Mercurial > hg > CbC > CbC_gcc

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

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc-8.2
author mir3636
date Thu, 25 Oct 2018 07:37:49 +0900
parents
children 1830386684a0
comparison
equal deleted inserted replaced
111:04ced10e8804 131:84e7813d76e9
1 ------------------------------------------------------------------------------
2 -- --
3 -- GNAT RUN-TIME COMPONENTS --
4 -- --
5 -- G N A T . S E T S --
6 -- --
7 -- S p e c --
8 -- --
9 -- Copyright (C) 2018, AdaCore --
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 -- GNAT was originally developed by the GNAT team at New York University. --
28 -- Extensive contributions were provided by Ada Core Technologies Inc. --
29 -- --
30 ------------------------------------------------------------------------------
31
32 pragma Compiler_Unit_Warning;
33
34 with GNAT.Dynamic_HTables; use GNAT.Dynamic_HTables;
35
36 package GNAT.Sets is
37
38 --------------------
39 -- Membership_Set --
40 --------------------
41
42 -- The following package offers a membership set abstraction with the
43 -- following characteristics:
44 --
45 -- * Creation of multiple instances, of different sizes.
46 -- * Iterable elements.
47 --
48 -- The following use pattern must be employed with this set:
49 --
50 -- Set : Instance := Create (<some size>);
51 --
52 -- <various operations>
53 --
54 -- Destroy (Set);
55 --
56 -- The destruction of the set reclaims all storage occupied by it.
57
58 generic
59 type Element_Type is private;
60
61 with function "="
62 (Left : Element_Type;
63 Right : Element_Type) return Boolean;
64
65 with function Hash (Key : Element_Type) return Bucket_Range_Type;
66 -- Map an arbitrary key into the range of buckets
67
68 package Membership_Set is
69
70 --------------------
71 -- Set operations --
72 --------------------
73
74 -- The following type denotes a membership set handle. Each instance
75 -- must be created using routine Create.
76
77 type Instance is private;
78 Nil : constant Instance;
79
80 function Contains (S : Instance; Elem : Element_Type) return Boolean;
81 -- Determine whether membership set S contains element Elem
82
83 function Create (Initial_Size : Positive) return Instance;
84 -- Create a new membership set with bucket capacity Initial_Size. This
85 -- routine must be called at the start of the membership set's lifetime.
86
87 procedure Delete (S : Instance; Elem : Element_Type);
88 -- Delete element Elem from membership set S. The routine has no effect
89 -- if the element is not present in the membership set. This action will
90 -- raise Iterated if the membership set has outstanding iterators.
91
92 procedure Destroy (S : in out Instance);
93 -- Destroy the contents of membership set S, rendering it unusable. This
94 -- routine must be called at the end of the membership set's lifetime.
95 -- This action will raise Iterated if the hash table has outstanding
96 -- iterators.
97
98 procedure Insert (S : Instance; Elem : Element_Type);
99 -- Insert element Elem in membership set S. The routine has no effect
100 -- if the element is already present in the membership set. This action
101 -- will raise Iterated if the membership set has outstanding iterators.
102
103 function Is_Empty (S : Instance) return Boolean;
104 -- Determine whether set S is empty
105
106 function Size (S : Instance) return Natural;
107 -- Obtain the number of elements in membership set S
108
109 -------------------------
110 -- Iterator operations --
111 -------------------------
112
113 -- The following type represents an element iterator. An iterator locks
114 -- all mutation operations, and unlocks them once it is exhausted. The
115 -- iterator must be used with the following pattern:
116 --
117 -- Iter := Iterate (My_Set);
118 -- while Has_Next (Iter) loop
119 -- Next (Iter, Element);
120 -- end loop;
121 --
122 -- It is possible to advance the iterator by using Next only, however
123 -- this risks raising Iterator_Exhausted.
124
125 type Iterator is private;
126
127 function Iterate (S : Instance) return Iterator;
128 -- Obtain an iterator over the elements of membership set S. This action
129 -- locks all mutation functionality of the associated membership set.
130
131 function Has_Next (Iter : Iterator) return Boolean;
132 -- Determine whether iterator Iter has more keys to examine. If the
133 -- iterator has been exhausted, restore all mutation functionality of
134 -- the associated membership set.
135
136 procedure Next (Iter : in out Iterator; Elem : out Element_Type);
137 -- Return the current element referenced by iterator Iter and advance
138 -- to the next available element. If the iterator has been exhausted
139 -- and further attempts are made to advance it, this routine restores
140 -- mutation functionality of the associated membership set, and then
141 -- raises Iterator_Exhausted.
142
143 private
144 package Hashed_Set is new Dynamic_HTable
145 (Key_Type => Element_Type,
146 Value_Type => Boolean,
147 No_Value => False,
148 Expansion_Threshold => 1.5,
149 Expansion_Factor => 2,
150 Compression_Threshold => 0.3,
151 Compression_Factor => 2,
152 "=" => "=",
153 Hash => Hash);
154
155 type Instance is new Hashed_Set.Instance;
156 Nil : constant Instance := Instance (Hashed_Set.Nil);
157
158 type Iterator is new Hashed_Set.Iterator;
159 end Membership_Set;
160
161 end GNAT.Sets;