1 ------------------------------------------------------------------------------
3 -- GNAT LIBRARY COMPONENTS --
5 -- ADA.CONTAINERS.HASH_TABLES.GENERIC_BOUNDED_KEYS --
9 -- Copyright (C) 2004-2019, 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 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. --
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. --
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/>. --
27 -- This unit was originally developed by Matthew J Heaney. --
28 ------------------------------------------------------------------------------
30 package body Ada.Containers.Hash_Tables.Generic_Bounded_Keys is
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
36 -----------------------------
37 -- Checked_Equivalent_Keys --
38 -----------------------------
40 function Checked_Equivalent_Keys
41 (HT : aliased in out Hash_Table_Type'Class;
43 Node : Count_Type) return Boolean
45 Lock : With_Lock (HT.TC'Unrestricted_Access);
47 return Equivalent_Keys (Key, HT.Nodes (Node));
48 end Checked_Equivalent_Keys;
54 function Checked_Index
55 (HT : aliased in out Hash_Table_Type'Class;
56 Key : Key_Type) return Hash_Type
58 Lock : With_Lock (HT.TC'Unrestricted_Access);
60 return HT.Buckets'First + Hash (Key) mod HT.Buckets'Length;
63 --------------------------
64 -- Delete_Key_Sans_Free --
65 --------------------------
67 procedure Delete_Key_Sans_Free
68 (HT : in out Hash_Table_Type'Class;
81 -- Per AI05-0022, the container implementation is required to detect
82 -- element tampering by a generic actual subprogram.
86 Indx := Checked_Index (HT, Key);
87 X := HT.Buckets (Indx);
93 if Checked_Equivalent_Keys (HT, Key, X) then
95 HT.Buckets (Indx) := Next (HT.Nodes (X));
96 HT.Length := HT.Length - 1;
102 X := Next (HT.Nodes (Prev));
108 if Checked_Equivalent_Keys (HT, Key, X) then
110 Set_Next (HT.Nodes (Prev), Next => Next (HT.Nodes (X)));
111 HT.Length := HT.Length - 1;
115 end Delete_Key_Sans_Free;
122 (HT : Hash_Table_Type'Class;
123 Key : Key_Type) return Count_Type
129 if HT.Length = 0 then
133 Indx := Checked_Index (HT'Unrestricted_Access.all, Key);
135 Node := HT.Buckets (Indx);
137 if Checked_Equivalent_Keys
138 (HT'Unrestricted_Access.all, Key, Node)
142 Node := Next (HT.Nodes (Node));
148 --------------------------------
149 -- Generic_Conditional_Insert --
150 --------------------------------
152 procedure Generic_Conditional_Insert
153 (HT : in out Hash_Table_Type'Class;
155 Node : out Count_Type;
156 Inserted : out Boolean)
161 -- Per AI05-0022, the container implementation is required to detect
162 -- element tampering by a generic actual subprogram.
166 Indx := Checked_Index (HT, Key);
167 Node := HT.Buckets (Indx);
170 if Checks and then HT.Length = HT.Capacity then
171 raise Capacity_Error with "no more capacity for insertion";
175 Set_Next (HT.Nodes (Node), Next => 0);
179 HT.Buckets (Indx) := Node;
180 HT.Length := HT.Length + 1;
186 if Checked_Equivalent_Keys (HT, Key, Node) then
191 Node := Next (HT.Nodes (Node));
196 if Checks and then HT.Length = HT.Capacity then
197 raise Capacity_Error with "no more capacity for insertion";
201 Set_Next (HT.Nodes (Node), Next => HT.Buckets (Indx));
205 HT.Buckets (Indx) := Node;
206 HT.Length := HT.Length + 1;
207 end Generic_Conditional_Insert;
209 -----------------------------
210 -- Generic_Replace_Element --
211 -----------------------------
213 procedure Generic_Replace_Element
214 (HT : in out Hash_Table_Type'Class;
218 pragma Assert (HT.Length > 0);
219 pragma Assert (Node /= 0);
221 BB : Buckets_Type renames HT.Buckets;
222 NN : Nodes_Type renames HT.Nodes;
224 Old_Indx : Hash_Type;
225 New_Indx : constant Hash_Type := Checked_Index (HT, Key);
227 New_Bucket : Count_Type renames BB (New_Indx);
231 -- Per AI05-0022, the container implementation is required to detect
232 -- element tampering by a generic actual subprogram.
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. ???
242 Lock : With_Lock (HT.TC'Unrestricted_Access);
244 Old_Indx := HT.Buckets'First + Hash (NN (Node)) mod HT.Buckets'Length;
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.)
252 if Checked_Equivalent_Keys (HT, Key, Node) then
255 -- The new Key value is mapped to this same Node, so Node
256 -- stays in the same bucket.
258 Assign (NN (Node), Key);
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
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";
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).
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.
291 Assign (NN (Node), Key);
295 -- The node is a bucket different from the bucket implied by Key
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).
303 Assign (NN (Node), Key);
305 -- Now we can safely remove the node from its current bucket
307 N := BB (Old_Indx); -- get value of first node in old bucket
308 pragma Assert (N /= 0);
310 if N = Node then -- node is first node in its bucket
311 BB (Old_Indx) := Next (NN (Node));
314 pragma Assert (HT.Length > 1);
318 pragma Assert (M /= 0);
321 Set_Next (NN (N), Next => Next (NN (Node)));
329 -- Now we link the node into its new bucket (corresponding to Key)
331 Set_Next (NN (Node), Next => New_Bucket);
333 end Generic_Replace_Element;
340 (HT : Hash_Table_Type'Class;
341 Key : Key_Type) return Hash_Type is
343 return HT.Buckets'First + Hash (Key) mod HT.Buckets'Length;
346 end Ada.Containers.Hash_Tables.Generic_Bounded_Keys;