Line data Source code
1 : #include "fd_forest.h"
2 :
3 0 : static void ver_inc( ulong ** ver ) {
4 0 : fd_fseq_update( *ver, fd_fseq_query( *ver ) + 1 );
5 0 : }
6 :
7 0 : #define VER_INC ulong * ver __attribute__((cleanup(ver_inc))) = fd_forest_ver( forest ); ver_inc( &ver )
8 :
9 : void *
10 0 : fd_forest_new( void * shmem, ulong ele_max, ulong seed ) {
11 0 : FD_TEST( fd_ulong_is_pow2( ele_max ) );
12 :
13 0 : if( FD_UNLIKELY( !shmem ) ) {
14 0 : FD_LOG_WARNING(( "NULL mem" ));
15 0 : return NULL;
16 0 : }
17 :
18 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_forest_align() ) ) ) {
19 0 : FD_LOG_WARNING(( "misaligned mem" ));
20 0 : return NULL;
21 0 : }
22 :
23 0 : ulong footprint = fd_forest_footprint( ele_max );
24 0 : if( FD_UNLIKELY( !footprint ) ) {
25 0 : FD_LOG_WARNING(( "bad ele_max (%lu)", ele_max ));
26 0 : return NULL;
27 0 : }
28 :
29 0 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
30 0 : if( FD_UNLIKELY( !wksp ) ) {
31 0 : FD_LOG_WARNING(( "shmem must be part of a workspace" ));
32 0 : return NULL;
33 0 : }
34 :
35 0 : fd_memset( shmem, 0, footprint );
36 0 : fd_forest_t * forest;
37 :
38 0 : FD_SCRATCH_ALLOC_INIT( l, shmem );
39 0 : forest = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_align(), sizeof(fd_forest_t) );
40 0 : void * ver = FD_SCRATCH_ALLOC_APPEND( l, fd_fseq_align(), fd_fseq_footprint() );
41 0 : void * pool = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_pool_align(), fd_forest_pool_footprint( ele_max ) );
42 0 : void * ancestry = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_ancestry_align(), fd_forest_ancestry_footprint( ele_max ) );
43 0 : void * frontier = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_frontier_align(), fd_forest_frontier_footprint( ele_max ) );
44 0 : void * orphaned = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_orphaned_align(), fd_forest_orphaned_footprint( ele_max ) );
45 0 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_forest_align() ) == (ulong)shmem + footprint );
46 :
47 0 : forest->root = ULONG_MAX;
48 0 : forest->wksp_gaddr = fd_wksp_gaddr_fast( wksp, forest );
49 0 : forest->ver_gaddr = fd_wksp_gaddr_fast( wksp, fd_fseq_join ( fd_fseq_new ( ver, FD_FOREST_VER_UNINIT ) ) );
50 0 : forest->pool_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_pool_join ( fd_forest_pool_new ( pool, ele_max ) ) );
51 0 : forest->ancestry_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_ancestry_join( fd_forest_ancestry_new( ancestry, ele_max, seed ) ) );
52 0 : forest->frontier_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_frontier_join( fd_forest_frontier_new( frontier, ele_max, seed ) ) );
53 0 : forest->orphaned_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_orphaned_join( fd_forest_orphaned_new( orphaned, ele_max, seed ) ) );
54 :
55 0 : FD_COMPILER_MFENCE();
56 0 : FD_VOLATILE( forest->magic ) = FD_FOREST_MAGIC;
57 0 : FD_COMPILER_MFENCE();
58 :
59 0 : return shmem;
60 0 : }
61 :
62 : fd_forest_t *
63 0 : fd_forest_join( void * shforest ) {
64 0 : fd_forest_t * forest = (fd_forest_t *)shforest;
65 :
66 0 : if( FD_UNLIKELY( !forest ) ) {
67 0 : FD_LOG_WARNING(( "NULL forest" ));
68 0 : return NULL;
69 0 : }
70 :
71 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)forest, fd_forest_align() ) ) ) {
72 0 : FD_LOG_WARNING(( "misaligned forest" ));
73 0 : return NULL;
74 0 : }
75 :
76 0 : fd_wksp_t * wksp = fd_wksp_containing( forest );
77 0 : if( FD_UNLIKELY( !wksp ) ) {
78 0 : FD_LOG_WARNING(( "forest must be part of a workspace" ));
79 0 : return NULL;
80 0 : }
81 :
82 0 : return forest;
83 0 : }
84 :
85 : void *
86 0 : fd_forest_leave( fd_forest_t const * forest ) {
87 :
88 0 : if( FD_UNLIKELY( !forest ) ) {
89 0 : FD_LOG_WARNING(( "NULL forest" ));
90 0 : return NULL;
91 0 : }
92 :
93 0 : return (void *)forest;
94 0 : }
95 :
96 : void *
97 0 : fd_forest_delete( void * forest ) {
98 :
99 0 : if( FD_UNLIKELY( !forest ) ) {
100 0 : FD_LOG_WARNING(( "NULL forest" ));
101 0 : return NULL;
102 0 : }
103 :
104 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)forest, fd_forest_align() ) ) ) {
105 0 : FD_LOG_WARNING(( "misaligned forest" ));
106 0 : return NULL;
107 0 : }
108 :
109 : // TODO: zero out mem?
110 :
111 0 : return forest;
112 0 : }
113 :
114 : fd_forest_t *
115 0 : fd_forest_init( fd_forest_t * forest, ulong root_slot ) {
116 0 : FD_TEST( forest );
117 0 : FD_TEST( fd_fseq_query( fd_forest_ver( forest ) ) == FD_FOREST_VER_UNINIT );
118 :
119 0 : VER_INC;
120 :
121 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
122 0 : ulong null = fd_forest_pool_idx_null( pool );
123 0 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
124 :
125 : /* Initialize the root node from a pool element. */
126 :
127 0 : fd_forest_ele_t * root_ele = fd_forest_pool_ele_acquire( pool );
128 0 : root_ele->slot = root_slot;
129 0 : root_ele->prev = null;
130 0 : root_ele->parent = null;
131 0 : root_ele->child = null;
132 0 : root_ele->sibling = null;
133 0 : root_ele->buffered_idx = 0;
134 0 : root_ele->complete_idx = 0;
135 :
136 0 : fd_forest_ele_idxs_null( root_ele->idxs );
137 :
138 0 : forest->root = fd_forest_pool_idx( pool, root_ele );
139 0 : fd_forest_frontier_ele_insert( frontier, root_ele, pool ); /* cannot fail */
140 :
141 : /* Sanity checks. */
142 :
143 0 : FD_TEST( root_ele );
144 0 : FD_TEST( root_ele == fd_forest_frontier_ele_query( frontier, &root_slot, NULL, pool ));
145 0 : FD_TEST( root_ele->slot == root_slot );
146 :
147 0 : return forest;
148 0 : }
149 :
150 : void *
151 0 : fd_forest_fini( fd_forest_t * forest ) {
152 0 : fd_fseq_update( fd_forest_ver( forest ), FD_FOREST_VER_UNINIT );
153 0 : return (void *)forest;
154 0 : }
155 :
156 : int
157 0 : fd_forest_verify( fd_forest_t const * forest ) {
158 0 : if( FD_UNLIKELY( !forest ) ) {
159 0 : FD_LOG_WARNING(( "NULL forest" ));
160 0 : return -1;
161 0 : }
162 :
163 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)forest, fd_forest_align() ) ) ) {
164 0 : FD_LOG_WARNING(( "misaligned forest" ));
165 0 : return -1;
166 0 : }
167 :
168 0 : fd_wksp_t * wksp = fd_wksp_containing( forest );
169 0 : if( FD_UNLIKELY( !wksp ) ) {
170 0 : FD_LOG_WARNING(( "forest must be part of a workspace" ));
171 0 : return -1;
172 0 : }
173 :
174 0 : if( FD_UNLIKELY( forest->magic!=FD_FOREST_MAGIC ) ) {
175 0 : FD_LOG_WARNING(( "bad magic" ));
176 0 : return -1;
177 0 : }
178 :
179 0 : if( FD_UNLIKELY( fd_fseq_query( fd_forest_ver_const( forest ) ) == ULONG_MAX ) ) {
180 0 : FD_LOG_WARNING(( "forest uninitialized or invalid" ));
181 0 : return -1;
182 0 : }
183 :
184 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
185 0 : if( fd_forest_ancestry_verify( fd_forest_ancestry_const( forest ), fd_forest_pool_max( pool ), pool ) == -1 ) return -1;
186 0 : if( fd_forest_frontier_verify( fd_forest_frontier_const( forest ), fd_forest_pool_max( pool ), pool ) == -1 ) return -1;
187 :
188 0 : return 0;
189 0 : }
190 :
191 : /* query queries for a connected ele keyed by slot. does not return
192 : orphaned ele. */
193 :
194 : static fd_forest_ele_t *
195 0 : ancestry_frontier_query( fd_forest_t * forest, ulong slot ) {
196 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
197 0 : fd_forest_ele_t * ele = NULL;
198 0 : ele = fd_forest_ancestry_ele_query( fd_forest_ancestry( forest ), &slot, NULL, pool );
199 0 : ele = fd_ptr_if( !ele, fd_forest_frontier_ele_query( fd_forest_frontier( forest ), &slot, NULL, pool ), ele );
200 0 : return ele;
201 0 : }
202 :
203 : /* remove removes and returns a connected ele from ancestry or frontier
204 : maps. does not remove orphaned ele. does not unlink ele. */
205 :
206 : static fd_forest_ele_t *
207 0 : ancestry_frontier_remove( fd_forest_t * forest, ulong slot ) {
208 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
209 0 : fd_forest_ele_t * ele = NULL;
210 0 : ele = fd_forest_ancestry_ele_remove( fd_forest_ancestry( forest ), &slot, NULL, pool );
211 0 : ele = fd_ptr_if( !ele, fd_forest_frontier_ele_remove( fd_forest_frontier( forest ), &slot, NULL, pool ), ele );
212 0 : return ele;
213 0 : }
214 :
215 : /* link ele to the tree via its sibling. */
216 :
217 : static void
218 0 : link_sibling( fd_forest_t * forest, fd_forest_ele_t * sibling, fd_forest_ele_t * ele ) {
219 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
220 0 : ulong null = fd_forest_pool_idx_null( pool );
221 0 : while( FD_UNLIKELY( sibling->sibling != null )) sibling = fd_forest_pool_ele( pool, sibling->sibling );
222 0 : sibling->sibling = fd_forest_pool_idx( pool, ele );
223 0 : }
224 :
225 : /* link child to the tree via its parent. */
226 :
227 : static void
228 0 : link( fd_forest_t * forest, fd_forest_ele_t * parent, fd_forest_ele_t * child ) {
229 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
230 0 : ulong null = fd_forest_pool_idx_null( pool );
231 0 : if( FD_LIKELY( parent->child == null ) ) parent->child = fd_forest_pool_idx( pool, child ); /* left-child */
232 0 : else link_sibling( forest, fd_forest_pool_ele( pool, parent->child ), child ); /* right-sibling */
233 0 : child->parent = fd_forest_pool_idx( pool, parent );
234 0 : }
235 :
236 : /* link_orphans performs a BFS beginning from head using BFS. head is
237 : the first element of a linked list representing the BFS queue. If the
238 : starting orphan is connected to the ancestry tree (ie. its parent is
239 : in the map), it is linked to the tree and removed from the orphaned
240 : map, and any of its orphaned children are added to the queue (linking
241 : a parent also links its direct children). Otherwise it remains in the
242 : orphaned map. The BFS continues until the queue is empty. */
243 :
244 : FD_FN_UNUSED static void
245 0 : link_orphans( fd_forest_t * forest, fd_forest_ele_t * head ) {
246 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
247 0 : ulong null = fd_forest_pool_idx_null( pool );
248 0 : fd_forest_ancestry_t * ancestry = fd_forest_ancestry( forest );
249 0 : fd_forest_orphaned_t * orphaned = fd_forest_orphaned( forest );
250 0 : fd_forest_ele_t * tail = head;
251 0 : fd_forest_ele_t * prev = NULL;
252 0 : while( FD_LIKELY( head ) ) { /* while queue is non-empty */
253 0 : if( FD_LIKELY( fd_forest_orphaned_ele_remove( orphaned, &head->slot, NULL, pool ) ) ) { /* head is orphan root */
254 0 : fd_forest_ancestry_ele_insert( ancestry, head, pool );
255 0 : fd_forest_ele_t * child = fd_forest_pool_ele( pool, head->child );
256 0 : while( FD_LIKELY( child ) ) { /* append children to frontier */
257 0 : tail->prev = fd_forest_pool_idx( pool, child ); /* safe to overwrite prev */
258 0 : tail = fd_forest_pool_ele( pool, tail->prev );
259 0 : tail->prev = null;
260 0 : ulong sibling = child->sibling;
261 0 : child->sibling = null;
262 0 : child = fd_forest_pool_ele( pool, sibling );
263 0 : }
264 0 : }
265 0 : prev = head;
266 0 : head = fd_forest_pool_ele( pool, head->prev );
267 0 : prev->prev = null;
268 0 : }
269 0 : }
270 :
271 : /* advance_frontier attempts to advance the frontier beginning from slot
272 : using BFS. head is the first element of a linked list representing
273 : the BFS queue. A slot can be advanced if all shreds for the block
274 : are received ie. consumed_idx = complete_idx. */
275 :
276 : static void
277 0 : advance_frontier( fd_forest_t * forest, ulong slot, ushort parent_off ) {
278 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
279 0 : ulong null = fd_forest_pool_idx_null( pool );
280 0 : fd_forest_ancestry_t * ancestry = fd_forest_ancestry( forest );
281 0 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
282 :
283 0 : fd_forest_ele_t * ele;
284 0 : ele = fd_forest_frontier_ele_query( fd_forest_frontier( forest ), &slot, NULL, pool );
285 0 : ulong parent_slot = slot - parent_off;
286 0 : ele = fd_ptr_if( !ele, fd_forest_frontier_ele_query( fd_forest_frontier( forest ), &parent_slot, NULL, pool ), ele );
287 :
288 0 : fd_forest_ele_t * head = ele;
289 0 : fd_forest_ele_t * tail = head;
290 0 : fd_forest_ele_t * prev = NULL;
291 :
292 0 : while( FD_LIKELY( head ) ) {
293 0 : fd_forest_ele_t * child = fd_forest_pool_ele( pool, head->child );
294 0 : if( FD_LIKELY( child && head->complete_idx != UINT_MAX && head->buffered_idx == head->complete_idx ) ) {
295 0 : fd_forest_frontier_ele_remove( frontier, &head->slot, NULL, pool );
296 0 : fd_forest_ancestry_ele_insert( ancestry, head, pool );
297 0 : while( FD_LIKELY( child ) ) { /* append children to frontier */
298 0 : fd_forest_ancestry_ele_remove( ancestry, &child->slot, NULL, pool );
299 0 : fd_forest_frontier_ele_insert( frontier, child, pool );
300 0 : tail->prev = fd_forest_pool_idx( pool, child );
301 0 : tail = fd_forest_pool_ele( pool, tail->prev );
302 0 : tail->prev = fd_forest_pool_idx_null( pool );
303 0 : child = fd_forest_pool_ele( pool, child->sibling );
304 0 : }
305 0 : }
306 0 : prev = head;
307 0 : head = fd_forest_pool_ele( pool, head->prev );
308 0 : prev->prev = null;
309 0 : }
310 0 : }
311 :
312 : static fd_forest_ele_t *
313 0 : query( fd_forest_t * forest, ulong slot ) {
314 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
315 0 : fd_forest_ancestry_t * ancestry = fd_forest_ancestry( forest );
316 0 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
317 0 : fd_forest_orphaned_t * orphaned = fd_forest_orphaned( forest );
318 :
319 0 : fd_forest_ele_t * ele;
320 0 : ele = fd_forest_ancestry_ele_query( ancestry, &slot, NULL, pool );
321 0 : ele = fd_ptr_if( !ele, fd_forest_frontier_ele_query( frontier, &slot, NULL, pool ), ele );
322 0 : ele = fd_ptr_if( !ele, fd_forest_orphaned_ele_query( orphaned, &slot, NULL, pool ), ele );
323 0 : return ele;
324 0 : }
325 :
326 : static fd_forest_ele_t *
327 0 : acquire( fd_forest_t * forest, ulong slot ) {
328 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
329 0 : fd_forest_ele_t * ele = fd_forest_pool_ele_acquire( pool );
330 0 : ulong null = fd_forest_pool_idx_null( pool );
331 :
332 0 : ele->slot = slot;
333 0 : ele->prev = null;
334 0 : ele->next = null;
335 0 : ele->parent = null;
336 0 : ele->child = null;
337 0 : ele->sibling = null;
338 :
339 0 : ele->buffered_idx = UINT_MAX;
340 0 : ele->complete_idx = UINT_MAX;
341 :
342 0 : fd_forest_ele_idxs_null( ele->cmpl ); /* FIXME expensive */
343 0 : fd_forest_ele_idxs_null( ele->fecs ); /* FIXME expensive */
344 0 : fd_forest_ele_idxs_null( ele->idxs ); /* FIXME expensive */
345 :
346 0 : return ele;
347 0 : }
348 :
349 : static fd_forest_ele_t *
350 0 : insert( fd_forest_t * forest, ulong slot, ushort parent_off ) {
351 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
352 :
353 0 : # if FD_FOREST_USE_HANDHOLDING
354 0 : FD_TEST( parent_off <= slot ); /* caller err - inval */
355 0 : FD_TEST( fd_forest_pool_free( pool ) ); /* impl err - oom */
356 0 : FD_TEST( slot > fd_forest_root_slot( forest ) ); /* caller error - inval */
357 0 : # endif
358 :
359 0 : fd_forest_ele_t * ele = acquire( forest, slot );
360 0 : ulong parent_slot = slot - parent_off;
361 0 : fd_forest_ele_t * parent = query( forest, parent_slot );
362 0 : if( FD_LIKELY( parent ) ) {
363 0 : fd_forest_ancestry_ele_insert( fd_forest_ancestry( forest ), ele, pool );
364 0 : link( forest, parent, ele ); /* cannot fail */
365 :
366 : /* Edge case where we are creating a fork off of a node that is behind the frontier.
367 : We need to add this node to the frontier. */
368 :
369 0 : fd_forest_ele_t * ancestor = parent;
370 0 : while( ancestor /* ancestor exists */
371 0 : && !fd_forest_frontier_ele_query( fd_forest_frontier( forest ), &ancestor->slot, NULL, pool ) /* ancestor is not on frontier */
372 0 : && !fd_forest_orphaned_ele_query( fd_forest_orphaned( forest ), &ancestor->slot, NULL, pool ) /* ancestor is not an orphan */ ) {
373 0 : ancestor = fd_forest_pool_ele( pool, ancestor->parent );
374 0 : }
375 0 : if( FD_UNLIKELY( !ancestor ) ) {
376 : /* Did not find ancestor on frontier OR orphan, which means it must be behind the frontier barrier. */
377 0 : fd_forest_frontier_ele_insert( fd_forest_frontier( forest ), ele, pool );
378 0 : }
379 0 : }
380 0 : return ele;
381 0 : }
382 :
383 : fd_forest_ele_t *
384 0 : fd_forest_query( fd_forest_t * forest, ulong slot ) {
385 0 : # if FD_FOREST_USE_HANDHOLDING
386 0 : FD_TEST( slot > fd_forest_root_slot( forest ) ); /* caller error - inval */
387 0 : # endif
388 0 : return query( forest, slot );
389 0 : }
390 :
391 : fd_forest_ele_t *
392 0 : fd_forest_data_shred_insert( fd_forest_t * forest, ulong slot, ushort parent_off, uint shred_idx, uint fec_set_idx, FD_PARAM_UNUSED int data_complete, int slot_complete ) {
393 0 : # if FD_FOREST_USE_HANDHOLDING
394 0 : FD_TEST( slot > fd_forest_root_slot( forest ) ); /* caller error - inval */
395 0 : # endif
396 :
397 0 : VER_INC;
398 :
399 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
400 0 : fd_forest_ele_t * ele = query( forest, slot );
401 0 : if( FD_UNLIKELY( !ele ) ) ele = insert( forest, slot, parent_off ); /* cannot fail */
402 0 : if( FD_UNLIKELY( ele->parent == fd_forest_pool_idx_null( pool ) ) ) {
403 :
404 : /* `ele` is an orphan tree root so it does not have a parent. Now,
405 : having received a shred for ele, we know ele's parent
406 : slot. Here we check whether ele's parent is already in the tree.
407 : If it is, then the orphan tree rooted at ele can be linked to the
408 : tree containing ele's parent (which may be another orphan tree or
409 : the canonical tree). */
410 :
411 0 : fd_forest_ele_t * parent = query( forest, slot - parent_off );
412 0 : if( FD_UNLIKELY( !parent ) ) { /* parent is either in canonical or another orphan tree */
413 0 : parent = acquire( forest, slot - parent_off );
414 0 : fd_forest_orphaned_ele_insert( fd_forest_orphaned( forest ), parent, pool ); /* update orphan root */
415 0 : }
416 0 : fd_forest_orphaned_ele_remove( fd_forest_orphaned( forest ), &ele->slot, NULL, pool );
417 0 : fd_forest_ancestry_ele_insert( fd_forest_ancestry( forest ), ele, pool );
418 0 : link( forest, parent, ele );
419 0 : }
420 0 : fd_forest_ele_idxs_insert( ele->fecs, fec_set_idx );
421 0 : fd_forest_ele_idxs_insert( ele->idxs, shred_idx );
422 0 : while( fd_forest_ele_idxs_test( ele->idxs, ele->buffered_idx + 1U ) ) ele->buffered_idx++;
423 0 : ele->complete_idx = fd_uint_if( slot_complete, shred_idx, ele->complete_idx );
424 0 : advance_frontier( forest, slot, parent_off );
425 0 : return ele;
426 0 : }
427 :
428 : fd_forest_ele_t const *
429 0 : fd_forest_publish( fd_forest_t * forest, ulong new_root_slot ) {
430 0 : FD_LOG_DEBUG(( "[%s] slot %lu", __func__, new_root_slot ));
431 :
432 0 : VER_INC;
433 :
434 0 : fd_forest_ancestry_t * ancestry = fd_forest_ancestry( forest );
435 0 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
436 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
437 0 : ulong null = fd_forest_pool_idx_null( pool );
438 :
439 0 : fd_forest_ele_t * old_root_ele = fd_forest_pool_ele( pool, forest->root );
440 0 : fd_forest_ele_t * new_root_ele = ancestry_frontier_query( forest, new_root_slot );
441 :
442 0 : # if FD_FOREST_USE_HANDHOLDING
443 0 : FD_TEST( new_root_ele ); /* caller error - not found */
444 0 : FD_TEST( new_root_ele->slot > old_root_ele->slot ); /* caller error - inval */
445 0 : # endif
446 :
447 : /* First, remove the previous root, and add it to a FIFO prune queue.
448 : head points to the queue head (initialized with old_root_ele). */
449 :
450 0 : fd_forest_ele_t * head = ancestry_frontier_remove( forest, old_root_ele->slot );
451 0 : head->next = null;
452 0 : fd_forest_ele_t * tail = head;
453 :
454 : /* Second, BFS down the tree, inserting each ele into the prune queue
455 : except for the new root. Loop invariant: head always descends from
456 : old_root_ele and never descends from new_root_ele. */
457 :
458 0 : while( head ) {
459 0 : fd_forest_ele_t * child = fd_forest_pool_ele( pool, head->child );
460 0 : while( FD_LIKELY( child ) ) {
461 0 : if( FD_LIKELY( child != new_root_ele ) ) { /* do not prune new root or descendants */
462 0 : ulong idx = fd_forest_ancestry_idx_remove( ancestry, &child->slot, null, pool );
463 0 : idx = fd_ulong_if( idx != null, idx, fd_forest_frontier_idx_remove( frontier, &child->slot, null, pool ) );
464 0 : tail->next = idx; /* insert prune queue */
465 0 : # if FD_FOREST_USE_HANDHOLDING
466 0 : FD_TEST( tail->next != null ); /* programming error in BFS */
467 0 : # endif
468 0 : tail = fd_forest_pool_ele( pool, tail->next ); /* advance prune queue */
469 0 : tail->next = null;
470 0 : }
471 0 : child = fd_forest_pool_ele( pool, child->sibling );
472 0 : }
473 0 : fd_forest_ele_t * next = fd_forest_pool_ele( pool, head->next ); /* FIFO pop */
474 0 : fd_forest_pool_ele_release( pool, head ); /* free head */
475 0 : head = next;
476 0 : }
477 :
478 0 : new_root_ele->parent = null; /* unlink new root from parent */
479 0 : forest->root = fd_forest_ancestry_idx_query( ancestry, &new_root_slot, null, pool );
480 0 : return new_root_ele;
481 0 : }
482 :
483 : fd_forest_iter_t
484 0 : fd_forest_iter_init( fd_forest_t * forest ) {
485 : /* Find first element. Anything on the frontier. */
486 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
487 0 : fd_forest_frontier_t const * frontier = fd_forest_frontier_const( forest );
488 :
489 0 : fd_forest_frontier_iter_t frontier_iter = fd_forest_frontier_iter_init( frontier, pool );
490 0 : fd_forest_iter_t repair_iter = { fd_forest_pool_idx_null( pool ),
491 0 : UINT_MAX,
492 0 : fd_fseq_query( fd_forest_ver_const( forest ) ),
493 0 : frontier_iter };
494 : /* Nothing on frontier */
495 :
496 0 : if( FD_UNLIKELY( fd_forest_frontier_iter_done( frontier_iter, frontier, pool ) ) ) return repair_iter;
497 :
498 : /* Populate initial iter shred index */
499 :
500 0 : fd_forest_ele_t const * ele = fd_forest_frontier_iter_ele_const( frontier_iter, frontier, pool );
501 0 : while( ele->complete_idx != UINT_MAX && ele->buffered_idx == ele->complete_idx ) {
502 : /* This fork frontier is actually complete, so we can skip it. Also
503 : handles edge case where we are calling iter_init right after a
504 : forest_init */
505 0 : frontier_iter = fd_forest_frontier_iter_next( frontier_iter, frontier, pool );
506 0 : if( FD_UNLIKELY( fd_forest_frontier_iter_done( frontier_iter, frontier, pool ) ) ) {
507 0 : repair_iter.ele_idx = fd_forest_pool_idx_null( pool );
508 0 : repair_iter.shred_idx = UINT_MAX; /* no more elements */
509 0 : return repair_iter;
510 0 : }
511 0 : ele = fd_forest_frontier_iter_ele_const( frontier_iter, frontier, pool );
512 0 : }
513 :
514 0 : repair_iter.ele_idx = frontier_iter.ele_idx;
515 0 : repair_iter.shred_idx = ele->complete_idx == UINT_MAX ? UINT_MAX : ele->buffered_idx + 1;
516 :
517 0 : return repair_iter;
518 0 : }
519 :
520 : fd_forest_iter_t
521 0 : fd_forest_iter_next( fd_forest_iter_t iter, fd_forest_t const * forest ) {
522 0 : fd_forest_frontier_t const * frontier = fd_forest_frontier_const( forest );
523 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
524 0 : fd_forest_ele_t const * ele = fd_forest_pool_ele_const( pool, iter.ele_idx );
525 :
526 0 : if( iter.frontier_ver != fd_fseq_query( fd_forest_ver_const( forest ) ) ) {
527 : /* If the frontier has changed since we started this traversal, we
528 : need to reset the iterator. */
529 0 : iter.ele_idx = fd_forest_pool_idx_null( pool ) ;
530 0 : iter.shred_idx = UINT_MAX; /* no more elements */
531 0 : return iter;
532 0 : }
533 :
534 0 : uint next_shred_idx = iter.shred_idx;
535 0 : for(;;) {
536 0 : next_shred_idx++;
537 :
538 : /* Case 1: No more shreds in this slot to request, move to the
539 : next one. Wraparound the shred_idx.
540 :
541 : Case 2: original iter.shred_idx == UINT_MAX (implies prev req
542 : was a highest_window_idx request). Also requires moving to next
543 : slot and wrapping the shred_idx. */
544 :
545 0 : if( FD_UNLIKELY( next_shred_idx >= ele->complete_idx || iter.shred_idx == UINT_MAX ) ) {
546 0 : iter.ele_idx = ele->child;
547 0 : ele = fd_forest_pool_ele_const( pool, iter.ele_idx );
548 0 : if( FD_UNLIKELY( iter.ele_idx == fd_forest_pool_idx_null( pool ) ) ) {
549 0 : iter.shred_idx = UINT_MAX; /* no more elements */
550 :
551 : /* rare and unlikely to happen during a regular run, but if the
552 : frontier pool hasn't changed at all since we started this
553 : traversal, we can cleanly select the next node in the
554 : frontier using the stored frontier iterator. If the frontier
555 : has changed though, we should just return done and let the
556 : caller reset the iterator. */
557 :
558 0 : if( FD_UNLIKELY( iter.frontier_ver == fd_fseq_query( fd_forest_ver_const( forest ) ) ) ) {
559 0 : iter.head = fd_forest_frontier_iter_next( iter.head, frontier, pool );
560 0 : if( FD_UNLIKELY( !fd_forest_frontier_iter_done( iter.head, frontier, pool ) ) ) {
561 0 : iter.ele_idx = iter.head.ele_idx;
562 0 : ele = fd_forest_pool_ele_const( pool, iter.head.ele_idx );
563 0 : iter.shred_idx = ele->complete_idx == UINT_MAX ? UINT_MAX : ele->buffered_idx + 1;
564 0 : }
565 0 : }
566 0 : return iter;
567 0 : }
568 0 : next_shred_idx = ele->buffered_idx + 1;
569 0 : }
570 :
571 : /* Common case - valid shred to request. Note you can't know the
572 : ele->complete_idx until you have actually recieved the slot
573 : complete shred, thus the we can do lt instead of leq */
574 :
575 0 : if( ele->complete_idx != UINT_MAX &&
576 0 : next_shred_idx < ele->complete_idx &&
577 0 : !fd_forest_ele_idxs_test( ele->idxs, next_shred_idx ) ) {
578 0 : iter.shred_idx = next_shred_idx;
579 0 : break;
580 0 : }
581 :
582 : /* Current slot actually needs a highest_window_idx request */
583 :
584 0 : if( FD_UNLIKELY( ele->complete_idx == UINT_MAX ) ) {
585 0 : iter.shred_idx = UINT_MAX;
586 0 : break;
587 0 : }
588 0 : }
589 0 : return iter;
590 0 : }
591 :
592 : int
593 0 : fd_forest_iter_done( fd_forest_iter_t iter, fd_forest_t const * forest ) {
594 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
595 0 : return iter.ele_idx == fd_forest_pool_idx_null( pool ); /* no more elements */
596 0 : }
597 :
598 : #include <stdio.h>
599 :
600 : static void
601 0 : preorder( fd_forest_t const * forest, fd_forest_ele_t const * ele ) {
602 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
603 0 : fd_forest_ele_t const * child = fd_forest_pool_ele_const( pool, ele->child );
604 0 : printf( "%lu ", ele->slot );
605 0 : while( FD_LIKELY( child ) ) {
606 0 : preorder( forest, child );
607 0 : child = fd_forest_pool_ele_const( pool, child->sibling );
608 0 : }
609 0 : }
610 :
611 : void
612 0 : fd_forest_preorder_print( fd_forest_t const * forest ) {
613 0 : FD_LOG_NOTICE( ( "\n\n[Preorder]" ) );
614 0 : preorder( forest, fd_forest_pool_ele_const( fd_forest_pool_const( forest ), forest->root ) );
615 0 : printf( "\n\n" );
616 0 : }
617 :
618 : /* TODO use bit tricks / change */
619 : static int
620 0 : num_digits( ulong slot ) {
621 : /* using log10 */
622 0 : int digits = 0;
623 0 : while( slot ) {
624 0 : digits++;
625 0 : slot /= 10;
626 0 : }
627 0 : return digits;
628 0 : }
629 :
630 : static void
631 : ancestry_print2( fd_forest_t const * forest,
632 : fd_forest_ele_t const * ele,
633 : fd_forest_ele_t const * prev,
634 : ulong last_printed,
635 : int depth,
636 0 : const char * prefix ) {
637 :
638 0 : if( FD_UNLIKELY( ele == NULL ) ) return;
639 :
640 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
641 0 : int digits = num_digits( ele->slot );
642 :
643 : /* If there is a prefix, this means we are on a fork, and we need to
644 : indent to the correct depth. We do depth - 1 for more satisfying
645 : spacing. */
646 0 : if( FD_UNLIKELY( strcmp( prefix, "" ) ) ) {
647 0 : for( int i = 0; i < depth - 1; i++ ) printf( " " );
648 0 : if( depth > 0 ) printf( "%s", prefix );
649 0 : }
650 :
651 0 : if ( FD_UNLIKELY( !prev ) ) { // New interval
652 0 : printf("[%lu" , ele->slot );
653 0 : last_printed = ele->slot;
654 0 : depth += 1 + digits;
655 0 : }
656 :
657 0 : fd_forest_ele_t const * curr = fd_forest_pool_ele_const( pool, ele->child );
658 :
659 : /* Cases in which we close the interval:
660 : 1. the slots are no longer consecutive. no eliding, close bracket
661 : 2. current ele has multiple children, want to print forks.
662 : Maintain last_printed on this fork so that we don't print [a, a]
663 : intervals. */
664 :
665 0 : fd_forest_ele_t const * new_prev = ele;
666 :
667 0 : if( prev && prev->slot != ele->slot - 1 ) { // non-consecutive, do not elide
668 0 : if( last_printed == prev->slot ){
669 0 : printf( "] ── [%lu", ele->slot );
670 0 : depth += digits + 6;
671 0 : } else {
672 0 : printf( ", %lu] ── [%lu", prev->slot, ele->slot );
673 0 : depth += digits + num_digits(prev->slot ) + 8;
674 0 : }
675 0 : last_printed = ele->slot;
676 0 : } else if( curr && curr->sibling != ULONG_MAX ) { // has multiple children, do not elide
677 0 : if( last_printed == ele->slot ){
678 0 : printf( "] ── " );
679 0 : depth += 5;
680 0 : } else {
681 0 : printf( ", %lu] ── ", ele->slot );
682 0 : depth += digits + 2;
683 0 : }
684 0 : last_printed = ele->slot;
685 0 : new_prev = NULL;
686 0 : }
687 :
688 0 : if( !curr ){ // no children, close bracket, end fork
689 0 : if( last_printed == ele->slot ){
690 0 : printf( "]\n" );
691 0 : } else {
692 0 : printf( ", %lu]\n", ele->slot );
693 0 : }
694 0 : return;
695 0 : }
696 :
697 0 : char new_prefix[512]; /* FIXME size this correctly */
698 0 : new_prefix[0] = '\0'; /* first fork stays on the same line, no prefix */
699 0 : while( curr ) {
700 0 : if( fd_forest_pool_ele_const( pool, curr->sibling ) ) {
701 0 : ancestry_print2( forest, curr, new_prev, last_printed, depth, new_prefix );
702 0 : } else {
703 0 : ancestry_print2( forest, curr, new_prev, last_printed, depth, new_prefix );
704 0 : }
705 0 : curr = fd_forest_pool_ele_const( pool, curr->sibling );
706 :
707 : /* Set up prefix for following iterations */
708 0 : if( curr && curr->sibling != ULONG_MAX ) {
709 0 : sprintf( new_prefix, "├── " ); /* any following forks start on new lines */
710 0 : } else {
711 0 : sprintf( new_prefix, "└── " ); /* any following forks start on new lines */
712 0 : }
713 0 : }
714 :
715 0 : }
716 :
717 : static void FD_FN_UNUSED
718 0 : ancestry_print( fd_forest_t const * forest, fd_forest_ele_t const * ele, int space, const char * prefix ) {
719 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
720 0 :
721 0 : if( ele == NULL ) return;
722 0 :
723 0 : if( space > 0 ) printf( "\n" );
724 0 : for( int i = 0; i < space; i++ ) printf( " " );
725 0 : if ( ele->complete_idx == UINT_MAX ) printf( "%s%lu (%u/?)", prefix, ele->slot, ele->buffered_idx + 1 );
726 0 : else printf( "%s%lu (%u/%u)", prefix, ele->slot, ele->buffered_idx + 1, ele->complete_idx + 1 );
727 0 :
728 0 : fd_forest_ele_t const * curr = fd_forest_pool_ele_const( pool, ele->child );
729 0 :
730 0 : char new_prefix[1024]; /* FIXME size this correctly */
731 0 : while( curr ) {
732 0 : if( fd_forest_pool_ele_const( pool, curr->sibling ) ) {
733 0 : sprintf( new_prefix, "├── " ); /* branch indicating more siblings follow */
734 0 : ancestry_print( forest, curr, space + 4, new_prefix );
735 0 : } else {
736 0 : sprintf( new_prefix, "└── " ); /* end branch */
737 0 : ancestry_print( forest, curr, space + 4, new_prefix );
738 0 : }
739 0 : curr = fd_forest_pool_ele_const( pool, curr->sibling );
740 0 : }
741 0 : }
742 :
743 : static void
744 0 : ancestry_print3( fd_forest_t const * forest, fd_forest_ele_t const * ele, int space, const char * prefix, fd_forest_ele_t const * prev, int elide ) {
745 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
746 :
747 0 : if( ele == NULL ) return;
748 :
749 : /* print the slot itself. either we might need to start a new interval, or it may get elided */
750 0 : fd_forest_ele_t const * child = fd_forest_pool_ele_const( pool, ele->child );
751 :
752 0 : if( !elide ) {
753 0 : if( space > 0 ) printf( "\n" );
754 0 : for( int i = 0; i < space; i++ ) printf( " " );
755 0 : printf( "%s", prefix );
756 0 : printf( "%lu", ele->slot );
757 0 : }
758 :
759 0 : if( !child && !elide ) { /* double check these cases arent the same...*/
760 0 : printf( "]" );
761 0 : return;
762 0 : } /* no children, close bracket */
763 :
764 0 : if( !child && elide ) {
765 0 : printf( ", %lu]", ele->slot );
766 0 : return;
767 0 : }
768 :
769 0 : prev = ele;
770 0 : char new_prefix[1024]; /* FIXME size this correctly */
771 0 : int one_child = child && child->sibling == ULONG_MAX;
772 0 : if( one_child &&
773 0 : child->slot != ele->slot + 1 ) { // if I have ONE CHILD and one child is non-consecutive
774 :
775 0 : if( elide ) {
776 : /* current slot wasn't printed, but now that we are branching,
777 : we will want to print the current slot and close the bracket */
778 0 : printf( ", %lu]", ele->slot );
779 0 : space += fd_int_max( num_digits( ele->slot ) + 2, 0 );
780 0 : } else {
781 0 : printf( "]");
782 0 : }
783 :
784 0 : sprintf( new_prefix, "└── [" ); /* end branch */
785 0 : ancestry_print3( forest, child, space + 5, new_prefix, prev, 0 );
786 0 : } else if ( one_child && child->slot == ele->slot + 1 ) {
787 0 : ancestry_print3( forest, child, space, prefix, prev, 1);
788 0 : } else { /* multiple children */
789 0 : if( elide ) {
790 : /* current slot wasn't printed, but now that we are branching,
791 : we will want to print the current slot and close the bracket */
792 0 : printf( ", %lu]", ele->slot );
793 0 : space += fd_int_max( num_digits( ele->slot ) + 2, 0 );
794 0 : } else {
795 0 : printf( "]");
796 0 : }
797 :
798 0 : while( child ) {
799 0 : if( fd_forest_pool_ele_const( pool, child->sibling ) ) {
800 0 : sprintf( new_prefix, "├── [" ); /* branch indicating more siblings follow */
801 0 : ancestry_print3( forest, child, space + 5, new_prefix, prev, 0 );
802 0 : } else {
803 0 : sprintf( new_prefix, "└── [" ); /* end branch */
804 0 : ancestry_print3( forest, child, space + 5, new_prefix, prev, 0 );
805 0 : }
806 0 : child = fd_forest_pool_ele_const( pool, child->sibling );
807 0 : }
808 0 : }
809 0 : }
810 :
811 : void
812 0 : fd_forest_ancestry_print( fd_forest_t const * forest ) {
813 0 : FD_LOG_NOTICE(("\n\n[Ancestry]\n\n" ) );
814 :
815 0 : ancestry_print3( forest, fd_forest_pool_ele_const( fd_forest_pool_const( forest ), forest->root ), 0, "[", NULL, 0 );
816 : //ancestry_print( forest, fd_forest_pool_ele_const( fd_forest_pool_const( forest ), forest->root ), 0, "" );
817 :
818 0 : }
819 :
820 : void
821 0 : fd_forest_frontier_print( fd_forest_t const * forest ) {
822 0 : printf( "\n\n[Frontier]\n" );
823 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
824 0 : fd_forest_frontier_t const * frontier = fd_forest_frontier_const( forest );
825 0 : for( fd_forest_frontier_iter_t iter = fd_forest_frontier_iter_init( frontier, pool );
826 0 : !fd_forest_frontier_iter_done( iter, frontier, pool );
827 0 : iter = fd_forest_frontier_iter_next( iter, frontier, pool ) ) {
828 0 : fd_forest_ele_t const * ele = fd_forest_frontier_iter_ele_const( iter, frontier, pool );
829 0 : printf("%lu (%u/%u)\n", ele->slot, ele->buffered_idx + 1, ele->complete_idx + 1 );
830 : //ancestry_print( forest, fd_forest_pool_ele_const( fd_forest_pool_const( forest ), fd_forest_pool_idx( pool, ele ) ), 0, "" );
831 0 : }
832 0 : }
833 :
834 : void
835 0 : fd_forest_orphaned_print( fd_forest_t const * forest ) {
836 0 : printf( "\n\n[Orphaned]\n" );
837 0 : fd_forest_orphaned_t const * orphaned = fd_forest_orphaned_const( forest );
838 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
839 0 : for( fd_forest_orphaned_iter_t iter = fd_forest_orphaned_iter_init( orphaned, pool );
840 0 : !fd_forest_orphaned_iter_done( iter, orphaned, pool );
841 0 : iter = fd_forest_orphaned_iter_next( iter, orphaned, pool ) ) {
842 0 : fd_forest_ele_t const * ele = fd_forest_orphaned_iter_ele_const( iter, orphaned, pool );
843 0 : ancestry_print2( forest, fd_forest_pool_ele_const( fd_forest_pool_const( forest ), fd_forest_pool_idx( pool, ele ) ), NULL, 0, 0, "" );
844 0 : }
845 0 : }
846 :
847 : void
848 0 : fd_forest_print( fd_forest_t const * forest ) {
849 0 : if( FD_UNLIKELY( forest->root == ULONG_MAX ) ) return;
850 0 : fd_forest_ancestry_print( forest );
851 0 : fd_forest_frontier_print( forest );
852 0 : fd_forest_orphaned_print( forest );
853 0 : printf("\n\n");
854 0 : }
|
