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