silo/util.h

   1 #ifndef _UTIL_H_
   2 #define _UTIL_H_
   3
   4 #include <iostream>
   5 #include <sstream>
   6 #include <string>
   7 #include <limits>
   8 #include <queue>
   9 #include <utility>
  10 #include <memory>
  11 #include <atomic>
  12 #include <tuple>
  13 #include <algorithm>
  14
  15 #include <stdint.h>
  16 #include <pthread.h>
  17 #include <sys/time.h>
  18 #include <time.h>
  19 #include <cxxabi.h>
  20
  21 #include "macros.h"
  22 #include "small_vector.h"
  23
  24 namespace util {
  25
  26 // padded, aligned primitives
  27 template <typename T, bool Pedantic = true>
  28 class aligned_padded_elem {
  29 public:
  30
  31   template <class... Args>
  32   aligned_padded_elem(Args &&... args)
  33     : elem(std::forward<Args>(args)...)
  34   {
  35     if (Pedantic)
  36       ALWAYS_ASSERT(((uintptr_t)this % CACHELINE_SIZE) == 0);
  37   }
  38
  39   T elem;
  40   CACHE_PADOUT;
  41
  42   // syntactic sugar- can treat like a pointer
  43   inline T & operator*() { return elem; }
  44   inline const T & operator*() const { return elem; }
  45   inline T * operator->() { return &elem; }
  46   inline const T * operator->() const { return &elem; }
  47
  48 private:
  49   inline void
  50   __cl_asserter() const
  51   {
  52     static_assert((sizeof(*this) % CACHELINE_SIZE) == 0, "xx");
  53   }
  54 } CACHE_ALIGNED;
  55
  56 // some pre-defs
  57 typedef aligned_padded_elem<uint8_t>  aligned_padded_u8;
  58 typedef aligned_padded_elem<uint16_t> aligned_padded_u16;
  59 typedef aligned_padded_elem<uint32_t> aligned_padded_u32;
  60 typedef aligned_padded_elem<uint64_t> aligned_padded_u64;
  61
  62 template <typename T>
  63 struct host_endian_trfm {
  64   inline ALWAYS_INLINE T operator()(const T &t) const { return t; }
  65 };
  66
  67 template <>
  68 struct host_endian_trfm<uint16_t> {
  69   inline ALWAYS_INLINE uint16_t operator()(uint16_t t) const { return be16toh(t); }
  70 };
  71
  72 template <>
  73 struct host_endian_trfm<int16_t> {
  74   inline ALWAYS_INLINE int16_t operator()(int16_t t) const { return be16toh(t); }
  75 };
  76
  77 template <>
  78 struct host_endian_trfm<int32_t> {
  79   inline ALWAYS_INLINE int32_t operator()(int32_t t) const { return be32toh(t); }
  80 };
  81
  82 template <>
  83 struct host_endian_trfm<uint32_t> {
  84   inline ALWAYS_INLINE uint32_t operator()(uint32_t t) const { return be32toh(t); }
  85 };
  86
  87 template <>
  88 struct host_endian_trfm<int64_t> {
  89   inline ALWAYS_INLINE int64_t operator()(int64_t t) const { return be64toh(t); }
  90 };
  91
  92 template <>
  93 struct host_endian_trfm<uint64_t> {
  94   inline ALWAYS_INLINE uint64_t operator()(uint64_t t) const { return be64toh(t); }
  95 };
  96
  97 template <typename T>
  98 struct big_endian_trfm {
  99   inline ALWAYS_INLINE T operator()(const T &t) const { return t; }
 100 };
 101
 102 template <>
 103 struct big_endian_trfm<uint16_t> {
 104   inline ALWAYS_INLINE uint16_t operator()(uint16_t t) const { return htobe16(t); }
 105 };
 106
 107 template <>
 108 struct big_endian_trfm<int16_t> {
 109   inline ALWAYS_INLINE int16_t operator()(int16_t t) const { return htobe16(t); }
 110 };
 111
 112 template <>
 113 struct big_endian_trfm<int32_t> {
 114   inline ALWAYS_INLINE int32_t operator()(int32_t t) const { return htobe32(t); }
 115 };
 116
 117 template <>
 118 struct big_endian_trfm<uint32_t> {
 119   inline ALWAYS_INLINE uint32_t operator()(uint32_t t) const { return htobe32(t); }
 120 };
 121
 122 template <>
 123 struct big_endian_trfm<int64_t> {
 124   inline ALWAYS_INLINE int64_t operator()(int64_t t) const { return htobe64(t); }
 125 };
 126
 127 template <>
 128 struct big_endian_trfm<uint64_t> {
 129   inline ALWAYS_INLINE uint64_t operator()(uint64_t t) const { return htobe64(t); }
 130 };
 131
 132 inline std::string
 133 hexify_buf(const char *buf, size_t len)
 134 {
 135   const char *const lut = "0123456789ABCDEF";
 136   std::string output;
 137   output.reserve(2 * len);
 138   for (size_t i = 0; i < len; ++i) {
 139     const unsigned char c = (unsigned char) buf[i];
 140     output.push_back(lut[c >> 4]);
 141     output.push_back(lut[c & 15]);
 142   }
 143   return output;
 144 }
 145
 146
 147 template <typename T>
 148 inline std::string
 149 hexify(const T &t)
 150 {
 151   std::ostringstream buf;
 152   buf << std::hex << t;
 153   return buf.str();
 154 }
 155
 156 template <>
 157 inline std::string
 158 hexify(const std::string &input)
 159 {
 160   return hexify_buf(input.data(), input.size());
 161 }
 162
 163 template <typename T, unsigned int lgbase>
 164 struct mask_ {
 165   static const T value = ((T(1) << lgbase) - 1);
 166 };
 167
 168 // rounding
 169 template <typename T, unsigned int lgbase>
 170 static constexpr inline ALWAYS_INLINE T
 171 round_up(T t)
 172 {
 173   return (t + mask_<T, lgbase>::value) & ~mask_<T, lgbase>::value;
 174 }
 175
 176 template <typename T, unsigned int lgbase>
 177 static constexpr inline ALWAYS_INLINE T
 178 round_down(T t)
 179 {
 180   return (t & ~mask_<T, lgbase>::value);
 181 }
 182
 183 template <typename T, typename U>
 184 static inline ALWAYS_INLINE T
 185 iceil(T x, U y)
 186 {
 187   U mod = x % y;
 188   return x + (mod ? y - mod : 0);
 189 }
 190
 191 template <typename T>
 192 static inline T
 193 slow_round_up(T x, T q)
 194 {
 195   const T r = x % q;
 196   if (!r)
 197     return x;
 198   return x + (q - r);
 199 }
 200
 201 template <typename T>
 202 static inline T
 203 slow_round_down(T x, T q)
 204 {
 205   const T r = x % q;
 206   if (!r)
 207     return x;
 208   return x - r;
 209 }
 210
 211 // not thread-safe
 212 //
 213 // taken from java:
 214 //   http://developer.classpath.org/doc/java/util/Random-source.html
 215 class fast_random {
 216 public:
 217   fast_random(unsigned long seed)
 218     : seed(0)
 219   {
 220     set_seed0(seed);
 221   }
 222
 223   inline unsigned long
 224   next()
 225   {
 226     return ((unsigned long) next(32) << 32) + next(32);
 227   }
 228
 229   inline uint32_t
 230   next_u32()
 231   {
 232     return next(32);
 233   }
 234
 235   inline uint16_t
 236   next_u16()
 237   {
 238     return next(16);
 239   }
 240
 241   /** [0.0, 1.0) */
 242   inline double
 243   next_uniform()
 244   {
 245     return (((unsigned long) next(26) << 27) + next(27)) / (double) (1L << 53);
 246   }
 247
 248   inline char
 249   next_char()
 250   {
 251     return next(8) % 256;
 252   }
 253
 254   inline char
 255   next_readable_char()
 256   {
 257     static const char readables[] = "0123456789@ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz";
 258     return readables[next(6)];
 259   }
 260
 261   inline std::string
 262   next_string(size_t len)
 263   {
 264     std::string s(len, 0);
 265     for (size_t i = 0; i < len; i++)
 266       s[i] = next_char();
 267     return s;
 268   }
 269
 270   inline std::string
 271   next_readable_string(size_t len)
 272   {
 273     std::string s(len, 0);
 274     for (size_t i = 0; i < len; i++)
 275       s[i] = next_readable_char();
 276     return s;
 277   }
 278
 279   inline unsigned long
 280   get_seed()
 281   {
 282     return seed;
 283   }
 284
 285   inline void
 286   set_seed(unsigned long seed)
 287   {
 288     this->seed = seed;
 289   }
 290
 291 private:
 292   inline void
 293   set_seed0(unsigned long seed)
 294   {
 295     this->seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
 296   }
 297
 298   inline unsigned long
 299   next(unsigned int bits)
 300   {
 301     seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
 302     return (unsigned long) (seed >> (48 - bits));
 303   }
 304
 305   unsigned long seed;
 306 };
 307
 308 template <typename ForwardIterator>
 309 std::string
 310 format_list(ForwardIterator begin, ForwardIterator end)
 311 {
 312   std::ostringstream ss;
 313   ss << "[";
 314   bool first = true;
 315   while (begin != end) {
 316     if (!first)
 317       ss << ", ";
 318     first = false;
 319     ss << *begin++;
 320   }
 321   ss << "]";
 322   return ss.str();
 323 }
 324
 325 /**
 326  * Returns the lowest position p such that p0+p != p1+p.
 327  */
 328 inline size_t
 329 first_pos_diff(const char *p0, size_t sz0,
 330                const char *p1, size_t sz1)
 331 {
 332   const char *p0end = p0 + sz0;
 333   const char *p1end = p1 + sz1;
 334   size_t n = 0;
 335   while (p0 != p0end &&
 336          p1 != p1end &&
 337          p0[n] == p1[n])
 338     n++;
 339   return n;
 340 }
 341
 342 class timer {
 343 private:
 344   timer(const timer &) = delete;
 345   timer &operator=(const timer &) = delete;
 346   timer(timer &&) = delete;
 347
 348 public:
 349   timer()
 350   {
 351     lap();
 352   }
 353
 354   inline uint64_t
 355   lap()
 356   {
 357     uint64_t t0 = start;
 358     uint64_t t1 = cur_usec();
 359     start = t1;
 360     return t1 - t0;
 361   }
 362
 363   inline double
 364   lap_ms()
 365   {
 366     return lap() / 1000.0;
 367   }
 368
 369   static inline uint64_t
 370   cur_usec()
 371   {
 372     struct timeval tv;
 373     gettimeofday(&tv, 0);
 374     return ((uint64_t)tv.tv_sec) * 1000000 + tv.tv_usec;
 375   }
 376
 377 private:
 378
 379   uint64_t start;
 380 };
 381
 382 class scoped_timer {
 383 private:
 384   timer t;
 385   std::string region;
 386   bool enabled;
 387
 388 public:
 389   scoped_timer(const std::string &region, bool enabled = true)
 390     : region(region), enabled(enabled)
 391   {}
 392
 393   ~scoped_timer()
 394   {
 395     if (enabled) {
 396       const double x = t.lap() / 1000.0; // ms
 397       std::cerr << "timed region " << region << " took " << x << " ms" << std::endl;
 398     }
 399   }
 400 };
 401
 402 inline std::string
 403 next_key(const std::string &s)
 404 {
 405   std::string s0(s);
 406   s0.resize(s.size() + 1);
 407   return s0;
 408 }
 409
 410 template <typename T, typename Container = std::vector<T> >
 411 struct std_reverse_pq {
 412   typedef std::priority_queue<T, Container, std::greater<T> > type;
 413 };
 414
 415 template <typename PairType, typename FirstComp>
 416 struct std_pair_first_cmp {
 417   inline bool
 418   operator()(const PairType &lhs, const PairType &rhs) const
 419   {
 420     FirstComp c;
 421     return c(lhs.first, rhs.first);
 422   }
 423 };
 424
 425 // deal with small container opt vectors correctly
 426 template <typename T, size_t SmallSize = SMALL_SIZE_VEC>
 427 struct vec {
 428 #ifdef USE_SMALL_CONTAINER_OPT
 429   typedef small_vector<T, SmallSize> type;
 430 #else
 431   typedef std::vector<T> type;
 432 #endif
 433 };
 434
 435 static inline std::vector<std::string>
 436 split(const std::string &s, char delim)
 437 {
 438   std::vector<std::string> elems;
 439   std::stringstream ss(s);
 440   std::string item;
 441   while (std::getline(ss, item, delim))
 442     elems.emplace_back(item);
 443   return elems;
 444 }
 445
 446 struct default_string_allocator {
 447   inline std::string *
 448   operator()()
 449   {
 450     strs.emplace_back(new std::string);
 451     return strs.back().get();
 452   }
 453   inline void
 454   return_last(std::string *px)
 455   {
 456     // XXX: check px in strs
 457   }
 458 private:
 459   std::vector<std::shared_ptr<std::string>> strs;
 460 };
 461
 462 static constexpr uint64_t
 463 compute_fields_mask()
 464 {
 465   return 0;
 466 }
 467
 468 template <typename First, typename... Rest>
 469 static constexpr uint64_t
 470 compute_fields_mask(First f, Rest... rest)
 471 {
 472   return (1UL << f) | compute_fields_mask(rest...);
 473 }
 474
 475 template <uint64_t Mask>
 476 struct Fields {
 477   static const uint64_t value = Mask;
 478 };
 479
 480 #define FIELDS(args...) \
 481   ::util::Fields< ::util::compute_fields_mask(args) >()
 482
 483 #ifdef DISABLE_FIELD_SELECTION
 484 #define GUARDED_FIELDS(args...) \
 485   ::util::Fields< ::std::numeric_limits<uint64_t>::max() >()
 486 #else
 487 #define GUARDED_FIELDS(args...) FIELDS(args)
 488 #endif
 489
 490 template <typename T>
 491 struct cxx_typename {
 492   static std::string
 493   value()
 494   {
 495     int st;
 496     char *name = abi::__cxa_demangle(typeid(T).name(), nullptr, nullptr, &st);
 497     if (unlikely(st))
 498       return std::string(typeid(T).name()) + "<demangle failed>";
 499     std::string ret(name);
 500     free(name);
 501     return ret;
 502   }
 503 };
 504
 505 // returns a vector of [start, ..., end)
 506 template <typename T>
 507 static std::vector<T>
 508 MakeRange(T start, T end)
 509 {
 510   std::vector<T> ret;
 511   for (T i = start; i < end; i++)
 512     ret.push_back(i);
 513   return ret;
 514 }
 515
 516 struct timespec_utils {
 517         // thanks austin
 518         static void
 519         subtract(const struct timespec *x,
 520                                          const struct timespec *y,
 521                                          struct timespec *out)
 522         {
 523                 // Perform the carry for the later subtraction by updating y.
 524                 struct timespec y2 = *y;
 525                 if (x->tv_nsec < y2.tv_nsec) {
 526                         int sec = (y2.tv_nsec - x->tv_nsec) / 1e9 + 1;
 527                         y2.tv_nsec -= 1e9 * sec;
 528                         y2.tv_sec += sec;
 529                 }
 530                 if (x->tv_nsec - y2.tv_nsec > 1e9) {
 531                         int sec = (x->tv_nsec - y2.tv_nsec) / 1e9;
 532                         y2.tv_nsec += 1e9 * sec;
 533                         y2.tv_sec -= sec;
 534                 }
 535
 536                 // Compute the time remaining to wait.  tv_nsec is certainly
 537                 // positive.
 538                 out->tv_sec  = x->tv_sec - y2.tv_sec;
 539                 out->tv_nsec = x->tv_nsec - y2.tv_nsec;
 540         }
 541 };
 542
 543 template <typename T>
 544 struct RangeAwareParser {
 545   inline std::vector<T>
 546   operator()(const std::string &s) const
 547   {
 548     std::vector<T> ret;
 549     if (s.find('-') == std::string::npos) {
 550       T t;
 551       std::istringstream iss(s);
 552       iss >> t;
 553       ret.emplace_back(t);
 554     } else {
 555       std::vector<std::string> toks(split(s, '-'));
 556       ALWAYS_ASSERT(toks.size() == 2);
 557       T t0, t1;
 558       std::istringstream iss0(toks[0]), iss1(toks[1]);
 559       iss0 >> t0;
 560       iss1 >> t1;
 561       for (T t = t0; t <= t1; t++)
 562         ret.emplace_back(t);
 563     }
 564     return ret;
 565   }
 566 };
 567
 568 template <typename T, typename Parser>
 569 static std::vector<T>
 570 ParseCSVString(const std::string &s, Parser p = Parser())
 571 {
 572   std::vector<T> ret;
 573   std::vector<std::string> toks(split(s, ','));
 574   for (auto &s : toks) {
 575     auto values = p(s);
 576     ret.insert(ret.end(), values.begin(), values.end());
 577   }
 578   return ret;
 579 }
 580
 581 template <typename T>
 582 static inline T
 583 non_atomic_fetch_add(std::atomic<T> &data, T arg)
 584 {
 585   const T ret = data.load(std::memory_order_acquire);
 586   data.store(ret + arg, std::memory_order_release);
 587   return ret;
 588 }
 589
 590 template <typename T>
 591 static inline T
 592 non_atomic_fetch_sub(std::atomic<T> &data, T arg)
 593 {
 594   const T ret = data.load(std::memory_order_acquire);
 595   data.store(ret - arg, std::memory_order_release);
 596   return ret;
 597 }
 598
 599 static inline std::string
 600 to_lower(const std::string &s)
 601 {
 602   std::string ret(s);
 603   std::transform(ret.begin(), ret.end(), ret.begin(), ::tolower);
 604   return ret;
 605 }
 606
 607 } // namespace util
 608
 609 // pretty printer for std::pair<A, B>
 610 template <typename A, typename B>
 611 inline std::ostream &
 612 operator<<(std::ostream &o, const std::pair<A, B> &p)
 613 {
 614   o << "[" << p.first << ", " << p.second << "]";
 615   return o;
 616 }
 617
 618 // pretty printer for std::vector<T, Alloc>
 619 template <typename T, typename Alloc>
 620 static std::ostream &
 621 operator<<(std::ostream &o, const std::vector<T, Alloc> &v)
 622 {
 623   bool first = true;
 624   o << "[";
 625   for (auto &p : v) {
 626     if (!first)
 627       o << ", ";
 628     first = false;
 629     o << p;
 630   }
 631   o << "]";
 632   return o;
 633 }
 634
 635 // pretty printer for std::tuple<...>
 636 namespace private_ {
 637   template <size_t Idx, bool Enable, class... Types>
 638   struct helper {
 639     static inline void
 640     apply(std::ostream &o, const std::tuple<Types...> &t)
 641     {
 642       if (Idx)
 643         o << ", ";
 644       o << std::get<Idx, Types...>(t);
 645       helper<Idx + 1,
 646              (Idx + 1) < std::tuple_size<std::tuple<Types...>>::value,
 647              Types...>::apply(o, t);
 648     }
 649   };
 650
 651   template <size_t Idx, class... Types>
 652   struct helper<Idx, false, Types...> {
 653     static inline void
 654     apply(std::ostream &o, const std::tuple<Types...> &t)
 655     {
 656     }
 657   };
 658 }
 659
 660 template <class... Types>
 661 static inline std::ostream &
 662 operator<<(std::ostream &o, const std::tuple<Types...> &t)
 663 {
 664   o << "[";
 665   private_::helper<0, 0 < std::tuple_size<std::tuple<Types...>>::value, Types...>::apply(o, t);
 666   o << "]";
 667   return o;
 668 }
 669
 670 // XXX: so nasty, but some things we want to explictly call their dtors we do
 671 // this anti-pattern all over the code base, might as well centralize it here
 672 template <typename T>
 673 class unmanaged {
 674 public:
 675   template <class... Args>
 676   unmanaged(Args &&... args)
 677 #ifdef CHECK_INVARIANTS
 678     : destroyed_(false)
 679 #endif
 680   {
 681     new (&obj_[0]) T(std::forward<Args>(args)...);
 682   }
 683
 684   // up to you to call this at most once
 685   inline void
 686   destroy()
 687   {
 688 #ifdef CHECK_INVARIANTS
 689     ALWAYS_ASSERT(!destroyed_);
 690     destroyed_ = true;
 691 #endif
 692     obj()->~T();
 693   }
 694
 695   inline T * obj() { return (T *) &obj_[0]; }
 696   inline const T * obj() const { return (const T *) &obj_[0]; }
 697
 698   // syntatic sugar
 699
 700   inline T & operator*() { return *obj(); }
 701   inline const T & operator*() const { return *obj(); }
 702   inline T * operator->() { return obj(); }
 703   inline const T * operator->() const { return obj(); }
 704
 705 private:
 706   char obj_[sizeof(T)];
 707 #ifdef CHECK_INVARIANTS
 708   bool destroyed_;
 709 #endif
 710 } PACKED;
 711
 712 #endif /* _UTIL_H_ */