A PiggyList that allows insertAt functionality. More...

#include <PiggyList.h>

Collaboration diagram for souffle::RandomInsertPiggyList< T >:

Public Member Functions
void	clear ()

void	freeList ()
	Free the arrays allocated within the linked list nodes. More...

T &	get (size_t index) const

T *	getBlock (size_t blockNum) const

void	insertAt (size_t index, T value)

RandomInsertPiggyList &	operator= (RandomInsertPiggyList &&other)=delete

RandomInsertPiggyList &	operator= (RandomInsertPiggyList &other)=delete

	RandomInsertPiggyList ()=default

	RandomInsertPiggyList (const RandomInsertPiggyList &other)
	copy constructor More...

	RandomInsertPiggyList (RandomInsertPiggyList &&other)=delete

	RandomInsertPiggyList (size_t initialbitsize)

size_t	size () const

	~RandomInsertPiggyList ()

Data Fields
const size_t	BLOCKBITS = 16ul

std::array< std::atomic< T * >, maxContainers >	blockLookupTable = {}

const size_t	INITIALBLOCKSIZE = (1ul << BLOCKBITS)

std::atomic< size_t >	numElements {0}

SpinLock	slock

Static Public Attributes
static constexpr size_t	maxContainers = 64

Detailed Description

template<class T>
class souffle::RandomInsertPiggyList< T >

A PiggyList that allows insertAt functionality.

This means we can't append, as we don't know the next available element. insertAt is dangerous. You must be careful not to call it for the same index twice!

Definition at line 37 of file PiggyList.h.

Constructor & Destructor Documentation

◆ RandomInsertPiggyList() [1/4]

template<class T >

souffle::RandomInsertPiggyList< T >::RandomInsertPiggyList ( )

default

◆ RandomInsertPiggyList() [2/4]

template<class T >

souffle::RandomInsertPiggyList< T >::RandomInsertPiggyList ( size_t initialbitsize )

inline

Definition at line 42 of file PiggyList.h.

42 : BLOCKBITS(initialbitsize) {}

◆ RandomInsertPiggyList() [3/4]

template<class T >

souffle::RandomInsertPiggyList< T >::RandomInsertPiggyList ( const RandomInsertPiggyList< T > & other )

inline

copy constructor

Definition at line 45 of file PiggyList.h.

                                                               : BLOCKBITS(other.BLOCKBITS) {
         this->numElements.store(other.numElements.load());
  
         // copy blocks from the old lookup table to this one
         for (size_t i = 0; i < maxContainers; ++i) {
             if (other.blockLookupTable[i].load() != nullptr) {
                 // calculate the size of that block
                 const size_t blockSize = INITIALBLOCKSIZE << i;
  
                 // allocate that in the new container
                 this->blockLookupTable[i].store(new T[blockSize]);
  
                 // then copy the stuff over
                 std::memcpy(this->blockLookupTable[i].load(), other.blockLookupTable[i].load(),
                         blockSize * sizeof(T));
             }
         }
     }

◆ RandomInsertPiggyList() [4/4]

template<class T >

souffle::RandomInsertPiggyList< T >::RandomInsertPiggyList ( RandomInsertPiggyList< T > && other )

delete

◆ ~RandomInsertPiggyList()

template<class T >

souffle::RandomInsertPiggyList< T >::~RandomInsertPiggyList ( )

inline

Definition at line 71 of file PiggyList.h.

                              {
         freeList();
     }

Member Function Documentation

◆ clear()

template<class T >

void souffle::RandomInsertPiggyList< T >::clear ( )

inline

Definition at line 110 of file PiggyList.h.

                  {
         freeList();
         numElements.store(0);
     }

Referenced by souffle::SparseDisjointSet< value_type >::size(), and souffle::test::TEST().

◆ freeList()

template<class T >

void souffle::RandomInsertPiggyList< T >::freeList ( )

inline

Free the arrays allocated within the linked list nodes.

Definition at line 130 of file PiggyList.h.

                     {
         slock.lock();
         // delete all - deleting a nullptr is a no-op
         for (size_t i = 0; i < maxContainers; ++i) {
             delete[] blockLookupTable[i].load();
             // reset the container within to be empty.
             blockLookupTable[i].store(nullptr);
         }
         slock.unlock();
     }

Referenced by souffle::RandomInsertPiggyList< SparseDomain >::clear(), and souffle::RandomInsertPiggyList< SparseDomain >::~RandomInsertPiggyList().

◆ get()

template<class T >

T& souffle::RandomInsertPiggyList< T >::get ( size_t index ) const

inline

Definition at line 83 of file PiggyList.h.

                                       {
         size_t nindex = index + INITIALBLOCKSIZE;
         size_t blockNum = (63 - __builtin_clzll(nindex));
         size_t blockInd = (nindex) & ((1 << blockNum) - 1);
         return this->getBlock(blockNum - BLOCKBITS)[blockInd];
     }

Referenced by souffle::RandomInsertPiggyList< SparseDomain >::insertAt().

◆ getBlock()

template<class T >

T* souffle::RandomInsertPiggyList< T >::getBlock ( size_t blockNum ) const

inline

Definition at line 79 of file PiggyList.h.

                                               {
         return blockLookupTable[blockNum];
     }

