Program Listing for File AdaptiveRadixTree.h

↰ Return to documentation for file (ADS/dictionary/AdaptiveRadixTree.h)

/*--------------------------------------------------------------------------*/
/*------------------------ File AdaptiveRadixTree.h ------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_AdaptiveRadixTree
 #define __ADS_AdaptiveRadixTree
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"
#include "ADS/memory/HugePageAllocator.h"
#include "ADS/memory/ObjectPool.h"

#include <cstddef>
#include <cstdint>
#include <cstring>
#include <iterator>
#include <optional>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS AdaptiveRadixTree -------------------------*/
/*--------------------------------------------------------------------------*/

template< class V >
class AdaptiveRadixTree {

/*--------------------------------------------------------------------------*/
 public:

 using Key = std::string;
 using Value = V;

 AdaptiveRadixTree( void ) = default;

 AdaptiveRadixTree( const AdaptiveRadixTree & o );

 AdaptiveRadixTree( AdaptiveRadixTree && o ) noexcept;

 AdaptiveRadixTree & operator=( AdaptiveRadixTree o ) noexcept;

 ~AdaptiveRadixTree();

/*--------------------------------------------------------------------------*/

 [[nodiscard]] std::optional< V > lookup( std::string_view k ) const;

 [[nodiscard]] const V * find( std::string_view k ) const;

 [[nodiscard]] V * find( std::string_view k );

 bool insert( std::string_view k , const V & v );

 bool remove( std::string_view k );

 [[nodiscard]] bool contains( std::string_view k ) const;

 [[nodiscard]] std::size_t size( void ) const;

 [[nodiscard]] bool empty( void ) const;

 void clear( void );

 void swap( AdaptiveRadixTree & o ) noexcept;

 template< class F >
 void forEach( F && f ) const;

 template< class F >
 void forPrefix( std::string_view p , F && f ) const;

 [[nodiscard]] std::vector< std::string > keysWithPrefix(
                                                  std::string_view p ) const;

/*--------------------------------------------------------------------------*/
 private:

 static constexpr unsigned MAXP = 8;

 enum Type : std::uint8_t { N4 , N16 , N48 , N256 };

 struct Leaf {
  V value;
  std::uint32_t len;
  [[nodiscard]] const char * key( void ) const {
   return( reinterpret_cast< const char * >( this + 1 ) );
   }
  [[nodiscard]] std::string_view view( void ) const {
   return( std::string_view( key() , len ) );
   }
  };

 struct Node {
  Type type;
  std::uint16_t count = 0;
  std::uint32_t plen = 0;
  unsigned char prefix[ MAXP ];
  Leaf * term = nullptr;
  explicit Node( Type t ) : type( t ) {}
  };

 struct Node4 : Node {
  unsigned char key[ 4 ];
  void * child[ 4 ];
  Node4( void ) : Node( N4 ) {}
  };

 struct Node16 : Node {
  alignas( 16 ) unsigned char key[ 16 ];
  void * child[ 16 ];
  Node16( void ) : Node( N16 ) {}
  };

 struct Node48 : Node {
  unsigned char index[ 256 ];
  void * child[ 48 ];
  Node48( void ) : Node( N48 ) { std::memset( index , 0 , 256 ); }
  };

 struct Node256 : Node {
  void * child[ 256 ];
  Node256( void ) : Node( N256 ) {
   for( auto & c : child ) c = nullptr;
   }
  };

 [[nodiscard]] static bool isLeaf( const void * p ) {
  return( reinterpret_cast< std::uintptr_t >( p ) & 1 );
  }
 [[nodiscard]] static Leaf * asLeaf( const void * p ) {
  return( reinterpret_cast< Leaf * >( reinterpret_cast< std::uintptr_t >(
                                       p ) - 1 ) );
  }
 [[nodiscard]] static void * tag( Leaf * l ) {
  return( reinterpret_cast< void * >( reinterpret_cast< std::uintptr_t >(
                                       l ) + 1 ) );
  }

