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