src/template.h

   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)>
  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
  54 template <typename T, size_t N> constexpr size_t array_size(T (&)[N]) {
  55   return N;
  56 }
  57
  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 {
  65   Defer(F &&f, T &&...t)
  66       : f(std::bind(std::forward<F>(f), std::forward<T>(t)...)) {}
  67   Defer(Defer &&o) noexcept : f(std::move(o.f)) {}
  68   ~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
  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
  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 {
  87   DList() : head(nullptr), tail(nullptr), len(0) {}
  88
  89   DList(const DList &) = delete;
  90   DList &operator=(const DList &) = delete;
  91
  92   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
 108   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
 119   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
 138   bool empty() const { return head == nullptr; }
 139
 140   size_t size() const { return len; }
 141
 142   T *head, *tail;
 143   size_t len;
 144 };
 145
 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>
 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|.
 191 inline std::unique_ptr<char[]> strcopy(const char *val) {
 192   return strcopy(val, val + strlen(val));
 193 }
 194
 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().
 200 inline std::unique_ptr<char[]> strcopy(const std::string &val) {
 201   return strcopy(std::begin(val), std::end(val));
 202 }
 203
 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
 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
 237   ImmutableString() : len(0), base("") {}
 238   ImmutableString(const char *s, size_t slen)
 239       : len(slen), base(copystr(s, s + len)) {}
 240   explicit ImmutableString(const char *s)
 241       : len(strlen(s)), base(copystr(s, s + len)) {}
 242   explicit ImmutableString(const std::string &s)
 243       : len(s.size()), base(copystr(std::begin(s), std::end(s))) {}
 244   template <typename InputIt>
 245   ImmutableString(InputIt first, InputIt last)
 246       : len(std::distance(first, last)), base(copystr(first, last)) {}
 247   ImmutableString(const ImmutableString &other)
 248       : len(other.len), base(copystr(std::begin(other), std::end(other))) {}
 249   ImmutableString(ImmutableString &&other) noexcept
 250       : len{std::exchange(other.len, 0)}, base{std::exchange(other.base, "")} {}
 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
 280   template <size_t N> static ImmutableString from_lit(const char (&s)[N]) {
 281     return ImmutableString(s, N - 1);
 282   }
 283
 284   const_iterator begin() const { return base; };
 285   const_iterator cbegin() const { return base; };
 286
 287   const_iterator end() const { return base + len; };
 288   const_iterator cend() const { return base + len; };
 289
 290   const_reverse_iterator rbegin() const {
 291     return const_reverse_iterator{base + len};
 292   }
 293   const_reverse_iterator crbegin() const {
 294     return const_reverse_iterator{base + len};
 295   }
 296
 297   const_reverse_iterator rend() const { return const_reverse_iterator{base}; }
 298   const_reverse_iterator crend() const { return const_reverse_iterator{base}; }
 299
 300   const char *c_str() const { return base; }
 301   size_type size() const { return len; }
 302   bool empty() const { return len == 0; }
 303   const_reference operator[](size_type pos) const { return *(base + pos); }
 304
 305 private:
 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
 389   constexpr StringRef() : base(""), len(0) {}
 390   explicit StringRef(const std::string &s) : base(s.c_str()), len(s.size()) {}
 391   explicit StringRef(const ImmutableString &s)
 392       : base(s.c_str()), len(s.size()) {}
 393   explicit StringRef(const char *s) : base(s), len(strlen(s)) {}
 394   constexpr StringRef(const char *s, size_t n) : base(s), len(n) {}
 395   template <typename CharT>
 396   constexpr StringRef(const CharT *s, size_t n)
 397       : base(reinterpret_cast<const char *>(s)), len(n) {}
 398   template <typename InputIt>
 399   StringRef(InputIt first, InputIt last)
 400       : base(reinterpret_cast<const char *>(&*first)),
 401         len(std::distance(first, last)) {}
 402   template <typename InputIt>
 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>
 407   constexpr static StringRef from_lit(const CharT (&s)[N]) {
 408     return StringRef{s, N - 1};
 409   }
 410   static StringRef from_maybe_nullptr(const char *s) {
 411     if (s == nullptr) {
 412       return StringRef();
 413     }
 414
 415     return StringRef(s);
 416   }
 417
 418   constexpr const_iterator begin() const { return base; };
 419   constexpr const_iterator cbegin() const { return base; };
 420
 421   constexpr const_iterator end() const { return base + len; };
 422   constexpr const_iterator cend() const { return base + len; };
 423
 424   const_reverse_iterator rbegin() const {
 425     return const_reverse_iterator{base + len};
 426   }
 427   const_reverse_iterator crbegin() const {
 428     return const_reverse_iterator{base + len};
 429   }
 430
 431   const_reverse_iterator rend() const { return const_reverse_iterator{base}; }
 432   const_reverse_iterator crend() const { return const_reverse_iterator{base}; }
 433
 434   constexpr const char *c_str() const { return base; }
 435   constexpr size_type size() const { return len; }
 436   constexpr bool empty() const { return len == 0; }
 437   constexpr const_reference operator[](size_type pos) const {
 438     return *(base + pos);
 439   }
 440
 441   std::string str() const { return std::string(base, len); }
 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
 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