YugabyteDB (2.13.0.0-b42, bfc6a6643e7399ac8a0e81d06a3ee6d6571b33ab)

// Copyright 2013 Facebook

//

// The following only applies to changes made to this file as part of YugaByte development.

//

// Portions Copyright (c) YugaByte, Inc.

//

// Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except

// in compliance with the License.  You may obtain a copy of the License at

//

// http://www.apache.org/licenses/LICENSE-2.0

//

// Unless required by applicable law or agreed to in writing, software distributed under the License

// is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express

// or implied.  See the License for the specific language governing permissions and limitations

// under the License.

//

/**

 * RedisListIterator:

 * An abstraction over the "list" concept (e.g.: for redis lists).

 * Provides functionality to read, traverse, edit, and write these lists.

 *

 * Upon construction, the RedisListIterator is given a block of list data.

 * Internally, it stores a pointer to the data and a pointer to current item.

 * It also stores a "result" list that will be mutated over time.

 *

 * Traversal and mutation are done by "forward iteration".

 * The Push() and Skip() methods will advance the iterator to the next item.

 * However, Push() will also "write the current item to the result".

 * Skip() will simply move to next item, causing current item to be dropped.

 *

 * Upon completion, the result (accessible by WriteResult()) will be saved.

 * All "skipped" items will be gone; all "pushed" items will remain.

 *

 * @throws Any of the operations may throw a RedisListException if an invalid

 *          operation is performed or if the data is found to be corrupt.

 *

 * @notes By default, if WriteResult() is called part-way through iteration,

 *        it will automatically advance the iterator to the end, and Keep()

 *        all items that haven't been traversed yet. This may be subject

 *        to review.

 *

 * @notes Can access the "current" item via GetCurrent(), and other

 *        list-specific information such as Length().

 *

 * @notes The internal representation is due to change at any time. Presently,

 *        the list is represented as follows:

 *          - 32-bit integer header: the number of items in the list

 *          - For each item:

 *              - 32-bit int (n): the number of bytes representing this item

 *              - n bytes of data: the actual data.

 *

 * @author Deon Nicholas (dnicholas@fb.com)

 */

#pragma once

#ifndef ROCKSDB_LITE

#include <string>

#include "redis_list_exception.h"

#include "yb/util/slice.h"

#include "yb/rocksdb/util/coding.h"

namespace rocksdb {

/// An abstraction over the "list" concept.

/// All operations may throw a RedisListException

class RedisListIterator {

 public:

  /// Construct a redis-list-iterator based on data.

  /// If the data is non-empty, it must formatted according to @notes above.

  ///

  /// If the data is valid, we can assume the following invariant(s):

  ///  a) length_, num_bytes_ are set correctly.

  ///  b) cur_byte_ always refers to the start of the current element,

  ///       just before the bytes that specify element length.

  ///  c) cur_elem_ is always the index of the current element.

  ///  d) cur_elem_length_ is always the number of bytes in current element,

  ///       excluding the 4-byte header itself.

  ///  e) result_ will always contain data_[0..cur_byte_) and a header

  ///  f) Whenever corrupt data is encountered or an invalid operation is

  ///      attempted, a RedisListException will immediately be thrown.

  explicit RedisListIterator(const std::string& list_data)

      : data_(list_data.data()),

        num_bytes_(static_cast<uint32_t>(list_data.size())),

        cur_byte_(0),

        cur_elem_(0),

        cur_elem_length_(0),

        length_(0),

        result_() {

    // Initialize the result_ (reserve enough space for header)

    InitializeResult();

    // Parse the data only if it is not empty.

    if (num_bytes_ == 0) {

      return;

    }

    // If non-empty, but less than 4 bytes, data must be corrupt

    if (num_bytes_ < sizeof(length_)) {

      ThrowError("Corrupt header.");    // Will break control flow

    }

    // Good. The first bytes specify the number of elements

    length_ = DecodeFixed32(data_);

    cur_byte_ = sizeof(length_);

    // If we have at least one element, point to that element.

    // Also, read the first integer of the element (specifying the size),

    //   if possible.

    if (length_ > 0) {

      if (cur_byte_ + sizeof(cur_elem_length_) <= num_bytes_) {

        cur_elem_length_ = DecodeFixed32(data_+cur_byte_);

      } else {

        ThrowError("Corrupt data for first element.");

      }

    }

    // At this point, we are fully set-up.

    // The invariants described in the header should now be true.

  }

  /// Reserve some space for the result_.

  /// Equivalent to result_.reserve(bytes).

  void Reserve(int bytes) {

    result_.reserve(bytes);

  }

  /// Go to next element in data file.

  /// Also writes the current element to result_.

  RedisListIterator& Push() {

    WriteCurrentElement();

    MoveNext();

    return *this;

  }

  /// Go to next element in data file.

  /// Drops/skips the current element. It will not be written to result_.

  RedisListIterator& Skip() {

    MoveNext();

    --length_;          // One less item

    --cur_elem_;        // We moved one forward, but index did not change

    return *this;

  }

  /// Insert elem into the result_ (just BEFORE the current element / byte)

  /// Note: if Done() (i.e.: iterator points to end), this will append elem.

  void InsertElement(const Slice& elem) {

    // Ensure we are in a valid state

    CheckErrors();

    const int kOrigSize = static_cast<int>(result_.size());

    result_.resize(kOrigSize + SizeOf(elem));

    EncodeFixed32(result_.data() + kOrigSize,

                  static_cast<uint32_t>(elem.size()));

    memcpy(result_.data() + kOrigSize + sizeof(uint32_t), elem.data(),

           elem.size());

    ++length_;

    ++cur_elem_;

  }

