fifo.h

Go to the documentation of this file.
00001 //
00002 //  Copyright (c) 1996-2006 by Autodesk, Inc.
00003 //
00004 //  By using this code, you are agreeing to the terms and conditions of
00005 //  the License Agreement included in the documentation for this code.
00006 //
00007 //  AUTODESK MAKES NO WARRANTIES, EXPRESS OR IMPLIED, AS TO THE CORRECTNESS
00008 //  OF THIS CODE OR ANY DERIVATIVE WORKS WHICH INCORPORATE IT. AUTODESK
00009 //  PROVIDES THE CODE ON AN "AS-IS" BASIS AND EXPLICITLY DISCLAIMS ANY
00010 //  LIABILITY, INCLUDING CONSEQUENTIAL AND INCIDENTAL DAMAGES FOR ERRORS,
00011 //  OMISSIONS, AND OTHER PROBLEMS IN THE CODE.
00012 //
00013 //  Use, duplication, or disclosure by the U.S. Government is subject to
00014 //  restrictions set forth in FAR 52.227-19 (Commercial Computer Software
00015 //  Restricted Rights) and DFAR 252.227-7013(c)(1)(ii) (Rights in Technical
00016 //  Data and Computer Software), as applicable.
00017 //
00018 #if !defined FIFO_HEADER
00019 #define FIFO_HEADER
00020 
00024 
00025 #include "whiptk/whipcore.h"
00026 
00027 #define WD_FIFO_SLACK_FRACTION 0.25
00028 
00030 template<class _ItemType>
00031 class WT_FIFO
00032 {
00033 private:
00034 
00035     int            m_size;         // The number of generic items being held in the FIFO.
00036     int            m_capacity;     // The number of items that can fit in the current FIFO.
00037     int            m_start;        // The position of the first item in the FIFO ring buffer.
00038     _ItemType *    m_buffer;       // The FIFO buffer itself.
00039 
00040     WT_FIFO (WT_FIFO const &)
00041       : m_size(0)
00042       , m_capacity(0)
00043       , m_start(0)
00044       , m_buffer(WD_Null)
00045     {
00046         WD_Complain ("cannot copy WT_FIFO");
00047     } // prohibited
00048 
00049     WT_FIFO & operator= (WT_FIFO const &)
00050     {
00051         WD_Complain ("cannot assign WT_FIFO");
00052         return *this;
00053     } // prohibited
00054 
00055 public:
00056 
00058     WT_FIFO()
00059         : m_size(0)
00060         , m_capacity(0)
00061         , m_start(0)
00062         , m_buffer(WD_Null)
00063     { }
00064 
00066     WT_FIFO(int initial_size)
00067         : m_size(0)
00068         , m_capacity(initial_size + 1)
00069         , m_start(0)
00070         , m_buffer(WD_Null)
00071     {
00072         m_buffer = new _ItemType[initial_size + 1];
00073         if (!m_buffer)
00074             throw WT_Result::Out_Of_Memory_Error;
00075     }
00076 
00078     virtual ~WT_FIFO()
00079     {
00080         delete []m_buffer;
00081     }
00082 public:
00084     int size() const
00085     {
00086         return m_size;
00087     }
00088 
00090     WT_Result add(
00091         int add_size, 
00092         _ItemType const * add_buffer 
00093         );
00095 
00096     void fetch(
00097         int fetch_size, 
00098         int start_item, 
00099         _ItemType * fetch_buffer 
00100         ) const;
00102 
00103     void remove(
00104         int remove_size, 
00105         _ItemType * remove_buffer 
00106         );
00108 
00109     void remove(
00110         int remove_size
00111         );
00113     void clear_all();
00115 
00119     int pointer_to_index(
00120         _ItemType const * ptr 
00121         ) const;
00123 
00125     _ItemType &  item(int index) const;
00127     void       pop();
00128 
00129 };
00130 
00131 template<class _ItemType>
00132 WT_Result WT_FIFO<_ItemType>::add(int add_size, _ItemType const * add_buffer)
00133 {
00134     WD_Assert(add_size > 0);
00135     WD_Assert(add_buffer);
00136 
00137     // Will we overflow the current buffer?
00138     if ( (m_size + add_size) > m_capacity)
00139     {
00140         // We're about to overflow the FIFO buffer, so let's allocate
00141         // a bigger FIFO buffer and copy the old one into it.
00142         _ItemType *    new_buffer;
00143         int            new_capacity;
00144 
00145         new_capacity  = m_size + add_size + 1;
00146         new_capacity += (int)(new_capacity * WD_FIFO_SLACK_FRACTION);
00147         new_buffer = new _ItemType[new_capacity];
00148         if (!new_buffer)
00149             return WT_Result::Out_Of_Memory_Error;
00150 
00151         if ( (m_start + m_size) <= m_capacity)
00152         {
00153             // The data doesn't wrap around the ring buffer in the orig. buffer,
00154             // so it is an easy copy to the new buffer.
00155             //WD_COPY_MEMORY(m_buffer + m_start, m_size, new_buffer);
00156             _ItemType *    source = m_buffer + m_start;
00157             _ItemType *    dest   = new_buffer;
00158             for (int loop = 0; loop < m_size; loop++)
00159                 *dest++ = *source++;
00160         }
00161         else
00162         {
00163             int    split_size = m_capacity - m_start;
00164             // The data is wrapped around in the source ring buffer.  Need to do
00165             // more work to copy it to the new buffer.
00166             // WD_COPY_MEMORY(m_buffer + m_start, split_size         , new_buffer);
00167             // WD_COPY_MEMORY(m_buffer          , m_size - split_size, new_buffer + split_size);
00168             _ItemType *     source = m_buffer + m_start;
00169             _ItemType *     dest   = new_buffer;
00170             int             loop;
00171 
00172             for (loop = 0; loop < split_size; loop++)
00173                 *dest++ = *source++;
00174 
00175             source = m_buffer;
00176             for (loop = 0; loop < (m_size - split_size); loop++)
00177                 *dest++ = *source++;
00178         }
00179 
00180         m_start = 0;
00181         m_capacity = new_capacity;
00182         delete []m_buffer;
00183         m_buffer = new_buffer;
00184     } // If orig buffer would have overflowed
00185 
00186     // Now add the new data to the buffer
00187 
00188     // Find the tail end where we start adding to the FIFO.  Note that the "tail" might
00189     // be "behind" the start if we've wrapped around the ring buffer.
00190     int tail = m_start + m_size;
00191     if (tail >= m_capacity)
00192         tail -= m_capacity;
00193 
00194     if ( (tail + add_size) <= m_capacity)
00195     {
00196         // The new data wont wrap around the ring buffer,
00197         // so it is an easy copy into the buffer.
00198         // WD_COPY_MEMORY(add_buffer, add_size, m_buffer + tail);
00199         _ItemType const *    source = add_buffer;
00200         _ItemType *        dest   = m_buffer + tail;
00201         for (int loop = 0; loop < add_size; loop++)
00202             *dest++ = *source++;
00203     }
00204     else
00205     {
00206         int    split_size = m_capacity - tail;
00207         // The new data will wrap around the ring buffer.  Need to do
00208         // more work to copy it in two chunks.
00209         // WD_COPY_MEMORY(add_buffer             , split_size           , m_buffer + tail);
00210         // WD_COPY_MEMORY(add_buffer + split_size, add_size - split_size, m_buffer       );
00211         _ItemType const *   source = add_buffer;
00212         _ItemType *         dest   = m_buffer + tail;
00213         int                 loop;
00214 
00215         for (loop = 0; loop < split_size; loop++)
00216             *dest++ = *source++;
00217 
00218         dest = m_buffer;
00219         for (loop = 0; loop < (add_size - split_size); loop++)
00220             *dest++ = *source++;
00221     }
00222 
00223     m_size += add_size;
00224 
00225     return WT_Result::Success;
00226 }
00227 
00228 template<class _ItemType>
00229 void WT_FIFO<_ItemType>::fetch(int fetch_size, int start_item, _ItemType * users_buffer) const
00230 {
00231     // Make sure that this FIFO has at least the amount of data that was asked for.
00232     WD_Assert((fetch_size + start_item) <= m_size);
00233     WD_Assert(users_buffer);
00234 
00235     int    pseudo_start = m_start + start_item;
00236     if (pseudo_start >= m_capacity)
00237         pseudo_start -= m_capacity;
00238 
00239     // Copy the data out of the FIFO and into the user's buffer.
00240     if ( (pseudo_start + fetch_size) <= m_capacity)
00241     {
00242         // The *requested* data doesn't wrap around the ring buffer,
00243         // so it is an easy copy to the user's buffer.
00244         _ItemType *    source = m_buffer + pseudo_start;
00245         _ItemType *    dest   = users_buffer;
00246         for (int loop = 0; loop < fetch_size; loop++)
00247             *dest++ = *source++;
00248     }
00249     else
00250     {
00251         int    split_size = m_capacity - pseudo_start;
00252         // The data is wrapped around in the FIFO ring buffer.  Need to do
00253         // more work to copy it to the user's buffer.
00254         _ItemType *     source = m_buffer + pseudo_start;
00255         _ItemType *     dest   = users_buffer;
00256         int             loop;
00257 
00258         for (loop = 0; loop < split_size; loop++)
00259             *dest++ = *source++;
00260 
00261         source = m_buffer;
00262         for (loop = 0; loop < (fetch_size - split_size); loop++)
00263             *dest++ = *source++;
00264     }
00265 }
00266 
00267 template<class _ItemType>
00268 void WT_FIFO<_ItemType>::remove(int remove_size, _ItemType * remove_buffer)
00269 {
00270     fetch(remove_size, 0, remove_buffer);
00271     // Now adjust for the fact that data was removed from the ring buffer.
00272     remove(remove_size);
00273 }
00274 
00275 
00276 template<class _ItemType>
00277 void WT_FIFO<_ItemType>::remove(int remove_size)
00278 {
00279     // Make sure that this FIFO has at least the amount of data that was asked for.
00280     WD_Assert(remove_size <= m_size);
00281     WD_Assert(remove_size >= 0);
00282 
00283 
00284     // Adjust for the fact that data was removed from the ring buffer.
00285     m_start += remove_size;
00286     if (m_start >= m_capacity)
00287         m_start -= m_capacity;
00288 
00289     m_size -= remove_size;
00290 
00291     if (!m_size)
00292         m_start = 0;
00293 
00294     WD_Assert (m_size >= 0);
00295     WD_Assert (m_start >= 0);
00296     WD_Assert (m_start < m_capacity);
00297 }
00298 
00299 template<class _ItemType>
00300 void WT_FIFO<_ItemType>::pop()
00301 {
00302     // pop the last added item off the fifo queue
00303     // (a little lifo routine)
00304     WD_Assert(1 <= m_size);
00305 
00306     m_size--;
00307     if (!m_size)
00308         m_start = 0;
00309 
00310     WD_Assert (m_size >= 0);
00311     WD_Assert (m_start >= 0);
00312     WD_Assert (m_start < m_capacity);
00313 }
00314 
00315 template<class _ItemType>
00316 _ItemType & WT_FIFO<_ItemType>::item(int index) const
00317 {
00318     // Make sure that this FIFO has at least the amount of data that was asked for.
00319     WD_Assert(index < m_size);
00320 
00321     // Copy the data out of the FIFO and into the user's buffer.
00322     int    position = m_start + index;
00323     if (position >= m_capacity)
00324     {
00325         // The *requested* data wrapped around the ring buffer.
00326         position -= m_capacity;
00327     }
00328 
00329     return m_buffer[position];
00330 }
00331 
00332 template<class _ItemType>
00333 void    WT_FIFO<_ItemType>::clear_all()
00334 {
00335     m_start = 0;
00336     m_size = 0;
00337 }
00338 
00339 template<class _ItemType>
00340 int WT_FIFO<_ItemType>::pointer_to_index(_ItemType const * ptr) const
00341 {
00342 
00343     WD_Assert(ptr >= m_buffer);
00344     WD_Assert(ptr < (m_buffer + m_capacity));
00345 
00346     int    pseudo_index = static_cast<int>(ptr - m_buffer);
00347     WD_Assert(pseudo_index == (ptr - m_buffer));
00348 
00349     // See if we wrap around or not
00350     if (pseudo_index < m_start)
00351         pseudo_index += m_capacity;
00352 
00353     WD_Assert(pseudo_index < (m_start + m_size));
00354     return pseudo_index - m_start;
00355 }
00356 
00357 #endif // FIFO_HEADER

Generated on Tue Jan 6 22:41:12 2009 for Autodesk DWF Whip 2D Toolkit by  doxygen 1.4.5