chromium/third_party/re2/src/re2/sparse_set.h

// Copyright 2006 The RE2 Authors.  All Rights Reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

#ifndef RE2_SPARSE_SET_H_
#define RE2_SPARSE_SET_H_

// DESCRIPTION
//
// SparseSet(m) is a set of integers in [0, m).
// It requires sizeof(int)*m memory, but it provides
// fast iteration through the elements in the set and fast clearing
// of the set.
//
// Insertion and deletion are constant time operations.
//
// Allocating the set is a constant time operation
// when memory allocation is a constant time operation.
//
// Clearing the set is a constant time operation (unusual!).
//
// Iterating through the set is an O(n) operation, where n
// is the number of items in the set (not O(m)).
//
// The set iterator visits entries in the order they were first
// inserted into the set.  It is safe to add items to the set while
// using an iterator: the iterator will visit indices added to the set
// during the iteration, but will not re-visit indices whose values
// change after visiting.  Thus SparseSet can be a convenient
// implementation of a work queue.
//
// The SparseSet implementation is NOT thread-safe.  It is up to the
// caller to make sure only one thread is accessing the set.  (Typically
// these sets are temporary values and used in situations where speed is
// important.)
//
// The SparseSet interface does not present all the usual STL bells and
// whistles.
//
// Implemented with reference to Briggs & Torczon, An Efficient
// Representation for Sparse Sets, ACM Letters on Programming Languages
// and Systems, Volume 2, Issue 1-4 (March-Dec.  1993), pp.  59-69.
//
// This is a specialization of sparse array; see sparse_array.h.

// IMPLEMENTATION
//
// See sparse_array.h for implementation details.

#include <assert.h>
#include <stdint.h>

#include <algorithm>
#include <memory>
#include <utility>

#include "re2/pod_array.h"

// Doing this simplifies the logic below.
#ifndef __has_feature
#define __has_feature …
#endif

#if __has_feature(memory_sanitizer)
#include <sanitizer/msan_interface.h>
#endif

namespace re2 {

template<typename Value>
class SparseSetT { … };

template<typename Value>
SparseSetT<Value>::SparseSetT() = default;

// Change the maximum size of the set.
// Invalidates all iterators.
template<typename Value>
void SparseSetT<Value>::resize(int new_max_size) { … }

// Check whether index i is in the set.
template<typename Value>
bool SparseSetT<Value>::contains(int i) const { … }

template<typename Value>
void SparseSetT<Value>::create_index(int i) { … }

template<typename Value> SparseSetT<Value>::SparseSetT(int max_size) : … { … }

template<typename Value> SparseSetT<Value>::~SparseSetT() { … }

template<typename Value> void SparseSetT<Value>::DebugCheckInvariants() const { … }

// Comparison function for sorting.
template<typename Value> bool SparseSetT<Value>::less(int a, int b) { … }

SparseSet;

}  // namespace re2

#endif  // RE2_SPARSE_SET_H_