Skip to content

Instantly share code, notes, and snippets.

@elder-george

elder-george/oa_map.cpp

Created October 17, 2021 20:57
Download ZIP

Revisions

  1. elder-george created this gist Oct 17, 2021.
    35 changes: 35 additions & 0 deletions oa_map.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,35 @@
    struct oa_map {
    using Store = std::vector<std::tuple<size_t, std::string, uint32_t>>;
    using iterator = Store::iterator;
    Store _store{1024};

    std::pair<iterator, bool> try_emplace(std::string&& s, uint32_t v) {
    auto full_h = std::hash<std::string>{}(s);
    return try_emplace(full_h, std::move(s), v);
    }

    std::pair<iterator, bool> try_emplace(size_t full_h, std::string&& s, uint32_t v) {
    auto h = full_h % _store.size();

    for(auto it = _store.begin() + h; ; ++it) {
    if (std::get<std::string>(*it).empty()) {
    *it = {full_h, s, v};
    return {it, true};
    }
    else if (std::get<std::string>(*it) == s) {
    return {it, false};
    }
    else if (it + 1 == _store.end()) {
    // hackish resize
    _store.resize(_store.size() * 2);
    // re-place existing values
    for (auto i = 0; i < _store.size() / 2; ++i) {
    auto [hash, key, value] = std::move(_store[i]);
    try_emplace(hash, std::move(key), value);
    }
    // this time it'll succeed, right? RIGHT?
    return try_emplace(full_h, std::move(s), v);
    }
    }
    }
    };