1 /* Copyright 2016, Ableton AG, Berlin. All rights reserved. 2 * 3 * This program is free software: you can redistribute it and/or modify 4 * it under the terms of the GNU General Public License as published by 5 * the Free Software Foundation, either version 2 of the License, or 6 * (at your option) any later version. 7 * 8 * This program is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * GNU General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public License 14 * along with this program. If not, see <http://www.gnu.org/licenses/>. 15 * 16 * If you would like to incorporate Link into a proprietary software application, 17 * please contact <link-devs@ableton.com>. 18 */ 19 20 #pragma once 21 22 #include <ableton/link/Optional.hpp> 23 #include <array> 24 #include <atomic> 25 #include <cassert> 26 27 namespace ableton 28 { 29 namespace link 30 { 31 32 // Single producer, single consumer lockfree Fifo 33 34 template <typename Type, std::size_t size> 35 class CircularFifo 36 { 37 public: CircularFifo()38 CircularFifo() 39 : tail(0) 40 , head(0) 41 { 42 assert(head.is_lock_free() && tail.is_lock_free()); 43 } 44 push(Type item)45 bool push(Type item) 46 { 47 const auto currentTail = tail.load(); 48 const auto nextTail = nextIndex(currentTail); 49 if (nextTail != head.load()) 50 { 51 data[currentTail] = std::move(item); 52 tail.store(nextTail); 53 return true; 54 } 55 return false; 56 } 57 pop()58 Optional<Type> pop() 59 { 60 const auto currentHead = head.load(); 61 if (currentHead == tail.load()) 62 { 63 return {}; 64 } 65 66 auto item = data[currentHead]; 67 head.store(nextIndex(currentHead)); 68 return Optional<Type>{std::move(item)}; 69 } 70 isEmpty() const71 bool isEmpty() const 72 { 73 return tail == head; 74 } 75 76 private: nextIndex(const size_t index) const77 size_t nextIndex(const size_t index) const 78 { 79 return (index + 1) % (size + 1); 80 } 81 previousIndex(const size_t index) const82 size_t previousIndex(const size_t index) const 83 { 84 return (index + size) % (size + 1); 85 } 86 87 std::atomic_size_t tail; 88 std::atomic_size_t head; 89 std::array<Type, size + 1> data; 90 }; 91 92 } // namespace link 93 } // namespace ableton 94