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