CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!
CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!
Path: blob/master/Common/Data/Collections/FixedSizeQueue.h
Views: 1401
// Copyright (C) 2003 Dolphin Project.12// This program is free software: you can redistribute it and/or modify3// it under the terms of the GNU General Public License as published by4// the Free Software Foundation, version 2.0 or later versions.56// This program is distributed in the hope that it will be useful,7// but WITHOUT ANY WARRANTY; without even the implied warranty of8// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the9// GNU General Public License 2.0 for more details.1011// A copy of the GPL 2.0 should have been included with the program.12// If not, see http://www.gnu.org/licenses/1314// Official SVN repository and contact information can be found at15// http://code.google.com/p/dolphin-emu/1617#pragma once1819#include <cstring>20#include "Common/MemoryUtil.h"21#include "Common/Serialize/Serializer.h"2223// STL-look-a-like interface, but name is mixed case to distinguish it clearly from the24// real STL classes.2526// Not fully featured, no safety checking yet. Add features as needed.2728template <class T, int N>29class FixedSizeQueue {30public:31FixedSizeQueue() {32storage_ = new T[N];33clear();34}3536~FixedSizeQueue() {37delete [] storage_;38}3940// Disallow copies.41FixedSizeQueue(FixedSizeQueue &other) = delete;42FixedSizeQueue& operator=(const FixedSizeQueue &other) = delete;4344void clear() {45head_ = 0;46tail_ = 0;47count_ = 0;48// Not entirely necessary, but keeps things clean.49memset(storage_, 0, sizeof(T) * N);50}5152void push(T t) {53storage_[tail_] = t;54tail_++;55if (tail_ == N)56tail_ = 0;57count_++;58}5960// Gets pointers to write to directly.61void pushPointers(size_t size, T **dest1, size_t *sz1, T **dest2, size_t *sz2) {62if (tail_ + (int)size < N) {63*dest1 = &storage_[tail_];64*sz1 = size;65tail_ += (int)size;66if (tail_ == N) tail_ = 0;67*dest2 = 0;68*sz2 = 0;69} else {70*dest1 = &storage_[tail_];71*sz1 = N - tail_;72tail_ = (int)(size - *sz1);73*dest2 = &storage_[0];74*sz2 = tail_;75}76count_ += (int)size;77}7879void popPointers(size_t size, const T **src1, size_t *sz1, const T **src2, size_t *sz2) {80if ((int)size > count_) size = count_;8182if (head_ + size < N) {83*src1 = &storage_[head_];84*sz1 = size;85head_ += (int)size;86if (head_ == N) head_ = 0;87*src2 = 0;88*sz2 = 0;89} else {90*src1 = &storage_[head_];91*sz1 = N - head_;92head_ = (int)(size - *sz1);93*src2 = &storage_[0];94*sz2 = head_;95}96count_ -= (int)size;97}9899void pop() {100head_++;101if (head_ == N)102head_ = 0;103count_--;104}105106/*107void push_array(const T *ptr, size_t num) {108// TODO: memcpy109for (size_t i = 0; i < num; i++) {110push(ptr[i]);111}112}113114void pop_array(T *outptr, size_t num) {115for (size_t i = 0; i < num; i++) {116outptr[i] = front();117pop();118}119}*/120121T pop_front() {122const T &temp = storage_[head_];123pop();124return temp;125}126127T &front() { return storage_[head_]; }128129const T &front() const { return storage_[head_]; }130131size_t size() const {132return count_;133}134135size_t capacity() const {136return N;137}138139int room() const {140return N - count_;141}142143bool empty() {144return count_ == 0;145}146147void DoState(PointerWrap &p) {148int size = N;149Do(p, size);150if (size != N)151{152ERROR_LOG(Log::Common, "Savestate failure: Incompatible queue size.");153return;154}155// TODO: This is quite wasteful, could just store the actual data. Would be slightly more complex though.156DoArray<T>(p, storage_, N);157Do(p, head_);158Do(p, tail_);159Do(p, count_);160p.DoMarker("FixedSizeQueue");161}162163private:164T *storage_;165int head_;166int tail_;167int count_; // sacrifice 4 bytes for a simpler implementation. may optimize away in the future.168};169170171// I'm not sure this is 100% safe but it might be "Good Enough" :)172// TODO: Use this, maybe make it safer first by using proper atomics173// instead of volatile174template<class T, int blockSize, int numBlocks>175class LockFreeBlockQueue {176public:177LockFreeBlockQueue() {178curReadBlock = 0;179curWriteBlock = 0;180for (size_t i = 0; i < numBlocks; i++) {181blocks[i] = new T[blockSize];182}183}184~LockFreeBlockQueue() {185for (size_t i = 0; i < numBlocks; i++) {186delete [] blocks[i];187}188}189190// Write to the returned pointer then call EndPush to finish the push.191T *BeginPush() {192return blocks[curWriteBlock];193}194void EndPush() {195curWriteBlock++;196if (curWriteBlock == NUM_BLOCKS)197curWriteBlock = 0;198}199200bool CanPush() {201int nextBlock = curWriteBlock + 1;202if (nextBlock == NUM_BLOCKS) nextBlock = 0;203return nextBlock != curReadBlock;204}205206bool CanPop() { return curReadBlock != curWriteBlock; }207208// Read from the returned pointer then call EndPush to finish the pop.209T *BeginPop() {210return blocks[curReadBlock];211}212void EndPop() {213curReadBlock++;214if (curReadBlock == NUM_BLOCKS)215curReadBlock = 0;216}217218private:219enum { NUM_BLOCKS = 16 };220T **blocks[NUM_BLOCKS];221222volatile int curReadBlock;223volatile int curWriteBlock;224};225226227