Referenced by souffle::RandomInsertPiggyList< SparseDomain >::get().

◆ insertAt()

template<class T >

void souffle::RandomInsertPiggyList< T >::insertAt	(	size_t	index,
		T	value
	)

inline

Definition at line 90 of file PiggyList.h.

                                          {
         // starting with an initial blocksize requires some shifting to transform into a nice powers of two
         // series
         size_t blockNum = (63 - __builtin_clzll(index + INITIALBLOCKSIZE)) - BLOCKBITS;
  
         // allocate the block if not allocated
         if (blockLookupTable[blockNum].load() == nullptr) {
             slock.lock();
             if (blockLookupTable[blockNum].load() == nullptr) {
                 blockLookupTable[blockNum].store(new T[INITIALBLOCKSIZE << blockNum]);
             }
             slock.unlock();
         }
  
         this->get(index) = value;
         // we ALWAYS increment size, even if there was something there before (its impossible to tell!)
         // the onus is up to the user to not call this for an index twice
         ++numElements;
     }

Referenced by souffle::test::TEST().

◆ operator=() [1/2]

template<class T >

RandomInsertPiggyList& souffle::RandomInsertPiggyList< T >::operator= ( RandomInsertPiggyList< T > && other )

delete

◆ operator=() [2/2]

template<class T >

RandomInsertPiggyList& souffle::RandomInsertPiggyList< T >::operator= ( RandomInsertPiggyList< T > & other )

delete

◆ size()

template<class T >

size_t souffle::RandomInsertPiggyList< T >::size ( ) const

inline

Definition at line 75 of file PiggyList.h.

                                {
         return numElements.load();
     }

Referenced by souffle::test::TEST().

Field Documentation

◆ BLOCKBITS

template<class T >

const size_t souffle::RandomInsertPiggyList< T >::BLOCKBITS = 16ul

Definition at line 114 of file PiggyList.h.

Referenced by souffle::RandomInsertPiggyList< SparseDomain >::get(), and souffle::RandomInsertPiggyList< SparseDomain >::insertAt().

◆ blockLookupTable

template<class T >

std::array<std::atomic<T*>, maxContainers> souffle::RandomInsertPiggyList< T >::blockLookupTable = {}

Definition at line 122 of file PiggyList.h.

Referenced by souffle::RandomInsertPiggyList< SparseDomain >::freeList(), souffle::RandomInsertPiggyList< SparseDomain >::getBlock(), souffle::RandomInsertPiggyList< SparseDomain >::insertAt(), and souffle::RandomInsertPiggyList< SparseDomain >::RandomInsertPiggyList().

◆ INITIALBLOCKSIZE

template<class T >

const size_t souffle::RandomInsertPiggyList< T >::INITIALBLOCKSIZE = (1ul << BLOCKBITS)

Definition at line 115 of file PiggyList.h.

Referenced by souffle::RandomInsertPiggyList< SparseDomain >::get(), souffle::RandomInsertPiggyList< SparseDomain >::insertAt(), and souffle::RandomInsertPiggyList< SparseDomain >::RandomInsertPiggyList().

◆ maxContainers

template<class T >

constexpr size_t souffle::RandomInsertPiggyList< T >::maxContainers = 64

staticconstexpr

Definition at line 121 of file PiggyList.h.

Referenced by souffle::RandomInsertPiggyList< SparseDomain >::freeList(), and souffle::RandomInsertPiggyList< SparseDomain >::RandomInsertPiggyList().

◆ numElements

template<class T >

std::atomic<size_t> souffle::RandomInsertPiggyList< T >::numElements {0}

Definition at line 118 of file PiggyList.h.

Referenced by souffle::RandomInsertPiggyList< SparseDomain >::clear(), souffle::RandomInsertPiggyList< SparseDomain >::insertAt(), souffle::RandomInsertPiggyList< SparseDomain >::RandomInsertPiggyList(), and souffle::RandomInsertPiggyList< SparseDomain >::size().

◆ slock

template<class T >

SpinLock souffle::RandomInsertPiggyList< T >::slock

mutable

Definition at line 125 of file PiggyList.h.

Referenced by souffle::RandomInsertPiggyList< SparseDomain >::freeList(), and souffle::RandomInsertPiggyList< SparseDomain >::insertAt().

The documentation for this class was generated from the following file:

include/souffle/datastructure/PiggyList.h

Public Member Functions

Data Fields

Static Public Attributes

Detailed Description

template<class T> class souffle::RandomInsertPiggyList< T >

Constructor & Destructor Documentation

◆ RandomInsertPiggyList() [1/4]

◆ RandomInsertPiggyList() [2/4]

◆ RandomInsertPiggyList() [3/4]

◆ RandomInsertPiggyList() [4/4]

◆ ~RandomInsertPiggyList()

Member Function Documentation

◆ clear()

◆ freeList()

◆ get()

◆ getBlock()

◆ insertAt()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ size()

Field Documentation

◆ BLOCKBITS

◆ blockLookupTable

◆ INITIALBLOCKSIZE

◆ maxContainers

◆ numElements

◆ slock

template<class T>
class souffle::RandomInsertPiggyList< T >