Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members

BaseQueue Class Reference

#include <Queue.h>

List of all members.

Public Member Functions

 ~BaseQueue ()
int length () const
int resize (int=0)
void clear ()
int front () const
int back () const
void incr (int &index)

Protected Member Functions

 BaseQueue (int=0)
void push_front (ent)
void push_back (ent)
ent pop_front ()
ent pop_back ()
ent operator[] (int i) const

Protected Attributes

ent * entry
int chunk_size
int max_entries
int num_entries
int head
int tail

Constructor & Destructor Documentation

BaseQueue::~BaseQueue (   )  [inline]
 

Definition at line 47 of file Queue.h.

References entry. 

00047 { delete[] entry; }

BaseQueue::BaseQueue (  int  = 0  )  [protected]
 

Definition at line 28 of file Queue.cc.

References chunk_size, ent, entry, head, max_entries, num_entries, size, and tail. 

00029         {
00030         const int DEFAULT_CHUNK_SIZE = 10;
00031 
00032         chunk_size = DEFAULT_CHUNK_SIZE;
00033 
00034         head = tail = num_entries = 0;
00035 
00036         if ( size < 0 )
00037                 {
00038                 entry = new ent[1];
00039                 max_entries = 0;
00040                 }
00041         else
00042                 {
00043                 if ( (entry = new ent[chunk_size+1]) )
00044                         max_entries = chunk_size;
00045                 else
00046                         {
00047                         entry = new ent[1];
00048                         max_entries = 0;
00049                         }
00050                 }
00051         }

Member Function Documentation

int BaseQueue::back (   )  const [inline]
 

Definition at line 57 of file Queue.h.

References tail. 

00057 { return tail; }

void BaseQueue::clear (   )  [inline]
 

Definition at line 53 of file Queue.h.

References head, num_entries, and tail. 

00053 { head = tail = num_entries = 0; }

int BaseQueue::front (   )  const [inline]
 

Definition at line 56 of file Queue.h.

References head. 

00056 { return head; }

void BaseQueue::incr (  int &  index  )  [inline]
 

Definition at line 58 of file Queue.h.

References max_entries. 

00058 { index < max_entries ? ++index : index = 0; }

int BaseQueue::length (   )  const [inline]
 

Definition at line 49 of file Queue.h.

References num_entries. 

00049 { return num_entries; }

ent BaseQueue::operator[] (  int  i  )  const [inline, protected]
 

Definition at line 69 of file Queue.h.

References ent, and entry. 

00069 { return entry[i]; }

ent BaseQueue::pop_back (   )  [protected]
 

Definition at line 104 of file Queue.cc.

References ent, entry, max_entries, num_entries, and tail. 

00105         {
00106         if ( ! num_entries )
00107                 return 0;
00108 
00109         --num_entries;
00110         if ( tail )
00111                 return entry[--tail];
00112         else
00113                 {
00114                 tail = max_entries;
00115                 return entry[tail];
00116                 }
00117         }

ent BaseQueue::pop_front (   )  [protected]
 

Definition at line 89 of file Queue.cc.

References ent, entry, head, max_entries, and num_entries. 

00090         {
00091         if ( ! num_entries )
00092                 return 0;
00093 
00094         --num_entries;
00095         if ( head < max_entries )
00096                 return entry[head++];
00097         else
00098                 {
00099                 head = 0;
00100                 return entry[max_entries];
00101                 }
00102         }

void BaseQueue::push_back (  ent   )  [protected]
 

Definition at line 71 of file Queue.cc.

References chunk_size, ent, entry, max_entries, num_entries, resize(), and tail. 

00072         {
00073         if ( num_entries == max_entries )
00074                 {
00075                 resize(max_entries+chunk_size); // make more room
00076                 chunk_size *= 2;
00077                 }
00078 
00079         ++num_entries;
00080         if ( tail < max_entries )
00081                 entry[tail++] = a;
00082         else
00083                 {
00084                 entry[tail] = a;
00085                 tail = 0;
00086                 }
00087         }

void BaseQueue::push_front (  ent   )  [protected]
 

Definition at line 53 of file Queue.cc.

References chunk_size, ent, entry, head, max_entries, num_entries, and resize(). 

00054         {
00055         if ( num_entries == max_entries )
00056                 {
00057                 resize(max_entries+chunk_size); // make more room
00058                 chunk_size *= 2;
00059                 }
00060 
00061         ++num_entries;
00062         if ( head )
00063                 entry[--head] = a;
00064         else
00065                 {
00066                 head = max_entries;
00067                 entry[head] = a;
00068                 }
00069         }

int BaseQueue::resize (  int  = 0  ) 
 

Definition at line 119 of file Queue.cc.

References ent, entry, head, len, max_entries, num_entries, and tail.

Referenced by push_back(), and push_front(). 

00120         {
00121         if ( new_size < num_entries )
00122                 new_size = num_entries; // do not lose any entries
00123 
00124         if ( new_size != max_entries )
00125                 {
00126                 // Note, allocate extra space, so that we can always
00127                 // use the [max_entries] element.
00128                 // ### Yin, why not use realloc()?
00129                 ent* new_entry = new ent[new_size+1];
00130 
00131                 if ( new_entry )
00132                         {
00133                         if ( head <= tail )
00134                                 memcpy( new_entry, entry + head,
00135                                         sizeof(ent) * num_entries );
00136                         else
00137                                 {
00138                                 int len = num_entries - tail;
00139                                 memcpy( new_entry, entry + head,
00140                                         sizeof(ent) * len );
00141                                 memcpy( new_entry + len, entry,
00142                                         sizeof(ent) * tail );
00143                                 }
00144                         delete [] entry;
00145                         entry = new_entry;
00146                         max_entries = new_size;
00147                         head = 0;
00148                         tail = num_entries;
00149                         }
00150                 else
00151                         { // out of memory
00152                         }
00153                 }
00154 
00155         return max_entries;
00156         }

Member Data Documentation

int BaseQueue::chunk_size [protected]
 

Definition at line 72 of file Queue.h.

Referenced by BaseQueue(), push_back(), and push_front().

ent* BaseQueue::entry [protected]
 

Definition at line 71 of file Queue.h.

Referenced by BaseQueue(), operator[](), pop_back(), pop_front(), push_back(), push_front(), resize(), and ~BaseQueue().

int BaseQueue::head [protected]
 

Definition at line 75 of file Queue.h.

Referenced by BaseQueue(), clear(), front(), pop_front(), push_front(), and resize().

int BaseQueue::max_entries [protected]
 

Definition at line 73 of file Queue.h.

Referenced by BaseQueue(), incr(), pop_back(), pop_front(), push_back(), push_front(), and resize().

int BaseQueue::num_entries [protected]
 

Definition at line 74 of file Queue.h.

Referenced by BaseQueue(), clear(), length(), pop_back(), pop_front(), push_back(), push_front(), and resize().

int BaseQueue::tail [protected]
 

Definition at line 76 of file Queue.h.

Referenced by back(), BaseQueue(), clear(), pop_back(), push_back(), and resize().

The documentation for this class was generated from the following files:
Generated on Wed Sep 14 03:07:53 2005 for bro_docs by doxygen 1.3.5