//============================================================================= // fifo.cpp // Simple first-in/first-out (FIFO) queue template class functions. // // Notes // Macro 'NO_NAMESPACES' should be set to nonzero (true) if the compiler // does not support namespaces. // // Macro 'NO_AND' should be set to nonzero (true) if the compiler does not // support the 'and' alternate spelling keyword. // // History // 1.00, 1998-10-17, David R Tribble. // First cut. // // Author // David R. Tribble // dtribble@technologist.com // http://www.flash.net/~dtribble // // Copyright ©1998 by David R. Tribble, all rights reserved. // Permission is hereby granted to use, distribute, and modify this source // code provided that the original copyright and authorship notices remain // intact. //----------------------------------------------------------------------------- // Identification static const char drt_fifo_cpp_id[] = "@(#)fifo.cpp 1.00 1998-10-17 dtribble"; // Special includes #ifdef _DLL #define drt_fifo_lib #endif #include "fifo.hpp" // System includes #if DrtFifo_TEST #include #endif // Compiler deficiencies #if NO_AND #ifndef and #define and && #define or || #define not ! #endif #endif // Namespace #if !NO_NAMESPACES namespace Drt { #endif //----------------------------------------------------------------------------- // Shared (static) class constants //----------------------------------------------------------------------------- #if DrtFifoImpl_VERS/100 != 1 #error DrtFifoImpl_VERS has changed #endif /*static*/ const int DrtFifoImpl::VERS = DrtFifoImpl_VERS; // Class version number //----------------------------------------------------------------------------- // Class member functions //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- // DrtFifoImpl::~DrtFifoImpl() // Destructor. // // Caveats // This is not thread-safe. //----------------------------------------------------------------------------- /*void*/ DrtFifoImpl::~DrtFifoImpl() { #if DrtFifoImpl_VERS != 100 #error DrtFifoImpl_VERS has changed #endif #if DrtFifo_TEST printf("Impl::~Impl(%08p)\n", this); #endif // Destroy all of the items in this queue clear(); } //----------------------------------------------------------------------------- // DrtFifoImpl::DrtFifoImpl() // Default constructor. //----------------------------------------------------------------------------- /*DrtFifoImpl*/ DrtFifoImpl::DrtFifoImpl(): m_head(NULL), m_size(0) { #if DrtFifoImpl_VERS != 100 #error DrtFifoImpl_VERS has changed #endif #if DrtFifo_TEST printf("Impl::Impl(%08p)\n", this); #endif // No other members to initialize } //----------------------------------------------------------------------------- // DrtFifoImpl::DrtFifoImpl() // Copy constructor. // // Caveats // This is not thread-safe. //----------------------------------------------------------------------------- /*DrtFifoImpl*/ DrtFifoImpl::DrtFifoImpl(const DrtFifoImpl &r): m_head(NULL), m_size(0) { #if DrtFifoImpl_VERS != 100 #error DrtFifoImpl_VERS has changed #endif #if DrtFifo_TEST printf("Impl::Impl(%08p: %08p)\n", this, &r); #endif // Copy members from 'r' copy(r); } //----------------------------------------------------------------------------- // DrtFifoImpl::put() // Adds item 'e' to the head of this queue. // // Returns // True if successful, otherwise false. // // Caveats // This is not thread-safe. //----------------------------------------------------------------------------- bool DrtFifoImpl::put(ElemPtr e) { #if DrtFifoImpl_VERS/100 != 1 #error DrtFifoImpl_VERS has changed #endif #if DrtFifo_TEST printf("Impl::put(%08p: [%u]:%08p)\n", this, m_size, e); #endif // Create a container for the inserted item Bucket * b; b = new(nothrow) Bucket; #if DrtFifo_TEST printf("Impl::put(): new Bucket[%u]=%08p\n", m_size, b); #endif if (b == NULL) { // Allocation failure #if DrtFifo_TEST printf("Impl::put(): new() failed, size=%u\n", sizeof(Bucket)); #endif return (false); } // Insert item 'e' onto the head of this queue m_size++; b->m_elem = e; b->m_prev = b; if (m_head != NULL) { b->m_prev = m_head->m_prev; m_head->m_prev = b; } m_head = b; return (true); } //----------------------------------------------------------------------------- // DrtFifoImpl::get() // Retrieves the item at the tail of this queue, removing it from the // queue. // // Returns // Pointer to the item at the tail of the queue if there is one, otherwise // null. // // Caveats // This is not thread-safe. //----------------------------------------------------------------------------- DrtFifoImpl::ElemPtr DrtFifoImpl::get() { #if DrtFifoImpl_VERS/100 != 1 #error DrtFifoImpl_VERS has changed #endif #if DrtFifo_TEST printf("Impl::get(%08p: [%u-1])\n", this, m_size); #endif // Check for an empty queue if (m_head == NULL) { // This queue is empty #if DrtFifo_TEST printf("Impl::get(): Empty\n"); #endif return (NULL); } // Retrieve the container for the tail item in this queue Bucket * b; b = m_head->m_prev; #if DrtFifo_TEST printf("Impl::get(): Bucket[%u-1]=%08p: %08p)\n", m_size, b, (b ? b->m_elem : NULL)); #endif // Remove the tail item from this queue m_size--; if (m_head == b) m_head = NULL; else m_head->m_prev = b->m_prev; // Retrieve the element from the container ElemPtr t; t = b->m_elem; // Destroy the tail item's container b->m_elem = NULL; b->m_prev = NULL; delete b; b = NULL; return (t); } //----------------------------------------------------------------------------- // DrtFifoImpl::size() // Determines the current number of items in this queue. // // Returns // The number of items in this queue, or zero if it is empty. //----------------------------------------------------------------------------- unsigned DrtFifoImpl::size() const { #if DrtFifoImpl_VERS/100 != 1 #error DrtFifoImpl_VERS has changed #endif #if DrtFifo_TEST printf("Impl::size(%08p: [%u])\n", this, m_size); #endif // Retrieve the current size of this queue return (m_size); } //----------------------------------------------------------------------------- // DrtFifoImpl::isEmpty() // Determines if this queue is currently empty. // // Returns // True if this queue has no items in it, otherwise false. //----------------------------------------------------------------------------- bool DrtFifoImpl::isEmpty() const { #if DrtFifoImpl_VERS/100 != 1 #error DrtFifoImpl_VERS has changed #endif #if DrtFifo_TEST printf("Impl::isEmpty(%08p: [%u])\n", this, m_size); #endif // Examine the current size of this queue return (m_size == 0); } //----------------------------------------------------------------------------- // DrtFifoImpl::clear() // Removes all of the items in this queue, making it empty. // // Caveats // This is not thread-safe. //----------------------------------------------------------------------------- void DrtFifoImpl::clear() { #if DrtFifoImpl_VERS/100 != 1 #error DrtFifoImpl_VERS has changed #endif #if DrtFifo_TEST printf("Impl::clear(%08p: [%u])\n", this, m_size); #endif // Destroy all of the items in this queue while (m_head != NULL) { Bucket * b; // Unlink and destroy the head item in this queue #if DrtFifo_TEST printf("Impl::~Impl(): delete %08p\n", m_head); #endif b = m_head->m_prev; if (b == m_head) b = NULL; m_head->m_elem = NULL; m_head->m_prev = NULL; delete m_head; m_head = b; } m_size = 0; } //----------------------------------------------------------------------------- // DrtFifoImpl::copy() // Copies the contents of queue 'r' into this queue. // // Returns // True if successful, otherwise false. // // Notes // The previous contents of this queue, if any, are removed before queue // 'r' is copied. // // Caveats // The resulting copy of queue 'r' is a list of items that each point to // the same elements (objects of type Elem) that the original list in // queue 'r' pointed to. In other words, only the element pointers are // replicated, not the elements themselves. // // This is not thread-safe. //----------------------------------------------------------------------------- bool DrtFifoImpl::copy(const DrtFifoImpl &r) { #if DrtFifoImpl_VERS/100 != 1 #error DrtFifoImpl_VERS has changed #endif #if DrtFifo_TEST printf("Impl::copy(%08p: %08p:[%u])\n", this, &r, r.m_size); #endif // Remove the current contents of this queue, if any clear(); // Copy the items from queue 'r' to this queue Bucket * n; Bucket * o; o = r.m_head; while (o != NULL) { // Create a bucket for the copy of the current item in 'r' n = new(nothrow) Bucket; #if DrtFifo_TEST printf("Impl::copy(): new Bucket[%u]=%08p: %08p\n", m_size, n, o->m_elem); #endif if (n == NULL) { // Allocation failure #if DrtFifo_TEST printf("Impl::copy(): new() failed, size=%u\n", sizeof(Bucket)); #endif return (false); } // Replicate the contents of the bucket in 'r' n->m_elem = o->m_elem; // Note: Only the element pointer is copied, // and not the element itself // Insert the replicated item bucket into this queue if (m_head != NULL) { n->m_prev = m_head->m_prev; m_head->m_prev = n; } else n->m_prev = n; m_head = n; m_size++; // Set up for next item in queue 'r' o = o->m_prev; if (o == r.m_head) break; } // Reposition the head of this queue if (m_head != NULL) m_head = m_head->m_prev; return (true); } // Namespace #if !NO_NAMESPACES } // namespace Drt #endif // Settings for Emacs: // Local Variables: // tab-width: 8 // End: // End fifo.cpp