Commit ff01629
Changed files (8)
datatypes
memory
platform
testing
tests
datatypes/array.h
@@ -0,0 +1,364 @@
+#ifndef NOTLIBC_HEADER_DATATYPES_ARRAY_INCLUDED
+#define NOTLIBC_HEADER_DATATYPES_ARRAY_INCLUDED
+
+#include "memory/heap.h"
+#include "platform/common/types.h"
+#include "platform/info/compiler.h"
+#include "platform/info/build.h"
+
+#include "./pointer.h"
+
+
+#define ARR_FOREACH( T, varname, arr) \
+ for( T *varname = &arr->data[0]; varname < &arr->data[arr->a.len]; varname += 1 )
+
+STRUCT( AnyArr,
+ usize len;
+ DEBUG(
+ Heap *heap;
+ usize checksum;
+ )
+);
+
+
+static inline Status AnyArr_create( usize count, AnyArr **out, Heap *h, usize elem_size );
+static inline Status AnyArr_destroy( AnyArr** arr, Heap *h );
+
+static inline Status AnyArr_extend( AnyArr **arr, usize additional_len, Heap *h, usize elem_size );
+static inline Status AnyArr_truncate( AnyArr *arr, usize cutlen, usize elem_size );
+
+static inline Status AnyArr_inflate( AnyArr **arr, usize additional_count, Heap *h, usize elem_size );
+static inline Status AnyArr_deflate( AnyArr **arr, Heap *h, usize elem_size );
+
+static inline Status AnyArr_push( AnyArr **arr, void* el, Heap *h, usize elem_size );
+static inline Status AnyArr_pop( AnyArr *arr, void* el_out, usize elem_size );
+
+static inline Status AnyArr_dup( const AnyArr *arr, AnyArr **out_arr, Heap *h, usize elem_size );
+
+DEBUG(
+ static inline void _AnyArr_update_checksum( AnyArr *arr );
+ static inline void _AnyArr_validate( const AnyArr *arr );
+)
+
+static inline Status AnyArr_create( usize count, AnyArr **out, Heap *h, usize elem_size ) {
+ usize alloc_count = count;
+ DEBUG( alloc_count++ ); /* additional poisoned element in debug */
+
+ usize alloc_size = sizeof(AnyArr) + alloc_count*elem_size;
+
+ TRY( Heap_alloc( h, alloc_size, (void**)out ) );
+ (*out)->len = count;
+ DEBUG(
+ (*out)->heap = h;
+ _AnyArr_update_checksum( *out )
+ );
+ return S_SUCCESS;
+}
+
+static inline Status AnyArr_destroy( AnyArr** arr, Heap *h ) {
+ DEBUG(
+ assert( h == (*arr)->heap );
+ _AnyArr_validate( *arr );
+ )
+
+ TRY( Heap_free( h, (void**)arr ) );
+ return S_SUCCESS;
+}
+
+DEBUG(
+ static inline void _AnyArr_update_checksum( AnyArr *arr ) {
+ usize heapblock_size = Heap_get_asize( arr->heap, arr );
+ arr->checksum = heapblock_size ^ (usize)arr->heap ^ arr->len ^ ARRAY_XOR_KEY;
+ }
+
+ static inline void _AnyArr_validate( const AnyArr *arr ) {
+ usize heapblock_size = Heap_get_asize( arr->heap, arr );
+ usize checksum = heapblock_size ^ (usize)arr->heap ^ arr->len ^ ARRAY_XOR_KEY;
+ assert( arr->checksum == checksum );
+ }
+)
+
+static inline Status AnyArr_inflate( AnyArr **arr, usize additional_count, Heap *h, usize elem_size ) {
+ DEBUG(
+ assert( h == (*arr)->heap );
+ _AnyArr_validate( *arr );
+ )
+
+ if( additional_count == 0 ) {
+ return S_COMPLETION;
+ }
+
+ usize newsize = ((*arr)->len + additional_count)*elem_size + sizeof(AnyArr);
+ DEBUG( newsize += elem_size; )
+
+ AnyArr *newarr = 0;
+ TRY( Heap_alloc( h, newsize, (void**)&newarr ) );
+
+ usize total_size = (*arr)->len*elem_size + sizeof(AnyArr);
+ DEBUG( total_size += elem_size; )
+
+ mem_copy( (*arr), newarr, total_size );
+ newarr->len = (*arr)->len;
+
+ DEBUG( _AnyArr_update_checksum( *arr ) );
+
+ TRY( Heap_free( h, (void**)arr ) );
+ *arr = newarr;
+ return S_SUCCESS;
+}
+
+
+static inline Status AnyArr_extend( AnyArr **arr, usize additional_len, Heap *h, usize elem_size ) {
+ DEBUG(
+ assert( (*arr)->heap == h );
+ _AnyArr_validate( *arr );
+ usize old_len = (*arr)->len;
+ )
+
+ usize asize = Heap_get_asize( h, *arr );
+ usize maxcount = asize - sizeof(AnyArr);
+ DEBUG( maxcount--);
+ maxcount /= elem_size;
+ usize newlen = (*arr)->len + additional_len;
+
+ if( newlen >= maxcount ) {
+ TRY( AnyArr_inflate( arr, additional_len, h, elem_size ) );
+ }
+
+ (*arr)->len += additional_len;
+
+ DEBUG(
+
+ u8 *data = (u8*)((*arr) + 1);
+ u8 *uninint = data + newlen*elem_size;
+ mem_set( uninint, (newlen - old_len)*elem_size, MAGIC_UNINITIALIZED_MEM );
+ _AnyArr_update_checksum( *arr );
+ )
+
+ return S_SUCCESS;
+}
+
+static inline Status AnyArr_truncate( AnyArr *arr, usize cutlen, usize elem_size ) {
+ DEBUG(
+ _AnyArr_validate( arr );
+ usize old_len = arr->len;
+ )
+ RELEASE(
+ (void)elem_size;
+ )
+
+ if( cutlen > arr->len ) {
+ DEBUG( assert(0) );
+ return S_FAILURE | ERR_INVALID_ARGUMENT | ERRSRC_ARG_2;
+ }
+
+ arr->len -= cutlen;
+
+ DEBUG(
+ u8 *data = (u8*)(arr + 1);
+ u8 *raticide = data + arr->len*elem_size;
+ mem_set( raticide, (old_len - arr->len)*elem_size, MAGIC_POISONED_MEM );
+
+ _AnyArr_update_checksum( arr );
+ )
+
+
+ return S_SUCCESS;
+}
+
+static inline Status AnyArr_deflate( AnyArr **arr, Heap *h, usize elem_size ) { /* reallocate to just fit the currently contained elements - we assume it's on the same heap */
+ DEBUG(
+ assert( h == (*arr)->heap );
+ _AnyArr_validate( (*arr) );
+ )
+
+ usize total_size = (*arr)->len*elem_size + sizeof(AnyArr);
+ DEBUG( total_size += elem_size; )
+
+ AnyArr *out = 0;
+ TRY( Heap_alloc( h, total_size, (void**)&out ) );
+ mem_copy( *arr, out, total_size );
+ TRY( Heap_free( h, (void**)arr ) );
+
+ *arr = out;
+
+ DEBUG( _AnyArr_update_checksum( *arr ) );
+
+ return S_SUCCESS;
+}
+
+static inline Status AnyArr_copy( const AnyArr *arr, AnyArr **out, Heap *source_heap, Heap *target_heap, usize maxcount, usize len, usize elem_size ) {
+ DEBUG(
+ assert( source_heap == arr->heap );
+ _AnyArr_validate( arr );
+ )
+
+ usize alloc_size = (maxcount)? maxcount*elem_size + sizeof(AnyArr) : Heap_get_asize( source_heap, arr );
+ DEBUG( alloc_size += elem_size );
+
+ TRY( Heap_alloc( target_heap, alloc_size, (void**)out ) );
+ (*out)->len = len;
+
+ DEBUG( _AnyArr_update_checksum( *out ); )
+
+ mem_copy( arr + 1, *out + 1, len*elem_size );
+
+ DEBUG(
+ u8* data = (u8*)(arr + 1);
+ usize data_size = len*elem_size;
+ u8* poison_start = data + data_size;
+ usize poison_amount = alloc_size - data_size - sizeof(AnyArr);
+ DEBUG( poison_amount += elem_size );
+
+ mem_set( poison_start, poison_amount, MAGIC_POISONED_MEM );
+ )
+ return S_SUCCESS;
+}
+
+static inline Status AnyArr_move( AnyArr **arr, AnyArr **out, Heap *source_heap, Heap *target_heap, usize maxcount, usize len, usize elem_size ) {
+ TRY( AnyArr_copy( *arr, out, source_heap, target_heap, maxcount, len, elem_size ) );
+ TRY( Heap_free( source_heap, (void**)arr ) );
+ return S_SUCCESS;
+}
+
+static inline Status AnyArr_push( AnyArr **arr, void* el, Heap *h, usize elem_size ) {
+ DEBUG(
+ assert( h == (*arr)->heap );
+ _AnyArr_validate( *arr );
+ )
+
+ usize s = Heap_get_asize(h, *arr);
+ usize maxcount = (s - sizeof(AnyArr))/elem_size;
+
+ DEBUG(
+ maxcount--; /* Additional poisoned element */
+ );
+
+ if( (*arr)->len*elem_size >= maxcount ) {
+ AnyArr_inflate( arr, (*arr)->len, h, elem_size );
+ }
+
+ u8 *data = (u8*)(*arr + 1);
+ void *new_elem = data + (*arr)->len*elem_size;
+
+ mem_copy( el, new_elem, elem_size );
+ (*arr)->len++;
+
+ DEBUG(
+ _AnyArr_update_checksum( *arr );
+ mem_set( data + ((*arr)->len)*elem_size, elem_size, MAGIC_POISONED_MEM );
+ )
+
+ return S_SUCCESS;
+}
+
+static inline Status AnyArr_pop( AnyArr *arr, void* el_out, usize elem_size ) {
+ DEBUG(
+ _AnyArr_validate( arr );
+ )
+ if( arr->len == 0 ) {
+ DEBUG( assert(0) );
+ return ERR_OUT_OF_BOUND;
+ }
+
+ arr->len--;
+
+ u8 *data = (u8*)(arr + 1);
+ usize offset = elem_size*arr->len;
+
+ mem_copy( data + offset, el_out, elem_size );
+ DEBUG(
+ _AnyArr_update_checksum( arr );
+ mem_set( data + offset, elem_size, MAGIC_POISONED_MEM );
+ )
+ return S_SUCCESS;
+}
+
+static inline Status AnyArr_dup( const AnyArr *arr, AnyArr **out_arr, Heap *h, usize elem_size ) {
+ DEBUG( _AnyArr_validate( arr );)
+ usize total_size = arr->len*elem_size + sizeof(AnyArr);
+
+ TRY( Heap_alloc( h, total_size, (void**)out_arr ) );
+ mem_copy( arr, *out_arr, total_size );
+
+ return S_SUCCESS;
+}
+
+
+#define GEN_ARRAY_TYPE( T ) \
+ STRUCT( T##s, \
+ usize len; \
+ DEBUG( \
+ Heap *heap; \
+ usize checksum; \
+ ) \
+ T data[]; \
+ ); \
+ ASSERT( sizeof(T##s)%sizeof(usize) == 0 ); \
+ ASSERT( sizeof(T##s) == sizeof(AnyArr) ); \
+ \
+static inline Status T##s_create( Heap *h, usize count, T ## s **out ) { \
+ return AnyArr_create( count, (AnyArr**) out, h, sizeof(T) ); \
+} \
+ \
+static inline Status T##s_push( T##s **arr, T* el, Heap *h ) { \
+ return AnyArr_push( (AnyArr**)arr, el, h, sizeof(T) ); \
+} \
+ \
+static inline Status T##s_pop( T##s *arr, T* el ) { \
+ return AnyArr_pop( (AnyArr*)arr, el, sizeof(T) ); \
+} \
+ \
+static inline Status T##s_extend( T##s **arr, usize additional_len, Heap *h ) { \
+ return AnyArr_extend( (AnyArr**)arr, additional_len, h, sizeof(T) ); \
+} \
+ \
+static inline Status T##s_truncate( T##s *arr, usize cutlen ) { \
+ return AnyArr_truncate( (AnyArr*)arr, cutlen, sizeof(T) ); \
+} \
+ \
+static inline Status T##s_inflate( T##s **arr, usize additional_count, Heap *h ) { \
+ return AnyArr_inflate( (AnyArr**)arr, additional_count, h, sizeof(T) ); \
+} \
+ \
+static inline Status T##s_deflate( T##s **arr, Heap *h ) { \
+ return AnyArr_deflate( (AnyArr**)arr, h, sizeof(T) ); \
+} \
+ \
+static inline Status T##s_dup( const T##s *arr, T##s **out_arr, Heap *h ) { \
+ return AnyArr_dup( (AnyArr*)arr, (AnyArr**)out_arr, h, sizeof(T) ); \
+} \
+ \
+static inline Status T ## s_destroy( T##s **arr, Heap *h ) { \
+ return AnyArr_destroy( (AnyArr**)arr, h ); \
+}
+
+GEN_ARRAY_TYPE( u8 )
+GEN_ARRAY_TYPE( u16 )
+GEN_ARRAY_TYPE( u32 )
+GEN_ARRAY_TYPE( u64 )
+GEN_ARRAY_TYPE( usize )
+
+GEN_ARRAY_TYPE( s8 )
+GEN_ARRAY_TYPE( s16 )
+GEN_ARRAY_TYPE( s32 )
+GEN_ARRAY_TYPE( s64 )
+
+GEN_ARRAY_TYPE( f32 )
+GEN_ARRAY_TYPE( f64 )
+
+GEN_ARRAY_TYPE( u8p )
+GEN_ARRAY_TYPE( u16p )
+GEN_ARRAY_TYPE( u32p )
+GEN_ARRAY_TYPE( u64p )
+GEN_ARRAY_TYPE( usizep )
+
+GEN_ARRAY_TYPE( s8p )
+GEN_ARRAY_TYPE( s16p )
+GEN_ARRAY_TYPE( s32p )
+GEN_ARRAY_TYPE( s64p )
+
+GEN_ARRAY_TYPE( f32p )
+GEN_ARRAY_TYPE( f64p )
+
+#endif
memory/heap/heap_debug.h
@@ -77,7 +77,7 @@ static inline void _Heap_link_block( Heap *h, HeapEntry *e ) {
e->checksum = e->size ^ e->allowed_size ^ (usize)e->next ^ HEAP_XOR_KEY;
}
-static inline usize Heap_get_asize( Heap *h, void *ptr ) {
+static inline usize Heap_get_asize( Heap *h, const void *ptr ) { /* asize = allocation size */
HeapEntry *e = (HeapEntry*)( (u8*)ptr - sizeof(HeapEntry) );
HeapEntry *prev = 0;
_Heap_check_entry( e );
memory/heap/heap_release.h
@@ -13,7 +13,7 @@ STRUCT( Heap,
HeapEntry *freelist_data;
);
-static inline usize Heap_get_asize( Heap *h, void *ptr ) {
+static inline usize Heap_get_asize( Heap *h, const void *ptr ) {
(void)h;
return *((usize*)ptr - 1);
}
memory/heap.h
@@ -19,7 +19,7 @@ Status Heap_create( Heap *out, usize size ); /* size - size of underlying arena.
Status Heap_alloc( Heap *h, usize amount, void **out );
Status Heap_free( Heap *h, void **ptr ); /* u8** cause it zeroes the pointer on success automatically. */
-static inline usize Heap_get_asize( Heap *h, void *ptr );
+static inline usize Heap_get_asize( Heap *h, const void *ptr );
Status Heap_destroy( Heap *h );
memory/memory.h
@@ -18,8 +18,8 @@
#define GiB(n) ((u64)(n) << 30)
#define TiB(n) ((u64)(n) << 40)
-static inline void* mem_copy( void *source, void *destination, u64 len ) {
- u8 *src = source;
+static inline void* mem_copy( const void *source, void *destination, u64 len ) {
+ const u8 *src = source;
u8 *dst = destination;
u64 i = 0;
platform/platform.h
@@ -17,7 +17,10 @@
#define HEAP_HEADER_GUARD_NUMBER 0xc0dedeaddeadc0de
#define HEAP_OVERRUN_GUARD_NUMBER 0xeeeedeaddeadeeee
-#define HEAP_XOR_KEY 0x0e0e0e0e0e0e0e0e
+#define HEAP_XOR_KEY 0x0e1e2e3e4e5e6e7e
+
+#define ARRAY_XOR_KEY 0x0a1a2a3a4a5a6a7a
+
#define MAGIC_UNINITIALIZED_MEM 0xf0
#define MAGIC_POISONED_MEM 0xfc
#define MAGIC_FREED_MEM 0xfe
testing/tests/013_heap.c → testing/tests/014_heap.c
File renamed without changes
testing/tests/015_array_basic.c
@@ -0,0 +1,46 @@
+#include "datatypes/array.h"
+
+void entry(void) {
+ Heap h = {0};
+
+ assert(S_OK( Heap_create( &h, KiB(8) ) ));
+
+ usizes *a = 0;
+ assert(S_OK( usizes_create( &h, 16, &a ) ));
+
+ /* Resize allocation to minimum needed size aka 16 elements + metadata */
+ assert(S_OK( usizes_deflate( &a, &h ) ));
+
+ /* Not much to assert here, since the heap may allocate more than asked for */
+
+ /* Truncate by cutting 16 elements off the end - this preserves allocation size, only changes logical length */
+ usizes_truncate( a, 16 );
+ assert( a->len == 0 );
+
+ /* extend - make sure 24 more elemets will fit (0 + 24 = 24) */
+ assert(S_OK( usizes_extend( &a, 24, &h ) ));
+ assert( a->len == 24 );
+
+ for( usize i = 0; i < a->len; ++i ) {
+ a->data[i] = i;
+ }
+
+ for( usize i = 0; i < a->len; ++i ) {
+ assert( a->data[i] == i );
+ }
+
+ usize el = 12;
+ usizes_push( &a, &el, &h );
+
+ assert( a->len == 25 );
+
+ el = 0;
+ usizes_pop( a, &el );
+ assert( el == 12 );
+
+ assert(S_OK( usizes_destroy( &a, &h ) ));
+
+ assert(S_OK( Heap_destroy( &h ) ));
+
+ terminate(0);
+}