Commit e6bf191
Changed files (13)
testing/tests/010_mem_basic.c
@@ -0,0 +1,49 @@
+#define NOTLIBC_NOMAIN
+#include "notlibc.c"
+
+u8 validate_array( u8* arr, usize len ) {
+ for( usize i = 0; i < len; ++i ) {
+ if( arr[i] != i ) {
+ return 0;
+ }
+ }
+ return 1;
+}
+
+void PRESERVE_WITH_LTO entry(void) {
+ u8 arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
+
+ u8 buf[sizeof(arr)];
+
+ /* Copy should actually copy */
+ mem_copy( &arr[0], &buf[0], sizeof(arr) );
+ assert( validate_array( arr, arr[0] ) );
+
+ mem_set( buf, sizeof(arr), 0 );
+ for( usize i = 0; i < sizeof(arr); i++ ) {
+ assert( buf[i] == 0 );
+ }
+
+ /* Move should also move */
+ mem_move( &arr[0], &buf[0], sizeof(arr) );
+ assert( validate_array( arr, arr[0] ) );
+
+ /* Overlapping move tests */
+ mem_move( &buf[0], &buf[1], sizeof(buf) - 1 );
+
+ assert( buf[0] == 0 );
+ for( usize i = 0; i < sizeof(buf)-1; ++i ) {
+ assert( buf[i+1] == i );
+ }
+
+ mem_copy( &arr[0], &buf[0], sizeof(arr) );
+
+ mem_move( &buf[1], &buf[0], sizeof(buf) - 1 );
+
+ assert( buf[sizeof(buf) - 1] == sizeof(buf) - 1 );
+ for( usize i = 0; i < sizeof(buf)-1; ++i ) {
+ assert( buf[i] == i + 1 );
+ }
+
+ terminate(0);
+}
testing/tests/012_mem_basic.c → testing/tests/011_mem_platform.c
File renamed without changes
testing/tests/020_binary_search.c
@@ -0,0 +1,88 @@
+#define NOTLIBC_NOMAIN
+#include "notlibc.c"
+
+s8 _u32_cmp( const void *n1, const void *n2 ) {
+ const u32 *a = n1;
+ const u32 *b = n2;
+ if( *a == *b ) return 0;
+ if( *a > *b ) return 1; else return -1;
+}
+
+void PRESERVE_WITH_LTO entry(void) {
+
+ u32 arr0[] = { 1, 4, 7, 12 };
+
+ Status s = S_SUCCESS;
+
+ u32 el = 1;
+ usize i = algo_binary_search( &s, &el, sizeof(arr0[0]), &arr0[0], 4, _u32_cmp );
+ assert( i == 0 );
+ assert( S_SUCCESSFUL(s) );
+
+ el = 4;
+ i = algo_binary_search( &s, &el, sizeof(arr0[0]), &arr0[0], 4, _u32_cmp );
+ assert( i == 1 );
+ assert( S_SUCCESSFUL(s) );
+
+ el = 7;
+ i = algo_binary_search( &s, &el, sizeof(arr0[0]), &arr0[0], 4, _u32_cmp );
+ assert( i == 2 );
+ assert( S_SUCCESSFUL(s) );
+
+ el = 12;
+ i = algo_binary_search( &s, &el, sizeof(arr0[0]), &arr0[0], 4, _u32_cmp );
+ assert( i == 3 );
+ assert( S_SUCCESSFUL(s) );
+
+ el = 3;
+ i = algo_binary_search( &s, &el, sizeof(arr0[0]), &arr0[0], 4, _u32_cmp );
+ assert( i == 1 );
+ assert( S_COMPLETED(s) );
+ s = S_SUCCESS;
+
+ el = 6;
+ i = algo_binary_search( &s, &el, sizeof(arr0[0]), &arr0[0], 4, _u32_cmp );
+ assert( i == 2 );
+ assert( S_COMPLETED(s) );
+ s = S_SUCCESS;
+
+ el = 0;
+ i = algo_binary_search( &s, &el, sizeof(arr0[0]), arr0, 4, _u32_cmp );
+ assert( i == 0 );
+ assert( S_COMPLETED(s) );
+ s = S_SUCCESS;
+
+ el = 13;
+ i = algo_binary_search( &s, &el, sizeof(arr0[0]), arr0, 4, _u32_cmp );
+ assert( i == 4 );
+ assert( S_COMPLETED(s) );
+ s = S_SUCCESS;
+
+ el = 5;
+ i = algo_binary_search( &s, &el, sizeof(arr0[0]), arr0, 0, _u32_cmp );
+ assert( i == 0 );
+ assert( S_COMPLETED(s) );
+ s = S_SUCCESS;
+
+ u32 sarr[] = { 42 };
+
+ el = 42;
+ i = algo_binary_search( &s, &el, sizeof(sarr[0]), sarr, 1, _u32_cmp );
+ assert( i == 0 );
+ assert( S_SUCCESSFUL(s) );
+ s = S_SUCCESS;
+
+ el = 45;
+ i = algo_binary_search( &s, &el, sizeof(sarr[0]), sarr, 1, _u32_cmp );
+ assert( i == 1 );
+ assert( S_COMPLETED(s) );
+ s = S_SUCCESS;
+
+ el = 32;
+ i = algo_binary_search( &s, &el, sizeof(sarr[0]), sarr, 1, _u32_cmp );
+ assert( i == 0 );
+ assert( S_COMPLETED(s) );
+ s = S_SUCCESS;
+
+ terminate(0);
+}
testing/tests/021_sorting.c
@@ -0,0 +1,43 @@
+#define NOTLIBC_NOMAIN
+#include "notlibc.c"
+
+s8 _usize_cmp( const void *n1, const void *n2 ) {
+ const usize *a = n1;
+ const usize *b = n2;
+ if( *a == *b ) return 0;
+ if( *a > *b ) return 1; else return -1;
+}
+
+
+SortFunc *sortfuncs[] = { algo_insertionsort, algo_sort_generic };
+FallbackingSortFunc *fallbacking_sortfuncs[] = { algo_quicksort };
+
+void PRESERVE_WITH_LTO entry(void) {
+ usize arr[] = { 41, 4, 2, 76, 30, 75, 49, 85, 67, 21, 11, 100, 29, 31, 72, 65, 35, 37, 1, 7, 87, 10, 8, 68, 5, 58, 61, 24, 23, 62, 52, 19 }; /* some random numbers from random.org */
+
+ usize data[sizeof(arr)/sizeof(arr[0])] = {0};
+
+ for( usize i = 0; i < sizeof(sortfuncs)/sizeof(sortfuncs[0]); ++i ) {
+ Status s = S_SUCCESS;
+ mem_copy( arr, data, sizeof(arr) );
+ sortfuncs[i]( &s, data, sizeof(arr)/sizeof(arr[0]), sizeof(arr[0]), _usize_cmp );
+ assert( S_OK( s ) );
+
+ for( usize j = 1; j < sizeof(arr)/sizeof(arr[0]); ++j ) {
+ assert( data[j-1] <= data[j] );
+ }
+ }
+
+ for( usize i = 0; i < sizeof(fallbacking_sortfuncs)/sizeof(fallbacking_sortfuncs[0]); ++i ) {
+ Status s = S_SUCCESS;
+ mem_copy( arr, data, sizeof(arr) );
+ fallbacking_sortfuncs[i]( &s, data, sizeof(arr)/sizeof(arr[0]), sizeof(arr[0]), _usize_cmp, 4, algo_insertionsort );
+ assert( S_OK( s ) );
+
+ for( usize j = 1; j < sizeof(arr)/sizeof(arr[0]); ++j ) {
+ assert( data[j-1] <= data[j] );
+ }
+ }
+
+ terminate(0);
+}
testing/tests/013_arena_basic.c → testing/tests/113_arena_basic.c
File renamed without changes
testing/tests/014_heap.c → testing/tests/114_heap.c
File renamed without changes
testing/tests/015_array_basic.c → testing/tests/115_array_basic.c
File renamed without changes
testing/tests/016_strings_and_slices.c → testing/tests/116_strings_and_slices.c
File renamed without changes
testing/tests/117_sorted_arrays.c
@@ -0,0 +1,72 @@
+#define NOTLIBC_NOMAIN
+#include "notlibc.c"
+
+s8 _usize_cmp( const usize *a, const usize *b ) {
+ if( *a == *b ) return 0;
+ if( *a > *b ) return 1; else return -1;
+}
+
+void PRESERVE_WITH_LTO entry(void) {
+
+ Status s = S_SUCCESS;
+
+ Heap h = Heap_create( &s, KiB(4) );
+ assert( S_OK(s) );
+
+ usizes *a = usizes_create( &s, &h, 8 );
+ assert( S_OK(s) );
+
+ usize value = 0;
+ a = usizes_push( &s, a, &value, &h );
+ assert( S_OK(s) );
+
+ value = 17;
+ a = usizes_push( &s, a, &value, &h );
+ assert( S_OK(s) );
+
+ value = 11;
+ a = usizes_push( &s, a, &value, &h );
+ assert( S_OK(s) );
+
+ value = 164;
+ a = usizes_push( &s, a, &value, &h );
+ assert( S_OK(s) );
+
+ value = 1248;
+ a = usizes_push( &s, a, &value, &h );
+ assert( S_OK(s) );
+
+ value = 3;
+ a = usizes_push( &s, a, &value, &h );
+ assert( S_OK(s) );
+
+ usizes_sort( &s, a, _usize_cmp );
+ assert( S_OK(s) );
+
+ for( u64 i = 1; i < a->len; ++i ) {
+ assert( a->data[i - 1] <= a->data[i] );
+ }
+
+
+ value = 11;
+ a = usizes_insert_sorted( &s, a, &value, _usize_cmp, &h );
+ assert( S_OK(s) );
+
+ value = 111;
+ a = usizes_insert_sorted( &s, a, &value, _usize_cmp, &h );
+ assert( S_OK(s) );
+
+ value = 111;
+ a = usizes_insert_sorted( &s, a, &value, _usize_cmp, &h );
+ assert( S_OK(s) );
+
+ value = 111111;
+ a = usizes_insert_sorted( &s, a, &value, _usize_cmp, &h );
+ assert( S_OK(s) );
+
+ for( u64 i = 1; i < a->len; ++i ) {
+ assert( a->data[i - 1] <= a->data[i] );
+ }
+
+ terminate(0);
+}
testing/tests/020_file_basic.c → testing/tests/120_file_basic.c
File renamed without changes
testing/tests/021_fileview.c → testing/tests/121_fileview.c
File renamed without changes
notlibc.c
@@ -30,6 +30,168 @@ void *memcpy( void *dest, const void *src, unsigned long n ) {
return dest;
}
+/*================================ Algorithms ================================*/
+
+usize algo_binary_search( Status *s, const void *restrict el, usize el_size, const void *restrict data, usize count, CmpFunc *cmp ) {
+ usize ret = 0;
+ END_IF_NOK( *s );
+
+ if( !data ) {
+ ERRORING_FAIL( S_FAILURE | ERR_INVALID_ARGUMENT | ERRSRC_ARG_2 );
+ goto end;
+ }
+
+ if( !count ) {
+ *s = S_COMPLETION;
+ return 0;
+ }
+
+ if( !el ) {
+ ERRORING_FAIL( S_FAILURE | ERR_INVALID_ARGUMENT | ERRSRC_ARG_4 );
+ goto end;
+ }
+
+ if( !el_size ) {
+ ERRORING_FAIL( S_FAILURE | ERR_INVALID_ARGUMENT | ERRSRC_ARG_5 );
+ goto end;
+ }
+
+ if( !cmp ) {
+ ERRORING_FAIL( S_FAILURE | ERR_INVALID_ARGUMENT | ERRSRC_ARG_6 );
+ goto end;
+ }
+
+ usize start = 0;
+ usize end = count;
+ usize middle;
+
+ while( start < end ) {
+ middle = start + (end - start)/2;
+ void *middle_el = (u8*)data + middle*el_size;
+
+ s8 eq = cmp( middle_el, el );
+
+ if( eq < 0 ) {
+ start = middle + 1;
+ } else if( eq > 0 ) {
+ end = middle;
+ } else {
+ *s = S_SUCCESS;
+ ret = middle;
+ goto end;
+ }
+ }
+ *s = S_COMPLETION;
+ ret = start;
+
+ end:
+ return ret;
+}
+
+void algo_sort_generic(Status *s, void *const data, usize count, usize el_size, CmpFunc *cmp) {
+ algo_quicksort( s, data, count, el_size, cmp, 16, algo_insertionsort );
+}
+
+void algo_insertionsort(Status *s, void *const data, usize count, usize el_size, CmpFunc *cmp) {
+ END_IF_NOK( *s );
+
+ if( count <= 1 ) {
+ return;
+ }
+
+ if( !data ) {
+ ERRORING_FAIL( S_FAILURE | ERR_INVALID_ARGUMENT | ERRSRC_ARG_2 );
+ }
+
+ if( !el_size ) {
+ ERRORING_FAIL( S_FAILURE | ERR_INVALID_ARGUMENT | ERRSRC_ARG_4 );
+ }
+
+ if( !cmp ) {
+ ERRORING_FAIL( S_FAILURE | ERR_INVALID_ARGUMENT | ERRSRC_ARG_5 );
+ }
+
+ for( usize i = 1; i < count; ++i ) {
+ for( usize j = i; j > 0 && cmp( (u8*)data + (j-1)*el_size, (u8*)data + j*el_size ) > 0; j-- ) {
+ swap( (u8*)data + j*el_size, (u8*)data + (j-1)*el_size, el_size );
+ }
+ }
+
+ end:
+ return;
+}
+
+usize _quicksort_partition( Status *s, void *const data, usize count, usize el_size, CmpFunc *cmp ) {
+ if( count < 1 ) {
+ ERRORING_FAIL( S_FAILURE | ERR_INVALID_ARGUMENT | ERRSRC_ARG_3 );
+ }
+
+ usize pivot_index = count/2;
+ usize hi = count - 1;
+
+ swap( (u8*)data + pivot_index*el_size, (u8*)data + hi*el_size, el_size);
+
+ /* This two-way partitioning isn't the best, because it can yield unbalanced partitions if there are many duplicates in the input */
+ usize i = 0;
+ for( usize j = 0; j < hi; ++j ) {
+ if( cmp( (u8*)data + j*el_size, (u8*)data + hi*el_size ) < 0 ) {
+ swap( (u8*)data + i*el_size, (u8*)data + j*el_size, el_size);
+ i++;
+ }
+ }
+
+ swap( (u8*)data + hi*el_size, (u8*)data + i*el_size, el_size);
+ return i;
+}
+
+void algo_quicksort(Status *s, void *const data, usize count, usize el_size, CmpFunc *cmp, usize fallback_at_count, SortFunc* fallback_algo) {
+ END_IF_NOK( *s );
+
+ if( count == 0 ) {
+ return;
+ }
+
+ if( !data ) {
+ ERRORING_FAIL( S_FAILURE | ERR_INVALID_ARGUMENT | ERRSRC_ARG_2 );
+ }
+
+ if( !el_size ) {
+ ERRORING_FAIL( S_FAILURE | ERR_INVALID_ARGUMENT | ERRSRC_ARG_4 );
+ }
+
+ if( !cmp ) {
+ ERRORING_FAIL( S_FAILURE | ERR_INVALID_ARGUMENT | ERRSRC_ARG_5 );
+ }
+
+ if( count <= fallback_at_count ) {
+ fallback_algo( s, data, count, el_size, cmp );
+ return;
+ }
+
+ usize pivot = _quicksort_partition( s, data, count, el_size, cmp );
+ END_IF_NOK( *s );
+
+ usize left_count = pivot;
+ usize right_count = count - pivot - 1;
+
+ void* right_data = (u8*)data + (pivot + 1)*el_size;
+
+ if (left_count < right_count) {
+ algo_quicksort( s, data, left_count, el_size, cmp, fallback_at_count, fallback_algo );
+ END_IF_NOK(*s);
+ algo_quicksort( s, right_data, right_count, el_size, cmp, fallback_at_count, fallback_algo );
+ } else {
+ algo_quicksort( s, right_data, right_count, el_size, cmp, fallback_at_count, fallback_algo );
+ END_IF_NOK(*s);
+ algo_quicksort( s, data, left_count, el_size, cmp, fallback_at_count, fallback_algo );
+ }
+
+ END_IF_NOK( *s );
+
+end:
+ return;
+}
+
/*================================ Arena =====================================*/
@@ -401,6 +563,8 @@ AnyArr* AnyArr_create( Status *s, usize count, Heap *h, usize elem_size ) {
ret->len = 0;
DEBUG(
ret->heap = h;
+ ret->sorted = 0;
+ ret->sortfunc = 0;
_AnyArr_update_checksum( ret )
);
@@ -429,7 +593,6 @@ void AnyArr_destroy( Status *s, AnyArr** arr, Heap *h ) {
usize checksum = heapblock_size ^ (usize)arr->heap ^ arr->len ^ ARRAY_XOR_KEY;
assert( arr->checksum == checksum );
}
-
#endif
AnyArr* AnyArr_inflate( Status *s, AnyArr *arr, usize additional_count, Heap *h, usize elem_size ) {
@@ -451,7 +614,6 @@ AnyArr* AnyArr_inflate( Status *s, AnyArr *arr, usize additional_count, Heap *h,
DEBUG( newsize += elem_size; )
ret = Heap_alloc( s, h, newsize );
-
END_IF_NOK( *s );
usize total_size = arr->len*elem_size + sizeof(AnyArr);
@@ -459,10 +621,14 @@ AnyArr* AnyArr_inflate( Status *s, AnyArr *arr, usize additional_count, Heap *h,
mem_copy( arr, ret, total_size );
- DEBUG( _AnyArr_update_checksum( ret ) );
+ DEBUG(
+ _AnyArr_update_checksum( ret );
+ mem_set( (u8*)(ret+1) + (ret->len)*elem_size, elem_size, MAGIC_POISONED_MEM );
+ );
/* Don't want to free the original if we couldn't grow it, hence it's
- * jumped over if the heap alloc fails - otherwise we risk double-free. */
+ * jumped over if the heap alloc fails - otherwise we risk double-free
+ * when it finally propagates down the chain to the destructor. */
Heap_free( s, h, arr );
end:
@@ -523,7 +689,7 @@ end:
return ret;
}
-AnyArr* AnyArr_push( Status *s, AnyArr *arr, void* el, Heap *h, usize elem_size ) {
+static inline AnyArr* _AnyArr_ensure_space_for_one_more_element( Status *s, AnyArr *arr, Heap *h, usize elem_size ) {
AnyArr *ret = arr;
END_IF_NOK( *s );
@@ -539,13 +705,20 @@ AnyArr* AnyArr_push( Status *s, AnyArr *arr, void* el, Heap *h, usize elem_size
maxcount--; /* Additional poisoned element */
);
-
if( arr->len == maxcount ) {
ret = AnyArr_inflate( s, arr, arr->len, h, elem_size );
}
END_IF_NOK( *s );
+end:
+ return ret;
+}
+
+AnyArr* AnyArr_push( Status *s, AnyArr *arr, void* el, Heap *h, usize elem_size ) {
+ AnyArr *ret = _AnyArr_ensure_space_for_one_more_element( s, arr, h, elem_size);
+ END_IF_NOK( *s );
+
u8 *data = (u8*)(ret + 1);
void *new_elem = data + ret->len*elem_size;
@@ -554,14 +727,17 @@ AnyArr* AnyArr_push( Status *s, AnyArr *arr, void* el, Heap *h, usize elem_size
DEBUG(
_AnyArr_update_checksum( ret );
- mem_set( data + (ret->len)*elem_size, elem_size, MAGIC_POISONED_MEM );
- )
+ ret->sorted = 0;
+ ret->sortfunc = 0;
+ );
+
+ DEBUG( arr->sorted = 0; )
end:
return ret;
}
-void AnyArr_pop( Status *s, AnyArr *arr, void* el_out, usize elem_size ) {
+void AnyArr_pop( Status *s, AnyArr *restrict arr, void *restrict el_out, usize elem_size ) {
END_IF_NOK( *s );
DEBUG(
@@ -575,19 +751,62 @@ void AnyArr_pop( Status *s, AnyArr *arr, void* el_out, usize elem_size ) {
arr->len--;
+ DEBUG(
+ _AnyArr_update_checksum( arr );
+ )
+
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 );
- )
+ )
end:
return;
}
+AnyArr* AnyArr_insert_at( Status *s, AnyArr *arr, usize index, const void *element, Heap *h, usize elem_size) {
+ AnyArr *ret = arr;
+ END_IF_NOK( *s );
+
+ if( arr->len <= index ) {
+ *s = S_FAILURE | ERR_OUT_OF_BOUND | ERRSRC_ARG_3;
+ goto end;
+ }
+ ret = _AnyArr_ensure_space_for_one_more_element( s, arr, h, elem_size );
+
+ u8 *data = (u8*)(arr + 1);
+ usize insertion_offset = elem_size*arr->len;
+ usize move_amount = (arr->len - index)*elem_size;
+
+ mem_move( data + insertion_offset , data + insertion_offset + elem_size, move_amount );
+ mem_copy( element, data + insertion_offset, elem_size );
+
+ DEBUG( arr->sorted = 0; )
+
+end:
+ return ret;
+}
+
+AnyArr* AnyArr_insert_sorted( Status *s, AnyArr *arr, const void *elem, CmpFunc *cmp, Heap *h, usize elem_size ) {
+ AnyArr *ret = 0;
+
+ END_IF_NOK( *s );
+ DEBUG( assert( arr->sorted ) );
+ DEBUG( assert( arr->sortfunc == cmp ) );
+
+ usize index = algo_binary_search( s, arr + 1, arr->len, elem, elem_size, cmp );
+ ret = AnyArr_insert_at( s, arr, index, elem, h, elem_size );
+
+ DEBUG( ret->sorted = 1; )
+
+end:
+ return ret;
+}
+
AnyArr* AnyArr_dup( Status *s, const AnyArr *arr, Heap *h, usize elem_size ) {
AnyArr *ret = 0;
END_IF_NOK( *s );
@@ -604,6 +823,20 @@ end:
return ret;
}
+
+void AnyArr_sort( Status *s, AnyArr *arr, CmpFunc *cmp, usize elem_size ) {
+ algo_sort_generic(s, arr + 1, arr->len, elem_size, cmp );
+ END_IF_NOK( *s );
+
+ DEBUG(
+ arr->sorted = 1;
+ arr->sortfunc = cmp;
+ )
+
+end:
+ return;
+}
+
/*================================= String ===================================*/
u8 Str_equals( const Str *s1, const Str *s2 ) {
notlibc.h
@@ -290,6 +290,7 @@ void *memset( void* ptr, int value, unsigned long count );
void *memcpy( void *dest, const void *src, unsigned long n );
+
/*========================== Derived Datatypes ===============================*/
@@ -481,6 +482,23 @@ GEN_VALUE_BY_STATUS( s64 )
GEN_VALUE_BY_STATUS( ssize )
+/* Generic function types */
+
+typedef s8 (CmpFunc)(const void*, const void*);
+GEN_POINTER_TYPE( CmpFunc );
+
+typedef usize (SearchFunc)( Status *s, const void *restrict el, usize el_size, const void *restrict data, usize count, CmpFunc *cmp );
+/* Returns the index and S_SUCCESS if the element was found.
+ * Returns the index after which a given element would belong and S_COMPLETION if the element was not found */
+GEN_POINTER_TYPE( SearchFunc );
+
+typedef void (SortFunc)(Status *s, void *const data, usize count, usize el_size, CmpFunc *cmp);
+GEN_POINTER_TYPE( SortFunc );
+
+typedef void (FallbackingSortFunc)(Status *s, void *const data, usize count, usize el_size, CmpFunc *cmp, usize fallback_at_count, SortFunc* fallback_algo);
+GEN_POINTER_TYPE( FallbackingSortFunc );
+
+
/******************************************************************************/
/* MATH STUFF */
/******************************************************************************/
@@ -898,6 +916,9 @@ STRUCT( AnyArr,
DEBUG(
Heap *heap;
usize checksum;
+ u32
+ sorted : 1;
+ CmpFunc *sortfunc;
)
);
@@ -910,11 +931,16 @@ AnyArr* AnyArr_deflate( Status *s, AnyArr *arr, Heap *h, usize elem_size ); /* r
void AnyArr_truncate( Status *s, AnyArr *arr, usize cutlen, usize elem_size );
-AnyArr* AnyArr_push( Status *s, AnyArr *arr, void* el, Heap *h, usize elem_size );
-void AnyArr_pop( Status *s, AnyArr *arr, void* el_out, usize elem_size );
+AnyArr* AnyArr_push( Status *s, AnyArr *restrict arr, void *restrict el, Heap *h, usize elem_size );
+void AnyArr_pop( Status *s, AnyArr *restrict arr, void *restrict el_out, usize elem_size );
+
+AnyArr* AnyArr_insert_at( Status *s, AnyArr *arr, usize index, const void *element, Heap *h, usize elem_size);
AnyArr* AnyArr_dup( Status *s, const AnyArr *arr, Heap *h, usize elem_size );
+void AnyArr_sort( Status *s, AnyArr *arr, CmpFunc *cmp, usize elem_size );
+AnyArr* AnyArr_insert_sorted( Status *s, AnyArr *arr, const void *elem, CmpFunc *cmp, Heap *h, usize elem_size );
+
DEBUG(
void _AnyArr_update_checksum( AnyArr *arr );
void _AnyArr_validate( const AnyArr *arr );
@@ -926,6 +952,9 @@ DEBUG(
DEBUG( \
Heap *heap; \
usize checksum; \
+ u32 \
+ sorted : 1; \
+ CmpFunc *sortfunc; \
) \
T data[]; \
); \
@@ -936,6 +965,10 @@ static inline T##s* T##s_create( Status *s, Heap *h, usize count ) {
return (T##s*)AnyArr_create( s, count, h, sizeof(T) ); \
} \
\
+static inline void T##s_destroy( Status *s, T##s **arr, Heap *h ) { \
+ AnyArr_destroy( s, (AnyArr**)arr, h ); \
+} \
+ \
static inline T##s* T##s_push( Status *s, T##s *arr, T* el, Heap *h ) { \
return (T##s*)AnyArr_push( s, (AnyArr*)arr, el, h, sizeof(T) ); \
} \
@@ -956,13 +989,22 @@ static inline T##s* T##s_deflate( Status *s, T##s *arr, Heap *h ) {
return (T##s*)AnyArr_deflate( s, (AnyArr*)arr, h, sizeof(T) ); \
} \
\
-static inline T##s* T##s_dup( Status *s, const T##s *arr, Heap *h ) {\
- return (T##s*)AnyArr_dup( s, (AnyArr*)arr, h, sizeof(T) ); \
+static inline T##s* T##s_dup( Status *s, const T##s *arr, Heap *h ) { \
+ return (T##s*)AnyArr_dup( s, (AnyArr*)arr, h, sizeof(T) ); \
} \
- \
-static inline void T##s_destroy( Status *s, T##s **arr, Heap *h ) { \
- AnyArr_destroy( s, (AnyArr**)arr, h ); \
-}
+ \
+static inline T##s* T##s_insert_at( Status *s, T##s *arr, usize index, T *element, Heap *h ) { \
+ return (T##s*)AnyArr_insert_at( s, (AnyArr*)arr, index, element, h, sizeof(T) ); \
+} \
+ \
+static inline void T##s_sort( Status *s, T##s *arr, s8 (*cmp)(const T* el1, const T* el2) ) { \
+ AnyArr_sort( s, (AnyArr*)arr, (CmpFunc *)cmp, sizeof(T) ); \
+} \
+ \
+static inline T##s* T##s_insert_sorted( Status *s, T##s *arr, const T *elem, s8 (*cmp)(const T* el1, const T* el2), Heap *h ) { \
+ return (T##s*)AnyArr_insert_sorted( s, (AnyArr*)arr, elem, (CmpFunc *)cmp, h, sizeof(T) ); \
+} \
+ \
GEN_ARRAY_TYPE( u8 )
GEN_ARRAY_TYPE( u16 )
@@ -1240,7 +1282,7 @@ static inline void assert( usize condition ) {
#define GiB(n) ((u64)(n) << 30)
#define TiB(n) ((u64)(n) << 40)
-static inline void* mem_copy( const void *source, void *destination, u64 len ) {
+static inline void mem_copy( const void *restrict source, void *restrict destination, u64 len ) {
const u8 *src = source;
u8 *dst = destination;
u64 i = 0;
@@ -1248,8 +1290,22 @@ static inline void* mem_copy( const void *source, void *destination, u64 len ) {
for( ; i < len; ++i ) {
dst[i] = src[i];
}
+}
- return &dst[i];
+static inline void mem_move( const void *source, void *destination, u64 len ) {
+ const u8 *src = source;
+ u8 *dst = destination;
+ u64 i;
+
+ if( src > dst ) {
+ for( i = 0; i < len; ++i ) {
+ dst[i] = src[i];
+ }
+ } else {
+ for( i = len; i >= 1; --i ) {
+ dst[i - 1] = src[i - 1];
+ }
+ }
}
static inline void* mem_set( void *start, u64 len, u8 value ) {
@@ -1274,6 +1330,61 @@ void mem_occupy( Status *s, Page *start, u32 page_count );
/* Allow removal of physical backing */
void mem_vacate( Status *s, Page *start, u32 page_count );
+/* Bits and pieces */
+static inline void swap( void *restrict el1, void *restrict el2, usize el_size );
+
+#define SWAP_STACK_BUFFER_SIZE 128
+static inline void swap( void *restrict el1, void *restrict el2, usize el_size ) {
+ register u64 tmp;
+ switch( el_size ) {
+ case sizeof(u8):
+ tmp = *(u8*)el1;
+ *(u8*)el1 = *(u8*)el2;
+ *(u8*)el2 = (u8)tmp;
+ break;
+ case sizeof(u16):
+ tmp = *(u16*)el1;
+ *(u16*)el1 = *(u16*)el2;
+ *(u16*)el2 = (u16)tmp;
+ break;
+ case sizeof(u32):
+ tmp = *(u32*)el1;
+ *(u32*)el1 = *(u32*)el2;
+ *(u32*)el2 = (u32)tmp;
+ break;
+ case sizeof(u64):
+ tmp = *(u64*)el1;
+ *(u64*)el1 = *(u64*)el2;
+ *(u64*)el2 = (u64)tmp;
+ break;
+
+ default: {
+ u8 local[SWAP_STACK_BUFFER_SIZE];
+
+ while( el_size >= SWAP_STACK_BUFFER_SIZE ) {
+ u64 offset = el_size - SWAP_STACK_BUFFER_SIZE;
+ mem_copy( (u8*)el1 + offset, local, SWAP_STACK_BUFFER_SIZE );
+ mem_copy( (u8*)el2 + offset, (u8*)el1 + offset, SWAP_STACK_BUFFER_SIZE );
+ mem_copy( local, (u8*)el2 + offset, SWAP_STACK_BUFFER_SIZE );
+ el_size -= SWAP_STACK_BUFFER_SIZE;
+ }
+
+ if( el_size ) {
+ mem_copy( (u8*)el1, local, el_size );
+ mem_copy( (u8*)el2, (u8*)el1, el_size );
+ mem_copy( local, (u8*)el2, el_size );
+ }
+ }
+ }
+}
+
+/* Algorithms */
+
+SearchFunc algo_binary_search;
+SortFunc algo_sort_generic;
+SortFunc algo_insertionsort;
+FallbackingSortFunc algo_quicksort;
+
/******************************************************************************/
/* COMMON PLATFORM IMPLEMENTATION */