1 /* Copyright 2015 The TensorFlow Authors. All Rights Reserved. 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 http://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 16 // An InlinedVector<T,N,A> is like a std::vector<T,A>, except that storage 17 // for sequences of length <= N are provided inline without requiring 18 // any heap allocation. Typically N is very small (e.g., 4) so that 19 // sequences that are expected to be short do not require allocations. 20 // 21 // Only some of the std::vector<> operations are currently implemented. 22 // Other operations may be added as needed to facilitate migrating 23 // code that uses std::vector<> to InlinedVector<>. 24 // 25 // NOTE: If you want an inlined version to replace use of a 26 // std::vector<bool>, consider using util::bitmap::InlinedBitVector<NBITS> 27 // in util/bitmap/inlined_bitvector.h 28 // 29 // TODO(billydonahue): change size_t to size_type where appropriate. 30 31 #ifndef TENSORFLOW_LIB_GTL_INLINED_VECTOR_H_ 32 #define TENSORFLOW_LIB_GTL_INLINED_VECTOR_H_ 33 34 #include <stddef.h> 35 #include <stdlib.h> 36 #include <string.h> 37 #include <sys/types.h> 38 #include <algorithm> 39 #include <cstddef> 40 #include <iterator> 41 #include <memory> 42 #include <type_traits> 43 #include <vector> 44 45 #include "tensorflow/core/lib/gtl/manual_constructor.h" 46 #include "tensorflow/core/platform/cpu_info.h" 47 #include "tensorflow/core/platform/logging.h" 48 #include "tensorflow/core/platform/mem.h" 49 #include "tensorflow/core/platform/types.h" 50 51 #include <initializer_list> // NOLINT(build/include_order) 52 53 namespace tensorflow { 54 namespace gtl { 55 56 template <typename T, int N> 57 class InlinedVector { 58 public: 59 typedef T value_type; 60 typedef T* pointer; 61 typedef const T* const_pointer; 62 typedef T& reference; 63 typedef const T& const_reference; 64 typedef size_t size_type; 65 typedef std::ptrdiff_t difference_type; 66 typedef pointer iterator; 67 typedef const_pointer const_iterator; 68 69 // Create an empty vector 70 InlinedVector(); 71 72 // Create a vector with n copies of value_type(). 73 explicit InlinedVector(size_t n); 74 75 // Create a vector with n copies of elem 76 InlinedVector(size_t n, const value_type& elem); 77 78 // Create and initialize with the elements [range_start .. range_end). 79 // The unused enable_if argument restricts this constructor so that it is 80 // elided when value_type is an integral type. This prevents ambiguous 81 // interpretation between a call to this constructor with two integral 82 // arguments and a call to the preceding (n, elem) constructor. 83 template <typename InputIterator> 84 InlinedVector( 85 InputIterator range_start, InputIterator range_end, 86 typename std::enable_if<!std::is_integral<InputIterator>::value>::type* = 87 NULL) { 88 InitRep(); 89 AppendRange(range_start, range_end); 90 } 91 92 InlinedVector(std::initializer_list<value_type> init) { 93 InitRep(); 94 AppendRange(init.begin(), init.end()); 95 } 96 97 InlinedVector(const InlinedVector& v); 98 99 ~InlinedVector() { clear(); } 100 101 InlinedVector& operator=(const InlinedVector& v) { 102 // Optimized to avoid reallocation. 103 // Prefer reassignment to copy construction for elements. 104 const size_t s = size(); 105 const size_t vs = v.size(); 106 if (s < vs) { // grow 107 reserve(vs); 108 if (s) std::copy(v.begin(), v.begin() + s, begin()); 109 std::copy(v.begin() + s, v.end(), std::back_inserter(*this)); 110 } else { // maybe shrink 111 erase(begin() + vs, end()); 112 std::copy(v.begin(), v.end(), begin()); 113 } 114 return *this; 115 } 116 117 size_t size() const { return size_internal(); } 118 119 bool empty() const { return (size() == 0); } 120 121 // Return number of elements that can be stored in vector 122 // without requiring a reallocation of underlying memory 123 size_t capacity() const { 124 if (is_inline()) { 125 return kFit; 126 } else { 127 return static_cast<size_t>(1) << u_.data[kSize - 2]; 128 } 129 } 130 131 // Return a pointer to the underlying array. 132 // Only result[0,size()-1] are defined. 133 pointer data() { 134 if (is_inline()) { 135 return reinterpret_cast<T*>(u_.data); 136 } else { 137 return outofline_pointer(); 138 } 139 } 140 const_pointer data() const { 141 return const_cast<InlinedVector<T, N>*>(this)->data(); 142 } 143 144 // Remove all elements 145 void clear() { 146 DiscardStorage(); 147 u_.data[kSize - 1] = 0; 148 } 149 150 // Return the ith element 151 // REQUIRES: 0 <= i < size() 152 const value_type& at(size_t i) const { 153 DCHECK_LT(i, size()); 154 return data()[i]; 155 } 156 const value_type& operator[](size_t i) const { 157 DCHECK_LT(i, size()); 158 return data()[i]; 159 } 160 161 // Return a non-const reference to the ith element 162 // REQUIRES: 0 <= i < size() 163 value_type& at(size_t i) { 164 DCHECK_LT(i, size()); 165 return data()[i]; 166 } 167 value_type& operator[](size_t i) { 168 DCHECK_LT(i, size()); 169 return data()[i]; 170 } 171 172 value_type& back() { 173 DCHECK(!empty()); 174 return at(size() - 1); 175 } 176 177 const value_type& back() const { 178 DCHECK(!empty()); 179 return at(size() - 1); 180 } 181 182 value_type& front() { 183 DCHECK(!empty()); 184 return at(0); 185 } 186 187 const value_type& front() const { 188 DCHECK(!empty()); 189 return at(0); 190 } 191 192 // Append a T constructed with args to the vector. 193 // Increases size() by one. 194 // Amortized complexity: O(1) 195 // Worst-case complexity: O(size()) 196 template <typename... Args> 197 void emplace_back(Args&&... args) { 198 size_t s = size(); 199 DCHECK_LE(s, capacity()); 200 if (s < capacity()) { 201 new (data() + s) T(std::forward<Args>(args)...); 202 set_size_internal(s + 1); 203 } else { 204 EmplaceBackSlow(std::forward<Args>(args)...); 205 } 206 } 207 208 // Append t to the vector. 209 // Increases size() by one. 210 // Amortized complexity: O(1) 211 // Worst-case complexity: O(size()) 212 void push_back(const value_type& t) { emplace_back(t); } 213 void push_back(value_type&& t) { emplace_back(std::move(t)); } 214 215 inline void pop_back() { 216 DCHECK(!empty()); 217 const size_t s = size(); 218 Destroy(data() + s - 1, 1); 219 set_size_internal(s - 1); 220 } 221 222 // Resizes the vector to contain "n" elements. 223 // If "n" is smaller than the initial size, extra elements are destroyed. 224 // If "n" is larger than the initial size, enough copies of "elem" 225 // are appended to increase the size to "n". If "elem" is omitted, 226 // new elements are value-initialized. 227 void resize(size_t n) { Resize<ValueInit>(n, nullptr); } 228 void resize(size_t n, const value_type& elem) { Resize<Fill>(n, &elem); } 229 230 iterator begin() { return data(); } 231 const_iterator begin() const { return data(); } 232 233 iterator end() { return data() + size(); } 234 const_iterator end() const { return data() + size(); } 235 236 iterator insert(iterator pos, const value_type& v); 237 238 iterator erase(iterator pos) { 239 DCHECK_LT(pos, end()); 240 DCHECK_GE(pos, begin()); 241 std::copy(pos + 1, end(), pos); 242 pop_back(); 243 return pos; 244 } 245 246 iterator erase(iterator first, iterator last); 247 248 // Enlarges the underlying representation so it can hold at least 249 // "n" elements without reallocation. 250 // Does not change size() or the actual contents of the vector. 251 void reserve(size_t n) { 252 if (n > capacity()) { 253 // Make room for new elements 254 Grow<Move>(n); 255 } 256 } 257 258 // Swap the contents of *this with other. 259 // REQUIRES: value_type is swappable and copyable. 260 void swap(InlinedVector& other); 261 262 private: 263 // Representation can either be inlined or out-of-line. 264 // In either case, at least sizeof(void*) + 8 bytes are available. 265 // 266 // Inlined: 267 // Last byte holds the length. 268 // First (length*sizeof(T)) bytes stores the elements. 269 // Outlined: 270 // Last byte holds kSentinel. 271 // Second-last byte holds lg(capacity) 272 // Preceding 6 bytes hold size. 273 // First sizeof(T*) bytes hold pointer. 274 275 // Compute rep size. 276 static const size_t kSizeUnaligned = N * sizeof(T) + 1; // Room for tag 277 static const size_t kSize = ((kSizeUnaligned + 15) / 16) * 16; // Align 278 279 // See how many fit T we can fit inside kSize, but no more than 254 280 // since 255 is used as sentinel tag for out-of-line allocation. 281 static const unsigned int kSentinel = 255; 282 static const size_t kFit1 = (kSize - 1) / sizeof(T); 283 static const size_t kFit = (kFit1 >= kSentinel) ? (kSentinel - 1) : kFit1; 284 285 union { 286 unsigned char data[kSize]; 287 // Force data to be aligned enough for a pointer. 288 T* unused_aligner; 289 } u_; 290 291 inline void InitRep() { u_.data[kSize - 1] = 0; } 292 inline bool is_inline() const { return u_.data[kSize - 1] != kSentinel; } 293 294 inline T* outofline_pointer() const { 295 T* ptr; 296 memcpy(&ptr, &u_.data[0], sizeof(ptr)); 297 return ptr; 298 } 299 300 inline void set_outofline_pointer(T* p) { 301 memcpy(&u_.data[0], &p, sizeof(p)); 302 } 303 304 inline uint64_t outofline_word() const { 305 uint64_t word; 306 memcpy(&word, &u_.data[kSize - 8], sizeof(word)); 307 return word; 308 } 309 310 inline void set_outofline_word(uint64_t w) { 311 memcpy(&u_.data[kSize - 8], &w, sizeof(w)); 312 } 313 314 inline size_t size_internal() const { 315 uint8_t s = static_cast<uint8_t>(u_.data[kSize - 1]); 316 if (s != kSentinel) { 317 return static_cast<size_t>(s); 318 } else { 319 const uint64_t word = outofline_word(); 320 if (port::kLittleEndian) { 321 // The sentinel and capacity bits are most-significant bits in word. 322 return static_cast<size_t>(word & 0xffffffffffffull); 323 } else { 324 // The sentinel and capacity bits are least-significant bits in word. 325 return static_cast<size_t>(word >> 16); 326 } 327 } 328 } 329 330 void set_size_internal(size_t n) { 331 if (is_inline()) { 332 DCHECK_LT(n, kSentinel); 333 u_.data[kSize - 1] = static_cast<unsigned char>(n); 334 } else { 335 uint64_t word; 336 if (port::kLittleEndian) { 337 // The sentinel and capacity bits are most-significant bits in word. 338 word = (static_cast<uint64_t>(n) | 339 (static_cast<uint64_t>(u_.data[kSize - 2]) << 48) | 340 (static_cast<uint64_t>(kSentinel) << 56)); 341 } else { 342 // The sentinel and capacity bits are least-significant bits in word. 343 word = ((static_cast<uint64_t>(n) << 16) | 344 (static_cast<uint64_t>(u_.data[kSize - 2]) << 8) | 345 (static_cast<uint64_t>(kSentinel))); 346 } 347 set_outofline_word(word); 348 DCHECK_EQ(u_.data[kSize - 1], kSentinel) << n; 349 } 350 } 351 352 void DiscardStorage() { 353 T* base = data(); 354 size_t n = size(); 355 Destroy(base, n); 356 if (!is_inline()) { 357 port::Free(base); 358 } 359 } 360 361 template <typename... Args> 362 void EmplaceBackSlow(Args&&... args) { 363 const size_t s = size(); 364 DCHECK_EQ(s, capacity()); 365 Grow<Move, Construct>(s + 1, std::forward<Args>(args)...); 366 set_size_internal(s + 1); 367 } 368 369 // Movers for Grow 370 // Does nothing. 371 static void Nop(T* src, size_t n, T* dst) {} 372 373 // Moves srcs[0,n-1] contents to dst[0,n-1]. 374 static void Move(T* src, size_t n, T* dst) { 375 for (size_t i = 0; i < n; i++) { 376 new (dst + i) T(std::move(*(src + i))); 377 } 378 } 379 380 // Initializers for Resize. 381 // Initializes dst[0,n-1] with empty constructor. 382 static void ValueInit(const T*, size_t n, T* dst) { 383 for (size_t i = 0; i < n; i++) { 384 new (dst + i) T(); 385 } 386 } 387 388 // Initializes dst[0,n-1] with copies of *src. 389 static void Fill(const T* src, size_t n, T* dst) { 390 for (size_t i = 0; i < n; i++) { 391 new (dst + i) T(*src); 392 } 393 } 394 395 void Destroy(T* src, int n) { 396 if (!std::is_trivially_destructible<T>::value) { 397 for (int i = 0; i < n; i++) { 398 (src + i)->~T(); 399 } 400 } 401 } 402 403 // Initialization methods for Grow. 404 // 1) Leave uninitialized memory. 405 struct Uninitialized { 406 void operator()(T*) const {} 407 }; 408 // 2) Construct a T with args at not-yet-initialized memory pointed by dst. 409 struct Construct { 410 template <class... Args> 411 void operator()(T* dst, Args&&... args) const { 412 new (dst) T(std::forward<Args>(args)...); 413 } 414 }; 415 416 // Grow so that capacity >= n. Uses Mover to move existing elements 417 // to new buffer, and possibly initialize the new element according 418 // to InitType. 419 // We pass the InitType and Mover as template arguments so that 420 // this code compiles even if T does not support copying or default 421 // construction. 422 template <void(Mover)(T*, size_t, T*), class InitType = Uninitialized, 423 class... Args> 424 void Grow(size_t n, Args&&... args) { 425 size_t s = size(); 426 DCHECK_LE(s, capacity()); 427 428 // Compute new capacity by repeatedly doubling current capacity 429 size_t target = 1; 430 size_t target_lg = 0; 431 while (target < kFit || target < n) { 432 // TODO(psrc): Check and avoid overflow? 433 target_lg++; 434 target <<= 1; 435 } 436 437 T* src = data(); 438 T* dst = static_cast<T*>(port::Malloc(target * sizeof(T))); 439 440 // Need to copy elem before discarding src since it might alias src. 441 InitType{}(dst + s, std::forward<Args>(args)...); 442 Mover(src, s, dst); 443 DiscardStorage(); 444 445 u_.data[kSize - 1] = kSentinel; 446 u_.data[kSize - 2] = static_cast<unsigned char>(target_lg); 447 set_size_internal(s); 448 DCHECK_EQ(capacity(), target); 449 set_outofline_pointer(dst); 450 } 451 452 // Resize to size n. Any new elements are initialized by passing 453 // elem and the destination to Initializer. We pass the Initializer 454 // as a template argument so that this code compiles even if T does 455 // not support copying. 456 template <void(Initializer)(const T*, size_t, T*)> 457 void Resize(size_t n, const T* elem) { 458 size_t s = size(); 459 if (n <= s) { 460 Destroy(data() + n, s - n); 461 set_size_internal(n); 462 return; 463 } 464 reserve(n); 465 DCHECK_GE(capacity(), n); 466 set_size_internal(n); 467 Initializer(elem, n - s, data() + s); 468 } 469 470 template <typename Iter> 471 void AppendRange(Iter first, Iter last, std::input_iterator_tag); 472 473 // Faster path for forward iterators. 474 template <typename Iter> 475 void AppendRange(Iter first, Iter last, std::forward_iterator_tag); 476 477 template <typename Iter> 478 void AppendRange(Iter first, Iter last); 479 }; 480 481 // Provide linkage for constants. 482 template <typename T, int N> 483 const size_t InlinedVector<T, N>::kSizeUnaligned; 484 template <typename T, int N> 485 const size_t InlinedVector<T, N>::kSize; 486 template <typename T, int N> 487 const unsigned int InlinedVector<T, N>::kSentinel; 488 template <typename T, int N> 489 const size_t InlinedVector<T, N>::kFit1; 490 template <typename T, int N> 491 const size_t InlinedVector<T, N>::kFit; 492 493 template <typename T, int N> 494 inline void swap(InlinedVector<T, N>& a, InlinedVector<T, N>& b) { 495 a.swap(b); 496 } 497 498 template <typename T, int N> 499 inline bool operator==(const InlinedVector<T, N>& a, 500 const InlinedVector<T, N>& b) { 501 return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin()); 502 } 503 504 template <typename T, int N> 505 inline bool operator!=(const InlinedVector<T, N>& a, 506 const InlinedVector<T, N>& b) { 507 return !(a == b); 508 } 509 510 template <typename T, int N> 511 inline bool operator<(const InlinedVector<T, N>& a, 512 const InlinedVector<T, N>& b) { 513 return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); 514 } 515 516 template <typename T, int N> 517 inline bool operator>(const InlinedVector<T, N>& a, 518 const InlinedVector<T, N>& b) { 519 return b < a; 520 } 521 522 template <typename T, int N> 523 inline bool operator<=(const InlinedVector<T, N>& a, 524 const InlinedVector<T, N>& b) { 525 return !(b < a); 526 } 527 528 template <typename T, int N> 529 inline bool operator>=(const InlinedVector<T, N>& a, 530 const InlinedVector<T, N>& b) { 531 return !(a < b); 532 } 533 534 // ======================================== 535 // Implementation 536 537 template <typename T, int N> 538 inline InlinedVector<T, N>::InlinedVector() { 539 InitRep(); 540 } 541 542 template <typename T, int N> 543 inline InlinedVector<T, N>::InlinedVector(size_t n) { 544 InitRep(); 545 if (n > capacity()) { 546 Grow<Nop>(n); // Must use Nop in case T is not copyable 547 } 548 set_size_internal(n); 549 ValueInit(nullptr, n, data()); 550 } 551 552 template <typename T, int N> 553 inline InlinedVector<T, N>::InlinedVector(size_t n, const value_type& elem) { 554 InitRep(); 555 if (n > capacity()) { 556 Grow<Nop>(n); // Can use Nop since we know we have nothing to copy 557 } 558 set_size_internal(n); 559 Fill(&elem, n, data()); 560 } 561 562 template <typename T, int N> 563 inline InlinedVector<T, N>::InlinedVector(const InlinedVector& v) { 564 InitRep(); 565 *this = v; 566 } 567 568 template <typename T, int N> 569 typename InlinedVector<T, N>::iterator InlinedVector<T, N>::insert( 570 iterator pos, const value_type& v) { 571 DCHECK_GE(pos, begin()); 572 DCHECK_LE(pos, end()); 573 if (pos == end()) { 574 push_back(v); 575 return end() - 1; 576 } 577 size_t s = size(); 578 size_t idx = std::distance(begin(), pos); 579 if (s == capacity()) { 580 Grow<Move>(s + 1); 581 } 582 CHECK_LT(s, capacity()); 583 pos = begin() + idx; // Reset 'pos' into a post-enlarge iterator. 584 Fill(data() + s - 1, 1, data() + s); // data[s] = data[s-1] 585 std::copy_backward(pos, data() + s - 1, data() + s); 586 *pos = v; 587 588 set_size_internal(s + 1); 589 return pos; 590 } 591 592 template <typename T, int N> 593 typename InlinedVector<T, N>::iterator InlinedVector<T, N>::erase( 594 iterator first, iterator last) { 595 DCHECK_LE(begin(), first); 596 DCHECK_LE(first, last); 597 DCHECK_LE(last, end()); 598 599 size_t s = size(); 600 ptrdiff_t erase_gap = std::distance(first, last); 601 std::copy(last, data() + s, first); 602 Destroy(data() + s - erase_gap, erase_gap); 603 set_size_internal(s - erase_gap); 604 return first; 605 } 606 607 template <typename T, int N> 608 void InlinedVector<T, N>::swap(InlinedVector& other) { 609 using std::swap; // Augment ADL with std::swap. 610 if (&other == this) { 611 return; 612 } 613 614 InlinedVector* a = this; 615 InlinedVector* b = &other; 616 617 const bool a_inline = a->is_inline(); 618 const bool b_inline = b->is_inline(); 619 620 if (!a_inline && !b_inline) { 621 // Just swap the top-level representations. 622 T* aptr = a->outofline_pointer(); 623 T* bptr = b->outofline_pointer(); 624 a->set_outofline_pointer(bptr); 625 b->set_outofline_pointer(aptr); 626 627 uint64_t aword = a->outofline_word(); 628 uint64_t bword = b->outofline_word(); 629 a->set_outofline_word(bword); 630 b->set_outofline_word(aword); 631 return; 632 } 633 634 // Make a the larger of the two to reduce number of cases. 635 size_t a_size = a->size(); 636 size_t b_size = b->size(); 637 if (a->size() < b->size()) { 638 swap(a, b); 639 swap(a_size, b_size); 640 } 641 DCHECK_GE(a_size, b_size); 642 643 if (b->capacity() < a_size) { 644 b->Grow<Move>(a_size); 645 } 646 647 // One is inline and one is not. 648 // 'a' is larger. Swap the elements up to the smaller array size. 649 std::swap_ranges(a->data(), a->data() + b_size, b->data()); 650 std::uninitialized_copy(a->data() + b_size, a->data() + a_size, 651 b->data() + b_size); 652 Destroy(a->data() + b_size, a_size - b_size); 653 a->set_size_internal(b_size); 654 b->set_size_internal(a_size); 655 DCHECK_EQ(b->size(), a_size); 656 DCHECK_EQ(a->size(), b_size); 657 } 658 659 template <typename T, int N> 660 template <typename Iter> 661 inline void InlinedVector<T, N>::AppendRange(Iter first, Iter last, 662 std::input_iterator_tag) { 663 std::copy(first, last, std::back_inserter(*this)); 664 } 665 666 template <typename T, int N> 667 template <typename Iter> 668 inline void InlinedVector<T, N>::AppendRange(Iter first, Iter last, 669 std::forward_iterator_tag) { 670 typedef typename std::iterator_traits<Iter>::difference_type Length; 671 Length length = std::distance(first, last); 672 size_t s = size(); 673 reserve(s + length); 674 std::uninitialized_copy_n(first, length, data() + s); 675 set_size_internal(s + length); 676 } 677 678 template <typename T, int N> 679 template <typename Iter> 680 inline void InlinedVector<T, N>::AppendRange(Iter first, Iter last) { 681 typedef typename std::iterator_traits<Iter>::iterator_category IterTag; 682 AppendRange(first, last, IterTag()); 683 } 684 685 } // namespace gtl 686 } // namespace tensorflow 687 688 #endif // TENSORFLOW_LIB_GTL_INLINED_VECTOR_H_ 689