#include <PiggyList.h>

Collaboration diagram for souffle::PiggyList< T >:

Data Structures
class	iterator

Public Member Functions
size_t	append (T element)

iterator	begin ()

void	clear ()
	Clear all elements from the PiggyList. More...

size_t	createNode ()

iterator	end ()

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

T &	get (size_t index) const
	Retrieve a reference to the stored value at index. More...

T *	getBlock (size_t blocknum) const

PiggyList &	operator= (const PiggyList &other)=delete
	copy assign ctor More...

	PiggyList ()

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

	PiggyList (PiggyList &&other)=delete
	move constructor More...

	PiggyList (size_t initialbitsize)

size_t	size () const
	Well, returns the number of nodes exist within the list + number of nodes queued to be inserted The reason for this, is that there may be many nodes queued up that haven't had time to had containers created and updated. More...

	~PiggyList ()

Data Fields
size_t	allocsize = BLOCKSIZE

const size_t	BLOCKBITS = 16ul

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

const size_t	BLOCKSIZE = (1ul << BLOCKBITS)

std::atomic< size_t >	container_size = 0

std::atomic< size_t >	m_size = 0

std::atomic< size_t >	num_containers = 0

SpinLock	sl

Static Public Attributes
static constexpr size_t	max_conts = 64

Detailed Description

template<class T>
class souffle::PiggyList< T >

Definition at line 143 of file PiggyList.h.

Constructor & Destructor Documentation

◆ PiggyList() [1/4]

template<class T >

souffle::PiggyList< T >::PiggyList ( )

inline

Definition at line 145 of file PiggyList.h.

145 : num_containers(0), container_size(0), m_size(0) {}

◆ PiggyList() [2/4]

template<class T >

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

inline

Definition at line 146 of file PiggyList.h.

147 : BLOCKBITS(initialbitsize), num_containers(0), container_size(0), m_size(0) {}

◆ PiggyList() [3/4]

template<class T >

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

inline

copy constructor

Definition at line 150 of file PiggyList.h.

                                       : BLOCKBITS(other.BLOCKBITS) {
         num_containers.store(other.num_containers.load());
         container_size.store(other.container_size.load());
         m_size.store(other.m_size.load());
         // copy each chunk from other into this
         // the size of the next container to allocate
         size_t cSize = BLOCKSIZE;
         for (size_t i = 0; i < other.num_containers; ++i) {
             this->blockLookupTable[i] = new T[cSize];
             std::memcpy(this->blockLookupTable[i], other.blockLookupTable[i], cSize * sizeof(T));
             cSize <<= 1;
         }
         // if this isn't the case, uhh
         assert((cSize >> 1) == container_size.load());
     }

◆ PiggyList() [4/4]

template<class T >

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

delete

move constructor

◆ ~PiggyList()

template<class T >

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

inline

Definition at line 171 of file PiggyList.h.

                  {
         freeList();
     }

Member Function Documentation

◆ append()

template<class T >

size_t souffle::PiggyList< T >::append ( T element )

inline

Definition at line 189 of file PiggyList.h.

                              {
         size_t new_index = m_size.fetch_add(1, std::memory_order_acquire);
  
         // will this not fit?
         if (container_size < new_index + 1) {
             sl.lock();
             // check and add as many containers as required
             while (container_size < new_index + 1) {
                 blockLookupTable[num_containers] = new T[allocsize];
                 num_containers += 1;
                 container_size += allocsize;
                 // double the number elements that will be allocated next time
                 allocsize <<= 1;
             }
             sl.unlock();
         }
  
         this->get(new_index) = element;
         return new_index;
     }

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

◆ begin()

template<class T >

iterator souffle::PiggyList< T >::begin ( )

inline

Definition at line 295 of file PiggyList.h.

                      {
         return iterator(this);
     }

◆ clear()

template<class T >

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

inline

Clear all elements from the PiggyList.

