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 choose 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 gives the maximum number of elements the underlying
194 : // linearly addressable storage can support
195 : // mytreap_ele_cnt gives the current number of elements in the treap
196 : // mytreap_{ele_max,ele_cnt} assumes treap is a current local join.
197 : // These might be deprecated in the future.
198 :
199 : ulong mytreap_ele_max( mytreap_t const * treap );
200 : ulong mytreap_ele_cnt( mytreap_t const * treap );
201 :
202 : // mytreap_idx_query finds where q is stored in the treap. Assumes
203 : // treap is a current local join and pool points in the caller's
204 : // address space to the ele_max element storage containing the
205 : // treap elements. Returns [0,ele_max) on success and
206 : // mytreap_idx_null() on failure. Lifetime of the returned idx is
207 : // the lesser of until it is removed or the underlying element
208 : // storage. mytreap_ele_query is the same but returns the location
209 : // in the caller's address space of the found element on success
210 : // and NULL on failure (lifetime of the returned pointer is until
211 : // ele is removed or ele's local lifetime). If there are multiple
212 : // elements matching q, this returns an arbitrary one of them.
213 : // mytreap_ele_query_const is a const correct version.
214 : //
215 : // These operations have HPC implementations and are O(lg N)
216 : // average with an ultra high probability of having a small
217 : // coefficient (i.e. close to algorithmically optimal trees).
218 :
219 : ulong mytreap_idx_query ( mytreap_t const * treap, char const * q, myele_t const * pool );
220 : myele_t * mytreap_ele_query ( mytreap_t * treap, char const * q, myele_t * pool );
221 : myele_t const * mytreap_ele_query_const( mytreap_t const * treap, char const * q, myele_t const * pool );
222 :
223 : // my_treap_idx_{ge,gt} return the index of the smallest element
224 : // in the treap that is {not less,strictly greater} than q.
225 : // my_treap_idx_{le,lt} return the index of the largest element
226 : // in the treap that is {not greater,strictly less} than q.
227 : // If no such element exists, they return idx_null
228 : // If the treap contains duplicate keys, any element with the
229 : // key satisfying the query is returned. E.g. if treap contains
230 : // {7,7,9}, lt(8) may return either of the 2 elements with key 7.
231 :
232 : ulong mytreap_idx_ge( mytreap_t const * treap, TREAP_QUERY_T * q, myele_t const * pool );
233 : ulong mytreap_idx_gt( mytreap_t const * treap, TREAP_QUERY_T * q, myele_t const * pool );
234 : ulong mytreap_idx_le( mytreap_t const * treap, TREAP_QUERY_T * q, myele_t const * pool );
235 : ulong mytreap_idx_lt( mytreap_t const * treap, TREAP_QUERY_T * q, myele_t const * pool );
236 :
237 : // mytreap_idx_{insert,remove} inserts / removes element n/d into
238 : // the treap and returns treap. Assumes treap is a current local
239 : // join, pool points in the caller's address space to the ele_max
240 : // element storage used for treap elements, n/d are in [0,ele_max),
241 : // n/d are currently out of / in the treap. Given these
242 : // assumptions, these cannot fail.
243 : //
244 : // For insert, n's query and prio fields should already be
245 : // populated (i.e. TREAP_LT( ele+n, ele+i ) should return valid
246 : // results before this is called and prio should be a suitable
247 : // value as described above. On return, n and n's queries will be
248 : // in the treap. n's left, right, parent, prio and/or queries
249 : // should not be modified while n is in the treap. Further, the
250 : // caller should not assume n's left, right or parent values are
251 : // stable while n is in the treap. The treap does not care about
252 : // any other fields and these can be modified by the user as
253 : // necessary.
254 : //
255 : // When inserting an element that compares equal (i.e.
256 : // TREAP_LT( x, y )==0 and TREAP_LT( y, x )==0), the newly inserted
257 : // element is treated as if being epsilon larger than all existing
258 : // equal elements. This means that iterating in forward order will
259 : // iterate over equal elements in "time" order, with the one
260 : // inserted first returned first.
261 : //
262 : // For remove, on return d and d's queries are no longer in the
263 : // treap. The caller is free to modify all fields of d as
264 : // necessary.
265 : //
266 : // mytreap_ele_{insert,remove} are the same but n and d point in
267 : // the caller's local address space the element to insert / remove.
268 : //
269 : // These operations have HPC implementations and are O(lg N)
270 : // average with an ultra high probability of having a small
271 : // coefficient (i.e. close to algorithmically optimal trees).
272 :
273 : mytreap_t * mytreap_idx_insert( mytreap_t * treap, ulong n, myele_t * pool );
274 : mytreap_t * mytreap_idx_remove( mytreap_t * treap, ulong d, myele_t * pool );
275 :
276 : mytreap_t * mytreap_ele_insert( mytreap_t * treap, myele_t * n, myele_t * pool );
277 : mytreap_t * mytreap_ele_remove( mytreap_t * treap, myele_t * d, myele_t * pool );
278 :
279 : // mytreap_fwd_iter_{init,done,next,idx,ele,ele_const} provide an
280 : // in-order iterator from smallest to largest value. Typical
281 : // usage:
282 : //
283 : // for( mytreap_fwd_iter_t iter = mytreap_fwd_iter_init( treap, pool );
284 : // !mytreap_fwd_iter_done( iter );
285 : // iter = mytreap_fwd_iter_next( iter, pool ) ) {
286 : // ulong i = mytreap_fwd_iter_idx( iter );
287 : // ... or myele_t * e = mytreap_fwd_iter_ele ( iter, pool );
288 : // ... or myele_t const * e = mytreap_fwd_iter_ele_const( iter, pool );
289 : //
290 : // ... process i (or e) here
291 : //
292 : // ... Do not remove the element the iterator is currently
293 : // ... pointing to, and do not change the element's parent,
294 : // ... left, right, prio or queries here. It is fine to run
295 : // ... queries and other iterations concurrently. Other fields
296 : // ... are free to modify (from the treap's POV, the
297 : // ... application manages concurrency for other fields).
298 : // }
299 : //
300 : // pool is a pointer in the caller's address space to the ele_max
301 : // linearly addressable storage region backing the treap.
302 :
303 : typedef ... mytreap_fwd_iter_t;
304 :
305 : mytreap_fwd_iter_t mytreap_fwd_iter_init ( mytreap_t const * treap, myele_t const * pool );
306 : int mytreap_fwd_iter_done ( mytreap_fwd_iter_t iter );
307 : mytreap_fwd_iter_t mytreap_fwd_iter_next ( mytreap_fwd_iter_t iter, myele_t const * pool );
308 : ulong mytreap_fwd_iter_idx ( mytreap_fwd_iter_t iter );
309 : myele_t * mytreap_fwd_iter_ele ( mytreap_fwd_iter_t iter, myele_t * pool );
310 : myele_t const * mytreap_fwd_iter_ele_const( mytreap_fwd_iter_t iter, myele_t const * pool );
311 :
312 : // mytreap_rev_iter_{init,done,next,idx,ele,ele_const} is the same
313 : // but used when iterating from largest to smallest.
314 :
315 : typedef ... mytreap_rev_iter_t;
316 :
317 : mytreap_rev_iter_t mytreap_rev_iter_init ( mytreap_t const * treap, myele_t const * pool );
318 : int mytreap_rev_iter_done ( mytreap_rev_iter_t iter );
319 : mytreap_rev_iter_t mytreap_rev_iter_next ( mytreap_rev_iter_t iter, myele_t const * pool );
320 : ulong mytreap_rev_iter_idx ( mytreap_rev_iter_t iter );
321 : myele_t * mytreap_rev_iter_ele ( mytreap_rev_iter_t iter, myele_t * pool );
322 : myele_t const * mytreap_rev_iter_ele_const( mytreap_rev_iter_t iter, myele_t const * pool );
323 :
324 : // mytreap_merge merges two treaps backed by the same pool into a
325 : // single treap. If all keys in treap_a and treap_b are distinct,
326 : // merge is equivalent to removing each element from treap_b and
327 : // inserting it into treap_a, but merging the heaps is
328 : // asymptotically slightly better. If there are some duplicate
329 : // elements, they may be interleaved arbitrarily. Returns treap_a,
330 : // which now additionally contains the elements from treap_b.
331 : // Requires that the treap does not use the maximum priority
332 : // element (see the note above about PRIO_MAX).
333 :
334 : mytreap * mytreap_merge( mytreap * treap_a, mytreap * treap_b, myele_t * pool );
335 :
336 : // mytreap_verify returns 0 if the mytreap is not obviously corrupt
337 : // or a -1 (i.e. ERR_INVAL) if it is (logs details). treap is
338 : // current local join to a mytreap. pool is a pointer in the
339 : // caller's address space to the ele_max linearly addressable
340 : // storage region backing the treap.
341 :
342 : int mytreap_verify( mytreap_t const * treap, myele_t const * pool );
343 :
344 : // IMPORTANT SAFETY TIP! queries and iteration can be done
345 : // concurrently by multiple threads distributed arbitrarily over
346 : // multiple processes provided there are no concurrent insert /
347 : // remove operations on the treap and the application manages
348 : // concurrency for fields not managed by the treap.
349 :
350 : You can do this as often as you like within a compilation unit to get
351 : different types of treaps. Variants exist for making separate headers
352 : and implementations for doing libraries and handling multiple
353 : compilation units. Additional options exist as detailed below. */
354 :
355 : /* TREAP_NAME gives the API prefix to use */
356 :
357 : #ifndef TREAP_NAME
358 : #error "Define TREAP_NAME"
359 : #endif
360 :
361 : /* TREAP_T is the treap element type */
362 :
363 : #ifndef TREAP_T
364 : #error "Define TREAP_T"
365 : #endif
366 :
367 : /* TREAP_QUERY_T is the type that is passed to the query function */
368 :
369 : #ifndef TREAP_QUERY_T
370 : #error "Define TREAP_QUERY_T"
371 : #endif
372 :
373 : /* TREAP_CMP compares a TREAP_QUERY_T q with an element e's query
374 : fields and returns a negative/zero/positive int if q is less
375 : than/equal/greater than element e's query fields. Should be a pure
376 : function. */
377 :
378 : #ifndef TREAP_CMP
379 : #error "Define TREAP_CMP"
380 : #endif
381 :
382 : /* TREAP_LT returns 1 if the element e0's query fields are strictly less
383 : element e1's query fields and 0 otherwise. Should be a pure
384 : function. */
385 :
386 : #ifndef TREAP_LT
387 : #error "Define TREAP_LT"
388 : #endif
389 :
390 : /* TREAP_IDX_T is the type used for the fields in the TREAP_T. Should
391 : be a primitive unsigned integer type. Defaults to ulong. A treap
392 : can't use element memory regions that contain more than the maximum
393 : value that can be represented by a TREAP_IDX_T. */
394 :
395 : #ifndef TREAP_IDX_T
396 175689321 : #define TREAP_IDX_T ulong
397 : #endif
398 :
399 : /* TREAP_{PARENT,LEFT,RIGHT,PRIO} is the name the treap element parent /
400 : left / right / prio fields. Defaults to parent / left / right /
401 : prio. */
402 :
403 : #ifndef TREAP_PARENT
404 136861020 : #define TREAP_PARENT parent
405 : #endif
406 :
407 : #ifndef TREAP_LEFT
408 109430117 : #define TREAP_LEFT left
409 : #endif
410 :
411 : #ifndef TREAP_RIGHT
412 82157433 : #define TREAP_RIGHT right
413 : #endif
414 :
415 : #ifndef TREAP_PRIO
416 75797378 : #define TREAP_PRIO prio
417 : #endif
418 :
419 : /* TREAP_OPTIMIZE_ITERATION controls a space/time tradeoff: when
420 : TREAP_OPTIMIZE_ITERATION is set to 1, each element has two additional
421 : fields and insert and delete take slightly longer. However, in
422 : return, iteration in either direction is substantially faster. This
423 : works by essentially threading a doubly-linked list through elements
424 : in iteration order. The default is sets this to 0, meaning that the
425 : next and prev fields are not required. */
426 :
427 : #ifndef TREAP_OPTIMIZE_ITERATION
428 : #define TREAP_OPTIMIZE_ITERATION 0
429 : #endif
430 :
431 : #if TREAP_OPTIMIZE_ITERATION
432 : # ifndef TREAP_NEXT
433 82079677 : # define TREAP_NEXT next
434 : # endif
435 : # ifndef TREAP_PREV
436 78760730 : # define TREAP_PREV prev
437 : # endif
438 : #endif
439 :
440 : /* TREAP_IMPL_STYLE controls what this template should emit.
441 : 0 - local use only
442 : 1 - library header
443 : 2 - library implementation */
444 :
445 : #ifndef TREAP_IMPL_STYLE
446 : #define TREAP_IMPL_STYLE 0
447 : #endif
448 :
449 : /* Implementation *****************************************************/
450 :
451 : #if TREAP_IMPL_STYLE==0
452 : #define TREAP_STATIC static FD_FN_UNUSED
453 : #else
454 : #define TREAP_STATIC
455 : #endif
456 :
457 3861927160 : #define TREAP_IDX_NULL ((ulong)(TREAP_IDX_T)(~0UL))
458 3638008201 : #define TREAP_IDX_IS_NULL( idx ) ((idx)==TREAP_IDX_NULL)
459 :
460 677064527 : #define TREAP_(n) FD_EXPAND_THEN_CONCAT3(TREAP_NAME,_,n)
461 :
462 : /* Verification logs details on failure. The rest only needs fd_bits.h
463 : (consider making logging a compile time option). */
464 :
465 : #include "../log/fd_log.h"
466 :
467 : #if TREAP_IMPL_STYLE!=2 /* need structures, prototypes and inlines */
468 :
469 : /* structures */
470 :
471 : /* TODO: consider eliminating ele_cnt and maybe ele_max fields (less overhead,
472 : faster bulk ops, concurrency options, simpler constructors, etc) */
473 :
474 : struct TREAP_(private) {
475 : ulong ele_max; /* Maximum number of elements in underlying storage, in [0,TREAP_IDX_NULL] */
476 : ulong ele_cnt; /* Current number of elements in treap, in [0,ele_max] */
477 : # if TREAP_OPTIMIZE_ITERATION
478 : TREAP_IDX_T first; /* Index of the left-most treap element, in [0,ele_max) or TREAP_IDX_NULL */
479 : TREAP_IDX_T last; /* Index of the right-most treap element, in [0,ele_max) or TREAP_IDX_NULL */
480 : # endif
481 : TREAP_IDX_T root; /* Index of the root treap element, in [0,ele_max) or TREAP_IDX_NULL */
482 : };
483 :
484 : typedef struct TREAP_(private) TREAP_(t);
485 :
486 : typedef ulong TREAP_(fwd_iter_t);
487 : typedef ulong TREAP_(rev_iter_t);
488 :
489 : FD_PROTOTYPES_BEGIN
490 :
491 : /* prototypes */
492 :
493 : TREAP_STATIC void TREAP_(seed)( TREAP_T * pool, ulong ele_max, ulong seed );
494 :
495 : TREAP_STATIC FD_FN_CONST ulong TREAP_(align) ( void );
496 : TREAP_STATIC FD_FN_CONST ulong TREAP_(footprint)( ulong ele_max );
497 : TREAP_STATIC /**/ void * TREAP_(new) ( void * shmem, ulong ele_max );
498 : TREAP_STATIC /**/ TREAP_(t) * TREAP_(join) ( void * shtreap );
499 : TREAP_STATIC /**/ void * TREAP_(leave) ( TREAP_(t) * treap );
500 : TREAP_STATIC /**/ void * TREAP_(delete) ( void * shtreap );
501 :
502 : TREAP_STATIC FD_FN_PURE ulong TREAP_(idx_query)( TREAP_(t) const * treap, TREAP_QUERY_T q, TREAP_T const * pool );
503 : TREAP_STATIC FD_FN_PURE ulong TREAP_(idx_ge)( TREAP_(t) const * treap, TREAP_QUERY_T q, TREAP_T const * pool );
504 : TREAP_STATIC FD_FN_PURE ulong TREAP_(idx_gt)( TREAP_(t) const * treap, TREAP_QUERY_T q, TREAP_T const * pool );
505 : TREAP_STATIC FD_FN_PURE ulong TREAP_(idx_le)( TREAP_(t) const * treap, TREAP_QUERY_T q, TREAP_T const * pool );
506 : TREAP_STATIC FD_FN_PURE ulong TREAP_(idx_lt)( TREAP_(t) const * treap, TREAP_QUERY_T q, TREAP_T const * pool );
507 :
508 : TREAP_STATIC TREAP_(t) * TREAP_(idx_insert)( TREAP_(t) * treap, ulong n, TREAP_T * pool );
509 : TREAP_STATIC TREAP_(t) * TREAP_(idx_remove)( TREAP_(t) * treap, ulong d, TREAP_T * pool );
510 :
511 : TREAP_STATIC FD_FN_PURE TREAP_(fwd_iter_t) TREAP_(fwd_iter_init)( TREAP_(t) const * treap, TREAP_T const * pool );
512 : TREAP_STATIC FD_FN_PURE TREAP_(rev_iter_t) TREAP_(rev_iter_init)( TREAP_(t) const * treap, TREAP_T const * pool );
513 :
514 : TREAP_STATIC FD_FN_PURE TREAP_(fwd_iter_t) TREAP_(fwd_iter_next)( TREAP_(fwd_iter_t) i, TREAP_T const * pool );
515 : TREAP_STATIC FD_FN_PURE TREAP_(rev_iter_t) TREAP_(rev_iter_next)( TREAP_(rev_iter_t) i, TREAP_T const * pool );
516 :
517 : TREAP_STATIC TREAP_(t) * TREAP_(merge)( TREAP_(t) * treap_a, TREAP_(t) * treap_b, TREAP_T * pool );
518 :
519 : TREAP_STATIC int TREAP_(verify)( TREAP_(t) const * treap, TREAP_T const * pool );
520 :
521 : /* inlines */
522 :
523 168757365 : FD_FN_PURE static inline int TREAP_(cmp)( TREAP_QUERY_T q, TREAP_T const * e ) { return TREAP_CMP( q, e ); }
524 1409135223 : FD_FN_PURE static inline int TREAP_(lt) ( TREAP_T const * e0, TREAP_T const * e1 ) { return TREAP_LT( e0, e1 ); }
525 :
526 692853 : FD_FN_CONST static inline ulong TREAP_(idx_null) ( void ) { return TREAP_IDX_NULL; }
527 3 : FD_FN_CONST static inline TREAP_T * TREAP_(ele_null) ( void ) { return NULL; }
528 3 : FD_FN_CONST static inline TREAP_T const * TREAP_(ele_null_const)( void ) { return NULL; }
529 :
530 2956794 : FD_FN_CONST static inline int TREAP_(idx_is_null)( ulong i ) { return TREAP_IDX_IS_NULL( i ); }
531 1536 : FD_FN_CONST static inline int TREAP_(ele_is_null)( TREAP_T const * e ) { return !e; }
532 :
533 : FD_FN_CONST static inline ulong
534 : TREAP_(idx)( TREAP_T const * e,
535 7507266 : TREAP_T const * pool ) {
536 7507266 : return fd_ulong_if( !!e, (ulong)(e - pool), TREAP_IDX_NULL );
537 7507266 : }
538 :
539 : FD_FN_CONST static inline TREAP_T *
540 : TREAP_(ele)( ulong i,
541 768 : TREAP_T * pool ) {
542 768 : return fd_ptr_if( !TREAP_IDX_IS_NULL( i ), pool + i, NULL );
543 768 : }
544 :
545 : FD_FN_CONST static inline TREAP_T const *
546 : TREAP_(ele_const)( ulong i,
547 768 : TREAP_T const * pool ) {
548 768 : return fd_ptr_if( !TREAP_IDX_IS_NULL( i ), pool + i, NULL );
549 768 : }
550 :
551 : FD_FN_CONST static inline ulong
552 : TREAP_(idx_fast)( TREAP_T const * e,
553 1776 : TREAP_T const * pool ) {
554 1776 : return (ulong)(e - pool);
555 1776 : }
556 :
557 765 : FD_FN_CONST static inline TREAP_T * TREAP_(ele_fast) ( ulong i, TREAP_T * pool ) { return pool + i; }
558 765 : FD_FN_CONST static inline TREAP_T const * TREAP_(ele_fast_const)( ulong i, TREAP_T const * pool ) { return pool + i; }
559 :
560 3858669 : FD_FN_PURE static inline ulong TREAP_(ele_max)( TREAP_(t) const * treap ) { return treap->ele_max; }
561 11298918 : FD_FN_PURE static inline ulong TREAP_(ele_cnt)( TREAP_(t) const * treap ) { return treap->ele_cnt; }
562 :
563 : FD_FN_PURE static inline TREAP_T *
564 : TREAP_(ele_query)( TREAP_(t) const * treap,
565 : TREAP_QUERY_T q,
566 3752880 : TREAP_T * pool ) {
567 3752880 : ulong i = TREAP_(idx_query)( treap, q, pool );
568 3752880 : return fd_ptr_if( !TREAP_IDX_IS_NULL( i ), pool + i, NULL );
569 3752880 : }
570 :
571 : FD_FN_PURE static inline TREAP_T const *
572 : TREAP_(ele_query_const)( TREAP_(t) const * treap,
573 : TREAP_QUERY_T q,
574 3752865 : TREAP_T const * pool ) {
575 3752865 : ulong i = TREAP_(idx_query)( treap, q, pool );
576 3752865 : return fd_ptr_if( !TREAP_IDX_IS_NULL( i ), pool + i, NULL );
577 3752865 : }
578 :
579 : static inline TREAP_(t) *
580 : TREAP_(ele_insert)( TREAP_(t) * treap,
581 : TREAP_T * e,
582 27476729 : TREAP_T * pool ) {
583 27476729 : return TREAP_(idx_insert)( treap, (ulong)(e - pool), pool );
584 27476729 : }
585 :
586 : static inline TREAP_(t) *
587 : TREAP_(ele_remove)( TREAP_(t) * treap,
588 : TREAP_T * e,
589 18049194 : TREAP_T * pool ) {
590 18049194 : return TREAP_(idx_remove)( treap, (ulong)(e - pool), pool );
591 18049194 : }
592 :
593 215090542 : FD_FN_CONST static inline int TREAP_(fwd_iter_done) ( TREAP_(fwd_iter_t) i ) { return TREAP_IDX_IS_NULL( i ); }
594 122905299 : FD_FN_CONST static inline ulong TREAP_(fwd_iter_idx) ( TREAP_(fwd_iter_t) i ) { return i; }
595 167266249 : FD_FN_CONST static inline TREAP_T * TREAP_(fwd_iter_ele) ( TREAP_(fwd_iter_t) i, TREAP_T * pool ) { return pool + i; }
596 122827101 : 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; }
597 :
598 25379853 : FD_FN_CONST static inline int TREAP_(rev_iter_done) ( TREAP_(rev_iter_t) i ) { return TREAP_IDX_IS_NULL( i ); }
599 2043 : FD_FN_CONST static inline ulong TREAP_(rev_iter_idx) ( TREAP_(rev_iter_t) i ) { return i; }
600 24597733 : FD_FN_CONST static inline TREAP_T * TREAP_(rev_iter_ele) ( TREAP_(rev_iter_t) i, TREAP_T * pool ) { return pool + i; }
601 423 : 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; }
602 :
603 : FD_PROTOTYPES_END
604 :
605 : #endif
606 :
607 : #if TREAP_IMPL_STYLE!=1 /* need implementations */
608 :
609 : TREAP_STATIC void
610 : TREAP_(seed)( TREAP_T * pool,
611 : ulong ele_max,
612 6429 : ulong seed ) {
613 7699644 : for( ulong ele_idx=0UL; ele_idx<ele_max; ele_idx++ ) {
614 7693215 : ulong r = fd_ulong_hash( ele_idx ^ seed ) & TREAP_IDX_NULL;
615 7693215 : pool[ ele_idx ].TREAP_PRIO = (TREAP_IDX_T)(r - (ulong)(r==TREAP_IDX_NULL));
616 7693215 : }
617 6429 : }
618 :
619 : TREAP_STATIC FD_FN_CONST ulong
620 5242086 : TREAP_(align)( void ) {
621 5242086 : return alignof(TREAP_(t));
622 5242086 : }
623 :
624 : TREAP_STATIC FD_FN_CONST ulong
625 183 : TREAP_(footprint)( ulong ele_max ) {
626 183 : if( FD_UNLIKELY( ele_max>TREAP_IDX_NULL ) ) return 0UL;
627 180 : return sizeof(TREAP_(t));
628 183 : }
629 :
630 : TREAP_STATIC void *
631 : TREAP_(new)( void * shmem,
632 2661465 : ulong ele_max ) {
633 2661465 : if( !shmem ) {
634 3 : FD_LOG_WARNING(( "NULL shmem" ));
635 3 : return NULL;
636 3 : }
637 :
638 2661462 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, TREAP_(align)() ) ) ) {
639 3 : FD_LOG_WARNING(( "misaligned shmem" ));
640 3 : return NULL;
641 3 : }
642 :
643 2661459 : if( FD_UNLIKELY( ele_max>TREAP_IDX_NULL ) ) {
644 3 : FD_LOG_WARNING(( "ele_max too large" ));
645 3 : return NULL;
646 3 : }
647 :
648 2661456 : TREAP_(t) * treap = (TREAP_(t) *)shmem;
649 :
650 2661456 : treap->ele_max = ele_max;
651 2661456 : treap->ele_cnt = 0UL;
652 2661456 : treap->root = (TREAP_IDX_T)TREAP_IDX_NULL;
653 :
654 : # if TREAP_OPTIMIZE_ITERATION
655 2661336 : treap->first = (TREAP_IDX_T)TREAP_IDX_NULL;
656 2661336 : treap->last = (TREAP_IDX_T)TREAP_IDX_NULL;
657 : # endif
658 :
659 2661456 : return treap;
660 2661459 : }
661 :
662 : TREAP_STATIC TREAP_(t) *
663 2551083 : TREAP_(join)( void * shtreap ) {
664 2551083 : if( FD_UNLIKELY( !shtreap ) ) {
665 3 : FD_LOG_WARNING(( "NULL shtreap" ));
666 3 : return NULL;
667 3 : }
668 :
669 2551080 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shtreap, TREAP_(align)() ) ) ) {
670 3 : FD_LOG_WARNING(( "misaligned shtreap" ));
671 3 : return NULL;
672 3 : }
673 :
674 2551077 : return (TREAP_(t) *)shtreap;
675 2551080 : }
676 :
677 : TREAP_STATIC void *
678 29208 : TREAP_(leave)( TREAP_(t) * treap ) {
679 29208 : if( FD_UNLIKELY( !treap ) ) {
680 3 : FD_LOG_WARNING(( "NULL treap" ));
681 3 : return NULL;
682 3 : }
683 :
684 29205 : return (void *)treap;
685 29208 : }
686 :
687 : TREAP_STATIC void *
688 29211 : TREAP_(delete)( void * shtreap ) {
689 29211 : if( FD_UNLIKELY( !shtreap ) ) {
690 3 : FD_LOG_WARNING(( "NULL shtreap" ));
691 3 : return NULL;
692 3 : }
693 :
694 29208 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shtreap, TREAP_(align)() ) ) ) {
695 3 : FD_LOG_WARNING(( "misaligned shtreap" ));
696 3 : return NULL;
697 3 : }
698 :
699 29205 : return shtreap;
700 29208 : }
701 :
702 : /* Template for binary search operations. Parameterized by:
703 : - name: function suffix (ge/gt/le/lt)
704 : - CMP: the corresponding comparator
705 :
706 : move_cmp is used to decide when to go left.
707 : - If le or lt, go left if c<=0.
708 : - Else, go left if c<0, which is equivalent to c<=-1 */
709 : #define TREAP_CMP_QUERY_IMPL(name, CMP) \
710 : TREAP_STATIC ulong \
711 : TREAP_(idx_##name)( TREAP_(t) const * treap, \
712 : TREAP_QUERY_T q, \
713 15440868 : TREAP_T const * pool ) { \
714 15440868 : int const allow_eq = 0 CMP 0; \
715 15440868 : int const move_cmp = 0 - (1 CMP 0); \
716 15440868 : ulong i = (ulong)treap->root; \
717 15440868 : ulong candidate = TREAP_IDX_NULL; \
718 15440868 : \
719 121235343 : while( FD_LIKELY( !TREAP_IDX_IS_NULL(i) ) ) { \
720 109591257 : ulong l = (ulong)pool[i].TREAP_LEFT; \
721 109591257 : ulong r = (ulong)pool[i].TREAP_RIGHT; \
722 109591257 : int c = TREAP_(cmp)( q, pool + i ); \
723 109591257 : if( allow_eq && FD_UNLIKELY( !c ) ) { \
724 3796782 : candidate = i; \
725 3796782 : break; \
726 3796782 : } \
727 109591257 : \
728 109591257 : candidate = fd_ulong_if( 0 CMP c, i, candidate ); \
729 105794475 : i = fd_ulong_if( c<=move_cmp, l, r ); \
730 105794475 : } \
731 15440868 : return candidate; \
732 15440868 : }
733 :
734 : TREAP_CMP_QUERY_IMPL(ge, >=)
735 : TREAP_CMP_QUERY_IMPL(gt, > )
736 : TREAP_CMP_QUERY_IMPL(le, <=)
737 : TREAP_CMP_QUERY_IMPL(lt, < )
738 :
739 : TREAP_STATIC ulong
740 : TREAP_(idx_query)( TREAP_(t) const * treap,
741 : TREAP_QUERY_T q,
742 11258610 : TREAP_T const * pool ) {
743 11258610 : ulong i = (ulong)treap->root;
744 64847238 : while( FD_LIKELY( !TREAP_IDX_IS_NULL( i ) ) ) { /* Optimize for found */
745 59166108 : ulong l = (ulong)pool[ i ].TREAP_LEFT;
746 59166108 : ulong r = (ulong)pool[ i ].TREAP_RIGHT;
747 59166108 : int c = TREAP_(cmp)( q, pool + i );
748 59166108 : if( FD_UNLIKELY( !c ) ) break; /* Optimize for larger treaps */
749 53588628 : i = fd_ulong_if( c<0, l, r );
750 53588628 : }
751 11258610 : return i;
752 11258610 : }
753 :
754 : TREAP_STATIC TREAP_(t) *
755 : TREAP_(idx_insert)( TREAP_(t) * treap,
756 : ulong n,
757 39101816 : TREAP_T * pool ) {
758 :
759 : # if FD_TMPL_USE_HANDHOLDING
760 : if( FD_UNLIKELY( n>=treap->ele_max ) ) FD_LOG_CRIT(( "index out of bounds" ));
761 : if( FD_UNLIKELY( treap->ele_cnt>=treap->ele_max ) ) FD_LOG_CRIT(( "treap full" ));
762 : # endif
763 :
764 : /* Find leaf where to insert n */
765 :
766 39101816 : TREAP_IDX_T * _p_child = &treap->root;
767 : # if TREAP_OPTIMIZE_ITERATION
768 34685675 : TREAP_IDX_T * _p_pnext = &treap->first; /* pointer to prev node's next idx */
769 34685675 : TREAP_IDX_T * _p_nprev = &treap->last; /* pointer to next node's prev idx */
770 : # endif
771 :
772 39101816 : ulong i = TREAP_IDX_NULL;
773 482784110 : for(;;) {
774 482784110 : ulong j = (ulong)*_p_child;
775 482784110 : if( FD_UNLIKELY( TREAP_IDX_IS_NULL( j ) ) ) break; /* Optimize for large treap */
776 443682294 : i = j;
777 443682294 : int lt = TREAP_(lt)( pool + n, pool + i );
778 443682294 : _p_child = fd_ptr_if( lt, &pool[ i ].TREAP_LEFT, &pool[ i ].TREAP_RIGHT );
779 : # if TREAP_OPTIMIZE_ITERATION
780 385222617 : _p_pnext = fd_ptr_if( lt, _p_pnext, &pool[ i ].TREAP_NEXT );
781 385222617 : _p_nprev = fd_ptr_if( lt, &pool[ i ].TREAP_PREV, _p_nprev );
782 : # endif
783 443682294 : }
784 :
785 : /* Insert n. This might momentarily break the heap property. */
786 :
787 39101816 : pool[ n ].TREAP_PARENT = (TREAP_IDX_T)i;
788 39101816 : pool[ n ].TREAP_LEFT = (TREAP_IDX_T)TREAP_IDX_NULL;
789 39101816 : pool[ n ].TREAP_RIGHT = (TREAP_IDX_T)TREAP_IDX_NULL;
790 39101816 : *_p_child = (TREAP_IDX_T)n;
791 :
792 : # if TREAP_OPTIMIZE_ITERATION
793 34685675 : pool[ n ].TREAP_PREV = *_p_nprev;
794 34685675 : pool[ n ].TREAP_NEXT = *_p_pnext;
795 : *_p_nprev = (TREAP_IDX_T)n;
796 : *_p_pnext = (TREAP_IDX_T)n;
797 : # endif
798 :
799 : /* Bubble n up until the heap property is restored. */
800 :
801 39101816 : ulong n_prio = (ulong)pool[ n ].TREAP_PRIO;
802 80456923 : while( !TREAP_IDX_IS_NULL( i ) ) {
803 63358456 : ulong i_prio = (ulong)pool[ i ].TREAP_PRIO;
804 :
805 63358456 : int heap_intact = (n_prio<i_prio) | ((n_prio==i_prio) & (!((n ^ i) & 1UL))); /* Flip coin on equal priority */
806 63358456 : if( heap_intact ) break;
807 :
808 : /* Get i's parent (if any) and parent's link to i (tree root link if no parent) */
809 :
810 41355107 : ulong p = (ulong)pool[ i ].TREAP_PARENT;
811 :
812 41355107 : TREAP_IDX_T * _t0 = fd_ptr_if( TREAP_IDX_IS_NULL( p ), &treap->root, &pool[ p ].TREAP_LEFT );
813 41355107 : /**/ _p_child = fd_ptr_if( i==(ulong)*_t0, _t0, &pool[ p ].TREAP_RIGHT );
814 :
815 : /* Get n's child (if any) that will become i's child */
816 :
817 41355107 : int n_is_left_child = (n==(ulong)pool[ i ].TREAP_LEFT);
818 41355107 : TREAP_IDX_T * _n_child = fd_ptr_if( n_is_left_child, &pool[ n ].TREAP_RIGHT, &pool[ n ].TREAP_LEFT );
819 41355107 : ulong j = (ulong)*_n_child;
820 :
821 : /* Make n child of p (or the root if no parent) */
822 :
823 41355107 : *_p_child = (TREAP_IDX_T)n;
824 41355107 : pool[ n ].TREAP_PARENT = (TREAP_IDX_T)p;
825 :
826 : /* Make i child of n */
827 :
828 41355107 : *_n_child = (TREAP_IDX_T)i;
829 41355107 : pool[ i ].TREAP_PARENT = (TREAP_IDX_T)n;
830 :
831 : /* Make j (if present) child of i */
832 :
833 41355107 : TREAP_IDX_T dummy;
834 41355107 : *fd_ptr_if( n_is_left_child, &pool[ i ].TREAP_LEFT, &pool[ i ].TREAP_RIGHT ) = (TREAP_IDX_T)j;
835 41355107 : *fd_ptr_if( TREAP_IDX_IS_NULL( j ), &dummy, &pool[ j ].TREAP_PARENT ) = (TREAP_IDX_T)i;
836 :
837 : /* Keep bubbling up */
838 :
839 41355107 : i = p;
840 41355107 : }
841 :
842 39101816 : treap->ele_cnt++;
843 39101816 : return treap;
844 39101816 : }
845 :
846 : TREAP_(t) *
847 : TREAP_(idx_remove)( TREAP_(t) * treap,
848 : ulong d,
849 39062004 : TREAP_T * pool ) {
850 : # if FD_TMPL_USE_HANDHOLDING
851 : if( FD_UNLIKELY( (d>=treap->ele_max) ) ) FD_LOG_CRIT(( "index out of bounds" ));
852 : if( FD_UNLIKELY( (treap->ele_cnt<1) ) ) FD_LOG_CRIT(( "index out of bounds" ));
853 : # endif
854 :
855 : /* Make a hole at d */
856 :
857 39062004 : ulong p = (ulong)pool[ d ].TREAP_PARENT;
858 39062004 : ulong l = (ulong)pool[ d ].TREAP_LEFT;
859 39062004 : ulong r = (ulong)pool[ d ].TREAP_RIGHT;
860 :
861 39062004 : TREAP_IDX_T * _t0 = fd_ptr_if( TREAP_IDX_IS_NULL( p ), &treap->root, &pool[ p ].TREAP_LEFT );
862 39062004 : TREAP_IDX_T * _p_child = fd_ptr_if( d==(ulong)*_t0, _t0, &pool[ p ].TREAP_RIGHT );
863 :
864 : # if TREAP_OPTIMIZE_ITERATION
865 31331643 : TREAP_IDX_T prev = pool[ d ].TREAP_PREV;
866 31331643 : TREAP_IDX_T next = pool[ d ].TREAP_NEXT;
867 31331643 : TREAP_IDX_T * _pnext = fd_ptr_if( TREAP_IDX_IS_NULL( prev ), &treap->first, &pool[ prev ].TREAP_NEXT );
868 31331643 : TREAP_IDX_T * _nprev = fd_ptr_if( TREAP_IDX_IS_NULL( next ), &treap->last, &pool[ next ].TREAP_PREV );
869 : *_pnext = next;
870 : *_nprev = prev;
871 : # endif
872 :
873 42139246 : for(;;) {
874 :
875 : /* At this point, we have a hole to fill at d:
876 :
877 : p is the hole's parent (if any)
878 : l is the hole's left subtree (if any)
879 : r is the hole's right subtree (if any)
880 :
881 : p_child points to the link from p to hole (if the hole has a
882 : parent) and to the treap root link otherwise.
883 :
884 : If there is neither a left subtree nor a right subtree, we are
885 : done. If there is a left/right subtree, we fill the hole with
886 : the right/left subtree and we are done. */
887 :
888 42139246 : int is_null_left = TREAP_IDX_IS_NULL( l );
889 42139246 : int is_null_right = TREAP_IDX_IS_NULL( r );
890 42139246 : if( FD_LIKELY( is_null_left | is_null_right ) ) { /* Most nodes near bottom */
891 39062004 : TREAP_IDX_T dummy;
892 39062004 : *_p_child = (TREAP_IDX_T)fd_ulong_if( !is_null_left, l, r );
893 39062004 : *( fd_ptr_if( !is_null_left, &pool[ l ].TREAP_PARENT,
894 39062004 : fd_ptr_if( !is_null_right, &pool[ r ].TREAP_PARENT, &dummy ) ) ) = (TREAP_IDX_T)p;
895 39062004 : break;
896 39062004 : }
897 :
898 : /* The hole has two subtrees. We bubble the hole down one, fill the
899 : hole with the root of the subtree that will preserve the heap
900 : priority up to the hole (flipping a coin on ties). Note we don't
901 : need to update any links to/from d as we will be getting rid of
902 : all links / from d. */
903 :
904 3077242 : ulong l_prio = (ulong)pool[ l ].TREAP_PRIO;
905 3077242 : ulong r_prio = (ulong)pool[ r ].TREAP_PRIO;
906 :
907 3077242 : int promote_left = (l_prio>r_prio) | ((l_prio==r_prio) & (!((p ^ d) & 1UL)));
908 :
909 3077242 : ulong c = fd_ulong_if( promote_left, l, r );
910 :
911 3077242 : *_p_child = (TREAP_IDX_T)c;
912 3077242 : pool[ c ].TREAP_PARENT = (TREAP_IDX_T)p;
913 :
914 3077242 : _p_child = fd_ptr_if ( promote_left, &pool[ l ].TREAP_RIGHT, &pool[ r ].TREAP_LEFT );
915 3077242 : p = c;
916 3077242 : l = fd_ulong_if( promote_left, pool[ l ].TREAP_RIGHT, l );
917 3077242 : r = fd_ulong_if( promote_left, r, pool[ r ].TREAP_LEFT );
918 :
919 3077242 : }
920 :
921 39062004 : treap->ele_cnt--;
922 39062004 : return treap;
923 39062004 : }
924 :
925 : static inline void
926 : TREAP_(private_split)( TREAP_IDX_T idx_node, /* Tree to split */
927 : TREAP_T * key, /* Element whose key is not in the treap rooted at idx_node */
928 : TREAP_IDX_T * _idx_left, /* Where to store the left tree root */
929 : TREAP_IDX_T * _idx_right, /* Where to store the right tree root */
930 : TREAP_IDX_T * _idx_last_left, /* Where to store the last (in BST order) element of the new left tree */
931 : TREAP_IDX_T * _idx_first_right, /* Where to store the first(in BST order) element in the new right tree */
932 3204168 : TREAP_T * pool ) { /* Underlying pool */
933 :
934 3204168 : TREAP_IDX_T idx_parent_left = TREAP_IDX_NULL;
935 3204168 : TREAP_IDX_T idx_parent_right = TREAP_IDX_NULL;
936 3204168 : *_idx_last_left = TREAP_IDX_NULL;
937 3204168 : *_idx_first_right = TREAP_IDX_NULL;
938 :
939 6622920 : while( !TREAP_IDX_IS_NULL( idx_node ) ) {
940 :
941 : /* At this point we have a non-empty subtree to split whose root is
942 : node and we should attach the left and right split trees at
943 : idx_parent_left / *_idx_left and idx_parent_right / *_idx_right.
944 : (On the first attach, idx_parent_left/right will be idx_null and
945 : *_idx_left / *_idx_right are locations where to store the output
946 : split treaps.) */
947 :
948 3418752 : if( TREAP_(lt)( &pool[ idx_node ], key ) ) {
949 :
950 : /* node is left of key which, by the BST property, means all
951 : elements in node's left subtree are also left of key. We don't
952 : know if node's right subtree contains any elements left of key.
953 : If it does, these elements should be attached to node's right
954 : subtree to preserve the BST property of the left split.
955 :
956 : As such, we attach node and node's left subtree to the
957 : left split, update the attach point for the left split to
958 : node's right subtree and then recurse on the node's right
959 : subtree.
960 :
961 : Note that this operation does not do any reordering of
962 : priorities (e.g. if element B was a descendant of element A
963 : before the split and both B and A belong on the left split, B
964 : will still be a descendant of A). */
965 :
966 : /* Attach node and node's left subtree to the left split */
967 3237015 : pool[ idx_node ].TREAP_PARENT = idx_parent_left;
968 3237015 : *_idx_left = idx_node;
969 :
970 : /* The next left split attach is node's right child */
971 3237015 : idx_parent_left = idx_node;
972 3237015 : _idx_left = &pool[ idx_node ].TREAP_RIGHT;
973 :
974 : /* If everything in the right subtree is to the right of the key,
975 : this is the last node on the left. */
976 3237015 : *_idx_last_left = idx_node;
977 :
978 : /* Recurse on the right subtree */
979 3237015 : idx_node = pool[ idx_node ].TREAP_RIGHT;
980 :
981 3237015 : } else { /* Mirror image of the above */
982 :
983 181737 : pool[ idx_node ].TREAP_PARENT = idx_parent_right;
984 181737 : *_idx_right = idx_node;
985 :
986 181737 : idx_parent_right = idx_node;
987 181737 : _idx_right = &pool[ idx_node ].TREAP_LEFT;
988 :
989 181737 : *_idx_first_right = idx_node;
990 :
991 181737 : idx_node = pool[ idx_node ].TREAP_LEFT;
992 :
993 181737 : }
994 3418752 : }
995 :
996 : /* At this point, we have an empty tree to split */
997 :
998 3204168 : *_idx_left = TREAP_IDX_NULL;
999 3204168 : *_idx_right = TREAP_IDX_NULL;
1000 3204168 : }
1001 :
1002 : #if !TREAP_OPTIMIZE_ITERATION
1003 : static inline void
1004 : TREAP_(private_join)( TREAP_IDX_T idx_left, /* Root of the left treap */
1005 : TREAP_IDX_T idx_right, /* Root of the right treap, keys in left treap < keys in right treap */
1006 : TREAP_IDX_T * _idx_join, /* Where to store root of joined treaps */
1007 0 : TREAP_T * pool ) { /* Underlying pool */
1008 0 :
1009 0 : TREAP_IDX_T idx_join_parent = TREAP_IDX_NULL;
1010 0 :
1011 0 : for(;;) {
1012 0 :
1013 0 : /* TODO: consolidate these cases into a single branch. */
1014 0 :
1015 0 : if( TREAP_IDX_IS_NULL( idx_left ) ) { /* Left treap empty */
1016 0 : /* join is the right treap (or empty if both left and right empty) */
1017 0 : if( !TREAP_IDX_IS_NULL( idx_right ) ) pool[ idx_right ].TREAP_PARENT = idx_join_parent;
1018 0 : *_idx_join = idx_right;
1019 0 : break;
1020 0 : }
1021 0 :
1022 0 : if( TREAP_IDX_IS_NULL( idx_right ) ) { /* Right treap empty */
1023 0 : /* join is the left treap */
1024 0 : pool[ idx_left ].TREAP_PARENT = idx_join_parent;
1025 0 : *_idx_join = idx_left;
1026 0 : break;
1027 0 : }
1028 0 :
1029 0 : /* At this point, we have two non empty treaps to join and elements
1030 0 : in the left treap have keys before elements in the right treap. */
1031 0 :
1032 0 : ulong prio_left = (ulong)pool[ idx_left ].TREAP_PRIO;
1033 0 : ulong prio_right = (ulong)pool[ idx_right ].TREAP_PRIO;
1034 0 : if( (prio_left>prio_right) | ((prio_left==prio_right) & (int)(idx_left^idx_right)) ) {
1035 0 :
1036 0 : /* At this point, the left treap root has higher priority than the
1037 0 : right treap root. So we attach the left treap root and left
1038 0 : treap left subtree to the join to preserve the heap property.
1039 0 : We know that the left treap right subtree is to the right of
1040 0 : these and that the right treap is to the right of that. So our
1041 0 : next join attachment point should be at the left treap right
1042 0 : subtree and we should recurse on the left treap right subtree
1043 0 : and the right treap. */
1044 0 :
1045 0 : /* Attach left's root and left's left subtree to the join */
1046 0 : pool[ idx_left ].TREAP_PARENT = idx_join_parent;
1047 0 : *_idx_join = idx_left;
1048 0 :
1049 0 : /* The next join attach should be left's right subtree */
1050 0 : idx_join_parent = idx_left;
1051 0 : _idx_join = &pool[ idx_left ].TREAP_LEFT;
1052 0 :
1053 0 : /* Recurse on left's right subtree and right treap */
1054 0 : idx_left = pool[ idx_left ].TREAP_RIGHT;
1055 0 :
1056 0 : } else { /* Mirror image of the above */
1057 0 :
1058 0 : pool[ idx_right ].TREAP_PARENT = idx_join_parent;
1059 0 : *_idx_join = idx_right;
1060 0 :
1061 0 : idx_join_parent = idx_right;
1062 0 : _idx_join = &pool[ idx_right ].TREAP_RIGHT;
1063 0 :
1064 0 : idx_right = pool[ idx_right ].TREAP_LEFT;
1065 0 :
1066 0 : }
1067 0 : }
1068 0 : }
1069 : #endif
1070 :
1071 : TREAP_(t) *
1072 : TREAP_(merge)( TREAP_(t) * treap_a,
1073 : TREAP_(t) * treap_b,
1074 26430 : TREAP_T * pool ) {
1075 :
1076 26430 : TREAP_IDX_T idx_a = treap_a->root;
1077 26430 : TREAP_IDX_T idx_b = treap_b->root;
1078 26430 : TREAP_IDX_T new_root = TREAP_IDX_NULL;
1079 26430 : TREAP_IDX_T * _idx_merge = &new_root;
1080 :
1081 : # if TREAP_OPTIMIZE_ITERATION
1082 : /* Invariant: idx_{a,b}_{first,last} is the index of the first/last
1083 : node in key order in the subtree rooted at idx_a/idx_b. */
1084 13065 : TREAP_IDX_T idx_a_first = treap_a->first;
1085 13065 : TREAP_IDX_T idx_a_last = treap_a->last;
1086 13065 : TREAP_IDX_T idx_b_first = treap_b->first;
1087 13065 : TREAP_IDX_T idx_b_last = treap_b->last;
1088 :
1089 : /* merged_{prev,next} are the nodes immediately before/after the
1090 : merged subtree. If these are IDX_NULL, then treap_a->first/last
1091 : should be updated instead. */
1092 13065 : TREAP_IDX_T merged_prev = TREAP_IDX_NULL;
1093 13065 : TREAP_IDX_T merged_next = TREAP_IDX_NULL;
1094 : # endif
1095 :
1096 26430 : # define STACK_MAX (128UL)
1097 :
1098 26430 : struct { TREAP_IDX_T idx_merge_parent; TREAP_IDX_T * _idx_merge; TREAP_IDX_T idx_a; TREAP_IDX_T idx_b;
1099 : # if TREAP_OPTIMIZE_ITERATION
1100 : TREAP_IDX_T idx_a_first, idx_a_last, idx_b_first, idx_b_last;
1101 : TREAP_IDX_T merged_prev, merged_next;
1102 : # endif
1103 26430 : } stack[ STACK_MAX ];
1104 26430 : ulong stack_top = 0UL;
1105 :
1106 3230598 : # define STACK_IS_EMPTY (!stack_top)
1107 26430 : # define STACK_IS_FULL (stack_top>=STACK_MAX)
1108 :
1109 : # if TREAP_OPTIMIZE_ITERATION
1110 1588032 : # define STACK_PUSH( imp, im, ia, ib, iaf, ial, ibf, ibl, mp, mn ) do { \
1111 1588032 : stack[ stack_top ].idx_merge_parent = (imp); \
1112 1588032 : stack[ stack_top ]._idx_merge = (im); \
1113 1588032 : stack[ stack_top ].idx_a = (ia); \
1114 1588032 : stack[ stack_top ].idx_b = (ib); \
1115 1588032 : stack[ stack_top ].idx_a_first = (iaf); \
1116 1588032 : stack[ stack_top ].idx_a_last = (ial); \
1117 1588032 : stack[ stack_top ].idx_b_first = (ibf); \
1118 1588032 : stack[ stack_top ].idx_b_last = (ibl); \
1119 1588032 : stack[ stack_top ].merged_prev = (mp); \
1120 1588032 : stack[ stack_top ].merged_next = (mn); \
1121 1588032 : stack_top++; \
1122 1588032 : } while(0)
1123 1588032 : # define STACK_POP( imp, im, ia, ib, iaf, ial, ibf, ibl, mp, mn ) do { \
1124 1588032 : stack_top--; \
1125 1588032 : (imp) = stack[ stack_top ].idx_merge_parent; \
1126 1588032 : (im) = stack[ stack_top ]._idx_merge; \
1127 1588032 : (ia) = stack[ stack_top ].idx_a; \
1128 1588032 : (ib) = stack[ stack_top ].idx_b; \
1129 1588032 : (iaf) = stack[ stack_top ].idx_a_first; \
1130 1588032 : (ial) = stack[ stack_top ].idx_a_last; \
1131 1588032 : (ibf) = stack[ stack_top ].idx_b_first; \
1132 1588032 : (ibl) = stack[ stack_top ].idx_b_last; \
1133 1588032 : (mp) = stack[ stack_top ].merged_prev; \
1134 1588032 : (mn) = stack[ stack_top ].merged_next; \
1135 1588032 : } while(0)
1136 : # else
1137 1616136 : # define STACK_PUSH( imp, im, ia, ib ) do { \
1138 1616136 : stack[ stack_top ].idx_merge_parent = (imp); \
1139 1616136 : stack[ stack_top ]._idx_merge = (im); \
1140 1616136 : stack[ stack_top ].idx_a = (ia); \
1141 1616136 : stack[ stack_top ].idx_b = (ib); \
1142 1616136 : stack_top++; \
1143 1616136 : } while(0)
1144 1616136 : # define STACK_POP( imp, im, ia, ib ) do { \
1145 1616136 : stack_top--; \
1146 1616136 : (imp) = stack[ stack_top ].idx_merge_parent; \
1147 1616136 : (im) = stack[ stack_top ]._idx_merge; \
1148 1616136 : (ia) = stack[ stack_top ].idx_a; \
1149 1616136 : (ib) = stack[ stack_top ].idx_b; \
1150 1616136 : } while(0)
1151 : # endif
1152 :
1153 26430 : TREAP_IDX_T idx_merge_parent = TREAP_IDX_NULL;
1154 :
1155 6434766 : for(;;) {
1156 :
1157 : /* At this point, we are to merge the treaps rooted at idx_a and
1158 : idx_b. The result should be attached to the output treap at node
1159 : idx_merge_parent via the link *idx_merge. (On the first
1160 : iteration, the idx_merge_parent will be idx_null and *_idx_merge
1161 : will be where to store the root of the output treap.) */
1162 :
1163 6434766 : int idx_a_is_null = TREAP_IDX_IS_NULL( idx_a );
1164 6434766 : int idx_b_is_null = TREAP_IDX_IS_NULL( idx_b );
1165 6434766 : if( idx_a_is_null | idx_b_is_null ) {
1166 :
1167 : /* At this point, at least one of the treaps to merge is empty.
1168 : Attach the non-empty treap (if any) accordingly. If both are
1169 : empty, we attach NULL and there is no parent field to update. */
1170 :
1171 3206598 : TREAP_IDX_T idx_tmp;
1172 3206598 : *fd_ptr_if( idx_b_is_null, fd_ptr_if( idx_a_is_null, &idx_tmp,
1173 3206598 : &pool[ idx_a ].TREAP_PARENT ),
1174 3206598 : &pool[ idx_b ].TREAP_PARENT ) = idx_merge_parent;
1175 3206598 : *_idx_merge = (TREAP_IDX_T)fd_ulong_if( idx_b_is_null, (ulong)idx_a, (ulong)idx_b );
1176 :
1177 : # if TREAP_OPTIMIZE_ITERATION
1178 : /* Update the four pointers to insert the range
1179 : idx_a_first and idx_a_last (or b if a is the empty subtree)
1180 : between merged_prev and merged_next. If both are the empty
1181 : subtree, then merged_prev connects directly to merged_next. */
1182 1589097 : *fd_ptr_if( TREAP_IDX_IS_NULL( merged_prev ), &treap_a->first, &pool[ merged_prev ].TREAP_NEXT ) =
1183 : (TREAP_IDX_T)fd_ulong_if( idx_b_is_null, fd_ulong_if( idx_a_is_null, (ulong)merged_next,
1184 : (ulong)idx_a_first ),
1185 : (ulong)idx_b_first );
1186 1589097 : *fd_ptr_if( TREAP_IDX_IS_NULL( merged_next ), &treap_a->last , &pool[ merged_next ].TREAP_PREV ) =
1187 : (TREAP_IDX_T)fd_ulong_if( idx_b_is_null, fd_ulong_if( idx_a_is_null, (ulong)merged_prev,
1188 : (ulong)idx_a_last ),
1189 : (ulong)idx_b_last );
1190 1589097 : *fd_ptr_if( idx_b_is_null, fd_ptr_if( idx_a_is_null, &idx_tmp,
1191 : &pool[ idx_a_first ].TREAP_PREV ),
1192 : &pool[ idx_b_first ].TREAP_PREV ) = merged_prev;
1193 1589097 : *fd_ptr_if( idx_b_is_null, fd_ptr_if( idx_a_is_null, &idx_tmp,
1194 : &pool[ idx_a_last ].TREAP_NEXT ),
1195 : &pool[ idx_b_last ].TREAP_NEXT ) = merged_next;
1196 :
1197 : # endif
1198 : /* Pop the stack to get the next merge to do. If the stack is
1199 : empty, we are done. */
1200 :
1201 3206598 : if( STACK_IS_EMPTY ) break;
1202 : # if TREAP_OPTIMIZE_ITERATION
1203 1576032 : 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 );
1204 : # else
1205 1604136 : STACK_POP( idx_merge_parent, _idx_merge, idx_a, idx_b );
1206 1604136 : # endif
1207 1604136 : continue;
1208 3206598 : }
1209 :
1210 : /* If the stack is full, it appears we have exceedingly poorly
1211 : balanced treaps to merge. To mitigate stack overflow risk from
1212 : the recursion, we fall back on a marginally less efficient brute
1213 : force non-recursive algorithm for the merge. FIXME: consider
1214 : doing this post swap for statistical reasons (i.e. the treap with
1215 : the higher root priority is likely to be the larger treap and
1216 : such might have some performance implications for the below
1217 : loop). */
1218 :
1219 3228168 : if( FD_UNLIKELY( STACK_IS_FULL ) ) {
1220 :
1221 : /* Remove elements from B one-by-one and insert them into A.
1222 : O(B lg B) for the removes, O(B lg(A + B)) for the inserts. The
1223 : value for ele_cnt in temp_treap_b is a dummy value to avoid
1224 : handholding checks from spuriously firing. */
1225 :
1226 : # if TREAP_OPTIMIZE_ITERATION
1227 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 };
1228 12000 : TREAP_(t) temp_treap_b = { .ele_max = treap_b->ele_max, .ele_cnt = treap_b->ele_max, .root = idx_b, .first=idx_b_first, .last=idx_b_last };
1229 : # else
1230 12000 : TREAP_(t) temp_treap_a = { .ele_max = treap_a->ele_max, .ele_cnt = 0UL, .root = idx_a };
1231 12000 : TREAP_(t) temp_treap_b = { .ele_max = treap_b->ele_max, .ele_cnt = treap_b->ele_max, .root = idx_b };
1232 : # endif
1233 24000 : pool[ idx_a ].TREAP_PARENT = TREAP_IDX_NULL;
1234 24000 : pool[ idx_b ].TREAP_PARENT = TREAP_IDX_NULL;
1235 1130412 : do {
1236 1130412 : TREAP_IDX_T idx_tmp = temp_treap_b.root;
1237 1130412 : TREAP_(idx_remove)( &temp_treap_b, idx_tmp, pool );
1238 1130412 : TREAP_(idx_insert)( &temp_treap_a, idx_tmp, pool );
1239 1130412 : } while( !TREAP_IDX_IS_NULL( temp_treap_b.root ) );
1240 :
1241 24000 : idx_b = TREAP_IDX_NULL;
1242 24000 : idx_a = temp_treap_a.root;
1243 :
1244 : /* Attach the merged treap to the output */
1245 :
1246 24000 : pool[ idx_a ].TREAP_PARENT = idx_merge_parent;
1247 24000 : *_idx_merge = idx_a;
1248 :
1249 : # if TREAP_OPTIMIZE_ITERATION
1250 12000 : *fd_ptr_if( TREAP_IDX_IS_NULL( merged_prev ), &treap_a->first, &pool[ merged_prev ].TREAP_NEXT ) = temp_treap_a.first;
1251 12000 : *fd_ptr_if( TREAP_IDX_IS_NULL( merged_next ), &treap_a->last, &pool[ merged_next ].TREAP_PREV ) = temp_treap_a.last;
1252 12000 : pool[ temp_treap_a.first ].TREAP_PREV = merged_prev;
1253 12000 : pool[ temp_treap_a.last ].TREAP_NEXT = merged_next;
1254 : # endif
1255 :
1256 : /* Pop the stack to get the next merge to do. If the stack is
1257 : empty, we are done. */
1258 :
1259 24000 : if( STACK_IS_EMPTY ) break;
1260 : # if TREAP_OPTIMIZE_ITERATION
1261 12000 : STACK_POP( idx_merge_parent, _idx_merge, idx_a, idx_b,
1262 12000 : idx_a_first, idx_a_last, idx_b_first, idx_b_last, merged_prev, merged_next );
1263 : # else
1264 12000 : STACK_POP( idx_merge_parent, _idx_merge, idx_a, idx_b );
1265 12000 : # endif
1266 12000 : continue;
1267 24000 : }
1268 :
1269 : /* At this point, we have two non-empty treaps A and B to merge and
1270 : we have stack space so we can use a fast recursive algorithm. If
1271 : A's root priority is below B's root priority, swap A and B. */
1272 :
1273 3204168 : TREAP_IDX_T prio_a = pool[ idx_a ].TREAP_PRIO;
1274 3204168 : TREAP_IDX_T prio_b = pool[ idx_b ].TREAP_PRIO;
1275 3204168 : int swap = (prio_a<prio_b) | ((prio_a==prio_b) & (int)(idx_a ^ idx_b));
1276 3204168 : fd_swap_if( swap, idx_a, idx_b );
1277 : # if TREAP_OPTIMIZE_ITERATION
1278 1588032 : fd_swap_if( swap, idx_a_first, idx_b_first );
1279 1588032 : fd_swap_if( swap, idx_a_last, idx_b_last );
1280 : # endif
1281 :
1282 : /* At this point, we have two non-empty treaps to merge and A's root
1283 : priority is higher than B's root priority. So, we know the root
1284 : of the merged treaps is A's root and can attach it to the output
1285 : treap accordingly. */
1286 :
1287 3204168 : pool[ idx_a ].TREAP_PARENT = idx_merge_parent;
1288 3204168 : *_idx_merge = idx_a;
1289 :
1290 : /* Get A's left and right subtrees */
1291 :
1292 3204168 : TREAP_IDX_T idx_a_left = pool[ idx_a ].TREAP_LEFT;
1293 3204168 : TREAP_IDX_T idx_a_right = pool[ idx_a ].TREAP_RIGHT;
1294 :
1295 : /* Split B by A's root key */
1296 :
1297 3204168 : TREAP_IDX_T idx_b_left;
1298 3204168 : TREAP_IDX_T idx_b_right;
1299 3204168 : TREAP_IDX_T idx_b_left_last;
1300 3204168 : TREAP_IDX_T idx_b_right_first;
1301 3204168 : TREAP_(private_split)( idx_b, &pool[ idx_a ], &idx_b_left, &idx_b_right, &idx_b_left_last, &idx_b_right_first, pool );
1302 :
1303 : # if TREAP_OPTIMIZE_ITERATION
1304 : /* Split the iteration order links in B as well */
1305 1588032 : TREAP_IDX_T dummy;
1306 1588032 : *fd_ptr_if( TREAP_IDX_IS_NULL( idx_b_left_last ), &dummy, &pool[ idx_b_left_last ].TREAP_NEXT ) = TREAP_IDX_NULL;
1307 1588032 : *fd_ptr_if( TREAP_IDX_IS_NULL( idx_b_right_first ), &dummy, &pool[ idx_b_right_first ].TREAP_PREV ) = TREAP_IDX_NULL;
1308 :
1309 : /* The first node in B's left subtree is the first node in B unless
1310 : it is empty. Similarly for B's right subtree. */
1311 1588032 : 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 );
1312 1588032 : 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 );
1313 : # endif
1314 :
1315 : /* At this point, A's left subtree and B's left split are all keys
1316 : to the left of A's root and A's right subtree. Similarly, B's
1317 : right split are all keys to the right of A's root and A's left
1318 : subtree. We can't do a fast join on A's left/right subtree and B's
1319 : left/right split though as theses are not guaranteed to already
1320 : have their keys distributed as required by join. We instead
1321 : recursively merge the left side and right side. We do the left
1322 : side first and the right side later (making this a cache oblivious
1323 : algorithm too). */
1324 :
1325 : # if TREAP_OPTIMIZE_ITERATION
1326 1588032 : STACK_PUSH( idx_a, &pool[ idx_a ].TREAP_RIGHT, idx_a_right, idx_b_right,
1327 : pool[ idx_a ].TREAP_NEXT, idx_a_last, idx_b_right_first, idx_b_right_last, idx_a, merged_next );
1328 : # else
1329 1616136 : STACK_PUSH( idx_a, &pool[ idx_a ].TREAP_RIGHT, idx_a_right, idx_b_right );
1330 : # endif
1331 :
1332 3204168 : idx_merge_parent = idx_a;
1333 3204168 : _idx_merge = &pool[ idx_a ].TREAP_LEFT;
1334 : # if TREAP_OPTIMIZE_ITERATION
1335 1588032 : idx_a_last = pool[ idx_a ].TREAP_PREV;
1336 : idx_b_first = idx_b_left_first;
1337 : idx_b_last = idx_b_left_last;
1338 : merged_next = idx_a;
1339 : # endif
1340 3204168 : idx_a = idx_a_left;
1341 3204168 : idx_b = idx_b_left;
1342 3204168 : }
1343 :
1344 26430 : treap_a->root = new_root;
1345 26430 : treap_b->root = TREAP_IDX_NULL;
1346 26430 : treap_a->ele_cnt += treap_b->ele_cnt;
1347 26430 : treap_b->ele_cnt = 0UL;
1348 : # if TREAP_OPTIMIZE_ITERATION
1349 13065 : treap_b->first = TREAP_IDX_NULL;
1350 13065 : treap_b->last = TREAP_IDX_NULL;
1351 : # endif
1352 :
1353 26430 : return treap_a;
1354 :
1355 26430 : # undef STACK_POP
1356 26430 : # undef STACK_PUSH
1357 26430 : # undef STACK_IS_FULL
1358 26430 : # undef STACK_IS_EMPTY
1359 26430 : # undef STACK_MAX
1360 26430 : }
1361 :
1362 : TREAP_STATIC TREAP_(fwd_iter_t)
1363 : TREAP_(fwd_iter_init)( TREAP_(t) const * treap,
1364 64569665 : TREAP_T const * pool ) {
1365 : # if TREAP_OPTIMIZE_ITERATION
1366 : (void)pool;
1367 : return treap->first;
1368 : # else
1369 3758886 : ulong i = TREAP_IDX_NULL;
1370 : ulong j = (ulong)treap->root;
1371 18049266 : while( FD_LIKELY( !TREAP_IDX_IS_NULL( j ) ) ) { i = j; j = (ulong)pool[ j ].TREAP_LEFT; }
1372 : return i;
1373 : # endif
1374 64569665 : }
1375 :
1376 : TREAP_STATIC TREAP_(rev_iter_t)
1377 : TREAP_(rev_iter_init)( TREAP_(t) const * treap,
1378 2204872 : TREAP_T const * pool ) {
1379 : # if TREAP_OPTIMIZE_ITERATION
1380 : (void)pool;
1381 : return treap->last;
1382 : # else
1383 1227 : ulong i = TREAP_IDX_NULL;
1384 : ulong j = (ulong)treap->root;
1385 956553 : while( FD_LIKELY( !TREAP_IDX_IS_NULL( j ) ) ) { i = j; j = (ulong)pool[ j ].TREAP_RIGHT; }
1386 : return i;
1387 : # endif
1388 2204872 : }
1389 :
1390 : TREAP_STATIC TREAP_(fwd_iter_t)
1391 : TREAP_(fwd_iter_next)( TREAP_(fwd_iter_t) i,
1392 150067451 : TREAP_T const * pool ) {
1393 : # if TREAP_OPTIMIZE_ITERATION
1394 27161975 : return pool[ i ].TREAP_NEXT;
1395 : # else
1396 122905476 : ulong r = (ulong)pool[ i ].TREAP_RIGHT;
1397 :
1398 122905476 : if( TREAP_IDX_IS_NULL( r ) ) {
1399 63315081 : ulong p = (ulong)pool[ i ].TREAP_PARENT;
1400 122905410 : while( !TREAP_IDX_IS_NULL( p ) ) {
1401 119202432 : if( i==(ulong)pool[ p ].TREAP_LEFT ) break;
1402 59590329 : i = p;
1403 59590329 : p = (ulong)pool[ p ].TREAP_PARENT;
1404 59590329 : }
1405 63315081 : return p;
1406 63315081 : }
1407 :
1408 59590395 : i = r;
1409 108615201 : for(;;) {
1410 108615201 : ulong l = (ulong)pool[ i ].TREAP_LEFT;
1411 108615201 : if( TREAP_IDX_IS_NULL( l ) ) break;
1412 49024806 : i = l;
1413 49024806 : }
1414 :
1415 59590395 : return i;
1416 : # endif
1417 150067451 : }
1418 :
1419 : TREAP_STATIC TREAP_(rev_iter_t)
1420 : TREAP_(rev_iter_next)( TREAP_(rev_iter_t) i,
1421 23845200 : TREAP_T const * pool ) {
1422 : # if TREAP_OPTIMIZE_ITERATION
1423 23843028 : return pool[ i ].TREAP_PREV;
1424 : #else
1425 2172 : ulong l = (ulong)pool[ i ].TREAP_LEFT;
1426 :
1427 2172 : if( TREAP_IDX_IS_NULL( l ) ) {
1428 360 : ulong p = (ulong)pool[ i ].TREAP_PARENT;
1429 1419 : while( !TREAP_IDX_IS_NULL( p ) ) {
1430 1383 : if( i==(ulong)pool[ p ].TREAP_RIGHT ) break;
1431 1059 : i = p;
1432 1059 : p = (ulong)pool[ p ].TREAP_PARENT;
1433 1059 : }
1434 360 : return p;
1435 360 : }
1436 :
1437 1812 : i = l;
1438 2028 : for(;;) {
1439 2028 : ulong r = (ulong)pool[ i ].TREAP_RIGHT;
1440 2028 : if( TREAP_IDX_IS_NULL( r ) ) break;
1441 216 : i = r;
1442 216 : }
1443 :
1444 1812 : return i;
1445 : #endif
1446 23845200 : }
1447 :
1448 : TREAP_STATIC int
1449 : TREAP_(verify)( TREAP_(t) const * treap,
1450 30061167 : TREAP_T const * pool ) {
1451 :
1452 7949150112 : # define TREAP_TEST( c ) do { if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: " #c )); return -1; } } while(0)
1453 :
1454 30061167 : TREAP_TEST( treap ); /* Validate local join */
1455 :
1456 30061167 : ulong ele_max = treap->ele_max; TREAP_TEST( ele_max<=TREAP_IDX_NULL ); /* Validate ele_max */
1457 30061167 : ulong ele_cnt = treap->ele_cnt; TREAP_TEST( ele_cnt<=ele_max ); /* Validate ele_cnt */
1458 30061167 : if( ele_max ) TREAP_TEST( pool ); /* Validate ele storage */
1459 :
1460 : /* Find leftmost */
1461 :
1462 30061167 : ulong i = TREAP_IDX_NULL;
1463 30061167 : ulong l = (ulong)treap->root;
1464 :
1465 30061167 : ulong loop_cnt = 0UL;
1466 153397833 : while( FD_LIKELY( !TREAP_IDX_IS_NULL( l ) ) ) {
1467 123336666 : TREAP_TEST( loop_cnt<ele_cnt ); /* Make sure no cycles */
1468 123336666 : TREAP_TEST( l <ele_max ); /* Make sure valid index */
1469 123336666 : i = l;
1470 123336666 : l = (ulong)pool[ l ].TREAP_LEFT;
1471 123336666 : loop_cnt++;
1472 123336666 : }
1473 : # if TREAP_OPTIMIZE_ITERATION
1474 43347 : TREAP_TEST( treap->first==i );
1475 43347 : # endif
1476 :
1477 : /* In-order traverse the treap starting from the leftmost */
1478 :
1479 30061167 : ulong cnt = 0UL; /* Number of elements we've visited so far */
1480 1021711710 : while( FD_LIKELY( !TREAP_IDX_IS_NULL( i ) ) ) {
1481 991650543 : TREAP_TEST( cnt<ele_cnt ); /* Make sure no cycles */
1482 :
1483 : /* At this point, we are visiting element i. We've already visited
1484 : all elements less than i and l is the last element we visited (or
1485 : NULL if i is the first element we are visiting. */
1486 :
1487 991650543 : if( FD_LIKELY( !TREAP_IDX_IS_NULL( l ) ) ) TREAP_TEST( !TREAP_(lt)( pool + i, pool + l ) ); /* Make sure ordering valid */
1488 : # if TREAP_OPTIMIZE_ITERATION
1489 : /* Check the l <-> i link */
1490 6839202 : if( FD_LIKELY( !TREAP_IDX_IS_NULL( l ) ) ) TREAP_TEST( pool[ l ].TREAP_NEXT==i );
1491 6839202 : if( FD_LIKELY( !TREAP_IDX_IS_NULL( i ) ) ) TREAP_TEST( pool[ i ].TREAP_PREV==l );
1492 6839202 : # endif
1493 :
1494 :
1495 991650543 : ulong p = (ulong)pool[ i ].TREAP_PARENT;
1496 991650543 : if( FD_LIKELY( !TREAP_IDX_IS_NULL( p ) ) ) {
1497 962034177 : TREAP_TEST( p < ele_max ); /* Make sure valid index */
1498 962034177 : TREAP_TEST( (ulong)pool[ p ].TREAP_PRIO >= (ulong)pool[ i ].TREAP_PRIO ); /* Make sure heap property valid */
1499 962034177 : }
1500 :
1501 : /* Done visiting i, advance to i's successor */
1502 :
1503 991650543 : cnt++;
1504 :
1505 991650543 : l = i;
1506 :
1507 991650543 : ulong r = (ulong)pool[ i ].TREAP_RIGHT;
1508 991650543 : if( TREAP_IDX_IS_NULL( r ) ) {
1509 :
1510 : /* i has no right subtree. Look for first ancestor of i that we
1511 : haven't visited (this will be the first ancestor for which i is
1512 : in the ancestor's left subtree). If there is no such ancestor,
1513 : we are at the rightmost and we are done. */
1514 :
1515 515402484 : loop_cnt = 0UL;
1516 991650543 : while( !TREAP_IDX_IS_NULL( p ) ) {
1517 962034177 : TREAP_TEST( loop_cnt<ele_cnt ); /* Make sure no cycles */
1518 962034177 : TREAP_TEST( p <ele_max ); /* Make sure valid index */
1519 962034177 : if( i==(ulong)pool[ p ].TREAP_LEFT ) break;
1520 476248059 : i = p;
1521 476248059 : p = (ulong)pool[ p ].TREAP_PARENT;
1522 476248059 : loop_cnt++;
1523 476248059 : }
1524 :
1525 515402484 : i = p;
1526 :
1527 515402484 : } else {
1528 :
1529 : /* i has a right subtree. Find the leftmost in this subtree. */
1530 :
1531 476248059 : i = r;
1532 :
1533 476248059 : loop_cnt = 0UL;
1534 868313877 : for(;;) {
1535 868313877 : TREAP_TEST( loop_cnt<ele_cnt ); /* Make sure no cycles */
1536 868313877 : TREAP_TEST( i <ele_max ); /* Make sure valid index */
1537 868313877 : ulong ll = (ulong)pool[ i ].TREAP_LEFT;
1538 868313877 : if( TREAP_IDX_IS_NULL( ll ) ) break;
1539 392065818 : i = ll;
1540 392065818 : loop_cnt++;
1541 392065818 : }
1542 :
1543 476248059 : }
1544 :
1545 991650543 : }
1546 :
1547 : # if TREAP_OPTIMIZE_ITERATION
1548 43347 : TREAP_TEST( treap->last==l );
1549 43347 : # endif
1550 :
1551 30061167 : TREAP_TEST( cnt==ele_cnt ); /* Make sure we visited correct number of elements */
1552 :
1553 30061167 : # undef TREAP_TEST
1554 :
1555 30061167 : return 0;
1556 30061167 : }
1557 :
1558 : #endif
1559 :
1560 : #undef TREAP_IDX_IS_NULL
1561 : #undef TREAP_IDX_NULL
1562 : #undef TREAP_STATIC
1563 :
1564 : #undef TREAP_IMPL_STYLE
1565 : #undef TREAP_NEXT
1566 : #undef TREAP_PREV
1567 : #undef TREAP_OPTIMIZE_ITERATION
1568 : #undef TREAP_PRIO
1569 : #undef TREAP_RIGHT
1570 : #undef TREAP_LEFT
1571 : #undef TREAP_PARENT
1572 : #undef TREAP_IDX_T
1573 : #undef TREAP_LT
1574 : #undef TREAP_CMP
1575 : #undef TREAP_QUERY_T
1576 : #undef TREAP_T
1577 : #undef TREAP_NAME
|
