A class for storing data.

mstore.hpp

#ifndef UTILS_MSTORE_HPP_INCLUDED
#define UTILS_MSTORE_HPP_INCLUDED

// C++ version of stdlib.h used, so that its memory free() function can be distinguished from mstore::free
#include <cstdlib>
#include <string.h>
#include <stddef.h>
#include <stdint.h>
#include <stdbool.h>
#include <limits.h>

//
// NOTE: A set bit (1-bit) in *free means that slot is free to be allocated.
//

// Some constants, adjusted by architecture. (MS stands for mstore)
#ifndef __x86_64__
  #define MS_SHIFT      ((unsigned int) 5)
  #define MS_MASK       ((unsigned int) 0x1F) // 0b00011111 (five set bits)
  #define MS_LOG2_SHIFT ((unsigned int) 2)    // log2(sizeof(msfree_t))          = log2(4) = 2
  #define MS_LOG2_MASK  ((unsigned int) 0x03) // 0b00000011 (MS_LOG2_SHIFT bits) = 2 set bits
  typedef uint32_t msfree_t;
#else
  #define MS_SHIFT      ((unsigned int) 6)
  #define MS_MASK       ((unsigned int) 0x3F) // 0b00111111 (six set bits)
  #define MS_LOG2_SHIFT ((unsigned int) 3)    // log2(sizeof(msfree_t))          = log2(8) = 3
  #define MS_LOG2_MASK  ((unsigned int) 0x07) // 0b00000111 (MS_LOG2_SHIFT bits) = 3 set bits
  typedef uint64_t msfree_t;
#endif

template <class T>
class mstore
{
	private:
		T        *data;
		msfree_t *free;
		msfree_t *last; // last keeps a pointer to the last known free slot bit in msfree_t *free.
		
		size_t dsize, fsize; // d[ata]-size and f[ree]-size, repectively.
		
		// Does not fix the problem.
		//class iterator;
		//friend class iterator;
		
		class iterator
		{
			private:
				size_t slot;
			
			public:
				iterator(size_t new_slot) : slot(new_slot) {}

				T&        operator* ()                         { return data[slot];      }
				bool      operator!=(const iterator& it) const { return slot != it.slot; }
				iterator& operator++();
		};
		
		//typedef iterator iterator;
		typedef ptrdiff_t difference_type;
		typedef size_t    size_type;
		typedef T         value_type;
		typedef T*        pointer;
		typedef T&        reference;
		
	public:
		 mstore()                { data = NULL; free = NULL; last = NULL; dsize = 0; fsize = 0;                   }
		 mstore(size_t new_size) { data = NULL; free = NULL; last = NULL; dsize = 0; fsize = 0; resize(new_size); }
		~mstore()                { release();                                                                     }
		
		bool resize(size_t new_size);
		void release();
		
		size_t allocate();
		void   deallocate(size_t slot);
		
		iterator begin() { return iterator(0);         }
		iterator end  () { return iterator(dsize - 1); }
		
		void   iterate(void (*function) (mstore& container, T& object_ptr, void *argument), void *argument);
		size_t next   (size_t slot);
		
		inline T& operator[] (size_t slot)
		{
			if (slot >= dsize)
			{
				// TODO: add logging here: Out of bounds array access.
				return data[0];
			}
			
			return data[slot];
		};
};



///////////////////////////////////////////////////////////////////////////////
////////////////////////// ---- IMPLEMENTATIONS ---- //////////////////////////
///////////////////////////////////////////////////////////////////////////////

template <class T>
bool mstore<T>::resize(size_t new_dsize)
{
	// Round up new_dsize to the next multiple of (number of bits in msfree_t) = 32 or 64
	new_dsize = (new_dsize & ~MS_MASK)  + (((new_dsize & MS_MASK) != 0) << MS_SHIFT);
	
	size_t new_fsize = new_dsize >> MS_SHIFT;
	
	free = (msfree_t*) std::realloc(free, new_fsize * sizeof(msfree_t));
	data = (T*)        std::realloc(data, new_dsize * sizeof(T)       );
	
	// If the new_dsize wasn't deliberately 0, check if any of the reallocs returned NULLs.
	if (new_dsize != 0 && (free == NULL || data == NULL))
	{
		// TODO: add logging here: Memory allocation failed.
		release();
		
		return false;
	}
	
	// Set any newly allocated bytes to their defaults: set all new slots to free, and data to 0.
	if (new_dsize > dsize)
	{
		memset(free + fsize, 0xFF, (new_fsize - fsize) * sizeof(msfree_t));
		memset(data + dsize, 0x00, (new_dsize - dsize) * sizeof(T)       );
	}
	
	// TODO: add logging here: Memory allocation successful.
	
	dsize = new_dsize;
	fsize = new_fsize;
	last  = free;
	
	return true;
}

// ------------------------------------------------------------------------- //

template <class T>
void mstore<T>::release()
{
	std::free(data);
	std::free(free);
	
	data = NULL;
	free = NULL;
	last = NULL;
	
	dsize = 0;
	fsize = 0;
}

// ------------------------------------------------------------------------- //

//
// NOTE: Each line of this function has been carefully coded so that it is
//       compiled very efficiently. Be careful editing it, but other compilers
//       will probably ruin this precious code.
//