Definition at line 246 of file PiggyList.h.

                  {
         freeList();
         m_size = 0;
         num_containers = 0;
  
         allocsize = BLOCKSIZE;
         container_size = 0;
     }

◆ createNode()

template<class T >

size_t souffle::PiggyList< T >::createNode ( )

inline

Definition at line 210 of file PiggyList.h.

                         {
         size_t new_index = m_size.fetch_add(1, std::memory_order_acquire);
  
         // will this not fit?
         if (container_size < new_index + 1) {
             sl.lock();
             // check and add as many containers as required
             while (container_size < new_index + 1) {
                 blockLookupTable[num_containers] = new T[allocsize];
                 num_containers += 1;
                 container_size += allocsize;
                 // double the number elements that will be allocated next time
                 allocsize <<= 1;
             }
             sl.unlock();
         }
  
         return new_index;
     }

◆ end()

template<class T >

iterator souffle::PiggyList< T >::end ( )

inline

Definition at line 298 of file PiggyList.h.

                    {
         return iterator(this, size());
     }

◆ freeList()

template<class T >

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

inline

Free the arrays allocated within the linked list nodes.

Definition at line 320 of file PiggyList.h.

                     {
         sl.lock();
         // we don't know which ones are taken up!
         for (size_t i = 0; i < num_containers; ++i) {
             delete[] blockLookupTable[i];
         }
         sl.unlock();
     }

Referenced by souffle::PiggyList< std::atomic< block_t > >::clear(), and souffle::PiggyList< std::atomic< block_t > >::~PiggyList().

◆ get()

template<class T >

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

inline

Retrieve a reference to the stored value at index.

Parameters

index position to search

Returns: the value at index

Definition at line 235 of file PiggyList.h.

                                       {
         // supa fast 2^16 size first block
         size_t nindex = index + BLOCKSIZE;
         size_t blockNum = (63 - __builtin_clzll(nindex));
         size_t blockInd = (nindex) & ((1 << blockNum) - 1);
         return this->getBlock(blockNum - BLOCKBITS)[blockInd];
     }

Referenced by souffle::PiggyList< std::atomic< block_t > >::append(), souffle::EquivalenceRelation< Arity >::insert(), souffle::EquivalenceRelation< TupleType >::iterator::iterator(), souffle::PiggyList< T >::iterator::operator*(), and souffle::DisjointSet::size().

◆ getBlock()

template<class T >

T* souffle::PiggyList< T >::getBlock ( size_t blocknum ) const

inline

Definition at line 185 of file PiggyList.h.

                                               {
         return this->blockLookupTable[blocknum];
     }

Referenced by souffle::PiggyList< std::atomic< block_t > >::get().

◆ operator=()

template<class T >

PiggyList& souffle::PiggyList< T >::operator= ( const PiggyList< T > & other )

delete

copy assign ctor

◆ size()

template<class T >

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

inline

Well, returns the number of nodes exist within the list + number of nodes queued to be inserted The reason for this, is that there may be many nodes queued up that haven't had time to had containers created and updated.

Returns: the number of nodes exist within the list + number of nodes queued to be inserted

Definition at line 181 of file PiggyList.h.

                                {
         return m_size.load();
     };

Referenced by souffle::PiggyList< std::atomic< block_t > >::end(), souffle::EquivalenceRelation< Arity >::insert(), and souffle::EquivalenceRelation< TupleType >::iterator::iterator().

Field Documentation

◆ allocsize

template<class T >

size_t souffle::PiggyList< T >::allocsize = BLOCKSIZE

Definition at line 306 of file PiggyList.h.

Referenced by souffle::PiggyList< std::atomic< block_t > >::append(), souffle::PiggyList< std::atomic< block_t > >::clear(), and souffle::PiggyList< std::atomic< block_t > >::createNode().

◆ BLOCKBITS

template<class T >

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

Definition at line 301 of file PiggyList.h.

