OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [ada/] [a-cohama.ads] - Blame information for rev 706

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 706 jeremybenn
------------------------------------------------------------------------------
2
--                                                                          --
3
--                         GNAT LIBRARY COMPONENTS                          --
4
--                                                                          --
5
--            A D A . C O N T A I N E R S . H A S H E D _ M A P S           --
6
--                                                                          --
7
--                                 S p e c                                  --
8
--                                                                          --
9
--          Copyright (C) 2004-2012, Free Software Foundation, Inc.         --
10
--                                                                          --
11
-- This specification is derived from the Ada Reference Manual for use with --
12
-- GNAT. The copyright notice above, and the license provisions that follow --
13
-- apply solely to the  contents of the part following the private keyword. --
14
--                                                                          --
15
-- GNAT is free software;  you can  redistribute it  and/or modify it under --
16
-- terms of the  GNU General Public License as published  by the Free Soft- --
17
-- ware  Foundation;  either version 3,  or (at your option) any later ver- --
18
-- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
19
-- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
20
-- or FITNESS FOR A PARTICULAR PURPOSE.                                     --
21
--                                                                          --
22
-- As a special exception under Section 7 of GPL version 3, you are granted --
23
-- additional permissions described in the GCC Runtime Library Exception,   --
24
-- version 3.1, as published by the Free Software Foundation.               --
25
--                                                                          --
26
-- You should have received a copy of the GNU General Public License and    --
27
-- a copy of the GCC Runtime Library Exception along with this program;     --
28
-- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
29
-- <http://www.gnu.org/licenses/>.                                          --
30
--                                                                          --
31
-- This unit was originally developed by Matthew J Heaney.                  --
32
------------------------------------------------------------------------------
33
 
34
with Ada.Iterator_Interfaces;
35
 
36
private with Ada.Containers.Hash_Tables;
37
private with Ada.Finalization;
38
private with Ada.Streams;
39
 
40
generic
41
   type Key_Type is private;
42
   type Element_Type is private;
43
 
44
   with function Hash (Key : Key_Type) return Hash_Type;
45
   with function Equivalent_Keys (Left, Right : Key_Type) return Boolean;
46
   with function "=" (Left, Right : Element_Type) return Boolean is <>;
47
 
48
package Ada.Containers.Hashed_Maps is
49
   pragma Preelaborate;
50
   pragma Remote_Types;
51
 
52
   type Map is tagged private
53
   with
54
      Constant_Indexing => Constant_Reference,
55
      Variable_Indexing => Reference,
56
      Default_Iterator  => Iterate,
57
      Iterator_Element  => Element_Type;
58
 
59
   pragma Preelaborable_Initialization (Map);
60
 
61
   type Cursor is private;
62
   pragma Preelaborable_Initialization (Cursor);
63
 
64
   Empty_Map : constant Map;
65
   --  Map objects declared without an initialization expression are
66
   --  initialized to the value Empty_Map.
67
 
68
   No_Element : constant Cursor;
69
   --  Cursor objects declared without an initialization expression are
70
   --  initialized to the value No_Element.
71
 
72
   function Has_Element (Position : Cursor) return Boolean;
73
   --  Equivalent to Position /= No_Element
74
 
75
   package Map_Iterator_Interfaces is new
76
     Ada.Iterator_Interfaces (Cursor, Has_Element);
77
 
78
   function "=" (Left, Right : Map) return Boolean;
79
   --  For each key/element pair in Left, equality attempts to find the key in
80
   --  Right; if a search fails the equality returns False. The search works by
81
   --  calling Hash to find the bucket in the Right map that corresponds to the
82
   --  Left key. If bucket is non-empty, then equality calls Equivalent_Keys
83
   --  to compare the key (in Left) to the key of each node in the bucket (in
84
   --  Right); if the keys are equivalent, then the equality test for this
85
   --  key/element pair (in Left) completes by calling the element equality
86
   --  operator to compare the element (in Left) to the element of the node
87
   --  (in Right) whose key matched.
88
 
89
   function Capacity (Container : Map) return Count_Type;
90
   --  Returns the current capacity of the map. Capacity is the maximum length
91
   --  before which rehashing in guaranteed not to occur.
92
 
93
   procedure Reserve_Capacity (Container : in out Map; Capacity : Count_Type);
94
   --  Adjusts the current capacity, by allocating a new buckets array. If the
95
   --  requested capacity is less than the current capacity, then the capacity
96
   --  is contracted (to a value not less than the current length). If the
97
   --  requested capacity is greater than the current capacity, then the
