lab0-实现ByteStream
CS144 lab0
lab0具体的相关事宜可以查看博客:https://kiprey.github.io/2021/11/cs144-lab0/
完整项目代码: CS144
缓冲区实现
固定大小
lab0要求实现的缓冲区就是固定大小的,具体要求是需要实现一个可读可写的缓冲区.我们先讲讲实现的逻辑,如下图:
由于大小固定,我们通过模运算得到每次需要读取或写入的实际位置,而 readIdx 和 writeIdx 则一直+1即可,每次在需要读取的时候判断当前可读区域的大小,我们始终只需要通过 readIdx 和 writeIdx 的相对位置得到刻度区域的大小,而 writeIdx 永远是大于 readIdx ,只有实际读写的时候通过模运算获得需要读写的具体位置,这样就可以避免 writeIdx 在具体逻辑中可能在 readIdx 之后的情况,readIdx 和 writeIdx 是直接存入的取模的结果那么就需要特殊处理可读区域为空以及可写区域为空两种情况(因为这个时候都满足 readIdx==writeIdx).所以我们是通过一直自增,存取的时候再取模的方式完美的避开了无法判空和判满的情况,每次只要计算出可读区域的大小 writeIdx - readIdx ,可写区域的大小就确定了 (capacity-可读区域大小),然后我们就只管根据 writeIdx 或者 readIdx 模运算得到起始位置,然后一直+1再取模得到具体的值即可完成对应操作.
并且这种方式实现的缓冲区, writeIdx 直接表示总共写入多少个字节,readIdx 表示总共读取多少个字节,正好就对应我们需要实现的 bytes_written 方法和 bytes_read 方法.
动态大小
当缓冲区需要动态大小的时候,上述策略将变得毫无意义,因为每次扩容的时候需要重新拷贝之前的数据,所以我们需要改变复用内存的模运算策略.
这种动态大小的缓冲区,一般都是在需要扩容的时候,把整体的可读区域重新迁移到最前面,再更新可写指针,这样我们就只需要拷贝部分数据了.
具体的应用有很多,比如muduo网络库种或go标准库种的buffer都是这样实现的.
我写的一个网络库 netpoll-cpp 也有类似的实现:
netpoll-cpp/netpoll/util/message_buffer.h
netpoll-cpp/netpoll/util/message_buffer.cc
ByteStream实现
声明
前面对固定大小缓冲区的实现方式已经描述完毕,现在我们来看看需要实现的函数声明:
class ByteStream
{
private:
bool _error{}; //!< Flag indicating that the stream suffered an error.
bool _eof{};
size_t _readIdx{};
size_t _writeIdx{};
std::vector<char> _buffer;
public:
explicit ByteStream(size_t capacity);
size_t write(const std::string &data);
size_t remaining_capacity() const;
void end_input();
//! Indicate that the stream suffered an error.
void set_error() { _error = true; }
std::string peek_output(const size_t len) const;
//! Remove bytes from the buffer
void pop_output(const size_t len);
std::string read(const size_t len);
//! \returns `true` if the stream input has ended
bool input_ended() const;
//! \returns `true` if the stream has suffered an error
bool error() const { return _error; }
//! \returns the maximum amount that can currently be read from the stream
size_t buffer_size() const;
//! \returns `true` if the buffer is empty
bool buffer_empty() const;
//! \returns `true` if the output has reached the ending
bool eof() const;
size_t bytes_written() const;
//! Total number of bytes popped
size_t bytes_read() const;
//!@}
};
实现
ByteStream::ByteStream(const size_t capacity) : _buffer(capacity, 0) {}
size_t ByteStream::write(const string &data)
{
assert(buffer_size() <= _buffer.size());
if (input_ended()) return 0;
size_t canWrite = _buffer.size() - buffer_size();
size_t realWrite = min(canWrite, data.size());
for (size_t i = 0; i < realWrite; i++)
{
_buffer[_writeIdx++ % _buffer.size()] = data[i];
}
return realWrite;
}
//! \param[in] len bytes will be copied from the output side of the buffer
string ByteStream::peek_output(const size_t len) const
{
assert(buffer_size() <= _buffer.size());
size_t canPeek = min(buffer_size(), len);
string ret;
for (size_t i = 0; i < canPeek; i++)
{
ret += _buffer[(_readIdx + i) % _buffer.size()];
}
return ret;
}
//! \param[in] len bytes will be removed from the output side of the buffer
void ByteStream::pop_output(const size_t len)
{
assert(buffer_size() <= _buffer.size());
if (len > buffer_size())
{
set_error();
return;
}
_readIdx += len;
}
std::string ByteStream::read(const size_t len)
{
assert(buffer_size() <= _buffer.size());
auto ret = peek_output(len);
pop_output(len);
if (_error) return {};
return ret;
}
void ByteStream::end_input() { _eof = true; }
bool ByteStream::input_ended() const { return _eof; }
size_t ByteStream::buffer_size() const
{
assert(_writeIdx >= _readIdx);
return _writeIdx - _readIdx;
}
bool ByteStream::buffer_empty() const { return _writeIdx == _readIdx; }
bool ByteStream::eof() const { return _eof && buffer_empty(); }
size_t ByteStream::bytes_written() const { return _writeIdx; }
size_t ByteStream::bytes_read() const { return _readIdx; }
size_t ByteStream::remaining_capacity() const
{
return _buffer.size() - buffer_size();
}