Util.hh

#ifndef BITUNWISE_UTIL_H
#define BITUNWISE_UTIL_H

#include <cstdlib>
#include <iostream>
#include <functional>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stdint.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/times.h>

/** The expression is very likely to be true */
#define LIKELY(exp) __builtin_expect(!!(exp), 1)
/** The expression is very unlikely to be true */
#define UNLIKELY(exp) __builtin_expect(!!(exp), 0)

#ifdef WMOST_ASSURED
#define MOST_LIKELY(exp) 1
#define MOST_UNLIKELY(exp) 0
#else
#define MOST_LIKELY LIKELY
#define MOST_UNLIKELY UNLIKELY
#endif

#define NOINLINE __attribute__((noinline))
#define FINLINE __attribute__((always_inline))

#define NOTICE(err) std::cout << "[NOTICE] " << err << std::endl
#define ERROR(err) std::cout << "[ERROR] " << err << std::endl
#ifdef NO_CXX11
#define FATAL(err) do {std::cout << "[FATAL] " << err << std::endl;asm("int3");/*std::exit(2);*/} while(0)
#else
#define FATAL(err) do {std::cout << "[FATAL] " << err << std::endl;if(U::onFatal)U::onFatal();asm("int3");/*std::exit(2);*/} while(0)
#endif

#define __TRACER__(...) U::Tracer _tracer(__VA_ARGS__)
#define __TRACE__(...) __TRACER__(__PRETTY_FUNCTION__, __VA_ARGS__)
#define __TRACE0__ __TRACER__(__PRETTY_FUNCTION__)
#define TRACE_TABS(x) (U::Tracer::m_pCurrent ? U::Tracer::m_pCurrent->tabs(x) : x)

#if defined(WTRACE)

#ifdef NO_CXX11
#error "You don't have full C++0x/C++11 support, you can't use WTRACE for tracing"
#endif

#define TRACER(...) __TRACER__(__VA_ARGS__)
#define TRACE0 __TRACE0__
#define TRACE(...) __TRACE__(__VA_ARGS__)
#define TRACET0 __TRACE__(this)
#define TRACET(...) __TRACE__(this, __VA_ARGS__)

#else

#define TRACER(...)
#define TRACE0
#define TRACE(...)
#define TRACET0
#define TRACET(...)

#endif

#define TIMER(x) U::Timer _timer_ ## x(#x)

#ifdef NO_CXX11
#define BITUNWISE_STATIC template <uint8_t nBitsPtr, uint64_t nDeps> typename U::Bit<nBitsPtr, nDeps>::Manager U::Bit<nBitsPtr, nDeps>::m_Manager
#else
#define BITUNWISE_STATIC \
U::Tracer *U::Tracer::m_pCurrent = 0;\
size_t U::Tracer::m_nDepth = 0;\
std::function<void()> U::onFatal;\
template <uint8_t nBitsPtr, uint64_t nDeps> typename U::Bit<nBitsPtr, nDeps>::Manager U::Bit<nBitsPtr, nDeps>::m_Manager
#endif

#define BITUNWISE_ALIAS(to, from) template <typename... T> using to = from<T...>;

namespace U {
#ifndef NO_CXX11
    extern std::function<void()> onFatal;
#endif
    
    BITUNWISE_ALIAS(Pair, std::pair);
    BITUNWISE_ALIAS(Set, std::set);
    BITUNWISE_ALIAS(Map, std::map);
    BITUNWISE_ALIAS(HashSet, std::unordered_set);
    BITUNWISE_ALIAS(HashMap, std::unordered_map);
    
    //BEGIN Tracer
#ifndef NO_CXX11
    struct Tracer {
        template<typename... Args>
        Tracer(std::string sFunc, const Args&... args) : m_pChilds(false) {
            tabs(std::cout);
            sFunc.erase(sFunc.find('('));
            std::cout << u8"╞>" << sFunc << '(';
            printArgs(args...);
            std::cout << ')' << std::endl;
                
            m_nDepth++;
            if(m_pCurrent)
                m_pCurrent->m_pChilds = true;
            m_pPrev = m_pCurrent;
            m_pCurrent = this;
        }
        
        ~Tracer() {
            m_nDepth--;
            if(m_pChilds) {
                tabs(std::cout);
                std::cout << u8"├┘" << std::endl;
            }
            
            m_pCurrent = m_pPrev;
        }
        
        void printArgs() {}
        template<typename T, typename... Args>
        void printArgs(T&, Args&...);
        
        std::ostream &tabs(std::ostream &os) {
            os << "[TRACE] ";
            for(size_t i = 0; i < m_nDepth; i++)
                os << u8"│";
            return os;
        }
        
        bool m_pChilds;
        Tracer *m_pPrev;
        
        static size_t m_nDepth;
        static Tracer *m_pCurrent;
    };
#endif
    //END Tracer
    
    //BEGIN Timer
    struct Timer {
        Timer(const char *sTimer) : m_sTimer(sTimer) {
            rusage tm;
            getrusage(RUSAGE_SELF, &tm);
            m_nStart = tm.ru_utime.tv_sec*1000000+tm.ru_utime.tv_usec;
        }
        
        ~Timer() {
            rusage tm;
            getrusage(RUSAGE_SELF, &tm);
            double nUserTime = (tm.ru_utime.tv_sec*1000000+tm.ru_utime.tv_usec)-m_nStart;
            std::cout.setf(std::ios::fixed, std::ios::floatfield);
            std::cout << "[TIMER] " << m_sTimer << '=' << (nUserTime / 1000) << "ms" << std::endl;
            std::cout.setf(std::ios::fmtflags(0), std::ios::floatfield);
        }
        