98
   --  capacity is expanded (to a value not less than what is requested). In
99
   --  either case, the nodes are rehashed from the old buckets array onto the
100
   --  new buckets array (Hash is called once for each existing key in order to
101
   --  compute the new index), and then the old buckets array is deallocated.
102
 
103
   function Length (Container : Map) return Count_Type;
104
   --  Returns the number of items in the map
105
 
106
   function Is_Empty (Container : Map) return Boolean;
107
   --  Equivalent to Length (Container) = 0
108
 
109
   procedure Clear (Container : in out Map);
110
   --  Removes all of the items from the map
111
 
112
   function Key (Position : Cursor) return Key_Type;
113
   --  Returns the key of the node designated by the cursor
114
 
115
   function Element (Position : Cursor) return Element_Type;
116
   --  Returns the element of the node designated by the cursor
117
 
118
   procedure Replace_Element
119
     (Container : in out Map;
120
      Position  : Cursor;
121
      New_Item  : Element_Type);
122
   --  Assigns the value New_Item to the element designated by the cursor
123
 
124
   procedure Query_Element
125
     (Position : Cursor;
126
      Process  : not null access
127
                   procedure (Key : Key_Type; Element : Element_Type));
128
   --  Calls Process with the key and element (both having only a constant
129
   --  view) of the node designed by the cursor.
130
 
131
   procedure Update_Element
132
     (Container : in out Map;
133
      Position  : Cursor;
134
      Process   : not null access
135
                    procedure (Key : Key_Type; Element : in out Element_Type));
136
   --  Calls Process with the key (with only a constant view) and element (with
137
   --  a variable view) of the node designed by the cursor.
138
 
139
   type Constant_Reference_Type
140
      (Element : not null access constant Element_Type) is private
141
   with
142
      Implicit_Dereference => Element;
143
 
144
   type Reference_Type (Element : not null access Element_Type) is private
145
   with
146
      Implicit_Dereference => Element;
147
 
148
   function Constant_Reference
149
     (Container : aliased Map;
150
      Position  : Cursor) return Constant_Reference_Type;
151
   pragma Inline (Constant_Reference);
152
 
153
   function Reference
154
     (Container : aliased in out Map;
155
      Position  : Cursor) return Reference_Type;
156
   pragma Inline (Reference);
157
 
158
   function Constant_Reference
159
     (Container : aliased Map;
160
      Key       : Key_Type) return Constant_Reference_Type;
161
   pragma Inline (Constant_Reference);
162
 
163
   function Reference
164
     (Container : aliased in out Map;
165
      Key       : Key_Type) return Reference_Type;
166
   pragma Inline (Reference);
167
 
168
   procedure Assign (Target : in out Map; Source : Map);
169
 
170
   function Copy (Source : Map; Capacity : Count_Type := 0) return Map;
171
 
172
   procedure Move (Target : in out Map; Source : in out Map);
