GCC v8.2
[gcc.git] / gcc / ada / libgnat / g-dynhta.ads
1 ------------------------------------------------------------------------------
2 --                                                                          --
3 --                         GNAT RUN-TIME COMPONENTS                         --
4 --                                                                          --
5 --                 G N A T . D Y N A M I C _ H T A B L E S                  --
6 --                                                                          --
7 --                                 S p e c                                  --
8 --                                                                          --
9 --                     Copyright (C) 1995-2018, AdaCore                     --
10 --                                                                          --
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.                                     --
17 --                                                                          --
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.               --
21 --                                                                          --
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/>.                                          --
26 --                                                                          --
27 -- GNAT was originally developed  by the GNAT team at  New York University. --
28 -- Extensive contributions were provided by Ada Core Technologies Inc.      --
29 --                                                                          --
30 ------------------------------------------------------------------------------
31
32 --  Hash table searching routines
33
34 --  This package contains three separate packages. The Simple_HTable package
35 --  provides a very simple abstraction that associates one element to one key
36 --  value and takes care of all allocations automatically using the heap. The
37 --  Static_HTable package provides a more complex interface that allows full
38 --  control over allocation. The Load_Factor_HTable package provides a more
39 --  complex abstraction where collisions are resolved by chaining, and the
40 --  table grows by a percentage after the load factor has been exceeded.
41
42 --  This package provides a facility similar to that of GNAT.HTable, except
43 --  that this package declares types that can be used to define dynamic
44 --  instances of hash tables, while instantiations in GNAT.HTable creates a
45 --  single instance of the hash table.
46
47 --  Note that this interface should remain synchronized with those in
48 --  GNAT.HTable to keep as much coherency as possible between these two
49 --  related units.
50
51 package GNAT.Dynamic_HTables is
52
53    -------------------
54    -- Static_HTable --
55    -------------------
56
57    --  A low-level Hash-Table abstraction, not as easy to instantiate as
58    --  Simple_HTable. This mirrors the interface of GNAT.HTable.Static_HTable,
59    --  but does require dynamic allocation (since we allow multiple instances
60    --  of the table). The model is that each Element contains its own Key that
61    --  can be retrieved by Get_Key. Furthermore, Element provides a link that
62    --  can be used by the HTable for linking elements with same hash codes:
63
64    --       Element
65
66    --         +-------------------+
67    --         |       Key         |
68    --         +-------------------+
69    --         :    other data     :
70    --         +-------------------+
71    --         |     Next Elmt     |
72    --         +-------------------+
73
74    generic
75       type Header_Num is range <>;
76       --  An integer type indicating the number and range of hash headers
77
78       type Element (<>) is limited private;
79       --  The type of element to be stored
80
81       type Elmt_Ptr is private;
82       --  The type used to reference an element (will usually be an access
83       --  type, but could be some other form of type such as an integer type).
84
85       Null_Ptr : Elmt_Ptr;
86       --  The null value of the Elmt_Ptr type
87
88       with procedure Set_Next (E : Elmt_Ptr; Next : Elmt_Ptr);
89       with function  Next     (E : Elmt_Ptr) return Elmt_Ptr;
90       --  The type must provide an internal link for the sake of the
91       --  staticness of the HTable.
92
93       type Key is limited private;
94       with function Get_Key (E : Elmt_Ptr) return Key;
95       with function Hash    (F : Key)      return Header_Num;
96       with function Equal   (F1, F2 : Key) return Boolean;
97
98    package Static_HTable is
99
100       type Instance is private;
101       Nil : constant Instance;
102
103       procedure Reset (T : in out Instance);
104       --  Resets the hash table by releasing all memory associated with
105       --  it. The hash table can safely be reused after this call. For the
106       --  most common case where Elmt_Ptr is an access type, and Null_Ptr is
107       --  null, this is only needed if the same table is reused in a new
108       --  context. If Elmt_Ptr is other than an access type, or Null_Ptr is
109       --  other than null, then Reset must be called before the first use of
110       --  the hash table.
111
112       procedure Set (T : in out Instance; E : Elmt_Ptr);
113       --  Insert the element pointer in the HTable
114
115       function Get (T : Instance; K : Key) return Elmt_Ptr;
116       --  Returns the latest inserted element pointer with the given Key
117       --  or null if none.
118
119       procedure Remove (T : Instance; K : Key);
120       --  Removes the latest inserted element pointer associated with the
121       --  given key if any, does nothing if none.
122
123       function Get_First (T : Instance) return Elmt_Ptr;
124       --  Returns Null_Ptr if the Htable is empty, otherwise returns one
125       --  unspecified element. There is no guarantee that 2 calls to this
126       --  function will return the same element.
127
128       function Get_Next (T : Instance) return Elmt_Ptr;
129       --  Returns an unspecified element that has not been returned by the
130       --  same function since the last call to Get_First or Null_Ptr if
131       --  there is no such element or Get_First has never been called. If
132       --  there is no call to 'Set' in between Get_Next calls, all the
133       --  elements of the Htable will be traversed.
134
135    private
136       type Table_Type is array (Header_Num) of Elmt_Ptr;
137
138       type Instance_Data is record
139          Table            : Table_Type;
140          Iterator_Index   : Header_Num;
141          Iterator_Ptr     : Elmt_Ptr;
142          Iterator_Started : Boolean := False;
143       end record;
144
145       type Instance is access all Instance_Data;
146
147       Nil : constant Instance := null;
148    end Static_HTable;
149
150    -------------------
151    -- Simple_HTable --
152    -------------------
153
154    --  A simple hash table abstraction, easy to instantiate, easy to use.
155    --  The table associates one element to one key with the procedure Set.
156    --  Get retrieves the Element stored for a given Key. The efficiency of
157    --  retrieval is function of the size of the Table parameterized by
158    --  Header_Num and the hashing function Hash.
159
160    generic
161       type Header_Num is range <>;
162       --  An integer type indicating the number and range of hash headers
163
164       type Element is private;
165       --  The type of element to be stored
166
167       No_Element : Element;
168       --  The object that is returned by Get when no element has been set for
169       --  a given key
170
171       type Key is private;
172       with function Hash  (F : Key)      return Header_Num;
173       with function Equal (F1, F2 : Key) return Boolean;
174
175    package Simple_HTable is
176
177       type Instance is private;
178       Nil : constant Instance;
179
180       type Key_Option (Present : Boolean := False) is record
181          case Present is
182             when True  => K : Key;
183             when False => null;
184          end case;
185       end record;
186
187       procedure Set (T : in out Instance; K : Key; E : Element);
188       --  Associates an element with a given key. Overrides any previously
189       --  associated element.
190
191       procedure Reset (T : in out Instance);
192       --  Releases all memory associated with the table. The table can be
193       --  reused after this call (it is automatically allocated on the first
194       --  access to the table).
195
196       function Get (T : Instance; K : Key) return Element;
197       --  Returns the Element associated with a key or No_Element if the given
198       --  key has not associated element
199
200       procedure Remove (T : Instance; K : Key);
201       --  Removes the latest inserted element pointer associated with the given
202       --  key if any, does nothing if none.
203
204       function Get_First (T : Instance) return Element;
205       --  Returns No_Element if the Htable is empty, otherwise returns one
206       --  unspecified element. There is no guarantee that two calls to this
207       --  function will return the same element, if the Htable has been
208       --  modified between the two calls.
209
210       function Get_First_Key (T : Instance) return Key_Option;
211       --  Returns an option type giving an unspecified key. If the Htable
212       --  is empty, the discriminant will have field Present set to False,
213       --  otherwise its Present field is set to True and the field K contains
214       --  the key. There is no guarantee that two calls to this function will
215       --  return the same key, if the Htable has been modified between the two
216       --  calls.
217
218       function Get_Next (T : Instance) return Element;
219       --  Returns an unspecified element that has not been returned by the
220       --  same function since the last call to Get_First or No_Element if
221       --  there is no such element. If there is no call to 'Set' in between
222       --  Get_Next calls, all the elements of the Htable will be traversed.
223       --  To guarantee that all the elements of the Htable will be traversed,
224       --  no modification of the Htable (Set, Reset, Remove) should occur
225       --  between a call to Get_First and subsequent consecutive calls to
226       --  Get_Next, until one of these calls returns No_Element.
227
228       function Get_Next_Key (T : Instance) return Key_Option;
229       --  Same as Get_Next except that this returns an option type having field
230       --  Present set either to False if there no key never returned before by
231       --  either Get_First_Key or this very same function, or to True if there
232       --  is one, with the field K containing the key specified as before. The
233       --  same restrictions apply as Get_Next.
234
235    private
236
237       type Element_Wrapper;
238       type Elmt_Ptr is access all Element_Wrapper;
239       type Element_Wrapper is record
240          K    : Key;
241          E    : Element;
242          Next : Elmt_Ptr;
243       end record;
244
245       procedure Set_Next (E : Elmt_Ptr; Next : Elmt_Ptr);
246       function  Next     (E : Elmt_Ptr) return Elmt_Ptr;
247       function  Get_Key  (E : Elmt_Ptr) return Key;
248
249       package Tab is new Static_HTable
250         (Header_Num => Header_Num,
251          Element    => Element_Wrapper,
252          Elmt_Ptr   => Elmt_Ptr,
253          Null_Ptr   => null,
254          Set_Next   => Set_Next,
255          Next       => Next,
256          Key        => Key,
257          Get_Key    => Get_Key,
258          Hash       => Hash,
259          Equal      => Equal);
260
261       type Instance is new Tab.Instance;
262       Nil : constant Instance := Instance (Tab.Nil);
263
264    end Simple_HTable;
265
266 end GNAT.Dynamic_HTables;