Jamoma API  0.6.0.a19
LockFreeFIFO.h
1 /* Copyright © 2007 Apple Inc. All Rights Reserved.
2 
3  Disclaimer: IMPORTANT: This Apple software is supplied to you by
4  Apple Inc. ("Apple") in consideration of your agreement to the
5  following terms, and your use, installation, modification or
6  redistribution of this Apple software constitutes acceptance of these
7  terms. If you do not agree with these terms, please do not use,
8  install, modify or redistribute this Apple software.
9 
10  In consideration of your agreement to abide by the following terms, and
11  subject to these terms, Apple grants you a personal, non-exclusive
12  license, under Apple's copyrights in this original Apple software (the
13  "Apple Software"), to use, reproduce, modify and redistribute the Apple
14  Software, with or without modifications, in source and/or binary forms;
15  provided that if you redistribute the Apple Software in its entirety and
16  without modifications, you must retain this notice and the following
17  text and disclaimers in all such redistributions of the Apple Software.
18  Neither the name, trademarks, service marks or logos of Apple Inc.
19  may be used to endorse or promote products derived from the Apple
20  Software without specific prior written permission from Apple. Except
21  as expressly stated in this notice, no other rights or licenses, express
22  or implied, are granted by Apple herein, including but not limited to
23  any patent rights that may be infringed by your derivative works or by
24  other works in which the Apple Software may be incorporated.
25 
26  The Apple Software is provided by Apple on an "AS IS" basis. APPLE
27  MAKES NO WARRANTIES, EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION
28  THE IMPLIED WARRANTIES OF NON-INFRINGEMENT, MERCHANTABILITY AND FITNESS
29  FOR A PARTICULAR PURPOSE, REGARDING THE APPLE SOFTWARE OR ITS USE AND
30  OPERATION ALONE OR IN COMBINATION WITH YOUR PRODUCTS.
31 
32  IN NO EVENT SHALL APPLE BE LIABLE FOR ANY SPECIAL, INDIRECT, INCIDENTAL
33  OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
34  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
35  INTERRUPTION) ARISING IN ANY WAY OUT OF THE USE, REPRODUCTION,
36  MODIFICATION AND/OR DISTRIBUTION OF THE APPLE SOFTWARE, HOWEVER CAUSED
37  AND WHETHER UNDER THEORY OF CONTRACT, TORT (INCLUDING NEGLIGENCE),
38  STRICT LIABILITY OR OTHERWISE, EVEN IF APPLE HAS BEEN ADVISED OF THE
39  POSSIBILITY OF SUCH DAMAGE.
40 */
41 #include <Carbon/Carbon.h>
42 
43 
44 template <class ITEM>
45 class LockFreeFIFOWithFree
46 {
47  LockFreeFIFOWithFree(); // private, unimplemented.
48 public:
49  LockFreeFIFOWithFree(UInt32 inMaxSize)
50  : mReadIndex(0), mWriteIndex(0), mFreeIndex(0)
51  {
52  //assert(IsPowerOfTwo(inMaxSize));
53  mItems = new ITEM[inMaxSize];
54  mMask = inMaxSize - 1;
55  }
56 
57  ~LockFreeFIFOWithFree()
58  {
59  delete [] mItems;
60  }
61 
62 
63  void Reset()
64  {
65  FreeItems();
66  mReadIndex = 0;
67  mWriteIndex = 0;
68  mFreeIndex = 0;
69  }
70 
71  ITEM* WriteItem()
72  {
73  //printf("WriteItem %d %d\n", mReadIndex, mWriteIndex);
74  FreeItems(); // free items on the write thread.
75  UInt32 nextWriteIndex = (mWriteIndex + 1) & mMask;
76  if (nextWriteIndex == mFreeIndex) return NULL;
77  return &mItems[mWriteIndex];
78  }
79 
80  ITEM* ReadItem()
81  {
82  //printf("ReadItem %d %d\n", mReadIndex, mWriteIndex);
83  if (mReadIndex == mWriteIndex) return NULL;
84  return &mItems[mReadIndex];
85  }
86 
87  // the CompareAndSwap will always succeed. We use CompareAndSwap because it calls the PowerPC sync instruction,
88  // plus any processor bug workarounds for various CPUs.
89  void AdvanceWritePtr() { CompareAndSwap(mWriteIndex, (mWriteIndex + 1) & mMask, (UInt32*)&mWriteIndex); }
90  void AdvanceReadPtr() { CompareAndSwap(mReadIndex, (mReadIndex + 1) & mMask, (UInt32*)&mReadIndex); }
91 
92 private:
93  ITEM* FreeItem()
94  {
95  if (mFreeIndex == mReadIndex) return NULL;
96  return &mItems[mFreeIndex];
97  }
98  void AdvanceFreePtr() { CompareAndSwap(mFreeIndex, (mFreeIndex + 1) & mMask, (UInt32*)&mFreeIndex); }
99 
100  void FreeItems()
101  {
102  ITEM* item;
103  while ((item = FreeItem()) != NULL)
104  {
105  item->Free();
106  AdvanceFreePtr();
107  }
108  }
109 
110  volatile UInt32 mReadIndex, mWriteIndex, mFreeIndex;
111  UInt32 mMask;
112  ITEM *mItems;
113 };
114 
115 
116 
117 // Same as above but no free.
118 
119 template <class ITEM>
120 class LockFreeFIFO
121 {
122  LockFreeFIFO(); // private, unimplemented.
123 public:
124  LockFreeFIFO(UInt32 inMaxSize)
125  : mReadIndex(0), mWriteIndex(0)
126  {
127  //assert(IsPowerOfTwo(inMaxSize));
128  mItems = new ITEM[inMaxSize];
129  mMask = inMaxSize - 1;
130  }
131 
132  ~LockFreeFIFO()
133  {
134  delete [] mItems;
135  }
136 
137  void Reset()
138  {
139  mReadIndex = 0;
140  mWriteIndex = 0;
141  }
142 
143  ITEM* WriteItem()
144  {
145  UInt32 nextWriteIndex = (mWriteIndex + 1) & mMask;
146  if (nextWriteIndex == mReadIndex) return NULL;
147  return &mItems[mWriteIndex];
148  }
149 
150  ITEM* ReadItem()
151  {
152  if (mReadIndex == mWriteIndex) return NULL;
153  return &mItems[mReadIndex];
154  }
155 
156  // the CompareAndSwap will always succeed. We use CompareAndSwap because it calls the PowerPC sync instruction,
157  // plus any processor bug workarounds for various CPUs.
158  void AdvanceWritePtr() { CompareAndSwap(mWriteIndex, (mWriteIndex + 1) & mMask, (UInt32*)&mWriteIndex); }
159  void AdvanceReadPtr() { CompareAndSwap(mReadIndex, (mReadIndex + 1) & mMask, (UInt32*)&mReadIndex); }
160 
161 private:
162 
163  volatile UInt32 mReadIndex, mWriteIndex;
164  UInt32 mMask;
165  ITEM *mItems;
166 };
167