ROSS
splay.c
Go to the documentation of this file.
1/*
2 * queue-splay.c :- splay tree for priority queue
3 *
4 * THIS IMPLEMENTATION IS ADAPTED FROM THE DASSF
5 * C++ IMPLEMENTATION.
6 * THEIR COPYRIGHT IS ATTACHED BELOW
7 */
8
9/*
10 * Copyright (c) 1998-2002 Dartmouth College
11 *
12 * Permission is hereby granted, free of charge, to any individual or
13 * institution obtaining a copy of this software and associated
14 * documentation files (the "Software"), to use, copy, modify, and
15 * distribute without restriction, provided that this copyright and
16 * permission notice is maintained, intact, in all copies and supporting
17 * documentation.
18 *
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
22 * IN NO EVENT SHALL DARTMOUTH COLLEGE BE LIABLE FOR ANY CLAIM, DAMAGES
23 * OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
24 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
25 * OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
26 */
27
28#include <ross.h>
29
30#define ROSS_WARN_TIE_COLLISION 1
31
32#define UP(t) ((t)->up)
33#define UPUP(t) ((t)->up->up)
34#define LEFT(t) ((t)->next)
35#define RIGHT(t) ((t)->prev)
36#define KEY(t) ((t)->recv_ts)
37
38struct tw_pq
39{
40 tw_event *root;
41 tw_event *least;
42 unsigned int nitems;
43 unsigned int max_size;
44};
45typedef tw_pq splay_tree;
46
47#define ROTATE_R(n,p,g) \
48 if((LEFT(p) = RIGHT(n))) UP(RIGHT(n)) = p; RIGHT(n) = p; \
49 UP(n) = g; UP(p) = n;
50
51#define ROTATE_L(n,p,g) \
52 if((RIGHT(p) = LEFT(n))) UP(LEFT(n)) = p; LEFT(n) = p; \
53 UP(n) = g; UP(p) = n;
54
55tw_pq *
56tw_pq_create(void)
57{
58 splay_tree *st = (splay_tree *) tw_calloc(TW_LOC, "splay tree queue", sizeof(splay_tree), 1);
59
60 st->root = 0;
61 st->least = 0;
62 st->nitems = 0;
63
64 return st;
65}
66
67static unsigned int tw_pq_compare_less_than( tw_event *n, tw_event *e )
68{
69 if (TW_STIME_CMP(KEY(n), KEY(e)) < 0)
70 return 1;
71 else if (TW_STIME_CMP(KEY(n), KEY(e)) > 0)
72 return 0;
73 else
74 {
75 if( n->send_lp < e->send_lp )
76 return 1;
77 else if( n->send_lp > e->send_lp )
78 return 0;
79 else
80 {
81 if( n->dest_lp->gid < e->dest_lp->gid )
82 return 1;
83 else if(n->dest_lp->gid > e->dest_lp->gid )
84 return 0;
85 else
86 {
87 if( n->event_id < e->event_id )
88 return 1;
89 else if( n->event_id > e->event_id )
90 return 0;
91 else
92 tw_error(TW_LOC, "Found tie events at ts %lf when it's impossible!!\n", e->recv_ts);
93 }
94 }
95 }
96}
97
98#ifdef USE_RAND_TIEBREAKER
99static unsigned int tw_pq_compare_less_than_rand(tw_event *n, tw_event *e)
100{
101 if (TW_STIME_CMP(KEY(n), KEY(e)) < 0)
102 return 1;
103 else if (TW_STIME_CMP(KEY(n), KEY(e)) > 0)
104 return 0;
105 else
106 {
107 if (TW_STIME_CMP(n->sig.priority, e->sig.priority) < 0)
108 return 1;
109 else if (TW_STIME_CMP(n->sig.priority, e->sig.priority) > 0)
110 return 0;
111 else {
112 int min_len = min_int(e->sig.tie_lineage_length, n->sig.tie_lineage_length);
113 for(int i = 0; i < min_len; i++)
114 {
115 if (e->sig.event_tiebreaker[i] < n->sig.event_tiebreaker[i])
116 return 0;
117 else if (e->sig.event_tiebreaker[i] > n->sig.event_tiebreaker[i])
118 return 1;
119 }
120 if (e->sig.tie_lineage_length == n->sig.tie_lineage_length) //total tie
121 {
122 if (n->event_id < e->event_id)
123 return 1;
124 else if (n->event_id > e->event_id)
125 return 0;
126 else {
127 if (ROSS_WARN_TIE_COLLISION)
128 printf("ROSS Splay Tree Warning: Identical Tiebreaker and Event IDs found - Implies RNG Collision\n");
129 if(n->send_pe < e->send_pe)
130 return 1;
131 else if (n->send_pe > e->send_pe)
132 return 0;
133 else
134 tw_error(TW_LOC,"Identical events found - impossible\n");
135 }
136 }
137 else if (e->sig.tie_lineage_length > n->sig.tie_lineage_length) //give priority to one with shorter lineage
138 return 1;
139 else
140 return 0;
141 }
142 }
143}
144#endif
145
146static void
147splay(tw_event * node)
148{
149 register tw_event *n = node, *g, *p;
150 register tw_event *x, *z;
151
152 for (; (p = UP(n));)
153 {
154 if (n == LEFT(p))
155 {
156 if (!((g = UPUP(n))))
157 {
158 ROTATE_R(n, p, g);
159 } else if (p == LEFT(g))
160 {
161 if ((z = UP(g)))
162 {
163 if (g == LEFT(z))
164 LEFT(z) = n;
165 else
166 RIGHT(z) = n;
167 }
168 UP(n) = z;
169 if ((x = LEFT(p) = RIGHT(n)))
170 UP(x) = p;
171 RIGHT(n) = p;
172 UP(p) = n;
173 if ((x = LEFT(g) = RIGHT(p)))
174 UP(x) = g;
175 RIGHT(p) = g;
176 UP(g) = p;
177 } else
178 {
179 if ((z = UP(g)))
180 {
181 if (g == LEFT(z))
182 LEFT(z) = n;
183 else
184 RIGHT(z) = n;
185 }
186 UP(n) = z;
187 if ((x = LEFT(p) = RIGHT(n)))
188 RIGHT(n) = UP(x) = p;
189 else
190 RIGHT(n) = p;
191 if ((x = RIGHT(g) = LEFT(n)))
192 LEFT(n) = UP(x) = g;
193 else
194 LEFT(n) = g;
195 UP(g) = UP(p) = n;
196 }
197 } else
198 {
199 if (!((g = UPUP(n))))
200 {
201 ROTATE_L(n, p, g);
202 } else if (p == RIGHT(g))
203 {
204 if ((z = UP(g)))
205 {
206 if (g == RIGHT(z))
207 RIGHT(z) = n;
208 else
209 LEFT(z) = n;
210 }
211 UP(n) = z;
212 if ((x = RIGHT(p) = LEFT(n)))
213 UP(x) = p;
214 LEFT(n) = p;
215 UP(p) = n;
216 if ((x = RIGHT(g) = LEFT(p)))
217 UP(x) = g;
218 LEFT(p) = g;
219 UP(g) = p;
220 } else
221 {
222 if ((z = UP(g)))
223 {
224 if (g == RIGHT(z))
225 RIGHT(z) = n;
226 else
227 LEFT(z) = n;
228 }
229 UP(n) = z;
230 if ((x = RIGHT(p) = LEFT(n)))
231 LEFT(n) = UP(x) = p;
232 else
233 LEFT(n) = p;
234 if ((x = LEFT(g) = RIGHT(n)))
235 RIGHT(n) = UP(x) = g;
236 else
237 RIGHT(n) = g;
238 UP(g) = UP(p) = n;
239 }
240 }
241 }
242}
243
244void
245tw_pq_enqueue(splay_tree *st, tw_event * e)
246{
247 tw_event *n = st->root;
248
249 st->nitems++;
250 if (st->nitems > st->max_size)
251 st->max_size = st->nitems;
252
253 e->state.owner = TW_pe_pq;
254
255 RIGHT(e) = LEFT(e) = 0;
256 if (n)
257 {
258 for (;;)
259 {
260#ifdef USE_RAND_TIEBREAKER
261 if( tw_pq_compare_less_than_rand( n, e ) )
262#else
263 if (tw_pq_compare_less_than( n, e) )
264#endif
265 {
266 if (RIGHT(n))
267 n = RIGHT(n);
268 else
269 {
270 RIGHT(n) = e;
271 UP(e) = n;
272 break;
273 }
274 } else
275 {
276 if (LEFT(n))
277 n = LEFT(n);
278 else
279 {
280 if (st->least == n)
281 st->least = e;
282 LEFT(n) = e;
283 UP(e) = n;
284 break;
285 }
286 }
287 }
288 splay(e);
289 st->root = e;
290 } else
291 {
292 st->root = st->least = e;
293 UP(e) = 0;
294 }
295}
296
297tw_event *
298tw_pq_dequeue(splay_tree *st)
299{
300 tw_event *r = st->least;
301 tw_event *tmp, *p;
302
303 if (st->nitems == 0)
304 return (tw_event *) NULL;
305
306 st->nitems--;
307
308 if ((p = UP(st->least)))
309 {
310 if ((tmp = RIGHT(st->least)))
311 {
312 LEFT(p) = tmp;
313 UP(tmp) = p;
314 for (; LEFT(tmp); tmp = LEFT(tmp));
315 st->least = tmp;
316 } else
317 {
318 st->least = UP(st->least);
319 LEFT(st->least) = 0;
320 }
321 } else
322 {
323 if ((st->root = RIGHT(st->least)))
324 {
325 UP(st->root) = 0;
326 for (tmp = st->root; LEFT(tmp); tmp = LEFT(tmp));
327 st->least = tmp;
328 } else
329 st->least = 0;
330 }
331
332 LEFT(r) = NULL;
333 RIGHT(r) = NULL;
334 UP(r) = NULL;
335 r->state.owner = 0;
336
337 return r;
338}
339
340void
341tw_pq_delete_any(splay_tree *st, tw_event * r)
342{
343 tw_event *n, *p;
344 tw_event *tmp;
345
346 r->state.owner = 0;
347
348 if (r == st->least)
349 {
350 tw_pq_dequeue(st);
351 return;
352 }
353
354 if (st->nitems == 0)
355 {
356 tw_error(TW_LOC,
357 "tw_pq_delete_any: attempt to delete from empty queue \n");
358 }
359
360 st->nitems--;
361
362 if ((n = LEFT(r)))
363 {
364 if ((tmp = RIGHT(r)))
365 {
366 UP(n) = 0;
367 for (; RIGHT(n); n = RIGHT(n));
368 splay(n);
369 RIGHT(n) = tmp;
370 UP(tmp) = n;
371 }
372 UP(n) = UP(r);
373 } else if ((n = RIGHT(r)))
374 {
375 UP(n) = UP(r);
376 }
377
378 if ((p = UP(r)))
379 {
380 if (r == LEFT(p))
381 LEFT(p) = n;
382 else
383 RIGHT(p) = n;
384 if (n)
385 {
386 splay(p);
387 st->root = p;
388 }
389 } else
390 st->root = n;
391
392 LEFT(r) = NULL;
393 RIGHT(r) = NULL;
394 UP(r) = NULL;
395}
396
397tw_stime
398tw_pq_minimum(splay_tree *pq)
399{
400 return ((pq->least ? pq->least->recv_ts : TW_STIME_MAX));
401}
402
403#ifdef USE_RAND_TIEBREAKER
404/* Returns the mininum value from priority-queue. Do NOT modify pointer. */
405tw_event_sig const *
406tw_pq_minimum_sig_ptr(splay_tree const * pq) {
407 return pq->least ? &pq->least->sig : &g_tw_max_sig;
408}
409
410inline tw_eventid
411tw_pq_minimum_get_event_id(splay_tree *pq)
412{
413 return((pq->least ? pq->least->event_id : UINT_MAX));
414}
415#endif
416
417unsigned int
418tw_pq_get_size(splay_tree *st)
419{
420 return (st->nitems);
421}
422
423unsigned int
424tw_pq_max_size(splay_tree *pq)
425{
426 return (pq->max_size);
427}
TW_STIME_MAX
#define TW_STIME_MAX
Definition ross-base.h:45
TW_STIME_CMP
#define TW_STIME_CMP(x, y)
Definition ross-base.h:43
tw_stime
double tw_stime
Definition ross-base.h:39
tw_calloc
void * tw_calloc(const char *file, int line, const char *for_who, size_t e_sz, size_t n)
Definition tw-util.c:206
tw_error
void tw_error(const char *file, int line, const char *fmt,...)
Definition tw-util.c:77
TW_LOC
#define TW_LOC
Definition ross-extern.h:178
g_tw_max_sig
tw_event_sig const g_tw_max_sig
min_int
static int min_int(int x, int y)
Definition ross-types.h:503
TW_pe_pq
@ TW_pe_pq
In a tw_pe.pq.
Definition ross-types.h:225
tw_eventid
unsigned int tw_eventid
Definition ross-types.h:56
ROSS_WARN_TIE_COLLISION
#define ROSS_WARN_TIE_COLLISION
Definition splay.c:30
LEFT
#define LEFT(t)
Definition splay.c:34
ROTATE_L
#define ROTATE_L(n, p, g)
Definition splay.c:51
tw_pq_max_size
unsigned int tw_pq_max_size(splay_tree *pq)
Definition splay.c:424
tw_pq_minimum
tw_stime tw_pq_minimum(splay_tree *pq)
Definition splay.c:398
KEY
#define KEY(t)
Definition splay.c:36
splay_tree
tw_pq splay_tree
Definition splay.c:45
UP
#define UP(t)
Definition splay.c:32
UPUP
#define UPUP(t)
Definition splay.c:33
tw_pq_enqueue
void tw_pq_enqueue(splay_tree *st, tw_event *e)
Definition splay.c:245
splay
static void splay(tw_event *node)
Definition splay.c:147
tw_pq_delete_any
void tw_pq_delete_any(splay_tree *st, tw_event *r)
Definition splay.c:341
tw_pq_compare_less_than
static unsigned int tw_pq_compare_less_than(tw_event *n, tw_event *e)
Definition splay.c:67
ROTATE_R
#define ROTATE_R(n, p, g)
Definition splay.c:47
tw_pq_dequeue
tw_event * tw_pq_dequeue(splay_tree *st)
Definition splay.c:298
tw_pq_get_size
unsigned int tw_pq_get_size(splay_tree *st)
Definition splay.c:418
RIGHT
#define RIGHT(t)
Definition splay.c:35
tw_pq_create
tw_pq * tw_pq_create(void)
Definition splay.c:56
tw_event_sig
Definition ross-types.h:259
tw_event_sig::event_tiebreaker
double event_tiebreaker[20]
Definition ross-types.h:263
tw_event_sig::priority
double priority
Definition ross-types.h:261
tw_event_sig::tie_lineage_length
unsigned int tie_lineage_length
Definition ross-types.h:262
tw_event
Event Stucture.
Definition ross-types.h:277
tw_event::state
struct tw_event::@130070134144252114152124341363102114315067064025 state
tw_event::recv_ts
tw_stime recv_ts
Actual time to be received.
Definition ross-types.h:314
tw_event::owner
unsigned char owner
Owner of the next/prev pointers; see tw_event_owner.
Definition ross-types.h:300
tw_event::send_lp
tw_lpid send_lp
sending LP ID for data collection uses
Definition ross-types.h:317
tw_event::dest_lp
tw_lp * dest_lp
Destination LP ID.
Definition ross-types.h:312
tw_event::event_id
tw_eventid event_id
Unique id assigned by src_lp->pe if remote.
Definition ross-types.h:291
tw_event::send_pe
tw_peid send_pe
Definition ross-types.h:316
tw_event::sig
tw_event_sig sig
Event signature, to be used by tiebreaker.
Definition ross-types.h:294
tw_lp::gid
tw_lpid gid
global LP id
Definition ross-types.h:338
tw_pq
Definition splay.c:39
tw_pq::root
tw_event * root
Definition splay.c:40
tw_pq::max_size
unsigned int max_size
Definition splay.c:43
tw_pq::least
tw_event * least
Definition splay.c:41
tw_pq::nitems
unsigned int nitems
Definition splay.c:42
Generated by doxygen 1.14.0