home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2006 March / Gamestar_82_2006-03_dvd.iso / DVDStar / Editace / quake4_sdkv10.exe / source / idlib / containers / Queue.h < prev    next >
C/C++ Source or Header  |  2005-11-14  |  5KB  |  176 lines
  1.  
  2. #ifndef __QUEUE_H__
  3. #define __QUEUE_H__
  4.  
  5. /*
  6. ===============================================================================
  7.  
  8.     Queue template
  9.  
  10. ===============================================================================
  11. */
  12.  
  13. #define idQueue( type, next )        idQueueTemplate<type, (int)&(((type*)NULL)->next)>
  14.  
  15. template< class type, int nextOffset >
  16. class idQueueTemplate {
  17. public:
  18.                             idQueueTemplate( void );
  19.  
  20.     void                    Add( type *element );
  21.     type *                    Get( void );
  22.  
  23. private:
  24.     type *                    first;
  25.     type *                    last;
  26. };
  27.  
  28. #define QUEUE_NEXT_PTR( element )        (*((type**)(((byte*)element)+nextOffset)))
  29.  
  30. template< class type, int nextOffset >
  31. idQueueTemplate<type,nextOffset>::idQueueTemplate( void ) {
  32.     first = last = NULL;
  33. }
  34.  
  35. template< class type, int nextOffset >
  36. void idQueueTemplate<type,nextOffset>::Add( type *element ) {
  37.     QUEUE_NEXT_PTR(element) = NULL;
  38.     if ( last ) {
  39.         QUEUE_NEXT_PTR(last) = element;
  40.     } else {
  41.         first = element;
  42.     }
  43.     last = element;
  44. }
  45.  
  46. template< class type, int nextOffset >
  47. type *idQueueTemplate<type,nextOffset>::Get( void ) {
  48.     type *element;
  49.  
  50.     element = first;
  51.     if ( element ) {
  52.         first = QUEUE_NEXT_PTR(first);
  53.         if ( last == element ) {
  54.             last = NULL;
  55.         }
  56.         QUEUE_NEXT_PTR(element) = NULL;
  57.     }
  58.     return element;
  59. }
  60.  
  61. /*
  62. ===============================================================================
  63.  
  64.     Raven Queue template
  65.  
  66. ===============================================================================
  67. */
  68. template<class TYPE, int CAPACITY>
  69. class rvQueue
  70. {
  71.     TYPE            mData[CAPACITY];                                // Total capacity of the queue
  72.     int                mNewest;                                        // Head
  73.     int                mOldest;                                        // Tail
  74.     int                mSize;                                            // Size... yes, this could be calculated...
  75.  
  76. public:
  77.     rvQueue()                                    {clear();}
  78.     int        size()                                {return mSize;}
  79.     bool    empty()                                {return mSize==0;}
  80.     bool    full()                                {return mSize>=CAPACITY;}
  81.     int        begin()                                {return (full())?(mOldest+1):(mOldest);}
  82.     int        end()                                {return mNewest-1;}
  83.     void    clear()                                {mNewest = mOldest = mSize = 0;}
  84.     bool    valid(int i)                        {return ((mNewest>=mOldest)?(i>=mOldest && i<mNewest):(!(i>=mNewest && i<mOldest)));}
  85.     void    inc(int& i)                            {i = (i>=(CAPACITY-1))?(0):(i+1);}
  86.     TYPE&    first()                                {assert(!empty()); return mData[mOldest];}
  87.     TYPE&    last()                                {assert(!empty()); return mData[mNewest-1];}
  88.     TYPE&    operator[] (int i)                    {assert(valid(i)); return mData[i];}
  89.     int        push(const TYPE& value)                {assert(!full()); mData[mNewest]=value; inc(mNewest); return (mSize++);}
  90.     int        pop()                                {assert(!empty());                        inc(mOldest); return (mSize--);}
  91. };
  92.  
  93. /*
  94. ===============================================================================
  95.  
  96.     Raven Bit Vector Template
  97.  
  98. ===============================================================================
  99. */
  100. template<int CAPACITY>
  101. class rvBits
  102. {
  103.     enum
  104.     {
  105.         BITS_SHIFT        = 5,                                        // 5.  Such A Nice Number
  106.         BITS_INT_SIZE    = 32,                                        // Size Of A Single Word
  107.         BITS_AND        = (BITS_INT_SIZE - 1),                        // Used For And Operation
  108.         ARRAY_SIZE        = ((CAPACITY + BITS_AND)/(BITS_INT_SIZE)),    // Num Words Used
  109.         BYTE_SIZE        = (ARRAY_SIZE*sizeof(unsigned int)),        // Num Bytes Used
  110.     };
  111.  
  112.     unsigned int    mData[ARRAY_SIZE];
  113.  
  114. public:
  115.     rvBits()                                    {clear();}
  116.     void    clear()                                {memset(mData, 0, (size_t)(ARRAY_SIZE * sizeof( unsigned int )));}
  117.     bool    valid(const int i)                    {return (i>=0 && i<CAPACITY);}
  118.     void    unset(const int i)                    {assert(valid(i));            mData[i>>BITS_SHIFT] &= ~(1<<(i&BITS_AND));}
  119.     void    set(const int i)                    {assert(valid(i));            mData[i>>BITS_SHIFT] |=  (1<<(i&BITS_AND));}
  120.     bool    operator[](const int i)                {assert(valid(i));    return (mData[i>>BITS_SHIFT] &   (1<<(i&BITS_AND)))!=0;}
  121. };
  122.  
  123. /*
  124. ===============================================================================
  125.  
  126.     Raven Pool
  127.  
  128. ===============================================================================
  129. */
  130. template<class TYPE, int CAPACITY>
  131. class rvPool
  132. {
  133.     TYPE            mData[CAPACITY];
  134.     TYPE*            mFree[CAPACITY];
  135.     int                mSize;
  136.  
  137. public:
  138.     rvPool()                                    {clear();}
  139.     int        size()                                {return mSize;}
  140.     bool    empty()                                {return mSize==0;}
  141.     bool    full()                                {return mSize>=CAPACITY;}
  142.     void    clear()                                {mSize=0; for (int i=0; i<CAPACITY; i++)                mFree[i]=&mData[i];}
  143.     void    free(TYPE* t)                        {assert(!empty());    mSize--;                            mFree[mSize]=t;}
  144.     TYPE*    alloc()                                {assert(!full());    mSize++;                            return mFree[mSize-1];}
  145. };
  146.  
  147.  
  148. /*
  149. ===============================================================================
  150.  
  151.     Raven Index Pool
  152.  
  153. ===============================================================================
  154. */
  155. template<class TYPE, int CAPACITY, int INDEXNUM>
  156. class rvIndexPool
  157. {
  158.     TYPE            mData[CAPACITY];
  159.     TYPE*            mFree[CAPACITY];
  160.     TYPE*            mIndx[INDEXNUM];
  161.     int                mSize;
  162.  
  163. public:
  164.     rvIndexPool()                                {clear();}
  165.     int        size()                                {return mSize;}
  166.     bool    empty()                                {return mSize==0;}
  167.     bool    full()                                {return mSize>=CAPACITY;}
  168.     void    clear()                                {mSize=0; for (int i=0; i<CAPACITY; i++) mFree[i]=&mData[i]; memset(mIndx, 0, sizeof(mIndx));}
  169.     bool    valid(int i)                        {return (i>=0 && i<INDEXNUM && mIndx[i]);}
  170.     TYPE*    operator[](int i)                    {assert(valid(i));    return mIndx[i];}
  171.     TYPE*    alloc(int i)                        {assert(!full());    mSize++;    mIndx[i]=mFree[mSize-1];    return mFree[mSize-1];}
  172.     void    free(int i)                            {assert(valid(i));    mSize--;    mFree[mSize]=mIndx[i];        mIndx[i]=NULL;}
  173. };
  174.  
  175. #endif /* !__QUEUE_H__ */
  176.