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>
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',
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_
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());
+}