hvec_set.h

/*
 * SPDX-FileCopyrightText: 2023 Intel
 * Copyright 2023-present Intel
 *
 * SPDX-License-Identifier: Apache-2.0
 */
 
#ifndef LIB_HVEC_SET_H_
#define LIB_HVEC_SET_H_
 
#include <initializer_list>
#include <tuple>
#include <vector>
 
#include "exceptions.h"
#include "hashvec.h"
 
namespace P4 {
 
template <class KEY, class HASH = std::hash<KEY>, class PRED = std::equal_to<KEY>,
          class ALLOC = std::allocator<KEY>>
class hvec_set : hash_vector_base {
    HASH hf;  // FIXME -- use empty base optimization for these?
    PRED eql;
 
 public:
    typedef const KEY value_type;
    typedef HASH hasher;
    typedef PRED key_equal;
    typedef ALLOC allocator_type;
    typedef value_type *pointer, *const_pointer, &reference, &const_reference;
    typedef hash_vector_base::lookup_cache lookup_cache;
 
    explicit hvec_set(size_t icap = 0, const hasher &hf = hasher(),
                      const key_equal &eql = key_equal(),
                      const allocator_type &a = allocator_type())
        : hash_vector_base(false, false, icap), hf(hf), eql(eql), data(a) {
        data.reserve(icap);
    }
    hvec_set(const hvec_set &) = default;
    hvec_set(hvec_set &&) = default;
    hvec_set &operator=(const hvec_set &that) {
        if (this != std::addressof(that)) {
            clear();
            hf = that.hf;
            eql = that.eql;
 
            data.reserve(that.size());
            insert(that.begin(), that.end());
        }
 
        return *this;
    }
    hvec_set &operator=(hvec_set &&) = default;
    ~hvec_set() = default;
    template <class ITER>
    hvec_set(ITER begin, ITER end, const hasher &hf = hasher(), const key_equal &eql = key_equal(),
             const allocator_type &a = allocator_type())
        : hash_vector_base(false, false, end - begin), hf(hf), eql(eql), data(a) {
        data.reserve(end - begin);
        for (auto it = begin; it != end; ++it) insert(*it);
    }
    hvec_set(std::initializer_list<value_type> il, const hasher &hf = hasher(),
             const key_equal &eql = key_equal(), const allocator_type &a = allocator_type())
        : hash_vector_base(false, false, il.size()), hf(hf), eql(eql), data(a) {
        data.reserve(il.size());
        for (auto &i : il) insert(i);
    }
 
 private:
    template <class HVM, class VT>
    class _iter {
        HVM *self;
        size_t idx;
 
        friend class hvec_set;
        _iter(HVM &s, size_t i) : self(&s), idx(i) {}
 
     public:
        using value_type = VT;
        using difference_type = ssize_t;
        using pointer = typename HVM::pointer;
        using reference = typename HVM::reference;
        using iterator_category = std::bidirectional_iterator_tag;
        _iter(const _iter &) = default;
        _iter &operator=(const _iter &a) {
            self = a.self;
            idx = a.idx;
            return *this;
        }
        value_type &operator*() const { return self->data[idx]; }
        value_type *operator->() const { return &self->data[idx]; }
        _iter &operator++() {
            do {
                ++idx;
            } while (self->erased[idx]);
            return *this;
        }
        _iter &operator--() {
            do {
                --idx;
            } while (self->erased[idx]);
            return *this;
        }
        _iter operator++(int) {
            auto copy = *this;
            ++*this;
            return copy;
        }
        _iter operator--(int) {
            auto copy = *this;
            --*this;
            return copy;
        }
        bool operator==(const _iter &a) const { return self == a.self && idx == a.idx; }
        bool operator!=(const _iter &a) const { return self != a.self || idx != a.idx; }
        operator _iter<const HVM, const VT>() const {
            return _iter<const HVM, const VT>(*self, idx);
        }
    };
 
 public:
    typedef _iter<hvec_set, value_type> iterator;
    typedef _iter<const hvec_set, const value_type> const_iterator;
    iterator begin() { return iterator(*this, erased.ffz()); }
    iterator end() { return iterator(*this, data.size()); }
    const_iterator begin() const { return const_iterator(*this, erased.ffz()); }
    const_iterator end() const { return const_iterator(*this, data.size()); }
    const_iterator cbegin() const { return const_iterator(*this, erased.ffz()); }
    const_iterator cend() const { return const_iterator(*this, data.size()); }
    value_type &front() const { return *begin(); }
    value_type &back() const {
        auto it = end();
        return *--it;
    }
 
