/ray/src/lib/tl/tllinearqueue.h

Go to the documentation of this file.

/*
 * lib/tl/tllinearqueue.h 
 * 
 * Implementation of a linear (non-priority) 2-ended queue. 
 * 
 * Copyright (c) 2004 by Wolfgang Wieser ] wwieser (a) gmx <*> de [ 
 * 
 * This file may be distributed and/or modified under the terms of the 
 * GNU General Public License version 2 as published by the Free Software 
 * Foundation. (See COPYING.GPL for details.)
 * 
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 * 
 */

#ifndef _TemplateLibrary_LinearQueue_H_
#define _TemplateLibrary_LinearQueue_H_ 1

#include <lib/sconfig.h>    /* MUST be first */

#include <lib/salloc.h>
#include <lib/tl/defop.h>
#include <lib/tl/linkedlist.h>


template<typename T,typename _OP=TLDefaultOperators_CDT<T> >class TLLinearQueue
{
    public:
        struct Chunk : LinkedListBase<Chunk>
        {
            // For GCC, we may use ent[0]. (zero-length array)
            T ent[];  
            
            inline Chunk() : LinkedListBase<Chunk>() {}
            inline ~Chunk() {}
        };
    
    public:
        class Iterator  // <-- more like a const-iterator
        {
            private:
                const TLLinearQueue *lq;
                Chunk *chk;
                size_t idx;
                
                inline bool _valid()
                    {  return(chk);  }
                inline void _assign(const TLLinearQueue &_lq)
                    {  lq=&_lq; chk=lq->clist.first(); idx=lq->first_idx;  }
            public:
                inline Iterator(const TLLinearQueue &_lq)  { _assign(_lq); }
                inline ~Iterator() {}
                
                inline operator bool()
                    {  return(_valid());  }
                
                inline T *operator*()
                    {  return(_valid() ? &(chk->ent[idx]) : NULL);  }
                
                inline bool operator=(const TLLinearQueue &_lq)
                    {  _assign(_lq);  return(_valid());  }
                
                inline bool operator++()
                {
                    if(!_valid())  return(0);
                    ++idx;
                    if(!chk->next && idx>lq->last_idx)  // reached end of list
                    {  chk=NULL;  }
                    else if(idx>=lq->chunk_size)
                    {  idx=0;  chk=chk->next;  }
                    return(_valid());
                }
                inline bool operator++(int)
                    {  return(operator++());  }
        };
        
    protected:
        size_t chunk_size;   
        int keep_old;        
        LinkedList<Chunk> clist;  
        size_t nelem;        
        
        //----------------------------------------------------------------------
        // Internal layout: 
        // 
        // tail->  [CHUNK]---[CHUNK]---[CHUNK]---[CHUNK]  <-head
        // FIRST,INSERT                              LAST,APPEND
        //----------------------------------------------------------------------
        
        size_t first_idx;  // 0
        size_t last_idx;  // chunk_size-1
        
        LinkedList<Chunk> old_list; 
        int old_nents;              
        
    public:
        _OP OP;
    
    private:
        inline Chunk *_AllocChunk()
        {
            char *mem=(char*)OP.alloc(sizeof(Chunk)+chunk_size*OP.size());
            Chunk *c = new(mem) Chunk();
            return(c);
        }
        inline void _FreeChunk(Chunk *c)
            {  c->Chunk::~Chunk();  OP.free((char*)c);  }
        
        void _FreeAllOld()
        {
            while(!old_list.IsEmpty())
            {  _FreeChunk(old_list.PopLast());  --old_nents;  }
            Assert(old_nents==0);
        }
        
        inline void _Add2Cache(Chunk *c)
        {
            if(!keep_old && !old_nents)
            {  _FreeChunk(c);  return;  }
            old_list.append(c);  ++old_nents;
            // Always add to the end of old_list because of caching strategy. 
            // In case there are too many elements, remove the oldest one 
            // (this is the first one). 
            while(old_nents>keep_old)
            {  _FreeChunk(old_list.PopFirst());  --old_nents;  }
        }
        inline Chunk *_NewChunkCache()
        {
            Chunk *c;
            // See if we can re-use a chunk. 
            if(!old_list.IsEmpty())
            {  c=old_list.PopLast();  --old_nents;  }
            else
            {  c=_AllocChunk();  }
            return(c);
        }
        
        void _AddChunkTail()  // <-- NON-inline. 
            {  clist.insert(_NewChunkCache());  first_idx=chunk_size-1;  }
        void _AddChunkHead()  // <-- NON-inline. 
            {  clist.append(_NewChunkCache());  last_idx=0;  }
        
        void _PopChunkTail()  // <-- NON-inline. 
            {  _Add2Cache(clist.PopFirst());  first_idx=0;  }
        void _PopChunkHead()  // <-- NON-inline. 
            {  _Add2Cache(clist.PopLast());  last_idx=chunk_size-1;  }
        
        inline void _DoPopTail()
        {
            OP.clr(&clist.first()->ent[first_idx]);  --nelem;
            if(!nelem /*first_idx==last_idx && clist.first()==clist.last()*/)
            {  last_idx=chunk_size-1;  _PopChunkTail();  return;  }
            if(++first_idx==chunk_size)  _PopChunkTail();
        }
        inline void _DoPopHead()
        {
            OP.clr(&clist.last()->ent[last_idx]);  --nelem;
            if(!nelem /*first_idx==last_idx && clist.first()==clist.last()*/)
            {  first_idx=0;  _PopChunkHead();  return;  }
            if(!last_idx)  _PopChunkHead();  else  --last_idx;
        }
        
    private:
        TLLinearQueue(const TLLinearQueue &);
        void operator=(const TLLinearQueue &);
    public:
        inline TLLinearQueue(size_t _chunk_size,int _keep_old=4,
            const _OP &op=_OP()) : 
            chunk_size(_chunk_size<1 ? 1 : _chunk_size),
            keep_old(_keep_old<0 ? 0 : _keep_old),
            clist(),nelem(0),first_idx(0),last_idx(chunk_size-1),
            old_list(),old_nents(0),OP(op)  {}
        inline ~TLLinearQueue()
            {  clear();  _FreeAllOld();  }
        
        inline bool IsEmpty() const
            {  return(clist.IsEmpty());  }
        
        inline size_t NElem() const
            {  return(nelem);  }
        
        void clear()
        {
            while(!IsEmpty())
            {  _DoPopTail();  }
            Assert(nelem==0);
        }
        
        inline T *head()
            {  return(clist.last() ? &clist.last()->ent[last_idx] : NULL);  }
        
        inline T *tail()
            {  return(clist.first() ? &clist.first()->ent[first_idx] : NULL);  }
        
        inline void PushTail(const T &e)
        {
            if(!first_idx)  _AddChunkTail();  else  --first_idx;
            Chunk *c=clist.first();  OP.ini(&c->ent[first_idx],e);  ++nelem;
        }
        
        inline void PushHead(const T &e)
        {
            if(++last_idx==chunk_size)  _AddChunkHead();
            Chunk *c=clist.last();  OP.ini(&c->ent[last_idx],e);  ++nelem;
        }
        
        int PopTail(T *re=NULL)
        {
            if(IsEmpty())  return(1);
            if(re)  OP.ass(*re,clist.first()->ent[first_idx]);
            _DoPopTail();
            return(0);
        }
        
        int PopHead(T *re=NULL)
        {
            if(IsEmpty())  return(1);
            if(re)  OP.ass(*re,clist.last()->ent[last_idx]);
            _DoPopHead();
            return(0);
        }
};

#endif  /* _TemplateLibrary_LinearQueue_H_ */

---