17ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany//===-- tsan_vector.h -------------------------------------------*- C++ -*-===//
27ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany//
37ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany//                     The LLVM Compiler Infrastructure
47ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany//
57ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// This file is distributed under the University of Illinois Open Source
67ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// License. See LICENSE.TXT for details.
77ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany//
87ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany//===----------------------------------------------------------------------===//
97ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany//
107ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// This file is a part of ThreadSanitizer (TSan), a race detector.
117ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany//
127ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany//===----------------------------------------------------------------------===//
137ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany
147ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany// Low-fat STL-like vector container.
157ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany
167ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany#ifndef TSAN_VECTOR_H
177ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany#define TSAN_VECTOR_H
187ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany
197ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany#include "tsan_defs.h"
207ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany#include "tsan_mman.h"
217ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany
227ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryanynamespace __tsan {
237ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany
247ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryanytemplate<typename T>
257ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryanyclass Vector {
267ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany public:
277ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  explicit Vector(MBlockType typ)
287ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany      : typ_(typ)
297ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany      , begin_()
307ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany      , end_()
317ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany      , last_() {
327ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  }
337ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany
347ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  ~Vector() {
357ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    if (begin_)
367ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany      internal_free(begin_);
377ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  }
387ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany
397ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  void Reset() {
407ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    if (begin_)
417ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany      internal_free(begin_);
427ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    begin_ = 0;
437ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    end_ = 0;
447ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    last_ = 0;
457ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  }
467ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany
477ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  uptr Size() const {
487ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    return end_ - begin_;
497ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  }
507ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany
517ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  T &operator[](uptr i) {
527ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    DCHECK_LT(i, end_ - begin_);
537ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    return begin_[i];
547ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  }
557ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany
567ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  const T &operator[](uptr i) const {
577ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    DCHECK_LT(i, end_ - begin_);
587ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    return begin_[i];
597ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  }
607ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany
612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines  T *PushBack() {
627ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    EnsureSize(Size() + 1);
632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines    T *p = &end_[-1];
642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines    internal_memset(p, 0, sizeof(*p));
652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines    return p;
662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines  }
672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines
682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines  T *PushBack(const T& v) {
692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines    EnsureSize(Size() + 1);
702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines    T *p = &end_[-1];
712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines    internal_memcpy(p, &v, sizeof(*p));
722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines    return p;
737ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  }
747ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany
758b30c254a63a7421dd81d13dee086a54c4ca134bDmitry Vyukov  void PopBack() {
768b30c254a63a7421dd81d13dee086a54c4ca134bDmitry Vyukov    DCHECK_GT(end_, begin_);
778b30c254a63a7421dd81d13dee086a54c4ca134bDmitry Vyukov    end_--;
788b30c254a63a7421dd81d13dee086a54c4ca134bDmitry Vyukov  }
798b30c254a63a7421dd81d13dee086a54c4ca134bDmitry Vyukov
807ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  void Resize(uptr size) {
816a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines    if (size == 0) {
826a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines      end_ = begin_;
836a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines      return;
846a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines    }
857ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    uptr old_size = Size();
867ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    EnsureSize(size);
877ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    if (old_size < size) {
887ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany      for (uptr i = old_size; i < size; i++)
892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines        internal_memset(&begin_[i], 0, sizeof(begin_[i]));
907ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    }
917ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  }
927ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany
937ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany private:
947ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  const MBlockType typ_;
957ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  T *begin_;
967ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  T *end_;
977ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  T *last_;
987ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany
997ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  void EnsureSize(uptr size) {
1007ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    if (size <= Size())
1017ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany      return;
1027ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    if (size <= (uptr)(last_ - begin_)) {
1037ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany      end_ = begin_ + size;
1047ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany      return;
1057ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    }
1067ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    uptr cap0 = last_ - begin_;
1076a211c5814e25d6745a5058cc0e499e5235d3821Stephen Hines    uptr cap = cap0 * 5 / 4;  // 25% growth
1087ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    if (cap == 0)
1097ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany      cap = 16;
1107ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    if (cap < size)
1117ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany      cap = size;
1127ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    T *p = (T*)internal_alloc(typ_, cap * sizeof(T));
1137ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    if (cap0) {
114d51a1a10cba87be50e9ada9fa21337c387edb237Dmitry Vyukov      internal_memcpy(p, begin_, cap0 * sizeof(T));
1157ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany      internal_free(begin_);
1167ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    }
1177ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    begin_ = p;
1187ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    end_ = begin_ + size;
1197ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany    last_ = begin_ + cap;
1207ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  }
1217ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany
1227ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  Vector(const Vector&);
1237ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany  void operator=(const Vector&);
1247ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany};
125ba5e99668e3030cc5bab357a04271a1bdbac209cAlexey Samsonov}  // namespace __tsan
1267ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany
1277ac41484ea322e0ea5774df681660269f5dc321eKostya Serebryany#endif  // #ifndef TSAN_VECTOR_H
128