    bool empty() const { return inuse == 0; }
    size_t size() const { return inuse; }
    size_t max_size() const { return UINT32_MAX; }
    bool operator==(const hvec_set &a) const {
        if (inuse != a.inuse) return false;
        auto it = begin();
        for (auto &el : a)
            if (el != *it++) return false;
        return true;
    }
    bool operator!=(const hvec_set &a) const { return !(*this == a); }
    void clear() {
        hash_vector_base::clear();
        data.clear();
    }
 
    iterator find(const KEY &k) {
        hash_vector_base::lookup_cache cache;
        size_t idx = hash_vector_base::find(&k, &cache);
        return idx ? iterator(*this, idx - 1) : end();
    }
    const_iterator find(const KEY &k) const {
        hash_vector_base::lookup_cache cache;
        size_t idx = hash_vector_base::find(&k, &cache);
        return idx ? const_iterator(*this, idx - 1) : end();
    }
    size_t count(const KEY &k) const {
        hash_vector_base::lookup_cache cache;
        size_t idx = hash_vector_base::find(&k, &cache);
        return idx > 0;
    }
 
    template <typename... KK>
    std::pair<iterator, bool> emplace(KK &&...k) {
        return insert(value_type(std::forward<KK>(k)...));
    }
    std::pair<iterator, bool> insert(const value_type &v) {
        bool new_key = false;
        size_t idx = hv_insert(&v);
        if (idx >= data.size()) {
            idx = data.size();
            data.push_back(v);
            new_key = true;
        } else if ((new_key = erased[idx])) {
            erased[idx] = 0;
            data[idx] = v;
        }
        return std::make_pair(iterator(*this, idx), new_key);
    }
    std::pair<iterator, bool> insert(value_type &&v) {
        bool new_key = false;
        size_t idx = hv_insert(&v);
        if (idx >= data.size()) {
            idx = data.size();
            data.push_back(std::move(v));
            new_key = true;
        } else if ((new_key = erased[idx])) {
            erased[idx] = 0;
            data[idx] = std::move(v);
        }
        return std::make_pair(iterator(*this, idx), new_key);
    }
 
    template <typename InputIterator>
    void insert(InputIterator first, InputIterator last) {
        for (; first != last; ++first) insert(*first);
    }
    void insert(std::initializer_list<value_type> vl) { return insert(vl.begin(), vl.end()); }
    template <class HVM, class VT>
    _iter<HVM, VT> erase(_iter<HVM, VT> it) {
        BUG_CHECK(this == it.self, "incorrect iterator for hvec_set::erase");
        erased[it.idx] = 1;
        // FIXME -- would be better to call dtor here, but that will cause
        // problems with the vector when it is resized or destroyed.  Could
        // use raw memory and manual construct instead.
        data[it.idx] = KEY();
        ++it;
        --inuse;
        return it;
    }
    size_t erase(const KEY &k) {
        size_t idx = remove(&k);
        if (idx + 1 == 0) return 0;
        if (idx < data.size()) {
            data[idx] = KEY();
        }
        return 1;
    }
#ifdef DEBUG
    using hash_vector_base::dump;
#endif
 
 private:
    std::vector<KEY, ALLOC> data;
    size_t hashfn(const void *a) const override { return hf(*static_cast<const KEY *>(a)); }
    bool cmpfn(const void *a, const void *b) const override {
        return eql(*static_cast<const KEY *>(a), *static_cast<const KEY *>(b));
    }
    bool cmpfn(const void *a, size_t b) const override {
        return eql(*static_cast<const KEY *>(a), data[b]);
    }
    const void *getkey(uint32_t i) const override { return &data[i]; }
    void *getval(uint32_t) override {
        BUG("getval in set");
        return nullptr;
    }
    uint32_t limit() override { return data.size(); }
    void resizedata(size_t sz) override { data.resize(sz); }
    void moveentry(size_t to, size_t from) override { data[to] = data[from]; }
};
 
}  // namespace P4
 
#endif /* LIB_HVEC_SET_H_ */