  /// Access the current element, and save the result into *curElem

  void GetCurrent(Slice* curElem) {

    // Ensure we are in a valid state

    CheckErrors();

    // Ensure that we are not past the last element.

    if (Done()) {

      ThrowError("Invalid dereferencing.");

    }

    // Dereference the element

    *curElem = Slice(data_+cur_byte_+sizeof(cur_elem_length_),

                     cur_elem_length_);

  }

  // Number of elements

  int Length() const {

    return length_;

  }

  // Number of bytes in the final representation (i.e: WriteResult().size())

  int Size() const {

    // result_ holds the currently written data

    // data_[cur_byte..num_bytes-1] is the remainder of the data

    return static_cast<int>(result_.size() + (num_bytes_ - cur_byte_));

  }

  // Reached the end?

  bool Done() const {

    return cur_byte_ >= num_bytes_ || cur_elem_ >= length_;

  }

  /// Returns a string representing the final, edited, data.

  /// Assumes that all bytes of data_ in the range [0,cur_byte_) have been read

  ///  and that result_ contains this data.

  /// The rest of the data must still be written.

  /// So, this method ADVANCES THE ITERATOR TO THE END before writing.

  Slice WriteResult() {

    CheckErrors();

    // The header should currently be filled with dummy data (0's)

    // Correctly update the header.

    // Note, this is safe since result_ is a vector (guaranteed contiguous)

    EncodeFixed32(&result_[0],length_);

    // Append the remainder of the data to the result.

    result_.insert(result_.end(),data_+cur_byte_, data_ +num_bytes_);

    // Seek to end of file

    cur_byte_ = num_bytes_;

    cur_elem_ = length_;

    cur_elem_length_ = 0;

    // Return the result

    return Slice(result_.data(),result_.size());

  }

 public: // Static public functions

  /// An upper-bound on the amount of bytes needed to store this element.

  /// This is used to hide representation information from the client.

  /// E.G. This can be used to compute the bytes we want to Reserve().

  static uint32_t SizeOf(const Slice& elem) {

    // [Integer Length . Data]

    return static_cast<uint32_t>(sizeof(uint32_t) + elem.size());

  }

 private: // Private functions

  /// Initializes the result_ string.

  /// It will fill the first few bytes with 0's so that there is

  ///  enough space for header information when we need to write later.

  /// Currently, "header information" means: the length (number of elements)

  /// Assumes that result_ is empty to begin with

  void InitializeResult() {

    assert(result_.empty());            // Should always be true.

    result_.resize(sizeof(uint32_t),0); // Put a block of 0's as the header

  }

  /// Go to the next element (used in Push() and Skip())

  void MoveNext() {

    CheckErrors();

    // Check to make sure we are not already in a finished state

    if (Done()) {

      ThrowError("Attempting to iterate past end of list.");

    }

    // Move forward one element.

    cur_byte_ += sizeof(cur_elem_length_) + cur_elem_length_;

    ++cur_elem_;

    // If we are at the end, finish

    if (Done()) {

      cur_elem_length_ = 0;

      return;

    }

    // Otherwise, we should be able to read the new element's length

    if (cur_byte_ + sizeof(cur_elem_length_) > num_bytes_) {

      ThrowError("Corrupt element data.");

    }

    // Set the new element's length

    cur_elem_length_ = DecodeFixed32(data_+cur_byte_);

    return;

  }

  /// Append the current element (pointed to by cur_byte_) to result_

  /// Assumes result_ has already been reserved appropriately.

  void WriteCurrentElement() {

    // First verify that the iterator is still valid.

    CheckErrors();

    if (Done()) {

      ThrowError("Attempting to write invalid element.");

    }

    // Append the cur element.

    result_.insert(result_.end(),

                   data_+cur_byte_,

                   data_+cur_byte_+ sizeof(uint32_t) + cur_elem_length_);

  }

  /// Will ThrowError() if necessary.

  /// Checks for common/ubiquitous errors that can arise after most operations.

  /// This method should be called before any reading operation.

  /// If this function succeeds, then we are guaranteed to be in a valid state.

  /// Other member functions should check for errors and ThrowError() also

  ///  if an error occurs that is specific to it even while in a valid state.

  void CheckErrors() {

    // Check if any crazy thing has happened recently

    if ((cur_elem_ > length_) ||                              // Bad index

        (cur_byte_ > num_bytes_) ||                           // No more bytes

        (cur_byte_ + cur_elem_length_ > num_bytes_) ||        // Item too large

        (cur_byte_ == num_bytes_ && cur_elem_ != length_) ||  // Too many items

        (cur_elem_ == length_ && cur_byte_ != num_bytes_)) {  // Too many bytes

      ThrowError("Corrupt data.");

    }

  }

  /// Will throw an exception based on the passed-in message.

  /// This function is guaranteed to STOP THE CONTROL-FLOW.

  /// (i.e.: you do not have to call "return" after calling ThrowError)

  void ThrowError(const char* const msg = NULL) {

    // TODO: For now we ignore the msg parameter. This can be expanded later.

    throw RedisListException();

  }

 private:

  const char* const data_;      // A pointer to the data (the first byte)

  const uint32_t num_bytes_;    // The number of bytes in this list

  uint32_t cur_byte_;           // The current byte being read

  uint32_t cur_elem_;           // The current element being read

  uint32_t cur_elem_length_;    // The number of bytes in current element

  uint32_t length_;             // The number of elements in this list

  std::vector<char> result_;    // The output data

};

} // namespace rocksdb

#endif  // ROCKSDB_LITE