1 ------------------------------------------------------------------------------
3 -- GNAT RUN-TIME COMPONENTS --
5 -- S Y S T E M . H T A B L E --
9 -- Copyright (C) 1995-2007, AdaCore --
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 -- GNAT was originally developed by the GNAT team at New York University. --
30 -- Extensive contributions were provided by Ada Core Technologies Inc. --
32 ------------------------------------------------------------------------------
34 pragma Warnings (Off);
38 with Ada.Unchecked_Deallocation;
40 package body System.HTable is
46 package body Static_HTable is
48 Table : array (Header_Num) of Elmt_Ptr;
50 Iterator_Index : Header_Num;
51 Iterator_Ptr : Elmt_Ptr;
52 Iterator_Started : Boolean := False;
54 function Get_Non_Null return Elmt_Ptr;
55 -- Returns Null_Ptr if Iterator_Started is false or the Table is empty.
56 -- Returns Iterator_Ptr if non null, or the next non null element in
63 function Get (K : Key) return Elmt_Ptr is
67 Elmt := Table (Hash (K));
70 if Elmt = Null_Ptr then
73 elsif Equal (Get_Key (Elmt), K) then
86 function Get_First return Elmt_Ptr is
88 Iterator_Started := True;
89 Iterator_Index := Table'First;
90 Iterator_Ptr := Table (Iterator_Index);
98 function Get_Next return Elmt_Ptr is
100 if not Iterator_Started then
104 Iterator_Ptr := Next (Iterator_Ptr);
112 function Get_Non_Null return Elmt_Ptr is
114 while Iterator_Ptr = Null_Ptr loop
115 if Iterator_Index = Table'Last then
116 Iterator_Started := False;
120 Iterator_Index := Iterator_Index + 1;
121 Iterator_Ptr := Table (Iterator_Index);
131 procedure Remove (K : Key) is
132 Index : constant Header_Num := Hash (K);
134 Next_Elmt : Elmt_Ptr;
137 Elmt := Table (Index);
139 if Elmt = Null_Ptr then
142 elsif Equal (Get_Key (Elmt), K) then
143 Table (Index) := Next (Elmt);
147 Next_Elmt := Next (Elmt);
149 if Next_Elmt = Null_Ptr then
152 elsif Equal (Get_Key (Next_Elmt), K) then
153 Set_Next (Elmt, Next (Next_Elmt));
169 for J in Table'Range loop
170 Table (J) := Null_Ptr;
178 procedure Set (E : Elmt_Ptr) is
182 Index := Hash (Get_Key (E));
183 Set_Next (E, Table (Index));
193 package body Simple_HTable is
195 type Element_Wrapper;
196 type Elmt_Ptr is access all Element_Wrapper;
197 type Element_Wrapper is record
203 procedure Free is new
204 Ada.Unchecked_Deallocation (Element_Wrapper, Elmt_Ptr);
206 procedure Set_Next (E : Elmt_Ptr; Next : Elmt_Ptr);
207 function Next (E : Elmt_Ptr) return Elmt_Ptr;
208 function Get_Key (E : Elmt_Ptr) return Key;
210 package Tab is new Static_HTable (
211 Header_Num => Header_Num,
212 Element => Element_Wrapper,
213 Elmt_Ptr => Elmt_Ptr,
215 Set_Next => Set_Next,
226 function Get (K : Key) return Element is
227 Tmp : constant Elmt_Ptr := Tab.Get (K);
240 function Get_First return Element is
241 Tmp : constant Elmt_Ptr := Tab.Get_First;
254 function Get_Key (E : Elmt_Ptr) return Key is
263 function Get_Next return Element is
264 Tmp : constant Elmt_Ptr := Tab.Get_Next;
277 function Next (E : Elmt_Ptr) return Elmt_Ptr is
286 procedure Remove (K : Key) is
307 while E1 /= null loop
320 procedure Set (K : Key; E : Element) is
321 Tmp : constant Elmt_Ptr := Tab.Get (K);
324 Tab.Set (new Element_Wrapper'(K, E, null));
334 procedure Set_Next (E : Elmt_Ptr; Next : Elmt_Ptr) is
344 function Hash (Key : String) return Header_Num is
346 type Uns is mod 2 ** 32;
348 function Rotate_Left (Value : Uns; Amount : Natural) return Uns;
349 pragma Import (Intrinsic, Rotate_Left);
355 for J in Key'Range loop
356 Hash_Value := Rotate_Left (Hash_Value, 3) + Character'Pos (Key (J));
359 return Header_Num'First +
360 Header_Num'Base (Hash_Value mod Header_Num'Range_Length);