src/api/internal/io/RollingBuffer_p.cpp

   1 // ***************************************************************************
   2 // RollingBuffer_p.cpp (c) 2011 Derek Barnett
   3 // Marth Lab, Department of Biology, Boston College
   4 // ---------------------------------------------------------------------------
   5 // Last modified: 8 December 2011 (DB)
   6 // ---------------------------------------------------------------------------
   7 // Provides a dynamic I/O FIFO byte queue, which removes bytes as they are
   8 // read from the front of the buffer and grows to accept bytes being written
   9 // to buffer end.
  10 //
  11 // implementation note: basically a 'smart' wrapper around 1..* ByteArrays
  12 // ***************************************************************************
  13
  14 #include "api/internal/io/RollingBuffer_p.h"
  15 using namespace BamTools;
  16 using namespace BamTools::Internal;
  17
  18 #include <climits>
  19 #include <cstring>
  20 #include <algorithm>
  21 #include <string>
  22 using namespace std;
  23
  24 // ------------------------------
  25 // RollingBuffer implementation
  26 // ------------------------------
  27
  28 RollingBuffer::RollingBuffer(size_t growth)
  29     : m_bufferGrowth(growth)
  30 {
  31     // buffer always contains at least 1 (maybe empty) byte array
  32     m_data.push_back( ByteArray() );
  33
  34     // set cleared state
  35     Clear();
  36 }
  37
  38 RollingBuffer::~RollingBuffer(void) { }
  39
  40 size_t RollingBuffer::BlockSize(void) const {
  41
  42     // if only one byte array in buffer <- needed?
  43     if ( m_tailBufferIndex == 0 )
  44         return m_tail - m_head;
  45
  46     // otherwise return remaining num bytes in first array
  47     const ByteArray& first = m_data.front();
  48     return first.Size() - m_head;
  49 }
  50
  51 bool RollingBuffer::CanReadLine(void) const {
  52     return IndexOf('\n') != string::npos;
  53 }
  54
  55 void RollingBuffer::Chop(size_t n) {
  56
  57     // update buffer size
  58     if ( n > m_totalBufferSize )
  59         m_totalBufferSize = 0;
  60     else
  61         m_totalBufferSize -= n;
  62
  63     // loop until target case hit
  64     for ( ; ; ) {
  65
  66         // if only one array, decrement tail
  67         if ( m_tailBufferIndex == 0 ) {
  68             m_tail -= n;
  69
  70             // if all data chopped
  71             if ( m_tail <= m_head ) {
  72                 m_head = 0;
  73                 m_tail = 0;
  74             }
  75             return;
  76         }
  77
  78         // if there's room in last byte array to 'chop', just decrement tail
  79         if ( n <= m_tail ) {
  80             m_tail -= n;
  81             return;
  82         }
  83
  84         // otherwise we're going to overlap our internal byte arrays
  85         // reduce our chop amount by the amount of data in the last byte array
  86         n -= m_tail;
  87
  88         // remove last byte array & set tail to it's end
  89         m_data.pop_back();
  90         --m_tailBufferIndex;
  91         m_tail = m_data.at(m_tailBufferIndex).Size();
  92     }
  93
  94     // if buffer is now empty, reset state & clear up memory
  95     if ( IsEmpty() )
  96         Clear();
  97 }
  98
  99 void RollingBuffer::Clear(void) {
 100
 101     // remove all byte arrays (except first)
 102     m_data.erase( m_data.begin()+1, m_data.end() );
 103
 104     // clear out first byte array
 105     m_data[0].Resize(0);
 106     m_data[0].Squeeze();
 107
 108     // reset index & size markers
 109     m_head = 0;
 110     m_tail = 0;
 111     m_tailBufferIndex = 0;
 112     m_totalBufferSize = 0;
 113 }
 114
 115 void RollingBuffer::Free(size_t n) {
 116
 117     // update buffer size
 118     if ( n > m_totalBufferSize )
 119         m_totalBufferSize = 0;
 120     else
 121         m_totalBufferSize -= n;
 122
 123     // loop until target case hit
 124     for ( ; ; ) {
 125
 126         const size_t blockSize = BlockSize();
 127
 128         // if there's room in current array
 129         if ( n < blockSize ) {
 130
 131             // shift 'head' over @n bytes
 132             m_head += n;
 133
 134             // check for emptied, single byte array
 135             if ( m_head == m_tail && m_tailBufferIndex == 0 ) {
 136                 m_head = 0;
 137                 m_tail = 0;
 138             }
 139
 140             break;
 141         }
 142
 143         // otherwise we need to check next byte array
 144         // first update amount to remove
 145         n -= blockSize;
 146
 147         // special case - there was only 1 array
 148         if ( m_data.size() == 1 ) {
 149             if ( m_data.at(0).Size() != m_bufferGrowth )
 150                 m_data[0].Resize(m_bufferGrowth);
 151             m_head = 0;
 152             m_tail = 0;
 153             m_tailBufferIndex = 0;
 154             break;
 155         }
 156
 157         // otherwise, remove first array and move to next iteration
 158         m_data.pop_front();
 159         --m_tailBufferIndex;
 160         m_head = 0;
 161     }
 162
 163     // if buffer is now empty, reset state & clear up memory
 164     if ( IsEmpty() )
 165         Clear();
 166 }
 167
 168 size_t RollingBuffer::IndexOf(char c) const {
 169
 170     // skip processing if empty buffer
 171     if ( IsEmpty() )
 172         return string::npos;
 173
 174     size_t index(0);
 175
 176     // iterate over byte arrays
 177     const size_t numBuffers = m_data.size();
 178     for ( size_t i = 0; i < numBuffers; ++i ) {
 179         const ByteArray& current = m_data.at(i);
 180
 181         // if on first array, use head; else 0
 182         const size_t start = ( (i==0) ? m_head : 0 );
 183
 184         // if on last array, set end; else use current byte array size
 185         const size_t end   = ( (i==m_tailBufferIndex) ? m_tail : current.Size());
 186
 187         // look through this iteration's byte array for @c
 188         const char* p = current.ConstData()+start;
 189         for ( size_t j = start; j < end; ++j ) {
 190             if ( *p++ == c )
 191                 return index;
 192             ++index;
 193         }
 194     }
 195
 196     // no match found
 197     return string::npos;
 198 }
 199
 200 bool RollingBuffer::IsEmpty(void) const {
 201     return (m_tailBufferIndex == 0) && (m_tail == 0);
 202 }
 203
 204 size_t RollingBuffer::Read(char* dest, size_t max) {
 205
 206     size_t bytesToRead    = std::min(Size(), max);
 207     size_t bytesReadSoFar = 0;
 208
 209     while ( bytesReadSoFar < bytesToRead ) {
 210         const char* readPtr = ReadPointer();
 211         size_t blockBytes = std::min( (bytesToRead - bytesReadSoFar), BlockSize() );
 212         if ( dest )
 213             memcpy(dest+bytesReadSoFar, readPtr, blockBytes);
 214         bytesReadSoFar += blockBytes;
 215         Free(blockBytes);
 216     }
 217
 218     return bytesReadSoFar;
 219 }
 220
 221 size_t RollingBuffer::ReadLine(char* dest, size_t max) {
 222
 223     // if we can't read line or if max is 0
 224     if ( !CanReadLine() || max == 0 )
 225         return 0;
 226
 227     // otherwise, read until we hit newline
 228     size_t bytesReadSoFar = 0;
 229     bool finished = false;
 230     while ( !finished ) {
 231
 232         const size_t index = IndexOf('\n');
 233         const char* readPtr = ReadPointer();
 234         size_t bytesToRead = std::min( (index+1)-bytesReadSoFar, BlockSize() );
 235         bytesToRead = std::min( bytesToRead, (max-1)-bytesReadSoFar );
 236         memcpy(dest+bytesReadSoFar, readPtr, bytesToRead);
 237         bytesReadSoFar += bytesToRead;
 238         Free(bytesToRead);
 239
 240         if ( !((bytesReadSoFar < index+1)&&(bytesReadSoFar < max-1)) )
 241             finished = true;
 242     }
 243
 244     // null terminate 'dest' & return numBytesRead
 245     dest[bytesReadSoFar] = '\0';
 246     return bytesReadSoFar;
 247 }
 248
 249 const char* RollingBuffer::ReadPointer(void) const {
 250
 251     // return null if empty buffer
 252     if ( m_data.empty() )
 253         return 0;
 254
 255     // otherwise return pointer to current position
 256     const ByteArray& first = m_data.front();
 257     return first.ConstData() + m_head;
 258 }
 259
 260 char* RollingBuffer::Reserve(size_t n) {
 261
 262     // if empty buffer
 263     if ( m_totalBufferSize == 0 ) {
 264         m_data[0].Resize( std::max(m_bufferGrowth, n) );
 265         m_totalBufferSize += n;
 266         m_tail = n;
 267         return m_data[m_tailBufferIndex].Data();
 268     }
 269
 270     // increment buffer's byte count
 271     m_totalBufferSize += n;
 272
 273     // if buffer already contains enough space to fit @n more bytes
 274     if ( (m_tail + n) <= m_data.at(m_tailBufferIndex).Size() ) {
 275
 276         // fetch write pointer at current 'tail', increment tail by @n & return
 277         char* ptr = m_data[m_tailBufferIndex].Data() + m_tail;
 278         m_tail += n;
 279         return ptr;
 280     }
 281
 282     // if last byte array isn't half full
 283     if ( m_tail < m_data.at(m_tailBufferIndex).Size()/2 ) {
 284
 285         // we'll allow simple resize
 286         m_data[m_tailBufferIndex].Resize(m_tail + n);
 287
 288         // fetch write pointer at current 'tail', increment tail by @n & return
 289         char* ptr = m_data[m_tailBufferIndex].Data() + m_tail;
 290         m_tail += n;
 291         return ptr;
 292     }
 293
 294     // otherwise, shrink last byte array to current used size
 295     m_data[m_tailBufferIndex].Resize(m_tail);
 296
 297     // then append new byte array
 298     m_data.push_back( ByteArray() );
 299     ++m_tailBufferIndex;
 300     m_data[m_tailBufferIndex].Resize( std::max(m_bufferGrowth, n) );
 301     m_tail = n;
 302
 303     // return write-able pointer on new array
 304     return m_data[m_tailBufferIndex].Data();
 305 }
 306
 307 size_t RollingBuffer::Size(void) const {
 308     return m_totalBufferSize;
 309 }
 310
 311 void RollingBuffer::Write(const char* src, size_t n) {
 312     char* writePtr = Reserve(n);
 313     memcpy(writePtr, src, n);
 314 }