Referenced by souffle::PiggyList< std::atomic< block_t > >::get().

◆ blockLookupTable

template<class T >

std::array<T*, max_conts> souffle::PiggyList< T >::blockLookupTable = {}

Definition at line 312 of file PiggyList.h.

Referenced by souffle::PiggyList< std::atomic< block_t > >::append(), souffle::PiggyList< std::atomic< block_t > >::createNode(), souffle::PiggyList< std::atomic< block_t > >::freeList(), souffle::PiggyList< std::atomic< block_t > >::getBlock(), and souffle::PiggyList< std::atomic< block_t > >::PiggyList().

◆ BLOCKSIZE

template<class T >

const size_t souffle::PiggyList< T >::BLOCKSIZE = (1ul << BLOCKBITS)

Definition at line 302 of file PiggyList.h.

Referenced by souffle::PiggyList< std::atomic< block_t > >::clear(), souffle::PiggyList< std::atomic< block_t > >::get(), and souffle::PiggyList< std::atomic< block_t > >::PiggyList().

◆ container_size

template<class T >

std::atomic<size_t> souffle::PiggyList< T >::container_size = 0

Definition at line 307 of file PiggyList.h.

Referenced by souffle::PiggyList< std::atomic< block_t > >::append(), souffle::PiggyList< std::atomic< block_t > >::clear(), souffle::PiggyList< std::atomic< block_t > >::createNode(), and souffle::PiggyList< std::atomic< block_t > >::PiggyList().

◆ m_size

template<class T >

std::atomic<size_t> souffle::PiggyList< T >::m_size = 0

Definition at line 308 of file PiggyList.h.

Referenced by souffle::PiggyList< std::atomic< block_t > >::append(), souffle::PiggyList< std::atomic< block_t > >::clear(), souffle::PiggyList< std::atomic< block_t > >::createNode(), souffle::PiggyList< std::atomic< block_t > >::PiggyList(), and souffle::PiggyList< std::atomic< block_t > >::size().

◆ max_conts

template<class T >

constexpr size_t souffle::PiggyList< T >::max_conts = 64

staticconstexpr

Definition at line 311 of file PiggyList.h.

◆ num_containers

template<class T >

std::atomic<size_t> souffle::PiggyList< T >::num_containers = 0

Definition at line 305 of file PiggyList.h.

Referenced by souffle::PiggyList< std::atomic< block_t > >::append(), souffle::PiggyList< std::atomic< block_t > >::clear(), souffle::PiggyList< std::atomic< block_t > >::createNode(), souffle::PiggyList< std::atomic< block_t > >::freeList(), and souffle::PiggyList< std::atomic< block_t > >::PiggyList().

◆ sl

template<class T >

SpinLock souffle::PiggyList< T >::sl

mutable

Definition at line 315 of file PiggyList.h.

Referenced by souffle::PiggyList< std::atomic< block_t > >::append(), souffle::PiggyList< std::atomic< block_t > >::createNode(), and souffle::PiggyList< std::atomic< block_t > >::freeList().

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

include/souffle/datastructure/PiggyList.h

Data Structures

Public Member Functions

Data Fields

Static Public Attributes

Detailed Description

template<class T> class souffle::PiggyList< T >

Constructor & Destructor Documentation

◆ PiggyList() [1/4]

◆ PiggyList() [2/4]

◆ PiggyList() [3/4]

◆ PiggyList() [4/4]

◆ ~PiggyList()

Member Function Documentation

◆ append()

◆ begin()

◆ clear()

◆ createNode()

◆ end()

◆ freeList()

◆ get()

◆ getBlock()

◆ operator=()

◆ size()

Field Documentation

◆ allocsize

◆ BLOCKBITS

◆ blockLookupTable

◆ BLOCKSIZE

◆ container_size

◆ m_size

◆ max_conts

◆ num_containers

◆ sl

template<class T>
class souffle::PiggyList< T >