Program Listing for File CellHeap.h

↰ Return to documentation for file (ADS/memory/CellHeap.h)

/*--------------------------------------------------------------------------*/
/*---------------------------- File CellHeap.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

#include <cstddef>
#include <set>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS CellHeap ------------------------------*/
/*--------------------------------------------------------------------------*/

class CellHeap {

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

 using Value = long;

 static constexpr Value nil = -1;

 static Value atom( long k );

 [[nodiscard]] static bool isCell( Value v );

 explicit CellHeap( std::size_t n );

 Value cons( Value car , Value cdr );

 [[nodiscard]] Value car( Value c ) const;
 [[nodiscard]] Value cdr( Value c ) const;
 void setCar( Value c , Value v );
 void setCdr( Value c , Value v );

 void addRoot( Value c );
 void removeRoot( Value c );

 std::size_t collect( bool reversal = true );

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

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

 struct Cell {
  Value car = nil , cdr = nil;
  bool mark = false;
  bool cdrSide = false;
  bool free = true;
  };

 void markReversal( Value root );
 void markStack( Value root );

 [[nodiscard]] std::vector< bool > reachable( void ) const;

 std::vector< Cell > f_C;
 Value f_free = nil;
 std::size_t f_nfree = 0;
 std::multiset< Value > f_roots;

 };  // end( class CellHeap )

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

}  // end( namespace ADS )

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

#include "ADS/memory/impl/CellHeap.tpp"

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

#endif  /* CellHeap.h included */

/*--------------------------------------------------------------------------*/
/*-------------------------- End File CellHeap.h ---------------------------*/
/*--------------------------------------------------------------------------*/