diff options
Diffstat (limited to 'src/util/allocator.h')
| -rw-r--r-- | src/util/allocator.h | 297 |
1 files changed, 297 insertions, 0 deletions
diff --git a/src/util/allocator.h b/src/util/allocator.h new file mode 100644 index 0000000..ee0ddd8 --- /dev/null +++ b/src/util/allocator.h @@ -0,0 +1,297 @@ +#pragma once + +#include <stdlib.h> +#include <string.h> +#include <functional> +#include "typedef.h" + +template < typename T > +using QSORT_FN = std::function< U8( T*, T* ) >; + +template < typename T > +static U8 qsort_basic_sort( T* t1, T* t2 ) { + return (*t1 > *t2); +} + +// sort fn should return 0 if t1 < t2, else 1 +template < typename T > +static void _qsort( T* arr, I32 low, I32 high, QSORT_FN<T> sortfn = qsort_basic_sort<T> ) { + if( low > high ) + return; + + T pivot = arr[high]; + I32 i = ( low - 1 ); + + for( I32 j = low; j <= high - 1; j++ ) { + if( sortfn( &arr[j], &pivot ) ) { + i++; + T temp = arr[i]; + arr[i] = arr[j]; + arr[j] = temp; + } + } + T temp = arr[i + 1]; + arr[i + 1] = arr[high]; + arr[high] = temp; + I32 pi = i + 1; + + _qsort( arr, low, pi - 1, sortfn ); + _qsort( arr, pi + 1, high, sortfn ); +} + +template < typename T > +struct LIST { + T* data; + U32 capacity; + U32 size; + + using ON_EACH_FN = std::function< void(T*) >; + using ON_SEARCH_FN = std::function< bool(T*) >; + + LIST() { + data = (T*)malloc( sizeof( T ) ); + memset( data, 0, sizeof( T ) ); + capacity = 1; + size = 0; + } + + LIST( U32 _size ) { + if( !_size ) _size = 1; + data = (T*)malloc( sizeof( T ) * _size ); + memset( data, 0, _size * sizeof( T ) ); + capacity = _size; + size = 0; + } + + LIST( const LIST<T>& other ) { + if( !other.capacity || !other.size ) { + capacity = 1; + size = 0; + data = (T*)malloc( sizeof( T ) ); + memset( data, 0, sizeof( T ) ); + return; + } + + data = (T*)malloc( sizeof( T ) * other.capacity ); + memcpy( data, other.data, other.size * sizeof( T ) ); + size = other.size; + capacity = other.capacity; + } + + LIST<T>& operator=( const LIST<T>& other ) { + if( this == &other ) + return *this; + + if( data && data != other.data ) + free( data ); + + data = 0; + + if( !other.capacity || !other.size ) { + capacity = 1; + size = 0; + data = (T*)malloc( sizeof( T ) ); + return *this; + } + + data = (T*)malloc( other.capacity * sizeof( T ) ); + memcpy( data, other.data, other.size * sizeof( T ) ); + size = other.size; + capacity = other.capacity; + + return *this; + } + + ~LIST() { + free( data ); + } + + void reserve( U32 count ) { + if( capacity >= count ) + return; + + T* newblock = (T*)malloc( count * sizeof( T ) ); + memset( newblock, 0, capacity * sizeof( T ) ); + if( data ) { + memcpy( newblock, data, size * sizeof( T ) ); + free( data ); + } + data = newblock; + capacity = count; + } + + void grow() { + capacity = 2 * capacity; + T* newblock = (T*)malloc( capacity * sizeof( T ) ); + memset( newblock, 0, capacity * sizeof( T ) ); + if( data ) { + memcpy( newblock, data, size * sizeof( T ) ); + free( data ); + } + data = newblock; + } + + void shrink() { + if( capacity == 0 ) + return; + + capacity /= 2; + T* newblock = (T*)malloc( capacity * sizeof( T ) ); + if( data ) { + memcpy( newblock, data, capacity * sizeof( T ) ); + free( data ); + } + data = newblock; + } + + // does not call copy funcs or constructors + T* emplace( const T& item ) { + if( capacity == size ) + grow(); + memcpy( &data[size++], &item, sizeof( T ) ); + + return &data[size - 1]; + } + + T* push( const T& item ) { + if( capacity == size ) + grow(); + data[size++] = item; + + return &data[size - 1]; + } + + // does not call copy constructors, raw memcpy + void emplace_list( const LIST<T>& list ) { + if( !list.size ) + return; + capacity += list.size; + T* newblock = (T*)malloc( capacity * sizeof(T) ); + memset( newblock, 0, sizeof(T) * capacity ); + if( data ) { + memcpy( newblock, data, sizeof(T) * size ); + free( data ); + } + + memcpy( &newblock[size], list.data, sizeof(T) * list.size ); + data = newblock; + size += list.size; + } + + // slow - pushes every item individually, calls copy constructors + void push_list( LIST<T>& list ) { + list.each( fn( T* item ) { + push( *item ); + } ); + } + + T pop() { + if( size == 0 ) { + dlog( "LIST::pop_front() : called on empty list\n" ); + abort(); + return {}; + } + + T ret = data[--size]; + if( size < capacity / 4 ) + shrink(); + + return ret; + } + + T pop_front() { + if( size == 0 ) { + dlog( "LIST::pop_front() : called on empty list\n" ); + abort(); + return {}; + } + + T ret = data[0]; + erase( 0 ); + return ret; + } + + void erase( U32 idx ) { + if( idx >= size ) + return; + + for( U32 i = idx; i < size - 1; i++ ) + data[i] = data[i + 1]; + + if( --size < capacity / 4 ) + shrink(); + } + + T& operator[]( U32 idx ) { + return data[idx]; + } + + void clear() { + size = 0; + free( data ); + data = (T*)malloc( sizeof( T ) ); + memset( data, 0, sizeof( T ) ); + capacity = 1; + } + + void each( ON_EACH_FN func ) { + for( U32 i = 0; i < size; ++i ) { + func( &data[i] ); + } + } + + I32 idx_of( const T& what ) { + for( U32 i = 0; i < size; ++i ) { + if( data[i] == what ) { + return i; + } + } + + return -1; + } + + I32 idx_where( ON_SEARCH_FN what ) { + for( U32 i = 0; i < size; ++i ) { + if( what( &data[i] ) ) { + return i; + } + } + + return -1; + } + + T* find( const T& what ) { + for( U32 i = 0; i < size; ++i ) { + if( data[i] == what ) { + return &data[i]; + } + } + return 0; + } + + T* where( ON_SEARCH_FN what ) { + for( U32 i = 0; i < size; ++i ) { + if( what( &data[i] ) ) { + return &data[i]; + } + } + return 0; + } + + // does not copy, sorts in place + // + // sort fn should return 0 if t1 < t2, else 1 + LIST<T>& sort( QSORT_FN<T> fn = qsort_basic_sort<T> ) { + _qsort<T>( data, 0, size - 1, fn ); + return *this; + } + + // creates a sorted copy + // + // sort fn should return 0 if t1 < t2, else 1 + LIST<T> sorted( QSORT_FN<T> fn = qsort_basic_sort<T> ) { + LIST<T> ret = LIST<T>( *this ); + ret.sort( fn ); + return ret; + } +}; |