1 ------------------------------------------------------------------------------
3 -- GNAT RUN-TIME COMPONENTS --
5 -- G N A T . H T A B L E --
9 -- Copyright (C) 1995-2010, 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 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 -- GNAT was originally developed by the GNAT team at New York University. --
28 -- Extensive contributions were provided by Ada Core Technologies Inc. --
30 ------------------------------------------------------------------------------
32 -- Hash table searching routines
34 -- This package contains two separate packages. The Simple_HTable package
35 -- provides a very simple abstraction that associates one element to one
36 -- key value and takes care of all allocations automatically using the heap.
37 -- The Static_HTable package provides a more complex interface that allows
38 -- complete control over allocation.
40 -- Note: actual code is found in System.HTable (s-htable.ads/adb) since
41 -- this facility is accessed from run time routines, but clients should
42 -- always access the version supplied via GNAT.HTable.
48 package GNAT.HTable is
50 pragma Elaborate_Body;
51 -- The elaborate body is because we have a dummy body to deal with
52 -- bootstrap path problems (we used to have a real body, and now we don't
53 -- need it any more, but the bootstrap requires that we have a dummy body,
54 -- since otherwise the old body gets picked up.
60 -- A simple hash table abstraction, easy to instantiate, easy to use.
61 -- The table associates one element to one key with the procedure Set.
62 -- Get retrieves the Element stored for a given Key. The efficiency of
63 -- retrieval is function of the size of the Table parameterized by
64 -- Header_Num and the hashing function Hash.
66 generic package Simple_HTable renames System.HTable.Simple_HTable;
68 -- For convenience of reference here is what this package has in it:
71 -- type Header_Num is range <>;
72 -- -- An integer type indicating the number and range of hash headers
74 -- type Element is private;
75 -- -- The type of element to be stored
77 -- No_Element : Element;
78 -- -- The object that is returned by Get when no element has been set
81 -- type Key is private;
82 -- with function Hash (F : Key) return Header_Num;
83 -- with function Equal (F1, F2 : Key) return Boolean;
85 -- package Simple_HTable is
87 -- procedure Set (K : Key; E : Element);
88 -- -- Associates an element with a given key. Overrides any previously
89 -- -- associated element.
92 -- -- Removes and frees all elements in the table
94 -- function Get (K : Key) return Element;
95 -- -- Returns the Element associated with a key or No_Element if the
96 -- -- given key has not associated element
98 -- procedure Remove (K : Key);
99 -- -- Removes the latest inserted element pointer associated with the
100 -- -- given key if any, does nothing if none.
102 -- function Get_First return Element;
103 -- -- Returns No_Element if the HTable is empty, otherwise returns one
104 -- -- non specified element. There is no guarantee that two calls to
105 -- -- this function will return the same element.
107 -- function Get_Next return Element;
108 -- -- Returns a non-specified element that has not been returned by the
109 -- -- same function since the last call to Get_First or No_Element if
110 -- -- there is no such element. If there is no call to 'Set' in between
111 -- -- Get_Next calls, all the elements of the HTable will be traversed.
113 -- procedure Get_First (K : out Key; E : out Element);
114 -- -- This version of the iterator returns a key/element pair. A non-
115 -- -- specified entry is returned, and there is no guarantee that two
116 -- -- calls to this procedure will return the same element.
118 -- procedure Get_Next (K : out Key; E : out Element);
119 -- -- This version of the iterator returns a key/element pair. It
120 -- -- returns a non-specified element that has not been returned since
121 -- -- the last call to Get_First. If there is no remaining element,
122 -- -- then E is set to No_Element, and the value in K is undefined.
123 -- -- If there is no call to Set in between Get_Next calls, all the
124 -- -- elements of the HTable will be traversed.
126 -- end Simple_HTable;
132 -- A low-level Hash-Table abstraction, not as easy to instantiate as
133 -- Simple_HTable but designed to allow complete control over the
134 -- allocation of necessary data structures. Particularly useful when
135 -- dynamic allocation is not desired. The model is that each Element
136 -- contains its own Key that can be retrieved by Get_Key. Furthermore,
137 -- Element provides a link that can be used by the HTable for linking
138 -- elements with same hash codes:
142 -- +-------------------+
144 -- +-------------------+
146 -- +-------------------+
148 -- +-------------------+
150 generic package Static_HTable renames System.HTable.Static_HTable;
152 -- For convenience of reference here is what this package has in it:
155 -- type Header_Num is range <>;
156 -- -- An integer type indicating the number and range of hash headers.
158 -- type Element (<>) is limited private;
159 -- -- The type of element to be stored
161 -- type Elmt_Ptr is private;
162 -- -- The type used to reference an element (will usually be an
163 -- -- access type, but could be some other form of type such as
164 -- -- an integer type).
166 -- Null_Ptr : Elmt_Ptr;
167 -- -- The null value of the Elmt_Ptr type.
169 -- with procedure Set_Next (E : Elmt_Ptr; Next : Elmt_Ptr);
170 -- with function Next (E : Elmt_Ptr) return Elmt_Ptr;
171 -- -- The type must provide an internal link for the sake of the
172 -- -- staticness of the HTable.
174 -- type Key is limited private;
175 -- with function Get_Key (E : Elmt_Ptr) return Key;
176 -- with function Hash (F : Key) return Header_Num;
177 -- with function Equal (F1, F2 : Key) return Boolean;
179 -- package Static_HTable is
182 -- -- Resets the hash table by setting all its elements to Null_Ptr.
183 -- -- The effect is to clear the hash table so that it can be reused.
184 -- -- For the most common case where Elmt_Ptr is an access type, and
185 -- -- Null_Ptr is null, this is only needed if the same table is
186 -- -- reused in a new context. If Elmt_Ptr is other than an access
187 -- -- type, or Null_Ptr is other than null, then Reset must be called
188 -- -- before the first use of the hash table.
190 -- procedure Set (E : Elmt_Ptr);
191 -- -- Insert the element pointer in the HTable
193 -- function Get (K : Key) return Elmt_Ptr;
194 -- -- Returns the latest inserted element pointer with the given Key
195 -- -- or null if none.
197 -- procedure Remove (K : Key);
198 -- -- Removes the latest inserted element pointer associated with the
199 -- -- given key if any, does nothing if none.
201 -- function Get_First return Elmt_Ptr;
202 -- -- Returns Null_Ptr if the HTable is empty, otherwise returns one
203 -- -- non specified element. There is no guarantee that two calls to
204 -- -- this function will return the same element.
206 -- function Get_Next return Elmt_Ptr;
207 -- -- Returns a non-specified element that has not been returned by
208 -- -- the same function since the last call to Get_First or Null_Ptr
209 -- -- if there is no such element or Get_First has never been called.
210 -- -- If there is no call to 'Set' in between Get_Next calls, all
211 -- -- the elements of the HTable will be traversed.
213 -- end Static_HTable;
219 -- A generic hashing function working on String keys
221 generic function Hash renames System.HTable.Hash;
224 -- type Header_Num is range <>;
225 -- function Hash (Key : String) return Header_Num;