blob: c590e0b3c1c44db424894dc507f7f9c43788277c [file] [log] [blame]
// Copyright (c) 2020 The Chromium 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 TOOLS_GN_STRING_ATOM_H_
#define TOOLS_GN_STRING_ATOM_H_
#include <functional>
#include <string>
#include <string_view>
// A StringAtom models a pointer to a globally unique constant string.
//
// They are useful as key types for sets and map container types, especially
// when a program uses multiple instances that tend to use the same strings
// (as happen very frequently in GN).
//
// Note that default equality and comparison functions will compare the
// string content, not the pointers, ensuring that the behaviour of
// standard containers using StringAtom key types is the same as if
// std::string was used.
//
// In addition, _ordered_ containers support heterogeneous lookups (i.e.
// using an std::string_view, and by automatic conversion, a const char*
// of const char[] literal) as a key type.
//
// Additionally, it is also possible to implement very fast _unordered_
// containers by using the StringAtom::Fast{Hash,Equal,Compare} structs,
// which will force containers to hash/compare pointer values instead,
// for example:
//
// // A fast unordered set of unique strings.
// //
// // Implementation uses a hash table so performance will be bounded
// // by the string hash function. Does not support heterogeneous lookups.
// //
// using FastStringSet = std::unordered_set<StringAtom,
// StringAtom::PtrHash,
// StringAtom::PtrEqual>;
//
// // A fast unordered set of unique strings.
// //
// // Implementation uses a balanced binary tree so performance will
// // be bounded by string comparisons. Does support heterogeneous lookups,
// // but not that this does not extend to the [] operator, only to the
// // find() method.
// //
// using FastStringSet = std::set<StringAtom, StringAtom::PtrCompare>
//
// // A fast unordered { string -> VALUE } map.
// //
// // Implementation uses a balanced binary tree. Supports heterogeneous
// // lookups.
// template <typename VALUE>
// using FastStringMap = std::map<StringAtom, VALUE, StringAtom::PtrCompare>
//
class StringAtom {
public:
// Default constructor. Value points to a globally unique empty string.
StringAtom();
// Destructor should do nothing at all.
~StringAtom() = default;
// Non-explicit constructors.
StringAtom(std::string_view str) noexcept;
// Copy and move operations.
StringAtom(const StringAtom& other) noexcept : value_(other.value_) {}
StringAtom& operator=(const StringAtom& other) noexcept {
if (this != &other) {
this->~StringAtom(); // really a no-op
new (this) StringAtom(other);
}
return *this;
}
StringAtom(StringAtom&& other) noexcept : value_(other.value_) {}
StringAtom& operator=(const StringAtom&& other) noexcept {
if (this != &other) {
this->~StringAtom(); // really a no-op
new (this) StringAtom(std::move(other));
}
return *this;
}
bool empty() const { return value_.empty(); }
// Explicit conversions.
const std::string& str() const { return value_; }
// Implicit conversions.
operator std::string_view() const { return {value_}; }
// Returns true iff this is the same key.
// Note that the default comparison functions compare the value instead
// in order to use them in standard containers without surprises by
// default.
bool SameAs(const StringAtom& other) const {
return &value_ == &other.value_;
}
// Default comparison functions.
bool operator==(const StringAtom& other) const {
return value_ == other.value_;
}
bool operator!=(const StringAtom& other) const {
return value_ != other.value_;
}
bool operator<(const StringAtom& other) const {
// Avoid one un-necessary string comparison if values are equal.
if (SameAs(other))
return false;
return value_ < other.value_;
}
size_t hash() const { return std::hash<std::string>()(value_); }
// Use the following method and structs to implement containers that
// use StringAtom values as keys, but only compare/hash the pointer
// values for speed.
//
// E.g.:
// using FastSet = std::unordered_set<StringAtom, PtrHash, PtrEqual>;
// using FastMap = std::map<StringAtom, Value, PtrCompare>;
//
// IMPORTANT: Note that FastMap above is ordered based in the StringAtom
// pointer value, not the string content.
//
size_t ptr_hash() const { return std::hash<const std::string*>()(&value_); }
struct PtrHash {
size_t operator()(const StringAtom& key) const noexcept {
return key.ptr_hash();
}
};
struct PtrEqual {
bool operator()(const StringAtom& a, const StringAtom& b) const noexcept {
return &a.value_ == &b.value_;
}
};
struct PtrCompare {
bool operator()(const StringAtom& a, const StringAtom& b) const noexcept {
return &a.value_ < &b.value_;
}
};
protected:
const std::string& value_;
};
namespace std {
// Ensure default heterogeneous lookups with other types like std::string_view.
template <>
struct less<StringAtom> {
using is_transparent = int;
bool operator()(const StringAtom& a, const StringAtom& b) const noexcept {
return a.str() < b.str();
}
template <typename U>
bool operator()(const StringAtom& a, const U& b) const noexcept {
return a.str() < b;
}
template <typename U>
bool operator()(const U& a, const StringAtom& b) const noexcept {
return a < b.str();
};
};
template <>
struct hash<StringAtom> {
size_t operator()(const StringAtom& key) const noexcept { return key.hash(); }
};
} // namespace std
#endif // TOOLS_GN_STRING_ATOM_H_