-
Notifications
You must be signed in to change notification settings - Fork 1
/
yu_common.h
244 lines (197 loc) · 6.18 KB
/
yu_common.h
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
#pragma once
#include <stddef.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <float.h>
/**
* A few things to keep in mind —
*
* 1. yu_common and associated files make _heavy_ use of the C preprocessor.
* Turn back now if you don't like cpp.
* 2. You should be familiar with X macros <https://en.wikipedia.org/wiki/X_Macro>.
* 3. You should probably sacrifice a young goat to Cthulhu before digging
* around in too much of the higher-order macro stuff.
*/
/* Integer types */
typedef int8_t s8;
typedef uint8_t u8;
typedef int16_t s16;
typedef uint16_t u16;
typedef int32_t s32;
typedef uint32_t u32;
typedef int64_t s64;
typedef uint64_t u64;
/* Compiler-specific directives */
#ifdef __GNUC__
#define YU_UNUSED(x) x __attribute__((unused))
#define YU_INLINE inline __attribute__((always_inline))
#define YU_PURE __attribute__((pure))
#define YU_CONST __attribute__((const))
#define YU_RETURN_ALIGNED(n) __attribute__((assume_aligned(n)))
#define YU_MALLOC_LIKE __attribute__((malloc))
#define YU_CHECK_RETURN(type) __attribute__((warn_unused_result)) type
#define YU_LIKELY(expr) __builtin_expect(!!(expr),1)
#define YU_UNLIKELY(expr) __builtin_expect(!!(expr),0)
#elif _MSC_VER
// Thanks to http://stackoverflow.com/a/9602511 for the warning number for MSVC
#define YU_UNUSED(x) __pragma(warning(surpress:4100)) x
#define YU_INLINE inline __forceinline
#define YU_PURE
#define YU_CONST
#define YU_RETURN_ALIGNED(n)
#define YU_MALLOC_LIKE __declspec(restrict)
#define YU_CHECK_RETURN(type) _Check_return_ type
#define YU_LIKELY(expr) (expr)
#define YU_UNLIKELY(expr) (expr)
#else
#define YU_INLINE inline
#define YU_PURE
#define YU_CONST
#define YU_RETURN_ALIGNED(n)
#define YU_MALLOC_LIKE
#define YU_CHECK_RETURN(type) type
#define YU_LIKELY(expr) (expr)
#define YU_UNLIKELY(expr) (expr)
#endif
#define YU_INTERNAL_INCLUDES
/** Common functions **/
/* Math */
u32 yu_ceil_log2(u64 n);
// *BSD puts alloca in stdlib.h (and doesn't have alloca.h)
// while other *nixes don't (OS X has it in both).
// Windows puts it in malloc.h and calls it _alloca.
#if defined(__unix__)
#include <sys/param.h>
#ifndef BSD
#include <alloca.h>
#endif
#elif defined(_WIN32)
#include <malloc.h>
#define alloca _alloca
#endif
/** Common macros **/
/* Macro manipulating macros */
#define PASTE(x, y) x ## y
#define CAT(x, y) PASTE(x, y)
#define NOTHING()
#define DEFER(x) x NOTHING()
#define EXPAND(...) __VA_ARGS__
/* Safe min/max */
#define min(a,b) ({ \
__typeof__(a) _a = (a); \
__typeof__(b) _b = (b); \
_a < _b ? _a : _b; \
})
#define max(a,b) ({ \
__typeof__(a) _a = (a); \
__typeof__(b) _b = (b); \
_a < _b ? _b : _a; \
})
#define elemcount(arr) (sizeof((arr))/sizeof((arr)[0]))
#define containerof(ptr,type,member) ({ \
__typeof__(((type *)0)->member) *_mp = (ptr); \
(type *)((u8 *)_mp - offsetof(type,member)); \
})
/* For namespacing various types of tables, trees, lists, etc */
#define YU_NAME(ns, name) EXPAND(DEFER(PASTE)(PASTE(ns, _), name))
/* Define enums with printable string names using X-macros */
#define DEF_ENUM_MEMBER(name, ...) name,
#define DEF_ENUM_NAME_CASE(name, ...) case name: return #name;
// Dummy value is to force a signed enum type and get GCC/Clang to
// shut up about certain warnings.
// TODO I feel like there's a better way.
#define DEF_ENUM(typename, XX) \
typedef enum { _ ## typename ## dummy = -1, XX(DEF_ENUM_MEMBER) } typename; \
#define DEF_ENUM_NAME_FUNC(typename, XX) \
inline const char *YU_NAME(typename, name)(typename x) { \
switch (x) { \
XX(DEF_ENUM_NAME_CASE) \
default: return "unknown"; \
} \
}
#ifdef __GNUC__
#define DEF_PACKED_ENUM(typename, XX) \
typedef enum __attribute__((packed)) { XX(DEF_ENUM_MEMBER) } typename;
#elif _MSVC_VER_
#define DEF_PACKED_ENUM(typename, XX) \
enum typename : unsigned char { XX(DEF_ENUM_MEMBER) };
#else
#define DEF_PACKED_ENUM(typename, XX) DEF_ENUM(typename, XX)
#endif
/* Assertions */
#include <assert.h>
/** External library includes **/
#include <gmp.h>
#include <mpfr.h>
#include "SFMT/SFMT.h"
/** Platform Abstraction Layer **/
#include "platform.h"
#include "yu_checked_math.h"
/** Core common Yu functions **/
/**
* ERROR HANDLING
*
* There are quite a lot of macros defined in yu_err. Most of it is not
* particularly important to understanding the rest of the source, but
* read it for more details.
* The gist of it is just a wrapper for code like
* `if ((yu_local_err = expr) != YU_OK) goto error;`
*/
#include "yu_err.h"
/**
* DATA STRUCTURES
*
* A small collection of useful, cache-friendly[1] data structures.
*
* These are implemented as giant macros that sort of emulate C++ templates.
* They come in pairs: YU_DATASTRUCTURE(...) AND YU_DATASTRUCTURE_IMPL(...)
* where the former defines the structs and prototypes and the latter
* defines the implementation. The arguments are always the same to the both
* of them.
*
* Yes, this does make debugging them something of a pain. In general, compiling
* with -g3 -gdwarf-4 eases the pain slightly. Otherwise, try the ‘debug_templates’
* rule in the Makefile.
*
*
* 1. splaytree is not particularly cache friendly. I'm working on a cache-oblivious
* layout for it.
*/
#include "yu_hashtable.h"
#include "yu_splaytree.h"
#include "yu_quickheap.h"
/**
* MEMORY MANAGEMENT
*
* Generic allocator API — see file for details.
*/
#include "yu_alloc.h"
/**
* DYNAMIC BUFFERS
*
* Heap-allocated buffers implemented with ‘fat pointers’.
*
* These keep some metadata in front of the memory that they allocate,
* for things like length, buffer capacity, etc. The memory layout looks
* like so:
*
* +-----------------------------------------+
* | struct yu_buf_dat | buffer contents ... |
* +-----------------------------------------+
* ^^^^^^^^^^^^^^^^^^^^^^^
* returned yu_buf pointer
*
* yu_str is slightly more interesting, in that it's fully Unicode-aware,
* including the Extended Grapheme Cluster.
*/
#include "yu_buf.h"
#include "yu_str.h"
#undef YU_INTERNAL_INCLUDES
#ifdef DMALLOC
#include <dmalloc.h>
#endif