circular_queue.h

Go to the documentation of this file.
00001 /** @file rutz/circular_queue.h */
00002 
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 8249 2007-04-12 06:03:40Z rjpeters $
00010 // $HeadURL: svn://isvn.usc.edu/software/invt/trunk/saliency/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 //
00031 ///////////////////////////////////////////////////////////////////////
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 {
00042   /// Circular fixed-size queue; T must have a default constructor
00043   /** This class is designed to be used in a situation where one
00044       thread is filling the queue while another thread is emptying the
00045       queue; in that situation, no locks should be needed to access
00046       the queue safely. */
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 
00064     /// Get the number of spaces in the queue (not all of which may be currently occupied)
00065     size_t size() const { return m_q_size; }
00066 
00067     /// Returns true of the pop succeeded
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 
00086     /// Returns true if the push succeeded
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 8249 2007-04-12 06:03:40Z rjpeters $ $HeadURL: svn://isvn.usc.edu/software/invt/trunk/saliency/src/rutz/circular_queue.h $";
00124 #endif // !GROOVX_RUTZ_CIRCULAR_QUEUE_H_UTC20061005174345DEFINED
Generated on Sun May 8 08:42:09 2011 for iLab Neuromorphic Vision Toolkit by  doxygen 1.6.3