1 /* this header file comes from libowfat, http://www.fefe.de/libowfat/ */ 2 #ifndef IARRAY_H 3 #define IARRAY_H 4 5 /* This header defines an indirect array for use with the io_* routines. 6 * Assumptions: 7 * - the elements are small (many fit on one page), 8 * - the platform has an atomic compare-and-swap instruction 9 * - the compiler supports it via __sync_val_compare_and_swap 10 */ 11 12 #include "uint64.h" 13 #include <stddef.h> 14 #ifdef __MINGW32__ 15 #include <windows.h> 16 #else 17 #include <pthread.h> 18 #endif 19 20 /* The basic data structure is a static array of pointers to pages. 21 * Each page also contains a next pointer to form a linked list. 22 * To get to element n, you take n % the number of elements in the 23 * static array (iarray->pages) to get to the list of pages that 24 * contains it. Then keep going to the next page until you are on the 25 * right page. 26 * Note: The elements on each page are not contiguous. If the fanout is 27 * 16, the indices on page 0 are 0, 16, 32, ... 28 * To get to element 0, you'd go to iarray->pages[0].data, 29 * to get to element 1, you'd go to iarray->pages[1].data, 30 * to get to element 16, you'd go to iarray->pages[0].data+iarray->elemsize. 31 */ 32 typedef struct _iarray_page { 33 struct _iarray_page* next; 34 char data[]; 35 } iarray_page; 36 37 typedef struct { 38 iarray_page* pages[16]; 39 size_t elemsize,elemperpage,bytesperpage,len; 40 } iarray; 41 42 void iarray_init(iarray* ia,size_t elemsize); 43 void* iarray_get(iarray* ia,size_t pos); 44 void* iarray_allocate(iarray* ia,size_t pos); 45 size_t iarray_length(iarray* ia); 46 47 /* WARNING: do not use the array during or after iarray_free, make sure 48 * no threads are potentially doing anything with the iarray while it is 49 * being freed! */ 50 void iarray_free(iarray* ia); 51 52 #endif 53