1/* (c) Magnus Auvinen. See licence.txt in the root of the distribution for more information. */
2/* If you are missing that file, acquire a complete release at teeworlds.com. */
3#include "ringbuffer.h"
4
5CRingBufferBase::CItem *CRingBufferBase::NextBlock(CItem *pItem)
6{
7 if(pItem->m_pNext)
8 return pItem->m_pNext;
9 return m_pFirst;
10}
11
12CRingBufferBase::CItem *CRingBufferBase::PrevBlock(CItem *pItem)
13{
14 if(pItem->m_pPrev)
15 return pItem->m_pPrev;
16 return m_pLast;
17}
18
19CRingBufferBase::CItem *CRingBufferBase::MergeBack(CItem *pItem)
20{
21 // make sure that this block and previous block is free
22 if(!pItem->m_Free || !pItem->m_pPrev || !pItem->m_pPrev->m_Free)
23 return pItem;
24
25 // merge the blocks
26 pItem->m_pPrev->m_Size += pItem->m_Size;
27 pItem->m_pPrev->m_pNext = pItem->m_pNext;
28
29 // fixup pointers
30 if(pItem->m_pNext)
31 pItem->m_pNext->m_pPrev = pItem->m_pPrev;
32 else
33 m_pLast = pItem->m_pPrev;
34
35 if(pItem == m_pProduce)
36 m_pProduce = pItem->m_pPrev;
37
38 if(pItem == m_pConsume)
39 m_pConsume = pItem->m_pPrev;
40
41 // return the current block
42 return pItem->m_pPrev;
43}
44
45void CRingBufferBase::Init(void *pMemory, int Size, int Flags)
46{
47 m_Size = Size / sizeof(CItem) * sizeof(CItem);
48 m_pBuffer = static_cast<CItem *>(pMemory);
49 m_Flags = Flags;
50 Clear();
51}
52
53void CRingBufferBase::Clear()
54{
55 m_pFirst = m_pBuffer;
56 m_pFirst->m_pPrev = nullptr;
57 m_pFirst->m_pNext = nullptr;
58 m_pFirst->m_Free = 1;
59 m_pFirst->m_Size = m_Size;
60 m_pLast = m_pFirst;
61 m_pProduce = m_pFirst;
62 m_pConsume = m_pFirst;
63}
64
65void *CRingBufferBase::Allocate(int Size)
66{
67 int WantedSize = (Size + sizeof(CItem) + sizeof(CItem) - 1) / sizeof(CItem) * sizeof(CItem);
68 CItem *pBlock = nullptr;
69
70 // check if we even can fit this block
71 if(WantedSize > m_Size)
72 return nullptr;
73
74 while(true)
75 {
76 // check for space
77 if(m_pProduce->m_Free)
78 {
79 if(m_pProduce->m_Size >= WantedSize)
80 pBlock = m_pProduce;
81 else
82 {
83 // wrap around to try to find a block
84 if(m_pFirst->m_Free && m_pFirst->m_Size >= WantedSize)
85 pBlock = m_pFirst;
86 }
87 }
88
89 if(pBlock)
90 break;
91 else
92 {
93 // we have no block, check our policy and see what todo
94 if(m_Flags & FLAG_RECYCLE)
95 {
96 if(!PopFirst())
97 return nullptr;
98 }
99 else
100 return nullptr;
101 }
102 }
103
104 // okey, we have our block
105
106 // split the block if needed
107 if(pBlock->m_Size > WantedSize + (int)sizeof(CItem))
108 {
109 CItem *pNewItem = (CItem *)((char *)pBlock + WantedSize);
110 pNewItem->m_pPrev = pBlock;
111 pNewItem->m_pNext = pBlock->m_pNext;
112 if(pNewItem->m_pNext)
113 pNewItem->m_pNext->m_pPrev = pNewItem;
114 pBlock->m_pNext = pNewItem;
115
116 pNewItem->m_Free = 1;
117 pNewItem->m_Size = pBlock->m_Size - WantedSize;
118 pBlock->m_Size = WantedSize;
119
120 if(!pNewItem->m_pNext)
121 m_pLast = pNewItem;
122 }
123
124 // set next block
125 m_pProduce = NextBlock(pItem: pBlock);
126
127 // set as used and return the item pointer
128 pBlock->m_Free = 0;
129 return (void *)(pBlock + 1);
130}
131
132void CRingBufferBase::SetPopCallback(std::function<void(void *pCurrent)> PopCallback)
133{
134 m_PopCallback = std::move(PopCallback);
135}
136
137int CRingBufferBase::PopFirst()
138{
139 if(m_pConsume->m_Free)
140 return 0;
141
142 if(m_PopCallback)
143 {
144 m_PopCallback(m_pConsume + 1);
145 }
146
147 // set the free flag
148 m_pConsume->m_Free = 1;
149
150 // previous block is also free, merge them
151 m_pConsume = MergeBack(pItem: m_pConsume);
152
153 // advance the consume pointer
154 m_pConsume = NextBlock(pItem: m_pConsume);
155 while(m_pConsume->m_Free && m_pConsume != m_pProduce)
156 {
157 m_pConsume = MergeBack(pItem: m_pConsume);
158 m_pConsume = NextBlock(pItem: m_pConsume);
159 }
160
161 // in the case that we have caught up with the produce pointer
162 // we might stand on a free block so merge em
163 MergeBack(pItem: m_pConsume);
164 return 1;
165}
166
167void *CRingBufferBase::Prev(void *pCurrent)
168{
169 CItem *pItem = ((CItem *)pCurrent) - 1;
170
171 while(true)
172 {
173 pItem = PrevBlock(pItem);
174 if(pItem == m_pProduce)
175 return nullptr;
176 if(!pItem->m_Free)
177 return pItem + 1;
178 }
179}
180
181void *CRingBufferBase::Next(void *pCurrent)
182{
183 CItem *pItem = ((CItem *)pCurrent) - 1;
184
185 while(true)
186 {
187 pItem = NextBlock(pItem);
188 if(pItem == m_pProduce)
189 return nullptr;
190 if(!pItem->m_Free)
191 return pItem + 1;
192 }
193}
194
195void *CRingBufferBase::First()
196{
197 if(m_pConsume->m_Free)
198 return nullptr;
199 return (void *)(m_pConsume + 1);
200}
201
202void *CRingBufferBase::Last()
203{
204 return Prev(pCurrent: m_pProduce + 1);
205}
206