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