compiler-rt/lib/sanitizer_common/sanitizer_vector.h

   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