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: 10 November 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     size_t index(0);
 171
 172     // iterate over byte arrays
 173     const size_t numBuffers = m_data.size();
 174     for ( size_t i = 0; i < numBuffers; ++i ) {
 175         const ByteArray& current = m_data.at(i);
 176
 177         // if on first array, use head; else 0
 178         const size_t start = ( (i==0) ? m_head : 0 );
 179
 180         // if on last array, set end; else use current byte array size
 181         const size_t end   = ( (i==m_tailBufferIndex) ? m_tail : current.Size());
 182
 183         // look through this iteration's byte array for @c
 184         const char* p = current.ConstData()+start;
 185         for ( size_t j = start; j < end; ++j ) {
 186             if ( *p++ == c )
 187                 return index;
 188             ++index;
 189         }
 190     }
 191
 192     // no match found
 193     return string::npos;
 194 }
 195
 196 bool RollingBuffer::IsEmpty(void) const {
 197     return (m_tailBufferIndex == 0) && (m_tail == 0);
 198 }
 199
 200 size_t RollingBuffer::Read(char* dest, size_t max) {
 201
 202     size_t bytesToRead    = std::min(Size(), max);
 203     size_t bytesReadSoFar = 0;
 204
 205     while ( bytesReadSoFar < bytesToRead ) {
 206         const char* readPtr = ReadPointer();
 207         size_t blockBytes = std::min( (bytesToRead - bytesReadSoFar), BlockSize() );
 208         if ( dest )
 209             memcpy(dest+bytesReadSoFar, readPtr, blockBytes);
 210         bytesReadSoFar += blockBytes;
 211         Free(blockBytes);
 212     }
 213
 214     return bytesReadSoFar;
 215 }
 216
 217 size_t RollingBuffer::ReadLine(char* dest, size_t max) {
 218
 219     // if we can't read line or if max is 0
 220     if ( !CanReadLine() || max == 0 )
 221         return 0;
 222
 223     // otherwise, read until we hit newline
 224     size_t bytesReadSoFar = 0;
 225     bool finished = false;
 226     while ( !finished ) {
 227
 228         const size_t index = IndexOf('\n');
 229         const char* readPtr = ReadPointer();
 230         size_t bytesToRead = std::min( (index+1)-bytesReadSoFar, BlockSize() );
 231         bytesToRead = std::min( bytesToRead, (max-1)-bytesReadSoFar );
 232         memcpy(dest+bytesReadSoFar, readPtr, bytesToRead);
 233         bytesReadSoFar += bytesToRead;
 234         Free(bytesToRead);
 235
 236         if ( !((bytesReadSoFar < index+1)&&(bytesReadSoFar < max-1)) )
 237             finished = true;
 238     }
 239
 240     // null terminate 'dest' & return numBytesRead
 241     dest[bytesReadSoFar] = '\0';
 242     return bytesReadSoFar;
 243 }
 244
 245 const char* RollingBuffer::ReadPointer(void) const {
 246
 247     // return null if empty buffer
 248     if ( m_data.empty() )
 249         return 0;
 250
 251     // otherwise return pointer to current position
 252     const ByteArray& first = m_data.front();
 253     return first.ConstData() + m_head;
 254 }
 255
 256 char* RollingBuffer::Reserve(size_t n) {
 257
 258     // if empty buffer
 259     if ( m_totalBufferSize == 0 ) {
 260         m_data[0].Resize( std::max(m_bufferGrowth, n) );
 261         m_totalBufferSize += n;
 262         m_tail = n;
 263         return m_data[m_tailBufferIndex].Data();
 264     }
 265
 266     // increment buffer's byte count
 267     m_totalBufferSize += n;
 268
 269     // if buffer already contains enough space to fit @n more bytes
 270     if ( (m_tail + n) <= m_data.at(m_tailBufferIndex).Size() ) {
 271
 272         // fetch write pointer at current 'tail', increment tail by @n & return
 273         char* ptr = m_data[m_tailBufferIndex].Data() + m_tail;
 274         m_tail += n;
 275         return ptr;
 276     }
 277
 278     // if last byte array isn't half full
 279     if ( m_tail < m_data.at(m_tailBufferIndex).Size()/2 ) {
 280
 281         // we'll allow simple resize
 282         m_data[m_tailBufferIndex].Resize(m_tail + n);
 283
 284         // fetch write pointer at current 'tail', increment tail by @n & return
 285         char* ptr = m_data[m_tailBufferIndex].Data() + m_tail;
 286         m_tail += n;
 287         return ptr;
 288     }
 289
 290     // otherwise, shrink last byte array to current used size
 291     m_data[m_tailBufferIndex].Resize(m_tail);
 292
 293     // then append new byte array
 294     m_data.push_back( ByteArray() );
 295     ++m_tailBufferIndex;
 296     m_data[m_tailBufferIndex].Resize( std::max(m_bufferGrowth, n) );
 297     m_tail = n;
 298
 299     // return write-able pointer on new array
 300     return m_data[m_tailBufferIndex].Data();
 301 }
 302
 303 size_t RollingBuffer::Size(void) const {
 304     return m_totalBufferSize;
 305 }
 306
 307 void RollingBuffer::Write(const char* src, size_t n) {
 308     char* writePtr = Reserve(n);
 309     memcpy(writePtr, src, n);
 310 }