X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2Fio%2FCursor.h;h=c16c6a45692bf41736ecb6a6b731b1032e3f6450;hb=6f8d37dc510dfbbf8beacc67b23d937bff69182d;hp=6ae8aef39fadc4863aff7d20044763f4d9e5b131;hpb=1d33fd218811e52e59ccb5824422e5cc96feb581;p=folly.git

diff --git a/folly/io/Cursor.h b/folly/io/Cursor.h
index 6ae8aef3..c16c6a45 100644
--- a/folly/io/Cursor.h
+++ b/folly/io/Cursor.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2014 Facebook, Inc.
+ * Copyright 2017 Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -14,8 +14,7 @@
  * limitations under the License.
  */
 
-#ifndef FOLLY_CURSOR_H
-#define FOLLY_CURSOR_H
+#pragma once
 
 #include <assert.h>
 #include <cstdarg>
@@ -25,12 +24,13 @@
 #include <memory>
 
 #include <folly/Bits.h>
-#include <folly/io/IOBuf.h>
-#include <folly/io/IOBufQueue.h>
 #include <folly/Likely.h>
 #include <folly/Memory.h>
 #include <folly/Portability.h>
 #include <folly/Range.h>
+#include <folly/io/IOBuf.h>
+#include <folly/io/IOBufQueue.h>
+#include <folly/portability/BitsFunctexcept.h>
 
 /**
  * Cursor class for fast iteration over IOBuf chains.
@@ -49,28 +49,54 @@
  * access to the buffer (you need to call unshare() yourself if necessary).
  **/
 namespace folly { namespace io {
+
 namespace detail {
 
-template <class Derived, typename BufType>
+template <class Derived, class BufType>
 class CursorBase {
+  // Make all the templated classes friends for copy constructor.
+  template <class D, typename B> friend class CursorBase;
  public:
+  explicit CursorBase(BufType* buf) : crtBuf_(buf), buffer_(buf) { }
+
+  /**
+   * Copy constructor.
+   *
+   * This also allows constructing a CursorBase from other derived types.
+   * For instance, this allows constructing a Cursor from an RWPrivateCursor.
+   */
+  template <class OtherDerived, class OtherBuf>
+  explicit CursorBase(const CursorBase<OtherDerived, OtherBuf>& cursor)
+    : crtBuf_(cursor.crtBuf_),
+      offset_(cursor.offset_),
+      buffer_(cursor.buffer_) { }
+
+  /**
+   * Reset cursor to point to a new buffer.
+   */
+  void reset(BufType* buf) {
+    crtBuf_ = buf;
+    buffer_ = buf;
+    offset_ = 0;
+  }
+
   const uint8_t* data() const {
     return crtBuf_->data() + offset_;
   }
 
-  /*
+  /**
    * Return the remaining space available in the current IOBuf.
    *
-   * May return 0 if the cursor is at the end of an IOBuf.  Use peek() instead
-   * if you want to avoid this.  peek() will advance to the next non-empty
-   * IOBuf (up to the end of the chain) if the cursor is currently pointing at
-   * the end of a buffer.
+   * May return 0 if the cursor is at the end of an IOBuf.  Use peekBytes()
+   * instead if you want to avoid this.  peekBytes() will advance to the next
+   * non-empty IOBuf (up to the end of the chain) if the cursor is currently
+   * pointing at the end of a buffer.
    */
   size_t length() const {
     return crtBuf_->length() - offset_;
   }
 
-  /*
+  /**
    * Return the space available until the end of the entire IOBuf chain.
    */
   size_t totalLength() const {
@@ -82,6 +108,62 @@ class CursorBase {
     return end - *this;
   }
 
+  /**
+   * Return true if the cursor could advance the specified number of bytes
+   * from its current position.
+   * This is useful for applications that want to do checked reads instead of
+   * catching exceptions and is more efficient than using totalLength as it
+   * walks the minimal set of buffers in the chain to determine the result.
+   */
+  bool canAdvance(size_t amount) const {
+    const IOBuf* nextBuf = crtBuf_;
+    size_t available = length();
+    do {
+      if (available >= amount) {
+        return true;
+      }
+      amount -= available;
+      nextBuf = nextBuf->next();
+      available = nextBuf->length();
+    } while (nextBuf != buffer_);
+    return false;
+  }
+
+  /*
+   * Return true if the cursor is at the end of the entire IOBuf chain.
+   */
+  bool isAtEnd() const {
+    // Check for the simple cases first.
+    if (offset_ != crtBuf_->length()) {
+      return false;
+    }
+    if (crtBuf_ == buffer_->prev()) {
+      return true;
+    }
+    // We are at the end of a buffer, but it isn't the last buffer.
+    // We might still be at the end if the remaining buffers in the chain are
+    // empty.
+    const IOBuf* buf = crtBuf_->next();;
+    while (buf != buffer_) {
+      if (buf->length() > 0) {
+        return false;
+      }
+      buf = buf->next();
+    }
+    return true;
+  }
+
+  /**
+   * Advances the cursor to the end of the entire IOBuf chain.
+   */
+  void advanceToEnd() {
+    offset_ = buffer_->prev()->length();
+    if (crtBuf_ != buffer_->prev()) {
+      crtBuf_ = buffer_->prev();
+      static_cast<Derived*>(this)->advanceDone();
+    }
+  }
+
   Derived& operator+=(size_t offset) {
     Derived* p = static_cast<Derived*>(this);
     p->skip(offset);
@@ -93,6 +175,17 @@ class CursorBase {
     return other;
   }
 
+  Derived& operator-=(size_t offset) {
+    Derived* p = static_cast<Derived*>(this);
+    p->retreat(offset);
+    return *p;
+  }
+  Derived operator-(size_t offset) const {
+    Derived other(*this);
+    other.retreat(offset);
+    return other;
+  }
+
   /**
    * Compare cursors for equality/inequality.
    *
@@ -107,10 +200,15 @@ class CursorBase {
   }
 
   template <class T>
-  typename std::enable_if<std::is_arithmetic<T>::value, T>::type
-  read() {
+  typename std::enable_if<std::is_arithmetic<T>::value, T>::type read() {
     T val;
-    pull(&val, sizeof(T));
+    if (LIKELY(length() >= sizeof(T))) {
+      val = loadUnaligned<T>(data());
+      offset_ += sizeof(T);
+      advanceBufferIfEmpty();
+    } else {
+      pullSlow(&val, sizeof(T));
+    }
     return val;
   }
 
@@ -133,23 +231,15 @@ class CursorBase {
    */
   std::string readFixedString(size_t len) {
     std::string str;
-
     str.reserve(len);
-    for (;;) {
-      // Fast path: it all fits in one buffer.
-      size_t available = length();
-      if (LIKELY(available >= len)) {
-        str.append(reinterpret_cast<const char*>(data()), len);
-        offset_ += len;
-        return str;
-      }
-
-      str.append(reinterpret_cast<const char*>(data()), available);
-      if (UNLIKELY(!tryAdvanceBuffer())) {
-        throw std::out_of_range("string underflow");
-      }
-      len -= available;
+    if (LIKELY(length() >= len)) {
+      str.append(reinterpret_cast<const char*>(data()), len);
+      offset_ += len;
+      advanceBufferIfEmpty();
+    } else {
+      readFixedStringSlow(&str, len);
     }
+    return str;
   }
 
   /**
@@ -161,130 +251,131 @@ class CursorBase {
    * vs. using pull().
    */
   std::string readTerminatedString(
-    char termChar = '\0',
-    size_t maxLength = std::numeric_limits<size_t>::max()) {
-    std::string str;
-
-    for (;;) {
-      const uint8_t* buf = data();
-      size_t buflen = length();
+      char termChar = '\0',
+      size_t maxLength = std::numeric_limits<size_t>::max());
 
-      size_t i = 0;
-      while (i < buflen && buf[i] != termChar) {
-        ++i;
+  /*
+   * Read all bytes until the specified predicate returns true.
+   *
+   * The predicate will be called on each byte in turn, until it returns false
+   * or until the end of the IOBuf chain is reached.
+   *
+   * Returns the result as a string.
+   */
+  template <typename Predicate>
+  std::string readWhile(const Predicate& predicate);
 
-        // Do this check after incrementing 'i', as even though we start at the
-        // 0 byte, it still represents a single character
-        if (str.length() + i >= maxLength) {
-          throw std::length_error("string overflow");
-        }
-      }
+  /*
+   * Read all bytes until the specified predicate returns true.
+   *
+   * This is a more generic version of readWhile() takes an arbitrary Output
+   * object, and calls Output::append() with each chunk of matching data.
+   */
+  template <typename Predicate, typename Output>
+  void readWhile(const Predicate& predicate, Output& out);
 
-      str.append(reinterpret_cast<const char*>(buf), i);
-      if (i < buflen) {
-        skip(i + 1);
-        return str;
-      }
+  /*
+   * Skip all bytes until the specified predicate returns true.
+   *
+   * The predicate will be called on each byte in turn, until it returns false
+   * or until the end of the IOBuf chain is reached.
+   */
+  template <typename Predicate>
+  void skipWhile(const Predicate& predicate);
 
-      skip(i);
+  size_t skipAtMost(size_t len) {
+    if (LIKELY(length() >= len)) {
+      offset_ += len;
+      advanceBufferIfEmpty();
+      return len;
+    }
+    return skipAtMostSlow(len);
+  }
 
-      if (UNLIKELY(!tryAdvanceBuffer())) {
-        throw std::out_of_range("string underflow");
-      }
+  void skip(size_t len) {
+    if (LIKELY(length() >= len)) {
+      offset_ += len;
+      advanceBufferIfEmpty();
+    } else {
+      skipSlow(len);
     }
   }
 
-  explicit CursorBase(BufType* buf)
-    : crtBuf_(buf)
-    , offset_(0)
-    , buffer_(buf) {}
+  size_t retreatAtMost(size_t len) {
+    if (len <= offset_) {
+      offset_ -= len;
+      return len;
+    }
+    return retreatAtMostSlow(len);
+  }
 
-  // Make all the templated classes friends for copy constructor.
-  template <class D, typename B> friend class CursorBase;
+  void retreat(size_t len) {
+    if (len <= offset_) {
+      offset_ -= len;
+    } else {
+      retreatSlow(len);
+    }
+  }
 
-  /*
-   * Copy constructor.
-   *
-   * This also allows constructing a CursorBase from other derived types.
-   * For instance, this allows constructing a Cursor from an RWPrivateCursor.
-   */
-  template <class OtherDerived, class OtherBuf>
-  explicit CursorBase(const CursorBase<OtherDerived, OtherBuf>& cursor)
-    : crtBuf_(cursor.crtBuf_),
-      offset_(cursor.offset_),
-      buffer_(cursor.buffer_) {}
+  size_t pullAtMost(void* buf, size_t len) {
+    // Fast path: it all fits in one buffer.
+    if (LIKELY(length() >= len)) {
+      memcpy(buf, data(), len);
+      offset_ += len;
+      advanceBufferIfEmpty();
+      return len;
+    }
+    return pullAtMostSlow(buf, len);
+  }
 
-  // reset cursor to point to a new buffer.
-  void reset(BufType* buf) {
-    crtBuf_ = buf;
-    buffer_ = buf;
-    offset_ = 0;
+  void pull(void* buf, size_t len) {
+    if (LIKELY(length() >= len)) {
+      memcpy(buf, data(), len);
+      offset_ += len;
+      advanceBufferIfEmpty();
+    } else {
+      pullSlow(buf, len);
+    }
   }
 
   /**
    * Return the available data in the current buffer.
    * If you want to gather more data from the chain into a contiguous region
-   * (for hopefully zero-copy access), use gather() before peek().
+   * (for hopefully zero-copy access), use gather() before peekBytes().
    */
-  std::pair<const uint8_t*, size_t> peek() {
+  ByteRange peekBytes() {
     // Ensure that we're pointing to valid data
     size_t available = length();
     while (UNLIKELY(available == 0 && tryAdvanceBuffer())) {
       available = length();
     }
-
-    return std::make_pair(data(), available);
+    return ByteRange{data(), available};
   }
 
-  void pull(void* buf, size_t len) {
-    if (UNLIKELY(pullAtMost(buf, len) != len)) {
-      throw std::out_of_range("underflow");
-    }
+  /**
+   * Alternate version of peekBytes() that returns a std::pair
+   * instead of a ByteRange.  (This method pre-dates ByteRange.)
+   *
+   * This function will eventually be deprecated.
+   */
+  std::pair<const uint8_t*, size_t> peek() {
+    auto bytes = peekBytes();
+    return std::make_pair(bytes.data(), bytes.size());
   }
 
   void clone(std::unique_ptr<folly::IOBuf>& buf, size_t len) {
     if (UNLIKELY(cloneAtMost(buf, len) != len)) {
-      throw std::out_of_range("underflow");
+      std::__throw_out_of_range("underflow");
     }
   }
 
   void clone(folly::IOBuf& buf, size_t len) {
     if (UNLIKELY(cloneAtMost(buf, len) != len)) {
-      throw std::out_of_range("underflow");
-    }
-  }
-
-  void skip(size_t len) {
-    if (UNLIKELY(skipAtMost(len) != len)) {
-      throw std::out_of_range("underflow");
-    }
-  }
-
-  size_t pullAtMost(void* buf, size_t len) {
-    uint8_t* p = reinterpret_cast<uint8_t*>(buf);
-    size_t copied = 0;
-    for (;;) {
-      // Fast path: it all fits in one buffer.
-      size_t available = length();
-      if (LIKELY(available >= len)) {
-        memcpy(p, data(), len);
-        offset_ += len;
-        return copied + len;
-      }
-
-      memcpy(p, data(), available);
-      copied += available;
-      if (UNLIKELY(!tryAdvanceBuffer())) {
-        return copied;
-      }
-      p += available;
-      len -= available;
+      std::__throw_out_of_range("underflow");
     }
   }
 
   size_t cloneAtMost(folly::IOBuf& buf, size_t len) {
-    buf = folly::IOBuf();
-
     std::unique_ptr<folly::IOBuf> tmp;
     size_t copied = 0;
     for (int loopCount = 0; true; ++loopCount) {
@@ -303,10 +394,10 @@ class CursorBase {
         }
 
         offset_ += len;
+        advanceBufferIfEmpty();
         return copied + len;
       }
 
-
       if (loopCount == 0) {
         crtBuf_->cloneOneInto(buf);
         buf.trimStart(offset_);
@@ -328,28 +419,9 @@ class CursorBase {
     if (!buf) {
       buf = make_unique<folly::IOBuf>();
     }
-
     return cloneAtMost(*buf, len);
   }
 
-  size_t skipAtMost(size_t len) {
-    size_t skipped = 0;
-    for (;;) {
-      // Fast path: it all fits in one buffer.
-      size_t available = length();
-      if (LIKELY(available >= len)) {
-        offset_ += len;
-        return skipped + len;
-      }
-
-      skipped += available;
-      if (UNLIKELY(!tryAdvanceBuffer())) {
-        return skipped;
-      }
-      len -= available;
-    }
-  }
-
   /**
    * Return the distance between two cursors.
    */
@@ -367,13 +439,13 @@ class CursorBase {
       }
 
       if (otherBuf == other.buffer_) {
-        throw std::out_of_range("wrap-around");
+        std::__throw_out_of_range("wrap-around");
       }
 
       len += offset_;
     } else {
       if (offset_ < other.offset_) {
-        throw std::out_of_range("underflow");
+        std::__throw_out_of_range("underflow");
       }
 
       len += offset_ - other.offset_;
@@ -388,12 +460,12 @@ class CursorBase {
   size_t operator-(const BufType* buf) const {
     size_t len = 0;
 
-    BufType *curBuf = buf;
+    const BufType* curBuf = buf;
     while (curBuf != crtBuf_) {
       len += curBuf->length();
       curBuf = curBuf->next();
       if (curBuf == buf || curBuf == buffer_) {
-        throw std::out_of_range("wrap-around");
+        std::__throw_out_of_range("wrap-around");
       }
     }
 
@@ -402,10 +474,7 @@ class CursorBase {
   }
 
  protected:
-  BufType* crtBuf_;
-  size_t offset_;
-
-  ~CursorBase(){}
+  ~CursorBase() { }
 
   BufType* head() {
     return buffer_;
@@ -424,14 +493,110 @@ class CursorBase {
     return true;
   }
 
+  bool tryRetreatBuffer() {
+    if (UNLIKELY(crtBuf_ == buffer_)) {
+      offset_ = 0;
+      return false;
+    }
+    crtBuf_ = crtBuf_->prev();
+    offset_ = crtBuf_->length();
+    static_cast<Derived*>(this)->advanceDone();
+    return true;
+  }
+
+  void advanceBufferIfEmpty() {
+    if (length() == 0) {
+      tryAdvanceBuffer();
+    }
+  }
+
+  BufType* crtBuf_;
+  size_t offset_ = 0;
+
  private:
+  void readFixedStringSlow(std::string* str, size_t len) {
+    for (size_t available; (available = length()) < len; ) {
+      str->append(reinterpret_cast<const char*>(data()), available);
+      if (UNLIKELY(!tryAdvanceBuffer())) {
+        std::__throw_out_of_range("string underflow");
+      }
+      len -= available;
+    }
+    str->append(reinterpret_cast<const char*>(data()), len);
+    offset_ += len;
+    advanceBufferIfEmpty();
+  }
+
+  size_t pullAtMostSlow(void* buf, size_t len) {
+    uint8_t* p = reinterpret_cast<uint8_t*>(buf);
+    size_t copied = 0;
+    for (size_t available; (available = length()) < len; ) {
+      memcpy(p, data(), available);
+      copied += available;
+      if (UNLIKELY(!tryAdvanceBuffer())) {
+        return copied;
+      }
+      p += available;
+      len -= available;
+    }
+    memcpy(p, data(), len);
+    offset_ += len;
+    advanceBufferIfEmpty();
+    return copied + len;
+  }
+
+  void pullSlow(void* buf, size_t len) {
+    if (UNLIKELY(pullAtMostSlow(buf, len) != len)) {
+      std::__throw_out_of_range("underflow");
+    }
+  }
+
+  size_t skipAtMostSlow(size_t len) {
+    size_t skipped = 0;
+    for (size_t available; (available = length()) < len; ) {
+      skipped += available;
+      if (UNLIKELY(!tryAdvanceBuffer())) {
+        return skipped;
+      }
+      len -= available;
+    }
+    offset_ += len;
+    advanceBufferIfEmpty();
+    return skipped + len;
+  }
+
+  void skipSlow(size_t len) {
+    if (UNLIKELY(skipAtMostSlow(len) != len)) {
+      std::__throw_out_of_range("underflow");
+    }
+  }
+
+  size_t retreatAtMostSlow(size_t len) {
+    size_t retreated = 0;
+    for (size_t available; (available = offset_) < len;) {
+      retreated += available;
+      if (UNLIKELY(!tryRetreatBuffer())) {
+        return retreated;
+      }
+      len -= available;
+    }
+    offset_ -= len;
+    return retreated + len;
+  }
+
+  void retreatSlow(size_t len) {
+    if (UNLIKELY(retreatAtMostSlow(len) != len)) {
+      std::__throw_out_of_range("underflow");
+    }
+  }
+
   void advanceDone() {
   }
 
   BufType* buffer_;
 };
 
-} //namespace detail
+}  // namespace detail
 
 class Cursor : public detail::CursorBase<Cursor, const IOBuf> {
  public:
@@ -471,13 +636,13 @@ class Writable {
   void push(const uint8_t* buf, size_t len) {
     Derived* d = static_cast<Derived*>(this);
     if (d->pushAtMost(buf, len) != len) {
-      throw std::out_of_range("overflow");
+      std::__throw_out_of_range("overflow");
     }
   }
 
   void push(ByteRange buf) {
     if (this->pushAtMost(buf) != buf.size()) {
-      throw std::out_of_range("overflow");
+      std::__throw_out_of_range("overflow");
     }
   }
 
@@ -493,16 +658,16 @@ class Writable {
    */
   void push(Cursor cursor, size_t len) {
     if (this->pushAtMost(cursor, len) != len) {
-      throw std::out_of_range("overflow");
+      std::__throw_out_of_range("overflow");
     }
   }
 
   size_t pushAtMost(Cursor cursor, size_t len) {
     size_t written = 0;
     for(;;) {
-      auto currentBuffer = cursor.peek();
-      const uint8_t* crtData = currentBuffer.first;
-      size_t available = currentBuffer.second;
+      auto currentBuffer = cursor.peekBytes();
+      const uint8_t* crtData = currentBuffer.data();
+      size_t available = currentBuffer.size();
       if (available == 0) {
         // end of buffer chain
         return written;
@@ -687,7 +852,7 @@ class Appender : public detail::Writable<Appender> {
     // Waste the rest of the current buffer and allocate a new one.
     // Don't make it too small, either.
     if (growth_ == 0) {
-      throw std::out_of_range("can't grow buffer chain");
+      std::__throw_out_of_range("can't grow buffer chain");
     }
 
     n = std::max(n, growth_);
@@ -830,6 +995,10 @@ class QueueAppender : public detail::Writable<QueueAppender> {
     }
   }
 
+  void insert(const folly::IOBuf& buf) {
+    insert(buf.clone());
+  }
+
  private:
   folly::IOBufQueue* queue_;
   size_t growth_;
@@ -837,4 +1006,4 @@ class QueueAppender : public detail::Writable<QueueAppender> {
 
 }}  // folly::io
 
-#endif // FOLLY_CURSOR_H
+#include <folly/io/Cursor-inl.h>