2 * Copyright 2013 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 #ifndef FOLLY_CURSOR_H
18 #define FOLLY_CURSOR_H
23 #include <type_traits>
26 #include "folly/Bits.h"
27 #include "folly/io/IOBuf.h"
28 #include "folly/io/IOBufQueue.h"
29 #include "folly/Likely.h"
32 * Cursor class for fast iteration over IOBuf chains.
34 * Cursor - Read-only access
36 * RWPrivateCursor - Read-write access, assumes private access to IOBuf chain
37 * RWUnshareCursor - Read-write access, calls unshare on write (COW)
38 * Appender - Write access, assumes private access to IOBuf chian
40 * Note that RW cursors write in the preallocated part of buffers (that is,
41 * between the buffer's data() and tail()), while Appenders append to the end
42 * of the buffer (between the buffer's tail() and bufferEnd()). Appenders
43 * automatically adjust the buffer pointers, so you may only use one
44 * Appender with a buffer chain; for this reason, Appenders assume private
45 * access to the buffer (you need to call unshare() yourself if necessary).
47 namespace folly { namespace io {
50 template <class Derived, typename BufType>
53 const uint8_t* data() const {
54 return crtBuf_->data() + offset_;
57 // Space available in the current IOBuf. May be 0; use peek() instead which
58 // will always point to a non-empty chunk of data or at the end of the
60 size_t length() const {
61 return crtBuf_->length() - offset_;
64 Derived& operator+=(size_t offset) {
65 Derived* p = static_cast<Derived*>(this);
71 typename std::enable_if<std::is_integral<T>::value, T>::type
74 pull(&val, sizeof(T));
80 return Endian::big(read<T>());
85 return Endian::little(read<T>());
89 * Read a fixed-length string.
91 * The std::string-based APIs should probably be avoided unless you
92 * ultimately want the data to live in an std::string. You're better off
93 * using the pull() APIs to copy into a raw buffer otherwise.
95 std::string readFixedString(size_t len) {
100 // Fast path: it all fits in one buffer.
101 size_t available = length();
102 if (LIKELY(available >= len)) {
103 str.append(reinterpret_cast<const char*>(data()), len);
108 str.append(reinterpret_cast<const char*>(data()), available);
109 if (UNLIKELY(!tryAdvanceBuffer())) {
110 throw std::out_of_range("string underflow");
117 * Read a string consisting of bytes until the given terminator character is
118 * seen. Raises an std::length_error if maxLength bytes have been processed
119 * before the terminator is seen.
121 * See comments in readFixedString() about when it's appropriate to use this
124 std::string readTerminatedString(
125 char termChar = '\0',
126 size_t maxLength = std::numeric_limits<size_t>::max()) {
130 const uint8_t* buf = data();
131 size_t buflen = length();
134 while (i < buflen && buf[i] != termChar) {
137 // Do this check after incrementing 'i', as even though we start at the
138 // 0 byte, it still represents a single character
139 if (str.length() + i >= maxLength) {
140 throw std::length_error("string overflow");
144 str.append(reinterpret_cast<const char*>(buf), i);
152 if (UNLIKELY(!tryAdvanceBuffer())) {
153 throw std::out_of_range("string underflow");
158 explicit CursorBase(BufType* buf)
163 // Make all the templated classes friends for copy constructor.
164 template <class D, typename B> friend class CursorBase;
167 explicit CursorBase(const T& cursor) {
168 crtBuf_ = cursor.crtBuf_;
169 offset_ = cursor.offset_;
170 buffer_ = cursor.buffer_;
173 // reset cursor to point to a new buffer.
174 void reset(BufType* buf) {
181 * Return the available data in the current buffer.
182 * If you want to gather more data from the chain into a contiguous region
183 * (for hopefully zero-copy access), use gather() before peek().
185 std::pair<const uint8_t*, size_t> peek() {
186 // Ensure that we're pointing to valid data
187 size_t available = length();
188 while (UNLIKELY(available == 0 && tryAdvanceBuffer())) {
189 available = length();
192 return std::make_pair(data(), available);
195 void pull(void* buf, size_t length) {
196 if (UNLIKELY(pullAtMost(buf, length) != length)) {
197 throw std::out_of_range("underflow");
201 void clone(std::unique_ptr<folly::IOBuf>& buf, size_t length) {
202 if (UNLIKELY(cloneAtMost(buf, length) != length)) {
203 throw std::out_of_range("underflow");
207 void skip(size_t length) {
208 if (UNLIKELY(skipAtMost(length) != length)) {
209 throw std::out_of_range("underflow");
213 size_t pullAtMost(void* buf, size_t len) {
214 uint8_t* p = reinterpret_cast<uint8_t*>(buf);
217 // Fast path: it all fits in one buffer.
218 size_t available = length();
219 if (LIKELY(available >= len)) {
220 memcpy(p, data(), len);
225 memcpy(p, data(), available);
227 if (UNLIKELY(!tryAdvanceBuffer())) {
235 size_t cloneAtMost(std::unique_ptr<folly::IOBuf>& buf, size_t len) {
238 std::unique_ptr<folly::IOBuf> tmp;
241 // Fast path: it all fits in one buffer.
242 size_t available = length();
243 if (LIKELY(available >= len)) {
244 tmp = crtBuf_->cloneOne();
245 tmp->trimStart(offset_);
246 tmp->trimEnd(tmp->length() - len);
249 buf = std::move(tmp);
251 buf->prependChain(std::move(tmp));
256 tmp = crtBuf_->cloneOne();
257 tmp->trimStart(offset_);
259 buf = std::move(tmp);
261 buf->prependChain(std::move(tmp));
265 if (UNLIKELY(!tryAdvanceBuffer())) {
272 size_t skipAtMost(size_t len) {
275 // Fast path: it all fits in one buffer.
276 size_t available = length();
277 if (LIKELY(available >= len)) {
279 return skipped + len;
282 skipped += available;
283 if (UNLIKELY(!tryAdvanceBuffer())) {
291 * Return the distance between two cursors.
293 size_t operator-(const CursorBase& other) const {
294 BufType *otherBuf = other.crtBuf_;
297 if (otherBuf != crtBuf_) {
298 len += otherBuf->length() - other.offset_;
300 for (otherBuf = otherBuf->next();
301 otherBuf != crtBuf_ && otherBuf != other.buffer_;
302 otherBuf = otherBuf->next()) {
303 len += otherBuf->length();
306 if (otherBuf == other.buffer_) {
307 throw std::out_of_range("wrap-around");
312 if (offset_ < other.offset_) {
313 throw std::out_of_range("underflow");
316 len += offset_ - other.offset_;
323 * Return the distance from the given IOBuf to the this cursor.
325 size_t operator-(const BufType* buf) const {
328 BufType *curBuf = buf;
329 while (curBuf != crtBuf_) {
330 len += curBuf->length();
331 curBuf = curBuf->next();
332 if (curBuf == buf || curBuf == buffer_) {
333 throw std::out_of_range("wrap-around");
347 bool tryAdvanceBuffer() {
348 BufType* nextBuf = crtBuf_->next();
349 if (UNLIKELY(nextBuf == buffer_)) {
350 offset_ = crtBuf_->length();
356 static_cast<Derived*>(this)->advanceDone();
367 template <class Derived>
371 typename std::enable_if<std::is_integral<T>::value>::type
373 const uint8_t* u8 = reinterpret_cast<const uint8_t*>(&value);
378 void writeBE(T value) {
379 write(Endian::big(value));
383 void writeLE(T value) {
384 write(Endian::little(value));
387 void push(const uint8_t* buf, size_t len) {
388 Derived* d = static_cast<Derived*>(this);
389 if (d->pushAtMost(buf, len) != len) {
390 throw std::out_of_range("overflow");
395 } // namespace detail
397 class Cursor : public detail::CursorBase<Cursor, const IOBuf> {
399 explicit Cursor(const IOBuf* buf)
400 : detail::CursorBase<Cursor, const IOBuf>(buf) {}
402 template <class CursorType>
403 explicit Cursor(CursorType& cursor)
404 : detail::CursorBase<Cursor, const IOBuf>(cursor) {}
407 enum class CursorAccess {
412 template <CursorAccess access>
414 : public detail::CursorBase<RWCursor<access>, IOBuf>,
415 public detail::Writable<RWCursor<access>> {
416 friend class detail::CursorBase<RWCursor<access>, IOBuf>;
418 explicit RWCursor(IOBuf* buf)
419 : detail::CursorBase<RWCursor<access>, IOBuf>(buf),
420 maybeShared_(true) {}
422 template <class CursorType>
423 explicit RWCursor(CursorType& cursor)
424 : detail::CursorBase<RWCursor<access>, IOBuf>(cursor),
425 maybeShared_(true) {}
427 * Gather at least n bytes contiguously into the current buffer,
428 * by coalescing subsequent buffers from the chain as necessary.
430 void gather(size_t n) {
431 this->crtBuf_->gather(this->offset_ + n);
434 size_t pushAtMost(const uint8_t* buf, size_t len) {
437 // Fast path: the current buffer is big enough.
438 size_t available = this->length();
439 if (LIKELY(available >= len)) {
440 if (access == CursorAccess::UNSHARE) {
443 memcpy(writableData(), buf, len);
444 this->offset_ += len;
448 if (access == CursorAccess::UNSHARE) {
451 memcpy(writableData(), buf, available);
453 if (UNLIKELY(!this->tryAdvanceBuffer())) {
461 void insert(std::unique_ptr<folly::IOBuf> buf) {
462 folly::IOBuf* nextBuf;
463 if (this->offset_ == 0) {
466 this->crtBuf_->prependChain(std::move(buf));
468 std::unique_ptr<folly::IOBuf> remaining;
469 if (this->crtBuf_->length() - this->offset_ > 0) {
470 // Need to split current IOBuf in two.
471 remaining = this->crtBuf_->cloneOne();
472 remaining->trimStart(this->offset_);
473 nextBuf = remaining.get();
474 buf->prependChain(std::move(remaining));
477 nextBuf = this->crtBuf_->next();
479 this->crtBuf_->trimEnd(this->length());
480 this->crtBuf_->appendChain(std::move(buf));
482 // Jump past the new links
484 this->crtBuf_ = nextBuf;
487 uint8_t* writableData() {
488 return this->crtBuf_->writableData() + this->offset_;
492 void maybeUnshare() {
493 if (UNLIKELY(maybeShared_)) {
494 this->crtBuf_->unshareOne();
495 maybeShared_ = false;
506 typedef RWCursor<CursorAccess::PRIVATE> RWPrivateCursor;
507 typedef RWCursor<CursorAccess::UNSHARE> RWUnshareCursor;
510 * Append to the end of a buffer chain, growing the chain (by allocating new
511 * buffers) in increments of at least growth bytes every time. Won't grow
512 * (and push() and ensure() will throw) if growth == 0.
514 * TODO(tudorb): add a flavor of Appender that reallocates one IOBuf instead
517 class Appender : public detail::Writable<Appender> {
519 Appender(IOBuf* buf, uint32_t growth)
521 crtBuf_(buf->prev()),
525 uint8_t* writableData() {
526 return crtBuf_->writableTail();
529 size_t length() const {
530 return crtBuf_->tailroom();
534 * Mark n bytes (must be <= length()) as appended, as per the
535 * IOBuf::append() method.
537 void append(size_t n) {
542 * Ensure at least n contiguous bytes available to write.
543 * Postcondition: length() >= n.
545 void ensure(uint32_t n) {
546 if (LIKELY(length() >= n)) {
550 // Waste the rest of the current buffer and allocate a new one.
551 // Don't make it too small, either.
553 throw std::out_of_range("can't grow buffer chain");
556 n = std::max(n, growth_);
557 buffer_->prependChain(IOBuf::create(n));
558 crtBuf_ = buffer_->prev();
561 size_t pushAtMost(const uint8_t* buf, size_t len) {
564 // Fast path: it all fits in one buffer.
565 size_t available = length();
566 if (LIKELY(available >= len)) {
567 memcpy(writableData(), buf, len);
572 memcpy(writableData(), buf, available);
575 if (UNLIKELY(!tryGrowChain())) {
584 bool tryGrowChain() {
585 assert(crtBuf_->next() == buffer_);
590 buffer_->prependChain(IOBuf::create(growth_));
591 crtBuf_ = buffer_->prev();
600 class QueueAppender : public detail::Writable<QueueAppender> {
603 * Create an Appender that writes to a IOBufQueue. When we allocate
604 * space in the queue, we grow no more than growth bytes at once
605 * (unless you call ensure() with a bigger value yourself).
606 * Throw if we ever need to allocate more than maxTotalGrowth.
608 QueueAppender(IOBufQueue* queue,
610 size_t maxTotalGrowth = std::numeric_limits<size_t>::max()) {
611 reset(queue, growth, maxTotalGrowth);
614 void reset(IOBufQueue* queue,
616 size_t maxTotalGrowth = std::numeric_limits<size_t>::max()) {
619 remainingGrowth_ = maxTotalGrowth;
624 uint8_t* writableData() { return next_; }
626 size_t length() const { return available_; }
628 void append(size_t n) {
629 assert(n <= available_);
630 assert(n <= remainingGrowth_);
631 queue_->postallocate(n);
634 remainingGrowth_ -= n;
637 // Ensure at least n contiguous; can go above growth_, throws if
639 void ensure(uint32_t n) {
640 if (UNLIKELY(n > remainingGrowth_)) {
641 throw std::out_of_range("overflow");
644 if (LIKELY(length() >= n)) {
648 size_t desired = std::min(growth_, remainingGrowth_ - n);
651 auto p = queue_->preallocate(n, desired);
653 next_ = static_cast<uint8_t*>(p.first);
654 available_ = p.second;
657 size_t pushAtMost(const uint8_t* buf, size_t len) {
658 if (UNLIKELY(len > remainingGrowth_)) {
659 len = remainingGrowth_;
662 size_t remaining = len;
663 while (remaining != 0) {
664 ensure(std::min(remaining, growth_));
665 size_t n = std::min(remaining, available_);
666 memcpy(next_, buf, n);
675 // insert doesn't count towards maxTotalGrowth
676 void insert(std::unique_ptr<folly::IOBuf> buf) {
678 queue_->append(std::move(buf), true);
685 folly::IOBufQueue* queue_;
687 size_t remainingGrowth_;
694 #endif // FOLLY_CURSOR_H