Mercurial > hg > CbC > CbC_gcc
comparison gcc/ada/libgnat/a-cuprqu.ads @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
1 ------------------------------------------------------------------------------ | |
2 -- -- | |
3 -- GNAT LIBRARY COMPONENTS -- | |
4 -- -- | |
5 -- ADA.CONTAINERS.UNBOUNDED_PRIORITY_QUEUES -- | |
6 -- -- | |
7 -- S p e c -- | |
8 -- -- | |
9 -- Copyright (C) 2011-2017, 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 System; | |
35 with Ada.Containers.Ordered_Sets; | |
36 with Ada.Containers.Synchronized_Queue_Interfaces; | |
37 | |
38 generic | |
39 with package Queue_Interfaces is | |
40 new Ada.Containers.Synchronized_Queue_Interfaces (<>); | |
41 | |
42 type Queue_Priority is private; | |
43 | |
44 with function Get_Priority | |
45 (Element : Queue_Interfaces.Element_Type) return Queue_Priority is <>; | |
46 | |
47 with function Before | |
48 (Left, Right : Queue_Priority) return Boolean is <>; | |
49 | |
50 Default_Ceiling : System.Any_Priority := System.Priority'Last; | |
51 | |
52 package Ada.Containers.Unbounded_Priority_Queues is | |
53 pragma Annotate (CodePeer, Skip_Analysis); | |
54 pragma Preelaborate; | |
55 | |
56 package Implementation is | |
57 | |
58 -- All identifiers in this unit are implementation defined | |
59 | |
60 pragma Implementation_Defined; | |
61 | |
62 -- We use an ordered set to hold the queue elements. This gives O(lg N) | |
63 -- performance in the worst case for Enqueue and Dequeue. | |
64 -- Sequence_Number is used to distinguish equivalent items. Each Enqueue | |
65 -- uses a higher Sequence_Number, so that a new item is placed after | |
66 -- already-enqueued equivalent items. | |
67 -- | |
68 -- At any time, the first set element is the one to be dequeued next (if | |
69 -- the queue is not empty). | |
70 | |
71 type Set_Elem is record | |
72 Sequence_Number : Count_Type; | |
73 Item : Queue_Interfaces.Element_Type; | |
74 end record; | |
75 | |
76 function "=" (X, Y : Queue_Interfaces.Element_Type) return Boolean is | |
77 (not Before (Get_Priority (X), Get_Priority (Y)) | |
78 and then not Before (Get_Priority (Y), Get_Priority (X))); | |
79 -- Elements are equal if neither is Before the other | |
80 | |
81 function "=" (X, Y : Set_Elem) return Boolean is | |
82 (X.Sequence_Number = Y.Sequence_Number and then X.Item = Y.Item); | |
83 -- Set_Elems are equal if the elements are equal, and the | |
84 -- Sequence_Numbers are equal. This is passed to Ordered_Sets. | |
85 | |
86 function "<" (X, Y : Set_Elem) return Boolean is | |
87 (if X.Item = Y.Item | |
88 then X.Sequence_Number < Y.Sequence_Number | |
89 else Before (Get_Priority (X.Item), Get_Priority (Y.Item))); | |
90 -- If the items are equal, Sequence_Number breaks the tie. Otherwise, | |
91 -- use Before. This is passed to Ordered_Sets. | |
92 | |
93 pragma Suppress (Container_Checks); | |
94 package Sets is new Ada.Containers.Ordered_Sets (Set_Elem); | |
95 | |
96 end Implementation; | |
97 | |
98 use Implementation, Implementation.Sets; | |
99 | |
100 protected type Queue (Ceiling : System.Any_Priority := Default_Ceiling) | |
101 with | |
102 Priority => Ceiling | |
103 is new Queue_Interfaces.Queue with | |
104 | |
105 overriding entry Enqueue (New_Item : Queue_Interfaces.Element_Type); | |
106 | |
107 overriding entry Dequeue (Element : out Queue_Interfaces.Element_Type); | |
108 | |
109 -- The priority queue operation Dequeue_Only_High_Priority had been a | |
110 -- protected entry in early drafts of AI05-0159, but it was discovered | |
111 -- that that operation as specified was not in fact implementable. The | |
112 -- operation was changed from an entry to a protected procedure per the | |
113 -- ARG meeting in Edinburgh (June 2011), with a different signature and | |
114 -- semantics. | |
115 | |
116 procedure Dequeue_Only_High_Priority | |
117 (At_Least : Queue_Priority; | |
118 Element : in out Queue_Interfaces.Element_Type; | |
119 Success : out Boolean); | |
120 | |
121 overriding function Current_Use return Count_Type; | |
122 | |
123 overriding function Peak_Use return Count_Type; | |
124 | |
125 private | |
126 Q_Elems : Set; | |
127 -- Elements of the queue | |
128 | |
129 Max_Length : Count_Type := 0; | |
130 -- The current length of the queue is the Length of Q_Elems. This is the | |
131 -- maximum value of that, so far. Updated by Enqueue. | |
132 | |
133 Next_Sequence_Number : Count_Type := 0; | |
134 -- Steadily increasing counter | |
135 end Queue; | |
136 | |
137 end Ada.Containers.Unbounded_Priority_Queues; |