turbolist/TurboList.hpp

#ifndef TURBO_LIST_HPP
#define TURBO_LIST_HPP

#include<cstdint>
#include<cstdlib>
#include<cassert>

#ifndef TL_NOINLINE
#define TL_NOINLINE __attribute__((noinline))
#endif /* TL_NOINLINE */
#ifndef TL_INLINE
#define TL_INLINE __attribute__((always_inline))
#endif /* TL_INLINE */

#ifndef TL_LIKELY
#define TL_LIKELY(x) __builtin_expect(!!(x), 1)
#endif /* TL_LIKELY */
#ifndef TL_UNLIKELY
#define TL_UNLIKELY(x) __builtin_expect(!!(x), 0)
#endif /* TL_UNLIKELY */

#ifndef TL_GROWTH_RATE
#define TL_GROWTH_RATE 2
#endif /* TL_GROWTH_RATE */

typedef void*(MallocLike)(size_t);
typedef void(FreeLike)(void*);

template<typename T, MallocLike MALLOC = malloc, FreeLike FREE = free>
class TurboList {
	T *old;
	T *nex;

	uint32_t mid; // non-inclusive . . . m
	uint32_t end; // non-inclusive     e . . . .

	uint32_t capacity;

	TL_NOINLINE void grow_and_insert(T elem) noexcept {
			// assert(mid == 0);
			if(old) FREE(old);
			old = nex;
			mid = end;
			capacity *= TL_GROWTH_RATE;
			nex = (T *) MALLOC(this->capacity * sizeof(T));

			// Will go into the INSERT code path here
			insert(elem);
	}

	template<typename... Args>
	TL_NOINLINE T& grow_and_emplace(Args&&... args) noexcept {
			// assert(mid == 0);
			if(old) FREE(old);
			old = nex;
			mid = end;
			capacity *= TL_GROWTH_RATE;
			nex = (T *) MALLOC(this->capacity * sizeof(T));

			// Will go into the INSERT code path here
			return emplace_back(std::forward<Args>(args)...);
	}
public:
	TL_INLINE TurboList(uint32_t initial_size = 0, uint32_t initial_cap = 16) noexcept :
			old(nullptr),
			mid(0),
			end(initial_size),
			capacity(initial_cap) {

		nex = (T *) MALLOC(this->capacity * sizeof(T));
	}

	TL_INLINE ~TurboList() noexcept {
		if(nex) FREE(nex);
		if(old) FREE(old);
	}

	TL_INLINE T& operator[](uint32_t i) const noexcept {
		// This seem to be more often compiled to cmov
		// branchless conditional codes this way..
		//
		T *base = (i < mid) ? old : nex;
		return base[i];
		//
		// if(i < mid)	return old[i];
		// else return nex[i];
		//
		// T* loc = (T*) ((i < mid) * (size_t)old +
		// 	(i>=mid) * (size_t)nex +
		// 	i* sizeof(T));
		// return *loc;
	}

	/** This is much faster than operator[] if you do small amounts of work per access */
	TL_INLINE void iterate(void(callback)(T&)) noexcept {
		// old
		for(uint32_t i = 0; i < mid; ++i) {
			callback(old[i]);
		}
		// nex
		for(uint32_t i = mid; i < end; ++i) {
			callback(nex[i]);
		}
	}

	/** Vector compatibility: Use insert() if you want the inserted thing as reference too */
	TL_INLINE void push_back(T elem) noexcept {
		this->insert(elem);
	}

	/** Vector compatibility: Use pop() if you want the popped thing out as copy too */
	TL_INLINE void pop_back() noexcept {
		if(end > 0) {
			--end;
			if(end < mid) { // end > 0 here!
				end = mid;
				mid = 0;
				FREE(nex);
				nex = old;
				old = nullptr;
			}
		}
	}

	TL_INLINE void insert(T elem) noexcept {
		if(TL_LIKELY(end < capacity)) {

			// INSERT

			/* Same as this - but in this case it measures as faster:
			if(mid > 0) {
				--mid;
				nex[mid] = old[mid];
			}
			*/
			bool hasmid = (mid > 0);
			mid -= hasmid;
			nex[mid] = hasmid ? old[mid] : nex[mid];

			nex[end++] = elem;
		} else {
			// GROW
			grow_and_insert(elem);
		}
	}

	template<typename... Args>
	TL_INLINE T& emplace_back(Args&&... args) {
		if(TL_LIKELY(end < capacity)) {

			// INSERT

			/* Same as this - but in this case it measures as faster:
			if(mid > 0) {
				nex[mid - 1] = old[mid - 1];
				--mid;
			}
			*/
			bool hasmid = (mid > 0);
			mid -= hasmid;
			nex[mid] = hasmid ? old[mid] : nex[mid];

			// Placement new
			return *new (nex + end++) T(std::forward<Args>(args)...);
		} else {
			// GROW
			return grow_and_emplace(std::forward<Args>(args)...);
		}
	}

	// TODO: finalize() call which memcpy remaining elements of old into nex and then frees old and sets nullptr + mid = 0;

	TL_INLINE uint32_t size() noexcept {
		return end;
	}
};

#endif /* TURBO_LIST_HPP */