src/api/internal/io/RollingBuffer_p.cpp

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