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 | |
5 | CRingBufferBase::CItem *CRingBufferBase::NextBlock(CItem *pItem) |
6 | { |
7 | if(pItem->m_pNext) |
8 | return pItem->m_pNext; |
9 | return m_pFirst; |
10 | } |
11 | |
12 | CRingBufferBase::CItem *CRingBufferBase::PrevBlock(CItem *pItem) |
13 | { |
14 | if(pItem->m_pPrev) |
15 | return pItem->m_pPrev; |
16 | return m_pLast; |
17 | } |
18 | |
19 | CRingBufferBase::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 | |
45 | void 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 | |
59 | void *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 | |
126 | void CRingBufferBase::SetPopCallback(std::function<void(void *pCurrent)> PopCallback) |
127 | { |
128 | m_PopCallback = std::move(PopCallback); |
129 | } |
130 | |
131 | int 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 | |
161 | void *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 | |
175 | void *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 | |
189 | void *CRingBufferBase::First() |
190 | { |
191 | if(m_pConsume->m_Free) |
192 | return 0; |
193 | return (void *)(m_pConsume + 1); |
194 | } |
195 | |
196 | void *CRingBufferBase::Last() |
197 | { |
198 | return Prev(pCurrent: m_pProduce + 1); |
199 | } |
200 |