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 0 : #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 0 : #define HEAP_LEFT left
259 : #endif
260 :
261 : #ifndef HEAP_RIGHT
262 0 : #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 2132295078 : #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 FD_FN_PURE 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 0 : FD_FN_CONST static inline ulong HEAP_(idx_null) ( void ) { return HEAP_IDX_NULL; }
329 0 : FD_FN_CONST static inline HEAP_T * HEAP_(ele_null) ( void ) { return NULL; }
330 0 : 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 768 : 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 29579712 : HEAP_T const * pool ) {
338 29579712 : return fd_ulong_if( !!e, (ulong)(e-pool), HEAP_IDX_NULL );
339 29579712 : }
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 765 : 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 0 : HEAP_(align)( void ) {
397 0 : return alignof(HEAP_(t));
398 0 : }
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 :
478 7386270 : HEAP_IDX_T * _p_child = &heap->root;
479 :
480 7386270 : ulong i = (ulong)*_p_child;
481 :
482 7386270 : if( FD_UNLIKELY( HEAP_IDX_IS_NULL( i ) ) ) { /* Heap was empty, make n the root, opt for larger heaps */
483 109533 : pool[ n ].HEAP_LEFT = (HEAP_IDX_T)HEAP_IDX_NULL;
484 109533 : pool[ n ].HEAP_RIGHT = (HEAP_IDX_T)HEAP_IDX_NULL;
485 109533 : *_p_child = (HEAP_IDX_T)n;
486 109533 : heap->ele_cnt++;
487 109533 : return heap;
488 109533 : }
489 :
490 7276737 : ulong rbits_cnt = 0UL;
491 7276737 : ulong rbits = 0UL;
492 :
493 31611390 : for(;;) {
494 31611390 : ulong l = (ulong)pool[ i ].HEAP_LEFT;
495 31611390 : ulong r = (ulong)pool[ i ].HEAP_RIGHT;
496 :
497 : /* At this point, i's ancestors are less than n. If n is before i,
498 : displace i with n. */
499 :
500 31611390 : if( FD_UNLIKELY( HEAP_(lt)( pool + n, pool + i ) ) ) { /* Opt for larger heaps and IID rank inserts */
501 25149279 : pool[ n ].HEAP_LEFT = (HEAP_IDX_T)l;
502 25149279 : pool[ n ].HEAP_RIGHT = (HEAP_IDX_T)r;
503 25149279 : *_p_child = (HEAP_IDX_T)n;
504 25149279 : ulong swap_tmp = i; i = n; n = swap_tmp;
505 25149279 : }
506 :
507 : /* At this point i < n. If there is neither a left subheap nor a
508 : right subheap, make n i's left child. If there is no left/right
509 : subheap, make n i's left/right child. */
510 :
511 31611390 : int is_null_left = HEAP_IDX_IS_NULL( l );
512 31611390 : int is_null_right = HEAP_IDX_IS_NULL( r );
513 31611390 : if( FD_UNLIKELY( (is_null_left | is_null_right) ) ) { /* Opt for larger heaps */
514 7276737 : pool[ n ].HEAP_LEFT = (HEAP_IDX_T)HEAP_IDX_NULL;
515 7276737 : pool[ n ].HEAP_RIGHT = (HEAP_IDX_T)HEAP_IDX_NULL;
516 7276737 : *fd_ptr_if( is_null_left, &pool[ i ].HEAP_LEFT, &pool[ i ].HEAP_RIGHT ) = (HEAP_IDX_T)n;
517 7276737 : break;
518 7276737 : }
519 :
520 : /* At this point, i has a left and right subheap. We need to pick one
521 : to insert n into. Ideally we'd pick the smaller one. But since
522 : we don't know this (might be possible to be clever here using the
523 : cnt of items in the heap on the assumption that heap has been
524 : optimally constructed thus far though this would probably only
525 : work in pure heapsort like cases), we pseudo randomly pick one
526 : instead. */
527 :
528 24334653 : if( FD_UNLIKELY( !rbits_cnt ) ) {
529 7037898 : rbits = fd_ulong_hash( ( i ^ fd_ulong_rotate_left( n, 16 )) ^
530 7037898 : (fd_ulong_rotate_left( l, 32 ) ^ fd_ulong_rotate_left( r, 48 )) );
531 7037898 : rbits_cnt = 64UL; /* TODO: consider using fraction to mix up further? */
532 7037898 : }
533 24334653 : int go_left = (int)(rbits & 1UL);
534 24334653 : rbits >>= 1;
535 24334653 : rbits_cnt--;
536 :
537 24334653 : _p_child = fd_ptr_if ( go_left, &pool[ i ].HEAP_LEFT, &pool[ i ].HEAP_RIGHT );
538 24334653 : i = fd_ulong_if( go_left, l, r );
539 24334653 : }
540 :
541 7276737 : heap->ele_cnt++;
542 7276737 : return heap;
543 7386270 : }
544 :
545 : HEAP_STATIC HEAP_(t) *
546 : HEAP_(idx_remove_min)( HEAP_(t) * heap,
547 7386120 : HEAP_T * pool ) {
548 7386120 : ulong d = (ulong)heap->root;
549 :
550 7386120 : HEAP_IDX_T * _p_child = &heap->root;
551 7386120 : ulong l = (ulong)pool[ d ].HEAP_LEFT;
552 7386120 : ulong r = (ulong)pool[ d ].HEAP_RIGHT;
553 :
554 34805271 : for(;;) {
555 :
556 : /* At this point, we have a hole to fill at d.
557 :
558 : l is the hole's left subheap (if any)
559 : r is the hole's right subheap (if any)
560 :
561 : p_child points to the link from the d's parent to d (if d has a
562 : parent) and to the heap root link otherwise.
563 :
564 : If there is neither a left subheap nor a right subheap, we are
565 : done. If there is a left/right subheap, we fill the hole with
566 : the right/left subheap and we are done. */
567 :
568 34805271 : int is_null_left = HEAP_IDX_IS_NULL( l );
569 34805271 : int is_null_right = HEAP_IDX_IS_NULL( r );
570 34805271 : if( FD_UNLIKELY( is_null_left | is_null_right ) ) { /* Opt for larger heaps */
571 7386120 : *_p_child = (HEAP_IDX_T)fd_ulong_if( is_null_left, r, l );
572 7386120 : break;
573 7386120 : }
574 :
575 : /* d has two subheaps. We fill the hole with the smaller root element
576 : (preserving the heap property). This bubbles d down one layer
577 : toward the subheap with the smaller root. We fill that hole the
578 : next iteration. Note we don't need to update any links to/from d
579 : as we will be getting rid of all links to/from d. */
580 :
581 27419151 : int promote_left = HEAP_(lt)( pool + l, pool + r );
582 :
583 27419151 : ulong c = fd_ulong_if( promote_left, l, r );
584 27419151 : ulong l_nxt = (ulong)pool[ c ].HEAP_LEFT;
585 27419151 : ulong r_nxt = (ulong)pool[ c ].HEAP_RIGHT;
586 :
587 27419151 : *_p_child = (HEAP_IDX_T)c;
588 :
589 27419151 : *fd_ptr_if( promote_left, &pool[ l ].HEAP_RIGHT, &pool[ r ].HEAP_LEFT ) = (HEAP_IDX_T)fd_ulong_if( promote_left, r, l );
590 :
591 27419151 : _p_child = fd_ptr_if( promote_left, &pool[ l ].HEAP_LEFT, &pool[ r ].HEAP_RIGHT );
592 27419151 : l = l_nxt;
593 27419151 : r = r_nxt;
594 27419151 : }
595 :
596 7386120 : heap->ele_cnt--;
597 7386120 : return heap;
598 7386120 : }
599 :
600 : HEAP_STATIC int
601 : HEAP_(verify)( HEAP_(t) const * heap,
602 30000003 : HEAP_T const * pool ) {
603 :
604 3970217940 : # define HEAP_TEST( c ) do { if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: " #c )); return -1; } } while(0)
605 :
606 30000003 : HEAP_TEST( heap ); /* Validate local join */
607 :
608 30000003 : ulong ele_max = heap->ele_max;
609 30000003 : ulong ele_cnt = heap->ele_cnt;
610 30000003 : HEAP_TEST( ele_max<=HEAP_IDX_NULL ); /* Validate ele_max */
611 30000003 : HEAP_TEST( ele_cnt<=ele_max ); /* Validate ele_cnt */
612 30000003 : if( ele_max ) HEAP_TEST( pool ); /* Validate ele storage */
613 :
614 30000003 : ulong stack[ 512 ];
615 30000003 : ulong stack_cnt = 0UL;
616 30000003 : ulong stack_max = 512UL; /* Should be impossibly large if heap is statistically well balanced */
617 :
618 30000003 : ulong visit_cnt = 0UL;
619 :
620 30000003 : ulong i = (ulong)heap->root;
621 30000003 : if( !HEAP_IDX_IS_NULL( i ) ) { /* Schedule first visit */
622 29565951 : HEAP_TEST( i<ele_max ); /* Make sure inbounds */
623 29565951 : HEAP_TEST( stack_cnt<stack_max ); /* Make sure no stack overflow */
624 29565951 : stack[ stack_cnt++ ] = i; /* Push i to stack */
625 29565951 : }
626 :
627 992445972 : while( stack_cnt ) { /* While still nodes to visit */
628 962445969 : HEAP_TEST( visit_cnt<ele_cnt ); /* Make sure no cycles */
629 :
630 962445969 : i = stack[ --stack_cnt ]; /* Pop the stack to get next visit (value was validated on push) */
631 :
632 : /* visit i and schedule visits to i's children */
633 :
634 962445969 : ulong r = (ulong)pool[ i ].HEAP_RIGHT;
635 962445969 : if( !HEAP_IDX_IS_NULL( r ) ) {
636 392997171 : HEAP_TEST( HEAP_(lt)( pool + i, pool + r ) ); /* Make sure heap property satisfied */
637 392997171 : HEAP_TEST( r<ele_max ); /* Make sure inbounds */
638 392997171 : HEAP_TEST( stack_cnt<stack_max ); /* Make sure no stack overflow */
639 392997171 : stack[ stack_cnt++ ] = r; /* Push r to stack */
640 392997171 : }
641 :
642 962445969 : ulong l = (ulong)pool[ i ].HEAP_LEFT;
643 962445969 : if( !HEAP_IDX_IS_NULL( l ) ) {
644 539882847 : HEAP_TEST( HEAP_(lt)( pool + i, pool + l ) ); /* Make sure heap property satisfied */
645 539882847 : HEAP_TEST( l<ele_max ); /* Make sure inbounds */
646 539882847 : HEAP_TEST( stack_cnt<stack_max ); /* Make sure no stack overflow */
647 539882847 : stack[ stack_cnt++ ] = l; /* Push l to stack */
648 539882847 : }
649 :
650 962445969 : visit_cnt++; /* update the number visited */
651 962445969 : }
652 :
653 30000003 : HEAP_TEST( visit_cnt==ele_cnt ); /* Make sure visit count matches */
654 30000003 : return 0;
655 30000003 : }
656 :
657 : #endif
658 :
659 : #undef HEAP_IDX_IS_NULL
660 : #undef HEAP_IDX_NULL
661 : #undef HEAP_STATIC
662 :
663 : #undef HEAP_IMPL_STYLE
664 : #undef HEAP_RIGHT
665 : #undef HEAP_LEFT
666 : #undef HEAP_IDX_T
667 : #undef HEAP_LT
668 : #undef HEAP_T
669 : #undef HEAP_NAME
670 :
|
