1 //===--- TrailingObjects.h - Variable-length classes ------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 /// 10 /// \file 11 /// This header defines support for implementing classes that have 12 /// some trailing object (or arrays of objects) appended to them. The 13 /// main purpose is to make it obvious where this idiom is being used, 14 /// and to make the usage more idiomatic and more difficult to get 15 /// wrong. 16 /// 17 /// The TrailingObject template abstracts away the reinterpret_cast, 18 /// pointer arithmetic, and size calculations used for the allocation 19 /// and access of appended arrays of objects, as well as asserts that 20 /// the alignment of the classes involved are appropriate for the 21 /// usage. Additionally, it ensures that the base type is final -- 22 /// deriving from a class that expects data appended immediately after 23 /// it is typically not safe. 24 /// 25 /// Users are expected to derive from this template, and provide 26 /// numTrailingObjects implementations for each trailing type, 27 /// e.g. like this sample: 28 /// 29 /// \code 30 /// class VarLengthObj : private TrailingObjects<VarLengthObj, int, double> { 31 /// friend TrailingObjects; 32 /// 33 /// unsigned NumInts, NumDoubles; 34 /// size_t numTrailingObjects(OverloadToken<int>) const { return NumInts; } 35 /// size_t numTrailingObjects(OverloadToken<double>) const { 36 /// return NumDoubles; 37 /// } 38 /// }; 39 /// \endcode 40 /// 41 /// You can access the appended arrays via 'getTrailingObjects', and 42 /// determine the size needed for allocation via 43 /// 'additionalSizeToAlloc' and 'totalSizeToAlloc'. 44 /// 45 /// All the methods implemented by this class are are intended for use 46 /// by the implementation of the class, not as part of its interface 47 /// (thus, private inheritance is suggested). 48 /// 49 //===----------------------------------------------------------------------===// 50 51 #ifndef LLVM_SUPPORT_TRAILINGOBJECTS_H 52 #define LLVM_SUPPORT_TRAILINGOBJECTS_H 53 54 #include <new> 55 #include <type_traits> 56 #include "llvm/Support/AlignOf.h" 57 #include "llvm/Support/Compiler.h" 58 #include "llvm/Support/type_traits.h" 59 60 namespace llvm { 61 62 namespace trailing_objects_internal { 63 /// Helper template to calculate the max alignment requirement for a set of 64 /// objects. 65 template <typename First, typename... Rest> class AlignmentCalcHelper { 66 private: 67 enum { 68 FirstAlignment = AlignOf<First>::Alignment, 69 RestAlignment = AlignmentCalcHelper<Rest...>::Alignment, 70 }; 71 72 public: 73 enum { 74 Alignment = FirstAlignment > RestAlignment ? FirstAlignment : RestAlignment 75 }; 76 }; 77 78 template <typename First> class AlignmentCalcHelper<First> { 79 public: 80 enum { Alignment = AlignOf<First>::Alignment }; 81 }; 82 83 /// The base class for TrailingObjects* classes. 84 class TrailingObjectsBase { 85 protected: 86 /// OverloadToken's purpose is to allow specifying function overloads 87 /// for different types, without actually taking the types as 88 /// parameters. (Necessary because member function templates cannot 89 /// be specialized, so overloads must be used instead of 90 /// specialization.) 91 template <typename T> struct OverloadToken {}; 92 }; 93 94 /// This helper template works-around MSVC 2013's lack of useful 95 /// alignas() support. The argument to LLVM_ALIGNAS(), in MSVC, is 96 /// required to be a literal integer. But, you *can* use template 97 /// specialization to select between a bunch of different LLVM_ALIGNAS 98 /// expressions... 99 template <int Align> 100 class TrailingObjectsAligner : public TrailingObjectsBase {}; 101 template <> 102 class LLVM_ALIGNAS(1) TrailingObjectsAligner<1> : public TrailingObjectsBase {}; 103 template <> 104 class LLVM_ALIGNAS(2) TrailingObjectsAligner<2> : public TrailingObjectsBase {}; 105 template <> 106 class LLVM_ALIGNAS(4) TrailingObjectsAligner<4> : public TrailingObjectsBase {}; 107 template <> 108 class LLVM_ALIGNAS(8) TrailingObjectsAligner<8> : public TrailingObjectsBase {}; 109 template <> 110 class LLVM_ALIGNAS(16) TrailingObjectsAligner<16> : public TrailingObjectsBase { 111 }; 112 template <> 113 class LLVM_ALIGNAS(32) TrailingObjectsAligner<32> : public TrailingObjectsBase { 114 }; 115 116 // Just a little helper for transforming a type pack into the same 117 // number of a different type. e.g.: 118 // ExtractSecondType<Foo..., int>::type 119 template <typename Ty1, typename Ty2> struct ExtractSecondType { 120 typedef Ty2 type; 121 }; 122 123 // TrailingObjectsImpl is somewhat complicated, because it is a 124 // recursively inheriting template, in order to handle the template 125 // varargs. Each level of inheritance picks off a single trailing type 126 // then recurses on the rest. The "Align", "BaseTy", and 127 // "TopTrailingObj" arguments are passed through unchanged through the 128 // recursion. "PrevTy" is, at each level, the type handled by the 129 // level right above it. 130 131 template <int Align, typename BaseTy, typename TopTrailingObj, typename PrevTy, 132 typename... MoreTys> 133 struct TrailingObjectsImpl { 134 // The main template definition is never used -- the two 135 // specializations cover all possibilities. 136 }; 137 138 template <int Align, typename BaseTy, typename TopTrailingObj, typename PrevTy, 139 typename NextTy, typename... MoreTys> 140 struct TrailingObjectsImpl<Align, BaseTy, TopTrailingObj, PrevTy, NextTy, 141 MoreTys...> 142 : public TrailingObjectsImpl<Align, BaseTy, TopTrailingObj, NextTy, 143 MoreTys...> { 144 145 typedef TrailingObjectsImpl<Align, BaseTy, TopTrailingObj, NextTy, MoreTys...> 146 ParentType; 147 148 // Ensure the methods we inherit are not hidden. 149 using ParentType::getTrailingObjectsImpl; 150 using ParentType::additionalSizeToAllocImpl; 151 152 static void verifyTrailingObjectsAssertions() { 153 static_assert(llvm::AlignOf<PrevTy>::Alignment >= 154 llvm::AlignOf<NextTy>::Alignment, 155 "A trailing object requires more alignment than the previous " 156 "trailing object provides"); 157 158 ParentType::verifyTrailingObjectsAssertions(); 159 } 160 161 // These two functions are helper functions for 162 // TrailingObjects::getTrailingObjects. They recurse to the left -- 163 // the result for each type in the list of trailing types depends on 164 // the result of calling the function on the type to the 165 // left. However, the function for the type to the left is 166 // implemented by a *subclass* of this class, so we invoke it via 167 // the TopTrailingObj, which is, via the 168 // curiously-recurring-template-pattern, the most-derived type in 169 // this recursion, and thus, contains all the overloads. 170 static const NextTy * 171 getTrailingObjectsImpl(const BaseTy *Obj, 172 TrailingObjectsBase::OverloadToken<NextTy>) { 173 return reinterpret_cast<const NextTy *>( 174 TopTrailingObj::getTrailingObjectsImpl( 175 Obj, TrailingObjectsBase::OverloadToken<PrevTy>()) + 176 TopTrailingObj::callNumTrailingObjects( 177 Obj, TrailingObjectsBase::OverloadToken<PrevTy>())); 178 } 179 180 static NextTy * 181 getTrailingObjectsImpl(BaseTy *Obj, 182 TrailingObjectsBase::OverloadToken<NextTy>) { 183 return reinterpret_cast<NextTy *>( 184 TopTrailingObj::getTrailingObjectsImpl( 185 Obj, TrailingObjectsBase::OverloadToken<PrevTy>()) + 186 TopTrailingObj::callNumTrailingObjects( 187 Obj, TrailingObjectsBase::OverloadToken<PrevTy>())); 188 } 189 190 // Helper function for TrailingObjects::additionalSizeToAlloc: this 191 // function recurses to superclasses, each of which requires one 192 // fewer size_t argument, and adds its own size. 193 static LLVM_CONSTEXPR size_t additionalSizeToAllocImpl( 194 size_t Count1, 195 typename ExtractSecondType<MoreTys, size_t>::type... MoreCounts) { 196 return sizeof(NextTy) * Count1 + additionalSizeToAllocImpl(MoreCounts...); 197 } 198 }; 199 200 // The base case of the TrailingObjectsImpl inheritance recursion, 201 // when there's no more trailing types. 202 template <int Align, typename BaseTy, typename TopTrailingObj, typename PrevTy> 203 struct TrailingObjectsImpl<Align, BaseTy, TopTrailingObj, PrevTy> 204 : public TrailingObjectsAligner<Align> { 205 // This is a dummy method, only here so the "using" doesn't fail -- 206 // it will never be called, because this function recurses backwards 207 // up the inheritance chain to subclasses. 208 static void getTrailingObjectsImpl(); 209 210 static LLVM_CONSTEXPR size_t additionalSizeToAllocImpl() { return 0; } 211 212 static void verifyTrailingObjectsAssertions() {} 213 }; 214 215 } // end namespace trailing_objects_internal 216 217 // Finally, the main type defined in this file, the one intended for users... 218 219 /// See the file comment for details on the usage of the 220 /// TrailingObjects type. 221 template <typename BaseTy, typename... TrailingTys> 222 class TrailingObjects : private trailing_objects_internal::TrailingObjectsImpl< 223 trailing_objects_internal::AlignmentCalcHelper< 224 TrailingTys...>::Alignment, 225 BaseTy, TrailingObjects<BaseTy, TrailingTys...>, 226 BaseTy, TrailingTys...> { 227 228 template <int A, typename B, typename T, typename P, typename... M> 229 friend struct trailing_objects_internal::TrailingObjectsImpl; 230 231 template <typename... Tys> class Foo {}; 232 233 typedef trailing_objects_internal::TrailingObjectsImpl< 234 trailing_objects_internal::AlignmentCalcHelper<TrailingTys...>::Alignment, 235 BaseTy, TrailingObjects<BaseTy, TrailingTys...>, BaseTy, TrailingTys...> 236 ParentType; 237 using TrailingObjectsBase = trailing_objects_internal::TrailingObjectsBase; 238 239 using ParentType::getTrailingObjectsImpl; 240 241 // Contains static_assert statements for the alignment of the 242 // types. Must not be at class-level, because BaseTy isn't complete 243 // at class instantiation time, but will be by the time this 244 // function is instantiated. Recurses through the superclasses. 245 static void verifyTrailingObjectsAssertions() { 246 #ifdef LLVM_IS_FINAL 247 static_assert(LLVM_IS_FINAL(BaseTy), "BaseTy must be final."); 248 #endif 249 ParentType::verifyTrailingObjectsAssertions(); 250 } 251 252 // These two methods are the base of the recursion for this method. 253 static const BaseTy * 254 getTrailingObjectsImpl(const BaseTy *Obj, 255 TrailingObjectsBase::OverloadToken<BaseTy>) { 256 return Obj; 257 } 258 259 static BaseTy * 260 getTrailingObjectsImpl(BaseTy *Obj, 261 TrailingObjectsBase::OverloadToken<BaseTy>) { 262 return Obj; 263 } 264 265 // callNumTrailingObjects simply calls numTrailingObjects on the 266 // provided Obj -- except when the type being queried is BaseTy 267 // itself. There is always only one of the base object, so that case 268 // is handled here. (An additional benefit of indirecting through 269 // this function is that consumers only say "friend 270 // TrailingObjects", and thus, only this class itself can call the 271 // numTrailingObjects function.) 272 static size_t 273 callNumTrailingObjects(const BaseTy *Obj, 274 TrailingObjectsBase::OverloadToken<BaseTy>) { 275 return 1; 276 } 277 278 template <typename T> 279 static size_t callNumTrailingObjects(const BaseTy *Obj, 280 TrailingObjectsBase::OverloadToken<T>) { 281 return Obj->numTrailingObjects(TrailingObjectsBase::OverloadToken<T>()); 282 } 283 284 public: 285 // make this (privately inherited) class public. 286 using ParentType::OverloadToken; 287 288 /// Returns a pointer to the trailing object array of the given type 289 /// (which must be one of those specified in the class template). The 290 /// array may have zero or more elements in it. 291 template <typename T> const T *getTrailingObjects() const { 292 verifyTrailingObjectsAssertions(); 293 // Forwards to an impl function with overloads, since member 294 // function templates can't be specialized. 295 return this->getTrailingObjectsImpl( 296 static_cast<const BaseTy *>(this), 297 TrailingObjectsBase::OverloadToken<T>()); 298 } 299 300 /// Returns a pointer to the trailing object array of the given type 301 /// (which must be one of those specified in the class template). The 302 /// array may have zero or more elements in it. 303 template <typename T> T *getTrailingObjects() { 304 verifyTrailingObjectsAssertions(); 305 // Forwards to an impl function with overloads, since member 306 // function templates can't be specialized. 307 return this->getTrailingObjectsImpl( 308 static_cast<BaseTy *>(this), TrailingObjectsBase::OverloadToken<T>()); 309 } 310 311 /// Returns the size of the trailing data, if an object were 312 /// allocated with the given counts (The counts are in the same order 313 /// as the template arguments). This does not include the size of the 314 /// base object. The template arguments must be the same as those 315 /// used in the class; they are supplied here redundantly only so 316 /// that it's clear what the counts are counting in callers. 317 template <typename... Tys> 318 static LLVM_CONSTEXPR typename std::enable_if< 319 std::is_same<Foo<TrailingTys...>, Foo<Tys...>>::value, size_t>::type 320 additionalSizeToAlloc( 321 typename trailing_objects_internal::ExtractSecondType< 322 TrailingTys, size_t>::type... Counts) { 323 return ParentType::additionalSizeToAllocImpl(Counts...); 324 } 325 326 /// Returns the total size of an object if it were allocated with the 327 /// given trailing object counts. This is the same as 328 /// additionalSizeToAlloc, except it *does* include the size of the base 329 /// object. 330 template <typename... Tys> 331 static LLVM_CONSTEXPR typename std::enable_if< 332 std::is_same<Foo<TrailingTys...>, Foo<Tys...>>::value, size_t>::type 333 totalSizeToAlloc(typename trailing_objects_internal::ExtractSecondType< 334 TrailingTys, size_t>::type... Counts) { 335 return sizeof(BaseTy) + ParentType::additionalSizeToAllocImpl(Counts...); 336 } 337 }; 338 339 } // end namespace llvm 340 341 #endif 342
