contrib/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   explicit Vector()
  27       : begin_()
  28       , end_()
  29       , last_() {
  30   }
  31
  32   ~Vector() {
  33     if (begin_)
  34       InternalFree(begin_);
  35   }
  36
  37   void Reset() {
  38     if (begin_)
  39       InternalFree(begin_);
  40     begin_ = 0;
  41     end_ = 0;
  42     last_ = 0;
  43   }
  44
  45   uptr Size() const {
  46     return end_ - begin_;
  47   }
  48
  49   T &operator[](uptr i) {
  50     DCHECK_LT(i, end_ - begin_);
  51     return begin_[i];
  52   }
  53
  54   const T &operator[](uptr i) const {
  55     DCHECK_LT(i, end_ - begin_);
  56     return begin_[i];
  57   }
  58
  59   T *PushBack() {
  60     EnsureSize(Size() + 1);
  61     T *p = &end_[-1];
  62     internal_memset(p, 0, sizeof(*p));
  63     return p;
  64   }
  65
  66   T *PushBack(const T& v) {
  67     EnsureSize(Size() + 1);
  68     T *p = &end_[-1];
  69     internal_memcpy(p, &v, sizeof(*p));
  70     return p;
  71   }
  72
  73   void PopBack() {
  74     DCHECK_GT(end_, begin_);
  75     end_--;
  76   }
  77
  78   void Resize(uptr size) {
  79     if (size == 0) {
  80       end_ = begin_;
  81       return;
  82     }
  83     uptr old_size = Size();
  84     if (size <= old_size) {
  85       end_ = begin_ + size;
  86       return;
  87     }
  88     EnsureSize(size);
  89     if (old_size < size) {
  90       for (uptr i = old_size; i < size; i++)
  91         internal_memset(&begin_[i], 0, sizeof(begin_[i]));
  92     }
  93   }
  94
  95  private:
  96   T *begin_;
  97   T *end_;
  98   T *last_;
  99
 100   void EnsureSize(uptr size) {
 101     if (size <= Size())
 102       return;
 103     if (size <= (uptr)(last_ - begin_)) {
 104       end_ = begin_ + size;
 105       return;
 106     }
 107     uptr cap0 = last_ - begin_;
 108     uptr cap = cap0 * 5 / 4;  // 25% growth
 109     if (cap == 0)
 110       cap = 16;
 111     if (cap < size)
 112       cap = size;
 113     T *p = (T*)InternalAlloc(cap * sizeof(T));
 114     if (cap0) {
 115       internal_memcpy(p, begin_, cap0 * sizeof(T));
 116       InternalFree(begin_);
 117     }
 118     begin_ = p;
 119     end_ = begin_ + size;
 120     last_ = begin_ + cap;
 121   }
 122
 123   Vector(const Vector&);
 124   void operator=(const Vector&);
 125 };
 126 }  // namespace __sanitizer
 127
 128 #endif  // #ifndef SANITIZER_VECTOR_H