1 // Copyright 2020 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef ABSL_STRINGS_INTERNAL_CORD_INTERNAL_H_
16 #define ABSL_STRINGS_INTERNAL_CORD_INTERNAL_H_
17
18 #include <atomic>
19 #include <cassert>
20 #include <cstddef>
21 #include <cstdint>
22 #include <type_traits>
23
24 #include "absl/meta/type_traits.h"
25 #include "absl/strings/string_view.h"
26
27 namespace absl {
28 ABSL_NAMESPACE_BEGIN
29 namespace cord_internal {
30
31 // Wraps std::atomic for reference counting.
32 class Refcount {
33 public:
Refcount()34 Refcount() : count_{1} {}
~Refcount()35 ~Refcount() {}
36
37 // Increments the reference count by 1. Imposes no memory ordering.
Increment()38 inline void Increment() { count_.fetch_add(1, std::memory_order_relaxed); }
39
40 // Asserts that the current refcount is greater than 0. If the refcount is
41 // greater than 1, decrements the reference count by 1.
42 //
43 // Returns false if there are no references outstanding; true otherwise.
44 // Inserts barriers to ensure that state written before this method returns
45 // false will be visible to a thread that just observed this method returning
46 // false.
Decrement()47 inline bool Decrement() {
48 int32_t refcount = count_.load(std::memory_order_acquire);
49 assert(refcount > 0);
50 return refcount != 1 && count_.fetch_sub(1, std::memory_order_acq_rel) != 1;
51 }
52
53 // Same as Decrement but expect that refcount is greater than 1.
DecrementExpectHighRefcount()54 inline bool DecrementExpectHighRefcount() {
55 int32_t refcount = count_.fetch_sub(1, std::memory_order_acq_rel);
56 assert(refcount > 0);
57 return refcount != 1;
58 }
59
60 // Returns the current reference count using acquire semantics.
Get()61 inline int32_t Get() const { return count_.load(std::memory_order_acquire); }
62
63 // Returns whether the atomic integer is 1.
64 // If the reference count is used in the conventional way, a
65 // reference count of 1 implies that the current thread owns the
66 // reference and no other thread shares it.
67 // This call performs the test for a reference count of one, and
68 // performs the memory barrier needed for the owning thread
69 // to act on the object, knowing that it has exclusive access to the
70 // object.
IsOne()71 inline bool IsOne() { return count_.load(std::memory_order_acquire) == 1; }
72
73 private:
74 std::atomic<int32_t> count_;
75 };
76
77 // The overhead of a vtable is too much for Cord, so we roll our own subclasses
78 // using only a single byte to differentiate classes from each other - the "tag"
79 // byte. Define the subclasses first so we can provide downcasting helper
80 // functions in the base class.
81
82 struct CordRepConcat;
83 struct CordRepSubstring;
84 struct CordRepExternal;
85
86 struct CordRep {
87 // The following three fields have to be less than 32 bytes since
88 // that is the smallest supported flat node size.
89 // We use uint64_t for the length even in 32-bit binaries.
90 uint64_t length;
91 Refcount refcount;
92 // If tag < FLAT, it represents CordRepKind and indicates the type of node.
93 // Otherwise, the node type is CordRepFlat and the tag is the encoded size.
94 uint8_t tag;
95 char data[1]; // Starting point for flat array: MUST BE LAST FIELD of CordRep
96
97 inline CordRepConcat* concat();
98 inline const CordRepConcat* concat() const;
99 inline CordRepSubstring* substring();
100 inline const CordRepSubstring* substring() const;
101 inline CordRepExternal* external();
102 inline const CordRepExternal* external() const;
103 };
104
105 struct CordRepConcat : public CordRep {
106 CordRep* left;
107 CordRep* right;
108
depthCordRepConcat109 uint8_t depth() const { return static_cast<uint8_t>(data[0]); }
set_depthCordRepConcat110 void set_depth(uint8_t depth) { data[0] = static_cast<char>(depth); }
111 };
112
113 struct CordRepSubstring : public CordRep {
114 size_t start; // Starting offset of substring in child
115 CordRep* child;
116 };
117
118 // TODO(strel): replace the following logic (and related functions in cord.cc)
119 // with container_internal::Layout.
120
121 // Alignment requirement for CordRepExternal so that the type erased releaser
122 // will be stored at a suitably aligned address.
ExternalRepAlignment()123 constexpr size_t ExternalRepAlignment() {
124 #if defined(__STDCPP_DEFAULT_NEW_ALIGNMENT__)
125 return __STDCPP_DEFAULT_NEW_ALIGNMENT__;
126 #else
127 return alignof(max_align_t);
128 #endif
129 }
130
131 // Type for function pointer that will invoke and destroy the type-erased
132 // releaser function object. Accepts a pointer to the releaser and the
133 // `string_view` that were passed in to `NewExternalRep` below. The return value
134 // is the size of the `Releaser` type.
135 using ExternalReleaserInvoker = size_t (*)(void*, absl::string_view);
136
137 // External CordReps are allocated together with a type erased releaser. The
138 // releaser is stored in the memory directly following the CordRepExternal.
139 struct alignas(ExternalRepAlignment()) CordRepExternal : public CordRep {
140 const char* base;
141 // Pointer to function that knows how to call and destroy the releaser.
142 ExternalReleaserInvoker releaser_invoker;
143 };
144
145 // TODO(strel): look into removing, it doesn't seem like anything relies on this
146 static_assert(sizeof(CordRepConcat) == sizeof(CordRepSubstring), "");
147
148 } // namespace cord_internal
149 ABSL_NAMESPACE_END
150 } // namespace absl
151 #endif // ABSL_STRINGS_INTERNAL_CORD_INTERNAL_H_
152