51 lines
1.6 KiB
C++
51 lines
1.6 KiB
C++
// Copyright (c) Microsoft Corporation. All rights reserved.
|
|
// Licensed under the MIT license.
|
|
|
|
#pragma once
|
|
|
|
#include <memory>
|
|
#include <type_traits>
|
|
|
|
#include "boost_dynamic_bitset_fwd.h"
|
|
|
|
namespace diskann
|
|
{
|
|
// A set of natural numbers (from 0 onwards). Made for scenario where the
|
|
// pool of numbers is consecutive from zero to some max value and very
|
|
// efficient methods for "add to set", "get any value from set", "is in set"
|
|
// are needed. The memory usage of the set is determined by the largest
|
|
// number of inserted entries (uses a vector as a backing store) as well as
|
|
// the largest value to be placed in it (uses bitset as well).
|
|
//
|
|
// Thread-safety: this class is not thread-safe in general.
|
|
// Exception: multiple read-only operations (e.g. is_in_set, empty, size) are
|
|
// safe on the object only if there are no writers to it in parallel.
|
|
template <typename T> class natural_number_set
|
|
{
|
|
public:
|
|
static_assert(std::is_trivial<T>::value, "Identifier must be a trivial type");
|
|
|
|
natural_number_set();
|
|
|
|
bool is_empty() const;
|
|
void reserve(size_t count);
|
|
void insert(T id);
|
|
T pop_any();
|
|
void clear();
|
|
size_t size() const;
|
|
bool is_in_set(T id) const;
|
|
|
|
private:
|
|
// Values that are currently in set.
|
|
std::vector<T> _values_vector;
|
|
|
|
// Values that are in the set have the corresponding bit index set
|
|
// to 1.
|
|
//
|
|
// Use a pointer here to allow for forward declaration of dynamic_bitset
|
|
// in public headers to avoid making boost a dependency for clients
|
|
// of DiskANN.
|
|
std::unique_ptr<boost::dynamic_bitset<>> _values_bitset;
|
|
};
|
|
} // namespace diskann
|