File : table.ads
1 ------------------------------------------------------------------------------
2 -- --
3 -- GNAT COMPILER COMPONENTS --
4 -- --
5 -- T A B L E --
6 -- --
7 -- S p e c --
8 -- --
9 -- Copyright (C) 1992-2015, Free Software Foundation, Inc. --
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 -- --
19 -- --
20 -- --
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 -- This package provides an implementation of dynamically resizable one
33 -- dimensional arrays. The idea is to mimic the normal Ada semantics for
34 -- arrays as closely as possible with the one additional capability of
35 -- dynamically modifying the value of the Last attribute.
36
37 -- Note that this interface should remain synchronized with those in
38 -- GNAT.Table and GNAT.Dynamic_Tables to keep coherency between these
39 -- three related units.
40
41 with Types; use Types;
42
43 package Table is
44 pragma Elaborate_Body;
45
46 generic
47 type Table_Component_Type is private;
48 type Table_Index_Type is range <>;
49
50 Table_Low_Bound : Table_Index_Type;
51 Table_Initial : Pos;
52 Table_Increment : Nat;
53 Table_Name : String;
54
55 package Table is
56
57 -- Table_Component_Type and Table_Index_Type specify the type of the
58 -- array, Table_Low_Bound is the lower bound. Table_Index_Type must be
59 -- an integer type. The effect is roughly to declare:
60
61 -- Table : array (Table_Index_Type range Table_Low_Bound .. <>)
62 -- of Table_Component_Type;
63
64 -- Note: since the upper bound can be one less than the lower
65 -- bound for an empty array, the table index type must be able
66 -- to cover this range, e.g. if the lower bound is 1, then the
67 -- Table_Index_Type should be Natural rather than Positive.
68
69 -- Table_Component_Type may be any Ada type, except that controlled
70 -- types are not supported. Note however that default initialization
71 -- will NOT occur for array components.
72
73 -- The Table_Initial values controls the allocation of the table when
74 -- it is first allocated, either by default, or by an explicit Init
75 -- call. The value used is Opt.Table_Factor * Table_Initial.
76
77 -- The Table_Increment value controls the amount of increase, if the
78 -- table has to be increased in size. The value given is a percentage
79 -- value (e.g. 100 = increase table size by 100%, i.e. double it).
80
81 -- The Table_Name parameter is simply use in debug output messages it
82 -- has no other usage, and is not referenced in non-debugging mode.
83
84 -- The Last and Set_Last subprograms provide control over the current
85 -- logical allocation. They are quite efficient, so they can be used
86 -- freely (expensive reallocation occurs only at major granularity
87 -- chunks controlled by the allocation parameters).
88
89 -- Note: We do not make the table components aliased, since this would
90 -- restrict the use of table for discriminated types. If it is necessary
91 -- to take the access of a table element, use Unrestricted_Access.
92
93 -- WARNING: On HPPA, the virtual addressing approach used in this unit
94 -- is incompatible with the indexing instructions on the HPPA. So when
95 -- using this unit, compile your application with -mdisable-indexing.
96
97 -- WARNING: If the table is reallocated, then the address of all its
98 -- components will change. So do not capture the address of an element
99 -- and then use the address later after the table may be reallocated.
100 -- One tricky case of this is passing an element of the table to a
101 -- subprogram by reference where the table gets reallocated during
102 -- the execution of the subprogram. The best rule to follow is never
103 -- to pass a table element as a parameter except for the case of IN
104 -- mode parameters with scalar values.
105
106 type Table_Type is
107 array (Table_Index_Type range <>) of Table_Component_Type;
108
109 subtype Big_Table_Type is
110 Table_Type (Table_Low_Bound .. Table_Index_Type'Last);
111 -- We work with pointers to a bogus array type that is constrained
112 -- with the maximum possible range bound. This means that the pointer
113 -- is a thin pointer, which is more efficient. Since subscript checks
114 -- in any case must be on the logical, rather than physical bounds,
115 -- safety is not compromised by this approach.
116
117 type Table_Ptr is access all Big_Table_Type;
118 for Table_Ptr'Storage_Size use 0;
119 -- The table is actually represented as a pointer to allow reallocation
120
121 Table : aliased Table_Ptr := null;
122 -- The table itself. The lower bound is the value of Low_Bound.
123 -- Logically the upper bound is the current value of Last (although
124 -- the actual size of the allocated table may be larger than this).
125 -- The program may only access and modify Table entries in the range
126 -- First .. Last.
127
128 Locked : Boolean := False;
129 -- Table expansion is permitted only if this switch is set to False. A
130 -- client may set Locked to True, in which case any attempt to expand
131 -- the table will cause an assertion failure. Note that while a table
132 -- is locked, its address in memory remains fixed and unchanging. This
133 -- feature is used to control table expansion during Gigi processing.
134 -- Gigi assumes that tables other than the Uint and Ureal tables do
135 -- not move during processing, which means that they cannot be expanded.
136 -- The Locked flag is used to enforce this restriction.
137
138 procedure Init;
139 -- This procedure allocates a new table of size Initial (freeing any
140 -- previously allocated larger table). It is not necessary to call
141 -- Init when a table is first instantiated (since the instantiation does
142 -- the same initialization steps). However, it is harmless to do so, and
143 -- Init is convenient in reestablishing a table for new use.
144
145 function Last return Table_Index_Type;
146 pragma Inline (Last);
147 -- Returns the current value of the last used entry in the table, which
148 -- can then be used as a subscript for Table. Note that the only way to
149 -- modify Last is to call the Set_Last procedure. Last must always be
150 -- used to determine the logically last entry.
151
152 procedure Release;
153 -- Storage is allocated in chunks according to the values given in the
154 -- Initial and Increment parameters. A call to Release releases all
155 -- storage that is allocated, but is not logically part of the current
156 -- array value. Current array values are not affected by this call.
157
158 procedure Free;
159 -- Free all allocated memory for the table. A call to init is required
160 -- before any use of this table after calling Free.
161
162 First : constant Table_Index_Type := Table_Low_Bound;
163 -- Export First as synonym for Low_Bound (parallel with use of Last)
164
165 procedure Set_Last (New_Val : Table_Index_Type);
166 pragma Inline (Set_Last);
167 -- This procedure sets Last to the indicated value. If necessary the
168 -- table is reallocated to accommodate the new value (i.e. on return
169 -- the allocated table has an upper bound of at least Last). If Set_Last
170 -- reduces the size of the table, then logically entries are removed
171 -- from the table. If Set_Last increases the size of the table, then
172 -- new entries are logically added to the table.
173
174 procedure Increment_Last;
175 pragma Inline (Increment_Last);
176 -- Adds 1 to Last (same as Set_Last (Last + 1)
177
178 procedure Decrement_Last;
179 pragma Inline (Decrement_Last);
180 -- Subtracts 1 from Last (same as Set_Last (Last - 1)
181
182 procedure Append (New_Val : Table_Component_Type);
183 pragma Inline (Append);
184 -- Equivalent to:
185 -- x.Increment_Last;
186 -- x.Table (x.Last) := New_Val;
187 -- i.e. the table size is increased by one, and the given new item
188 -- stored in the newly created table element.
189
190 procedure Append_All (New_Vals : Table_Type);
191 -- Appends all components of New_Vals
192
193 procedure Set_Item
194 (Index : Table_Index_Type;
195 Item : Table_Component_Type);
196 pragma Inline (Set_Item);
197 -- Put Item in the table at position Index. The table is expanded if
198 -- current table length is less than Index and in that case Last is set
199 -- to Index. Item will replace any value already present in the table
200 -- at this position.
201
202 type Saved_Table is private;
203 -- Type used for Save/Restore subprograms
204
205 function Save return Saved_Table;
206 -- Resets table to empty, but saves old contents of table in returned
207 -- value, for possible later restoration by a call to Restore.
208
209 procedure Restore (T : Saved_Table);
210 -- Given a Saved_Table value returned by a prior call to Save, restores
211 -- the table to the state it was in at the time of the Save call.
212
213 procedure Tree_Write;
214 -- Writes out contents of table using Tree_IO
215
216 procedure Tree_Read;
217 -- Initializes table by reading contents previously written
218 -- with the Tree_Write call (also using Tree_IO)
219
220 private
221
222 Last_Val : Int;
223 -- Current value of Last. Note that we declare this in the private part
224 -- because we don't want the client to modify Last except through one of
225 -- the official interfaces (since a modification to Last may require a
226 -- reallocation of the table).
227
228 Max : Int;
229 -- Subscript of the maximum entry in the currently allocated table
230
231 type Saved_Table is record
232 Last_Val : Int;
233 Max : Int;
234 Table : Table_Ptr;
235 end record;
236
237 end Table;
238 end Table;