template <class T>
size_t mstore<T>::allocate()
{
	// Start checking from the last pointer, and note: ptr2 - ptr1 = number of elements, not bytes.
	msfree_t *ptr   = last;
	size_t    count = fsize - (last - free);
	size_t    slot = 0;
	
	// search:
		while (slot != count)
		{
			if (*ptr)
				goto found;
			
			ptr++;
			slot++;
		}
	
	// failure:
		{
			// TODO: add logging here: Slot allocation/search failed, attempting resize, let resize() report status.
			// NOTE: Current fix is to only resize the array, later will add more complex mechanisms to manage the size.
			
			ptrdiff_t displacement = ptr - free;
			
			if (!resize(dsize + (sizeof(T) < 4096 ? (4096 / sizeof(T)) : 16 * sizeof(T))))
				return 0;
			
			// In case the array was moved to a new location, restore ptr with the displacement from free it had.
			ptr = free + displacement;
			
			// We let it continue from here because ptr should point at a new empty msfree_t, because of the last ptr++.
		}
	
	found:
		// No free bit was found below here, so update last to a new best guess.
		last = ptr;
		
		// This simply uses BSF to load the index of the lowest 1-bit into slot, and then resets it with BTR.
		__asm__ (
		          "bsf	%0, %1" "\n\t"
		          "btr	%1, %0"
		         : "=r" (slot), "+r" (*ptr)
		         : /* no sole inputs */
		         : "cc"
		        );
		
		// Here is a derivation of the formula. Note, normally (ptr2 - ptr1) gives the number of elements,
		// but here (ptrdiff_t) is used so that it means their displacement, to avoid more calculations.
		// => slot += ((ptr - free)            / sizeof(msfree_t)) * 64
		// =>         ((ptr - free)          >> 3 = MS_LOG2_SHIFT) << 6 = MS_SHIFT
		// =>         ((ptr - free) & mask out MS_LOG2_SHIFT bits) << (MS_SHIFT - MS_LOG2_SHIFT)
		// =>         ((ptr - free)               & ~MS_LOG2_MASK) << 3
		slot += (((ptrdiff_t) ptr - (ptrdiff_t) free) & ~MS_LOG2_MASK) * 8;
		
	return slot;
}

// ------------------------------------------------------------------------- //

template <class T>
void mstore<T>::deallocate(size_t slot)
{
	msfree_t *ptr = (msfree_t*) ((long unsigned int) free + (long unsigned int) (slot & ~MS_MASK));
	
	if (ptr < last)
		last = ptr;
	
	__asm__ (
	         "bts	%0, %1"
	         : "+r" (*ptr)
	         : "ri" (slot & MS_MASK)
	         : "cc"
	        );
}

// ------------------------------------------------------------------------- //

template <class T>
void mstore<T>::iterate (void (*function) (mstore<T>& container, T& object_ptr, void *argument), void *argument)
{
	T        *data_ptr = data;
	msfree_t *free_ptr = free;
	msfree_t *end_ptr  = free + fsize;
	
	msfree_t temp;
	msfree_t bitslot;
	
	while (free_ptr != end_ptr)
	{
		// By NOTing, the used (0) bits become 1-bits and then we can use BSF to get their indexes.
		temp = ~(*free_ptr);
		
		while (temp)
		{
			// This simply uses BSF to load the index of the lowest 1-bit in temp into bitslot, and then resets it with BTR.
			__asm__ (
			         "bsf	%0, %1" "\n\t"
			         "btr	%1, %0"
			         : "=r" (bitslot), "+r" (temp)
			         : /* no sole inputs */
			         : "cc"
			        );
			
			// Call the given function, giving it (this), the pointer to the object, and the user-supplied argument.
			function(*this, *(data_ptr + bitslot), argument);
		}
		
		// data_ptr is like (data + slot*32 (or 64)), so by simply adding a bitslot to it,
		// we retrieve a pointer to the object. Hence every iteration, 32 (or 64) is added.
		free_ptr++;
		data_ptr += (sizeof(msfree_t) * CHAR_BIT);
	}
}

// ------------------------------------------------------------------------- //

template <class T>
typename mstore<T>::iterator& mstore<T>::iterator::operator++()
{
	msfree_t *free_ptr = (msfree_t*) ((long unsigned int) free + (long unsigned int) (slot & ~MS_MASK));
	msfree_t *end_ptr  = free + fsize;
	
	msfree_t temp = ~(*free_ptr), temp2;
	
	// Reset the bit corresponding to slot so it isn't retrieved as the answer.
	__asm__ ("btr	%0, %1" : "+r" (temp) : "ri" (slot & MS_MASK) : "cc");
	goto check;
	
	for (; free_ptr != end_ptr; free_ptr++)
	{
		temp = ~(*free_ptr);
		
		check:
		if (temp)
		{
			__asm__ (
			         "bsf	%1, %0"
			         : "=r" (temp2)
			         : "r"  (temp)
			         : "cc"
			        );
			
			slot = (free_ptr - free) + temp2;
			break;
		}
	}
	
	return *this;
}

// ------------------------------------------------------------------------- //

#endif // UTILS_MSTORE_HPP_INCLUDED