Line data Source code
1 : /* Generate prototypes, inlines and implementations for ultra high
2 : performance zero copy heaps for use in situations where the heap
3 : elements are not stored sequentially in memory (textbook heap
4 : algorithms, including prq, assume the heap elements will be stored in
5 : an array such that the root, parent, left/right children and next
6 : heap element to use are all implied by the element cnt and array
7 : indices ... also worth noting that this API does assume that heap
8 : elements themselves are embedded in a linear addressable storage
9 : region such as a fd_pool for persistence and relocatability though).
10 :
11 : This API is designed for ultra tight coupling with pools, maps, other
12 : heaps, etc. Likewise, a heap can be persisted beyond the lifetime of
13 : creating process, used concurrently in many common operations, used
14 : inter-process, relocated in memory, naively serialized/deserialized,
15 : moved between hosts, supports index compression for cache and memory
16 : bandwidth efficiency, etc.
17 :
18 : Typical usage:
19 :
20 : struct myele {
21 :
22 : ... Each field below can be located arbitrarily in the struct
23 :
24 : ulong left; // Technically "HEAP_IDX_T HEAP_LEFT;" (default is ulong left), similarly for right.
25 : ulong right; // These are managed by the heap when a myele is in the heap.
26 :
27 : ... Note that other kinds of objects can use these fields for
28 : ... their metadata needs to keep element metadata / cache
29 : ... footprint overheads minimal. The only restriction is that
30 : ... they cannot concurrently use the same field.
31 :
32 : ... Note that fields could be in an anonymous union and/or made
33 : ... into narrow bit fields if useful for additional layout,
34 : ... memory, bandwidth and cache efficiency.
35 :
36 : ... Arbitrary application fields mixed in here. Power-of-2
37 : ... element sizes have good cache and indexing Feng Shui.
38 :
39 : char key[ KEY_MAX ]; // For demonstration purposes
40 :
41 : };
42 :
43 : typedef struct myele myele_t;
44 :
45 : #define HEAP_NAME myheap
46 : #define HEAP_T myele_t
47 : #define HEAP_LT(e0,e1) (strcmp( e0->key, e1->key )<0)
48 : #include "fd_heap.c"
49 :
50 : will declare the following APIs as a header-only style library in the
51 : compilation unit:
52 :
53 : int myheap_lt( myele_t const * e0, myele_t const * e1 ); // Provides HEAP_LT
54 :
55 : // myheap_idx_null returns the element index used to represent
56 : // NULL, infinite lifetime. myheap_ele_null returns NULL, infinite
57 : // lifetime, for completeness, myheap_ele_null_const is a
58 : // const-correct version, also for completeness.
59 :
60 : ulong myheap_idx_null ( void );
61 : myele_t * myheap_ele_null ( void );
62 : myele_t const * myheap_ele_null_const( void );
63 :
64 : // myheap_{idx,ele}_is_null returns i==myheap_idx_null() / !e
65 :
66 : int myheap_idx_is_null( ulong i );
67 : int myheap_ele_is_null( myele_t const * e );
68 :
69 : // myheap_idx returns e's index. Assumes e is a pointer in the
70 : // caller's local address space to a pool element or is NULL.
71 : // Return will be in [0,ele_max) or myheap_idx_null(). Lifetime is
72 : // the element storage lifetime. myheap_idx_fast is the same but
73 : // assumes e is not NULL. pool is a pointer in the caller's
74 : // address space to the ele_max linearly addressable storage region
75 : // backing the heap.
76 :
77 : ulong myheap_idx ( myele_t const * e, myele_t const * pool );
78 : ulong myheap_idx_fast( myele_t const * e, myele_t const * pool );
79 :
80 : // myheap_ele returns a pointer in the caller's address space to
81 : // element idx. Assumes idx is in [0,ele_max) or is
82 : // myheap_idx_null(). Return pointer lifetime is ele's local
83 : // lifetime. myheap_ele_fast is the same but assumes idx is not
84 : // myheap_idx_null(). myheap_ele[_fast]_const is a const correct
85 : // version. pool is a pointer in the caller's address space to the
86 : // ele_max linearly addressable storage region backing the heap.
87 :
88 : myele_t * myheap_ele ( ulong i, myele_t * pool );
89 : myele_t * myheap_ele_fast( ulong i, myele_t * pool );
90 :
91 : myele_t const * myheap_ele_const ( ulong i, myele_t const * pool );
92 : myele_t const * myheap_ele_fast_const( ulong i, myele_t const * pool );
93 :
94 : // myheap_{align,footprint} returns the alignment and footprint
95 : // needed for a memory region to hold the state of a myheap of
96 : // elements from an ele_max element storage. align will be an
97 : // integer power-of-two and footprint will be a multiple of align.
98 : // footprint will non-zero on a success and 0 on failure (silent)
99 : // (e.g. ele_max too large for the specified HEAP_IDX_T). myheap_t
100 : // is stack declaration, data segment declaration, heap allocation
101 : // and stack allocation friendly. Even though footprint is passed
102 : // ele_max, the footprint is a small O(1) spatial overhead.
103 : //
104 : // myheap_new formats a memory region with the appropriate
105 : // alignment and footprint whose first byte in the caller's address
106 : // space is pointed to by shmem as a myheap for elements from an
107 : // ele_max element storage. Returns shmem on success and NULL on
108 : // failure (log details, e.g. ele_max is too large for the width of
109 : // the HEAP_IDX_T specified). Caller is not joined on return. The
110 : // heap will be empty.
111 : //
112 : // myheap_join joins a myheap. Assumes shheap points at a memory
113 : // region formatted as a myheap in the caller's address space.
114 : // Returns a handle to the caller's local join on success and NULL
115 : // on failure (logs details).
116 : //
117 : // myheap_leave leaves a myheap. Assumes join points to a current
118 : // local join. Returns shheap used on join and NULL on failure
119 : // (logs details).
120 : //
121 : // myheap_delete unformats a memory region used as a myheap.
122 : // Assumes shheap points to a memory region in the caller's local
123 : // address space formatted as a myheap, that there are no joins to
124 : // the myheap and that any application side cleanups have been
125 : // done. Returns shheap on success and NULL on failure (logs
126 : // details).
127 :
128 : ulong myheap_align ( void );
129 : ulong myheap_footprint( ulong ele_max );
130 : void * myheap_new ( void * shmem, ulong ele_max );
131 : myheap_t * myheap_join ( void * shheap );
132 : void * myheap_leave ( myheap_t * heap );
133 : void * myheap_delete ( void * shheap );
134 :
135 : // myheap_{ele_max,ele_cnt} gives the maximum number of elements
136 : // the heap can support / the current number of elements in the
137 : // heap. Assumes heap is a current local join. These might be
138 : // deprecated in the future.
139 :
140 : ulong myheap_ele_max( myheap_t const * heap );
141 : ulong myheap_ele_cnt( myheap_t const * heap );
142 :
143 : // myheap_idx_peek_min returns the index where the minimum element
144 : // is on the heap. Returns [0,ele_max) on success and
145 : // myheap_idx_null() if the heap is empty. Lifetime of the
146 : // returned idx is the lesser of until the min element is removed
147 : // or the underlying element storage lifetime. myheap_ele_peek_min
148 : // is the same but returns the location in the caller's address
149 : // space of the found element on success and NULL on failure
150 : // (lifetime of the returned pointer is until the min element is
151 : // removed or ele's local lifetime). myheap_ele_peek_min_const is
152 : // a const correct version. These operations are a fast O(1).
153 : // pool is a pointer in the caller's address space to the ele_max
154 : // linearly addressable storage region backing the heap.
155 :
156 : ulong myheap_idx_peek_min ( myheap_t const * heap, char const * q, myele_t const * pool );
157 : myele_t * myheap_ele_peek_min ( myheap_t * heap, char const * q, myele_t * pool );
158 : myele_t const * myheap_ele_peek_min_const( myheap_t const * heap, char const * q, myele_t const * pool );
159 :
160 : // myheap_idx_insert inserts element n into the heap and returns
161 : // heap. Assumes heap is a current local join, ele points in the
162 : // caller's address space to the ele_max element storage used for
163 : // heap elements, n is in [0,ele_max), n is currently not in the
164 : // heap, and n's queries are not in the heap (n's queries are the
165 : // set of queries that are covered by n). pool is a pointer in the
166 : // caller's address space to the ele_max linearly addressable
167 : // storage region backing the heap. Given these assumptions, this
168 : // cannot fail.
169 : //
170 : // n's query fields should already be populated (i.e.
171 : // MYHEAP_LT(ele+n,ele+i) should return valid results before this
172 : // is called). On return, n and n's queries will be in the heap.
173 : // n's left and right should not be modified while n is in the
174 : // heap. Further, the caller should not assume n's left and right
175 : // values are stable while n is in the heap. The heap does not
176 : // care about any other fields and these can be modified by the
177 : // user as necessary.
178 : //
179 : // myheap_ele_insert is the same but n points in the caller's local
180 : // address space the element to insert / remove.
181 : //
182 : // These operations have HPC implementations and are O(lg N)
183 : // average with an ultra high probability of having a small
184 : // coefficient.
185 :
186 : myheap_t * myheap_idx_insert( myheap_t * heap, ulong n, myele_t * pool );
187 : myheap_t * myheap_ele_insert( myheap_t * heap, myele_t * n, myele_t * pool );
188 :
189 : // myheap_idx_remove_min removes the min element from the heap and
190 : // returns heap. Assumes heap is a current local join, ele points
191 : // in the caller's address space to the ele_max element storage
192 : // used for heap elements and the heap has at least one element.
193 : // pool is a pointer in the caller's address space to the ele_max
194 : // linearly addressable storage region backing the heap. Given
195 : // these assumptions, this cannot fail.
196 : //
197 : // On return the min element and the min element's queries are no
198 : // longer in the heap. Use peek before calling this to get the
199 : // location of the min element to be removed. The fields of the
200 : // removed element can be freely modified on return.
201 : //
202 : // myheap_ele_remove_min is the same and just for naming
203 : // consistency.
204 : //
205 : // These operations have HPC implementations and are O(lg N)
206 : // average with an ultra high probability of having a small
207 : // coefficient (i.e. close to algorithmically optimal trees).
208 :
209 : myheap_t * myheap_idx_remove_min( myheap_t * heap, myele_t * pool );
210 : myheap_t * myheap_ele_remove_min( myheap_t * heap, myele_t * pool );
211 :
212 : // myheap_verify returns 0 if the myheap is not obviously corrupt
213 : // or a -1 (i.e. ERR_INVAL) if it is (logs details). heap is a
214 : // current local join to a myheap. pool is a pointer in the
215 : // caller's address space to the ele_max linearly addressable
216 : // storage region backing the heap.
217 :
218 : int myheap_verify( myheap_t const * heap, myele_t const * pool );
219 :
220 : You can do this as often as you like within a compilation unit to get
221 : different types of heaps. Variants exist for making separate headers
222 : and implementations for doing libraries and handling multiple
223 : compilation units. Additional options exist as detailed below. */
224 :
225 : /* HEAP_NAME gives the API prefix to use */
226 :
227 : #ifndef HEAP_NAME
228 : #error "Define HEAP_NAME"
229 : #endif
230 :
231 : /* HEAP_T is the heap element type */
232 :
233 : #ifndef HEAP_T
234 : #error "Define HEAP_T"
235 : #endif
236 :
237 : /* HEAP_LT returns 1 if the element e0's query fields are strictly less
238 : element e1's query fields and 0 otherwise. Should be a pure
239 : function. */
240 :
241 : #ifndef HEAP_LT
242 : #error "Define HEAP_LT"
243 : #endif
244 :
245 : /* HEAP_IDX_T is the type used for the HEAP_T fields. Should be a
246 : primitive unsigned integer type. Defaults to ulong. A heap can't
247 : use element memory regions that contain more than the maximum value
248 : that can be represented by a HEAP_IDX_T. */
249 :
250 : #ifndef HEAP_IDX_T
251 : #define HEAP_IDX_T ulong
252 : #endif
253 :
254 : /* HEAP_{LEFT,RIGHT} is the name of the heap element left / right
255 : fields. Defaults to left / right. */
256 :
257 : #ifndef HEAP_LEFT
258 : #define HEAP_LEFT left
259 : #endif
260 :
261 : #ifndef HEAP_RIGHT
262 : #define HEAP_RIGHT right
263 : #endif
264 :
265 : /* HEAP_IMPL_STYLE controls what this template should emit.
266 : 0 - local use only
267 : 1 - library header
268 : 2 - library implementation */
269 :
270 : #ifndef HEAP_IMPL_STYLE
271 : #define HEAP_IMPL_STYLE 0
272 : #endif
273 :
274 : /* Implementation *****************************************************/
275 :
276 : #if HEAP_IMPL_STYLE==0
277 : #define HEAP_STATIC static FD_FN_UNUSED
278 : #else
279 : #define HEAP_STATIC
280 : #endif
281 :
282 2132295849 : #define HEAP_IDX_NULL ((ulong)(HEAP_IDX_T)(~0UL))
283 2087942823 : #define HEAP_IDX_IS_NULL( idx ) ((idx)==HEAP_IDX_NULL)
284 :
285 34803810 : #define HEAP_(n) FD_EXPAND_THEN_CONCAT3(HEAP_NAME,_,n)
286 :
287 : /* Verification logs details on failure. The rest only needs fd_bits.h
288 : (consider making logging a compile time option). */
289 :
290 : #include "../log/fd_log.h"
291 :
292 : #if HEAP_IMPL_STYLE!=2 /* need structures, prototypes and inlines */
293 :
294 : /* structures */
295 :
296 : /* TODO: consider eliminating ele_cnt and maybe ele_max fields (less overhead,
297 : faster bulk ops, concurrency options, simpler constructors, etc) */
298 :
299 : struct HEAP_(private) {
300 : ulong ele_max; /* Maximum number of elements in heap, in [0,HEAP_IDX_NULL] */
301 : ulong ele_cnt; /* Current number of elements in heap, in [0,ele_max] */
302 : HEAP_IDX_T root; /* Index of the root heap element, in [0,ele_max) or HEAP_IDX_NULL */
303 : };
304 :
305 : typedef struct HEAP_(private) HEAP_(t);
306 :
307 : FD_PROTOTYPES_BEGIN
308 :
309 : /* prototypes */
310 :
311 : HEAP_STATIC FD_FN_CONST ulong HEAP_(align) ( void );
312 : HEAP_STATIC FD_FN_CONST ulong HEAP_(footprint)( ulong ele_max );
313 : HEAP_STATIC /**/ void * HEAP_(new) ( void * shmem, ulong ele_max );
314 : HEAP_STATIC /**/ HEAP_(t) * HEAP_(join) ( void * shheap );
315 : HEAP_STATIC /**/ void * HEAP_(leave) ( HEAP_(t) * heap );
316 : HEAP_STATIC /**/ void * HEAP_(delete) ( void * shheap );
317 :
318 : HEAP_STATIC HEAP_(t) * HEAP_(idx_insert)( HEAP_(t) * heap, ulong n, HEAP_T * pool );
319 :
320 : HEAP_STATIC HEAP_(t) * HEAP_(idx_remove_min)( HEAP_(t) * heap, HEAP_T * pool );
321 :
322 : HEAP_STATIC int HEAP_(verify)( HEAP_(t) const * heap, HEAP_T const * pool );
323 :
324 : /* inlines */
325 :
326 991910559 : FD_FN_PURE static inline int HEAP_(lt) ( HEAP_T const * e0, HEAP_T const * e1 ) { return HEAP_LT( e0, e1 ); }
327 :
328 3 : FD_FN_CONST static inline ulong HEAP_(idx_null) ( void ) { return HEAP_IDX_NULL; }
329 3 : FD_FN_CONST static inline HEAP_T * HEAP_(ele_null) ( void ) { return NULL; }
330 3 : FD_FN_CONST static inline HEAP_T const * HEAP_(ele_null_const)( void ) { return NULL; }
331 :
332 217560 : FD_FN_CONST static inline int HEAP_(idx_is_null)( ulong i ) { return HEAP_IDX_IS_NULL( i ); }
333 1536 : FD_FN_CONST static inline int HEAP_(ele_is_null)( HEAP_T const * e ) { return !e; }
334 :
335 : FD_FN_CONST static inline ulong
336 : HEAP_(idx)( HEAP_T const * e,
337 29580480 : HEAP_T const * pool ) {
338 29580480 : return fd_ulong_if( !!e, (ulong)(e-pool), HEAP_IDX_NULL );
339 29580480 : }
340 :
341 : FD_FN_CONST static inline HEAP_T *
342 : HEAP_(ele)( ulong i,
343 768 : HEAP_T * pool ) {
344 768 : return fd_ptr_if( !HEAP_IDX_IS_NULL( i ), pool + i, NULL );
345 768 : }
346 :
347 : FD_FN_CONST static inline HEAP_T const *
348 : HEAP_(ele_const)( ulong i,
349 768 : HEAP_T const * pool ) {
350 768 : return fd_ptr_if( !HEAP_IDX_IS_NULL( i ), pool + i, NULL );
351 768 : }
352 :
353 1530 : FD_FN_CONST static inline ulong HEAP_(idx_fast) ( HEAP_T const * e, HEAP_T const * pool ) { return (ulong)(e - pool); }
354 765 : FD_FN_CONST static inline HEAP_T * HEAP_(ele_fast) ( ulong i, HEAP_T * pool ) { return pool + i; }
355 765 : FD_FN_CONST static inline HEAP_T const * HEAP_(ele_fast_const)( ulong i, HEAP_T const * pool ) { return pool + i; }
356 :
357 15006264 : FD_FN_PURE static inline ulong HEAP_(ele_max)( HEAP_(t) const * heap ) { return heap->ele_max; }
358 15006264 : FD_FN_PURE static inline ulong HEAP_(ele_cnt)( HEAP_(t) const * heap ) { return heap->ele_cnt; }
359 :
360 22392384 : FD_FN_PURE static inline ulong HEAP_(idx_peek_min)( HEAP_(t) const * heap ) { return (ulong)heap->root; }
361 :
362 : FD_FN_PURE static inline HEAP_T *
363 : HEAP_(ele_peek_min)( HEAP_(t) const * heap,
364 15006264 : HEAP_T * pool ) {
365 15006264 : ulong i = (ulong)heap->root;
366 15006264 : return fd_ptr_if( !HEAP_IDX_IS_NULL( i ), pool + i, NULL );
367 15006264 : }
368 :
369 : FD_FN_PURE static inline HEAP_T const *
370 : HEAP_(ele_peek_min_const)( HEAP_(t) const * heap,
371 15006264 : HEAP_T const * pool ) {
372 15006264 : ulong i = (ulong)heap->root;
373 15006264 : return fd_ptr_if( !HEAP_IDX_IS_NULL( i ), pool + i, NULL );
374 15006264 : }
375 :
376 : static inline HEAP_(t) *
377 : HEAP_(ele_insert)( HEAP_(t) * heap,
378 : HEAP_T * e,
379 3692667 : HEAP_T * pool ) {
380 3692667 : return HEAP_(idx_insert)( heap, (ulong)(e - pool), pool );
381 3692667 : }
382 :
383 : static inline HEAP_(t) *
384 : HEAP_(ele_remove_min)( HEAP_(t) * heap,
385 3691989 : HEAP_T * pool ) {
386 3691989 : return HEAP_(idx_remove_min)( heap, pool );
387 3691989 : }
388 :
389 : FD_PROTOTYPES_END
390 :
391 : #endif
392 :
393 : #if HEAP_IMPL_STYLE!=1 /* need implementations */
394 :
395 : HEAP_STATIC FD_FN_CONST ulong
396 24 : HEAP_(align)( void ) {
397 24 : return alignof(HEAP_(t));
398 24 : }
399 :
400 : HEAP_STATIC FD_FN_CONST ulong
401 6 : HEAP_(footprint)( ulong ele_max ) {
402 6 : if( FD_UNLIKELY( ele_max>HEAP_IDX_NULL ) ) return 0UL;
403 3 : return sizeof(HEAP_(t));
404 6 : }
405 :
406 : HEAP_STATIC void *
407 : HEAP_(new)( void * shmem,
408 12 : ulong ele_max ) {
409 12 : if( !shmem ) {
410 3 : FD_LOG_WARNING(( "NULL shmem" ));
411 3 : return NULL;
412 3 : }
413 :
414 9 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, HEAP_(align)() ) ) ) {
415 3 : FD_LOG_WARNING(( "misaligned shmem" ));
416 3 : return NULL;
417 3 : }
418 :
419 6 : if( FD_UNLIKELY( ele_max>HEAP_IDX_NULL ) ) {
420 3 : FD_LOG_WARNING(( "ele_max too large" ));
421 3 : return NULL;
422 3 : }
423 :
424 3 : HEAP_(t) * heap = (HEAP_(t) *)shmem;
425 :
426 3 : heap->ele_max = ele_max;
427 3 : heap->ele_cnt = 0UL;
428 3 : heap->root = (HEAP_IDX_T)HEAP_IDX_NULL;
429 :
430 3 : return heap;
431 6 : }
432 :
433 : HEAP_STATIC HEAP_(t) *
434 9 : HEAP_(join)( void * shheap ) {
435 9 : if( FD_UNLIKELY( !shheap ) ) {
436 3 : FD_LOG_WARNING(( "NULL shheap" ));
437 3 : return NULL;
438 3 : }
439 :
440 6 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shheap, HEAP_(align)() ) ) ) {
441 3 : FD_LOG_WARNING(( "misaligned shheap" ));
442 3 : return NULL;
443 3 : }
444 :
445 3 : return (HEAP_(t) *)shheap;
446 6 : }
447 :
448 : HEAP_STATIC void *
449 6 : HEAP_(leave)( HEAP_(t) * heap ) {
450 6 : if( FD_UNLIKELY( !heap ) ) {
451 3 : FD_LOG_WARNING(( "NULL heap" ));
452 3 : return NULL;
453 3 : }
454 :
455 3 : return (void *)heap;
456 6 : }
457 :
458 : HEAP_STATIC void *
459 9 : HEAP_(delete)( void * shheap ) {
460 9 : if( FD_UNLIKELY( !shheap ) ) {
461 3 : FD_LOG_WARNING(( "NULL shheap" ));
462 3 : return NULL;
463 3 : }
464 :
465 6 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shheap, HEAP_(align)() ) ) ) {
466 3 : FD_LOG_WARNING(( "misaligned shheap" ));
467 3 : return NULL;
468 3 : }
469 :
470 3 : return shheap;
471 6 : }
472 :
473 : HEAP_STATIC HEAP_(t) *
474 : HEAP_(idx_insert)( HEAP_(t) * heap,
475 : ulong n,
476 7386270 : HEAP_T * pool ) {
477 : # if FD_TMPL_USE_HANDHOLDING
478 : if( FD_UNLIKELY( n>=heap->ele_max ) ) FD_LOG_CRIT(( "n out of range" ));
479 : # endif
480 :
481 7386270 : HEAP_IDX_T * _p_child = &heap->root;
482 :
483 7386270 : ulong i = (ulong)*_p_child;
484 :
485 7386270 : if( FD_UNLIKELY( HEAP_IDX_IS_NULL( i ) ) ) { /* Heap was empty, make n the root, opt for larger heaps */
486 109533 : pool[ n ].HEAP_LEFT = (HEAP_IDX_T)HEAP_IDX_NULL;
487 109533 : pool[ n ].HEAP_RIGHT = (HEAP_IDX_T)HEAP_IDX_NULL;
488 109533 : *_p_child = (HEAP_IDX_T)n;
489 109533 : heap->ele_cnt++;
490 109533 : return heap;
491 109533 : }
492 :
493 7276737 : ulong rbits_cnt = 0UL;
494 7276737 : ulong rbits = 0UL;
495 :
496 31611390 : for(;;) {
497 31611390 : ulong l = (ulong)pool[ i ].HEAP_LEFT;
498 31611390 : ulong r = (ulong)pool[ i ].HEAP_RIGHT;
499 :
500 : /* At this point, i's ancestors are less than n. If n is before i,
501 : displace i with n. */
502 :
503 31611390 : if( FD_UNLIKELY( HEAP_(lt)( pool + n, pool + i ) ) ) { /* Opt for larger heaps and IID rank inserts */
504 25149279 : pool[ n ].HEAP_LEFT = (HEAP_IDX_T)l;
505 25149279 : pool[ n ].HEAP_RIGHT = (HEAP_IDX_T)r;
506 25149279 : *_p_child = (HEAP_IDX_T)n;
507 25149279 : ulong swap_tmp = i; i = n; n = swap_tmp;
508 25149279 : }
509 :
510 : /* At this point i < n. If there is neither a left subheap nor a
511 : right subheap, make n i's left child. If there is no left/right
512 : subheap, make n i's left/right child. */
513 :
514 31611390 : int is_null_left = HEAP_IDX_IS_NULL( l );
515 31611390 : int is_null_right = HEAP_IDX_IS_NULL( r );
516 31611390 : if( FD_UNLIKELY( (is_null_left | is_null_right) ) ) { /* Opt for larger heaps */
517 7276737 : pool[ n ].HEAP_LEFT = (HEAP_IDX_T)HEAP_IDX_NULL;
518 7276737 : pool[ n ].HEAP_RIGHT = (HEAP_IDX_T)HEAP_IDX_NULL;
519 7276737 : *fd_ptr_if( is_null_left, &pool[ i ].HEAP_LEFT, &pool[ i ].HEAP_RIGHT ) = (HEAP_IDX_T)n;
520 7276737 : break;
521 7276737 : }
522 :
523 : /* At this point, i has a left and right subheap. We need to pick one
524 : to insert n into. Ideally we'd pick the smaller one. But since
525 : we don't know this (might be possible to be clever here using the
526 : cnt of items in the heap on the assumption that heap has been
527 : optimally constructed thus far though this would probably only
528 : work in pure heapsort like cases), we pseudo randomly pick one
529 : instead. */
530 :
531 24334653 : if( FD_UNLIKELY( !rbits_cnt ) ) {
532 7037898 : rbits = fd_ulong_hash( ( i ^ fd_ulong_rotate_left( n, 16 )) ^
533 7037898 : (fd_ulong_rotate_left( l, 32 ) ^ fd_ulong_rotate_left( r, 48 )) );
534 7037898 : rbits_cnt = 64UL; /* TODO: consider using fraction to mix up further? */
535 7037898 : }
536 24334653 : int go_left = (int)(rbits & 1UL);
537 24334653 : rbits >>= 1;
538 24334653 : rbits_cnt--;
539 :
540 24334653 : _p_child = fd_ptr_if ( go_left, &pool[ i ].HEAP_LEFT, &pool[ i ].HEAP_RIGHT );
541 24334653 : i = fd_ulong_if( go_left, l, r );
542 24334653 : }
543 :
544 7276737 : heap->ele_cnt++;
545 7276737 : return heap;
546 7386270 : }
547 :
548 : HEAP_STATIC HEAP_(t) *
549 : HEAP_(idx_remove_min)( HEAP_(t) * heap,
550 7386120 : HEAP_T * pool ) {
551 : # if FD_TMPL_USE_HANDHOLDING
552 : if( FD_UNLIKELY( !heap->ele_cnt ) ) FD_LOG_CRIT(( "heap empty" ));
553 : # endif
554 :
555 7386120 : ulong d = (ulong)heap->root;
556 :
557 7386120 : HEAP_IDX_T * _p_child = &heap->root;
558 7386120 : ulong l = (ulong)pool[ d ].HEAP_LEFT;
559 7386120 : ulong r = (ulong)pool[ d ].HEAP_RIGHT;
560 :
561 34805271 : for(;;) {
562 :
563 : /* At this point, we have a hole to fill at d.
564 :
565 : l is the hole's left subheap (if any)
566 : r is the hole's right subheap (if any)
567 :
568 : p_child points to the link from the d's parent to d (if d has a
569 : parent) and to the heap root link otherwise.
570 :
571 : If there is neither a left subheap nor a right subheap, we are
572 : done. If there is a left/right subheap, we fill the hole with
573 : the right/left subheap and we are done. */
574 :
575 34805271 : int is_null_left = HEAP_IDX_IS_NULL( l );
576 34805271 : int is_null_right = HEAP_IDX_IS_NULL( r );
577 34805271 : if( FD_UNLIKELY( is_null_left | is_null_right ) ) { /* Opt for larger heaps */
578 7386120 : *_p_child = (HEAP_IDX_T)fd_ulong_if( is_null_left, r, l );
579 7386120 : break;
580 7386120 : }
581 :
582 : /* d has two subheaps. We fill the hole with the smaller root element
583 : (preserving the heap property). This bubbles d down one layer
584 : toward the subheap with the smaller root. We fill that hole the
585 : next iteration. Note we don't need to update any links to/from d
586 : as we will be getting rid of all links to/from d. */
587 :
588 27419151 : int promote_left = HEAP_(lt)( pool + l, pool + r );
589 :
590 27419151 : ulong c = fd_ulong_if( promote_left, l, r );
591 27419151 : ulong l_nxt = (ulong)pool[ c ].HEAP_LEFT;
592 27419151 : ulong r_nxt = (ulong)pool[ c ].HEAP_RIGHT;
593 :
594 27419151 : *_p_child = (HEAP_IDX_T)c;
595 :
596 27419151 : *fd_ptr_if( promote_left, &pool[ l ].HEAP_RIGHT, &pool[ r ].HEAP_LEFT ) = (HEAP_IDX_T)fd_ulong_if( promote_left, r, l );
597 :
598 27419151 : _p_child = fd_ptr_if( promote_left, &pool[ l ].HEAP_LEFT, &pool[ r ].HEAP_RIGHT );
599 27419151 : l = l_nxt;
600 27419151 : r = r_nxt;
601 27419151 : }
602 :
603 7386120 : heap->ele_cnt--;
604 7386120 : return heap;
605 7386120 : }
606 :
607 : HEAP_STATIC int
608 : HEAP_(verify)( HEAP_(t) const * heap,
609 30000003 : HEAP_T const * pool ) {
610 :
611 3970217940 : # define HEAP_TEST( c ) do { if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: " #c )); return -1; } } while(0)
612 :
613 30000003 : HEAP_TEST( heap ); /* Validate local join */
614 :
615 30000003 : ulong ele_max = heap->ele_max;
616 30000003 : ulong ele_cnt = heap->ele_cnt;
617 30000003 : HEAP_TEST( ele_max<=HEAP_IDX_NULL ); /* Validate ele_max */
618 30000003 : HEAP_TEST( ele_cnt<=ele_max ); /* Validate ele_cnt */
619 30000003 : if( ele_max ) HEAP_TEST( pool ); /* Validate ele storage */
620 :
621 30000003 : ulong stack[ 512 ];
622 30000003 : ulong stack_cnt = 0UL;
623 30000003 : ulong stack_max = 512UL; /* Should be impossibly large if heap is statistically well balanced */
624 :
625 30000003 : ulong visit_cnt = 0UL;
626 :
627 30000003 : ulong i = (ulong)heap->root;
628 30000003 : if( !HEAP_IDX_IS_NULL( i ) ) { /* Schedule first visit */
629 29565951 : HEAP_TEST( i<ele_max ); /* Make sure inbounds */
630 29565951 : HEAP_TEST( stack_cnt<stack_max ); /* Make sure no stack overflow */
631 29565951 : stack[ stack_cnt++ ] = i; /* Push i to stack */
632 29565951 : }
633 :
634 992445972 : while( stack_cnt ) { /* While still nodes to visit */
635 962445969 : HEAP_TEST( visit_cnt<ele_cnt ); /* Make sure no cycles */
636 :
637 962445969 : i = stack[ --stack_cnt ]; /* Pop the stack to get next visit (value was validated on push) */
638 :
639 : /* visit i and schedule visits to i's children */
640 :
641 962445969 : ulong r = (ulong)pool[ i ].HEAP_RIGHT;
642 962445969 : if( !HEAP_IDX_IS_NULL( r ) ) {
643 392997171 : HEAP_TEST( HEAP_(lt)( pool + i, pool + r ) ); /* Make sure heap property satisfied */
644 392997171 : HEAP_TEST( r<ele_max ); /* Make sure inbounds */
645 392997171 : HEAP_TEST( stack_cnt<stack_max ); /* Make sure no stack overflow */
646 392997171 : stack[ stack_cnt++ ] = r; /* Push r to stack */
647 392997171 : }
648 :
649 962445969 : ulong l = (ulong)pool[ i ].HEAP_LEFT;
650 962445969 : if( !HEAP_IDX_IS_NULL( l ) ) {
651 539882847 : HEAP_TEST( HEAP_(lt)( pool + i, pool + l ) ); /* Make sure heap property satisfied */
652 539882847 : HEAP_TEST( l<ele_max ); /* Make sure inbounds */
653 539882847 : HEAP_TEST( stack_cnt<stack_max ); /* Make sure no stack overflow */
654 539882847 : stack[ stack_cnt++ ] = l; /* Push l to stack */
655 539882847 : }
656 :
657 962445969 : visit_cnt++; /* update the number visited */
658 962445969 : }
659 :
660 30000003 : HEAP_TEST( visit_cnt==ele_cnt ); /* Make sure visit count matches */
661 30000003 : return 0;
662 30000003 : }
663 :
664 : #endif
665 :
666 : #undef HEAP_IDX_IS_NULL
667 : #undef HEAP_IDX_NULL
668 : #undef HEAP_STATIC
669 :
670 : #undef HEAP_IMPL_STYLE
671 : #undef HEAP_RIGHT
672 : #undef HEAP_LEFT
673 : #undef HEAP_IDX_T
674 : #undef HEAP_LT
675 : #undef HEAP_T
676 : #undef HEAP_NAME
|
