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
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
|
// Copyright © Tavian Barnes <tavianator@tavianator.com>
// SPDX-License-Identifier: 0BSD
/**
* Configuration and fundamental utilities.
*/
#ifndef BFS_H
#define BFS_H
#include <assert.h> // For __GLIBC__
#include <stddef.h> // For offsetof
// Standard versions
/** Possible __STDC_VERSION__ values. */
#define C95 199409L
#define C99 199901L
#define C11 201112L
#define C17 201710L
#define C23 202311L
/** Possible _POSIX_C_SOURCE and _POSIX_<OPTION> values. */
#define POSIX_1990 1
#define POSIX_1992 2
#define POSIX_1993 199309L
#define POSIX_1995 199506L
#define POSIX_2001 200112L
#define POSIX_2008 200809L
#define POSIX_2024 202405L
// Build configuration
#include "config.h"
#ifndef BFS_COMMAND
# define BFS_COMMAND "bfs"
#endif
#ifndef BFS_HOMEPAGE
# define BFS_HOMEPAGE "https://tavianator.com/projects/bfs.html"
#endif
#ifndef BFS_LINT
# define BFS_LINT false
#endif
// This is a symbol instead of a literal so we don't have to rebuild everything
// when the version number changes
extern const char bfs_version[];
extern const char bfs_confflags[];
extern const char bfs_cc[];
extern const char bfs_cppflags[];
extern const char bfs_cflags[];
extern const char bfs_ldflags[];
extern const char bfs_ldlibs[];
// Fundamental utilities
/**
* Given `ptr = &t->member`, return `t`.
*/
#define container_of(ptr, type, member) \
(container_of_typecheck(ptr, type, member), \
(type *)((char *)ptr - offsetof(type, member)))
#define container_of_typecheck(ptr, type, field) \
(void)sizeof(ptr - &((type *)NULL)->field)
/**
* A preprocessor conditional.
*
* BFS_VA_IF(A)(B)(C) => B
* BFS_VA_IF( )(B)(C) => C
*/
#define BFS_VA_IF(...) BFS_VA_IF_AB ## __VA_OPT__(C)
// BFS_VA_IF(A)(B)(C) => BFS_VA_IF_ABC(B)(C)
// BFS_VA_IF( )(B)(C) => BFS_VA_IF_AB(B)(C)
#define BFS_VA_IF_ABC(...) __VA_ARGS__ BFS_VA_IGNORE
// BFS_VA_IF_ABC(B)(C) => B BFS_VA_IGNORE(C)
#define BFS_VA_IF_AB(...) BFS_VA_REPEAT
// BFS_VA_IF_AB(B)(C) => BFS_VA_REPEAT(C)
#define BFS_VA_IGNORE(...)
#define BFS_VA_REPEAT(...) __VA_ARGS__
/**
* False sharing/destructive interference/largest cache line size.
*/
#ifdef __GCC_DESTRUCTIVE_SIZE
# define FALSE_SHARING_SIZE __GCC_DESTRUCTIVE_SIZE
#else
# define FALSE_SHARING_SIZE 64
#endif
/**
* True sharing/constructive interference/smallest cache line size.
*/
#ifdef __GCC_CONSTRUCTIVE_SIZE
# define TRUE_SHARING_SIZE __GCC_CONSTRUCTIVE_SIZE
#else
# define TRUE_SHARING_SIZE 64
#endif
/**
* Alignment specifier that avoids false sharing.
*/
#define cache_align alignas(FALSE_SHARING_SIZE)
// Wrappers for attributes
/**
* Silence warnings about unused declarations.
*/
#if __has_c_attribute(maybe_unused)
# define _maybe_unused maybe_unused
#elif __has_c_attribute(gnu::unused)
# define _maybe_unused gnu::unused
#else
# define _maybe_unused
#endif
/**
* Warn if a value is unused.
*/
#if __has_c_attribute(nodiscard)
# define _nodiscard nodiscard
#elif __has_c_attribute(gnu::warn_unused_result)
# define _nodiscard gnu::warn_unused_result
#else
# define _nodiscard
#endif
/**
* Hint to avoid inlining a function.
*/
#if __has_c_attribute(gnu::noinline)
# define _noinline gnu::noinline
#else
# define _noinline
#endif
/**
* Hint that a function is unlikely to be called.
*/
#if __has_c_attribute(gnu::cold)
# define _cold _noinline, gnu::cold
#else
# define _cold _noinline
#endif
/**
* Marks a non-returning function.
*/
#if __has_c_attribute(noreturn)
# define _noreturn noreturn
#elif __has_c_attribute(gnu::noreturn)
# define _noreturn gnu::noreturn
#else
# define _noreturn
#endif
/**
* Adds compiler warnings for bad printf()-style function calls, if supported.
*/
#if __has_c_attribute(gnu::format)
# define _printf(fmt, args) gnu::format(printf, fmt, args)
#else
# define _printf(fmt, args)
#endif
/**
* Annotates functions that potentially modify and return format strings.
*/
#if __has_c_attribute(gnu::format_arg)
# define _format_arg(arg) gnu::format_arg(arg)
#else
# define _format_arg(arg)
#endif
/**
* Annotates allocator-like functions.
*/
#if __has_c_attribute(gnu::malloc)
# if __GNUC__ >= 11 && !__OPTIMIZE__ // malloc(deallocator) disables inlining on GCC
# define _malloc(...) _nodiscard, gnu::malloc(__VA_ARGS__)
# else
# define _malloc(...) _nodiscard, gnu::malloc
# endif
#else
# define _malloc(...) _nodiscard
#endif
/**
* Specifies that a function returns allocations with a given alignment.
*/
#if __has_c_attribute(gnu::alloc_align)
# define _alloc_align(param) gnu::alloc_align(param)
#else
# define _alloc_align(param)
#endif
/**
* Specifies that a function returns allocations with a given size.
*/
#if __has_c_attribute(gnu::alloc_size)
# define _alloc_size(...) gnu::alloc_size(__VA_ARGS__)
#else
# define _alloc_size(...)
#endif
/**
* Shorthand for _alloc_align() and _alloc_size().
*/
#define _aligned_alloc(align, ...) _alloc_align(align), _alloc_size(__VA_ARGS__)
/**
* Check if function multiversioning via GNU indirect functions (ifunc) is supported.
*
* Disabled on TSan due to https://github.com/google/sanitizers/issues/342.
*/
#ifndef BFS_USE_TARGET_CLONES
# if __has_c_attribute(gnu::target_clones) \
&& (__GLIBC__ || __FreeBSD__) \
&& !__SANITIZE_THREAD__ \
&& !__SANITIZE_TYPE__
# define BFS_USE_TARGET_CLONES true
# else
# define BFS_USE_TARGET_CLONES false
# endif
#endif
/**
* Apply the target_clones attribute, if available.
*/
#if BFS_USE_TARGET_CLONES
# define _target_clones(...) gnu::target_clones(__VA_ARGS__)
#else
# define _target_clones(...)
#endif
/**
* Mark the size of a flexible array member.
*/
#if __has_c_attribute(clang::counted_by)
# define _counted_by(...) clang::counted_by(__VA_ARGS__)
#elif __has_c_attribute(gnu::counted_by)
# define _counted_by(...) gnu::counted_by(__VA_ARGS__)
#else
# define _counted_by(...)
#endif
/**
* Optimization hint to not unroll a loop.
*/
#if BFS_HAS_PRAGMA_NOUNROLL
# define _nounroll _Pragma("nounroll")
#elif __GNUC__ && !__clang__
# define _nounroll _Pragma("GCC unroll 0")
#else
# define _nounroll
#endif
#endif // BFS_H
|
