cds/intrusive/split_list_nogc.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H
   4 #define CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H
   5
   6 #include <limits>
   7
   8 #include <cds/intrusive/details/split_list_base.h>
   9 #include <cds/gc/nogc.h>
  10
  11 namespace cds { namespace intrusive {
  12
  13     /// Split-ordered list (template specialization for gc::nogc)
  14     /** @ingroup cds_intrusive_map
  15         \anchor cds_intrusive_SplitListSet_nogc
  16
  17         This specialization is intended for so-called persistent usage when no item
  18         reclamation may be performed. The class does not support deleting of list item.
  19
  20         See \ref cds_intrusive_SplitListSet_hp "SplitListSet" for description of template parameters.
  21         The template parameter \p OrderedList should be any gc::nogc-derived ordered list, for example,
  22         \ref cds_intrusive_MichaelList_nogc "persistent MichaelList",
  23         \ref cds_intrusive_LazyList_nogc "persistent LazyList"
  24     */
  25     template <
  26         class OrderedList,
  27 #ifdef CDS_DOXYGEN_INVOKED
  28         class Traits = split_list::traits
  29 #else
  30         class Traits
  31 #endif
  32     >
  33     class SplitListSet< cds::gc::nogc, OrderedList, Traits >
  34     {
  35     public:
  36         typedef cds::gc::nogc gc;     ///< Garbage collector
  37         typedef Traits        traits; ///< Traits template parameters
  38
  39         /// Hash functor for \p value_type and all its derivatives that you use
  40         typedef typename cds::opt::v::hash_selector< typename traits::hash >::type   hash;
  41
  42         //@cond
  43         typedef cds::intrusive::split_list::implementation_tag implementation_tag;
  44         //@endcond
  45
  46     protected:
  47         //@cond
  48         typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
  49         //@endcond
  50
  51     public:
  52 #   ifdef CDS_DOXYGEN_INVOKED
  53         typedef OrderedList ordered_list;   ///< type of ordered list used as base for split-list
  54 #   else
  55         typedef typename wrapped_ordered_list::result ordered_list;
  56 #   endif
  57         typedef typename ordered_list::value_type     value_type;     ///< type of value stored in the split-list
  58         typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
  59         typedef typename ordered_list::disposer       disposer;       ///< Node disposer functor
  60
  61         typedef typename traits::item_counter item_counter; ///< Item counter type
  62         typedef typename traits::back_off     back_off;     ///< back-off strategy
  63         typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
  64         typedef typename traits::stat         stat;         ///< Internal statistics, see \p spit_list::stat
  65
  66     protected:
  67         typedef typename ordered_list::node_type  list_node_type;  ///< Node type as declared in ordered list
  68         typedef split_list::node<list_node_type>  node_type;       ///< split-list node type
  69         typedef node_type                         dummy_node_type; ///< dummy node type
  70
  71         /// Split-list node traits
  72         /**
  73             This traits is intended for converting between underlying ordered list node type \ref list_node_type
  74             and split-list node type \ref node_type
  75         */
  76         typedef split_list::node_traits<typename ordered_list::node_traits>  node_traits;
  77
  78         //@cond
  79         /// Bucket table implementation
  80         typedef typename split_list::details::bucket_table_selector<
  81             traits::dynamic_bucket_table
  82             , gc
  83             , dummy_node_type
  84             , opt::allocator< typename traits::allocator >
  85             , opt::memory_model< memory_model >
  86         >::type bucket_table;
  87
  88         typedef typename ordered_list::iterator list_iterator;
  89         typedef typename ordered_list::const_iterator list_const_iterator;
  90         //@endcond
  91
  92     protected:
  93         //@cond
  94         /// Ordered list wrapper to access protected members
  95         class ordered_list_wrapper: public ordered_list
  96         {
  97             typedef ordered_list base_class;
  98             typedef typename base_class::auxiliary_head       bucket_head_type;
  99
 100         public:
 101             list_iterator insert_at_( dummy_node_type * pHead, value_type& val )
 102             {
 103                 assert( pHead != nullptr );
 104                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 105                 return base_class::insert_at_( h, val );
 106             }
 107
 108             template <typename Func>
 109             std::pair<list_iterator, bool> ensure_at_( dummy_node_type * pHead, value_type& val, Func func )
 110             {
 111                 assert( pHead != nullptr );
 112                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 113                 return base_class::ensure_at_( h, val, func );
 114             }
 115
 116             template <typename Q, typename Compare, typename Func>
 117             bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
 118             {
 119                 assert( pHead != nullptr );
 120                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 121                 return base_class::find_at( h, val, cmp, f );
 122             }
 123
 124             template <typename Q, typename Compare>
 125             list_iterator find_at_( dummy_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
 126             {
 127                 assert( pHead != nullptr );
 128                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 129                 return base_class::find_at_( h, val, cmp );
 130             }
 131
 132             bool insert_aux_node( dummy_node_type * pNode )
 133             {
 134                 return base_class::insert_aux_node( pNode );
 135             }
 136             bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
 137             {
 138                 bucket_head_type h(static_cast<list_node_type *>(pHead));
 139                 return base_class::insert_aux_node( h, pNode );
 140             }
 141         };
 142
 143         //@endcond
 144
 145     protected:
 146         ordered_list_wrapper    m_List;             ///< Ordered list containing split-list items
 147         bucket_table            m_Buckets;          ///< bucket table
 148         atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
 149         atomics::atomic<size_t> m_nMaxItemCount;    ///< number of items container can hold, before we have to resize
 150         item_counter            m_ItemCounter;      ///< Item counter
 151         hash                    m_HashFunctor;      ///< Hash functor
 152         stat                    m_Stat;             ///< Internal statistics
 153
 154     protected:
 155         //@cond
 156         typedef cds::details::Allocator< dummy_node_type, typename traits::allocator >   dummy_node_allocator;
 157
 158         dummy_node_type * alloc_dummy_node( size_t nHash )
 159         {
 160             m_Stat.onHeadNodeAllocated();
 161             return dummy_node_allocator().New( nHash );
 162         }
 163         void free_dummy_node( dummy_node_type * p )
 164         {
 165             dummy_node_allocator().Delete( p );
 166             m_Stat.onHeadNodeFreed();
 167         }
 168
 169         /// Calculates hash value of \p key
 170         template <typename Q>
 171         size_t hash_value( Q const& key ) const
 172         {
 173             return m_HashFunctor( key );
 174         }
 175
 176         size_t bucket_no( size_t nHash ) const
 177         {
 178             return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
 179         }
 180
 181         static size_t parent_bucket( size_t nBucket )
 182         {
 183             assert( nBucket > 0 );
 184             return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
 185         }
 186
 187         dummy_node_type * init_bucket( size_t nBucket )
 188         {
 189             assert( nBucket > 0 );
 190             size_t nParent = parent_bucket( nBucket );
 191
 192             dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
 193             if ( pParentBucket == nullptr ) {
 194                 pParentBucket = init_bucket( nParent );
 195                 m_Stat.onRecursiveInitBucket();
 196             }
 197
 198             assert( pParentBucket != nullptr );
 199
 200             // Allocate a dummy node for new bucket
 201             {
 202                 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
 203                 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
 204                     m_Buckets.bucket( nBucket, pBucket );
 205                     m_Stat.onNewBucket();
 206                     return pBucket;
 207                 }
 208                 free_dummy_node( pBucket );
 209             }
 210
 211             // Another thread set the bucket. Wait while it done
 212
 213             // In this point, we must wait while nBucket is empty.
 214             // The compiler can decide that waiting loop can be "optimized" (stripped)
 215             // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
 216             //
 217             m_Stat.onBucketInitContenton();
 218             back_off bkoff;
 219             while ( true ) {
 220                 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
 221                 if ( p && p != nullptr )
 222                     return const_cast<dummy_node_type *>( p );
 223                 bkoff();
 224                 m_Stat.onBusyWaitBucketInit();
 225             }
 226         }
 227
 228         dummy_node_type * get_bucket( size_t nHash )
 229         {
 230             size_t nBucket = bucket_no( nHash );
 231
 232             dummy_node_type * pHead = m_Buckets.bucket( nBucket );
 233             if ( pHead == nullptr )
 234                 pHead = init_bucket( nBucket );
 235
 236             assert( pHead->is_dummy() );
 237
 238             return pHead;
 239         }
 240
 241         void init()
 242         {
 243             // GC and OrderedList::gc must be the same
 244             static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
 245
 246             // atomicity::empty_item_counter is not allowed as a item counter
 247             static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
 248                            "cds::atomicity::empty_item_counter is not allowed as a item counter");
 249
 250             // Initialize bucket 0
 251             dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
 252
 253             // insert_aux_node cannot return false for empty list
 254             CDS_VERIFY( m_List.insert_aux_node( pNode ));
 255
 256             m_Buckets.bucket( 0, pNode );
 257         }
 258
 259         static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
 260         {
 261             return nBucketCount * nLoadFactor;
 262         }
 263
 264         void inc_item_count()
 265         {
 266             size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
 267             if ( ++m_ItemCounter <= nMaxCount )
 268                 return;
 269
 270             size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
 271             const size_t nBucketCount = static_cast<size_t>(1) << sz;
 272             if ( nBucketCount < m_Buckets.capacity() ) {
 273                 // we may grow the bucket table
 274                 const size_t nLoadFactor = m_Buckets.load_factor();
 275                 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
 276                     return; // someone already have updated m_nBucketCountLog2, so stop here
 277
 278                 const size_t nNewMaxCount = (nBucketCount < m_Buckets.capacity()) ? max_item_count( nBucketCount << 1, nLoadFactor )
 279                                                                                   : std::numeric_limits<size_t>::max();
 280                 m_nMaxItemCount.compare_exchange_strong( nMaxCount, nNewMaxCount, memory_model::memory_order_relaxed,
 281                     atomics::memory_order_relaxed );
 282                 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
 283             }
 284         }
 285
 286         //@endcond
 287
 288     public:
 289         /// Initialize split-ordered list of default capacity
 290         /**
 291             The default capacity is defined in bucket table constructor.
 292             See split_list::expandable_bucket_table, split_list::static_ducket_table
 293             which selects by split_list::dynamic_bucket_table option.
 294         */
 295         SplitListSet()
 296             : m_nBucketCountLog2(1)
 297             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
 298         {
 299             init();
 300         }
 301
 302         /// Initialize split-ordered list
 303         SplitListSet(
 304             size_t nItemCount           ///< estimate average of item count
 305             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
 306             )
 307             : m_Buckets( nItemCount, nLoadFactor )
 308             , m_nBucketCountLog2(1)
 309             , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
 310         {
 311             init();
 312         }
 313
 314     public:
 315         /// Inserts new node
 316         /**
 317             The function inserts \p val in the set if it does not contain
 318             an item with key equal to \p val.
 319
 320             Returns \p true if \p val is placed into the set, \p false otherwise.
 321         */
 322         bool insert( value_type& val )
 323         {
 324             return insert_( val ) != end();
 325         }
 326
 327         /// Ensures that the \p item exists in the set
 328         /**
 329             The operation performs inserting or changing data with lock-free manner.
 330
 331             If the item \p val not found in the set, then \p val is inserted into the set.
 332             Otherwise, the functor \p func is called with item found.
 333             The functor signature is:
 334             \code
 335             struct ensure_functor {
 336                 void operator()( bool bNew, value_type& item, value_type& val );
 337             };
 338             \endcode
 339             with arguments:
 340             - \p bNew - \p true if the item has been inserted, \p false otherwise
 341             - \p item - item of the set
 342             - \p val - argument \p val passed into the \p ensure function
 343             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 344             refers to the same thing.
 345
 346             The functor can change non-key fields of the \p item.
 347
 348             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 349             \p second is \p true if new item has been added or \p false if the item with given key
 350             already is in the set.
 351
 352             @warning For \ref cds_intrusive_MichaelList_nogc "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 353             \ref cds_intrusive_LazyList_nogc "LazyList" provides exclusive access to inserted item and does not require any node-level
 354             synchronization.
 355         */
 356         template <typename Func>
 357         std::pair<bool, bool> ensure( value_type& val, Func func )
 358         {
 359             std::pair<iterator, bool> ret = ensure_( val, func );
 360             return std::make_pair( ret.first != end(), ret.second );
 361         }
 362
 363         /// Finds the key \p key
 364         /** \anchor cds_intrusive_SplitListSet_nogc_find_val
 365             The function searches the item with key equal to \p key
 366             and returns pointer to item found or , and \p nullptr otherwise.
 367
 368             Note the hash functor specified for class \p Traits template parameter
 369             should accept a parameter of type \p Q that can be not the same as \p value_type.
 370         */
 371         template <typename Q>
 372         value_type * find( Q const& key )
 373         {
 374             iterator it = find_( key );
 375             if ( it == end() )
 376                 return nullptr;
 377             return &*it;
 378         }
 379
 380         /// Finds the key \p key with \p pred predicate for comparing
 381         /**
 382             The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_val "find(Q const&)"
 383             but \p cmp is used for key compare.
 384             \p Less has the interface like \p std::less.
 385             \p cmp must imply the same element order as the comparator used for building the set.
 386         */
 387         template <typename Q, typename Less>
 388         value_type * find_with( Q const& key, Less pred )
 389         {
 390             iterator it = find_with_( key, pred );
 391             if ( it == end() )
 392                 return nullptr;
 393             return &*it;
 394         }
 395
 396         /// Finds the key \p key
 397         /** \anchor cds_intrusive_SplitListSet_nogc_find_func
 398             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 399             The interface of \p Func functor is:
 400             \code
 401             struct functor {
 402                 void operator()( value_type& item, Q& key );
 403             };
 404             \endcode
 405             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 406
 407             The functor can change non-key fields of \p item.
 408             The functor does not serialize simultaneous access to the set \p item. If such access is
 409             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 410
 411             Note the hash functor specified for class \p Traits template parameter
 412             should accept a parameter of type \p Q that can be not the same as \p value_type.
 413
 414             The function returns \p true if \p key is found, \p false otherwise.
 415         */
 416         template <typename Q, typename Func>
 417         bool find( Q& key, Func f )
 418         {
 419             return find_( key, key_comparator(), f );
 420         }
 421         //@cond
 422         template <typename Q, typename Func>
 423         bool find( Q const& key, Func f )
 424         {
 425             return find_( key, key_comparator(), f );
 426         }
 427         //@endcond
 428
 429         /// Finds the key \p key with \p pred predicate for comparing
 430         /**
 431             The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_func "find(Q&, Func)"
 432             but \p cmp is used for key compare.
 433             \p Less has the interface like \p std::less.
 434             \p cmp must imply the same element order as the comparator used for building the set.
 435         */
 436         template <typename Q, typename Less, typename Func>
 437         bool find_with( Q& key, Less pred, Func f )
 438         {
 439             CDS_UNUSED( pred );
 440             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 441         }
 442         //@cond
 443         template <typename Q, typename Less, typename Func>
 444         bool find_with( Q const& key, Less pred, Func f )
 445         {
 446             CDS_UNUSED( pred );
 447             return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
 448         }
 449         //@endcond
 450
 451         /// Checks if the set is empty
 452         /**
 453             Emptiness is checked by item counting: if item count is zero then the set is empty.
 454             Thus, the correct item counting feature is an important part of split-list implementation.
 455         */
 456         bool empty() const
 457         {
 458             return size() == 0;
 459         }
 460
 461         /// Returns item count in the set
 462         size_t size() const
 463         {
 464             return m_ItemCounter;
 465         }
 466
 467         /// Returns internal statistics
 468         stat const& statistics() const
 469         {
 470             return m_Stat;
 471         }
 472
 473     protected:
 474         //@cond
 475         template <bool IsConst>
 476         class iterator_type
 477             : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
 478         {
 479             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
 480             typedef typename iterator_base_class::list_iterator list_iterator;
 481         public:
 482             iterator_type()
 483                 : iterator_base_class()
 484             {}
 485
 486             iterator_type( iterator_type const& src )
 487                 : iterator_base_class( src )
 488             {}
 489
 490             // This ctor should be protected...
 491             iterator_type( list_iterator itCur, list_iterator itEnd )
 492                 : iterator_base_class( itCur, itEnd )
 493             {}
 494         };
 495         //@endcond
 496
 497     public:
 498         /// Forward iterator
 499         /**
 500             The forward iterator for a split-list has some features:
 501             - it has no post-increment operator
 502             - it depends on iterator of underlying \p OrderedList
 503         */
 504         typedef iterator_type<false>    iterator;
 505         /// Const forward iterator
 506         /**
 507             For iterator's features and requirements see \ref iterator
 508         */
 509         typedef iterator_type<true>     const_iterator;
 510
 511         /// Returns a forward iterator addressing the first element in a split-list
 512         /**
 513             For empty list \code begin() == end() \endcode
 514         */
 515         iterator begin()
 516         {
 517             return iterator( m_List.begin(), m_List.end() );
 518         }
 519
 520         /// Returns an iterator that addresses the location succeeding the last element in a split-list
 521         /**
 522             Do not use the value returned by <tt>end</tt> function to access any item.
 523
 524             The returned value can be used only to control reaching the end of the split-list.
 525             For empty list \code begin() == end() \endcode
 526         */
 527         iterator end()
 528         {
 529             return iterator( m_List.end(), m_List.end() );
 530         }
 531
 532         /// Returns a forward const iterator addressing the first element in a split-list
 533         //@{
 534         const_iterator begin() const
 535         {
 536             return const_iterator( m_List.begin(), m_List.end() );
 537         }
 538         const_iterator cbegin() const
 539         {
 540             return const_iterator( m_List.cbegin(), m_List.cend() );
 541         }
 542         //@}
 543
 544         /// Returns an const iterator that addresses the location succeeding the last element in a split-list
 545         //@{
 546         const_iterator end() const
 547         {
 548             return const_iterator( m_List.end(), m_List.end() );
 549         }
 550         const_iterator cend() const
 551         {
 552             return const_iterator( m_List.cend(), m_List.cend() );
 553         }
 554         //@}
 555
 556     protected:
 557         //@cond
 558         iterator insert_( value_type& val )
 559         {
 560             size_t nHash = hash_value( val );
 561             dummy_node_type * pHead = get_bucket( nHash );
 562             assert( pHead != nullptr );
 563
 564             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 565
 566             list_iterator it = m_List.insert_at_( pHead, val );
 567             if ( it != m_List.end() ) {
 568                 inc_item_count();
 569                 m_Stat.onInsertSuccess();
 570                 return iterator( it, m_List.end() );
 571             }
 572             m_Stat.onInsertFailed();
 573             return end();
 574         }
 575
 576         template <typename Func>
 577         std::pair<iterator, bool> ensure_( value_type& val, Func func )
 578         {
 579             size_t nHash = hash_value( val );
 580             dummy_node_type * pHead = get_bucket( nHash );
 581             assert( pHead != nullptr );
 582
 583             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
 584
 585             std::pair<list_iterator, bool> ret = m_List.ensure_at_( pHead, val, func );
 586             if ( ret.first != m_List.end() ) {
 587                 if ( ret.second ) {
 588                     inc_item_count();
 589                     m_Stat.onEnsureNew();
 590                 }
 591                 else
 592                     m_Stat.onEnsureExist();
 593                 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
 594             }
 595             return std::make_pair( end(), ret.second );
 596         }
 597
 598         template <typename Q, typename Less >
 599         iterator find_with_( Q& val, Less pred )
 600         {
 601             CDS_UNUSED( pred );
 602             size_t nHash = hash_value( val );
 603             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 604             dummy_node_type * pHead = get_bucket( nHash );
 605             assert( pHead != nullptr );
 606
 607             auto it = m_List.find_at_( pHead, sv, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
 608             m_Stat.onFind( it != m_List.end() );
 609             return iterator( it, m_List.end() );
 610         }
 611
 612         template <typename Q>
 613         iterator find_( Q const& val )
 614         {
 615             size_t nHash = hash_value( val );
 616             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
 617             dummy_node_type * pHead = get_bucket( nHash );
 618             assert( pHead != nullptr );
 619
 620             auto it = m_List.find_at_( pHead, sv, key_comparator() );
 621             m_Stat.onFind( it != m_List.end() );
 622             return iterator( it, m_List.end() );
 623         }
 624
 625         template <typename Q, typename Compare, typename Func>
 626         bool find_( Q& val, Compare cmp, Func f )
 627         {
 628             size_t nHash = hash_value( val );
 629             split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash( nHash ));
 630             dummy_node_type * pHead = get_bucket( nHash );
 631             assert( pHead != nullptr );
 632             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
 633                 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
 634         }
 635
 636         //@endcond
 637     };
 638
 639 }} // namespace cds::intrusive
 640
 641 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H