Line data Source code
1 : /* Generate prototypes, inlines and implementations for ultra high
2 : performance treaps. A treap hybrid of a binary search tree and heap
3 : such that it will well-balanced on average statistically.
4 :
5 : It is not as well-balanced theoretically as more complex
6 : non-randomized balancing tree algorithms (e.g. red-black trees, AVL
7 : trees, etc). But it is often better in practice as it is much
8 : simpler (i.e. amenable for ultra high performance and small code
9 : footprint implementation) and very adaptable (e.g. easy to tweak to
10 : support adaptive queries like a splay tree, etc). Additionally,
11 : there are a bunch of tricks in the below to optimize this much
12 : further than textbook implementations (those tend to miss a lot of
13 : practical opportunities including eliminating the cost of random
14 : number generation during operations).
15 :
16 : This API is designed for ultra tight coupling with pools, maps, other
17 : treaps, etc. Likewise, a treap can be persisted beyond the lifetime
18 : of creating process, used concurrently in many common operations,
19 : used inter-process, relocated in memory, naively
20 : serialized/deserialized, moved between hosts, supports index
21 : compression for cache and memory bandwidth efficiency, etc.
22 :
23 : Typical usage:
24 :
25 : struct myele {
26 :
27 : ... Each field below can be located arbitrarily in the struct
28 :
29 : ulong parent; // Technically "TREAP_IDX_T TREAP_PARENT;" (default is ulong parent), similarly for left, right, and prio.
30 : ulong left; // parent, left and right managed by the treap when a myele is in the treap. prio is constant while in a
31 : ulong right; // treap. Further, all these can be used arbitrarily when not in treap (this includes perhaps using an
32 : ulong prio; // anonymous union and/or bit fields for even more flexibility). Additional considerations for prio below.
33 :
34 : // if TREAP_OPTIMIZE_ITERATION is set to 1, the following two
35 : // fields are also needed:
36 : ulong next; // Similarly to above, technically TREAP_IDX_T TREAP_NEXT, TREAP_PREV. These fields are treap-managed when
37 : ulong prev; // a myele is in the treap and can be used arbitrarily when not.
38 :
39 :
40 : ... Generally speaking, this treap implement is agnostic to how
41 : ... the user manages treap priorities. The algorithmic costs
42 : ... below assume that priorities are random though.
43 :
44 : ... For stock usage cases, the most optimal handling of prio is
45 : ... to initialize the prio field exactly once when the myele
46 : ... storage is first created with random values and then leave it
47 : ... unchanged thereafter (and potentially reused by other APIs
48 : ... needing similar randomization). This eliminates all
49 : ... overheads associated with random number generation during
50 : ... operation. But this also means that prio field is not
51 : ... available for use when a myele is not in the treap.
52 :
53 : ... In other situations, the user might chose to generate random
54 : ... priorities dynamically (as it done in textbook
55 : ... implementations) and/or adjust element priorities on the fly
56 : ... to splay-tree-like adaptively optimize treap queries.
57 :
58 : ... To support potential future bulk operations (e.g. fast treap
59 : ... splits / joins), it is recommended that these random values
60 : ... exclude the largest possible value but this is not strictly
61 : ... required currently.
62 :
63 : ... Note that other kinds of objects can use these fields for
64 : ... their metadata needs to keep element metadata / cache
65 : ... footprint overheads minimal. The only restriction is that
66 : ... they cannot concurrently use the same field. E.g. a pool
67 : ... could use the "parent" field for its next pointer while
68 : ... multiple other _disjoint_ treaps of myele_t from the same
69 : ... pool can all use the same treap fields.
70 :
71 : ... Note that fields could be made into narrow bit fields if
72 : ... useful for additional memory, bandwidth and cache efficiency.
73 : ... In particular, for priorities, unbiased pseudo random coin
74 : ... flipping is used to break ties (a little priority can go a
75 : ... very long way practically).
76 :
77 : ... Arbitrary application fields mixed in here. Power-of-2
78 : ... element sizes have good cache and indexing Feng Shui.
79 :
80 : char key[ KEY_MAX ]; // For demonstration purposes
81 :
82 : };
83 :
84 : typedef struct myele myele_t;
85 :
86 : #define TREAP_NAME mytreap
87 : #define TREAP_T myele_t
88 : #define TREAP_QUERY_T char const *
89 : #define TREAP_CMP(q,e) strcmp( q, e->key )
90 : #define TREAP_LT(e0,e1) (strcmp( e0->key, e1->key )<0)
91 : #include "fd_treap.c"
92 :
93 : will declare the following APIs as a header-only style library in the
94 : compilation unit:
95 :
96 : int mytreap_cmp( char const * q, myele_t const * e ); // Provides TREAP_CMP
97 : int mytreap_lt ( myele_t const * e0, myele_t const * e1 ); // Provides TREAP_LT
98 :
99 : // mytreap_idx_null returns the element index used to represent
100 : // NULL, infinite lifetime. mytreap_ele_null returns NULL,
101 : // infinite lifetime, for completeness, mytreap_ele_null_const is a
102 : // const-correct version, also for completeness.
103 :
104 : ulong mytreap_idx_null ( void );
105 : myele_t * mytreap_ele_null ( void );
106 : myele_t const * mytreap_ele_null_const( void );
107 :
108 : // mytreap_{idx,ele}_is_null returns i==mytreap_idx_null() / !e
109 :
110 : int mytreap_idx_is_null( ulong i );
111 : int mytreap_ele_is_null( myele_t const * e );
112 :
113 : // mytreap_idx returns e's index. Assumes e is a pointer in the
114 : // caller's local address space to a pool element or is NULL.
115 : // Return will be in [0,ele_max) or mytreap_idx_null(). Lifetime
116 : // is the element storage lifetime. mytreap_idx_fast is the same
117 : // assumes e is not NULL. pool is a pointer in the caller's
118 : // address space to the ele_max linearly addressable storage region
119 : // backing the treap.
120 :
121 : ulong mytreap_idx ( myele_t const * e, myele_t const * pool );
122 : ulong mytreap_idx_fast( myele_t const * e, myele_t const * pool );
123 :
124 : // mytreap_ele returns a pointer in the caller's address space to
125 : // element idx. Assumes idx is in [0,ele_max) or is
126 : // mytreap_idx_null(). Return pointer lifetime is ele's local
127 : // lifetime. mytreap_ele_fast is the same but assumes idx is not
128 : // mytreap_idx_null(). mytreap_ele[_fast]_const is a const correct
129 : // version. pool is a pointer in the caller's address space to the
130 : // ele_max linearly addressable storage region backing the treap.
131 :
132 : myele_t * mytreap_ele ( ulong i, myele_t * pool );
133 : myele_t * mytreap_ele_fast( ulong i, myele_t * pool );
134 :
135 : myele_t const * mytreap_ele_const ( ulong i, myele_t const * pool );
136 : myele_t const * mytreap_ele_fast_const( ulong i, myele_t const * pool );
137 :
138 : // mytreap_seed is a helper that sets pool[i].prio for i in
139 : // [0,ele_max) to a random value in [0,PRIO_MAX) (yes half-open)
140 : // where PRIO_MAX is the largest possible value representable in
141 : // the prio field. Uses seed (arbitrary) to select a simple hash
142 : // based random number of sequence for prio.
143 : //
144 : // If an application wants to set this as optimally and securely as
145 : // possible, it should seed pool[i].prio with a cryptographic
146 : // secure uniform random permutation of [0,ele_max) and/or
147 : // dynamically manage the prio field as described above.
148 :
149 : void mytreap_seed( myele_t * pool, ulong ele_max, ulong seed );
150 :
151 : // mytreap_{align,footprint} returns the alignment and footprint
152 : // needed for a memory region to hold the state of a mytreap of
153 : // elements from a linearly addressable ele_max element storage.
154 : // align will be an integer power-of-two and footprint will be a
155 : // multiple of align. footprint will non-zero on a success and 0
156 : // on failure (silent) (e.g. ele_max too large for the specified
157 : // TREAP_IDX_T). mytreap_t is stack declaration, data segment
158 : // declaration, heap allocation and stack allocation friendly.
159 : // Even though footprint is passed ele_max, the footprint is a
160 : // small O(1) spatial overhead.
161 : //
162 : // mytreap_new formats a memory region with the appropriate
163 : // alignment and footprint whose first byte in the caller's address
164 : // space is pointed to by shmem as a mytreap for elements from a
165 : // linearly addressable ele_max element storage. Returns shmem on
166 : // success and NULL on failure (log details, e.g. ele_max is too
167 : // large for the width of the TREAP_IDX_T specified). Caller is
168 : // not joined on return. The treap will be empty.
169 : //
170 : // mytreap_join joins a mytreap. Assumes shtreap points at a
171 : // memory region formatted as a mytreap in the caller's address
172 : // space. Returns a handle to the caller's local join on success
173 : // and NULL on failure (logs details).
174 : //
175 : // mytreap_leave leaves a mytreap. Assumes join points to a
176 : // current local join. Returns shtreap used on join and NULL on
177 : // failure (logs details).
178 : //
179 : // mytreap_delete unformats a memory region used as a mytreap.
180 : // Assumes shtreap points to a memory region in the caller's local
181 : // address space formatted as a mytreap, that there are no joins to
182 : // the mytreap and that any application side cleanups have been
183 : // done. Returns shtreap on success and NULL on failure (logs
184 : // details).
185 :
186 : ulong mytreap_align ( void );
187 : ulong mytreap_footprint( ulong ele_max );
188 : void * mytreap_new ( void * shmem, ulong ele_max );
189 : mytreap_t * mytreap_join ( void * shtreap );
190 : void * mytreap_leave ( mytreap_t * treap );
191 : void * mytreap_delete ( void * shtreap );
192 :
193 : // mytreap_{ele_max,ele_cnt} gives the maximum number of elements
194 : // the treap can support / the current number of elements in the
195 : // treap. Assumes treap is a current local join. These might be
196 : // deprecated in the future.
197 :
198 : ulong mytreap_ele_max( mytreap_t const * treap );
199 : ulong mytreap_ele_cnt( mytreap_t const * treap );
200 :
201 : // mytreap_idx_query finds where q is stored in the treap. Assumes
202 : // treap is a current local join and pool points in the caller's
203 : // address space to the ele_max element storage containing the
204 : // treap elements. Returns [0,ele_max) on success and
205 : // mytreap_idx_null() on failure. Lifetime of the returned idx is
206 : // the lesser of until it is removed or the underlying element
207 : // storage. mytreap_ele_query is the same but returns the location
208 : // in the caller's address space of the found element on success
209 : // and NULL on failure (lifetime of the returned pointer is until
210 : // ele is removed or ele's local lifetime).
211 : // mytreap_ele_query_const is a const correct version.
212 : //
213 : // These operations have HPC implementations and are O(lg N)
214 : // average with an ultra high probability of having a small
215 : // coefficient (i.e. close to algorithmically optimal trees).
216 :
217 : ulong mytreap_idx_query ( mytreap_t const * treap, char const * q, myele_t const * pool );
218 : myele_t * mytreap_ele_query ( mytreap_t * treap, char const * q, myele_t * pool );
219 : myele_t const * mytreap_ele_query_const( mytreap_t const * treap, char const * q, myele_t const * pool );
220 :
221 : // mytreap_idx_{insert,remove} inserts / removes element n/d into
222 : // the treap and returns treap. Assumes treap is a current local
223 : // join, pool points in the caller's address space to the ele_max
224 : // element storage used for treap elements, n/d are in [0,ele_max),
225 : // n/d are currently out of / in the treap. Insert further assumes
226 : // that n's queries are not in the treap (n's queries are the set
227 : // of queries that are covered by n). Given these assumptions,
228 : // these cannot fail.
229 : //
230 : // For insert, n's query and prio fields should already be
231 : // populated (i.e. MYTREAP_LT( ele+n, ele+i ) should return valid
232 : // results before this is called and prio should be a suitable
233 : // value as described above. On return, n and n's queries will be
234 : // in the treap. n's left, right, parent, prio and/or queries
235 : // should not be modified while n is in the treap. Further, the
236 : // caller should not assume n's left, right or parent values are
237 : // stable while n is in the treap. The treap does not care about
238 : // any other fields and these can be modified by the user as
239 : // necessary.
240 : //
241 : // For remove, on return d and d's queries are no longer in the
242 : // treap. The caller is free to modify all fields of d as
243 : // necessary.
244 : //
245 : // mytreap_ele_{insert,remove} are the same but n and d point in
246 : // the caller's local address space the element to insert / remove.
247 : //
248 : // These operations have HPC implementations and are O(lg N)
249 : // average with an ultra high probability of having a small
250 : // coefficient (i.e. close to algorithmically optimal trees).
251 :
252 : mytreap_t * mytreap_idx_insert( mytreap_t * treap, ulong n, myele_t * pool );
253 : mytreap_t * mytreap_idx_remove( mytreap_t * treap, ulong d, myele_t * pool );
254 :
255 : mytreap_t * mytreap_ele_insert( mytreap_t * treap, myele_t * n, myele_t * pool );
256 : mytreap_t * mytreap_ele_remove( mytreap_t * treap, myele_t * d, myele_t * pool );
257 :
258 : // mytreap_fwd_iter_{init,done,next,idx,ele,ele_const} provide an
259 : // in-order iterator from smallest to largest value. Typical
260 : // usage:
261 : //
262 : // for( mytreap_fwd_iter_t iter = mytreap_fwd_iter_init( treap, pool );
263 : // !mytreap_fwd_iter_done( iter );
264 : // iter = mytreap_fwd_iter_next( iter, pool ) ) {
265 : // ulong i = mytreap_fwd_iter_idx( iter );
266 : // ... or myele_t * e = mytreap_fwd_iter_ele ( iter, pool );
267 : // ... or myele_t const * e = mytreap_fwd_iter_ele_const( iter, pool );
268 : //
269 : // ... process i (or e) here
270 : //
271 : // ... Do not remove the element the iterator is currently
272 : // ... pointing to, and do not change the element's parent,
273 : // ... left, right, prio or queries here. It is fine to run
274 : // ... queries and other iterations concurrently. Other fields
275 : // ... are free to modify (from the treap's POV, the
276 : // ... application manages concurrency for other fields).
277 : // }
278 : //
279 : // pool is a pointer in the caller's address space to the ele_max
280 : // linearly addressable storage region backing the treap.
281 :
282 : typedef ... mytreap_fwd_iter_t;
283 :
284 : mytreap_fwd_iter_t mytreap_fwd_iter_init ( mytreap_t const * treap, myele_t const * pool );
285 : int mytreap_fwd_iter_done ( mytreap_fwd_iter_t iter );
286 : mytreap_fwd_iter_t mytreap_fwd_iter_next ( mytreap_fwd_iter_t iter, myele_t const * pool );
287 : ulong mytreap_fwd_iter_idx ( mytreap_fwd_iter_t iter );
288 : myele_t * mytreap_fwd_iter_ele ( mytreap_fwd_iter_t iter, myele_t * pool );
289 : myele_t const * mytreap_fwd_iter_ele_const( mytreap_fwd_iter_t iter, myele_t const * pool );
290 :
291 : // mytreap_rev_iter_{init,done,next,idx,ele,ele_const} is the same
292 : // but used when iterating from largest to smallest.
293 :
294 : typedef ... mytreap_rev_iter_t;
295 :
296 : mytreap_rev_iter_t mytreap_rev_iter_init ( mytreap_t const * treap, myele_t const * pool );
297 : int mytreap_rev_iter_done ( mytreap_rev_iter_t iter );
298 : mytreap_rev_iter_t mytreap_rev_iter_next ( mytreap_rev_iter_t iter, myele_t const * pool );
299 : ulong mytreap_rev_iter_idx ( mytreap_rev_iter_t iter );
300 : myele_t * mytreap_rev_iter_ele ( mytreap_rev_iter_t iter, myele_t * pool );
301 : myele_t const * mytreap_rev_iter_ele_const( mytreap_rev_iter_t iter, myele_t const * pool );
302 :
303 : // mytreap_merge merges two treaps backed by the same pool into a
304 : // single treap. Merge is equivalent to removing each element from
305 : // treap_b and inserting it into treap_a, but merging the heaps is
306 : // asymptotically slightly better. Returns treap_a, which now
307 : // additionally contains the elements from treap_b. Requires that
308 : // the treap does not use the maximum priority element (see the
309 : // note above about PRIO_MAX). Assumes the A and B treaps contain
310 : // no common keys.
311 :
312 : mytreap * mytreap_merge( mytreap * treap_a, mytreap * treap_b, myele_t * pool );
313 :
314 : // mytreap_verify returns 0 if the mytreap is not obviously corrupt
315 : // or a -1 (i.e. ERR_INVAL) if it is (logs details). treap is
316 : // current local join to a mytreap. pool is a pointer in the
317 : // caller's address space to the ele_max linearly addressable
318 : // storage region backing the treap.
319 :
320 : int mytreap_verify( mytreap_t const * treap, myele_t const * pool );
321 :
322 : // IMPORTANT SAFETY TIP! queries and iteration can be done
323 : // concurrently by multiple threads distributed arbitrarily over
324 : // multiple processes provided there are no concurrent insert /
325 : // remove operations on the treap and the application manages
326 : // concurrency for fields not managed by the treap.
327 :
328 : You can do this as often as you like within a compilation unit to get
329 : different types of treaps. Variants exist for making separate headers
330 : and implementations for doing libraries and handling multiple
331 : compilation units. Additional options exist as detailed below. */
332 :
333 : /* TREAP_NAME gives the API prefix to use */
334 :
335 : #ifndef TREAP_NAME
336 : #error "Define TREAP_NAME"
337 : #endif
338 :
339 : /* TREAP_T is the treap element type */
340 :
341 : #ifndef TREAP_T
342 : #error "Define TREAP_T"
343 : #endif
344 :
345 : /* TREAP_QUERY_T is the type that is passed to the query function */
346 :
347 : #ifndef TREAP_QUERY_T
348 : #error "Define TREAP_QUERY_T"
349 : #endif
350 :
351 : /* TREAP_CMP compares a TREAP_QUERY_T q with an element e's query
352 : fields and returns a negative/zero/positive int if q is less
353 : than/equal/greater than element e's query fields. Should be a pure
354 : function. */
355 :
356 : #ifndef TREAP_CMP
357 : #error "Define TREAP_CMP"
358 : #endif
359 :
360 : /* TREAP_LT returns 1 if the element e0's query fields are strictly less
361 : element e1's query fields and 0 otherwise. Should be a pure
362 : function. */
363 :
364 : #ifndef TREAP_LT
365 : #error "Define TREAP_LT"
366 : #endif
367 :
368 : /* TREAP_IDX_T is the type used for the fields in the TREAP_T. Should
369 : be a primitive unsigned integer type. Defaults to ulong. A treap
370 : can't use element memory regions that contain more than the maximum
371 : value that can be represented by a TREAP_IDX_T. */
372 :
373 : #ifndef TREAP_IDX_T
374 9410049 : #define TREAP_IDX_T ulong
375 : #endif
376 :
377 : /* TREAP_{PARENT,LEFT,RIGHT,PRIO} is the name the treap element parent /
378 : left / right / prio fields. Defaults to parent / left / right /
379 : prio. */
380 :
381 : #ifndef TREAP_PARENT
382 77294467 : #define TREAP_PARENT parent
383 : #endif
384 :
385 : #ifndef TREAP_LEFT
386 49787709 : #define TREAP_LEFT left
387 : #endif
388 :
389 : #ifndef TREAP_RIGHT
390 32067478 : #define TREAP_RIGHT right
391 : #endif
392 :
393 : #ifndef TREAP_PRIO
394 46379740 : #define TREAP_PRIO prio
395 : #endif
396 :
397 : /* TREAP_OPTIMIZE_ITERATION controls a space/time tradeoff: when
398 : TREAP_OPTIMIZE_ITERATION is set to 1, each element has two additional
399 : fields and insert and delete take slightly longer. However, in
400 : return, iteration in either direction is substantially faster. This
401 : works by essentially threading a doubly-linked list through elements
402 : in iteration order. The default is sets this to 0, meaning that the
403 : next and prev fields are not required. */
404 : #ifndef TREAP_OPTIMIZE_ITERATION
405 : #define TREAP_OPTIMIZE_ITERATION 0
406 : #endif
407 :
408 : #if TREAP_OPTIMIZE_ITERATION
409 : # ifndef TREAP_NEXT
410 26161545 : # define TREAP_NEXT next
411 : # endif
412 :
413 : # ifndef TREAP_PREV
414 147096450 : # define TREAP_PREV prev
415 : # endif
416 : #endif
417 :
418 : /* TREAP_IMPL_STYLE controls what this template should emit.
419 : 0 - local use only
420 : 1 - library header
421 : 2 - library implementation */
422 :
423 : #ifndef TREAP_IMPL_STYLE
424 : #define TREAP_IMPL_STYLE 0
425 : #endif
426 :
427 : /* Implementation *****************************************************/
428 :
429 : #if TREAP_IMPL_STYLE==0
430 : #define TREAP_STATIC static FD_FN_UNUSED
431 : #else
432 : #define TREAP_STATIC
433 : #endif
434 :
435 4230749752 : #define TREAP_IDX_NULL ((ulong)(TREAP_IDX_T)(~0UL))
436 4055103907 : #define TREAP_IDX_IS_NULL( idx ) ((idx)==TREAP_IDX_NULL)
437 :
438 617644281 : #define TREAP_(n) FD_EXPAND_THEN_CONCAT3(TREAP_NAME,_,n)
439 :
440 : /* Verification logs details on failure. The rest only needs fd_bits.h
441 : (consider making logging a compile time option). */
442 :
443 : #include "../log/fd_log.h"
444 :
445 : #if TREAP_IMPL_STYLE!=2 /* need structures, prototypes and inlines */
446 :
447 : /* structures */
448 :
449 : /* TODO: consider eliminating ele_cnt and maybe ele_max fields (less overhead,
450 : faster bulk ops, concurrency options, simpler constructors, etc) */
451 :
452 : struct TREAP_(private) {
453 : ulong ele_max; /* Maximum number of elements in treap, in [0,TREAP_IDX_NULL] */
454 : ulong ele_cnt; /* Current number of elements in treap, in [0,ele_max] */
455 : #if TREAP_OPTIMIZE_ITERATION
456 : TREAP_IDX_T first; /* Index of the left-most treap element, in [0,ele_max) or TREAP_IDX_NULL */
457 : TREAP_IDX_T last; /* Index of the right-most treap element, in [0,ele_max) or TREAP_IDX_NULL */
458 : #endif
459 : TREAP_IDX_T root; /* Index of the root treap element, in [0,ele_max) or TREAP_IDX_NULL */
460 : };
461 :
462 : typedef struct TREAP_(private) TREAP_(t);
463 :
464 : typedef ulong TREAP_(fwd_iter_t);
465 : typedef ulong TREAP_(rev_iter_t);
466 :
467 : FD_PROTOTYPES_BEGIN
468 :
469 : /* prototypes */
470 :
471 : TREAP_STATIC void TREAP_(seed)( TREAP_T * pool, ulong ele_max, ulong seed );
472 :
473 : TREAP_STATIC FD_FN_CONST ulong TREAP_(align) ( void );
474 : TREAP_STATIC FD_FN_CONST ulong TREAP_(footprint)( ulong ele_max );
475 : TREAP_STATIC /**/ void * TREAP_(new) ( void * shmem, ulong ele_max );
476 : TREAP_STATIC /**/ TREAP_(t) * TREAP_(join) ( void * shtreap );
477 : TREAP_STATIC /**/ void * TREAP_(leave) ( TREAP_(t) * treap );
478 : TREAP_STATIC /**/ void * TREAP_(delete) ( void * shtreap );
479 :
480 : TREAP_STATIC FD_FN_PURE ulong TREAP_(idx_query)( TREAP_(t) const * treap, TREAP_QUERY_T q, TREAP_T const * pool );
481 :
482 : TREAP_STATIC TREAP_(t) * TREAP_(idx_insert)( TREAP_(t) * treap, ulong n, TREAP_T * pool );
483 : TREAP_STATIC TREAP_(t) * TREAP_(idx_remove)( TREAP_(t) * treap, ulong d, TREAP_T * pool );
484 :
485 : TREAP_STATIC FD_FN_PURE TREAP_(fwd_iter_t) TREAP_(fwd_iter_init)( TREAP_(t) const * treap, TREAP_T const * pool );
486 : TREAP_STATIC FD_FN_PURE TREAP_(rev_iter_t) TREAP_(rev_iter_init)( TREAP_(t) const * treap, TREAP_T const * pool );
487 :
488 : TREAP_STATIC FD_FN_PURE TREAP_(fwd_iter_t) TREAP_(fwd_iter_next)( TREAP_(fwd_iter_t) i, TREAP_T const * pool );
489 : TREAP_STATIC FD_FN_PURE TREAP_(rev_iter_t) TREAP_(rev_iter_next)( TREAP_(rev_iter_t) i, TREAP_T const * pool );
490 :
491 : TREAP_STATIC TREAP_(t) * TREAP_(merge)( TREAP_(t) * treap_a, TREAP_(t) * treap_b, TREAP_T * pool );
492 :
493 : TREAP_STATIC FD_FN_PURE int TREAP_(verify)( TREAP_(t) const * treap, TREAP_T const * pool );
494 :
495 : /* inlines */
496 :
497 119069568 : FD_FN_PURE static inline int TREAP_(cmp)( TREAP_QUERY_T q, TREAP_T const * e ) { return TREAP_CMP( q, e ); }
498 1404495186 : FD_FN_PURE static inline int TREAP_(lt) ( TREAP_T const * e0, TREAP_T const * e1 ) { return TREAP_LT( e0, e1 ); }
499 :
500 0 : FD_FN_CONST static inline ulong TREAP_(idx_null) ( void ) { return TREAP_IDX_NULL; }
501 0 : FD_FN_CONST static inline TREAP_T * TREAP_(ele_null) ( void ) { return NULL; }
502 0 : FD_FN_CONST static inline TREAP_T const * TREAP_(ele_null_const)( void ) { return NULL; }
503 :
504 3831663 : FD_FN_CONST static inline int TREAP_(idx_is_null)( ulong i ) { return TREAP_IDX_IS_NULL( i ); }
505 768 : FD_FN_CONST static inline int TREAP_(ele_is_null)( TREAP_T const * e ) { return !e; }
506 :
507 : FD_FN_CONST static inline ulong
508 : TREAP_(idx)( TREAP_T const * e,
509 15006036 : TREAP_T const * pool ) {
510 15006036 : return fd_ulong_if( !!e, (ulong)(e - pool), TREAP_IDX_NULL );
511 15006036 : }
512 :
513 : FD_FN_CONST static inline TREAP_T *
514 : TREAP_(ele)( ulong i,
515 768 : TREAP_T * pool ) {
516 768 : return fd_ptr_if( !TREAP_IDX_IS_NULL( i ), pool + i, NULL );
517 768 : }
518 :
519 : FD_FN_CONST static inline TREAP_T const *
520 : TREAP_(ele_const)( ulong i,
521 768 : TREAP_T const * pool ) {
522 768 : return fd_ptr_if( !TREAP_IDX_IS_NULL( i ), pool + i, NULL );
523 768 : }
524 :
525 : FD_FN_CONST static inline ulong
526 : TREAP_(idx_fast)( TREAP_T const * e,
527 765 : TREAP_T const * pool ) {
528 765 : return (ulong)(e - pool);
529 765 : }
530 :
531 765 : FD_FN_CONST static inline TREAP_T * TREAP_(ele_fast) ( ulong i, TREAP_T * pool ) { return pool + i; }
532 765 : FD_FN_CONST static inline TREAP_T const * TREAP_(ele_fast_const)( ulong i, TREAP_T const * pool ) { return pool + i; }
533 :
534 7513548 : FD_FN_PURE static inline ulong TREAP_(ele_max)( TREAP_(t) const * treap ) { return treap->ele_max; }
535 9326772 : FD_FN_PURE static inline ulong TREAP_(ele_cnt)( TREAP_(t) const * treap ) { return treap->ele_cnt; }
536 :
537 : FD_FN_PURE static inline TREAP_T *
538 : TREAP_(ele_query)( TREAP_(t) const * treap,
539 : TREAP_QUERY_T q,
540 7663467 : TREAP_T * pool ) {
541 7663467 : ulong i = TREAP_(idx_query)( treap, q, pool );
542 7663467 : return fd_ptr_if( !TREAP_IDX_IS_NULL( i ), pool + i, NULL );
543 7663467 : }
544 :
545 : FD_FN_PURE static inline TREAP_T const *
546 : TREAP_(ele_query_const)( TREAP_(t) const * treap,
547 : TREAP_QUERY_T q,
548 7508184 : TREAP_T const * pool ) {
549 7508184 : ulong i = TREAP_(idx_query)( treap, q, pool );
550 7508184 : return fd_ptr_if( !TREAP_IDX_IS_NULL( i ), pool + i, NULL );
551 7508184 : }
552 :
553 : static inline TREAP_(t) *
554 : TREAP_(ele_insert)( TREAP_(t) * treap,
555 : TREAP_T * e,
556 19085484 : TREAP_T * pool ) {
557 19085484 : return TREAP_(idx_insert)( treap, (ulong)(e - pool), pool );
558 19085484 : }
559 :
560 : static inline TREAP_(t) *
561 : TREAP_(ele_remove)( TREAP_(t) * treap,
562 : TREAP_T * e,
563 3746388 : TREAP_T * pool ) {
564 3746388 : return TREAP_(idx_remove)( treap, (ulong)(e - pool), pool );
565 3746388 : }
566 :
567 127094352 : FD_FN_CONST static inline int TREAP_(fwd_iter_done) ( TREAP_(fwd_iter_t) i ) { return TREAP_IDX_IS_NULL( i ); }
568 122331900 : FD_FN_CONST static inline ulong TREAP_(fwd_iter_idx) ( TREAP_(fwd_iter_t) i ) { return i; }
569 124294083 : FD_FN_CONST static inline TREAP_T * TREAP_(fwd_iter_ele) ( TREAP_(fwd_iter_t) i, TREAP_T * pool ) { return pool + i; }
570 120978141 : FD_FN_CONST static inline TREAP_T const * TREAP_(fwd_iter_ele_const)( TREAP_(fwd_iter_t) i, TREAP_T const * pool ) { return pool + i; }
571 :
572 246812079 : FD_FN_CONST static inline int TREAP_(rev_iter_done) ( TREAP_(rev_iter_t) i ) { return TREAP_IDX_IS_NULL( i ); }
573 121162683 : FD_FN_CONST static inline ulong TREAP_(rev_iter_idx) ( TREAP_(rev_iter_t) i ) { return i; }
574 121174026 : FD_FN_CONST static inline TREAP_T * TREAP_(rev_iter_ele) ( TREAP_(rev_iter_t) i, TREAP_T * pool ) { return pool + i; }
575 242095545 : FD_FN_CONST static inline TREAP_T const * TREAP_(rev_iter_ele_const)( TREAP_(rev_iter_t) i, TREAP_T const * pool ) { return pool + i; }
576 :
577 : FD_PROTOTYPES_END
578 :
579 : #endif
580 :
581 : #if TREAP_IMPL_STYLE!=1 /* need implementations */
582 :
583 : TREAP_STATIC void
584 : TREAP_(seed)( TREAP_T * pool,
585 : ulong ele_max,
586 2661 : ulong seed ) {
587 2720490 : for( ulong ele_idx=0UL; ele_idx<ele_max; ele_idx++ ) {
588 2717829 : ulong r = fd_ulong_hash( ele_idx ^ seed ) & TREAP_IDX_NULL;
589 2717829 : pool[ ele_idx ].TREAP_PRIO = (TREAP_IDX_T)(r - (ulong)(r==TREAP_IDX_NULL));
590 2717829 : }
591 2661 : }
592 :
593 : TREAP_STATIC FD_FN_CONST ulong
594 0 : TREAP_(align)( void ) {
595 0 : return alignof(TREAP_(t));
596 0 : }
597 :
598 : TREAP_STATIC FD_FN_CONST ulong
599 24 : TREAP_(footprint)( ulong ele_max ) {
600 24 : if( FD_UNLIKELY( ele_max>TREAP_IDX_NULL ) ) return 0UL;
601 21 : return sizeof(TREAP_(t));
602 24 : }
603 :
604 : TREAP_STATIC void *
605 : TREAP_(new)( void * shmem,
606 205377 : ulong ele_max ) {
607 205377 : if( !shmem ) {
608 3 : FD_LOG_WARNING(( "NULL shmem" ));
609 3 : return NULL;
610 3 : }
611 :
612 205374 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, TREAP_(align)() ) ) ) {
613 3 : FD_LOG_WARNING(( "misaligned shmem" ));
614 3 : return NULL;
615 3 : }
616 :
617 205371 : if( FD_UNLIKELY( ele_max>TREAP_IDX_NULL ) ) {
618 3 : FD_LOG_WARNING(( "ele_max too large" ));
619 3 : return NULL;
620 3 : }
621 :
622 205368 : TREAP_(t) * treap = (TREAP_(t) *)shmem;
623 :
624 205368 : treap->ele_max = ele_max;
625 205368 : treap->ele_cnt = 0UL;
626 205368 : treap->root = (TREAP_IDX_T)TREAP_IDX_NULL;
627 :
628 : #if TREAP_OPTIMIZE_ITERATION
629 27264 : treap->first = (TREAP_IDX_T)TREAP_IDX_NULL;
630 27264 : treap->last = (TREAP_IDX_T)TREAP_IDX_NULL;
631 : #endif
632 :
633 205368 : return treap;
634 205371 : }
635 :
636 : TREAP_STATIC TREAP_(t) *
637 204330 : TREAP_(join)( void * shtreap ) {
638 204330 : if( FD_UNLIKELY( !shtreap ) ) {
639 3 : FD_LOG_WARNING(( "NULL shtreap" ));
640 3 : return NULL;
641 3 : }
642 :
643 204327 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shtreap, TREAP_(align)() ) ) ) {
644 3 : FD_LOG_WARNING(( "misaligned shtreap" ));
645 3 : return NULL;
646 3 : }
647 :
648 204324 : return (TREAP_(t) *)shtreap;
649 204327 : }
650 :
651 : TREAP_STATIC void *
652 62796 : TREAP_(leave)( TREAP_(t) * treap ) {
653 62796 : if( FD_UNLIKELY( !treap ) ) {
654 3 : FD_LOG_WARNING(( "NULL treap" ));
655 3 : return NULL;
656 3 : }
657 :
658 62793 : return (void *)treap;
659 62796 : }
660 :
661 : TREAP_STATIC void *
662 62799 : TREAP_(delete)( void * shtreap ) {
663 62799 : if( FD_UNLIKELY( !shtreap ) ) {
664 3 : FD_LOG_WARNING(( "NULL shtreap" ));
665 3 : return NULL;
666 3 : }
667 :
668 62796 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shtreap, TREAP_(align)() ) ) ) {
669 3 : FD_LOG_WARNING(( "misaligned shtreap" ));
670 3 : return NULL;
671 3 : }
672 :
673 62793 : return shtreap;
674 62796 : }
675 :
676 : TREAP_STATIC ulong
677 : TREAP_(idx_query)( TREAP_(t) const * treap,
678 : TREAP_QUERY_T q,
679 22674285 : TREAP_T const * pool ) {
680 22674285 : ulong i = (ulong)treap->root;
681 130672515 : while( FD_LIKELY( !TREAP_IDX_IS_NULL( i ) ) ) { /* Optimize for found */
682 119069568 : ulong l = (ulong)pool[ i ].TREAP_LEFT;
683 119069568 : ulong r = (ulong)pool[ i ].TREAP_RIGHT;
684 119069568 : int c = TREAP_(cmp)( q, pool + i );
685 119069568 : if( FD_UNLIKELY( !c ) ) break; /* Optimize for larger treaps */
686 107998230 : i = fd_ulong_if( c<0, l, r );
687 107998230 : }
688 22674285 : return i;
689 22674285 : }
690 :
691 : TREAP_STATIC TREAP_(t) *
692 : TREAP_(idx_insert)( TREAP_(t) * treap,
693 : ulong n,
694 30568962 : TREAP_T * pool ) {
695 :
696 : /* Find leaf where to insert n */
697 :
698 30568962 : TREAP_IDX_T * _p_child = &treap->root;
699 : #if TREAP_OPTIMIZE_ITERATION
700 20288853 : TREAP_IDX_T * _p_pnext = &treap->first; /* pointer to prev node's next idx */
701 20288853 : TREAP_IDX_T * _p_nprev = &treap->last; /* pointer to next node's prev idx */
702 : #endif
703 :
704 30568962 : ulong i = TREAP_IDX_NULL;
705 485445204 : for(;;) {
706 485445204 : ulong j = (ulong)*_p_child;
707 485445204 : if( FD_UNLIKELY( TREAP_IDX_IS_NULL( j ) ) ) break; /* Optimize for large treap */
708 454876242 : i = j;
709 454876242 : int lt = TREAP_(lt)( pool + n, pool + i );
710 454876242 : _p_child = fd_ptr_if( lt, &pool[ i ].TREAP_LEFT, &pool[ i ].TREAP_RIGHT );
711 : #if TREAP_OPTIMIZE_ITERATION
712 373360263 : _p_pnext = fd_ptr_if( lt, _p_pnext, &pool[ i ].TREAP_NEXT );
713 373360263 : _p_nprev = fd_ptr_if( lt, &pool[ i ].TREAP_PREV, _p_nprev );
714 : #endif
715 454876242 : }
716 :
717 : /* Insert n. This might momentarily break the heap property. */
718 :
719 30568962 : pool[ n ].TREAP_PARENT = (TREAP_IDX_T)i;
720 30568962 : pool[ n ].TREAP_LEFT = (TREAP_IDX_T)TREAP_IDX_NULL;
721 30568962 : pool[ n ].TREAP_RIGHT = (TREAP_IDX_T)TREAP_IDX_NULL;
722 30568962 : *_p_child = (TREAP_IDX_T)n;
723 :
724 : #if TREAP_OPTIMIZE_ITERATION
725 20288853 : pool[ n ].TREAP_PREV = *_p_nprev;
726 20288853 : pool[ n ].TREAP_NEXT = *_p_pnext;
727 : *_p_nprev = (TREAP_IDX_T)n;
728 : *_p_pnext = (TREAP_IDX_T)n;
729 : #endif
730 :
731 : /* Bubble n up until the heap property is restored. */
732 :
733 30568962 : ulong n_prio = (ulong)pool[ n ].TREAP_PRIO;
734 65914526 : while( !TREAP_IDX_IS_NULL( i ) ) {
735 60007598 : ulong i_prio = (ulong)pool[ i ].TREAP_PRIO;
736 :
737 60007598 : int heap_intact = (n_prio<i_prio) | ((n_prio==i_prio) & (!((n ^ i) & 1UL))); /* Flip coin on equal priority */
738 60007598 : if( heap_intact ) break;
739 :
740 : /* Get i's parent (if any) and parent's link to i (tree root link if no parent) */
741 :
742 35345564 : ulong p = (ulong)pool[ i ].TREAP_PARENT;
743 :
744 35345564 : TREAP_IDX_T * _t0 = fd_ptr_if( TREAP_IDX_IS_NULL( p ), &treap->root, &pool[ p ].TREAP_LEFT );
745 35345564 : /**/ _p_child = fd_ptr_if( i==(ulong)*_t0, _t0, &pool[ p ].TREAP_RIGHT );
746 :
747 : /* Get n's child (if any) that will become i's child */
748 :
749 35345564 : int n_is_left_child = (n==(ulong)pool[ i ].TREAP_LEFT);
750 35345564 : TREAP_IDX_T * _n_child = fd_ptr_if( n_is_left_child, &pool[ n ].TREAP_RIGHT, &pool[ n ].TREAP_LEFT );
751 35345564 : ulong j = (ulong)*_n_child;
752 :
753 : /* Make n child of p (or the root if no parent) */
754 :
755 35345564 : *_p_child = (TREAP_IDX_T)n;
756 35345564 : pool[ n ].TREAP_PARENT = (TREAP_IDX_T)p;
757 :
758 : /* Make i child of n */
759 :
760 35345564 : *_n_child = (TREAP_IDX_T)i;
761 35345564 : pool[ i ].TREAP_PARENT = (TREAP_IDX_T)n;
762 :
763 : /* Make j (if present) child of i */
764 :
765 35345564 : TREAP_IDX_T dummy;
766 35345564 : *fd_ptr_if( n_is_left_child, &pool[ i ].TREAP_LEFT, &pool[ i ].TREAP_RIGHT ) = (TREAP_IDX_T)j;
767 35345564 : *fd_ptr_if( TREAP_IDX_IS_NULL( j ), &dummy, &pool[ j ].TREAP_PARENT ) = (TREAP_IDX_T)i;
768 :
769 : /* Keep bubbling up */
770 :
771 35345564 : i = p;
772 35345564 : }
773 :
774 30568962 : treap->ele_cnt++;
775 30568962 : return treap;
776 30568962 : }
777 :
778 : TREAP_(t) *
779 : TREAP_(idx_remove)( TREAP_(t) * treap,
780 : ulong d,
781 28294659 : TREAP_T * pool ) {
782 :
783 : /* Make a hole at d */
784 :
785 28294659 : ulong p = (ulong)pool[ d ].TREAP_PARENT;
786 28294659 : ulong l = (ulong)pool[ d ].TREAP_LEFT;
787 28294659 : ulong r = (ulong)pool[ d ].TREAP_RIGHT;
788 :
789 28294659 : TREAP_IDX_T * _t0 = fd_ptr_if( TREAP_IDX_IS_NULL( p ), &treap->root, &pool[ p ].TREAP_LEFT );
790 28294659 : TREAP_IDX_T * _p_child = fd_ptr_if( d==(ulong)*_t0, _t0, &pool[ p ].TREAP_RIGHT );
791 :
792 : #if TREAP_OPTIMIZE_ITERATION
793 16967448 : TREAP_IDX_T prev = pool[ d ].TREAP_PREV;
794 16967448 : TREAP_IDX_T next = pool[ d ].TREAP_NEXT;
795 16967448 : TREAP_IDX_T * _pnext = fd_ptr_if( TREAP_IDX_IS_NULL( prev ), &treap->first, &pool[ prev ].TREAP_NEXT );
796 16967448 : TREAP_IDX_T * _nprev = fd_ptr_if( TREAP_IDX_IS_NULL( next ), &treap->last, &pool[ next ].TREAP_PREV );
797 : *_pnext = next;
798 : *_nprev = prev;
799 : #endif
800 :
801 33864601 : for(;;) {
802 :
803 : /* At this point, we have a hole to fill at d:
804 :
805 : p is the hole's parent (if any)
806 : l is the hole's left subtree (if any)
807 : r is the hole's right subtree (if any)
808 :
809 : p_child points to the link from p to hole (if the hole has a
810 : parent) and to the treap root link otherwise.
811 :
812 : If there is neither a left subtree nor a right subtree, we are
813 : done. If there is a left/right subtree, we fill the hole with
814 : the right/left subtree and we are done. */
815 :
816 33864601 : int is_null_left = TREAP_IDX_IS_NULL( l );
817 33864601 : int is_null_right = TREAP_IDX_IS_NULL( r );
818 33864601 : if( FD_LIKELY( is_null_left | is_null_right ) ) { /* Most nodes near bottom */
819 28294659 : TREAP_IDX_T dummy;
820 28294659 : *_p_child = (TREAP_IDX_T)fd_ulong_if( !is_null_left, l, r );
821 28294659 : *( fd_ptr_if( !is_null_left, &pool[ l ].TREAP_PARENT,
822 28294659 : fd_ptr_if( !is_null_right, &pool[ r ].TREAP_PARENT, &dummy ) ) ) = (TREAP_IDX_T)p;
823 28294659 : break;
824 28294659 : }
825 :
826 : /* The hole has two subtrees. We bubble the hole down one, fill the
827 : hole with the root of the subtree that will preserve the heap
828 : priority up to the hole (flipping a coin on ties). Note we don't
829 : need to update any links to/from d as we will be getting rid of
830 : all links / from d. */
831 :
832 5569942 : ulong l_prio = (ulong)pool[ l ].TREAP_PRIO;
833 5569942 : ulong r_prio = (ulong)pool[ r ].TREAP_PRIO;
834 :
835 5569942 : int promote_left = (l_prio>r_prio) | ((l_prio==r_prio) & (!((p ^ d) & 1UL)));
836 :
837 5569942 : ulong c = fd_ulong_if( promote_left, l, r );
838 :
839 5569942 : *_p_child = (TREAP_IDX_T)c;
840 5569942 : pool[ c ].TREAP_PARENT = (TREAP_IDX_T)p;
841 :
842 5569942 : _p_child = fd_ptr_if ( promote_left, &pool[ l ].TREAP_RIGHT, &pool[ r ].TREAP_LEFT );
843 5569942 : p = c;
844 5569942 : l = fd_ulong_if( promote_left, pool[ l ].TREAP_RIGHT, l );
845 5569942 : r = fd_ulong_if( promote_left, r, pool[ r ].TREAP_LEFT );
846 :
847 5569942 : }
848 :
849 28294659 : treap->ele_cnt--;
850 28294659 : return treap;
851 28294659 : }
852 :
853 : static inline void
854 : TREAP_(private_split)( TREAP_IDX_T idx_node, /* Tree to split */
855 : TREAP_T * key, /* Element whose key is not in the treap rooted at idx_node */
856 : TREAP_IDX_T * _idx_left, /* Where to store the left tree root */
857 : TREAP_IDX_T * _idx_right, /* Where to store the right tree root */
858 : TREAP_IDX_T * _idx_last_left, /* Where to store the last (in BST order) element of the new left tree */
859 : TREAP_IDX_T * _idx_first_right, /* Where to store the first(in BST order) element in the new right tree */
860 3176244 : TREAP_T * pool ) { /* Underlying pool */
861 :
862 3176244 : TREAP_IDX_T idx_parent_left = TREAP_IDX_NULL;
863 3176244 : TREAP_IDX_T idx_parent_right = TREAP_IDX_NULL;
864 3176244 : *_idx_last_left = TREAP_IDX_NULL;
865 3176244 : *_idx_first_right = TREAP_IDX_NULL;
866 :
867 6521286 : while( !TREAP_IDX_IS_NULL( idx_node ) ) {
868 :
869 : /* At this point we have a non-empty subtree to split whose root is
870 : node and we should attach the left and right split trees at
871 : idx_parent_left / *_idx_left and idx_parent_right / *_idx_right.
872 : (On the first attach, idx_parent_left/right will be idx_null and
873 : *_idx_left / *_idx_right are locations where to store the output
874 : split treaps.) */
875 :
876 3345042 : if( TREAP_LT( &pool[ idx_node ], key ) ) {
877 :
878 : /* node is left of key which, by the BST property, means all
879 : elements in node's left subtree are also left of key. We don't
880 : know if node's right subtree contains any elements left of key.
881 : If it does, these elements should be attached to node's right
882 : subtree to preserve the BST property of the left split.
883 :
884 : As such, we attach node and node's left subtree to the
885 : left split, update the attach point for the left split to
886 : node's right subtree and then recurse on the node's right
887 : subtree.
888 :
889 : Note that this operation does not do any reordering of
890 : priorities (e.g. if element B was a descendant of element A
891 : before the split and both B and A belong on the left split, B
892 : will still be a descendant of A). */
893 :
894 : /* Attach node and node's left subtree to the left split */
895 3210357 : pool[ idx_node ].TREAP_PARENT = idx_parent_left;
896 3210357 : *_idx_left = idx_node;
897 :
898 : /* The next left split attach is node's right child */
899 3210357 : idx_parent_left = idx_node;
900 3210357 : _idx_left = &pool[ idx_node ].TREAP_RIGHT;
901 :
902 : /* If everything in the right subtree is to the right of the key,
903 : this is the last node on the left. */
904 3210357 : *_idx_last_left = idx_node;
905 :
906 : /* Recurse on the right subtree */
907 3210357 : idx_node = pool[ idx_node ].TREAP_RIGHT;
908 :
909 3210357 : } else { /* Mirror image of the above */
910 :
911 134685 : pool[ idx_node ].TREAP_PARENT = idx_parent_right;
912 134685 : *_idx_right = idx_node;
913 :
914 134685 : idx_parent_right = idx_node;
915 134685 : _idx_right = &pool[ idx_node ].TREAP_LEFT;
916 :
917 134685 : *_idx_first_right = idx_node;
918 :
919 134685 : idx_node = pool[ idx_node ].TREAP_LEFT;
920 :
921 134685 : }
922 3345042 : }
923 :
924 : /* At this point, we have an empty tree to split */
925 :
926 3176244 : *_idx_left = TREAP_IDX_NULL;
927 3176244 : *_idx_right = TREAP_IDX_NULL;
928 3176244 : }
929 :
930 : #if !TREAP_OPTIMIZE_ITERATION
931 : static inline void
932 : TREAP_(private_join)( TREAP_IDX_T idx_left, /* Root of the left treap */
933 : TREAP_IDX_T idx_right, /* Root of the right treap, keys in left treap < keys in right treap */
934 : TREAP_IDX_T * _idx_join, /* Where to store root of joined treaps */
935 0 : TREAP_T * pool ) { /* Underlying pool */
936 0 :
937 0 : TREAP_IDX_T idx_join_parent = TREAP_IDX_NULL;
938 0 :
939 0 : for(;;) {
940 0 :
941 0 : /* TODO: consolidate these cases into a single branch. */
942 0 :
943 0 : if( TREAP_IDX_IS_NULL( idx_left ) ) { /* Left treap empty */
944 0 : /* join is the right treap (or empty if both left and right empty) */
945 0 : if( !TREAP_IDX_IS_NULL( idx_right ) ) pool[ idx_right ].TREAP_PARENT = idx_join_parent;
946 0 : *_idx_join = idx_right;
947 0 : break;
948 0 : }
949 0 :
950 0 : if( TREAP_IDX_IS_NULL( idx_right ) ) { /* Right treap empty */
951 0 : /* join is the left treap */
952 0 : pool[ idx_left ].TREAP_PARENT = idx_join_parent;
953 0 : *_idx_join = idx_left;
954 0 : break;
955 0 : }
956 0 :
957 0 : /* At this point, we have two non empty treaps to join and elements
958 0 : in the left treap have keys before elements in the right treap. */
959 0 :
960 0 : ulong prio_left = (ulong)pool[ idx_left ].TREAP_PRIO;
961 0 : ulong prio_right = (ulong)pool[ idx_right ].TREAP_PRIO;
962 0 : if( (prio_left>prio_right) | ((prio_left==prio_right) & (int)(idx_left^idx_right)) ) {
963 0 :
964 0 : /* At this point, the left treap root has higher priority than the
965 0 : right treap root. So we attach the left treap root and left
966 0 : treap left subtree to the join to preserve the heap property.
967 0 : We know that the left treap right subtree is to the right of
968 0 : these and that the right treap is to the right of that. So our
969 0 : next join attachment point should be at the left treap right
970 0 : subtree and we should recurse on the left treap right subtree
971 0 : and the right treap. */
972 0 :
973 0 : /* Attach left's root and left's left subtree to the join */
974 0 : pool[ idx_left ].TREAP_PARENT = idx_join_parent;
975 0 : *_idx_join = idx_left;
976 0 :
977 0 : /* The next join attach should be left's right subtree */
978 0 : idx_join_parent = idx_left;
979 0 : _idx_join = &pool[ idx_left ].TREAP_LEFT;
980 0 :
981 0 : /* Recurse on left's right subtree and right treap */
982 0 : idx_left = pool[ idx_left ].TREAP_RIGHT;
983 0 :
984 0 : } else { /* Mirror image of the above */
985 0 :
986 0 : pool[ idx_right ].TREAP_PARENT = idx_join_parent;
987 0 : *_idx_join = idx_right;
988 0 :
989 0 : idx_join_parent = idx_right;
990 0 : _idx_join = &pool[ idx_right ].TREAP_RIGHT;
991 0 :
992 0 : idx_right = pool[ idx_right ].TREAP_LEFT;
993 0 :
994 0 : }
995 0 : }
996 0 : }
997 : #endif
998 :
999 : TREAP_(t) *
1000 : TREAP_(merge)( TREAP_(t) * treap_a,
1001 : TREAP_(t) * treap_b,
1002 26130 : TREAP_T * pool ) {
1003 :
1004 26130 : TREAP_IDX_T idx_a = treap_a->root;
1005 26130 : TREAP_IDX_T idx_b = treap_b->root;
1006 26130 : TREAP_IDX_T new_root = TREAP_IDX_NULL;
1007 26130 : TREAP_IDX_T * _idx_merge = &new_root;
1008 :
1009 : # if TREAP_OPTIMIZE_ITERATION
1010 : /* Invariant: idx_{a,b}_{first,last} is the index of the first/last
1011 : node in key order in the subtree rooted at idx_a/idx_b. */
1012 13065 : TREAP_IDX_T idx_a_first = treap_a->first;
1013 13065 : TREAP_IDX_T idx_a_last = treap_a->last;
1014 13065 : TREAP_IDX_T idx_b_first = treap_b->first;
1015 13065 : TREAP_IDX_T idx_b_last = treap_b->last;
1016 :
1017 : /* merged_{prev,next} are the nodes immediately before/after the
1018 : merged subtree. If these are IDX_NULL, then treap_a->first/last
1019 : should be updated instead. */
1020 13065 : TREAP_IDX_T merged_prev = TREAP_IDX_NULL;
1021 13065 : TREAP_IDX_T merged_next = TREAP_IDX_NULL;
1022 : # endif
1023 :
1024 26130 : # define STACK_MAX (128UL)
1025 :
1026 26130 : struct { TREAP_IDX_T idx_merge_parent; TREAP_IDX_T * _idx_merge; TREAP_IDX_T idx_a; TREAP_IDX_T idx_b;
1027 : # if TREAP_OPTIMIZE_ITERATION
1028 : TREAP_IDX_T idx_a_first, idx_a_last, idx_b_first, idx_b_last;
1029 : TREAP_IDX_T merged_prev, merged_next;
1030 : # endif
1031 26130 : } stack[ STACK_MAX ];
1032 26130 : ulong stack_top = 0UL;
1033 :
1034 3202374 : # define STACK_IS_EMPTY (!stack_top)
1035 26130 : # define STACK_IS_FULL (stack_top>=STACK_MAX)
1036 :
1037 : #if TREAP_OPTIMIZE_ITERATION
1038 1588221 : # define STACK_PUSH( imp, im, ia, ib, iaf, ial, ibf, ibl, mp, mn ) do { \
1039 1588221 : stack[ stack_top ].idx_merge_parent = (imp); \
1040 1588221 : stack[ stack_top ]._idx_merge = (im); \
1041 1588221 : stack[ stack_top ].idx_a = (ia); \
1042 1588221 : stack[ stack_top ].idx_b = (ib); \
1043 1588221 : stack[ stack_top ].idx_a_first = (iaf); \
1044 1588221 : stack[ stack_top ].idx_a_last = (ial); \
1045 1588221 : stack[ stack_top ].idx_b_first = (ibf); \
1046 1588221 : stack[ stack_top ].idx_b_last = (ibl); \
1047 1588221 : stack[ stack_top ].merged_prev = (mp); \
1048 1588221 : stack[ stack_top ].merged_next = (mn); \
1049 1588221 : stack_top++; \
1050 1588221 : } while(0)
1051 1588221 : # define STACK_POP( imp, im, ia, ib, iaf, ial, ibf, ibl, mp, mn ) do { \
1052 1588221 : stack_top--; \
1053 1588221 : (imp) = stack[ stack_top ].idx_merge_parent; \
1054 1588221 : (im) = stack[ stack_top ]._idx_merge; \
1055 1588221 : (ia) = stack[ stack_top ].idx_a; \
1056 1588221 : (ib) = stack[ stack_top ].idx_b; \
1057 1588221 : (iaf) = stack[ stack_top ].idx_a_first; \
1058 1588221 : (ial) = stack[ stack_top ].idx_a_last; \
1059 1588221 : (ibf) = stack[ stack_top ].idx_b_first; \
1060 1588221 : (ibl) = stack[ stack_top ].idx_b_last; \
1061 1588221 : (mp) = stack[ stack_top ].merged_prev; \
1062 1588221 : (mn) = stack[ stack_top ].merged_next; \
1063 1588221 : } while(0)
1064 : #else
1065 1588023 : # define STACK_PUSH( imp, im, ia, ib ) do { \
1066 1588023 : stack[ stack_top ].idx_merge_parent = (imp); \
1067 1588023 : stack[ stack_top ]._idx_merge = (im); \
1068 1588023 : stack[ stack_top ].idx_a = (ia); \
1069 1588023 : stack[ stack_top ].idx_b = (ib); \
1070 1588023 : stack_top++; \
1071 1588023 : } while(0)
1072 1588023 : # define STACK_POP( imp, im, ia, ib ) do { \
1073 1588023 : stack_top--; \
1074 1588023 : (imp) = stack[ stack_top ].idx_merge_parent; \
1075 1588023 : (im) = stack[ stack_top ]._idx_merge; \
1076 1588023 : (ia) = stack[ stack_top ].idx_a; \
1077 1588023 : (ib) = stack[ stack_top ].idx_b; \
1078 1588023 : } while(0)
1079 : #endif
1080 :
1081 26130 : TREAP_IDX_T idx_merge_parent = TREAP_IDX_NULL;
1082 :
1083 6378618 : for(;;) {
1084 :
1085 : /* At this point, we are to merge the treaps rooted at idx_a and
1086 : idx_b. The result should be attached to the output treap at node
1087 : idx_merge_parent via the link *idx_merge. (On the first
1088 : iteration, the idx_merge_parent will be idx_null and *_idx_merge
1089 : will be where to store the root of the output treap.) */
1090 :
1091 6378618 : int idx_a_is_null = TREAP_IDX_IS_NULL( idx_a );
1092 6378618 : int idx_b_is_null = TREAP_IDX_IS_NULL( idx_b );
1093 6378618 : if( idx_a_is_null | idx_b_is_null ) {
1094 :
1095 : /* At this point, at least one of the treaps to merge is empty.
1096 : Attach the non-empty treap (if any) accordingly. If both are
1097 : empty, we attach NULL and there is no parent field to update. */
1098 :
1099 3178374 : TREAP_IDX_T idx_tmp;
1100 3178374 : *fd_ptr_if( idx_b_is_null, fd_ptr_if( idx_a_is_null, &idx_tmp,
1101 3178374 : &pool[ idx_a ].TREAP_PARENT ),
1102 3178374 : &pool[ idx_b ].TREAP_PARENT ) = idx_merge_parent;
1103 3178374 : *_idx_merge = (TREAP_IDX_T)fd_ulong_if( idx_b_is_null, (ulong)idx_a, (ulong)idx_b );
1104 :
1105 : # if TREAP_OPTIMIZE_ITERATION
1106 : /* Update the four pointers to insert the range
1107 : idx_a_first and idx_a_last (or b if a is the empty subtree)
1108 : between merged_prev and merged_next. If both are the empty
1109 : subtree, then merged_prev connects directly to merged_next. */
1110 1589286 : *fd_ptr_if( TREAP_IDX_IS_NULL( merged_prev ), &treap_a->first, &pool[ merged_prev ].TREAP_NEXT ) =
1111 : (TREAP_IDX_T)fd_ulong_if( idx_b_is_null, fd_ulong_if( idx_a_is_null, (ulong)merged_next,
1112 : (ulong)idx_a_first ),
1113 : (ulong)idx_b_first );
1114 1589286 : *fd_ptr_if( TREAP_IDX_IS_NULL( merged_next ), &treap_a->last , &pool[ merged_next ].TREAP_PREV ) =
1115 : (TREAP_IDX_T)fd_ulong_if( idx_b_is_null, fd_ulong_if( idx_a_is_null, (ulong)merged_prev,
1116 : (ulong)idx_a_last ),
1117 : (ulong)idx_b_last );
1118 1589286 : *fd_ptr_if( idx_b_is_null, fd_ptr_if( idx_a_is_null, &idx_tmp,
1119 : &pool[ idx_a_first ].TREAP_PREV ),
1120 : &pool[ idx_b_first ].TREAP_PREV ) = merged_prev;
1121 1589286 : *fd_ptr_if( idx_b_is_null, fd_ptr_if( idx_a_is_null, &idx_tmp,
1122 : &pool[ idx_a_last ].TREAP_NEXT ),
1123 : &pool[ idx_b_last ].TREAP_NEXT ) = merged_next;
1124 :
1125 : # endif
1126 : /* Pop the stack to get the next merge to do. If the stack is
1127 : empty, we are done. */
1128 :
1129 3178374 : if( STACK_IS_EMPTY ) break;
1130 : # if TREAP_OPTIMIZE_ITERATION
1131 1576221 : STACK_POP( idx_merge_parent, _idx_merge, idx_a, idx_b, idx_a_first, idx_a_last, idx_b_first, idx_b_last, merged_prev, merged_next );
1132 : # else
1133 1576023 : STACK_POP( idx_merge_parent, _idx_merge, idx_a, idx_b );
1134 1576023 : # endif
1135 1576023 : continue;
1136 3178374 : }
1137 :
1138 : /* If the stack is full, it appears we have exceedingly poorly
1139 : balanced treaps to merge. To mitigate stack overflow risk from
1140 : the recursion, we fall back on a marginally less efficient brute
1141 : force non-recursive algorithm for the merge. FIXME: consider
1142 : doing this post swap for statistical reasons (i.e. the treap with
1143 : the higher root priority is likely to be the larger treap and
1144 : such might have some performance implications for the below
1145 : loop). */
1146 :
1147 3200244 : if( FD_UNLIKELY( STACK_IS_FULL ) ) {
1148 :
1149 : /* Remove elements from B one-by-one and insert them into A.
1150 : O(B lg B) for the removes, O(B lg(A + B)) for the inserts. */
1151 :
1152 : # if TREAP_OPTIMIZE_ITERATION
1153 12000 : TREAP_(t) temp_treap_a = { .ele_max = treap_a->ele_max, .ele_cnt = 0UL, .root = idx_a, .first=idx_a_first, .last=idx_a_last };
1154 12000 : TREAP_(t) temp_treap_b = { .ele_max = treap_b->ele_max, .ele_cnt = 0UL, .root = idx_b, .first=idx_b_first, .last=idx_b_last };
1155 : # else
1156 12000 : TREAP_(t) temp_treap_a = { .ele_max = treap_a->ele_max, .ele_cnt = 0UL, .root = idx_a };
1157 12000 : TREAP_(t) temp_treap_b = { .ele_max = treap_b->ele_max, .ele_cnt = 0UL, .root = idx_b };
1158 : # endif
1159 24000 : pool[ idx_a ].TREAP_PARENT = TREAP_IDX_NULL;
1160 24000 : pool[ idx_b ].TREAP_PARENT = TREAP_IDX_NULL;
1161 1132668 : do {
1162 1132668 : TREAP_IDX_T idx_tmp = temp_treap_b.root;
1163 1132668 : TREAP_(idx_remove)( &temp_treap_b, idx_tmp, pool );
1164 1132668 : TREAP_(idx_insert)( &temp_treap_a, idx_tmp, pool );
1165 1132668 : } while( !TREAP_IDX_IS_NULL( temp_treap_b.root ) );
1166 :
1167 24000 : idx_b = TREAP_IDX_NULL;
1168 24000 : idx_a = temp_treap_a.root;
1169 :
1170 : /* Attach the merged treap to the output */
1171 :
1172 24000 : pool[ idx_a ].TREAP_PARENT = idx_merge_parent;
1173 24000 : *_idx_merge = idx_a;
1174 :
1175 : # if TREAP_OPTIMIZE_ITERATION
1176 12000 : *fd_ptr_if( TREAP_IDX_IS_NULL( merged_prev ), &treap_a->first, &pool[ merged_prev ].TREAP_NEXT ) = temp_treap_a.first;
1177 12000 : *fd_ptr_if( TREAP_IDX_IS_NULL( merged_next ), &treap_a->last, &pool[ merged_next ].TREAP_PREV ) = temp_treap_a.last;
1178 12000 : pool[ temp_treap_a.first ].TREAP_PREV = merged_prev;
1179 12000 : pool[ temp_treap_a.last ].TREAP_NEXT = merged_next;
1180 : # endif
1181 :
1182 : /* Pop the stack to get the next merge to do. If the stack is
1183 : empty, we are done. */
1184 :
1185 24000 : if( STACK_IS_EMPTY ) break;
1186 : # if TREAP_OPTIMIZE_ITERATION
1187 12000 : STACK_POP( idx_merge_parent, _idx_merge, idx_a, idx_b,
1188 12000 : idx_a_first, idx_a_last, idx_b_first, idx_b_last, merged_prev, merged_next );
1189 : # else
1190 12000 : STACK_POP( idx_merge_parent, _idx_merge, idx_a, idx_b );
1191 12000 : # endif
1192 12000 : continue;
1193 24000 : }
1194 :
1195 : /* At this point, we have two non-empty treaps A and B to merge and
1196 : we have stack space so we can use a fast recursive algorithm. If
1197 : A's root priority is below B's root priority, swap A and B. */
1198 :
1199 3176244 : TREAP_IDX_T prio_a = pool[ idx_a ].TREAP_PRIO;
1200 3176244 : TREAP_IDX_T prio_b = pool[ idx_b ].TREAP_PRIO;
1201 3176244 : int swap = (prio_a<prio_b) | ((prio_a==prio_b) & (int)(idx_a ^ idx_b));
1202 3176244 : fd_swap_if( swap, idx_a, idx_b );
1203 : # if TREAP_OPTIMIZE_ITERATION
1204 1588221 : fd_swap_if( swap, idx_a_first, idx_b_first );
1205 1588221 : fd_swap_if( swap, idx_a_last, idx_b_last );
1206 : # endif
1207 :
1208 : /* At this point, we have two non-empty treaps to merge and A's root
1209 : priority is higher than B's root priority. So, we know the root
1210 : of the merged treaps is A's root and can attach it to the output
1211 : treap accordingly. */
1212 :
1213 3176244 : pool[ idx_a ].TREAP_PARENT = idx_merge_parent;
1214 3176244 : *_idx_merge = idx_a;
1215 :
1216 : /* Get A's left and right subtrees */
1217 :
1218 3176244 : TREAP_IDX_T idx_a_left = pool[ idx_a ].TREAP_LEFT;
1219 3176244 : TREAP_IDX_T idx_a_right = pool[ idx_a ].TREAP_RIGHT;
1220 :
1221 : /* Split B by A's root key */
1222 :
1223 3176244 : TREAP_IDX_T idx_b_left;
1224 3176244 : TREAP_IDX_T idx_b_right;
1225 3176244 : TREAP_IDX_T idx_b_left_last;
1226 3176244 : TREAP_IDX_T idx_b_right_first;
1227 3176244 : TREAP_(private_split)( idx_b, &pool[ idx_a ], &idx_b_left, &idx_b_right, &idx_b_left_last, &idx_b_right_first, pool );
1228 :
1229 : # if TREAP_OPTIMIZE_ITERATION
1230 : /* Split the iteration order links in B as well */
1231 1588221 : TREAP_IDX_T dummy;
1232 1588221 : *fd_ptr_if( TREAP_IDX_IS_NULL( idx_b_left_last ), &dummy, &pool[ idx_b_left_last ].TREAP_NEXT ) = TREAP_IDX_NULL;
1233 1588221 : *fd_ptr_if( TREAP_IDX_IS_NULL( idx_b_right_first ), &dummy, &pool[ idx_b_right_first ].TREAP_PREV ) = TREAP_IDX_NULL;
1234 :
1235 : /* The first node in B's left subtree is the first node in B unless
1236 : it is empty. Similarly for B's right subtree. */
1237 1588221 : TREAP_IDX_T idx_b_left_first = (TREAP_IDX_T)fd_ulong_if( TREAP_IDX_IS_NULL( idx_b_left ), TREAP_IDX_NULL, idx_b_first );
1238 1588221 : TREAP_IDX_T idx_b_right_last = (TREAP_IDX_T)fd_ulong_if( TREAP_IDX_IS_NULL( idx_b_right ), TREAP_IDX_NULL, idx_b_last );
1239 : # endif
1240 :
1241 : /* At this point, A's left subtree and B's left split are all keys
1242 : to the left of A's root and A's right subtree. Similarly, B's
1243 : right split are all keys to the right of A's root and A's left
1244 : subtree. We can't do a fast join on A's left/right subtree and B's
1245 : left/right split though as theses are not guaranteed to already
1246 : have their keys distributed as required by join. We instead
1247 : recursively merge the left side and right side. We do the left
1248 : side first and the right side later (making this a cache oblivious
1249 : algorithm too). */
1250 :
1251 : # if TREAP_OPTIMIZE_ITERATION
1252 1588221 : STACK_PUSH( idx_a, &pool[ idx_a ].TREAP_RIGHT, idx_a_right, idx_b_right,
1253 : pool[ idx_a ].TREAP_NEXT, idx_a_last, idx_b_right_first, idx_b_right_last, idx_a, merged_next );
1254 : # else
1255 1588023 : STACK_PUSH( idx_a, &pool[ idx_a ].TREAP_RIGHT, idx_a_right, idx_b_right );
1256 : # endif
1257 :
1258 3176244 : idx_merge_parent = idx_a;
1259 3176244 : _idx_merge = &pool[ idx_a ].TREAP_LEFT;
1260 : # if TREAP_OPTIMIZE_ITERATION
1261 1588221 : idx_a_last = pool[ idx_a ].TREAP_PREV;
1262 : idx_b_first = idx_b_left_first;
1263 : idx_b_last = idx_b_left_last;
1264 : merged_next = idx_a;
1265 : # endif
1266 3176244 : idx_a = idx_a_left;
1267 3176244 : idx_b = idx_b_left;
1268 3176244 : }
1269 :
1270 26130 : treap_a->root = new_root;
1271 26130 : treap_b->root = TREAP_IDX_NULL;
1272 26130 : treap_a->ele_cnt += treap_b->ele_cnt;
1273 26130 : treap_b->ele_cnt = 0UL;
1274 : # if TREAP_OPTIMIZE_ITERATION
1275 13065 : treap_b->first = TREAP_IDX_NULL;
1276 13065 : treap_b->last = TREAP_IDX_NULL;
1277 : # endif
1278 :
1279 26130 : return treap_a;
1280 :
1281 26130 : # undef STACK_POP
1282 26130 : # undef STACK_PUSH
1283 26130 : # undef STACK_IS_FULL
1284 26130 : # undef STACK_IS_EMPTY
1285 26130 : # undef STACK_MAX
1286 26130 : }
1287 :
1288 : TREAP_STATIC TREAP_(fwd_iter_t)
1289 : TREAP_(fwd_iter_init)( TREAP_(t) const * treap,
1290 6128505 : TREAP_T const * pool ) {
1291 : #if TREAP_OPTIMIZE_ITERATION
1292 : (void)pool;
1293 : return treap->first;
1294 : #else
1295 3787455 : ulong i = TREAP_IDX_NULL;
1296 : ulong j = (ulong)treap->root;
1297 18311556 : while( FD_LIKELY( !TREAP_IDX_IS_NULL( j ) ) ) { i = j; j = (ulong)pool[ j ].TREAP_LEFT; }
1298 : return i;
1299 : #endif
1300 6128505 : }
1301 :
1302 : TREAP_STATIC TREAP_(rev_iter_t)
1303 : TREAP_(rev_iter_init)( TREAP_(t) const * treap,
1304 4536228 : TREAP_T const * pool ) {
1305 : #if TREAP_OPTIMIZE_ITERATION
1306 : (void)pool;
1307 : return treap->last;
1308 : #else
1309 3776349 : ulong i = TREAP_IDX_NULL;
1310 : ulong j = (ulong)treap->root;
1311 17945457 : while( FD_LIKELY( !TREAP_IDX_IS_NULL( j ) ) ) { i = j; j = (ulong)pool[ j ].TREAP_RIGHT; }
1312 : return i;
1313 : #endif
1314 4536228 : }
1315 :
1316 : TREAP_STATIC TREAP_(fwd_iter_t)
1317 : TREAP_(fwd_iter_next)( TREAP_(fwd_iter_t) i,
1318 123307053 : TREAP_T const * pool ) {
1319 : #if TREAP_OPTIMIZE_ITERATION
1320 2172 : return pool[ i ].TREAP_NEXT;
1321 : #else
1322 123304881 : ulong r = (ulong)pool[ i ].TREAP_RIGHT;
1323 :
1324 123304881 : if( TREAP_IDX_IS_NULL( r ) ) {
1325 62789109 : ulong p = (ulong)pool[ i ].TREAP_PARENT;
1326 123304821 : while( !TREAP_IDX_IS_NULL( p ) ) {
1327 119577366 : if( i==(ulong)pool[ p ].TREAP_LEFT ) break;
1328 60515712 : i = p;
1329 60515712 : p = (ulong)pool[ p ].TREAP_PARENT;
1330 60515712 : }
1331 62789109 : return p;
1332 62789109 : }
1333 :
1334 60515772 : i = r;
1335 108780810 : for(;;) {
1336 108780810 : ulong l = (ulong)pool[ i ].TREAP_LEFT;
1337 108780810 : if( TREAP_IDX_IS_NULL( l ) ) break;
1338 48265038 : i = l;
1339 48265038 : }
1340 :
1341 60515772 : return i;
1342 : #endif
1343 123307053 : }
1344 :
1345 : TREAP_STATIC TREAP_(rev_iter_t)
1346 : TREAP_(rev_iter_next)( TREAP_(rev_iter_t) i,
1347 242110803 : TREAP_T const * pool ) {
1348 : #if TREAP_OPTIMIZE_ITERATION
1349 120937077 : return pool[ i ].TREAP_PREV;
1350 : #else
1351 121173726 : ulong l = (ulong)pool[ i ].TREAP_LEFT;
1352 :
1353 121173726 : if( TREAP_IDX_IS_NULL( l ) ) {
1354 62467806 : ulong p = (ulong)pool[ i ].TREAP_PARENT;
1355 121172973 : while( !TREAP_IDX_IS_NULL( p ) ) {
1356 117462792 : if( i==(ulong)pool[ p ].TREAP_RIGHT ) break;
1357 58705167 : i = p;
1358 58705167 : p = (ulong)pool[ p ].TREAP_PARENT;
1359 58705167 : }
1360 62467806 : return p;
1361 62467806 : }
1362 :
1363 58705920 : i = l;
1364 107005542 : for(;;) {
1365 107005542 : ulong r = (ulong)pool[ i ].TREAP_RIGHT;
1366 107005542 : if( TREAP_IDX_IS_NULL( r ) ) break;
1367 48299622 : i = r;
1368 48299622 : }
1369 :
1370 58705920 : return i;
1371 : #endif
1372 242110803 : }
1373 :
1374 : TREAP_STATIC int
1375 : TREAP_(verify)( TREAP_(t) const * treap,
1376 30060567 : TREAP_T const * pool ) {
1377 :
1378 7849850331 : # define TREAP_TEST( c ) do { if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: " #c )); return -1; } } while(0)
1379 :
1380 30060567 : TREAP_TEST( treap ); /* Validate local join */
1381 :
1382 30060567 : ulong ele_max = treap->ele_max; TREAP_TEST( ele_max<=TREAP_IDX_NULL ); /* Validate ele_max */
1383 30060567 : ulong ele_cnt = treap->ele_cnt; TREAP_TEST( ele_cnt<=ele_max ); /* Validate ele_cnt */
1384 30060567 : if( ele_max ) TREAP_TEST( pool ); /* Validate ele storage */
1385 :
1386 : /* Find leftmost */
1387 :
1388 30060567 : ulong i = TREAP_IDX_NULL;
1389 30060567 : ulong l = (ulong)treap->root;
1390 :
1391 30060567 : ulong loop_cnt = 0UL;
1392 152399880 : while( FD_LIKELY( !TREAP_IDX_IS_NULL( l ) ) ) {
1393 122339313 : TREAP_TEST( loop_cnt<ele_cnt ); /* Make sure no cycles */
1394 122339313 : TREAP_TEST( l <ele_max ); /* Make sure valid index */
1395 122339313 : i = l;
1396 122339313 : l = (ulong)pool[ l ].TREAP_LEFT;
1397 122339313 : loop_cnt++;
1398 122339313 : }
1399 : #if TREAP_OPTIMIZE_ITERATION
1400 43347 : TREAP_TEST( treap->first==i );
1401 43347 : #endif
1402 :
1403 : /* In-order traverse the treap starting from the leftmost */
1404 :
1405 30060567 : ulong cnt = 0UL; /* Number of elements we've visited so far */
1406 1009304238 : while( FD_LIKELY( !TREAP_IDX_IS_NULL( i ) ) ) {
1407 979243671 : TREAP_TEST( cnt<ele_cnt ); /* Make sure no cycles */
1408 :
1409 : /* At this point, we are visiting element i. We've already visited
1410 : all elements less than i and l is the last element we visited (or
1411 : NULL if i is the first element we are visiting. */
1412 :
1413 979243671 : if( FD_LIKELY( !TREAP_IDX_IS_NULL( l ) ) ) TREAP_TEST( TREAP_(lt)( pool + l, pool + i ) ); /* Make sure ordering valid */
1414 : #if TREAP_OPTIMIZE_ITERATION
1415 : /* Check the l <-> i link */
1416 6839202 : if( FD_LIKELY( !TREAP_IDX_IS_NULL( l ) ) ) TREAP_TEST( pool[ l ].TREAP_NEXT==i );
1417 6839202 : if( FD_LIKELY( !TREAP_IDX_IS_NULL( i ) ) ) TREAP_TEST( pool[ i ].TREAP_PREV==l );
1418 6839202 : #endif
1419 :
1420 :
1421 979243671 : ulong p = (ulong)pool[ i ].TREAP_PARENT;
1422 979243671 : if( FD_LIKELY( !TREAP_IDX_IS_NULL( p ) ) ) {
1423 949618944 : TREAP_TEST( p < ele_max ); /* Make sure valid index */
1424 949618944 : TREAP_TEST( (ulong)pool[ p ].TREAP_PRIO >= (ulong)pool[ i ].TREAP_PRIO ); /* Make sure heap property valid */
1425 949618944 : }
1426 :
1427 : /* Done visiting i, advance to i's successor */
1428 :
1429 979243671 : cnt++;
1430 :
1431 979243671 : l = i;
1432 :
1433 979243671 : ulong r = (ulong)pool[ i ].TREAP_RIGHT;
1434 979243671 : if( TREAP_IDX_IS_NULL( r ) ) {
1435 :
1436 : /* i has no right subtree. Look for first ancestor of i that we
1437 : haven't visited (this will be the first ancestor for which i is
1438 : in the ancestor's left subtree). If there is no such ancestor,
1439 : we are at the rightmost and we are done. */
1440 :
1441 508904307 : loop_cnt = 0UL;
1442 979243671 : while( !TREAP_IDX_IS_NULL( p ) ) {
1443 949618944 : TREAP_TEST( loop_cnt<ele_cnt ); /* Make sure no cycles */
1444 949618944 : TREAP_TEST( p <ele_max ); /* Make sure valid index */
1445 949618944 : if( i==(ulong)pool[ p ].TREAP_LEFT ) break;
1446 470339364 : i = p;
1447 470339364 : p = (ulong)pool[ p ].TREAP_PARENT;
1448 470339364 : loop_cnt++;
1449 470339364 : }
1450 :
1451 508904307 : i = p;
1452 :
1453 508904307 : } else {
1454 :
1455 : /* i has a right subtree. Find the leftmost in this subtree. */
1456 :
1457 470339364 : i = r;
1458 :
1459 470339364 : loop_cnt = 0UL;
1460 856904358 : for(;;) {
1461 856904358 : TREAP_TEST( loop_cnt<ele_cnt ); /* Make sure no cycles */
1462 856904358 : TREAP_TEST( i <ele_max ); /* Make sure valid index */
1463 856904358 : ulong ll = (ulong)pool[ i ].TREAP_LEFT;
1464 856904358 : if( TREAP_IDX_IS_NULL( ll ) ) break;
1465 386564994 : i = ll;
1466 386564994 : loop_cnt++;
1467 386564994 : }
1468 :
1469 470339364 : }
1470 :
1471 979243671 : }
1472 :
1473 : #if TREAP_OPTIMIZE_ITERATION
1474 43347 : TREAP_TEST( treap->last==l );
1475 43347 : #endif
1476 :
1477 30060567 : TREAP_TEST( cnt==ele_cnt ); /* Make sure we visited correct number of elements */
1478 :
1479 30060567 : # undef TREAP_TEST
1480 :
1481 30060567 : return 0;
1482 30060567 : }
1483 :
1484 : #endif
1485 :
1486 : #undef TREAP_IDX_IS_NULL
1487 : #undef TREAP_IDX_NULL
1488 : #undef TREAP_STATIC
1489 :
1490 : #undef TREAP_IMPL_STYLE
1491 : #undef TREAP_NEXT
1492 : #undef TREAP_PREV
1493 : #undef TREAP_OPTIMIZE_ITERATION
1494 : #undef TREAP_PRIO
1495 : #undef TREAP_RIGHT
1496 : #undef TREAP_LEFT
1497 : #undef TREAP_PARENT
1498 : #undef TREAP_IDX_T
1499 : #undef TREAP_LT
1500 : #undef TREAP_CMP
1501 : #undef TREAP_QUERY_T
1502 : #undef TREAP_T
1503 : #undef TREAP_NAME
1504 :
|
