1 #include "likely.h"
2 #include <stdlib.h>
3 #ifndef __MINGW32__
4 #include <fcntl.h>
5 #include <sys/mman.h>
6 #include <unistd.h>
7 #endif
8 #include "iarray.h"
9 #ifdef __dietlibc__
10 #include <sys/atomic.h>
11 #else
12 #define __CAS(ptr,oldval,newval) __sync_val_compare_and_swap(ptr,oldval,newval)
13 #endif
14
new_page(size_t pagesize)15 static iarray_page* new_page(size_t pagesize) {
16 #ifdef __MINGW32__
17 void* x=malloc(pagesize);
18 if (x==0) return 0;
19 #else
20 void* x=mmap(0,pagesize,PROT_READ|PROT_WRITE,MAP_ANONYMOUS|MAP_PRIVATE,-1,0);
21 if (x==MAP_FAILED) return 0;
22 #endif
23 return (iarray_page*)x;
24 }
25
iarray_allocate(iarray * ia,size_t pos)26 void* iarray_allocate(iarray* ia,size_t pos) {
27 size_t index,prevlen=ia->len;
28 /* first, find the linked list of pages */
29 iarray_page** p=&ia->pages[pos%(sizeof(ia->pages)/sizeof(ia->pages[0]))];
30 /* this is here so we don't munmap and then re-mmap pages when a
31 * certain path makes it necessary to mmap several pages into the
32 * linked list and we are competing with another thread that does the
33 * same thing */
34 iarray_page* newpage=0;
35 /* since we have a fan-out of 16, on page 0 the elements are 0, 16, 32, ...
36 * so we divide pos by the fan-out here */
37 size_t realpos=pos;
38 pos /= sizeof(ia->pages)/sizeof(ia->pages[0]);
39 /* now walk the linked list of pages until we reach the one we want */
40 for (index=0; ; index+=ia->elemperpage) {
41 if (!*p) {
42 if (!newpage)
43 if (!(newpage=new_page(ia->bytesperpage))) return 0;
44 if (__CAS(p,0,newpage)==0)
45 newpage=0;
46 }
47 if (index+ia->elemperpage>pos)
48 break;
49 p=&(*p)->next;
50 }
51 if (newpage)
52 #ifdef __MINGW32__
53 free(newpage);
54 #else
55 munmap(newpage,ia->bytesperpage);
56 #endif
57 {
58 size_t l;
59 do {
60 l=__CAS(&ia->len,prevlen,realpos);
61 } while (l<realpos);
62 }
63 return &(*p)->data[(pos-index)*ia->elemsize];
64 }
65