|
111
|
1 ------------------------------------------------------------------------------
|
|
|
2 -- --
|
|
|
3 -- GNAT LIBRARY COMPONENTS --
|
|
|
4 -- --
|
|
|
5 -- ADA.CONTAINERS.HASH_TABLES.GENERIC_BOUNDED_KEYS --
|
|
|
6 -- --
|
|
|
7 -- B o d y --
|
|
|
8 -- --
|
|
|
9 -- Copyright (C) 2004-2017, Free Software Foundation, Inc. --
|
|
|
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 package body Ada.Containers.Hash_Tables.Generic_Bounded_Keys is
|
|
|
31
|
|
|
32 pragma Warnings (Off, "variable ""Busy*"" is not referenced");
|
|
|
33 pragma Warnings (Off, "variable ""Lock*"" is not referenced");
|
|
|
34 -- See comment in Ada.Containers.Helpers
|
|
|
35
|
|
|
36 -----------------------------
|
|
|
37 -- Checked_Equivalent_Keys --
|
|
|
38 -----------------------------
|
|
|
39
|
|
|
40 function Checked_Equivalent_Keys
|
|
|
41 (HT : aliased in out Hash_Table_Type'Class;
|
|
|
42 Key : Key_Type;
|
|
|
43 Node : Count_Type) return Boolean
|
|
|
44 is
|
|
|
45 Lock : With_Lock (HT.TC'Unrestricted_Access);
|
|
|
46 begin
|
|
|
47 return Equivalent_Keys (Key, HT.Nodes (Node));
|
|
|
48 end Checked_Equivalent_Keys;
|
|
|
49
|
|
|
50 -------------------
|
|
|
51 -- Checked_Index --
|
|
|
52 -------------------
|
|
|
53
|
|
|
54 function Checked_Index
|
|
|
55 (HT : aliased in out Hash_Table_Type'Class;
|
|
|
56 Key : Key_Type) return Hash_Type
|
|
|
57 is
|
|
|
58 Lock : With_Lock (HT.TC'Unrestricted_Access);
|
|
|
59 begin
|
|
|
60 return HT.Buckets'First + Hash (Key) mod HT.Buckets'Length;
|
|
|
61 end Checked_Index;
|
|
|
62
|
|
|
63 --------------------------
|
|
|
64 -- Delete_Key_Sans_Free --
|
|
|
65 --------------------------
|
|
|
66
|
|
|
67 procedure Delete_Key_Sans_Free
|
|
|
68 (HT : in out Hash_Table_Type'Class;
|
|
|
69 Key : Key_Type;
|
|
|
70 X : out Count_Type)
|
|
|
71 is
|
|
|
72 Indx : Hash_Type;
|
|
|
73 Prev : Count_Type;
|
|
|
74
|
|
|
75 begin
|
|
|
76 if HT.Length = 0 then
|
|
|
77 X := 0;
|
|
|
78 return;
|
|
|
79 end if;
|
|
|
80
|
|
|
81 -- Per AI05-0022, the container implementation is required to detect
|
|
|
82 -- element tampering by a generic actual subprogram.
|
|
|
83
|
|
|
84 TC_Check (HT.TC);
|
|
|
85
|
|
|
86 Indx := Checked_Index (HT, Key);
|
|
|
87 X := HT.Buckets (Indx);
|
|
|
88
|
|
|
89 if X = 0 then
|
|
|
90 return;
|
|
|
91 end if;
|
|
|
92
|
|
|
93 if Checked_Equivalent_Keys (HT, Key, X) then
|
|
|
94 TC_Check (HT.TC);
|
|
|
95 HT.Buckets (Indx) := Next (HT.Nodes (X));
|
|
|
96 HT.Length := HT.Length - 1;
|
|
|
97 return;
|
|
|
98 end if;
|
|
|
99
|
|
|
100 loop
|
|
|
101 Prev := X;
|
|
|
102 X := Next (HT.Nodes (Prev));
|
|
|
103
|
|
|
104 if X = 0 then
|
|
|
105 return;
|
|
|
106 end if;
|
|
|
107
|
|
|
108 if Checked_Equivalent_Keys (HT, Key, X) then
|
|
|
109 TC_Check (HT.TC);
|
|
|
110 Set_Next (HT.Nodes (Prev), Next => Next (HT.Nodes (X)));
|
|
|
111 HT.Length := HT.Length - 1;
|
|
|
112 return;
|
|
|
113 end if;
|
|
|
114 end loop;
|
|
|
115 end Delete_Key_Sans_Free;
|
|
|
116
|
|
|
117 ----------
|
|
|
118 -- Find --
|
|
|
119 ----------
|
|
|
120
|
|
|
121 function Find
|
|
|
122 (HT : Hash_Table_Type'Class;
|
|
|
123 Key : Key_Type) return Count_Type
|
|
|
124 is
|
|
|
125 Indx : Hash_Type;
|
|
|
126 Node : Count_Type;
|
|
|
127
|
|
|
128 begin
|
|
|
129 if HT.Length = 0 then
|
|
|
130 return 0;
|
|
|
131 end if;
|
|
|
132
|
|
|
133 Indx := Checked_Index (HT'Unrestricted_Access.all, Key);
|
|
|
134
|
|
|
135 Node := HT.Buckets (Indx);
|
|
|
136 while Node /= 0 loop
|
|
|
137 if Checked_Equivalent_Keys
|
|
|
138 (HT'Unrestricted_Access.all, Key, Node)
|
|
|
139 then
|
|
|
140 return Node;
|
|
|
141 end if;
|
|
|
142 Node := Next (HT.Nodes (Node));
|
|
|
143 end loop;
|
|
|
144
|
|
|
145 return 0;
|
|
|
146 end Find;
|
|
|
147
|
|
|
148 --------------------------------
|
|
|
149 -- Generic_Conditional_Insert --
|
|
|
150 --------------------------------
|
|
|
151
|
|
|
152 procedure Generic_Conditional_Insert
|
|
|
153 (HT : in out Hash_Table_Type'Class;
|
|
|
154 Key : Key_Type;
|
|
|
155 Node : out Count_Type;
|
|
|
156 Inserted : out Boolean)
|
|
|
157 is
|
|
|
158 Indx : Hash_Type;
|
|
|
159
|
|
|
160 begin
|
|
|
161 -- Per AI05-0022, the container implementation is required to detect
|
|
|
162 -- element tampering by a generic actual subprogram.
|
|
|
163
|
|
|
164 TC_Check (HT.TC);
|
|
|
165
|
|
|
166 Indx := Checked_Index (HT, Key);
|
|
|
167 Node := HT.Buckets (Indx);
|
|
|
168
|
|
|
169 if Node = 0 then
|
|
|
170 if Checks and then HT.Length = HT.Capacity then
|
|
|
171 raise Capacity_Error with "no more capacity for insertion";
|
|
|
172 end if;
|
|
|
173
|
|
|
174 Node := New_Node;
|
|
|
175 Set_Next (HT.Nodes (Node), Next => 0);
|
|
|
176
|
|
|
177 Inserted := True;
|
|
|
178
|
|
|
179 HT.Buckets (Indx) := Node;
|
|
|
180 HT.Length := HT.Length + 1;
|
|
|
181
|
|
|
182 return;
|
|
|
183 end if;
|
|
|
184
|
|
|
185 loop
|
|
|
186 if Checked_Equivalent_Keys (HT, Key, Node) then
|
|
|
187 Inserted := False;
|
|
|
188 return;
|
|
|
189 end if;
|
|
|
190
|
|
|
191 Node := Next (HT.Nodes (Node));
|
|
|
192
|
|
|
193 exit when Node = 0;
|
|
|
194 end loop;
|
|
|
195
|
|
|
196 if Checks and then HT.Length = HT.Capacity then
|
|
|
197 raise Capacity_Error with "no more capacity for insertion";
|
|
|
198 end if;
|
|
|
199
|
|
|
200 Node := New_Node;
|
|
|
201 Set_Next (HT.Nodes (Node), Next => HT.Buckets (Indx));
|
|
|
202
|
|
|
203 Inserted := True;
|
|
|
204
|
|
|
205 HT.Buckets (Indx) := Node;
|
|
|
206 HT.Length := HT.Length + 1;
|
|
|
207 end Generic_Conditional_Insert;
|
|
|
208
|
|
|
209 -----------------------------
|
|
|
210 -- Generic_Replace_Element --
|
|
|
211 -----------------------------
|
|
|
212
|
|
|
213 procedure Generic_Replace_Element
|
|
|
214 (HT : in out Hash_Table_Type'Class;
|
|
|
215 Node : Count_Type;
|
|
|
216 Key : Key_Type)
|
|
|
217 is
|
|
|
218 pragma Assert (HT.Length > 0);
|
|
|
219 pragma Assert (Node /= 0);
|
|
|
220
|
|
|
221 BB : Buckets_Type renames HT.Buckets;
|
|
|
222 NN : Nodes_Type renames HT.Nodes;
|
|
|
223
|
|
|
224 Old_Indx : Hash_Type;
|
|
|
225 New_Indx : constant Hash_Type := Checked_Index (HT, Key);
|
|
|
226
|
|
|
227 New_Bucket : Count_Type renames BB (New_Indx);
|
|
|
228 N, M : Count_Type;
|
|
|
229
|
|
|
230 begin
|
|
|
231 -- Per AI05-0022, the container implementation is required to detect
|
|
|
232 -- element tampering by a generic actual subprogram.
|
|
|
233
|
|
|
234 -- The following block appears to be vestigial -- this should be done
|
|
|
235 -- using Checked_Index instead. Also, we might have to move the actual
|
|
|
236 -- tampering checks to the top of the subprogram, in order to prevent
|
|
|
237 -- infinite recursion when calling Hash. (This is similar to how Insert
|
|
|
238 -- and Delete are implemented.) This implies that we will have to defer
|
|
|
239 -- the computation of New_Index until after the tampering check. ???
|
|
|
240
|
|
|
241 declare
|
|
|
242 Lock : With_Lock (HT.TC'Unrestricted_Access);
|
|
|
243 begin
|
|
|
244 Old_Indx := HT.Buckets'First + Hash (NN (Node)) mod HT.Buckets'Length;
|
|
|
245 end;
|
|
|
246
|
|
|
247 -- Replace_Element is allowed to change a node's key to Key
|
|
|
248 -- (generic formal operation Assign provides the mechanism), but
|
|
|
249 -- only if Key is not already in the hash table. (In a unique-key
|
|
|
250 -- hash table as this one, a key is mapped to exactly one node.)
|
|
|
251
|
|
|
252 if Checked_Equivalent_Keys (HT, Key, Node) then
|
|
|
253 TE_Check (HT.TC);
|
|
|
254
|
|
|
255 -- The new Key value is mapped to this same Node, so Node
|
|
|
256 -- stays in the same bucket.
|
|
|
257
|
|
|
258 Assign (NN (Node), Key);
|
|
|
259 return;
|
|
|
260 end if;
|
|
|
261
|
|
|
262 -- Key is not equivalent to Node, so we now have to determine if it's
|
|
|
263 -- equivalent to some other node in the hash table. This is the case
|
|
|
264 -- irrespective of whether Key is in the same or a different bucket from
|
|
|
265 -- Node.
|
|
|
266
|
|
|
267 N := New_Bucket;
|
|
|
268 while N /= 0 loop
|
|
|
269 if Checks and then Checked_Equivalent_Keys (HT, Key, N) then
|
|
|
270 pragma Assert (N /= Node);
|
|
|
271 raise Program_Error with
|
|
|
272 "attempt to replace existing element";
|
|
|
273 end if;
|
|
|
274
|
|
|
275 N := Next (NN (N));
|
|
|
276 end loop;
|
|
|
277
|
|
|
278 -- We have determined that Key is not already in the hash table, so
|
|
|
279 -- the change is tentatively allowed. We now perform the standard
|
|
|
280 -- checks to determine whether the hash table is locked (because you
|
|
|
281 -- cannot change an element while it's in use by Query_Element or
|
|
|
282 -- Update_Element), or if the container is busy (because moving a
|
|
|
283 -- node to a different bucket would interfere with iteration).
|
|
|
284
|
|
|
285 if Old_Indx = New_Indx then
|
|
|
286 -- The node is already in the bucket implied by Key. In this case
|
|
|
287 -- we merely change its value without moving it.
|
|
|
288
|
|
|
289 TE_Check (HT.TC);
|
|
|
290
|
|
|
291 Assign (NN (Node), Key);
|
|
|
292 return;
|
|
|
293 end if;
|
|
|
294
|
|
|
295 -- The node is a bucket different from the bucket implied by Key
|
|
|
296
|
|
|
297 TC_Check (HT.TC);
|
|
|
298
|
|
|
299 -- Do the assignment first, before moving the node, so that if Assign
|
|
|
300 -- propagates an exception, then the hash table will not have been
|
|
|
301 -- modified (except for any possible side-effect Assign had on Node).
|
|
|
302
|
|
|
303 Assign (NN (Node), Key);
|
|
|
304
|
|
|
305 -- Now we can safely remove the node from its current bucket
|
|
|
306
|
|
|
307 N := BB (Old_Indx); -- get value of first node in old bucket
|
|
|
308 pragma Assert (N /= 0);
|
|
|
309
|
|
|
310 if N = Node then -- node is first node in its bucket
|
|
|
311 BB (Old_Indx) := Next (NN (Node));
|
|
|
312
|
|
|
313 else
|
|
|
314 pragma Assert (HT.Length > 1);
|
|
|
315
|
|
|
316 loop
|
|
|
317 M := Next (NN (N));
|
|
|
318 pragma Assert (M /= 0);
|
|
|
319
|
|
|
320 if M = Node then
|
|
|
321 Set_Next (NN (N), Next => Next (NN (Node)));
|
|
|
322 exit;
|
|
|
323 end if;
|
|
|
324
|
|
|
325 N := M;
|
|
|
326 end loop;
|
|
|
327 end if;
|
|
|
328
|
|
|
329 -- Now we link the node into its new bucket (corresponding to Key)
|
|
|
330
|
|
|
331 Set_Next (NN (Node), Next => New_Bucket);
|
|
|
332 New_Bucket := Node;
|
|
|
333 end Generic_Replace_Element;
|
|
|
334
|
|
|
335 -----------
|
|
|
336 -- Index --
|
|
|
337 -----------
|
|
|
338
|
|
|
339 function Index
|
|
|
340 (HT : Hash_Table_Type'Class;
|
|
|
341 Key : Key_Type) return Hash_Type is
|
|
|
342 begin
|
|
|
343 return HT.Buckets'First + Hash (Key) mod HT.Buckets'Length;
|
|
|
344 end Index;
|
|
|
345
|
|
|
346 end Ada.Containers.Hash_Tables.Generic_Bounded_Keys;
|
