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          53 :                                   fd_wksp_private_pinfo_t * pinfo ) {
       7          53 :   if( FD_UNLIKELY( !((wksp->gaddr_lo<=gaddr) & (gaddr<wksp->gaddr_hi)) ) ) return FD_WKSP_PRIVATE_PINFO_IDX_NULL; /* Not in range */
       8             : 
       9          53 :   ulong part_max  = wksp->part_max;
      10          53 :   ulong cycle_tag = wksp->cycle_tag++;
      11             : 
      12          53 :   ulong i = fd_wksp_private_pinfo_idx( wksp->part_used_cidx );
      13         391 :   while( !fd_wksp_private_pinfo_idx_is_null( i ) ) {
      14         391 :     if( FD_UNLIKELY( i>=part_max                     ) ) return FD_WKSP_PRIVATE_PINFO_IDX_NULL; /* Bad index */
      15         391 :     if( FD_UNLIKELY( pinfo[ i ].cycle_tag==cycle_tag ) ) return FD_WKSP_PRIVATE_PINFO_IDX_NULL; /* Cycle detected */
      16         391 :     pinfo[ i ].cycle_tag = cycle_tag;                                                           /* Mark i as visited */
      17             : 
      18         391 :     ulong gaddr_lo = pinfo[ i ].gaddr_lo;
      19         391 :     ulong gaddr_hi = pinfo[ i ].gaddr_hi;
      20         391 :     if( gaddr <  gaddr_lo ) { i = fd_wksp_private_pinfo_idx( pinfo[ i ].left_cidx  ); continue; }
      21         189 :     if( gaddr >= gaddr_hi ) { i = fd_wksp_private_pinfo_idx( pinfo[ i ].right_cidx ); continue; }
      22          53 :     break;
      23         189 :   }
      24             : 
      25          53 :   return i;
      26          53 : }
      27             : 
      28        3732 : #define TEST(c) do { if( FD_UNLIKELY( !(c) ) ) { /*FD_LOG_WARNING(( "FAIL: %s", #c ));*/ return FD_WKSP_ERR_CORRUPT; } } while(0)
      29             : 
      30        1812 : #define TEST_AND_MARK( i ) do {                                                                              \
      31        1812 :     ulong _i = (i);                                                                                          \
      32        1812 :     TEST( fd_wksp_private_pinfo_idx_is_null( _i ) | ((_i<part_max) && (pinfo[ _i ].cycle_tag!=cycle_tag)) ); \
      33        1812 :     if( !fd_wksp_private_pinfo_idx_is_null( _i ) ) pinfo[ _i ].cycle_tag = cycle_tag;                        \
      34        1812 :   } while(0)
      35             : 
      36        1758 : #define TEST_PARENT( i, p ) do {                                                       \
      37        1758 :     ulong _i = (i);                                                                    \
      38        1758 :     if( _i<part_max ) TEST( fd_wksp_private_pinfo_idx( pinfo[_i].parent_cidx )==(p) ); \
      39        1758 :   } while(0)
      40             : 
      41             : int
      42             : fd_wksp_private_used_treap_insert( ulong                     n,
      43             :                                    fd_wksp_t *               wksp,
      44         137 :                                    fd_wksp_private_pinfo_t * pinfo ) {
      45             : 
      46         137 :   ulong part_max  = wksp->part_max;
      47         137 :   ulong cycle_tag = wksp->cycle_tag++;
      48             : 
      49         137 :   TEST( n<part_max );               /* Make sure valid n */
      50         137 :   pinfo[ n ].cycle_tag = cycle_tag; /* Mark n */
      51             : 
      52         137 :   ulong g0 = pinfo[ n ].gaddr_lo;
      53         137 :   ulong g1 = pinfo[ n ].gaddr_hi;
      54             : 
      55         137 :   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         137 :   uint * _p_child_cidx = &wksp->part_used_cidx;
      62             : 
      63         137 :   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         137 :   if( FD_UNLIKELY( fd_wksp_private_pinfo_idx_is_null( i ) ) ) { /* Assume lots of used partitions typically */
      68           1 :     pinfo[ n ].in_same     = 0U;
      69           1 :     pinfo[ n ].left_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
      70           1 :     pinfo[ n ].right_cidx  = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
      71           1 :     pinfo[ n ].same_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
      72           1 :     pinfo[ n ].parent_cidx = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
      73           1 :     *_p_child_cidx = fd_wksp_private_pinfo_cidx( n );
      74           1 :     return FD_WKSP_SUCCESS;
      75           1 :   }
      76             : 
      77         136 :   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         734 :   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         734 :     ulong l = fd_wksp_private_pinfo_idx( pinfo[ i ].left_cidx  ); TEST_AND_MARK( l ); TEST_PARENT( l, i );
      94         734 :     ulong r = fd_wksp_private_pinfo_idx( pinfo[ i ].right_cidx ); TEST_AND_MARK( r ); TEST_PARENT( r, i );
      95             : 
      96         734 :     int go_left = (g1 <= pinfo[ i ].gaddr_lo);
      97         734 :     if( go_left ) { /* 50/50 unpredictable */
      98          62 :       _p_child_cidx = &pinfo[ i ].left_cidx;
      99          62 :       if( fd_wksp_private_pinfo_idx_is_null( l ) ) break;
     100          50 :       i = l;
     101          50 :       continue;
     102          62 :     }
     103             : 
     104         672 :     int go_right = (g0 >= pinfo[ i ].gaddr_hi);
     105         672 :     if( FD_LIKELY( go_right ) ) {
     106         672 :       _p_child_cidx = &pinfo[ i ].right_cidx;
     107         672 :       if( fd_wksp_private_pinfo_idx_is_null( r ) ) break;
     108         548 :       i = r;
     109         548 :       continue;
     110         672 :     }
     111             : 
     112             :     /* Looks like n overlaps i */
     113             : 
     114           0 :     return FD_WKSP_ERR_CORRUPT;
     115         672 :   }
     116             : 
     117             :   /* Make n the appropriate child of i.  This might momentarily break
     118             :      the heap property. */
     119             : 
     120         136 :   pinfo[ n ].in_same     = 0U;
     121         136 :   pinfo[ n ].left_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     122         136 :   pinfo[ n ].right_cidx  = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     123         136 :   pinfo[ n ].same_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     124         136 :   pinfo[ n ].parent_cidx = fd_wksp_private_pinfo_cidx( i );
     125         136 :   *_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         291 :   while( !fd_wksp_private_pinfo_idx_is_null( i ) ) {
     133         286 :     uint n_prio = pinfo[ n ].heap_prio;
     134         286 :     uint i_prio = pinfo[ i ].heap_prio;
     135         286 :     int heap_intact = (n_prio<i_prio) | ((n_prio==i_prio) & (!((n ^ i) & 1UL))); /* Flip coin on equal priority */
     136         286 :     if( heap_intact ) break;
     137             : 
     138         155 :     ulong nl = fd_wksp_private_pinfo_idx( pinfo[ n ].left_cidx   ); /* Validated above */
     139         155 :     ulong nr = fd_wksp_private_pinfo_idx( pinfo[ n ].right_cidx  ); /* Validated above */
     140         155 :     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         155 :     ulong p  = fd_wksp_private_pinfo_idx( pinfo[ i ].parent_cidx ); /* Validated above */
     143         155 :     _p_child_cidx = fd_wksp_private_pinfo_idx_is_null( p )                 ? &wksp->part_used_cidx
     144         155 :                   : (fd_wksp_private_pinfo_idx( pinfo[ p ].left_cidx )==i) ? &pinfo[ p ].left_cidx   /* Validated above */
     145         150 :                   :                                                          &pinfo[ p ].right_cidx;
     146             : 
     147         155 :     int left_child = (il==n);
     148         155 :     if( left_child ) { /* 50/50 unpredictable */
     149             : 
     150          24 :       pinfo[ n ].right_cidx  = fd_wksp_private_pinfo_cidx( i  ); pinfo[ i ].parent_cidx = fd_wksp_private_pinfo_cidx( n  );
     151          24 :       pinfo[ n ].parent_cidx = fd_wksp_private_pinfo_cidx( p  ); *_p_child_cidx         = fd_wksp_private_pinfo_cidx( n );
     152             : 
     153          24 :       pinfo[ i ].left_cidx = fd_wksp_private_pinfo_cidx( nr );
     154          24 :       if( !fd_wksp_private_pinfo_idx_is_null( nr ) ) pinfo[ nr ].parent_cidx = fd_wksp_private_pinfo_cidx( i );
     155             : 
     156         131 :     } else {
     157             : 
     158         131 :       pinfo[ n ].left_cidx   = fd_wksp_private_pinfo_cidx( i  ); pinfo[ i  ].parent_cidx = fd_wksp_private_pinfo_cidx( n );
     159         131 :       pinfo[ n ].parent_cidx = fd_wksp_private_pinfo_cidx( p  ); *_p_child_cidx          = fd_wksp_private_pinfo_cidx( n );
     160             : 
     161         131 :       pinfo[ i ].right_cidx = fd_wksp_private_pinfo_cidx( nl );
     162         131 :       if( !fd_wksp_private_pinfo_idx_is_null( nl ) ) pinfo[ nl ].parent_cidx = fd_wksp_private_pinfo_cidx( i );
     163             : 
     164         131 :     }
     165             : 
     166         155 :     i = p;
     167         155 :   }
     168             : 
     169         136 :   return FD_WKSP_SUCCESS;
     170         136 : }
     171             : 
     172             : int
     173             : fd_wksp_private_used_treap_remove( ulong                     d,
     174             :                                    fd_wksp_t *               wksp,
     175          53 :                                    fd_wksp_private_pinfo_t * pinfo ) {
     176             : 
     177          53 :   ulong part_max  = wksp->part_max;
     178          53 :   ulong cycle_tag = wksp->cycle_tag++;
     179             : 
     180          53 :   TEST( d<part_max );
     181          53 :   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          53 :   TEST( !pinfo[ d ].in_same );
     186          53 :   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          53 :   ulong l = fd_wksp_private_pinfo_idx( pinfo[ d ].left_cidx   ); TEST_AND_MARK( l ); TEST_PARENT( l, d );
     191          53 :   ulong r = fd_wksp_private_pinfo_idx( pinfo[ d ].right_cidx  ); TEST_AND_MARK( r ); TEST_PARENT( r, d );
     192          53 :   ulong p = fd_wksp_private_pinfo_idx( pinfo[ d ].parent_cidx ); TEST_AND_MARK( p );
     193             : 
     194          53 :   uint * _p_child_cidx;
     195          53 :   if( fd_wksp_private_pinfo_idx_is_null( p ) ) {
     196           1 :     _p_child_cidx = &wksp->part_used_cidx;
     197           1 :     TEST( (*_p_child_cidx)==d );
     198          52 :   } else {
     199          52 :     ulong pl = fd_wksp_private_pinfo_idx( pinfo[ p ].left_cidx  ); /* One should be marked from above */
     200          52 :     ulong pr = fd_wksp_private_pinfo_idx( pinfo[ p ].right_cidx ); /* The other should not */
     201          52 :     int is_left_child  = (pl==d);
     202          52 :     int is_right_child = (pr==d);
     203          52 :     TEST( is_left_child!=is_right_child );
     204          52 :     _p_child_cidx = fd_ptr_if( is_left_child, &pinfo[ p ].left_cidx, &pinfo[ p ].right_cidx );
     205          52 :   }
     206             : 
     207         101 :   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         101 :     if( fd_wksp_private_pinfo_idx_is_null( l ) ) {
     224          31 :       if( !fd_wksp_private_pinfo_idx_is_null( r ) ) pinfo[ r ].parent_cidx = fd_wksp_private_pinfo_cidx( p );
     225          31 :       *_p_child_cidx = fd_wksp_private_pinfo_cidx( r );
     226          31 :       break;
     227          31 :     }
     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          70 :     if( fd_wksp_private_pinfo_idx_is_null( r ) ) {
     234          22 :       pinfo[ l ].parent_cidx = fd_wksp_private_pinfo_cidx( p );
     235          22 :       *_p_child_cidx = fd_wksp_private_pinfo_cidx( l );
     236          22 :       break;
     237          22 :     }
     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          48 :     uint l_prio = pinfo[ l ].heap_prio;
     249          48 :     uint r_prio = pinfo[ r ].heap_prio;
     250          48 :     int promote_left = (l_prio>r_prio) | ((l_prio==r_prio) & (!((p ^ d) & 1UL)));
     251          48 :     if( promote_left ) {
     252             : 
     253          20 :       ulong t = fd_wksp_private_pinfo_idx( pinfo[ l ].right_cidx ); TEST_AND_MARK( t ); TEST_PARENT( t, l );
     254             : 
     255          20 :       *_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          20 :       _p_child_cidx = &pinfo[ l ].right_cidx; /* TBD next iteration */
     261             : 
     262          20 :       p = l;
     263          20 :       l = t;
     264             : 
     265          28 :     } else { /* This is the mirror image of the above */
     266             : 
     267          28 :       ulong t = fd_wksp_private_pinfo_idx( pinfo[ r ].left_cidx ); TEST_AND_MARK( t ); TEST_PARENT( t, r );
     268             : 
     269          28 :       *_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          28 :       _p_child_cidx = &pinfo[ r ].left_cidx; /* TBD next iteration */
     275             : 
     276          28 :       p = r;
     277          28 :       r = t;
     278             : 
     279          28 :     }
     280             : 
     281          48 :   }
     282             : 
     283          53 :   pinfo[ d ].in_same     = 0U;
     284          53 :   pinfo[ d ].left_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     285          53 :   pinfo[ d ].right_cidx  = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     286          53 :   pinfo[ d ].same_cidx   = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     287          53 :   pinfo[ d ].parent_cidx = fd_wksp_private_pinfo_cidx( FD_WKSP_PRIVATE_PINFO_IDX_NULL );
     288          53 :   return FD_WKSP_SUCCESS;
     289          53 : }
     290             : 
     291             : #undef TEST_PARENT
     292             : #undef TEST_AND_MARK
     293             : #undef TEST