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