// paged_array.c // PUBLIC DOMAIN // http:///www.purposeful.co.uk/software/yabaplib /* I, Tom Vajzovic, am the author of this software and its documentation. I permanently abandon all intellectual property rights in them, including copyright, trademarks, design rights, database right, patents, and the right to be identified as the author. I am fairly certain that the software does what the documentation says it does, but I do not guarantee that it does, or that it does what you think it should. I do not guarantee that it will not have undesirable side effects. You are free to use, modify and distribute this software as you please, but you do so at your own risk. If you do not pass on this warning then you may be responsible for any problems encountered by those who obtain the software through you. */ #include #include #include #include "paged_array.h" /***************************************************************************************************************************/ /* PAGE_ARRAY_ELEMS_PAGE */ /* */ /* Number of page-pointers per page in the paged-array of pages. */ /* This determines the number of levels of indirection required to index all paged arrays. */ /* Tune it carefully: */ /* - Bigger means less indirections, so maybe faster. */ /* - Smaller means less wasted space, and perhaps less cache misses too, so maybe faster. */ /***************************************************************************************************************************/ #define PAGE_ARRAY_ELEMS_PAGE 128 /***************************************************************************************************************************/ /* LOCAL FUNCTION PROTOTYPES */ /***************************************************************************************************************************/ static void *allocate( size_t size ); static void indirect_free( void *pp, void *unrequired ); /***************************************************************************************************************************/ /* paged_array_init_empty */ /***************************************************************************************************************************/ void paged_array_init_empty(paged_array_t *pa, size_t elem_size, size_t elems_page) { pa-> len= 0; pa-> elem_size= elem_size; pa-> elems_page= elems_page; } /***************************************************************************************************************************/ /* paged_array_init */ /***************************************************************************************************************************/ void paged_array_init(paged_array_t *pa, size_t elem_size, size_t elems_page, const void *input_array, size_t len) { paged_array_init_empty(pa, elem_size, elems_page); paged_array_append(pa, input_array, len); } /***************************************************************************************************************************/ /* paged_array_destroy */ /***************************************************************************************************************************/ void paged_array_destroy(paged_array_t *pa) { paged_array_set_length(pa, 0); } /***************************************************************************************************************************/ /* paged_array_new_empty */ /***************************************************************************************************************************/ paged_array_t *paged_array_new_empty(size_t elem_size, size_t elems_page) { paged_array_t *pa= allocate( sizeof *pa ); paged_array_init_empty( pa, elem_size, elems_page ); return pa; } /***************************************************************************************************************************/ /* paged_array_new */ /***************************************************************************************************************************/ paged_array_t *paged_array_new(size_t elem_size, size_t elems_page, const void *input_array, size_t len) { paged_array_t *pa= paged_array_new_empty(elem_size, elems_page); paged_array_append(pa, input_array, len); return pa; } /***************************************************************************************************************************/ /* paged_array_delete */ /***************************************************************************************************************************/ void paged_array_delete(paged_array_t *pa) { paged_array_destroy(pa); free(pa); } /***************************************************************************************************************************/ /* paged_array_length */ /***************************************************************************************************************************/ size_t paged_array_length(const paged_array_t *pa) { return pa-> len; } /***************************************************************************************************************************/ /* paged_array_index */ /***************************************************************************************************************************/ void *paged_array_index(const paged_array_t *pa, size_t index) { if( pa-> len <= index ) { /* array doesn't have that many elements */ return NULL; } if( pa-> len <= pa-> elems_page ) { /* array has one page */ return pa-> ptr. page + ( pa-> elem_size * index ); } /* array has several pages */ return (*(char**) paged_array_index( pa-> ptr. pages, index / pa-> elems_page )) + ( pa-> elem_size * ( index % pa-> elems_page )); } /***************************************************************************************************************************/ /* paged_array_extract */ /***************************************************************************************************************************/ void paged_array_extract(const paged_array_t *pa, void *output_array, size_t first, size_t num) { if( first >= pa-> len ) { /* requested start is after the end so cannot do anything */ return; } if(( first + num )> pa-> len) { /* requested length is less than we have after requested start */ num= pa-> len - first; } if((( first % pa-> elems_page) + num) <= pa-> elems_page ) { /* requested range is all within one page */ memcpy( output_array, paged_array_index( pa, first ), pa-> elem_size * num); } else { size_t page_size= pa-> elem_size * pa-> elems_page; char *out_ptr= output_array; /* number of elements to extract from the page starting at first */ size_t remainder= pa-> elems_page - (first % pa-> elems_page); size_t remainder_size = pa-> elem_size * remainder; /* copy from the page starting at first */ memcpy( out_ptr, paged_array_index( pa, first ), remainder_size ); first+= remainder; num-= remainder; out_ptr+= remainder_size; while( num > pa-> elems_page ) { /* copy whole pages */ memcpy( out_ptr, paged_array_index( pa, first ), page_size ); first+= pa-> elems_page; num-= pa-> elems_page; out_ptr+= page_size; } /* copy the last partial page */ memcpy( out_ptr, paged_array_index( pa, first ), pa-> elem_size * num ); } } /***************************************************************************************************************************/ /* paged_array_new_array_all */ /***************************************************************************************************************************/ void *paged_array_new_array_all(const paged_array_t *pa) { return paged_array_new_array(pa, 0, pa->len); } /***************************************************************************************************************************/ /* paged_array_new_array */ /***************************************************************************************************************************/ void *paged_array_new_array(const paged_array_t *pa, size_t first, size_t num) { void *output_array= allocate( pa-> elem_size * num ); paged_array_extract( pa, output_array, first, num ); return output_array; } /***************************************************************************************************************************/ /* paged_array_find */ /***************************************************************************************************************************/ ptrdiff_t paged_array_find(const paged_array_t *pa, int (*comp_fn)(const void*,const void*,size_t), const void *user) { size_t i; for( i= 0; i < pa-> len; ++i ) if( ! comp_fn( paged_array_index( pa, i ), user, pa-> elem_size )) return i; return -1; } /***************************************************************************************************************************/ /* paged_array_callback_all */ /***************************************************************************************************************************/ void paged_array_callback_all(const paged_array_t *pa, void (*callback)(void*,void*), void *user) { paged_array_callback(pa, callback, user, 0, pa->len); } /***************************************************************************************************************************/ /* paged_array_callback */ /***************************************************************************************************************************/ void paged_array_callback(const paged_array_t *pa, void (*callback)(void*,void*), void *user, size_t first, size_t num) { size_t i= first; size_t n= first + num; for( ; i < n; ++i ) { callback( paged_array_index( pa, i ), user ); } } /***************************************************************************************************************************/ /* paged_array_set_length */ /***************************************************************************************************************************/ void paged_array_set_length(paged_array_t *pa, size_t len) { size_t need_pages= (len + pa-> elems_page - 1) / pa-> elems_page; if( len < pa-> len ) { /* we are shortening the array */ if( pa-> len > pa-> elems_page ) { /* the array has more than one page */ if( pa-> ptr. pages-> len > need_pages ) { /* free some pages */ paged_array_callback(pa-> ptr. pages, indirect_free, NULL, need_pages, pa-> ptr. pages-> len - need_pages); paged_array_set_length(pa-> ptr. pages, need_pages); pa-> len= pa-> ptr. pages-> len * pa-> elems_page; if( need_pages < 2 ) { /* change the array from multi-pages to one page */ char *page= *(char**) pa-> ptr. pages-> ptr. page; paged_array_delete( pa-> ptr. pages ); pa-> ptr. page= page; } } } if(( pa-> len != 0 )&&( len == 0 )) { /* array has one page that is no longer needed */ free( pa-> ptr. page ); } } else { /* we are lengthening the array */ if(( pa-> len == 0 )&&( len != 0 )) { /* the array has no pages but needs at least one */ pa-> ptr. page= allocate( pa-> elem_size * pa-> elems_page ); pa-> len= 1; } if(( pa-> len <= pa-> elems_page )&&( len > pa-> elems_page )) { /* the array has one page and needs more than one */ char *pages[2] = { pa-> ptr. page, allocate( pa-> elem_size * pa-> elems_page ) }; pa-> ptr. pages = paged_array_new( sizeof pages[0], PAGE_ARRAY_ELEMS_PAGE, pages, sizeof pages / sizeof pages[0] ); pa-> len= pa-> elems_page + 1; } if( need_pages > 2 ) { while( pa-> ptr. pages-> len < need_pages ) { /* we need another whole page */ char *new_page= allocate( pa-> elem_size * pa-> elems_page ); paged_array_append1( pa-> ptr. pages, & new_page ); pa-> len= pa-> ptr. pages-> len * pa-> elems_page; } } } pa-> len= len; } /***************************************************************************************************************************/ /* paged_array_extend1 */ /***************************************************************************************************************************/ void *paged_array_extend1(paged_array_t *pa) { paged_array_set_length( pa, pa-> len + 1 ); return paged_array_index( pa, pa-> len - 1 ); } /***************************************************************************************************************************/ /* paged_array_append1 */ /***************************************************************************************************************************/ void *paged_array_append1(paged_array_t *pa, const void *elem) { return memcpy( paged_array_extend1(pa), elem, pa-> elem_size ); } /***************************************************************************************************************************/ /* paged_array_append */ /***************************************************************************************************************************/ void paged_array_append(paged_array_t *pa, const void *input_array, size_t num) { paged_array_set_length( pa, pa-> len + num ); paged_array_overwrite(pa, input_array, pa-> len - num, num); } /***************************************************************************************************************************/ /* paged_array_overwrite1 */ /***************************************************************************************************************************/ void *paged_array_overwrite1(paged_array_t *pa, size_t index, const void *elem) { if( pa-> len <= index ) paged_array_set_length( pa, index + 1 ); return memcpy( paged_array_index( pa, index), elem, pa-> elem_size ); } /***************************************************************************************************************************/ /* paged_array_overwrite */ /***************************************************************************************************************************/ void paged_array_overwrite(paged_array_t *pa, const void *input_array, size_t first, size_t num) { if( pa-> len <( first + num )) { /* need to lengthen array first */ paged_array_set_length( pa, first + num ); } if((( first % pa-> elems_page) + num) <= pa-> elems_page ) { /* requested range is all within one page */ memcpy( paged_array_index( pa, first ), input_array, pa-> elem_size * num); } else { size_t page_size= pa-> elem_size * pa-> elems_page; const char *in_ptr= input_array; /* number of elements in the page starting at first */ size_t remainder= pa-> elems_page - (first % pa-> elems_page); size_t remainder_size = pa-> elem_size * remainder; /* copy to the page starting at first */ memcpy( paged_array_index( pa, first ), in_ptr, remainder_size ); first+= remainder; num-= remainder; in_ptr+= remainder_size; while( num > pa-> elems_page ) { /* copy whole pages */ memcpy( paged_array_index( pa, first ), in_ptr, page_size ); first+= pa-> elems_page; num-= pa-> elems_page; in_ptr+= page_size; } /* copy the last partial page */ memcpy( paged_array_index( pa, first ), in_ptr, pa-> elem_size * num ); } } /***************************************************************************************************************************/ /* allocate */ /***************************************************************************************************************************/ static void *allocate( size_t size ) { void *mem= malloc( size ); if( !mem ) abort(); return mem; } /***************************************************************************************************************************/ /* indirect_free */ /***************************************************************************************************************************/ static void indirect_free( void *pp, void *unrequired ) { (void) unrequired; free( *(char**) pp ); }