Daily bump.
[official-gcc.git] / gcc / ada / s-htable.ads
blobd5116c69f3b38c963f7667bd704fa66026b6b4a2
1 ------------------------------------------------------------------------------
2 -- --
3 -- GNAT RUN-TIME COMPONENTS --
4 -- --
5 -- S Y S T E M . H T A B L E --
6 -- --
7 -- S p e c --
8 -- --
9 -- Copyright (C) 1995-2007, 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 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. --
21 -- --
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. --
28 -- --
29 -- GNAT was originally developed by the GNAT team at New York University. --
30 -- Extensive contributions were provided by Ada Core Technologies Inc. --
31 -- --
32 ------------------------------------------------------------------------------
34 -- Hash table searching routines
36 -- This package contains two separate packages. The Simple_HTable package
37 -- provides a very simple abstraction that associates one element to one
38 -- key value and takes care of all allocations automatically using the heap.
39 -- The Static_HTable package provides a more complex interface that allows
40 -- complete control over allocation.
42 pragma Warnings (Off);
43 pragma Compiler_Unit;
44 pragma Warnings (On);
46 package System.HTable is
47 pragma Preelaborate;
49 -------------------
50 -- Simple_HTable --
51 -------------------
53 -- A simple hash table abstraction, easy to instantiate, easy to use.
54 -- The table associates one element to one key with the procedure Set.
55 -- Get retrieves the Element stored for a given Key. The efficiency of
56 -- retrieval is function of the size of the Table parameterized by
57 -- Header_Num and the hashing function Hash.
59 generic
60 type Header_Num is range <>;
61 -- An integer type indicating the number and range of hash headers
63 type Element is private;
64 -- The type of element to be stored
66 No_Element : Element;
67 -- The object that is returned by Get when no element has been set for
68 -- a given key
70 type Key is private;
71 with function Hash (F : Key) return Header_Num;
72 with function Equal (F1, F2 : Key) return Boolean;
74 package Simple_HTable is
76 procedure Set (K : Key; E : Element);
77 -- Associates an element with a given key. Overrides any previously
78 -- associated element.
80 procedure Reset;
81 -- Removes and frees all elements in the table
83 function Get (K : Key) return Element;
84 -- Returns the Element associated with a key or No_Element if the
85 -- given key has not associated element
87 procedure Remove (K : Key);
88 -- Removes the latest inserted element pointer associated with the
89 -- given key if any, does nothing if none.
91 function Get_First return Element;
92 -- Returns No_Element if the HTable is empty, otherwise returns one
93 -- non specified element. There is no guarantee that 2 calls to this
94 -- function will return the same element.
96 function Get_Next return Element;
97 -- Returns a non-specified element that has not been returned by the
98 -- same function since the last call to Get_First or No_Element if
99 -- there is no such element. If there is no call to 'Set' in between
100 -- Get_Next calls, all the elements of the HTable will be traversed.
101 end Simple_HTable;
103 -------------------
104 -- Static_HTable --
105 -------------------
107 -- A low-level Hash-Table abstraction, not as easy to instantiate as
108 -- Simple_HTable but designed to allow complete control over the
109 -- allocation of necessary data structures. Particularly useful when
110 -- dynamic allocation is not desired. The model is that each Element
111 -- contains its own Key that can be retrieved by Get_Key. Furthermore,
112 -- Element provides a link that can be used by the HTable for linking
113 -- elements with same hash codes:
115 -- Element
117 -- +-------------------+
118 -- | Key |
119 -- +-------------------+
120 -- : other data :
121 -- +-------------------+
122 -- | Next Elmt |
123 -- +-------------------+
125 generic
126 type Header_Num is range <>;
127 -- An integer type indicating the number and range of hash headers
129 type Element (<>) is limited private;
130 -- The type of element to be stored. This is historically part of the
131 -- interface, even though it is not used at all in the operations of
132 -- the package.
134 pragma Warnings (Off, Element);
135 -- We have to kill warnings here, because Element is and always
136 -- has been unreferenced, but we cannot remove it at this stage,
137 -- since this unit is in wide use, and it certainly seems harmless.
139 type Elmt_Ptr is private;
140 -- The type used to reference an element (will usually be an access
141 -- type, but could be some other form of type such as an integer type).
143 Null_Ptr : Elmt_Ptr;
144 -- The null value of the Elmt_Ptr type
146 with procedure Set_Next (E : Elmt_Ptr; Next : Elmt_Ptr);
147 with function Next (E : Elmt_Ptr) return Elmt_Ptr;
148 -- The type must provide an internal link for the sake of the
149 -- staticness of the HTable.
151 type Key is limited private;
152 with function Get_Key (E : Elmt_Ptr) return Key;
153 with function Hash (F : Key) return Header_Num;
154 with function Equal (F1, F2 : Key) return Boolean;
156 package Static_HTable is
158 procedure Reset;
159 -- Resets the hash table by setting all its elements to Null_Ptr. The
160 -- effect is to clear the hash table so that it can be reused. For the
161 -- most common case where Elmt_Ptr is an access type, and Null_Ptr is
162 -- null, this is only needed if the same table is reused in a new
163 -- context. If Elmt_Ptr is other than an access type, or Null_Ptr is
164 -- other than null, then Reset must be called before the first use
165 -- of the hash table.
167 procedure Set (E : Elmt_Ptr);
168 -- Insert the element pointer in the HTable
170 function Get (K : Key) return Elmt_Ptr;
171 -- Returns the latest inserted element pointer with the given Key
172 -- or null if none.
174 procedure Remove (K : Key);
175 -- Removes the latest inserted element pointer associated with the
176 -- given key if any, does nothing if none.
178 function Get_First return Elmt_Ptr;
179 -- Returns Null_Ptr if the HTable is empty, otherwise returns one
180 -- non specified element. There is no guarantee that 2 calls to this
181 -- function will return the same element.
183 function Get_Next return Elmt_Ptr;
184 -- Returns a non-specified element that has not been returned by the
185 -- same function since the last call to Get_First or Null_Ptr if
186 -- there is no such element or Get_First has bever been called. If
187 -- there is no call to 'Set' in between Get_Next calls, all the
188 -- elements of the HTable will be traversed.
190 end Static_HTable;
192 ----------
193 -- Hash --
194 ----------
196 -- A generic hashing function working on String keys
198 generic
199 type Header_Num is range <>;
200 function Hash (Key : String) return Header_Num;
202 end System.HTable;