Commit | Line | Data |
---|---|---|
920dae64 AT |
1 | // ========== Copyright Header Begin ========================================== |
2 | // | |
3 | // OpenSPARC T2 Processor File: prioque.cc | |
4 | // Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved. | |
5 | // DO NOT ALTER OR REMOVE COPYRIGHT NOTICES. | |
6 | // | |
7 | // The above named program is free software; you can redistribute it and/or | |
8 | // modify it under the terms of the GNU General Public | |
9 | // License version 2 as published by the Free Software Foundation. | |
10 | // | |
11 | // The above named program is distributed in the hope that it will be | |
12 | // useful, but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | // General Public License for more details. | |
15 | // | |
16 | // You should have received a copy of the GNU General Public | |
17 | // License along with this work; if not, write to the Free Software | |
18 | // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. | |
19 | // | |
20 | // ========== Copyright Header End ============================================ | |
21 | /* | |
22 | * Copyright (C) 2004 Sun Microsystems, Inc. | |
23 | * All rights reserved. | |
24 | */ | |
25 | #pragma ident "@(#)1.2 04/08/13 prioque.cc" | |
26 | ||
27 | ||
28 | /* | |
29 | * | |
30 | */ | |
31 | ||
32 | ||
33 | extern long SYSTEM_get_time (int whence = 0); | |
34 | ||
35 | #include "prioque.h" | |
36 | ||
37 | ||
38 | /*static*/ int EventQue::debug = 0; | |
39 | /*static*/ volatile int EventQue::event_id = 1; | |
40 | ||
41 | ||
42 | #define PQ_PARENT(x) ((x)>>1) | |
43 | #define PQ_LEFT(x) ((x)<<1) | |
44 | #define PQ_RIGHT(x) (((x)<<1)+1) | |
45 | ||
46 | ||
47 | EventQue::EventQue () { | |
48 | _size = 0; | |
49 | _limit = 63; | |
50 | _heap = (Event_t*) malloc ((_limit+1) * sizeof (Event_t)); | |
51 | mutex_init (&_lock, 0, 0); // other options include recursive locks, ... | |
52 | } | |
53 | ||
54 | void | |
55 | EventQue::_grow () { | |
56 | _limit = 2 * _limit + 1; | |
57 | _heap = (Event_t*) realloc (_heap, (_limit+1) * sizeof (Event_t)); | |
58 | } | |
59 | ||
60 | EventQue::~EventQue () { | |
61 | free (_heap); | |
62 | _heap = NULL; | |
63 | _size = _limit = 0; | |
64 | mutex_destroy (&_lock); | |
65 | } | |
66 | ||
67 | ||
68 | static int ulog2 (uint32_t x) {int i; for (i=-1;x>0;i++) x>>=1; return i;} | |
69 | static void indent (int x) { for (int i = 0; i < x; i++) printf (" "); } | |
70 | ||
71 | void EventQue::internaldebug (int x) { | |
72 | if (x == 1) printf ("size=%d\n", _size); | |
73 | if (PQ_RIGHT(x) <= _size) | |
74 | internaldebug (PQ_RIGHT(x)); | |
75 | // identify violations of the heap-invariant (top down sorted property) | |
76 | if (x>1 && _heap[x].pq_priority < _heap[PQ_PARENT(x)].pq_priority) | |
77 | printf ("*"); | |
78 | indent (ulog2 (x)); printf ("%d: %lld\n", x, _heap[x].pq_priority); | |
79 | if (PQ_LEFT(x) <= _size) | |
80 | internaldebug (PQ_LEFT(x)); | |
81 | } | |
82 | ||
83 | ||
84 | void | |
85 | EventQue::_topdown_update (int index) // aka. MIN-HEAPIFY in "Intro to Algs", | |
86 | // but should have been called MIN-INCREASE-KEY for symmetry! | |
87 | { | |
88 | // Top down restoration of the heap invariant starting at index, | |
89 | // assuming that only the node at index has been modified and that | |
90 | // only that node potentially fails the invariant. It might have to | |
91 | // percolate downwards if its priority is too high (too far in the future). | |
92 | ||
93 | uint64_t min = _heap[index].pq_priority; | |
94 | int imin = index; | |
95 | ||
96 | tailrecurse: | |
97 | ||
98 | /* see if a child has lower priority (earlier time) than index's */ | |
99 | if (PQ_LEFT(index) <= _size && _heap[PQ_LEFT(index)].pq_priority < min) { | |
100 | min = _heap[PQ_LEFT(index)].pq_priority; | |
101 | imin = PQ_LEFT(index); | |
102 | } | |
103 | if (PQ_RIGHT(index) <= _size && _heap[PQ_RIGHT(index)].pq_priority < min) { | |
104 | min = _heap[PQ_RIGHT(index)].pq_priority; | |
105 | imin = PQ_RIGHT(index); | |
106 | } | |
107 | ||
108 | /* if so swap it up into index's place, then descend... */ | |
109 | if (imin != index) { | |
110 | Event_t temp = _heap[index]; // copy semantics, ugh... | |
111 | _heap[index] = _heap[imin]; // ugh... | |
112 | _heap[imin] = temp; // ugh... | |
113 | ||
114 | // fix parameters and loop, instead of recursing | |
115 | index = imin; | |
116 | min = _heap[index].pq_priority; // loop invar, but comp wont figure it | |
117 | goto tailrecurse; | |
118 | } else | |
119 | return; | |
120 | } | |
121 | ||
122 | ||
123 | void | |
124 | EventQue::_bottomup_update (int index) // aka. MIN-DECREASE-KEY in "Intro to Algs" | |
125 | { | |
126 | // Bottom up restoration of the heap invariant starting at index, | |
127 | // assuming that only the node at index has been modified and that | |
128 | // only that node potentially fails the invariant. If might have to | |
129 | // percolate updwards if its priority is too low (too near in the future). | |
130 | ||
131 | uint64_t min = _heap[index].pq_priority; | |
132 | int imin = index; | |
133 | ||
134 | tailrecurse: | |
135 | ||
136 | /* see if index has a lower priority (earlier time) than its parent */ | |
137 | if (index > 1 && min < _heap[PQ_PARENT(index)].pq_priority) { | |
138 | imin = PQ_PARENT(index); | |
139 | /* oops, dont do this!: min = _heap[imin].pq_priority; */ | |
140 | } else | |
141 | return; | |
142 | ||
143 | /* if so swap it up into its parent's place, then ascend... */ | |
144 | if (imin != index) { | |
145 | Event_t temp = _heap[index]; // copy semantics, ugh... | |
146 | _heap[index] = _heap[imin]; // ugh... | |
147 | _heap[imin] = temp; // ugh... | |
148 | ||
149 | // fix parameters and loop, instead of recursing | |
150 | index = imin; | |
151 | goto tailrecurse; | |
152 | } | |
153 | } | |
154 | ||
155 | ||
156 | void | |
157 | EventQue::_insert (Event_t * object) | |
158 | { | |
159 | if (_size == _limit) | |
160 | _grow(); | |
161 | _heap[_size+1] = *object; // copy semantics... | |
162 | _bottomup_update (_size+1); | |
163 | _size = _size+1; | |
164 | } | |
165 | ||
166 | ||
167 | void | |
168 | EventQue::_delete (Event_t * object) | |
169 | { | |
170 | if (object != NULL) *object = _heap[1]; // copy semantics... | |
171 | if (_size > 1) { | |
172 | _heap[1] = _heap[_size]; | |
173 | _size = _size-1; | |
174 | _topdown_update (1); | |
175 | } else | |
176 | _size = 0; | |
177 | } | |
178 | ||
179 | ||
180 | ||
181 | ||
182 | ||
183 | #if 0 /* SELFTEST */ | |
184 | ||
185 | /* Stateless random number generator, 31-bit integer result. */ | |
186 | int rand31 (int prev) | |
187 | { | |
188 | int hi, lo, next; | |
189 | ||
190 | /* See "Random Number Generators: Good Ones Are Hard To Find", */ | |
191 | /* Park & Miller, CACM 31#10 October 1988 pages 1192-1201. */ | |
192 | #define _A_MULTIPLIER 16807 | |
193 | #define _M_MODULUS 2147483647 /* (2**31)-1 */ | |
194 | #define _Q_QUOTIENT 127773 /* 2147483647 / 16807 */ | |
195 | #define _R_REMAINDER 2836 /* 2147483647 % 16807 */ | |
196 | ||
197 | hi = prev / _Q_QUOTIENT; | |
198 | lo = prev % _Q_QUOTIENT; | |
199 | next = _A_MULTIPLIER * lo - _R_REMAINDER * hi; | |
200 | if (next > 0) { | |
201 | return next; | |
202 | } else { | |
203 | return next + _M_MODULUS; | |
204 | } | |
205 | } | |
206 | ||
207 | ||
208 | ||
209 | int main (int argc, char * argv[]) | |
210 | { | |
211 | int i, RN = 0x12345678; | |
212 | uint64_t dummy_data[8]; | |
213 | EventQue pq; | |
214 | EventQue::Event_t temp; | |
215 | ||
216 | if (argc == 2 && strcmp (argv[1], "-rand") == 0) { | |
217 | for (i=0; i<100; i++) { | |
218 | RN = rand31(RN); | |
219 | printf ("%4d\n", RN%1000); | |
220 | } | |
221 | exit (0); | |
222 | } else if (argc == 2) { | |
223 | printf ("usage:\n"); | |
224 | printf ("\ta.out > prioque.out;\n"); | |
225 | printf ("\ta.out -rand | sort > sort.out;\n"); | |
226 | printf ("\tdiff prioque.out sort.out; # should be equal...\n"); | |
227 | } | |
228 | ||
229 | ||
230 | for (i=0; i<100; i++) { // insert 100 items | |
231 | RN = rand31(RN); | |
232 | pq.insert_mondo ((uint64_t)RN%1000, (uint64_t)RN%1000, &dummy_data[0]); | |
233 | /*printf ("--- after insert ---\n");pq.debug ();*/ | |
234 | } | |
235 | if (pq.size () != 100) | |
236 | printf ("1) size=%d, expecting 10\n", pq.size ()); | |
237 | ||
238 | #if 0 | |
239 | for (i=0; i<900; i++) { // insert and delete 900 | |
240 | pq.get_top (&temp); | |
241 | if (temp.pq_kind == EventQue::PQ_MONDO) { | |
242 | printf ("%4d\n", (int)temp.pq_ctrl); | |
243 | } else | |
244 | printf ("2.a) kind=%d, expecting %d\n", temp.pq_kind, EventQue::PQ_MONDO); | |
245 | ||
246 | RN = rand31(RN); | |
247 | pq.insert_mondo ((uint64_t)RN%1000, (uint64_t)RN%1000, &dummy_data[0]); | |
248 | } | |
249 | if (pq.size () != 100) | |
250 | printf ("2) size=%d, expecting 10\n", pq.size ()); | |
251 | #endif | |
252 | ||
253 | ||
254 | for (i=0; i<100; i++) { // delete 100 items | |
255 | pq.get_top (&temp); | |
256 | if (temp.pq_kind == EventQue::PQ_MONDO) { | |
257 | printf ("%4d\n", (int)temp.pq_ctrl); | |
258 | } else | |
259 | printf ("3.a) kind=%d, expecting %d\n", temp.pq_kind, EventQue::PQ_MONDO); | |
260 | /*printf ("--- after delete ---\n");pq.debug ();*/ | |
261 | } | |
262 | if (!pq.empty () || pq.size () != 0) | |
263 | printf ("3) size=%d, expecting 0\n", pq.size ()); | |
264 | ||
265 | return 0; | |
266 | } | |
267 | ||
268 | #endif |