src/gn/string_atom.h

// 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>

// 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 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.
  //
  struct PtrHash {
    size_t operator()(const StringAtom& key) const noexcept {
      return std::hash<const std::string*>()(&key.value_);
    }
  };

  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_