173
   --  Clears Target (if it's not empty), and then moves (not copies) the
174
   --  buckets array and nodes from Source to Target.
175
 
176
   procedure Insert
177
     (Container : in out Map;
178
      Key       : Key_Type;
179
      New_Item  : Element_Type;
180
      Position  : out Cursor;
181
      Inserted  : out Boolean);
182
   --  Conditionally inserts New_Item into the map. If Key is already in the
183
   --  map, then Inserted returns False and Position designates the node
184
   --  containing the existing key/element pair (neither of which is modified).
185
   --  If Key is not already in the map, the Inserted returns True and Position
186
   --  designates the newly-inserted node container Key and New_Item. The
187
   --  search for the key works as follows. Hash is called to determine Key's
188
   --  bucket; if the bucket is non-empty, then Equivalent_Keys is called to
189
   --  compare Key to each node in that bucket. If the bucket is empty, or
190
   --  there were no matching keys in the bucket, the search "fails" and the
191
   --  key/item pair is inserted in the map (and Inserted returns True);
192
   --  otherwise, the search "succeeds" (and Inserted returns False).
193
 
194
   procedure Insert
195
     (Container : in out Map;
196
      Key       : Key_Type;
197
      Position  : out Cursor;
198
      Inserted  : out Boolean);
199
   --  The same as the (conditional) Insert that accepts an element parameter,
200
   --  with the difference that if Inserted returns True, then the element of
201
   --  the newly-inserted node is initialized to its default value.
202
 
203
   procedure Insert
204
     (Container : in out Map;
205
      Key       : Key_Type;
206
      New_Item  : Element_Type);
207
   --  Attempts to insert Key into the map, performing the usual search (which
208
   --  involves calling both Hash and Equivalent_Keys); if the search succeeds
209
   --  (because Key is already in the map), then it raises Constraint_Error.
210
   --  (This version of Insert is similar to Replace, but having the opposite
211
   --  exception behavior. It is intended for use when you want to assert that
212
   --  Key is not already in the map.)
213
 
214
   procedure Include
215
     (Container : in out Map;
216
      Key       : Key_Type;
217
      New_Item  : Element_Type);
218
   --  Attempts to insert Key into the map. If Key is already in the map, then
219
   --  both the existing key and element are assigned the values of Key and
220
   --  New_Item, respectively. (This version of Insert only raises an exception
221
   --  if cursor tampering occurs. It is intended for use when you want to
222
   --  insert the key/element pair in the map, and you don't care whether Key
223
   --  is already present.)
224
 
225
   procedure Replace
226
     (Container : in out Map;
227
      Key       : Key_Type;
228
      New_Item  : Element_Type);
229
   --  Searches for Key in the map; if the search fails (because Key was not in
230
   --  the map), then it raises Constraint_Error. Otherwise, both the existing
231
   --  key and element are assigned the values of Key and New_Item rsp. (This
232
   --  is similar to Insert, but with the opposite exception behavior. It is to
233
   --  be used when you want to assert that Key is already in the map.)
234
 
235
   procedure Exclude (Container : in out Map; Key : Key_Type);
236
   --  Searches for Key in the map, and if found, removes its node from the map
237
   --  and then deallocates it. The search works as follows. The operation
238
   --  calls Hash to determine the key's bucket; if the bucket is not empty, it
239
   --  calls Equivalent_Keys to compare Key to each key in the bucket. (This is
240
   --  the deletion analog of Include. It is intended for use when you want to
241
   --  remove the item from the map, but don't care whether the key is already
242
   --  in the map.)
243
 
244
   procedure Delete (Container : in out Map; Key : Key_Type);
245
   --  Searches for Key in the map (which involves calling both Hash and
246
   --  Equivalent_Keys). If the search fails, then the operation raises
247
   --  Constraint_Error. Otherwise it removes the node from the map and then
248
   --  deallocates it. (This is the deletion analog of non-conditional
249
   --  Insert. It is intended for use when you want to assert that the item is
250
   --  already in the map.)
251
 
252
   procedure Delete (Container : in out Map; Position : in out Cursor);
253
   --  Removes the node designated by Position from the map, and then
254
   --  deallocates the node. The operation calls Hash to determine the bucket,
255
   --  and then compares Position to each node in the bucket until there's a
256
   --  match (it does not call Equivalent_Keys).
257
 
258
   function First (Container : Map) return Cursor;
259
   --  Returns a cursor that designates the first non-empty bucket, by
260
   --  searching from the beginning of the buckets array.
261
 
262
   function Next (Position : Cursor) return Cursor;
263
   --  Returns a cursor that designates the node that follows the current one
264
   --  designated by Position. If Position designates the last node in its
265
   --  bucket, the operation calls Hash to compute the index of this bucket,
266
   --  and searches the buckets array for the first non-empty bucket, starting
267
   --  from that index; otherwise, it simply follows the link to the next node
268
   --  in the same bucket.
269
 
270
   procedure Next (Position : in out Cursor);
271
   --  Equivalent to Position := Next (Position)
272
 
273
   function Find (Container : Map; Key : Key_Type) return Cursor;
274
   --  Searches for Key in the map. Find calls Hash to determine the key's
275
   --  bucket; if the bucket is not empty, it calls Equivalent_Keys to compare
276
   --  Key to each key in the bucket. If the search succeeds, Find returns a
277
   --  cursor designating the matching node; otherwise, it returns No_Element.
278
 
279
   function Contains (Container : Map; Key : Key_Type) return Boolean;
280
   --  Equivalent to Find (Container, Key) /= No_Element
281
 
282
   function Element (Container : Map; Key : Key_Type) return Element_Type;
283
   --  Equivalent to Element (Find (Container, Key))
284
 
285
   function Equivalent_Keys (Left, Right : Cursor) return Boolean;
286
   --  Returns the result of calling Equivalent_Keys with the keys of the nodes
287
   --  designated by cursors Left and Right.
288
 
289
   function Equivalent_Keys (Left : Cursor; Right : Key_Type) return Boolean;
290
   --  Returns the result of calling Equivalent_Keys with key of the node
291
   --  designated by Left and key Right.
292
 
293
   function Equivalent_Keys (Left : Key_Type; Right : Cursor) return Boolean;
294
   --  Returns the result of calling Equivalent_Keys with key Left and the node
295
   --  designated by Right.
296
 
297
   procedure Iterate
298
     (Container : Map;
299
      Process   : not null access procedure (Position : Cursor));
300
   --  Calls Process for each node in the map
301
 
302
   function Iterate
303
     (Container : Map) return Map_Iterator_Interfaces.Forward_Iterator'class;
304
 
305
private
306
   pragma Inline ("=");
307
   pragma Inline (Length);
308
   pragma Inline (Is_Empty);
309
   pragma Inline (Clear);
310
   pragma Inline (Key);
311
   pragma Inline (Element);
312
   pragma Inline (Move);
313
   pragma Inline (Contains);
314
   pragma Inline (Capacity);
315
   pragma Inline (Reserve_Capacity);
316
   pragma Inline (Has_Element);
317
   pragma Inline (Equivalent_Keys);
318
   pragma Inline (Next);
319
 
320
   type Node_Type;
321
   type Node_Access is access Node_Type;
322
 
323
   type Node_Type is limited record
324
      Key     : Key_Type;
325
      Element : aliased Element_Type;
326
      Next    : Node_Access;
327
   end record;
328
 
329
   package HT_Types is
330
     new Hash_Tables.Generic_Hash_Table_Types (Node_Type, Node_Access);
331
 
332
   type Map is new Ada.Finalization.Controlled with record
333
      HT : HT_Types.Hash_Table_Type;
334
   end record;
335
 
336
   overriding procedure Adjust (Container : in out Map);
337
 
338
   overriding procedure Finalize (Container : in out Map);
339
 
340
   use HT_Types;
341
   use Ada.Finalization;
342
   use Ada.Streams;
343
 
344
   procedure Write
345
     (Stream    : not null access Root_Stream_Type'Class;
346
      Container : Map);
347
 
348
   for Map'Write use Write;
349
 
350
   procedure Read
351
     (Stream    : not null access Root_Stream_Type'Class;
352
      Container : out Map);
353
 
354
   for Map'Read use Read;
355
 
356
   type Map_Access is access all Map;
357
   for Map_Access'Storage_Size use 0;
358
 
359
   type Cursor is record
360
      Container : Map_Access;
361
      Node      : Node_Access;
362
   end record;
363
 
364
   procedure Read
365
     (Stream : not null access Root_Stream_Type'Class;
366
      Item   : out Cursor);
367
 
368
   for Cursor'Read use Read;
369
 
370
   procedure Write
371
     (Stream : not null access Root_Stream_Type'Class;
372
      Item   : Cursor);
373
 
374
   for Cursor'Write use Write;
375
 
376
   type Reference_Control_Type is
377
      new Controlled with record
378
         Container : Map_Access;
379
      end record;
380
 
381
   overriding procedure Adjust (Control : in out Reference_Control_Type);
382
   pragma Inline (Adjust);
383
 
384
   overriding procedure Finalize (Control : in out Reference_Control_Type);
385
   pragma Inline (Finalize);
386
 
387
   type Constant_Reference_Type
388
      (Element : not null access constant Element_Type) is
389
      record
390
         Control : Reference_Control_Type;
391
      end record;
392
 
393
   procedure Write
394
     (Stream : not null access Root_Stream_Type'Class;
395
      Item   : Constant_Reference_Type);
396
 
397
   for Constant_Reference_Type'Write use Write;
398
 
399
   procedure Read
400
     (Stream : not null access Root_Stream_Type'Class;
401
      Item   : out Constant_Reference_Type);
402
 
403
   for Constant_Reference_Type'Read use Read;
404
 
405
   type Reference_Type
406
      (Element : not null access Element_Type) is
407
      record
408
         Control : Reference_Control_Type;
409
      end record;
410
 
411
   procedure Write
412
     (Stream : not null access Root_Stream_Type'Class;
413
      Item   : Reference_Type);
414
 
415
   for Reference_Type'Write use Write;
416
 
417
   procedure Read
418
     (Stream : not null access Root_Stream_Type'Class;
419
      Item   : out Reference_Type);
420
 
421
   for Reference_Type'Read use Read;
422
 
423
   Empty_Map : constant Map := (Controlled with HT => (null, 0, 0, 0));
424
 
425
   No_Element : constant Cursor := (Container => null, Node => null);
426
 
427
end Ada.Containers.Hashed_Maps;

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.