1 ------------------------------------------------------------------------------
3 -- GNAT RUN-TIME COMPONENTS --
5 -- S Y S T E M . H T A B L E --
9 -- Copyright (C) 1995-2009, 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 ------------------------------------------------------------------------------
36 with Ada
.Unchecked_Deallocation
;
37 with System
.String_Hash
;
39 package body System
.HTable
is
45 package body Static_HTable
is
47 Table
: array (Header_Num
) of Elmt_Ptr
;
49 Iterator_Index
: Header_Num
;
50 Iterator_Ptr
: Elmt_Ptr
;
51 Iterator_Started
: Boolean := False;
53 function Get_Non_Null
return Elmt_Ptr
;
54 -- Returns Null_Ptr if Iterator_Started is false or the Table is empty.
55 -- Returns Iterator_Ptr if non null, or the next non null element in
62 function Get
(K
: Key
) return Elmt_Ptr
is
66 Elmt
:= Table
(Hash
(K
));
69 if Elmt
= Null_Ptr
then
72 elsif Equal
(Get_Key
(Elmt
), K
) then
85 function Get_First
return Elmt_Ptr
is
87 Iterator_Started
:= True;
88 Iterator_Index
:= Table
'First;
89 Iterator_Ptr
:= Table
(Iterator_Index
);
97 function Get_Next
return Elmt_Ptr
is
99 if not Iterator_Started
then
103 Iterator_Ptr
:= Next
(Iterator_Ptr
);
111 function Get_Non_Null
return Elmt_Ptr
is
113 while Iterator_Ptr
= Null_Ptr
loop
114 if Iterator_Index
= Table
'Last then
115 Iterator_Started
:= False;
119 Iterator_Index
:= Iterator_Index
+ 1;
120 Iterator_Ptr
:= Table
(Iterator_Index
);
130 procedure Remove
(K
: Key
) is
131 Index
: constant Header_Num
:= Hash
(K
);
133 Next_Elmt
: Elmt_Ptr
;
136 Elmt
:= Table
(Index
);
138 if Elmt
= Null_Ptr
then
141 elsif Equal
(Get_Key
(Elmt
), K
) then
142 Table
(Index
) := Next
(Elmt
);
146 Next_Elmt
:= Next
(Elmt
);
148 if Next_Elmt
= Null_Ptr
then
151 elsif Equal
(Get_Key
(Next_Elmt
), K
) then
152 Set_Next
(Elmt
, Next
(Next_Elmt
));
168 for J
in Table
'Range loop
169 Table
(J
) := Null_Ptr
;
177 procedure Set
(E
: Elmt_Ptr
) is
181 Index
:= Hash
(Get_Key
(E
));
182 Set_Next
(E
, Table
(Index
));
192 package body Simple_HTable
is
194 type Element_Wrapper
;
195 type Elmt_Ptr
is access all Element_Wrapper
;
196 type Element_Wrapper
is record
202 procedure Free
is new
203 Ada
.Unchecked_Deallocation
(Element_Wrapper
, Elmt_Ptr
);
205 procedure Set_Next
(E
: Elmt_Ptr
; Next
: Elmt_Ptr
);
206 function Next
(E
: Elmt_Ptr
) return Elmt_Ptr
;
207 function Get_Key
(E
: Elmt_Ptr
) return Key
;
209 package Tab
is new Static_HTable
(
210 Header_Num
=> Header_Num
,
211 Element
=> Element_Wrapper
,
212 Elmt_Ptr
=> Elmt_Ptr
,
214 Set_Next
=> Set_Next
,
225 function Get
(K
: Key
) return Element
is
226 Tmp
: constant Elmt_Ptr
:= Tab
.Get
(K
);
239 function Get_First
return Element
is
240 Tmp
: constant Elmt_Ptr
:= Tab
.Get_First
;
253 function Get_Key
(E
: Elmt_Ptr
) return Key
is
262 function Get_Next
return Element
is
263 Tmp
: constant Elmt_Ptr
:= Tab
.Get_Next
;
276 function Next
(E
: Elmt_Ptr
) return Elmt_Ptr
is
285 procedure Remove
(K
: Key
) is
306 while E1
/= null loop
319 procedure Set
(K
: Key
; E
: Element
) is
320 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
344 type Uns is mod 2 ** 32;
347 new System.String_Hash.Hash (Character, String, Uns);
350 return Header_Num'First +
351 Header_Num'Base (Hash_Fun (Key) mod Header_Num'Range_Length);