diff options
Diffstat (limited to 'src/engine/e_ringbuffer.cpp')
| -rw-r--r-- | src/engine/e_ringbuffer.cpp | 194 |
1 files changed, 194 insertions, 0 deletions
diff --git a/src/engine/e_ringbuffer.cpp b/src/engine/e_ringbuffer.cpp new file mode 100644 index 00000000..eb8a8af4 --- /dev/null +++ b/src/engine/e_ringbuffer.cpp @@ -0,0 +1,194 @@ +#include <base/system.h> + +#include "e_ringbuffer.h" + +CRingBufferBase::CItem *CRingBufferBase::NextBlock(CItem *pItem) +{ + if(pItem->m_pNext) + return pItem->m_pNext; + return m_pFirst; +} + +CRingBufferBase::CItem *CRingBufferBase::PrevBlock(CItem *pItem) +{ + if(pItem->m_pPrev) + return pItem->m_pPrev; + return m_pLast; +} + +CRingBufferBase::CItem *CRingBufferBase::MergeBack(CItem *pItem) +{ + /* make sure that this block and previous block is free */ + if(!pItem->m_Free || !pItem->m_pPrev || !pItem->m_pPrev->m_Free) + return pItem; + + /* merge the blocks */ + pItem->m_pPrev->m_Size += pItem->m_Size; + pItem->m_pPrev->m_pNext = pItem->m_pNext; + + /* fixup pointers */ + if(pItem->m_pNext) + pItem->m_pNext->m_pPrev = pItem->m_pPrev; + else + m_pLast = pItem->m_pPrev; + + if(pItem == m_pProduce) + m_pProduce = pItem->m_pPrev; + + if(pItem == m_pConsume) + m_pConsume = pItem->m_pPrev; + + /* return the current block */ + return pItem->m_pPrev; +} + +void CRingBufferBase::Init(void *pMemory, int Size, int Flags) +{ + mem_zero(pMemory, Size); + m_Size = (Size)/sizeof(CItem)*sizeof(CItem); + m_pFirst = (CItem *)pMemory; + m_pFirst->m_Free = 1; + m_pFirst->m_Size = m_Size; + m_pLast = m_pFirst; + m_pProduce = m_pFirst; + m_pConsume = m_pFirst; + m_Flags = Flags; + +} + +void *CRingBufferBase::Allocate(int Size) +{ + int WantedSize = (Size+sizeof(CItem)+sizeof(CItem)-1)/sizeof(CItem)*sizeof(CItem); + CItem *pBlock = 0; + + /* check if we even can fit this block */ + if(WantedSize > m_Size) + return 0; + + while(1) + { + /* check for space */ + if(m_pProduce->m_Free) + { + if(m_pProduce->m_Size >= WantedSize) + pBlock = m_pProduce; + else + { + /* wrap around to try to find a block */ + if(m_pFirst->m_Free && m_pFirst->m_Size >= WantedSize) + pBlock = m_pFirst; + } + } + + if(pBlock) + break; + else + { + /* we have no block, check our policy and see what todo */ + if(m_Flags&FLAG_RECYCLE) + { + if(!PopFirst()) + return 0; + } + else + return 0; + } + } + + /* okey, we have our block */ + + /* split the block if needed */ + if(pBlock->m_Size > WantedSize) + { + CItem *pNewItem = (CItem *)((char *)pBlock + WantedSize); + pNewItem->m_pPrev = pBlock; + pNewItem->m_pNext = pBlock->m_pNext; + if(pNewItem->m_pNext) + pNewItem->m_pNext->m_pPrev = pNewItem; + pBlock->m_pNext = pNewItem; + + pNewItem->m_Free = 1; + pNewItem->m_Size = pBlock->m_Size - WantedSize; + pBlock->m_Size = WantedSize; + + if(!pNewItem->m_pNext) + m_pLast = pNewItem; + } + + + /* set next block */ + m_pProduce = NextBlock(pBlock); + + /* set as used and return the item pointer */ + pBlock->m_Free = 0; + return (void *)(pBlock+1); +} + +int CRingBufferBase::PopFirst() +{ + if(m_pConsume->m_Free) + return 0; + + /* set the free flag */ + m_pConsume->m_Free = 1; + + /* previous block is also free, merge them */ + m_pConsume = MergeBack(m_pConsume); + + /* advance the consume pointer */ + m_pConsume = NextBlock(m_pConsume); + while(m_pConsume->m_Free && m_pConsume != m_pProduce) + { + m_pConsume = MergeBack(m_pConsume); + m_pConsume = NextBlock(m_pConsume); + } + + /* in the case that we have catched up with the produce pointer */ + /* we might stand on a free block so merge em */ + MergeBack(m_pConsume); + return 1; +} + + +void *CRingBufferBase::Prev(void *pCurrent) +{ + CItem *pItem = ((CItem *)pCurrent) - 1; + + while(1) + { + pItem = PrevBlock(pItem); + if(pItem == m_pProduce) + return 0; + if(!pItem->m_Free) + return pItem+1; + } +} + +void *CRingBufferBase::Next(void *pCurrent) +{ + CItem *pItem = ((CItem *)pCurrent) - 1; + + while(1) + { + pItem = NextBlock(pItem); + if(pItem == m_pProduce) + return 0; + if(!pItem->m_Free) + return pItem+1; + } +} + +void *CRingBufferBase::First() +{ + if(m_pConsume->m_Free) + return 0; + return (void *)(m_pConsume+1); +} + +void *CRingBufferBase::Last() +{ + if(!m_pProduce->m_Free) + return m_pProduce+1; + return Prev(m_pProduce+1); +} + |