1 //===-- esan_circular_buffer.h ----------------------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file is a part of EfficiencySanitizer, a family of performance tuners. 11 // 12 // Circular buffer data structure. 13 //===----------------------------------------------------------------------===// 14 15 #include "sanitizer_common/sanitizer_common.h" 16 17 namespace __esan { 18 19 // A circular buffer for POD data whose memory is allocated using mmap. 20 // There are two usage models: one is to use initialize/free (for global 21 // instances) and the other is to use placement new with the 22 // constructor and to call the destructor or free (they are equivalent). 23 template<typename T> 24 class CircularBuffer { 25 public: 26 // To support global instances we cannot initialize any field in the 27 // default constructor. CircularBuffer()28 explicit CircularBuffer() {} CircularBuffer(uptr BufferCapacity)29 CircularBuffer(uptr BufferCapacity) { 30 initialize(BufferCapacity); 31 WasConstructed = true; 32 } ~CircularBuffer()33 ~CircularBuffer() { 34 if (WasConstructed) // Else caller will call free() explicitly. 35 free(); 36 } initialize(uptr BufferCapacity)37 void initialize(uptr BufferCapacity) { 38 Capacity = BufferCapacity; 39 // MmapOrDie rounds up to the page size for us. 40 Data = (T *)MmapOrDie(Capacity * sizeof(T), "CircularBuffer"); 41 StartIdx = 0; 42 Count = 0; 43 WasConstructed = false; 44 } free()45 void free() { 46 UnmapOrDie(Data, Capacity * sizeof(T)); 47 } 48 T &operator[](uptr Idx) { 49 CHECK_LT(Idx, Count); 50 uptr ArrayIdx = (StartIdx + Idx) % Capacity; 51 return Data[ArrayIdx]; 52 } 53 const T &operator[](uptr Idx) const { 54 CHECK_LT(Idx, Count); 55 uptr ArrayIdx = (StartIdx + Idx) % Capacity; 56 return Data[ArrayIdx]; 57 } push_back(const T & Item)58 void push_back(const T &Item) { 59 CHECK_GT(Capacity, 0); 60 uptr ArrayIdx = (StartIdx + Count) % Capacity; 61 Data[ArrayIdx] = Item; 62 if (Count < Capacity) 63 ++Count; 64 else 65 StartIdx = (StartIdx + 1) % Capacity; 66 } back()67 T &back() { 68 CHECK_GT(Count, 0); 69 uptr ArrayIdx = (StartIdx + Count - 1) % Capacity; 70 return Data[ArrayIdx]; 71 } pop_back()72 void pop_back() { 73 CHECK_GT(Count, 0); 74 --Count; 75 } size()76 uptr size() const { 77 return Count; 78 } clear()79 void clear() { 80 StartIdx = 0; 81 Count = 0; 82 } empty()83 bool empty() const { return size() == 0; } 84 85 private: 86 CircularBuffer(const CircularBuffer&); 87 void operator=(const CircularBuffer&); 88 89 bool WasConstructed; 90 T *Data; 91 uptr Capacity; 92 uptr StartIdx; 93 uptr Count; 94 }; 95 96 } // namespace __esan 97