Add TaggedPointer<T,N> template.

A compact encoding for a (pointer, tag) pair, where |tag| is a
small unsigned integer that uses no more than N bits, and
|pointer| is guaranteed to be aligned on N bits as well.

This will be used by future CLs to optimize memory usage of some
critical GN data structures.

Bug: None
Change-Id: Ica9d720a4579cbc30b312c1f940e46dd9230a0c8
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/13622
Reviewed-by: Sylvain Defresne <sdefresne@chromium.org>
Commit-Queue: David Turner <digit@google.com>

build/gen.py

diff --git a/build/gen.py b/build/gen.py
index f695ccd..4c75502 100755
--- a/build/gen.py
+++ b/build/gen.py
@@ -803,6 +803,7 @@
         'src/gn/string_utils_unittest.cc',
         'src/gn/substitution_pattern_unittest.cc',
         'src/gn/substitution_writer_unittest.cc',
+        'src/gn/tagged_pointer_unittest.cc',
         'src/gn/target_unittest.cc',
         'src/gn/template_unittest.cc',
         'src/gn/test_with_scheduler.cc',

src/gn/tagged_pointer.h

diff --git a/src/gn/tagged_pointer.h b/src/gn/tagged_pointer.h
new file mode 100644
index 0000000..df760d1
--- /dev/null
+++ b/src/gn/tagged_pointer.h
@@ -0,0 +1,58 @@
+// Copyright 2022 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_TAGGED_POINTER_H_
+#define TOOLS_GN_TAGGED_POINTER_H_
+
+#include "base/logging.h"
+
+// A TaggedPointer<T.N> is a compact encoding of a (pointer, tag) pair
+// when all |tag| values are guaranteed to be less than N bits long, and
+// all pointer values are guaranteed to be aligned to at least N bits.
+template <typename T, size_t BITS>
+class TaggedPointer {
+ public:
+  TaggedPointer() = default;
+  TaggedPointer(T* ptr, unsigned tag)
+      : value_(reinterpret_cast<uintptr_t>(ptr)) {
+    CheckPointerValue(ptr);
+    CheckTagValue(tag);
+    value_ |= static_cast<uintptr_t>(tag);
+  }
+
+  T* ptr() const { return reinterpret_cast<T*>(value_ & ~kTagMask); }
+  unsigned tag() const { return static_cast<unsigned>(value_ & kTagMask); }
+
+  void set_ptr(T* ptr) {
+    CheckPointerValue(ptr);
+    value_ = reinterpret_cast<uintptr_t>(ptr) | (value_ & kTagMask);
+  }
+
+  void set_tag(unsigned tag) {
+    CheckTagValue(tag);
+    value_ = (value_ & ~kTagMask) | tag;
+  }
+
+  bool operator==(TaggedPointer other) const { return value_ == other.value_; }
+
+  bool operator!=(TaggedPointer other) const { return !(*this == other); }
+
+  bool operator<(TaggedPointer other) const { return value_ < other.value_; }
+
+ private:
+  static const uintptr_t kTagMask = (uintptr_t(1) << BITS) - 1u;
+
+  static void CheckPointerValue(T* ptr) {
+    DCHECK((reinterpret_cast<uintptr_t>(ptr) & kTagMask) == 0)
+        << "Pointer is not aligned to " << BITS << " bits: " << ptr;
+  }
+  static void CheckTagValue(unsigned tag) {
+    DCHECK(tag <= kTagMask)
+        << "Tag value is larger than " << BITS << " bits: " << tag;
+  }
+
+  uintptr_t value_ = 0;
+};
+
+#endif  // TOOLS_GN_TAGGED_POINTER_H_

src/gn/tagged_pointer_unittest.cc

diff --git a/src/gn/tagged_pointer_unittest.cc b/src/gn/tagged_pointer_unittest.cc
new file mode 100644
index 0000000..b6d68e5
--- /dev/null
+++ b/src/gn/tagged_pointer_unittest.cc
@@ -0,0 +1,19 @@
+#include "gn/tagged_pointer.h"
+#include "util/test/test.h"
+
+struct Point {
+  double x;
+  double y;
+};
+
+TEST(TaggedPointer, Creation) {
+  TaggedPointer<Point, 2> ptr;
+
+  EXPECT_FALSE(ptr.ptr());
+  EXPECT_EQ(0u, ptr.tag());
+
+  Point point1 = {1., 2.};
+  TaggedPointer<Point, 2> ptr2(&point1, 2);
+  EXPECT_EQ(&point1, ptr2.ptr());
+  EXPECT_EQ(2u, ptr2.tag());
+}