1 /*
2 Copyright (C) 2016 Apple Inc. All Rights Reserved.
3 See LICENSE.txt for this sample’s licensing information
4 
5 Abstract:
6 Part of Core Audio AUInstrument Base Classes
7 */
8 
9 #include <libkern/OSAtomic.h>
10 
11 template <class ITEM>
12 class LockFreeFIFOWithFree
13 {
14 	LockFreeFIFOWithFree(); // private, unimplemented.
15 public:
LockFreeFIFOWithFree(UInt32 inMaxSize)16 	LockFreeFIFOWithFree(UInt32 inMaxSize)
17 		: mReadIndex(0), mWriteIndex(0), mFreeIndex(0)
18 	{
19 		//assert(IsPowerOfTwo(inMaxSize));
20 		mItems = new ITEM[inMaxSize];
21 		mMask = inMaxSize - 1;
22 	}
23 
~LockFreeFIFOWithFree()24 	~LockFreeFIFOWithFree()
25 	{
26 		delete [] mItems;
27 	}
28 
29 
Reset()30 	void Reset()
31 	{
32 		FreeItems();
33 		mReadIndex = 0;
34 		mWriteIndex = 0;
35 		mFreeIndex = 0;
36 	}
37 
WriteItem()38 	ITEM* WriteItem()
39 	{
40 		//printf("WriteItem %d %d\n", mReadIndex, mWriteIndex);
41 		FreeItems(); // free items on the write thread.
42 		int32_t nextWriteIndex = (mWriteIndex + 1) & mMask;
43 		if (nextWriteIndex == mFreeIndex) return NULL;
44 		return &mItems[mWriteIndex];
45 	}
46 
ReadItem()47 	ITEM* ReadItem()
48 	{
49 		//printf("ReadItem %d %d\n", mReadIndex, mWriteIndex);
50 		if (mReadIndex == mWriteIndex) return NULL;
51 		return &mItems[mReadIndex];
52 	}
AdvanceWritePtr()53 	void AdvanceWritePtr() { OSAtomicCompareAndSwap32(mWriteIndex, (mWriteIndex + 1) & mMask, &mWriteIndex); }
AdvanceReadPtr()54 	void AdvanceReadPtr()  { OSAtomicCompareAndSwap32(mReadIndex,  (mReadIndex  + 1) & mMask, &mReadIndex); }
55 private:
FreeItem()56 	ITEM* FreeItem()
57 	{
58 		if (mFreeIndex == mReadIndex) return NULL;
59 		return &mItems[mFreeIndex];
60 	}
AdvanceFreePtr()61 	void AdvanceFreePtr() { OSAtomicCompareAndSwap32(mFreeIndex, (mFreeIndex + 1) & mMask, &mFreeIndex); }
62 
FreeItems()63 	void FreeItems()
64 	{
65 		ITEM* item;
66 		while ((item = FreeItem()) != NULL)
67 		{
68 			item->Free();
69 			AdvanceFreePtr();
70 		}
71 	}
72 
73 	volatile int32_t mReadIndex, mWriteIndex, mFreeIndex;
74 	int32_t mMask;
75 	ITEM *mItems;
76 };
77 
78 
79 
80 // Same as above but no free.
81 
82 template <class ITEM>
83 class LockFreeFIFO
84 {
85 	LockFreeFIFO(); // private, unimplemented.
86 public:
LockFreeFIFO(UInt32 inMaxSize)87 	LockFreeFIFO(UInt32 inMaxSize)
88 		: mReadIndex(0), mWriteIndex(0)
89 	{
90 		//assert(IsPowerOfTwo(inMaxSize));
91 		mItems = new ITEM[inMaxSize];
92 		mMask = inMaxSize - 1;
93 	}
94 
~LockFreeFIFO()95 	~LockFreeFIFO()
96 	{
97 		delete [] mItems;
98 	}
99 
Reset()100 	void Reset()
101 	{
102 		mReadIndex = 0;
103 		mWriteIndex = 0;
104 	}
105 
WriteItem()106 	ITEM* WriteItem()
107 	{
108 		int32_t nextWriteIndex = (mWriteIndex + 1) & mMask;
109 		if (nextWriteIndex == mReadIndex) return NULL;
110 		return &mItems[mWriteIndex];
111 	}
112 
ReadItem()113 	ITEM* ReadItem()
114 	{
115 		if (mReadIndex == mWriteIndex) return NULL;
116 		return &mItems[mReadIndex];
117 	}
118 
119 		// the CompareAndSwap will always succeed. We use CompareAndSwap because it calls the PowerPC sync instruction,
120 		// plus any processor bug workarounds for various CPUs.
AdvanceWritePtr()121 	void AdvanceWritePtr() { OSAtomicCompareAndSwap32(mWriteIndex, (mWriteIndex + 1) & mMask, &mWriteIndex); }
AdvanceReadPtr()122 	void AdvanceReadPtr()  { OSAtomicCompareAndSwap32(mReadIndex,  (mReadIndex  + 1) & mMask, &mReadIndex); }
123 
124 private:
125 
126 	volatile int32_t mReadIndex, mWriteIndex;
127 	int32_t mMask;
128 	ITEM *mItems;
129 };
130 
131