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