Line data    Source code

       1             : #include "fd_wksp_private.h"
       2             : 
       3             : ulong
       4             : fd_wksp_private_free_treap_query( ulong                     sz,
       5             :                                   fd_wksp_t *               wksp,
       6   229490871 :                                   fd_wksp_private_pinfo_t * pinfo ) {
       7   229490871 :   if( FD_UNLIKELY( !sz ) ) return FD_WKSP_PRIVATE_PINFO_IDX_NULL;
       8             : 
       9   227249298 :   ulong f = FD_WKSP_PRIVATE_PINFO_IDX_NULL;
      10             : 
      11   227249298 :   ulong part_max  = wksp->part_max;
      12   227249298 :   ulong cycle_tag = wksp->cycle_tag++;
      13             : 
      14   227249298 :   ulong i = fd_wksp_private_pinfo_idx( wksp->part_free_cidx );
      15  1376267106 :   while( !fd_wksp_private_pinfo_idx_is_null( i ) ) {
      16  1222590105 :     if( FD_UNLIKELY( i>=part_max                     ) ) return FD_WKSP_PRIVATE_PINFO_IDX_NULL; /* Bad index */
      17  1222590105 :     if( FD_UNLIKELY( pinfo[ i ].cycle_tag==cycle_tag ) ) return FD_WKSP_PRIVATE_PINFO_IDX_NULL; /* Cycle detected */
      18  1222590105 :     pinfo[ i ].cycle_tag = cycle_tag;                                                           /* Mark i as visited */
      19             :    
      20  1222590105 :     ulong part_sz = fd_wksp_private_pinfo_sz( pinfo + i );
      21  1222590105 :     if( sz>part_sz ) i = fd_wksp_private_pinfo_idx( pinfo[ i ].right_cidx ); /* Partition list and left too small, go right */
      22   618164919 :     else {
      23   618164919 :       f = i; /* If all else fails, partitions of this sz will work */
      24   618164919 :       if( sz==part_sz ) break; /* Exact match (we aren't going to find anything better to our left) */
      25   544592622 :       i = fd_wksp_private_pinfo_idx( pinfo[ i ].left_cidx );
      26   544592622 :     }
      27  1222590105 :   }
      28             : 
      29   227249298 :   return f;
      30   227249298 : }
      31             : 
      32  7857657600 : #define TEST(c) do { if( FD_UNLIKELY( !(c) ) ) { /*FD_LOG_WARNING(( "FAIL: %s", #c ));*/ return FD_WKSP_ERR_CORRUPT; } } while(0)
      33             : 
      34  3564317529 : #define TEST_AND_MARK( i ) do {                                                                              \
      35  3564317529 :     ulong _i = (i);                                                                                          \
      36  3564317529 :     TEST( fd_wksp_private_pinfo_idx_is_null( _i ) | ((_i<part_max) && (pinfo[ _i ].cycle_tag!=cycle_tag)) ); \
      37  3564317529 :     if( !fd_wksp_private_pinfo_idx_is_null( _i ) ) pinfo[ _i ].cycle_tag = cycle_tag;                        \
      38  3546564162 :   } while(0)
      39             : 
      40  3192891129 : #define TEST_PARENT( i, p ) do {                                                       \
      41  3192891129 :     ulong _i = (i);                                                                    \
      42  3192891129 :     if( _i<part_max ) TEST( fd_wksp_private_pinfo_idx( pinfo[_i].parent_cidx )==(p) ); \
      43  3192891129 :   } while(0)
      44             : 
      45             : int
      46             : fd_wksp_private_free_treap_insert( ulong                     n,
      47             :                                    fd_wksp_t *               wksp,
      48   246507231 :                                    fd_wksp_private_pinfo_t * pinfo ) {
      49             : 
      50   246507231 :   ulong part_max  = wksp->part_max;
      51   246507231 :   ulong cycle_tag = wksp->cycle_tag++;
      52             : 
      53   246507231 :   TEST( n<part_max );               /* Make sure valid n */
      54   246507231 :   pinfo[ n ].cycle_tag = cycle_tag; /* Mark n */
      55             : 
      56   246507231 :   ulong g0 = pinfo[ n ].gaddr_lo;
      57   246507231 :   ulong g1 = pinfo[ n ].gaddr_hi;
      58   246507231 :   ulong n_sz = g1 - g0;
      59             : 
      60   246507231 :   TEST( (wksp->gaddr_lo<=g0) & (g0<g1) & (g1<=wksp->gaddr_hi) ); /* Make sure valid range */
      61             : 
      62             :   /* Note: non-zero tag is okay temporarily.  We assume the caller
      63             :      will set the tag to non-zero immediately afterward to make the
      64             :      allocation "official". */
      65             : 
      66   246507231 :   uint * _p_child_cidx = &wksp->part_free_cidx;
      67             : 
      68   246507231 :   ulong i = fd_wksp_private_pinfo_idx( *_p_child_cidx ); TEST_AND_MARK( i );
      69             : 
      70             :   /* If an empty treap, make n the root and we are done */
      71             : 
      72   245913420 :   if( FD_UNLIKELY( fd_wksp_private_pinfo_idx_is_null( i ) ) ) { /* Assume lots of free partitions typically */
      73     4114173 :     pinfo[ n ].in_same     = 0U;
      74     4114173 :     pinfo[ n ].left_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
      75     4114173 :     pinfo[ n ].right_cidx  = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
      76     4114173 :     pinfo[ n ].same_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
      77     4114173 :     pinfo[ n ].parent_cidx = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
      78     4114173 :     *_p_child_cidx = fd_wksp_private_pinfo_cidx( n );
      79     4114173 :     return FD_WKSP_SUCCESS;
      80     4114173 :   }
      81             : 
      82   241799247 :   TEST_PARENT( i, FD_WKSP_PRIVATE_PINFO_IDX_NULL ); /* Make sure good parent link */
      83             : 
      84             :   /* Find the leaf node where we can insert n */
      85             : 
      86             :   /* TODO: Consider pushing path down onto stack and bubble up
      87             :      using the stack? */
      88             : 
      89  1106897562 :   for(;;) {
      90             : 
      91  1106897562 :     TEST( !pinfo[ i ].in_same );
      92             : 
      93             :     /* At this point, i is a valid marked index with good parent
      94             :        connectivity.  TODO: Consider validating ranges of visited nodes
      95             :        and tags of visited nodes */
      96             : 
      97             :     /* We need to validate both left and right child links to make the
      98             :        bubble up phase robust (because we do that after we actually have
      99             :        inserted). */
     100             : 
     101  1106897562 :     ulong l = fd_wksp_private_pinfo_idx( pinfo[ i ].left_cidx  ); TEST_AND_MARK( l ); TEST_PARENT( l, i );
     102  1097863008 :     ulong r = fd_wksp_private_pinfo_idx( pinfo[ i ].right_cidx ); TEST_AND_MARK( r ); TEST_PARENT( r, i );
     103             : 
     104  1089738006 :     ulong i_sz = fd_wksp_private_pinfo_sz( pinfo + i );
     105             : 
     106  1089738006 :     int go_left = (n_sz < i_sz);
     107  1089738006 :     if( go_left ) {
     108   483997932 :       _p_child_cidx = &pinfo[ i ].left_cidx;
     109   483997932 :       if( fd_wksp_private_pinfo_idx_is_null( l ) ) break;
     110   419671320 :       i = l;
     111   419671320 :       continue;
     112   483997932 :     }
     113             : 
     114   605740074 :     int go_right = (n_sz > i_sz);
     115   605740074 :     if( go_right ) {
     116   518661027 :       _p_child_cidx = &pinfo[ i ].right_cidx;
     117   518661027 :       if( fd_wksp_private_pinfo_idx_is_null( r ) ) break;
     118   445426995 :       i = r;
     119   445426995 :       continue;
     120   518661027 :     }
     121             : 
     122             :     /* n and i have the same size.  Insert into i's same list */
     123             : 
     124    87079047 : #   if 1 /* This doesn't validate whether or not n is already in same list.  But it is O(1). */
     125             : 
     126    87079047 :     ulong j = fd_wksp_private_pinfo_idx( pinfo[ i ].same_cidx ); TEST_AND_MARK( j );
     127             : 
     128    87079047 :     pinfo[ n ].in_same     = 1U;
     129    87079047 :     pinfo[ n ].left_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     130    87079047 :     pinfo[ n ].right_cidx  = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     131    87079047 :     pinfo[ n ].same_cidx   = fd_wksp_private_pinfo_cidx( j );
     132    87079047 :     pinfo[ n ].parent_cidx = fd_wksp_private_pinfo_cidx( i );
     133             : 
     134             :     /**/                                          pinfo[ i ].same_cidx   = fd_wksp_private_pinfo_cidx( n );
     135    87079047 :     if( !fd_wksp_private_pinfo_idx_is_null( j ) ) pinfo[ j ].parent_cidx = fd_wksp_private_pinfo_cidx( n );
     136             : 
     137             : #   else /* This does but it is O(same_list_length). */
     138             : 
     139             :     ulong j = i;
     140             :     for(;;) {
     141             :       ulong k = fd_wksp_private_pinfo_idx( pinfo[ j ].same_cidx ); TEST_AND_MARK( k );
     142             :       if( fd_wksp_private_pinfo_idx_is_null( k ) ) break;
     143             :       TEST( fd_wksp_private_pinfo_idx( pinfo[ k ].parent_cidx )==j ); /* Make sure good prev */
     144             :       j = k;
     145             :     } 
     146             : 
     147             :     pinfo[ n ].in_same     = 1U;
     148             :     pinfo[ n ].left_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     149             :     pinfo[ n ].right_cidx  = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     150             :     pinfo[ n ].same_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     151             :     pinfo[ n ].parent_cidx = fd_wksp_private_pinfo_cidx( j );
     152             : 
     153             :     pinfo[ j ].same_cidx = fd_wksp_private_pinfo_cidx( n );
     154             : 
     155             : #   endif
     156             : 
     157    87079047 :     return FD_WKSP_SUCCESS;
     158    87079047 :   }
     159             : 
     160             :   /* Make n the appropriate child of i.  This might momentarily break
     161             :      the heap property. */
     162             : 
     163   137560644 :   pinfo[ n ].in_same     = 0U;
     164   137560644 :   pinfo[ n ].left_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     165   137560644 :   pinfo[ n ].right_cidx  = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     166   137560644 :   pinfo[ n ].same_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     167   137560644 :   pinfo[ n ].parent_cidx = fd_wksp_private_pinfo_cidx( i );
     168   137560644 :   *_p_child_cidx         = fd_wksp_private_pinfo_cidx( n );
     169             : 
     170             :   /* Bubble n up until the heap property is restored.  Note that in the
     171             :      traversal above, we also validated parent links for this traversal
     172             :      (so that we could insert without worrying about encountering
     173             :      unpleasantness after we changed the treap). */
     174             : 
     175   347348895 :   while( !fd_wksp_private_pinfo_idx_is_null( i ) ) {
     176   334529976 :     uint n_prio = pinfo[ n ].heap_prio;
     177   334529976 :     uint i_prio = pinfo[ i ].heap_prio;
     178   334529976 :     int heap_intact = (n_prio < i_prio) | ((n_prio==i_prio) & (!((n ^ i) & 1UL))); /* Flip coin on equal priority */
     179   334529976 :     if( heap_intact ) break;
     180             : 
     181   209788251 :     ulong nl = fd_wksp_private_pinfo_idx( pinfo[ n ].left_cidx   ); /* Validated above */
     182   209788251 :     ulong nr = fd_wksp_private_pinfo_idx( pinfo[ n ].right_cidx  ); /* Validated above */
     183   209788251 :     ulong il = fd_wksp_private_pinfo_idx( pinfo[ i ].left_cidx   ); /* Validated above */
     184             :   //ulong ir = fd_wksp_private_pinfo_idx( pinfo[ i ].right_cidx  ); /* Validated above */
     185   209788251 :     ulong p  = fd_wksp_private_pinfo_idx( pinfo[ i ].parent_cidx ); /* Validated above */
     186   209788251 :     _p_child_cidx = fd_wksp_private_pinfo_idx_is_null( p )                 ? &wksp->part_free_cidx 
     187   209788251 :                   : (fd_wksp_private_pinfo_idx( pinfo[ p ].left_cidx )==i) ? &pinfo[ p ].left_cidx   /* Validated above */
     188   196969332 :                   :                                                          &pinfo[ p ].right_cidx;
     189             : 
     190   209788251 :     int left_child = (il==n);
     191   209788251 :     if( left_child ) { /* 50/50 unpredictable */
     192             : 
     193    94534689 :       pinfo[ n ].right_cidx  = fd_wksp_private_pinfo_cidx( i  ); pinfo[ i ].parent_cidx = fd_wksp_private_pinfo_cidx( n  );
     194    94534689 :       pinfo[ n ].parent_cidx = fd_wksp_private_pinfo_cidx( p  ); *_p_child_cidx         = fd_wksp_private_pinfo_cidx( n );
     195             : 
     196    94534689 :       pinfo[ i ].left_cidx = fd_wksp_private_pinfo_cidx( nr );
     197    94534689 :       if( !fd_wksp_private_pinfo_idx_is_null( nr ) ) pinfo[ nr ].parent_cidx = fd_wksp_private_pinfo_cidx( i );
     198             : 
     199   115253562 :     } else {
     200             : 
     201   115253562 :       pinfo[ n ].left_cidx   = fd_wksp_private_pinfo_cidx( i  ); pinfo[ i  ].parent_cidx = fd_wksp_private_pinfo_cidx( n );
     202   115253562 :       pinfo[ n ].parent_cidx = fd_wksp_private_pinfo_cidx( p  ); *_p_child_cidx          = fd_wksp_private_pinfo_cidx( n );
     203             : 
     204   115253562 :       pinfo[ i ].right_cidx = fd_wksp_private_pinfo_cidx( nl );
     205   115253562 :       if( !fd_wksp_private_pinfo_idx_is_null( nl ) ) pinfo[ nl ].parent_cidx = fd_wksp_private_pinfo_cidx( i );
     206             : 
     207   115253562 :     }
     208             : 
     209   209788251 :     i = p;
     210   209788251 :   }
     211             : 
     212   137560644 :   return FD_WKSP_SUCCESS;
     213   241799247 : }
     214             : 
     215             : int
     216             : fd_wksp_private_free_treap_remove( ulong                     d,
     217             :                                    fd_wksp_t *               wksp,
     218   262479813 :                                    fd_wksp_private_pinfo_t * pinfo ) {
     219             : 
     220   262479813 :   ulong part_max  = wksp->part_max;
     221   262479813 :   ulong cycle_tag = wksp->cycle_tag++;
     222             : 
     223   262479813 :   TEST( d<part_max );
     224   262479813 :   pinfo[ d ].cycle_tag = cycle_tag; /* Mark d */
     225             : 
     226             :   /* If d is in a same list, remove it */
     227             : 
     228   262479813 :   ulong j = fd_wksp_private_pinfo_idx( pinfo[ d ].same_cidx ); TEST_AND_MARK( j ); TEST_PARENT( j, d );
     229             : 
     230   262479813 :   if( pinfo[ d ].in_same ) {
     231    55300539 :     ulong i = fd_wksp_private_pinfo_idx( pinfo[ d ].parent_cidx ); TEST_AND_MARK( i );
     232             : 
     233    55300539 :     TEST( !fd_wksp_private_pinfo_idx_is_null( i ) );
     234    55300539 :     TEST( pinfo[ i ].same_cidx==d );
     235             : 
     236    55300539 :     if( !fd_wksp_private_pinfo_idx_is_null( j ) ) pinfo[ j ].parent_cidx = fd_wksp_private_pinfo_cidx( i );
     237    55300539 :     pinfo[ i ].same_cidx = fd_wksp_private_pinfo_cidx( j );
     238    55300539 :     goto done;
     239    55300539 :   }
     240             : 
     241             :   /* d is not in a same list.  Load and validate the environment
     242             :      surrounding d. */
     243             : 
     244   207179274 :   ulong l = fd_wksp_private_pinfo_idx( pinfo[ d ].left_cidx   ); TEST_AND_MARK( l ); TEST_PARENT( l, d );
     245   207179274 :   ulong r = fd_wksp_private_pinfo_idx( pinfo[ d ].right_cidx  ); TEST_AND_MARK( r ); TEST_PARENT( r, d );
     246   207179274 :   ulong p = fd_wksp_private_pinfo_idx( pinfo[ d ].parent_cidx ); TEST_AND_MARK( p );
     247             : 
     248   207179274 :   uint * _p_child_cidx;
     249   207179274 :   if( fd_wksp_private_pinfo_idx_is_null( p ) ) {
     250    55862724 :     _p_child_cidx = &wksp->part_free_cidx;
     251    55862724 :     TEST( (*_p_child_cidx)==d );
     252   151316550 :   } else {
     253   151316550 :     ulong pl = fd_wksp_private_pinfo_idx( pinfo[ p ].left_cidx  ); /* One should be marked from above */
     254   151316550 :     ulong pr = fd_wksp_private_pinfo_idx( pinfo[ p ].right_cidx ); /* The other should not. */
     255   151316550 :     int is_left_child  = (pl==d);
     256   151316550 :     int is_right_child = (pr==d);
     257   151316550 :     TEST( is_left_child!=is_right_child );
     258   151316148 :     _p_child_cidx = fd_ptr_if( is_left_child, &pinfo[ p ].left_cidx, &pinfo[ p ].right_cidx );
     259   151316148 :   }
     260             : 
     261             :   /* If d has non-empty same list, fill the hole made by removing d with
     262             :      the first partition in d's same list.  This might break the heap
     263             :      property.  Instead of doing a bunch of bubbling, since d already
     264             :      had a valid heap priority, we just swap the heap priorities of j
     265             :      with the heap priority of d. */
     266             : 
     267   169687011 :   if( !fd_wksp_private_pinfo_idx_is_null( j ) ) {
     268    28021728 :     pinfo[ j ].in_same     = 0U;
     269    28021728 :     pinfo[ j ].left_cidx   = fd_wksp_private_pinfo_cidx( l );
     270    28021728 :     pinfo[ j ].right_cidx  = fd_wksp_private_pinfo_cidx( r );
     271    28021728 :     pinfo[ j ].parent_cidx = fd_wksp_private_pinfo_cidx( p );
     272             :   //pinfo[ j ].same_cidx unchanged
     273             : 
     274    28021728 :     uint j_prio = pinfo[ j ].heap_prio;
     275    28021728 :     uint d_prio = pinfo[ d ].heap_prio;
     276    28021728 :     pinfo[ j ].heap_prio = d_prio & ((1UL<<31)-1UL); /* Quell dubious compiler warning */
     277    28021728 :     pinfo[ d ].heap_prio = j_prio & ((1UL<<31)-1UL); /* " */
     278             : 
     279    28021728 :     if( !fd_wksp_private_pinfo_idx_is_null( l ) ) pinfo[ l ].parent_cidx = fd_wksp_private_pinfo_cidx( j );
     280    28021728 :     if( !fd_wksp_private_pinfo_idx_is_null( r ) ) pinfo[ r ].parent_cidx = fd_wksp_private_pinfo_cidx( j );
     281    28021728 :     *_p_child_cidx = fd_wksp_private_pinfo_cidx( j );
     282             : 
     283    28021728 :     goto done;
     284    28021728 :   }
     285             : 
     286   228317790 :   for(;;) {
     287             : 
     288             :     /* At this point, d is the only partition of its size and we have a
     289             :        non-trivial hole to fill.
     290             : 
     291             :        i and j are IDX_NULL as d has no same sized partitions
     292             :        l is the hole's left subtree (if any), validated and marked
     293             :        r is the hole's right subtree (if any), validated and marked
     294             :        p is the hole's parent (if any), if non-NULL, validated and marked
     295             : 
     296             :        _p_child_cidx is the location of link from the parent to the hole
     297             :        (or the pointer to the tree root if d is the root), validated. */
     298             : 
     299             :     /* If the hole has no left subtree (and maybe no right subtree and
     300             :        maybe no parent), fill the hole with the right subtree (or with
     301             :        nothing if no right subtree) and we are done. */
     302             : 
     303   228317790 :     if( fd_wksp_private_pinfo_idx_is_null( l ) ) {
     304    95653467 :       if( !fd_wksp_private_pinfo_idx_is_null( r ) ) pinfo[ r ].parent_cidx = fd_wksp_private_pinfo_cidx( p );
     305    95653467 :       *_p_child_cidx = fd_wksp_private_pinfo_cidx( r );
     306    95653467 :       break;
     307    95653467 :     }
     308             : 
     309             :     /* If the hole has no right subtree but has a left subtree (and
     310             :        maybe no parent), fill the hole with the left subtree and we are
     311             :        done. */
     312             : 
     313   132664323 :     if( fd_wksp_private_pinfo_idx_is_null( r ) ) {
     314    46011816 :       pinfo[ l ].parent_cidx = fd_wksp_private_pinfo_cidx( p );
     315    46011816 :       *_p_child_cidx = fd_wksp_private_pinfo_cidx( l );
     316    46011816 :       break;
     317    46011816 :     }
     318             : 
     319             :     /* At this point, we have to push the hole down the left or right
     320             :        subtree (and we still maybe have no parent).  We use the heap
     321             :        priorities to decide such that we preserve the heap property (we
     322             :        flip a coin on equal priorities).  We ultimately can omit any
     323             :        link updates involving d as these will be replaced with correct
     324             :        links before this returns. */
     325             : 
     326    86652507 :     uint l_prio = pinfo[ l ].heap_prio;
     327    86652507 :     uint r_prio = pinfo[ r ].heap_prio;
     328             : 
     329    86652507 :     int promote_left = (l_prio>r_prio) | ((l_prio==r_prio) & (!((p ^ d) & 1UL)));
     330    86652507 :     if( promote_left ) {
     331             : 
     332    46999794 :       ulong t = fd_wksp_private_pinfo_idx( pinfo[ l ].right_cidx ); TEST_AND_MARK( t ); TEST_PARENT( t, l );
     333             : 
     334    46999794 :       *_p_child_cidx        = fd_wksp_private_pinfo_cidx( l ); pinfo[ l ].parent_cidx = fd_wksp_private_pinfo_cidx( p );
     335             :     //pinfo[ l ].right_cidx = fd_wksp_private_pinfo_cidx( d ); pinfo[ d ].parent_cidx = fd_wksp_private_pinfo_cidx( l );
     336             :     //pinfo[ d ].left_cidx  = fd_wksp_private_pinfo_cidx( t );
     337             :     //if( !fd_wksp_private_pinfo_idx_is_null( t ) ) pinfo[ t ].parent_cidx = fd_wksp_private_pinfo_cidx( d );
     338             : 
     339    46999794 :       _p_child_cidx = &pinfo[ l ].right_cidx; /* TBD next iteration */
     340             : 
     341    46999794 :       p = l;
     342    46999794 :       l = t;
     343             : 
     344    46999794 :     } else { /* This is the mirror image of the above */
     345             : 
     346    39652713 :       ulong t = fd_wksp_private_pinfo_idx( pinfo[ r ].left_cidx ); TEST_AND_MARK( t ); TEST_PARENT( t, r );
     347             : 
     348    39652713 :       *_p_child_cidx        = fd_wksp_private_pinfo_cidx( r ); pinfo[ r ].parent_cidx = fd_wksp_private_pinfo_cidx( p );
     349             :     //pinfo[ r ].left_cidx  = fd_wksp_private_pinfo_cidx( d ); pinfo[ d ].parent_cidx = fd_wksp_private_pinfo_cidx( r );
     350             :     //pinfo[ d ].right_cidx = fd_wksp_private_pinfo_cidx( t );
     351             :     //if( !fd_wksp_private_pinfo_idx_is_null( t ) ) pinfo[ t ].parent_cidx = fd_wksp_private_pinfo_cidx( d );
     352             : 
     353    39652713 :       _p_child_cidx = &pinfo[ r ].left_cidx; /* TBD next iteration */
     354             : 
     355    39652713 :       p = r;
     356    39652713 :       r = t;
     357             : 
     358    39652713 :     }
     359             : 
     360    86652507 :   }
     361             : 
     362   224987550 : done:
     363   224987550 :   pinfo[ d ].in_same     = 0U;
     364   224987550 :   pinfo[ d ].left_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     365   224987550 :   pinfo[ d ].right_cidx  = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     366   224987550 :   pinfo[ d ].same_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     367   224987550 :   pinfo[ d ].parent_cidx = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     368   224987550 :   return FD_WKSP_SUCCESS;
     369   141665283 : }
     370             : 
     371             : #undef TEST_PARENT
     372             : #undef TEST_AND_MARK
     373             : #undef TEST