Calculation of an LRU index (from 0-8) using bitwise instructions based on Hacker's Delight.

LruCache.hpp

#ifdef _MSC_VER
    #include <intrin.h> // _BitScanForward
#endif

#include <cassert>
#include <cstdint>



class LruCache
{
  private:
    static unsigned _count_trailing_zero_bits(const uint64_t) noexcept;

    static unsigned _calc_zero_byte_index(const uint64_t) noexcept;

  public:
    ~LruCache() = default;

    constexpr LruCache() noexcept;

    LruCache(const LruCache&) noexcept = default;
    LruCache(LruCache&&) noexcept = default;
    LruCache& operator=(const LruCache&) noexcept = default;
    LruCache& operator=(LruCache&&) noexcept = default;

    void update(unsigned key) noexcept;

    unsigned value(unsigned i) const noexcept;

    unsigned least_used_index() const noexcept;

  private:
    union
    {
        uint8_t mRows[8];
        uint64_t mCols;
    };
};



inline unsigned LruCache::_count_trailing_zero_bits(const uint64_t n) noexcept
{
    #if defined(__GNUC__)
        return (unsigned)__builtin_ctzll(n);

    #elif defined(_MSC_VER)
        unsigned long ret;
        #ifdef _WIN64
            return (_BitScanForward64(&ret, (unsigned long long)n) ? (unsigned)ret : 64u);
        #else
            return (_BitScanForward(&ret, (unsigned long)n) ? (unsigned)ret : 64u);
        #endif

    #else
        unsigned ret = 0ull;
        while (!(n & 1ull))
        {
            n >>= 1ull;
            ++ret;
        }
        return ret;

    #endif
}



inline unsigned LruCache::_calc_zero_byte_index(const uint64_t x) noexcept
{
    const uint64_t y = (x-0x0101010101010101ull) & ~x & 0x8080808080808080ull;
    return LruCache::_count_trailing_zero_bits(y) >> 3;
}



constexpr LruCache::LruCache() noexcept :
    mCols{0ull}
{}



inline void LruCache::update(unsigned key) noexcept
{
    assert(key < 8);
    mRows[key] = 0xFF;
    mCols &= ~(0x0101010101010101ull << key);
}



inline unsigned LruCache::value(unsigned i) const noexcept
{
    assert(key < 8);
    return (unsigned)mRows[i];
}



inline unsigned LruCache::least_used_index() const noexcept
{
    return LruCache::_calc_zero_byte_index(mCols);
}

main.cpp

#include <iostream>

#include "LruCache.hpp"



std::ostream& operator << (std::ostream& ostr, const LruCache& lru)
{
    for (unsigned i = 0; i < 8; ++i)
    {
        ostr << lru.value(i) << std::endl;
    }

    return ostr;
}



int main()
{
    LruCache lru{};

    lru.update(0);
    lru.update(2);
    lru.update(1);
    lru.update(4);
    lru.update(3);
    lru.update(6);
    lru.update(5);
    lru.update(7);
    lru.update(3);
    lru.update(0);
    lru.update(2);
    lru.update(1);

    std::cout
        << "LRU Id: " << lru.least_used_index() << ' ' << lru.value(lru.least_used_index()) << '\n'
        << lru
        << std::endl;

    return 0;
}