1 /*
2 * nghttp2 - HTTP/2 C Library
3 *
4 * Copyright (c) 2015 Tatsuhiro Tsujikawa
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 */
25 #ifndef TEMPLATE_H
26 #define TEMPLATE_H
27
28 #include "nghttp2_config.h"
29
30 #include <cstring>
31 #include <cstdio>
32 #include <cstdlib>
33 #include <memory>
34 #include <array>
35 #include <functional>
36 #include <typeinfo>
37 #include <algorithm>
38 #include <ostream>
39 #include <utility>
40
41 namespace nghttp2 {
42
43 // std::forward is constexpr since C++14
44 template <typename... T>
45 constexpr std::array<
46 typename std::decay<typename std::common_type<T...>::type>::type,
47 sizeof...(T)>
make_array(T &&...t)48 make_array(T &&...t) {
49 return std::array<
50 typename std::decay<typename std::common_type<T...>::type>::type,
51 sizeof...(T)>{{std::forward<T>(t)...}};
52 }
53
array_size(T (&)[N])54 template <typename T, size_t N> constexpr size_t array_size(T (&)[N]) {
55 return N;
56 }
57
str_size(T (&)[N])58 template <typename T, size_t N> constexpr size_t str_size(T (&)[N]) {
59 return N - 1;
60 }
61
62 // inspired by <http://blog.korfuri.fr/post/go-defer-in-cpp/>, but our
63 // template can take functions returning other than void.
64 template <typename F, typename... T> struct Defer {
DeferDefer65 Defer(F &&f, T &&...t)
66 : f(std::bind(std::forward<F>(f), std::forward<T>(t)...)) {}
DeferDefer67 Defer(Defer &&o) noexcept : f(std::move(o.f)) {}
~DeferDefer68 ~Defer() { f(); }
69
70 using ResultType = typename std::result_of<typename std::decay<F>::type(
71 typename std::decay<T>::type...)>::type;
72 std::function<ResultType()> f;
73 };
74
defer(F && f,T &&...t)75 template <typename F, typename... T> Defer<F, T...> defer(F &&f, T &&...t) {
76 return Defer<F, T...>(std::forward<F>(f), std::forward<T>(t)...);
77 }
78
test_flags(T t,F flags)79 template <typename T, typename F> bool test_flags(T t, F flags) {
80 return (t & flags) == flags;
81 }
82
83 // doubly linked list of element T*. T must have field T *dlprev and
84 // T *dlnext, which point to previous element and next element in the
85 // list respectively.
86 template <typename T> struct DList {
DListDList87 DList() : head(nullptr), tail(nullptr), len(0) {}
88
89 DList(const DList &) = delete;
90 DList &operator=(const DList &) = delete;
91
DListDList92 DList(DList &&other) noexcept
93 : head{std::exchange(other.head, nullptr)},
94 tail{std::exchange(other.tail, nullptr)},
95 len{std::exchange(other.len, 0)} {}
96
97 DList &operator=(DList &&other) noexcept {
98 if (this == &other) {
99 return *this;
100 }
101 head = std::exchange(other.head, nullptr);
102 tail = std::exchange(other.tail, nullptr);
103 len = std::exchange(other.len, 0);
104
105 return *this;
106 }
107
appendDList108 void append(T *t) {
109 ++len;
110 if (tail) {
111 tail->dlnext = t;
112 t->dlprev = tail;
113 tail = t;
114 return;
115 }
116 head = tail = t;
117 }
118
removeDList119 void remove(T *t) {
120 --len;
121 auto p = t->dlprev;
122 auto n = t->dlnext;
123 if (p) {
124 p->dlnext = n;
125 }
126 if (head == t) {
127 head = n;
128 }
129 if (n) {
130 n->dlprev = p;
131 }
132 if (tail == t) {
133 tail = p;
134 }
135 t->dlprev = t->dlnext = nullptr;
136 }
137
emptyDList138 bool empty() const { return head == nullptr; }
139
sizeDList140 size_t size() const { return len; }
141
142 T *head, *tail;
143 size_t len;
144 };
145
dlist_delete_all(DList<T> & dl)146 template <typename T> void dlist_delete_all(DList<T> &dl) {
147 for (auto e = dl.head; e;) {
148 auto next = e->dlnext;
149 delete e;
150 e = next;
151 }
152 }
153
154 // User-defined literals for K, M, and G (powers of 1024)
155
156 constexpr unsigned long long operator"" _k(unsigned long long k) {
157 return k * 1024;
158 }
159
160 constexpr unsigned long long operator"" _m(unsigned long long m) {
161 return m * 1024 * 1024;
162 }
163
164 constexpr unsigned long long operator"" _g(unsigned long long g) {
165 return g * 1024 * 1024 * 1024;
166 }
167
168 // User-defined literals for time, converted into double in seconds
169
170 // hours
171 constexpr double operator"" _h(unsigned long long h) { return h * 60 * 60; }
172
173 // minutes
174 constexpr double operator"" _min(unsigned long long min) { return min * 60; }
175
176 // seconds
177 constexpr double operator"" _s(unsigned long long s) { return s; }
178
179 // milliseconds
180 constexpr double operator"" _ms(unsigned long long ms) { return ms / 1000.; }
181
182 // Returns a copy of NULL-terminated string [first, last).
183 template <typename InputIt>
strcopy(InputIt first,InputIt last)184 std::unique_ptr<char[]> strcopy(InputIt first, InputIt last) {
185 auto res = std::make_unique<char[]>(last - first + 1);
186 *std::copy(first, last, res.get()) = '\0';
187 return res;
188 }
189
190 // Returns a copy of NULL-terminated string |val|.
strcopy(const char * val)191 inline std::unique_ptr<char[]> strcopy(const char *val) {
192 return strcopy(val, val + strlen(val));
193 }
194
strcopy(const char * val,size_t n)195 inline std::unique_ptr<char[]> strcopy(const char *val, size_t n) {
196 return strcopy(val, val + n);
197 }
198
199 // Returns a copy of val.c_str().
strcopy(const std::string & val)200 inline std::unique_ptr<char[]> strcopy(const std::string &val) {
201 return strcopy(std::begin(val), std::end(val));
202 }
203
strcopy(const std::unique_ptr<char[]> & val)204 inline std::unique_ptr<char[]> strcopy(const std::unique_ptr<char[]> &val) {
205 if (!val) {
206 return nullptr;
207 }
208 return strcopy(val.get());
209 }
210
strcopy(const std::unique_ptr<char[]> & val,size_t n)211 inline std::unique_ptr<char[]> strcopy(const std::unique_ptr<char[]> &val,
212 size_t n) {
213 if (!val) {
214 return nullptr;
215 }
216 return strcopy(val.get(), val.get() + n);
217 }
218
219 // ImmutableString represents string that is immutable unlike
220 // std::string. It has c_str() and size() functions to mimic
221 // std::string. It manages buffer by itself. Just like std::string,
222 // c_str() returns NULL-terminated string, but NULL character may
223 // appear before the final terminal NULL.
224 class ImmutableString {
225 public:
226 using traits_type = std::char_traits<char>;
227 using value_type = traits_type::char_type;
228 using allocator_type = std::allocator<char>;
229 using size_type = std::allocator_traits<allocator_type>::size_type;
230 using difference_type =
231 std::allocator_traits<allocator_type>::difference_type;
232 using const_reference = const value_type &;
233 using const_pointer = const value_type *;
234 using const_iterator = const_pointer;
235 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
236
ImmutableString()237 ImmutableString() : len(0), base("") {}
ImmutableString(const char * s,size_t slen)238 ImmutableString(const char *s, size_t slen)
239 : len(slen), base(copystr(s, s + len)) {}
ImmutableString(const char * s)240 explicit ImmutableString(const char *s)
241 : len(strlen(s)), base(copystr(s, s + len)) {}
ImmutableString(const std::string & s)242 explicit ImmutableString(const std::string &s)
243 : len(s.size()), base(copystr(std::begin(s), std::end(s))) {}
244 template <typename InputIt>
ImmutableString(InputIt first,InputIt last)245 ImmutableString(InputIt first, InputIt last)
246 : len(std::distance(first, last)), base(copystr(first, last)) {}
ImmutableString(const ImmutableString & other)247 ImmutableString(const ImmutableString &other)
248 : len(other.len), base(copystr(std::begin(other), std::end(other))) {}
ImmutableString(ImmutableString && other)249 ImmutableString(ImmutableString &&other) noexcept
250 : len{std::exchange(other.len, 0)}, base{std::exchange(other.base, "")} {}
~ImmutableString()251 ~ImmutableString() {
252 if (len) {
253 delete[] base;
254 }
255 }
256
257 ImmutableString &operator=(const ImmutableString &other) {
258 if (this == &other) {
259 return *this;
260 }
261 if (len) {
262 delete[] base;
263 }
264 len = other.len;
265 base = copystr(std::begin(other), std::end(other));
266 return *this;
267 }
268 ImmutableString &operator=(ImmutableString &&other) noexcept {
269 if (this == &other) {
270 return *this;
271 }
272 if (len) {
273 delete[] base;
274 }
275 len = std::exchange(other.len, 0);
276 base = std::exchange(other.base, "");
277 return *this;
278 }
279
from_lit(const char (& s)[N])280 template <size_t N> static ImmutableString from_lit(const char (&s)[N]) {
281 return ImmutableString(s, N - 1);
282 }
283
begin()284 const_iterator begin() const { return base; };
cbegin()285 const_iterator cbegin() const { return base; };
286
end()287 const_iterator end() const { return base + len; };
cend()288 const_iterator cend() const { return base + len; };
289
rbegin()290 const_reverse_iterator rbegin() const {
291 return const_reverse_iterator{base + len};
292 }
crbegin()293 const_reverse_iterator crbegin() const {
294 return const_reverse_iterator{base + len};
295 }
296
rend()297 const_reverse_iterator rend() const { return const_reverse_iterator{base}; }
crend()298 const_reverse_iterator crend() const { return const_reverse_iterator{base}; }
299
c_str()300 const char *c_str() const { return base; }
size()301 size_type size() const { return len; }
empty()302 bool empty() const { return len == 0; }
303 const_reference operator[](size_type pos) const { return *(base + pos); }
304
305 private:
copystr(InputIt first,InputIt last)306 template <typename InputIt> const char *copystr(InputIt first, InputIt last) {
307 if (first == last) {
308 return "";
309 }
310 auto res = new char[std::distance(first, last) + 1];
311 *std::copy(first, last, res) = '\0';
312 return res;
313 }
314
315 size_type len;
316 const char *base;
317 };
318
319 inline bool operator==(const ImmutableString &lhs, const ImmutableString &rhs) {
320 return lhs.size() == rhs.size() &&
321 std::equal(std::begin(lhs), std::end(lhs), std::begin(rhs));
322 }
323
324 inline bool operator==(const ImmutableString &lhs, const std::string &rhs) {
325 return lhs.size() == rhs.size() &&
326 std::equal(std::begin(lhs), std::end(lhs), std::begin(rhs));
327 }
328
329 inline bool operator==(const std::string &lhs, const ImmutableString &rhs) {
330 return rhs == lhs;
331 }
332
333 inline bool operator==(const ImmutableString &lhs, const char *rhs) {
334 return lhs.size() == strlen(rhs) &&
335 std::equal(std::begin(lhs), std::end(lhs), rhs);
336 }
337
338 inline bool operator==(const char *lhs, const ImmutableString &rhs) {
339 return rhs == lhs;
340 }
341
342 inline bool operator!=(const ImmutableString &lhs, const ImmutableString &rhs) {
343 return !(lhs == rhs);
344 }
345
346 inline bool operator!=(const ImmutableString &lhs, const std::string &rhs) {
347 return !(lhs == rhs);
348 }
349
350 inline bool operator!=(const std::string &lhs, const ImmutableString &rhs) {
351 return !(rhs == lhs);
352 }
353
354 inline bool operator!=(const ImmutableString &lhs, const char *rhs) {
355 return !(lhs == rhs);
356 }
357
358 inline bool operator!=(const char *lhs, const ImmutableString &rhs) {
359 return !(rhs == lhs);
360 }
361
362 inline std::ostream &operator<<(std::ostream &o, const ImmutableString &s) {
363 return o.write(s.c_str(), s.size());
364 }
365
366 inline std::string &operator+=(std::string &lhs, const ImmutableString &rhs) {
367 lhs.append(rhs.c_str(), rhs.size());
368 return lhs;
369 }
370
371 // StringRef is a reference to a string owned by something else. So
372 // it behaves like simple string, but it does not own pointer. When
373 // it is default constructed, it has empty string. You can freely
374 // copy or move around this struct, but never free its pointer. str()
375 // function can be used to export the content as std::string.
376 class StringRef {
377 public:
378 using traits_type = std::char_traits<char>;
379 using value_type = traits_type::char_type;
380 using allocator_type = std::allocator<char>;
381 using size_type = std::allocator_traits<allocator_type>::size_type;
382 using difference_type =
383 std::allocator_traits<allocator_type>::difference_type;
384 using const_reference = const value_type &;
385 using const_pointer = const value_type *;
386 using const_iterator = const_pointer;
387 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
388
StringRef()389 constexpr StringRef() : base(""), len(0) {}
StringRef(const std::string & s)390 explicit StringRef(const std::string &s) : base(s.c_str()), len(s.size()) {}
StringRef(const ImmutableString & s)391 explicit StringRef(const ImmutableString &s)
392 : base(s.c_str()), len(s.size()) {}
StringRef(const char * s)393 explicit StringRef(const char *s) : base(s), len(strlen(s)) {}
StringRef(const char * s,size_t n)394 constexpr StringRef(const char *s, size_t n) : base(s), len(n) {}
395 template <typename CharT>
StringRef(const CharT * s,size_t n)396 constexpr StringRef(const CharT *s, size_t n)
397 : base(reinterpret_cast<const char *>(s)), len(n) {}
398 template <typename InputIt>
StringRef(InputIt first,InputIt last)399 StringRef(InputIt first, InputIt last)
400 : base(reinterpret_cast<const char *>(&*first)),
401 len(std::distance(first, last)) {}
402 template <typename InputIt>
StringRef(InputIt * first,InputIt * last)403 StringRef(InputIt *first, InputIt *last)
404 : base(reinterpret_cast<const char *>(first)),
405 len(std::distance(first, last)) {}
406 template <typename CharT, size_t N>
from_lit(const CharT (& s)[N])407 constexpr static StringRef from_lit(const CharT (&s)[N]) {
408 return StringRef{s, N - 1};
409 }
from_maybe_nullptr(const char * s)410 static StringRef from_maybe_nullptr(const char *s) {
411 if (s == nullptr) {
412 return StringRef();
413 }
414
415 return StringRef(s);
416 }
417
begin()418 constexpr const_iterator begin() const { return base; };
cbegin()419 constexpr const_iterator cbegin() const { return base; };
420
end()421 constexpr const_iterator end() const { return base + len; };
cend()422 constexpr const_iterator cend() const { return base + len; };
423
rbegin()424 const_reverse_iterator rbegin() const {
425 return const_reverse_iterator{base + len};
426 }
crbegin()427 const_reverse_iterator crbegin() const {
428 return const_reverse_iterator{base + len};
429 }
430
rend()431 const_reverse_iterator rend() const { return const_reverse_iterator{base}; }
crend()432 const_reverse_iterator crend() const { return const_reverse_iterator{base}; }
433
c_str()434 constexpr const char *c_str() const { return base; }
size()435 constexpr size_type size() const { return len; }
empty()436 constexpr bool empty() const { return len == 0; }
437 constexpr const_reference operator[](size_type pos) const {
438 return *(base + pos);
439 }
440
str()441 std::string str() const { return std::string(base, len); }
byte()442 const uint8_t *byte() const {
443 return reinterpret_cast<const uint8_t *>(base);
444 }
445
446 private:
447 const char *base;
448 size_type len;
449 };
450
451 inline bool operator==(const StringRef &lhs, const StringRef &rhs) {
452 return lhs.size() == rhs.size() &&
453 std::equal(std::begin(lhs), std::end(lhs), std::begin(rhs));
454 }
455
456 inline bool operator==(const StringRef &lhs, const std::string &rhs) {
457 return lhs.size() == rhs.size() &&
458 std::equal(std::begin(lhs), std::end(lhs), std::begin(rhs));
459 }
460
461 inline bool operator==(const std::string &lhs, const StringRef &rhs) {
462 return rhs == lhs;
463 }
464
465 inline bool operator==(const StringRef &lhs, const char *rhs) {
466 return lhs.size() == strlen(rhs) &&
467 std::equal(std::begin(lhs), std::end(lhs), rhs);
468 }
469
470 inline bool operator==(const StringRef &lhs, const ImmutableString &rhs) {
471 return lhs.size() == rhs.size() &&
472 std::equal(std::begin(lhs), std::end(lhs), std::begin(rhs));
473 }
474
475 inline bool operator==(const ImmutableString &lhs, const StringRef &rhs) {
476 return rhs == lhs;
477 }
478
479 inline bool operator==(const char *lhs, const StringRef &rhs) {
480 return rhs == lhs;
481 }
482
483 inline bool operator!=(const StringRef &lhs, const StringRef &rhs) {
484 return !(lhs == rhs);
485 }
486
487 inline bool operator!=(const StringRef &lhs, const std::string &rhs) {
488 return !(lhs == rhs);
489 }
490
491 inline bool operator!=(const std::string &lhs, const StringRef &rhs) {
492 return !(rhs == lhs);
493 }
494
495 inline bool operator!=(const StringRef &lhs, const char *rhs) {
496 return !(lhs == rhs);
497 }
498
499 inline bool operator!=(const char *lhs, const StringRef &rhs) {
500 return !(rhs == lhs);
501 }
502
503 inline bool operator<(const StringRef &lhs, const StringRef &rhs) {
504 return std::lexicographical_compare(std::begin(lhs), std::end(lhs),
505 std::begin(rhs), std::end(rhs));
506 }
507
508 inline std::ostream &operator<<(std::ostream &o, const StringRef &s) {
509 return o.write(s.c_str(), s.size());
510 }
511
512 inline std::string &operator+=(std::string &lhs, const StringRef &rhs) {
513 lhs.append(rhs.c_str(), rhs.size());
514 return lhs;
515 }
516
run_app(std::function<int (int,char **)> app,int argc,char ** argv)517 inline int run_app(std::function<int(int, char **)> app, int argc,
518 char **argv) {
519 try {
520 return app(argc, argv);
521 } catch (const std::bad_alloc &) {
522 fputs("Out of memory\n", stderr);
523 } catch (const std::exception &x) {
524 fprintf(stderr, "Caught %s:\n%s\n", typeid(x).name(), x.what());
525 } catch (...) {
526 fputs("Unknown exception caught\n", stderr);
527 }
528 return EXIT_FAILURE;
529 }
530
531 } // namespace nghttp2
532
533 namespace std {
534 template <> struct hash<nghttp2::StringRef> {
535 std::size_t operator()(const nghttp2::StringRef &s) const noexcept {
536 // 32 bit FNV-1a:
537 // https://tools.ietf.org/html/draft-eastlake-fnv-16#section-6.1.1
538 uint32_t h = 2166136261u;
539 for (auto c : s) {
540 h ^= static_cast<uint8_t>(c);
541 h += (h << 1) + (h << 4) + (h << 7) + (h << 8) + (h << 24);
542 }
543 return h;
544 }
545 };
546 } // namespace std
547
548 #endif // TEMPLATE_H
549