22 #include "small_vector.h"
26 // padded, aligned primitives
27 template <typename T, bool Pedantic = true>
28 class aligned_padded_elem {
31 template <class... Args>
32 aligned_padded_elem(Args &&... args)
33 : elem(std::forward<Args>(args)...)
36 ALWAYS_ASSERT(((uintptr_t)this % CACHELINE_SIZE) == 0);
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; }
52 static_assert((sizeof(*this) % CACHELINE_SIZE) == 0, "xx");
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;
63 struct host_endian_trfm {
64 inline ALWAYS_INLINE T operator()(const T &t) const { return t; }
68 struct host_endian_trfm<uint16_t> {
69 inline ALWAYS_INLINE uint16_t operator()(uint16_t t) const { return be16toh(t); }
73 struct host_endian_trfm<int16_t> {
74 inline ALWAYS_INLINE int16_t operator()(int16_t t) const { return be16toh(t); }
78 struct host_endian_trfm<int32_t> {
79 inline ALWAYS_INLINE int32_t operator()(int32_t t) const { return be32toh(t); }
83 struct host_endian_trfm<uint32_t> {
84 inline ALWAYS_INLINE uint32_t operator()(uint32_t t) const { return be32toh(t); }
88 struct host_endian_trfm<int64_t> {
89 inline ALWAYS_INLINE int64_t operator()(int64_t t) const { return be64toh(t); }
93 struct host_endian_trfm<uint64_t> {
94 inline ALWAYS_INLINE uint64_t operator()(uint64_t t) const { return be64toh(t); }
98 struct big_endian_trfm {
99 inline ALWAYS_INLINE T operator()(const T &t) const { return t; }
103 struct big_endian_trfm<uint16_t> {
104 inline ALWAYS_INLINE uint16_t operator()(uint16_t t) const { return htobe16(t); }
108 struct big_endian_trfm<int16_t> {
109 inline ALWAYS_INLINE int16_t operator()(int16_t t) const { return htobe16(t); }
113 struct big_endian_trfm<int32_t> {
114 inline ALWAYS_INLINE int32_t operator()(int32_t t) const { return htobe32(t); }
118 struct big_endian_trfm<uint32_t> {
119 inline ALWAYS_INLINE uint32_t operator()(uint32_t t) const { return htobe32(t); }
123 struct big_endian_trfm<int64_t> {
124 inline ALWAYS_INLINE int64_t operator()(int64_t t) const { return htobe64(t); }
128 struct big_endian_trfm<uint64_t> {
129 inline ALWAYS_INLINE uint64_t operator()(uint64_t t) const { return htobe64(t); }
133 hexify_buf(const char *buf, size_t len)
135 const char *const lut = "0123456789ABCDEF";
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]);
147 template <typename T>
151 std::ostringstream buf;
152 buf << std::hex << t;
158 hexify(const std::string &input)
160 return hexify_buf(input.data(), input.size());
163 template <typename T, unsigned int lgbase>
165 static const T value = ((T(1) << lgbase) - 1);
169 template <typename T, unsigned int lgbase>
170 static constexpr inline ALWAYS_INLINE T
173 return (t + mask_<T, lgbase>::value) & ~mask_<T, lgbase>::value;
176 template <typename T, unsigned int lgbase>
177 static constexpr inline ALWAYS_INLINE T
180 return (t & ~mask_<T, lgbase>::value);
183 template <typename T, typename U>
184 static inline ALWAYS_INLINE T
188 return x + (mod ? y - mod : 0);
191 template <typename T>
193 slow_round_up(T x, T q)
201 template <typename T>
203 slow_round_down(T x, T q)
214 // http://developer.classpath.org/doc/java/util/Random-source.html
217 fast_random(unsigned long seed)
226 return ((unsigned long) next(32) << 32) + next(32);
245 return (((unsigned long) next(26) << 27) + next(27)) / (double) (1L << 53);
251 return next(8) % 256;
257 static const char readables[] = "0123456789@ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz";
258 return readables[next(6)];
262 next_string(size_t len)
264 std::string s(len, 0);
265 for (size_t i = 0; i < len; i++)
271 next_readable_string(size_t len)
273 std::string s(len, 0);
274 for (size_t i = 0; i < len; i++)
275 s[i] = next_readable_char();
286 set_seed(unsigned long seed)
293 set_seed0(unsigned long seed)
295 this->seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
299 next(unsigned int bits)
301 seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
302 return (unsigned long) (seed >> (48 - bits));
308 template <typename ForwardIterator>
310 format_list(ForwardIterator begin, ForwardIterator end)
312 std::ostringstream ss;
315 while (begin != end) {
326 * Returns the lowest position p such that p0+p != p1+p.
329 first_pos_diff(const char *p0, size_t sz0,
330 const char *p1, size_t sz1)
332 const char *p0end = p0 + sz0;
333 const char *p1end = p1 + sz1;
335 while (p0 != p0end &&
344 timer(const timer &) = delete;
345 timer &operator=(const timer &) = delete;
346 timer(timer &&) = delete;
358 uint64_t t1 = cur_usec();
366 return lap() / 1000.0;
369 static inline uint64_t
373 gettimeofday(&tv, 0);
374 return ((uint64_t)tv.tv_sec) * 1000000 + tv.tv_usec;
389 scoped_timer(const std::string ®ion, bool enabled = true)
390 : region(region), enabled(enabled)
396 const double x = t.lap() / 1000.0; // ms
397 std::cerr << "timed region " << region << " took " << x << " ms" << std::endl;
403 next_key(const std::string &s)
406 s0.resize(s.size() + 1);
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;
415 template <typename PairType, typename FirstComp>
416 struct std_pair_first_cmp {
418 operator()(const PairType &lhs, const PairType &rhs) const
421 return c(lhs.first, rhs.first);
425 // deal with small container opt vectors correctly
426 template <typename T, size_t SmallSize = SMALL_SIZE_VEC>
428 #ifdef USE_SMALL_CONTAINER_OPT
429 typedef small_vector<T, SmallSize> type;
431 typedef std::vector<T> type;
435 static inline std::vector<std::string>
436 split(const std::string &s, char delim)
438 std::vector<std::string> elems;
439 std::stringstream ss(s);
441 while (std::getline(ss, item, delim))
442 elems.emplace_back(item);
446 struct default_string_allocator {
450 strs.emplace_back(new std::string);
451 return strs.back().get();
454 return_last(std::string *px)
456 // XXX: check px in strs
459 std::vector<std::shared_ptr<std::string>> strs;
462 static constexpr uint64_t
463 compute_fields_mask()
468 template <typename First, typename... Rest>
469 static constexpr uint64_t
470 compute_fields_mask(First f, Rest... rest)
472 return (1UL << f) | compute_fields_mask(rest...);
475 template <uint64_t Mask>
477 static const uint64_t value = Mask;
480 #define FIELDS(args...) \
481 ::util::Fields< ::util::compute_fields_mask(args) >()
483 #ifdef DISABLE_FIELD_SELECTION
484 #define GUARDED_FIELDS(args...) \
485 ::util::Fields< ::std::numeric_limits<uint64_t>::max() >()
487 #define GUARDED_FIELDS(args...) FIELDS(args)
490 template <typename T>
491 struct cxx_typename {
496 char *name = abi::__cxa_demangle(typeid(T).name(), nullptr, nullptr, &st);
498 return std::string(typeid(T).name()) + "<demangle failed>";
499 std::string ret(name);
505 // returns a vector of [start, ..., end)
506 template <typename T>
507 static std::vector<T>
508 MakeRange(T start, T end)
511 for (T i = start; i < end; i++)
516 struct timespec_utils {
519 subtract(const struct timespec *x,
520 const struct timespec *y,
521 struct timespec *out)
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;
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;
536 // Compute the time remaining to wait. tv_nsec is certainly
538 out->tv_sec = x->tv_sec - y2.tv_sec;
539 out->tv_nsec = x->tv_nsec - y2.tv_nsec;
543 template <typename T>
544 struct RangeAwareParser {
545 inline std::vector<T>
546 operator()(const std::string &s) const
549 if (s.find('-') == std::string::npos) {
551 std::istringstream iss(s);
555 std::vector<std::string> toks(split(s, '-'));
556 ALWAYS_ASSERT(toks.size() == 2);
558 std::istringstream iss0(toks[0]), iss1(toks[1]);
561 for (T t = t0; t <= t1; t++)
568 template <typename T, typename Parser>
569 static std::vector<T>
570 ParseCSVString(const std::string &s, Parser p = Parser())
573 std::vector<std::string> toks(split(s, ','));
574 for (auto &s : toks) {
576 ret.insert(ret.end(), values.begin(), values.end());
581 template <typename T>
583 non_atomic_fetch_add(std::atomic<T> &data, T arg)
585 const T ret = data.load(std::memory_order_acquire);
586 data.store(ret + arg, std::memory_order_release);
590 template <typename T>
592 non_atomic_fetch_sub(std::atomic<T> &data, T arg)
594 const T ret = data.load(std::memory_order_acquire);
595 data.store(ret - arg, std::memory_order_release);
599 static inline std::string
600 to_lower(const std::string &s)
603 std::transform(ret.begin(), ret.end(), ret.begin(), ::tolower);
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)
614 o << "[" << p.first << ", " << p.second << "]";
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)
635 // pretty printer for std::tuple<...>
637 template <size_t Idx, bool Enable, class... Types>
640 apply(std::ostream &o, const std::tuple<Types...> &t)
644 o << std::get<Idx, Types...>(t);
646 (Idx + 1) < std::tuple_size<std::tuple<Types...>>::value,
647 Types...>::apply(o, t);
651 template <size_t Idx, class... Types>
652 struct helper<Idx, false, Types...> {
654 apply(std::ostream &o, const std::tuple<Types...> &t)
660 template <class... Types>
661 static inline std::ostream &
662 operator<<(std::ostream &o, const std::tuple<Types...> &t)
665 private_::helper<0, 0 < std::tuple_size<std::tuple<Types...>>::value, Types...>::apply(o, t);
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>
675 template <class... Args>
676 unmanaged(Args &&... args)
677 #ifdef CHECK_INVARIANTS
681 new (&obj_[0]) T(std::forward<Args>(args)...);
684 // up to you to call this at most once
688 #ifdef CHECK_INVARIANTS
689 ALWAYS_ASSERT(!destroyed_);
695 inline T * obj() { return (T *) &obj_[0]; }
696 inline const T * obj() const { return (const T *) &obj_[0]; }
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(); }
706 char obj_[sizeof(T)];
707 #ifdef CHECK_INVARIANTS
712 #endif /* _UTIL_H_ */