1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
#ifndef XAR_H
#define XAR_H
/* inspired by andrew reece's "exponential array" */
/* see https://danielchasehooper.com/posts/segment_array/ */
#include <stdbit.h>
#include "arena.h"
#define XAR_INIT_SZ 8
#define XAR_MAX_DOUBLE 26
typedef struct {
int n, chunks;
void *chunk[XAR_MAX_DOUBLE];
} XarHdr;
#define XAR(T) struct { int n, chunks; T *chunk[XAR_MAX_DOUBLE]; }
#define XAR_GET_T(xar, T, idx) (T*)(xar_get((XarHdr*)(xar), idx, sizeof(T)))
#define XAR_PUT_T(xar, T, idx, a) (T*)(xar_put((XarHdr*)(xar), idx, sizeof(T), a))
#define XAR_GET(xar, idx) XAR_GET_T(xar, typeof(**(xar)->chunk), idx)
#define XAR_PUT(xar, idx, a) XAR_PUT_T(xar, typeof(**(xar)->chunk), idx, a)
#define XAR_PUSH(xar, v, a) (*XAR_PUT(xar, (xar)->n++, a) = (v))
#define XAR_PUSH_T(xar, T, v, a) (*XAR_PUT_T(xar, T, (xar)->n++, a) = (v))
#define XAR_CHUNK(idx) (unsigned)(31 - stdc_leading_zeros(((unsigned)(idx) / XAR_INIT_SZ) + 1))
#define XAR_CHUNK_SZ(chnk) (XAR_INIT_SZ << (chnk))
#define XAR_SLOT(chnk, idx) ((idx) - (XAR_CHUNK_SZ(chnk) - XAR_CHUNK_SZ(0)))
static inline void *xar_get(XarHdr *xar, uint32_t idx, size_t elsz) {
uint32_t chnk = XAR_CHUNK(idx);
uint32_t slot = XAR_SLOT(chnk, idx);
return (char*)xar->chunk[chnk] + (slot * elsz);
}
static inline void *xar_put(XarHdr *xar, uint32_t idx, size_t elsz, Arena *a) {
uint32_t chnk = XAR_CHUNK(idx);
uint32_t slot = XAR_SLOT(chnk, idx);
while (xar->chunks <= chnk) {
xar->chunk[xar->chunks] = arena_alloc(a, elsz * XAR_CHUNK_SZ(xar->chunks), elsz);
xar->chunks++;
}
return (char*)xar->chunk[chnk] + (slot * elsz);
}
#define XAR_FOR_IDX_PTR_T(x, T, i, v, ...)\
do {\
int i = 0;\
for (int xar_for_chnk = 0; xar_for_chnk < (x)->chunks; xar_for_chnk++) {\
T *v = (x)->chunk[xar_for_chnk];\
T *xar_for_chnk_end = v + (xar_for_chnk == (x)->chunks - 1\
? XAR_SLOT(xar_for_chnk, (x)->n)\
: XAR_CHUNK_SZ(xar_for_chnk));\
while (v != xar_for_chnk_end) {\
__VA_ARGS__;\
v++;\
i++;\
}\
}\
} while(0)
#define XAR_FOR_IDX_VAL_T(x, T, i, v, ...)\
XAR_FOR_IDX_PTR_T(x, T, i, xar_for_chnk_##v##_ptr, {\
T v = *xar_for_chnk_##v##_ptr;\
__VA_ARGS__;\
})
#define XAR_FOR_PTR_T(x, T, v, ...)\
XAR_FOR_IDX_PTR_T(x, T, _xar_foreach_i, v, __VA_ARGS__)
#define XAR_FOR_VAL_T(x, T, v, ...)\
XAR_FOR_IDX_VAL_T(x, T, _xar_foreach_i, v, __VA_ARGS__)
#define XAR_FOR_IDX_PTR(xar, i, v, ...)\
XAR_FOR_IDX_PTR_T(xar, typeof(**(xar)->chunk), i, v, __VA_ARGS__)
#define XAR_FOR_IDX_VAL(xar, i, v, ...)\
XAR_FOR_IDX_VAL_T(xar, typeof(**(xar)->chunk), i, v, __VA_ARGS__)
#define XAR_FOR_VAL(xar, v, ...)\
XAR_FOR_VAL_T(xar, typeof(**(xar)->chunk), v, __VA_ARGS__)
#endif
|
