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