circular_queue.h

Go to the documentation of this file.
00001 
00003 
00004 //
00005 // Copyright (c) 2005-2007 University of Southern California
00006 // Rob Peters <rjpeters at usc dot edu>
00007 //
00008 // created: Thu Oct  5 10:43:45 2006
00009 // commit: $Id: circular_queue.h 10065 2007-04-12 05:54:56Z rjpeters $
00010 // $HeadURL: file:///lab/rjpeters/svnrepo/code/trunk/groovx/src/rutz/circular_queue.h $
00011 //
00012 // --------------------------------------------------------------------
00013 //
00014 // This file is part of GroovX.
00015 //   [http://www.klab.caltech.edu/rjpeters/groovx/]
00016 //
00017 // GroovX is free software; you can redistribute it and/or modify it
00018 // under the terms of the GNU General Public License as published by
00019 // the Free Software Foundation; either version 2 of the License, or
00020 // (at your option) any later version.
00021 //
00022 // GroovX is distributed in the hope that it will be useful, but
00023 // WITHOUT ANY WARRANTY; without even the implied warranty of
00024 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00025 // General Public License for more details.
00026 //
00027 // You should have received a copy of the GNU General Public License
00028 // along with GroovX; if not, write to the Free Software Foundation,
00029 // Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
00030 //
00032 
00033 #ifndef GROOVX_RUTZ_CIRCULAR_QUEUE_H_UTC20061005174345_DEFINED
00034 #define GROOVX_RUTZ_CIRCULAR_QUEUE_H_UTC20061005174345_DEFINED
00035 
00036 #include "rutz/atomic.h"
00037 
00038 #include <cstddef> // for size_t
00039 
00040 namespace rutz
00041 {
00043 
00047   template <class T>
00048   class circular_queue
00049   {
00050   public:
00051     circular_queue(const size_t n)
00052       :
00053       m_q(new entry[n == 0 ? 1 : n]),
00054       m_q_size(n == 0 ? 1 : n),
00055       m_front(0),
00056       m_back(0)
00057     {}
00058 
00059     ~circular_queue()
00060     {
00061       delete [] m_q;
00062     }
00063 
00065     size_t size() const { return m_q_size; }
00066 
00068     bool pop_front(T& dest)
00069     {
00070       if (m_q[m_front].valid.atomic_get() == 0)
00071         // the queue is empty right now:
00072         return false;
00073 
00074       dest = m_q[m_front].value;
00075 
00076       m_q[m_front].value = T();
00077       m_q[m_front].valid.atomic_set(0);
00078       if (m_front+1 == m_q_size)
00079         m_front = 0;
00080       else
00081         ++m_front;
00082 
00083       return true;
00084     }
00085 
00087     bool push_back(const T& val)
00088     {
00089       if (m_q[m_back].valid.atomic_get() != 0)
00090         // we don't have any space in the queue for another entry
00091         // right now:
00092         return false;
00093 
00094       m_q[m_back].value = val;
00095       m_q[m_back].valid.atomic_set(1);
00096       if (m_back+1 == m_q_size)
00097         m_back = 0;
00098       else
00099         ++m_back;
00100 
00101       return true;
00102     }
00103 
00104   private:
00105     circular_queue(const circular_queue&);
00106     circular_queue& operator=(const circular_queue&);
00107 
00108     struct entry
00109     {
00110       entry() : value(), valid() {}
00111 
00112       T value;
00113       rutz::atomic_int_t valid;
00114     };
00115 
00116     entry* const m_q;
00117     size_t m_q_size;
00118     size_t m_front;
00119     size_t m_back;
00120   };
00121 }
00122 
00123 static const char vcid_groovx_rutz_circular_queue_h_utc20061005174345[] = "$Id: circular_queue.h 10065 2007-04-12 05:54:56Z rjpeters $ $HeadURL: file:///lab/rjpeters/svnrepo/code/trunk/groovx/src/rutz/circular_queue.h $";
00124 #endif // !GROOVX_RUTZ_CIRCULAR_QUEUE_H_UTC20061005174345DEFINED

The software described here is Copyright (c) 1998-2005, Rob Peters.
This page was generated Wed Dec 3 06:49:40 2008 by Doxygen version 1.5.5.