1  //===-- sanitizer_vector.h -------------------------------------*- C++ -*-===//
       2  //
       3  // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
       4  // See https://llvm.org/LICENSE.txt for license information.
       5  // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
       6  //
       7  //===----------------------------------------------------------------------===//
       8  //
       9  // This file is shared between sanitizers run-time libraries.
      10  //
      11  //===----------------------------------------------------------------------===//
      12  
      13  // Low-fat STL-like vector container.
      14  
      15  #ifndef SANITIZER_VECTOR_H
      16  #define SANITIZER_VECTOR_H
      17  
      18  #include "sanitizer_common/sanitizer_allocator_internal.h"
      19  #include "sanitizer_common/sanitizer_libc.h"
      20  
      21  namespace __sanitizer {
      22  
      23  template<typename T>
      24  class Vector {
      25   public:
      26    Vector() : begin_(), end_(), last_() {}
      27  
      28    ~Vector() {
      29      if (begin_)
      30        InternalFree(begin_);
      31    }
      32  
      33    void Reset() {
      34      if (begin_)
      35        InternalFree(begin_);
      36      begin_ = 0;
      37      end_ = 0;
      38      last_ = 0;
      39    }
      40  
      41    uptr Size() const {
      42      return end_ - begin_;
      43    }
      44  
      45    T &operator[](uptr i) {
      46      DCHECK_LT(i, end_ - begin_);
      47      return begin_[i];
      48    }
      49  
      50    const T &operator[](uptr i) const {
      51      DCHECK_LT(i, end_ - begin_);
      52      return begin_[i];
      53    }
      54  
      55    T *PushBack() {
      56      EnsureSize(Size() + 1);
      57      T *p = &end_[-1];
      58      internal_memset(p, 0, sizeof(*p));
      59      return p;
      60    }
      61  
      62    T *PushBack(const T& v) {
      63      EnsureSize(Size() + 1);
      64      T *p = &end_[-1];
      65      internal_memcpy(p, &v, sizeof(*p));
      66      return p;
      67    }
      68  
      69    void PopBack() {
      70      DCHECK_GT(end_, begin_);
      71      end_--;
      72    }
      73  
      74    void Resize(uptr size) {
      75      if (size == 0) {
      76        end_ = begin_;
      77        return;
      78      }
      79      uptr old_size = Size();
      80      if (size <= old_size) {
      81        end_ = begin_ + size;
      82        return;
      83      }
      84      EnsureSize(size);
      85      if (old_size < size) {
      86        internal_memset(&begin_[old_size], 0,
      87                        sizeof(begin_[old_size]) * (size - old_size));
      88      }
      89    }
      90  
      91   private:
      92    T *begin_;
      93    T *end_;
      94    T *last_;
      95  
      96    void EnsureSize(uptr size) {
      97      if (size <= Size())
      98        return;
      99      if (size <= (uptr)(last_ - begin_)) {
     100        end_ = begin_ + size;
     101        return;
     102      }
     103      uptr cap0 = last_ - begin_;
     104      uptr cap = cap0 * 5 / 4;  // 25% growth
     105      if (cap == 0)
     106        cap = 16;
     107      if (cap < size)
     108        cap = size;
     109      T *p = (T*)InternalAlloc(cap * sizeof(T));
     110      if (cap0) {
     111        internal_memcpy(p, begin_, cap0 * sizeof(T));
     112        InternalFree(begin_);
     113      }
     114      begin_ = p;
     115      end_ = begin_ + size;
     116      last_ = begin_ + cap;
     117    }
     118  
     119    Vector(const Vector&);
     120    void operator=(const Vector&);
     121  };
     122  }  // namespace __sanitizer
     123  
     124  #endif  // #ifndef SANITIZER_VECTOR_H