 class Slab {
  public:
  Slab( void ) = default;
  Slab( const Slab & ) = delete;
  Slab & operator=( const Slab & ) = delete;
  ~Slab() { release(); }
  [[nodiscard]] void * take( std::size_t bytes );
  void give( void * p , std::size_t bytes ) noexcept;
  void release( void ) noexcept;
  void swap( Slab & o ) noexcept;
  private:
  static constexpr std::size_t STEP = 16 , CLASSES = 32;
  struct Free { Free * next; };
  std::vector< std::pair< char * , std::size_t > > f_blocks;
  char * f_cur = nullptr;
  char * f_end = nullptr;
  Free * f_free[ CLASSES + 1 ] = {};
  };

 [[nodiscard]] Leaf * newLeaf( std::string_view k , const V & v );

 void freeLeaf( Leaf * l ) noexcept;

 template< class N >
 [[nodiscard]] N * make( void );

 void freeNode( Node * n ) noexcept;

 [[nodiscard]] static void * const * child( const Node * n ,
                                            unsigned char c );

 [[nodiscard]] static void * * child( Node * n , unsigned char c );

 [[nodiscard]] static const Leaf * minimum( const void * p );

 [[nodiscard]] static std::uint32_t mismatch( const Node * n ,
                                              std::string_view k ,
                                              std::size_t d );

 void addChild( void * * ref , Node * n , unsigned char c , void * x );

 void split( void * * ref , std::size_t d , std::string_view k ,
             const V & v );

 void removeChild( void * * ref , Node * n , unsigned char c ,
                   void * * slot );

 void shrink( void * * ref , Node * n );

 [[nodiscard]] const Leaf * search( std::string_view k ) const;

 static void ahead( const void * p , unsigned char c );

 static void children( const Node * n );

 void destroy( void * p ) noexcept;

 template< class F >
 static void visit( const void * p , F & f );

 template< class F >
 static void each( const Node * n , F && f );

 [[nodiscard]] bool valid( void ) const;

 [[nodiscard]] bool valid( const void * p , std::string & path ,
                           std::size_t & leaves , bool root ) const;

 void * f_root = nullptr;
 std::size_t f_size = 0;
 ObjectPool< Node4 > f_n4;
 ObjectPool< Node16 > f_n16;
 ObjectPool< Node48 > f_n48;
 ObjectPool< Node256 > f_n256;
 Slab f_slab;

/*------------------------- THE STANDARD INTERFACE -------------------------*/
 public:

 // a constant view of the pairs ( key , value ) by increasing keys,
 // forward, a stack of the nodes on the way to a leaf

 class const_iterator;

 using value_type = std::pair< std::string_view , const V & >;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = value_type;
 using const_reference = value_type;
 using iterator = const_iterator;

 [[nodiscard]] const_iterator begin( void ) const;
 [[nodiscard]] const_iterator end( void ) const;
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

 class const_iterator {
  public:
  using value_type = std::pair< std::string_view , const V & >;
  using reference = value_type;
  using difference_type = std::ptrdiff_t;
  using iterator_concept = std::forward_iterator_tag;
  using iterator_category = std::input_iterator_tag;

  const_iterator( void ) = default;

  reference operator*( void ) const {
   return( reference( f_leaf->view() , f_leaf->value ) );
   }

  const_iterator & operator++( void ) {
   f_leaf = step( f_S );
   return( *this );
   }
  const_iterator operator++( int ) { auto t = *this; ++*this; return( t ); }

  bool operator==( const const_iterator & o ) const {
   return( f_leaf == o.f_leaf );
   }

  private:
  friend class AdaptiveRadixTree;

  struct Frame {
   const Node * node;
   int next;
   };

  explicit const_iterator( const void * root ) {
   if( ! root )
    return;
   if( isLeaf( root ) ) {
    f_leaf = asLeaf( root );
    return;
    }
   f_S.push_back( Frame{ static_cast< const Node * >( root ) , -1 } );
   f_leaf = step( f_S );
   }

  static const Leaf * step( std::vector< Frame > & S );

  std::vector< Frame > f_S;
  const Leaf * f_leaf = nullptr;

 };  // end( class const_iterator )

 };  // end( class AdaptiveRadixTree )

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/dictionary/impl/AdaptiveRadixTree.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* AdaptiveRadixTree.h included */

/*--------------------------------------------------------------------------*/
/*---------------------- End File AdaptiveRadixTree.h ----------------------*/
/*--------------------------------------------------------------------------*/