1
\$\begingroup\$

This creates something like constexpr mar<String, T> using C++14.

Collision resolution is with static_assert and manually increase of hashtable buckets.

I do not store keys inside the hashtable, so I can get wrong results for a non-existent key. However, for my use case, this is OK.

#include <cstdint>

#include <initializer_list>

template<typename T, uint32_t SIZE, T ZERO = T(0)>
class StringTable{
public:
    using size_type = uint32_t;

    struct Pair{
        const char  *key;
        T       value;
    };

    constexpr StringTable(const std::initializer_list<Pair>& list){
        for (auto &x : values)
            x = ZERO;

        for(const Pair &p : list)
            push_(p.key, p.value);
    }

    constexpr bool collisions() const{
        return collisions_;
    }

    constexpr const T &operator[](const char *key) const{
        auto const bucket = bucket__(key);

        return values[bucket];
    }

private:
    constexpr void push_(const char *key, const T &value){
        auto const bucket = bucket__(key);

        auto &element = values[bucket];

        if (element != ZERO)
            collisions_ = true;

        element = value;
    }

    constexpr static size_type bucket__(const char *key){
        return hash__(key) % SIZE;
    }

private:
    constexpr static size_type hash__(const char* str){
        size_type hash = 5381;

        for(auto it = str; *it; ++it)
            hash = ((hash << 5) + hash) + (*it);

        return hash;
    }

private:
    bool    collisions_ = false;
    T   values[SIZE]    = {};
};

#include <iostream>

int main(int argc, char **argv){
    enum class Commands : char{
        NONE    ,
        GET ,
        SET ,
        SETEX   ,
        SAVE
    };

    constexpr uint32_t BUCKETS = 21;

    using CmdTable = StringTable<Commands, BUCKETS, Commands::NONE>;
    using Pair  = CmdTable::Pair;

    constexpr CmdTable table{ {
        Pair{ "get",    Commands::GET   },
        Pair{ "set",    Commands::SET   },
        Pair{ "setex",  Commands::SETEX },
        Pair{ "save",   Commands::SAVE  },
        Pair{ "bgsave", Commands::SAVE  }
    } };

    static_assert( ! table.collisions() );

    static_assert( table["save"] == Commands::SAVE );
    static_assert( table["bala"] == Commands::NONE );

    return int( table[ argv[1] ] );
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.