        double m_nStart;
        
        const char *m_sTimer;
    };
    //END Timer
    
    //BEGIN Helpers
    template <uint8_t> struct IntHelper {typedef void type;};
    template <> struct IntHelper<8> {typedef uint8_t type;};
    template <> struct IntHelper<16> {typedef uint16_t type;};
    template <> struct IntHelper<32> {typedef uint32_t type;};
    template <> struct IntHelper<64> {typedef uint64_t type;};
    
#ifdef NO_CXX11
    template <uint64_t N>
    struct ApproxIntSize {
        enum {value = N > 32 ? 64 : (N > 16 ? 32 : (N > 8 ? 16 : 8))};
    };
#define INT_APPROX(N) typename IntHelper<ApproxIntSize<N>::value>::type
#else
    constexpr uint8_t approxIntSize(uint64_t N) {
        return N > 32 ? 64 : (N > 16 ? 32 : (N > 8 ? 16 : 8));
    }
#define INT_APPROX(N) typename IntHelper<approxIntSize(N)>::type
#endif
    
    /*template <size_t nBits, typename T>
    FINLINE bool atMostOneBit(T x) {
        if(!x)
            return true;
        for(size_t i = 0; i < nBits; i++, x >>= 1)
            if(x & 1)
                return x == 1;
        return false;
    }*/
    constexpr uint64_t bitMask64(size_t n) {
        return (n >= 64 ? 0 : (1ULL << (n % 64))) - 1ULL;
    }
    
    template <size_t nBits=32>
    size_t bitCount(uint32_t x) {
        return __builtin_popcountl(nBits >= 32 ? x : (x & ((1UL << (nBits % 32)) - 1UL)));
    }
    template <size_t nBits=64>
    size_t bitCount(uint64_t x) {
        return __builtin_popcountll(nBits >= 64 ? x : (x & ((1ULL << (nBits % 64)) - 1ULL)));
    }
    template <size_t nBits, typename T>
    size_t bitCount(T x) {
        return nBits <= 32 ? bitCount<nBits>(uint32_t(x)) : bitCount<nBits>(uint64_t(x));
    }
    
    template <size_t N, typename T, bool bDtors=false>
    struct MemArray {
        enum {
            TotalSize = N * sizeof(T)
        };
        MemArray() : array_(static_cast<T*>(mmap(0, TotalSize, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS | MAP_NORESERVE, -1, 0))), refCount_(*(new size_t)) {
            if(MOST_UNLIKELY(!array_))
                FATAL("MemArray allocation failed");
            refCount_ = 1;
        }
        MemArray(const MemArray &that) : array_(that.array_), refCount_(that.refCount_) {
            if(LIKELY(array_))
                refCount_++;
        }
        MemArray(MemArray &&that) : array_(that.array_), refCount_(that.refCount_) {
            that.array_ = 0;
        }
        
        ~MemArray() {
            free();
        }
        void free() {
            if(LIKELY(array_) && LIKELY(!--refCount_)) {
                if(bDtors) {
                    size_t pageSize = sysconf(_SC_PAGESIZE), nPages = (TotalSize+pageSize-1) / pageSize;
                    uint8_t v[nPages];
                    mincore(array_, TotalSize, v);
                    uintptr_t lastEnd = 0;
                    for(size_t i = 0; i < nPages; i++) {
                        if(!(v[i] & 1))
                            continue;
                        uintptr_t start = i*pageSize, end = start + pageSize + sizeof(T) - 1;
                        start = (start - start%sizeof(T)), end = (end - end%sizeof(T));
                        (start < lastEnd) && (start = lastEnd);
                        lastEnd = end;
                        (end > TotalSize) && (end = TotalSize);
                        start += reinterpret_cast<uintptr_t>(array_), end += reinterpret_cast<uintptr_t>(array_);
                        for(T *j = reinterpret_cast<T*>(start); j != reinterpret_cast<T*>(end); j++)
                            j->~T();
                    }
                                
                }
                munmap(array_, TotalSize), array_ = 0;
                delete &refCount_;
            }
        }
        
        const MemArray &operator=(const MemArray &that) {
            if(UNLIKELY(!that.array_)) {
                free();
                return *this;
            }
            that.refCount_++;
            free();
            array_ = that.array_;
            refCount_ = that.refCount_;
            return *this;
        }
        const MemArray &operator=(MemArray &&that) {
            if(UNLIKELY(!that.array_)) {
                free();
                return *this;
            }
            free();
            array_ = that.array_;
            refCount_ = that.refCount_;
            that.array_ = 0;
            return *this;
        }
        
        FINLINE T &operator[](size_t i) {
            return array_[i];
        }
        
        T *array_;
        size_t &refCount_;
    };
    //END Helpers
    
#ifndef NO_CXX11
    //BEGIN TracerPrint
    
    /*template<typename T>
    void printArg(T x) {
        std::cout << x;
    }*/
    
    void printArg(uint64_t x) {
        std::cout << x << "ull";
    }
    void printArg(int64_t x) {
        std::cout << x << "ll";
    }
    void printArg(uint32_t x) {
        std::cout << x << "ul";
    }
    void printArg(int32_t x) {
        std::cout << x << "l";
    }
    void printArg(bool x) {
        std::cout << (x ? "true" : "false");
    }
    void printArg(char x) {
        std::cout << '\'' << x << '\'';
    }
    void printArg(const char *x) {
        std::cout << x;
    }
    template<typename T, typename... Args>
    void Tracer::printArgs(T &x, Args&... args) {
        printArg(x);
        if(sizeof...(args))
            std::cout << ", ";
        printArgs(args...);
    }
    //END TracerPrint
#endif
    
}

#endif