Branch data     Line data    Source code

       1                 :            : // $Id: Queue.cc 6219 2008-10-01 05:39:07Z vern $
       2                 :            : //
       3                 :            : // See the file "COPYING" in the main distribution directory for copyright.
       4                 :            : 
       5                 :            : #include "config.h"
       6                 :            : 
       7                 :            : #include <string.h>
       8                 :            : 
       9                 :            : #include "Queue.h"
      10                 :            : 
      11                 :          3 : BaseQueue::BaseQueue(int size)
      12                 :            :         {
      13                 :          3 :         const int DEFAULT_CHUNK_SIZE = 10;
      14                 :            : 
      15                 :          3 :         chunk_size = DEFAULT_CHUNK_SIZE;
      16                 :            : 
      17                 :          3 :         head = tail = num_entries = 0;
      18                 :            : 
      19 [ #  # ][ -  + ]:          3 :         if ( size < 0 )
      20                 :            :                 {
      21                 :          0 :                 entry = new ent[1];
      22                 :          0 :                 max_entries = 0;
      23                 :            :                 }
      24                 :            :         else
      25                 :            :                 {
      26 [ #  # ][ +  - ]:          3 :                 if ( (entry = new ent[chunk_size+1]) )
      27                 :          3 :                         max_entries = chunk_size;
      28                 :            :                 else
      29                 :            :                         {
      30                 :          0 :                         entry = new ent[1];
      31                 :          0 :                         max_entries = 0;
      32                 :            :                         }
      33                 :            :                 }
      34                 :          3 :         }
      35                 :            : 
      36                 :          0 : void BaseQueue::push_front(ent a)
      37                 :            :         {
      38         [ #  # ]:          0 :         if ( num_entries == max_entries )
      39                 :            :                 {
      40                 :          0 :                 resize(max_entries+chunk_size); // make more room
      41                 :          0 :                 chunk_size *= 2;
      42                 :            :                 }
      43                 :            : 
      44                 :          0 :         ++num_entries;
      45         [ #  # ]:          0 :         if ( head )
      46                 :          0 :                 entry[--head] = a;
      47                 :            :         else
      48                 :            :                 {
      49                 :          0 :                 head = max_entries;
      50                 :          0 :                 entry[head] = a;
      51                 :            :                 }
      52                 :          0 :         }
      53                 :            : 
      54                 :          0 : void BaseQueue::push_back(ent a)
      55                 :            :         {
      56         [ #  # ]:          0 :         if ( num_entries == max_entries )
      57                 :            :                 {
      58                 :          0 :                 resize(max_entries+chunk_size); // make more room
      59                 :          0 :                 chunk_size *= 2;
      60                 :            :                 }
      61                 :            : 
      62                 :          0 :         ++num_entries;
      63         [ #  # ]:          0 :         if ( tail < max_entries )
      64                 :          0 :                 entry[tail++] = a;
      65                 :            :         else
      66                 :            :                 {
      67                 :          0 :                 entry[tail] = a;
      68                 :          0 :                 tail = 0;
      69                 :            :                 }
      70                 :          0 :         }
      71                 :            : 
      72                 :          0 : ent BaseQueue::pop_front()
      73                 :            :         {
      74         [ #  # ]:          0 :         if ( ! num_entries )
      75                 :          0 :                 return 0;
      76                 :            : 
      77                 :          0 :         --num_entries;
      78         [ #  # ]:          0 :         if ( head < max_entries )
      79                 :          0 :                 return entry[head++];
      80                 :            :         else
      81                 :            :                 {
      82                 :          0 :                 head = 0;
      83                 :          0 :                 return entry[max_entries];
      84                 :            :                 }
      85                 :            :         }
      86                 :            : 
      87                 :          0 : ent BaseQueue::pop_back()
      88                 :            :         {
      89         [ #  # ]:          0 :         if ( ! num_entries )
      90                 :          0 :                 return 0;
      91                 :            : 
      92                 :          0 :         --num_entries;
      93         [ #  # ]:          0 :         if ( tail )
      94                 :          0 :                 return entry[--tail];
      95                 :            :         else
      96                 :            :                 {
      97                 :          0 :                 tail = max_entries;
      98                 :          0 :                 return entry[tail];
      99                 :            :                 }
     100                 :            :         }
     101                 :            : 
     102                 :          0 : int BaseQueue::resize(int new_size)
     103                 :            :         {
     104         [ #  # ]:          0 :         if ( new_size < num_entries )
     105                 :          0 :                 new_size = num_entries; // do not lose any entries
     106                 :            : 
     107         [ #  # ]:          0 :         if ( new_size != max_entries )
     108                 :            :                 {
     109                 :            :                 // Note, allocate extra space, so that we can always
     110                 :            :                 // use the [max_entries] element.
     111                 :            :                 // ### Yin, why not use realloc()?
     112                 :          0 :                 ent* new_entry = new ent[new_size+1];
     113                 :            : 
     114         [ #  # ]:          0 :                 if ( new_entry )
     115                 :            :                         {
     116         [ #  # ]:          0 :                         if ( head <= tail )
     117                 :            :                                 memcpy( new_entry, entry + head,
     118                 :          0 :                                         sizeof(ent) * num_entries );
     119                 :            :                         else
     120                 :            :                                 {
     121                 :          0 :                                 int len = num_entries - tail;
     122                 :            :                                 memcpy( new_entry, entry + head,
     123                 :          0 :                                         sizeof(ent) * len );
     124                 :            :                                 memcpy( new_entry + len, entry,
     125                 :          0 :                                         sizeof(ent) * tail );
     126                 :            :                                 }
     127         [ #  # ]:          0 :                         delete [] entry;
     128                 :          0 :                         entry = new_entry;
     129                 :          0 :                         max_entries = new_size;
     130                 :          0 :                         head = 0;
     131                 :          0 :                         tail = num_entries;
     132                 :            :                         }
     133                 :            :                 else
     134                 :            :                         { // out of memory
     135                 :            :                         }
     136                 :            :                 }
     137                 :            : 
     138                 :          0 :         return max_entries;
     139                 :            :         }