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