Line data    Source code

       1             : #include "fd_wksp_private.h"
       2             : 
       3             : ulong
       4             : fd_wksp_private_used_treap_query( ulong                     gaddr,
       5             :                                   fd_wksp_t *               wksp,
       6   634716498 :                                   fd_wksp_private_pinfo_t * pinfo ) {
       7   634716498 :   if( FD_UNLIKELY( !((wksp->gaddr_lo<=gaddr) & (gaddr<wksp->gaddr_hi)) ) ) return FD_WKSP_PRIVATE_PINFO_IDX_NULL; /* Not in range */
       8             : 
       9   522234312 :   ulong part_max  = wksp->part_max;
      10   522234312 :   ulong cycle_tag = wksp->cycle_tag++;
      11             : 
      12   522234312 :   ulong i = fd_wksp_private_pinfo_idx( wksp->part_used_cidx );
      13  2171561991 :   while( !fd_wksp_private_pinfo_idx_is_null( i ) ) {
      14  2108598492 :     if( FD_UNLIKELY( i>=part_max                     ) ) return FD_WKSP_PRIVATE_PINFO_IDX_NULL; /* Bad index */
      15  2108598492 :     if( FD_UNLIKELY( pinfo[ i ].cycle_tag==cycle_tag ) ) return FD_WKSP_PRIVATE_PINFO_IDX_NULL; /* Cycle detected */
      16  2108598492 :     pinfo[ i ].cycle_tag = cycle_tag;                                                           /* Mark i as visited */
      17             : 
      18  2108598492 :     ulong gaddr_lo = pinfo[ i ].gaddr_lo;
      19  2108598492 :     ulong gaddr_hi = pinfo[ i ].gaddr_hi;
      20  2108598492 :     if( gaddr <  gaddr_lo ) { i = fd_wksp_private_pinfo_idx( pinfo[ i ].left_cidx  ); continue; }
      21  1454997354 :     if( gaddr >= gaddr_hi ) { i = fd_wksp_private_pinfo_idx( pinfo[ i ].right_cidx ); continue; }
      22   459270813 :     break;
      23  1454997354 :   }
      24             : 
      25   522234312 :   return i;
      26   522234312 : }
      27             : 
      28  5419044954 : #define TEST(c) do { if( FD_UNLIKELY( !(c) ) ) { /*FD_LOG_WARNING(( "FAIL: %s", #c ));*/ return FD_WKSP_ERR_CORRUPT; } } while(0)
      29             : 
      30  2636430513 : #define TEST_AND_MARK( i ) do {                                                                              \
      31  2636430513 :     ulong _i = (i);                                                                                          \
      32  2636430513 :     TEST( fd_wksp_private_pinfo_idx_is_null( _i ) | ((_i<part_max) && (pinfo[ _i ].cycle_tag!=cycle_tag)) ); \
      33  2636430513 :     if( !fd_wksp_private_pinfo_idx_is_null( _i ) ) pinfo[ _i ].cycle_tag = cycle_tag;                        \
      34  2598916836 :   } while(0)
      35             : 
      36  2444393313 : #define TEST_PARENT( i, p ) do {                                                       \
      37  2444393313 :     ulong _i = (i);                                                                    \
      38  2444393313 :     if( _i<part_max ) TEST( fd_wksp_private_pinfo_idx( pinfo[_i].parent_cidx )==(p) ); \
      39  2444393313 :   } while(0)
      40             : 
      41             : int
      42             : fd_wksp_private_used_treap_insert( ulong                     n,
      43             :                                    fd_wksp_t *               wksp,
      44   153590853 :                                    fd_wksp_private_pinfo_t * pinfo ) {
      45             : 
      46   153590853 :   ulong part_max  = wksp->part_max;
      47   153590853 :   ulong cycle_tag = wksp->cycle_tag++;
      48             : 
      49   153590853 :   TEST( n<part_max );               /* Make sure valid n */
      50   153590853 :   pinfo[ n ].cycle_tag = cycle_tag; /* Mark n */
      51             : 
      52   153590853 :   ulong g0 = pinfo[ n ].gaddr_lo;
      53   153590853 :   ulong g1 = pinfo[ n ].gaddr_hi;
      54             : 
      55   153590853 :   TEST( (wksp->gaddr_lo<=g0) & (g0<g1) & (g1<=wksp->gaddr_hi) ); /* Make sure valid range */
      56             : 
      57             :   /* Note: zero tag is okay temporarily.  We assume the caller will set
      58             :      the tag to non-zero immediately afterward to make the allocation
      59             :      "official". */
      60             : 
      61   153590853 :   uint * _p_child_cidx = &wksp->part_used_cidx;
      62             : 
      63   153590853 :   ulong i = fd_wksp_private_pinfo_idx( *_p_child_cidx ); TEST_AND_MARK( i );
      64             : 
      65             :   /* If an empty treap, make n the root and we are done */
      66             : 
      67   152994624 :   if( FD_UNLIKELY( fd_wksp_private_pinfo_idx_is_null( i ) ) ) { /* Assume lots of used partitions typically */
      68      976902 :     pinfo[ n ].in_same     = 0U;
      69      976902 :     pinfo[ n ].left_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
      70      976902 :     pinfo[ n ].right_cidx  = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
      71      976902 :     pinfo[ n ].same_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
      72      976902 :     pinfo[ n ].parent_cidx = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
      73      976902 :     *_p_child_cidx = fd_wksp_private_pinfo_cidx( n );
      74      976902 :     return FD_WKSP_SUCCESS;
      75      976902 :   }
      76             : 
      77   152017722 :   TEST_PARENT( i, FD_WKSP_PRIVATE_PINFO_IDX_NULL ); /* Make sure good parent link */
      78             : 
      79             :   /* Find the leaf node where we can insert n */
      80             : 
      81             :   /* TODO: Consider pushing path down onto stack and bubble up
      82             :      using the stack? */
      83             : 
      84   975417252 :   for(;;) {
      85             : 
      86             :     /* At this point, i is a valid marked idx with good parent
      87             :        connectivity.  TODO: Consider validating ranges of visited nodes
      88             :        and tags of visited nodes */
      89             : 
      90             :     /* We need to validate both left and right child links to make the
      91             :        bubble up phase robust (because we do that after we insert). */
      92             : 
      93   975417252 :     ulong l = fd_wksp_private_pinfo_idx( pinfo[ i ].left_cidx  ); TEST_AND_MARK( l ); TEST_PARENT( l, i );
      94   956574471 :     ulong r = fd_wksp_private_pinfo_idx( pinfo[ i ].right_cidx ); TEST_AND_MARK( r ); TEST_PARENT( r, i );
      95             : 
      96   938499804 :     int go_left = (g1 <= pinfo[ i ].gaddr_lo);
      97   938499804 :     if( go_left ) { /* 50/50 unpredictable */
      98   447297780 :       _p_child_cidx = &pinfo[ i ].left_cidx;
      99   447297780 :       if( fd_wksp_private_pinfo_idx_is_null( l ) ) break;
     100   394103103 :       i = l;
     101   394103103 :       continue;
     102   447297780 :     }
     103             : 
     104   491202024 :     int go_right = (g0 >= pinfo[ i ].gaddr_hi);
     105   491202024 :     if( FD_LIKELY( go_right ) ) {
     106   491202024 :       _p_child_cidx = &pinfo[ i ].right_cidx;
     107   491202024 :       if( fd_wksp_private_pinfo_idx_is_null( r ) ) break;
     108   429296427 :       i = r;
     109   429296427 :       continue;
     110   491202024 :     }
     111             : 
     112             :     /* Looks like n overlaps i */
     113             : 
     114           0 :     return FD_WKSP_ERR_CORRUPT;
     115   491202024 :   }
     116             : 
     117             :   /* Make n the appropriate child of i.  This might momentarily break
     118             :      the heap property. */
     119             : 
     120   115100274 :   pinfo[ n ].in_same     = 0U;
     121   115100274 :   pinfo[ n ].left_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     122   115100274 :   pinfo[ n ].right_cidx  = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     123   115100274 :   pinfo[ n ].same_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     124   115100274 :   pinfo[ n ].parent_cidx = fd_wksp_private_pinfo_cidx( i );
     125   115100274 :   *_p_child_cidx         = fd_wksp_private_pinfo_cidx( n );
     126             : 
     127             :   /* Bubble n up until the heap property is restored.  Note that in the
     128             :      traversal above, we also validated parent links for this traversal
     129             :      (so that we could insert without worrying about encountering
     130             :      unpleasantness after we changed the treap). */
     131             : 
     132   312694077 :   while( !fd_wksp_private_pinfo_idx_is_null( i ) ) {
     133   307970064 :     uint n_prio = pinfo[ n ].heap_prio;
     134   307970064 :     uint i_prio = pinfo[ i ].heap_prio;
     135   307970064 :     int heap_intact = (n_prio<i_prio) | ((n_prio==i_prio) & (!((n ^ i) & 1UL))); /* Flip coin on equal priority */
     136   307970064 :     if( heap_intact ) break;
     137             : 
     138   197593803 :     ulong nl = fd_wksp_private_pinfo_idx( pinfo[ n ].left_cidx   ); /* Validated above */
     139   197593803 :     ulong nr = fd_wksp_private_pinfo_idx( pinfo[ n ].right_cidx  ); /* Validated above */
     140   197593803 :     ulong il = fd_wksp_private_pinfo_idx( pinfo[ i ].left_cidx   ); /* Validated above */
     141             :   //ulong ir = fd_wksp_private_pinfo_idx( pinfo[ i ].right_cidx  ); /* Validated above */
     142   197593803 :     ulong p  = fd_wksp_private_pinfo_idx( pinfo[ i ].parent_cidx ); /* Validated above */
     143   197593803 :     _p_child_cidx = fd_wksp_private_pinfo_idx_is_null( p )                 ? &wksp->part_used_cidx 
     144   197593803 :                   : (fd_wksp_private_pinfo_idx( pinfo[ p ].left_cidx )==i) ? &pinfo[ p ].left_cidx   /* Validated above */
     145   192869790 :                   :                                                          &pinfo[ p ].right_cidx;
     146             : 
     147   197593803 :     int left_child = (il==n);
     148   197593803 :     if( left_child ) { /* 50/50 unpredictable */
     149             : 
     150    96587808 :       pinfo[ n ].right_cidx  = fd_wksp_private_pinfo_cidx( i  ); pinfo[ i ].parent_cidx = fd_wksp_private_pinfo_cidx( n  );
     151    96587808 :       pinfo[ n ].parent_cidx = fd_wksp_private_pinfo_cidx( p  ); *_p_child_cidx         = fd_wksp_private_pinfo_cidx( n );
     152             : 
     153    96587808 :       pinfo[ i ].left_cidx = fd_wksp_private_pinfo_cidx( nr );
     154    96587808 :       if( !fd_wksp_private_pinfo_idx_is_null( nr ) ) pinfo[ nr ].parent_cidx = fd_wksp_private_pinfo_cidx( i );
     155             : 
     156   101005995 :     } else {
     157             : 
     158   101005995 :       pinfo[ n ].left_cidx   = fd_wksp_private_pinfo_cidx( i  ); pinfo[ i  ].parent_cidx = fd_wksp_private_pinfo_cidx( n );
     159   101005995 :       pinfo[ n ].parent_cidx = fd_wksp_private_pinfo_cidx( p  ); *_p_child_cidx          = fd_wksp_private_pinfo_cidx( n );
     160             : 
     161   101005995 :       pinfo[ i ].right_cidx = fd_wksp_private_pinfo_cidx( nl );
     162   101005995 :       if( !fd_wksp_private_pinfo_idx_is_null( nl ) ) pinfo[ nl ].parent_cidx = fd_wksp_private_pinfo_cidx( i );
     163             : 
     164   101005995 :     }
     165             : 
     166   197593803 :     i = p;
     167   197593803 :   }
     168             : 
     169   115100274 :   return FD_WKSP_SUCCESS;
     170   152017722 : }
     171             : 
     172             : int
     173             : fd_wksp_private_used_treap_remove( ulong                     d,
     174             :                                    fd_wksp_t *               wksp,
     175   153546621 :                                    fd_wksp_private_pinfo_t * pinfo ) {
     176             : 
     177   153546621 :   ulong part_max  = wksp->part_max;
     178   153546621 :   ulong cycle_tag = wksp->cycle_tag++;
     179             : 
     180   153546621 :   TEST( d<part_max );
     181   153546621 :   pinfo[ d ].cycle_tag = cycle_tag; /* Mark d */
     182             : 
     183             :   /* d should not be in or have a same list in a used treap */
     184             : 
     185   153546621 :   TEST( !pinfo[ d ].in_same );
     186   153546621 :   TEST( fd_wksp_private_pinfo_idx_is_null( fd_wksp_private_pinfo_idx( pinfo[ d ].same_cidx ) ) );
     187             : 
     188             :   /* Load and validate the environment surrounding d. */
     189             : 
     190   153546621 :   ulong l = fd_wksp_private_pinfo_idx( pinfo[ d ].left_cidx   ); TEST_AND_MARK( l ); TEST_PARENT( l, d );
     191   153546621 :   ulong r = fd_wksp_private_pinfo_idx( pinfo[ d ].right_cidx  ); TEST_AND_MARK( r ); TEST_PARENT( r, d );
     192   153546621 :   ulong p = fd_wksp_private_pinfo_idx( pinfo[ d ].parent_cidx ); TEST_AND_MARK( p );
     193             : 
     194   153546621 :   uint * _p_child_cidx;
     195   153546621 :   if( fd_wksp_private_pinfo_idx_is_null( p ) ) {
     196    43191708 :     _p_child_cidx = &wksp->part_used_cidx;
     197    43191708 :     TEST( (*_p_child_cidx)==d );
     198   110354913 :   } else {
     199   110354913 :     ulong pl = fd_wksp_private_pinfo_idx( pinfo[ p ].left_cidx  ); /* One should be marked from above */
     200   110354913 :     ulong pr = fd_wksp_private_pinfo_idx( pinfo[ p ].right_cidx ); /* The other should not */
     201   110354913 :     int is_left_child  = (pl==d);
     202   110354913 :     int is_right_child = (pr==d);
     203   110354913 :     TEST( is_left_child!=is_right_child );
     204   110354511 :     _p_child_cidx = fd_ptr_if( is_left_child, &pinfo[ p ].left_cidx, &pinfo[ p ].right_cidx );
     205   110354511 :   }
     206             : 
     207   206262432 :   for(;;) {
     208             : 
     209             :     /* At this point, we have a non-trivial hole to fill at d.
     210             : 
     211             :        i and j are IDX_NULL as d has no overlapping partitions
     212             :        l is the hole's left subtree (if any), validated and marked
     213             :        r is the hole's right subtree (if any), validated and marked
     214             :        p is the hole's parent (if any), if non-NULL, validated and marked
     215             : 
     216             :        _p_child_cidx is the location of link from the parent to the hole
     217             :        (or the pointer to the tree root if d is the root), validated. */
     218             : 
     219             :     /* If the hole has no left subtree (and maybe no right subtree and
     220             :        maybe no parent), fill the hole with the right subtree (or with
     221             :        nothing if no right subtree) and we are done. */
     222             : 
     223   206262432 :     if( fd_wksp_private_pinfo_idx_is_null( l ) ) {
     224    77951835 :       if( !fd_wksp_private_pinfo_idx_is_null( r ) ) pinfo[ r ].parent_cidx = fd_wksp_private_pinfo_cidx( p );
     225    77951835 :       *_p_child_cidx = fd_wksp_private_pinfo_cidx( r );
     226    77951835 :       break;
     227    77951835 :     }
     228             : 
     229             :     /* If the hole has no right subtree but has a left subtree (and
     230             :        maybe no parent), fill the hole with the left subtree and we are
     231             :        done. */
     232             : 
     233   128310597 :     if( fd_wksp_private_pinfo_idx_is_null( r ) ) {
     234    38102523 :       pinfo[ l ].parent_cidx = fd_wksp_private_pinfo_cidx( p );
     235    38102523 :       *_p_child_cidx = fd_wksp_private_pinfo_cidx( l );
     236    38102523 :       break;
     237    38102523 :     }
     238             : 
     239             :     /* At this point we have to push the hole down the left or right
     240             :        subtree (and we still maybe have no parent).  We use the heap
     241             :        priorities to decide such that we preserve the heap property (we
     242             :        flip a coin on equal priorities).  We can omit any link updates
     243             :        from d as d is getting removed and the above just needs the
     244             :        environment around d.  Likewise, we can omit any link updates to
     245             :        d these will be ultimately replaced with links to something other
     246             :        than d before this returns. */
     247             : 
     248    90208074 :     uint l_prio = pinfo[ l ].heap_prio;
     249    90208074 :     uint r_prio = pinfo[ r ].heap_prio;
     250    90208074 :     int promote_left = (l_prio>r_prio) | ((l_prio==r_prio) & (!((p ^ d) & 1UL)));
     251    90208074 :     if( promote_left ) {
     252             : 
     253    44187777 :       ulong t = fd_wksp_private_pinfo_idx( pinfo[ l ].right_cidx ); TEST_AND_MARK( t ); TEST_PARENT( t, l );
     254             : 
     255    44187777 :       *_p_child_cidx        = fd_wksp_private_pinfo_cidx( l ); pinfo[ l ].parent_cidx = fd_wksp_private_pinfo_cidx( p );
     256             :     //pinfo[ l ].right_cidx = fd_wksp_private_pinfo_cidx( d ); pinfo[ d ].parent_cidx = fd_wksp_private_pinfo_cidx( l );
     257             :     //pinfo[ d ].left_cidx  = fd_wksp_private_pinfo_cidx( t );
     258             :     //if( !fd_wksp_private_pinfo_idx_is_null( t ) ) pinfo[ t ].parent_cidx = fd_wksp_private_pinfo_cidx( d );
     259             : 
     260    44187777 :       _p_child_cidx = &pinfo[ l ].right_cidx; /* TBD next iteration */
     261             : 
     262    44187777 :       p = l;
     263    44187777 :       l = t;
     264             : 
     265    46020297 :     } else { /* This is the mirror image of the above */
     266             : 
     267    46020297 :       ulong t = fd_wksp_private_pinfo_idx( pinfo[ r ].left_cidx ); TEST_AND_MARK( t ); TEST_PARENT( t, r );
     268             : 
     269    46020297 :       *_p_child_cidx        = fd_wksp_private_pinfo_cidx( r ); pinfo[ r ].parent_cidx = fd_wksp_private_pinfo_cidx( p );
     270             :     //pinfo[ r ].left_cidx  = fd_wksp_private_pinfo_cidx( d ); pinfo[ d ].parent_cidx = fd_wksp_private_pinfo_cidx( r );
     271             :     //pinfo[ d ].right_cidx = fd_wksp_private_pinfo_cidx( t );
     272             :     //if( !fd_wksp_private_pinfo_idx_is_null( t ) ) pinfo[ t ].parent_cidx = fd_wksp_private_pinfo_cidx( d );
     273             : 
     274    46020297 :       _p_child_cidx = &pinfo[ r ].left_cidx; /* TBD next iteration */
     275             : 
     276    46020297 :       p = r;
     277    46020297 :       r = t;
     278             : 
     279    46020297 :     }
     280             : 
     281    90208074 :   }
     282             : 
     283   116054358 :   pinfo[ d ].in_same     = 0U;
     284   116054358 :   pinfo[ d ].left_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     285   116054358 :   pinfo[ d ].right_cidx  = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     286   116054358 :   pinfo[ d ].same_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     287   116054358 :   pinfo[ d ].parent_cidx = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     288   116054358 :   return FD_WKSP_SUCCESS;
     289   116054358 : }
     290             : 
     291             : #undef TEST_PARENT
     292             : #undef TEST_AND_MARK
     293             : #undef TEST