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 len) {
196 if (UNLIKELY(pullAtMost(buf, len) != len)) {
197 throw std::out_of_range("underflow");
201 void clone(std::unique_ptr<folly::IOBuf>& buf, size_t len) {
202 if (UNLIKELY(cloneAtMost(buf, len) != len)) {
203 throw std::out_of_range("underflow");
207 void skip(size_t len) {
208 if (UNLIKELY(skipAtMost(len) != len)) {
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);
374 Derived* d = static_cast<Derived*>(this);
379 void writeBE(T value) {
380 Derived* d = static_cast<Derived*>(this);
381 d->write(Endian::big(value));
385 void writeLE(T value) {
386 Derived* d = static_cast<Derived*>(this);
387 d->write(Endian::little(value));
390 void push(const uint8_t* buf, size_t len) {
391 Derived* d = static_cast<Derived*>(this);
392 if (d->pushAtMost(buf, len) != len) {
393 throw std::out_of_range("overflow");
398 } // namespace detail
400 class Cursor : public detail::CursorBase<Cursor, const IOBuf> {
402 explicit Cursor(const IOBuf* buf)
403 : detail::CursorBase<Cursor, const IOBuf>(buf) {}
405 template <class CursorType>
406 explicit Cursor(CursorType& cursor)
407 : detail::CursorBase<Cursor, const IOBuf>(cursor) {}
410 enum class CursorAccess {
415 template <CursorAccess access>
417 : public detail::CursorBase<RWCursor<access>, IOBuf>,
418 public detail::Writable<RWCursor<access>> {
419 friend class detail::CursorBase<RWCursor<access>, IOBuf>;
421 explicit RWCursor(IOBuf* buf)
422 : detail::CursorBase<RWCursor<access>, IOBuf>(buf),
423 maybeShared_(true) {}
425 template <class CursorType>
426 explicit RWCursor(CursorType& cursor)
427 : detail::CursorBase<RWCursor<access>, IOBuf>(cursor),
428 maybeShared_(true) {}
430 * Gather at least n bytes contiguously into the current buffer,
431 * by coalescing subsequent buffers from the chain as necessary.
433 void gather(size_t n) {
434 this->crtBuf_->gather(this->offset_ + n);
437 size_t pushAtMost(const uint8_t* buf, size_t len) {
440 // Fast path: the current buffer is big enough.
441 size_t available = this->length();
442 if (LIKELY(available >= len)) {
443 if (access == CursorAccess::UNSHARE) {
446 memcpy(writableData(), buf, len);
447 this->offset_ += len;
451 if (access == CursorAccess::UNSHARE) {
454 memcpy(writableData(), buf, available);
456 if (UNLIKELY(!this->tryAdvanceBuffer())) {
464 void insert(std::unique_ptr<folly::IOBuf> buf) {
465 folly::IOBuf* nextBuf;
466 if (this->offset_ == 0) {
469 this->crtBuf_->prependChain(std::move(buf));
471 std::unique_ptr<folly::IOBuf> remaining;
472 if (this->crtBuf_->length() - this->offset_ > 0) {
473 // Need to split current IOBuf in two.
474 remaining = this->crtBuf_->cloneOne();
475 remaining->trimStart(this->offset_);
476 nextBuf = remaining.get();
477 buf->prependChain(std::move(remaining));
480 nextBuf = this->crtBuf_->next();
482 this->crtBuf_->trimEnd(this->length());
483 this->crtBuf_->appendChain(std::move(buf));
485 // Jump past the new links
487 this->crtBuf_ = nextBuf;
490 uint8_t* writableData() {
491 return this->crtBuf_->writableData() + this->offset_;
495 void maybeUnshare() {
496 if (UNLIKELY(maybeShared_)) {
497 this->crtBuf_->unshareOne();
498 maybeShared_ = false;
509 typedef RWCursor<CursorAccess::PRIVATE> RWPrivateCursor;
510 typedef RWCursor<CursorAccess::UNSHARE> RWUnshareCursor;
513 * Append to the end of a buffer chain, growing the chain (by allocating new
514 * buffers) in increments of at least growth bytes every time. Won't grow
515 * (and push() and ensure() will throw) if growth == 0.
517 * TODO(tudorb): add a flavor of Appender that reallocates one IOBuf instead
520 class Appender : public detail::Writable<Appender> {
522 Appender(IOBuf* buf, uint32_t growth)
524 crtBuf_(buf->prev()),
528 uint8_t* writableData() {
529 return crtBuf_->writableTail();
532 size_t length() const {
533 return crtBuf_->tailroom();
537 * Mark n bytes (must be <= length()) as appended, as per the
538 * IOBuf::append() method.
540 void append(size_t n) {
545 * Ensure at least n contiguous bytes available to write.
546 * Postcondition: length() >= n.
548 void ensure(uint32_t n) {
549 if (LIKELY(length() >= n)) {
553 // Waste the rest of the current buffer and allocate a new one.
554 // Don't make it too small, either.
556 throw std::out_of_range("can't grow buffer chain");
559 n = std::max(n, growth_);
560 buffer_->prependChain(IOBuf::create(n));
561 crtBuf_ = buffer_->prev();
564 size_t pushAtMost(const uint8_t* buf, size_t len) {
567 // Fast path: it all fits in one buffer.
568 size_t available = length();
569 if (LIKELY(available >= len)) {
570 memcpy(writableData(), buf, len);
575 memcpy(writableData(), buf, available);
578 if (UNLIKELY(!tryGrowChain())) {
587 bool tryGrowChain() {
588 assert(crtBuf_->next() == buffer_);
593 buffer_->prependChain(IOBuf::create(growth_));
594 crtBuf_ = buffer_->prev();
603 class QueueAppender : public detail::Writable<QueueAppender> {
606 * Create an Appender that writes to a IOBufQueue. When we allocate
607 * space in the queue, we grow no more than growth bytes at once
608 * (unless you call ensure() with a bigger value yourself).
610 QueueAppender(IOBufQueue* queue, uint32_t growth) {
611 reset(queue, growth);
614 void reset(IOBufQueue* queue, uint32_t growth) {
619 uint8_t* writableData() {
620 return static_cast<uint8_t*>(queue_->writableTail());
623 size_t length() const { return queue_->tailroom(); }
625 void append(size_t n) { queue_->postallocate(n); }
627 // Ensure at least n contiguous; can go above growth_, throws if
629 void ensure(uint32_t n) { queue_->preallocate(n, growth_); }
632 typename std::enable_if<std::is_integral<T>::value>::type
635 auto p = queue_->preallocate(sizeof(T), growth_);
636 storeUnaligned(p.first, value);
637 queue_->postallocate(sizeof(T));
641 size_t pushAtMost(const uint8_t* buf, size_t len) {
642 size_t remaining = len;
643 while (remaining != 0) {
644 auto p = queue_->preallocate(std::min(remaining, growth_),
647 memcpy(p.first, buf, p.second);
648 queue_->postallocate(p.second);
650 remaining -= p.second;
656 void insert(std::unique_ptr<folly::IOBuf> buf) {
658 queue_->append(std::move(buf), true);
663 folly::IOBufQueue* queue_;
669 #endif // FOLLY_CURSOR_H