1 ------------------------------------------------------------------------------
3 -- GNAT RUNTIME COMPONENTS --
5 -- G N A T . H T A B L E --
10 -- Copyright (C) 1995-1999 Ada Core Technologies, Inc. --
12 -- GNAT is free software; you can redistribute it and/or modify it under --
13 -- terms of the GNU General Public License as published by the Free Soft- --
14 -- ware Foundation; either version 2, or (at your option) any later ver- --
15 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
16 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
17 -- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License --
18 -- for more details. You should have received a copy of the GNU General --
19 -- Public License distributed with GNAT; see file COPYING. If not, write --
20 -- to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, --
21 -- MA 02111-1307, USA. --
23 -- As a special exception, if other files instantiate generics from this --
24 -- unit, or you link this unit with other files to produce an executable, --
25 -- this unit does not by itself cause the resulting executable to be --
26 -- covered by the GNU General Public License. This exception does not --
27 -- however invalidate any other reasons why the executable file might be --
28 -- covered by the GNU Public License. --
30 -- GNAT is maintained by Ada Core Technologies Inc (http://www.gnat.com). --
32 ------------------------------------------------------------------------------
34 with Ada
.Unchecked_Deallocation
;
35 package body GNAT
.HTable
is
41 package body Static_HTable
is
43 Table
: array (Header_Num
) of Elmt_Ptr
;
45 Iterator_Index
: Header_Num
;
46 Iterator_Ptr
: Elmt_Ptr
;
47 Iterator_Started
: Boolean := False;
49 function Get_Non_Null
return Elmt_Ptr
;
50 -- Returns Null_Ptr if Iterator_Started is false of the Table is
51 -- empty. Returns Iterator_Ptr if non null, or the next non null
52 -- element in table if any.
58 function Get
(K
: Key
) return Elmt_Ptr
is
62 Elmt
:= Table
(Hash
(K
));
65 if Elmt
= Null_Ptr
then
68 elsif Equal
(Get_Key
(Elmt
), K
) then
81 function Get_First
return Elmt_Ptr
is
83 Iterator_Started
:= True;
84 Iterator_Index
:= Table
'First;
85 Iterator_Ptr
:= Table
(Iterator_Index
);
93 function Get_Next
return Elmt_Ptr
is
95 if not Iterator_Started
then
99 Iterator_Ptr
:= Next
(Iterator_Ptr
);
107 function Get_Non_Null
return Elmt_Ptr
is
109 while Iterator_Ptr
= Null_Ptr
loop
110 if Iterator_Index
= Table
'Last then
111 Iterator_Started
:= False;
115 Iterator_Index
:= Iterator_Index
+ 1;
116 Iterator_Ptr
:= Table
(Iterator_Index
);
126 procedure Remove
(K
: Key
) is
127 Index
: constant Header_Num
:= Hash
(K
);
129 Next_Elmt
: Elmt_Ptr
;
132 Elmt
:= Table
(Index
);
134 if Elmt
= Null_Ptr
then
137 elsif Equal
(Get_Key
(Elmt
), K
) then
138 Table
(Index
) := Next
(Elmt
);
142 Next_Elmt
:= Next
(Elmt
);
144 if Next_Elmt
= Null_Ptr
then
147 elsif Equal
(Get_Key
(Next_Elmt
), K
) then
148 Set_Next
(Elmt
, Next
(Next_Elmt
));
164 for J
in Table
'Range loop
165 Table
(J
) := Null_Ptr
;
173 procedure Set
(E
: Elmt_Ptr
) is
177 Index
:= Hash
(Get_Key
(E
));
178 Set_Next
(E
, Table
(Index
));
188 package body Simple_HTable
is
190 type Element_Wrapper
;
191 type Elmt_Ptr
is access all Element_Wrapper
;
192 type Element_Wrapper
is record
198 procedure Free
is new
199 Ada
.Unchecked_Deallocation
(Element_Wrapper
, Elmt_Ptr
);
201 procedure Set_Next
(E
: Elmt_Ptr
; Next
: Elmt_Ptr
);
202 function Next
(E
: Elmt_Ptr
) return Elmt_Ptr
;
203 function Get_Key
(E
: Elmt_Ptr
) return Key
;
205 package Tab
is new Static_HTable
(
206 Header_Num
=> Header_Num
,
207 Element
=> Element_Wrapper
,
208 Elmt_Ptr
=> Elmt_Ptr
,
210 Set_Next
=> Set_Next
,
221 function Get
(K
: Key
) return Element
is
222 Tmp
: constant Elmt_Ptr
:= Tab
.Get
(K
);
236 function Get_First
return Element
is
237 Tmp
: constant Elmt_Ptr
:= Tab
.Get_First
;
251 function Get_Key
(E
: Elmt_Ptr
) return Key
is
260 function Get_Next
return Element
is
261 Tmp
: constant Elmt_Ptr
:= Tab
.Get_Next
;
275 function Next
(E
: Elmt_Ptr
) return Elmt_Ptr
is
284 procedure Remove
(K
: Key
) is
305 while E1
/= null loop
318 procedure Set
(K
: Key
; E
: Element
) is
319 Tmp
: constant Elmt_Ptr
:= Tab
.Get
(K
);
323 Tab
.Set
(new Element_Wrapper
'(K, E, null));
333 procedure Set_Next (E : Elmt_Ptr; Next : Elmt_Ptr) is
343 function Hash (Key : String) return Header_Num is
345 type Uns is mod 2 ** 32;
347 function Rotate_Left (Value : Uns; Amount : Natural) return Uns;
348 pragma Import (Intrinsic, Rotate_Left);
353 for J in Key'Range loop
354 Tmp := Rotate_Left (Tmp, 1) + Character'Pos (Key (J));
357 return Header_Num'First +
358 Header_Num'Base (Tmp mod Header_Num'Range_Length);