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 {
81 pBlock = m_pProduce;
82 }
83 else
84 {
85 // wrap around to try to find a block
86 if(m_pFirst->m_Free && m_pFirst->m_Size >= WantedSize)
87 pBlock = m_pFirst;
88 }
89 }
90
91 if(pBlock)
92 {
93 break;
94 }
95 else
96 {
97 // we have no block, check our policy and see what todo
98 if(m_Flags & FLAG_RECYCLE)
99 {
100 if(!PopFirst())
101 return nullptr;
102 }
103 else
104 {
105 return nullptr;
106 }
107 }
108 }
109
110 // okey, we have our block
111
112 // split the block if needed
113 if(pBlock->m_Size > WantedSize + (int)sizeof(CItem))
114 {
115 CItem *pNewItem = (CItem *)((char *)pBlock + WantedSize);
116 pNewItem->m_pPrev = pBlock;
117 pNewItem->m_pNext = pBlock->m_pNext;
118 if(pNewItem->m_pNext)
119 pNewItem->m_pNext->m_pPrev = pNewItem;
120 pBlock->m_pNext = pNewItem;
121
122 pNewItem->m_Free = 1;
123 pNewItem->m_Size = pBlock->m_Size - WantedSize;
124 pBlock->m_Size = WantedSize;
125
126 if(!pNewItem->m_pNext)
127 m_pLast = pNewItem;
128 }
129
130 // set next block
131 m_pProduce = NextBlock(pItem: pBlock);
132
133 // set as used and return the item pointer
134 pBlock->m_Free = 0;
135 return (void *)(pBlock + 1);
136}
137
138void CRingBufferBase::SetPopCallback(std::function<void(void *pCurrent)> PopCallback)
139{
140 m_PopCallback = std::move(PopCallback);
141}
142
143int CRingBufferBase::PopFirst()
144{
145 if(m_pConsume->m_Free)
146 return 0;
147
148 if(m_PopCallback)
149 {
150 m_PopCallback(m_pConsume + 1);
151 }
152
153 // set the free flag
154 m_pConsume->m_Free = 1;
155
156 // previous block is also free, merge them
157 m_pConsume = MergeBack(pItem: m_pConsume);
158
159 // advance the consume pointer
160 m_pConsume = NextBlock(pItem: m_pConsume);
161 while(m_pConsume->m_Free && m_pConsume != m_pProduce)
162 {
163 m_pConsume = MergeBack(pItem: m_pConsume);
164 m_pConsume = NextBlock(pItem: m_pConsume);
165 }
166
167 // in the case that we have caught up with the produce pointer
168 // we might stand on a free block so merge em
169 MergeBack(pItem: m_pConsume);
170 return 1;
171}
172
173void *CRingBufferBase::Prev(void *pCurrent)
174{
175 CItem *pItem = ((CItem *)pCurrent) - 1;
176
177 while(true)
178 {
179 pItem = PrevBlock(pItem);
180 if(pItem == m_pProduce)
181 return nullptr;
182 if(!pItem->m_Free)
183 return pItem + 1;
184 }
185}
186
187void *CRingBufferBase::Next(void *pCurrent)
188{
189 CItem *pItem = ((CItem *)pCurrent) - 1;
190
191 while(true)
192 {
193 pItem = NextBlock(pItem);
194 if(pItem == m_pProduce)
195 return nullptr;
196 if(!pItem->m_Free)
197 return pItem + 1;
198 }
199}
200
201void *CRingBufferBase::First()
202{
203 if(m_pConsume->m_Free)
204 return nullptr;
205 return (void *)(m_pConsume + 1);
206}
207
208void *CRingBufferBase::Last()
209{
210 return Prev(pCurrent: m_pProduce + 1);
211}
212