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.

//

/**

 * A (persistent) Redis API built using the rocksdb backend.

 * Implements Redis Lists as described on: http://redis.io/commands#list

 *

 * @throws All functions may throw a RedisListException on error/corruption.

 *

 * @notes Internally, the set of lists is stored in a rocksdb database,

 *        mapping keys to values. Each "value" is the list itself, storing

 *        some kind of internal representation of the data. All the

 *        representation details are handled by the RedisListIterator class.

 *        The present file should be oblivious to the representation details,

 *        handling only the client (Redis) API, and the calls to rocksdb.

 *

 * @TODO  Presently, all operations take at least O(NV) time where

 *        N is the number of elements in the list, and V is the average

 *        number of bytes per value in the list. So maybe, with merge operator

 *        we can improve this to an optimal O(V) amortized time, since we

 *        wouldn't have to read and re-write the entire list.

 *

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

 */

#ifndef ROCKSDB_LITE

#include "yb/rocksdb/utilities/redis/redis_lists.h"

#include <iostream>

#include <memory>

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

#include "yb/util/slice.h"

#include "yb/util/status_log.h"

namespace rocksdb {

/// Constructors

RedisLists::RedisLists(const std::string& db_path,

                       Options options, bool destructive)

    : put_option_(),

      get_option_() {

  // Store the name of the database

  db_name_ = db_path;

  // If destructive, destroy the DB before re-opening it.

  if (destructive) {

    CHECK_OK(DestroyDB(db_name_, Options()));

  }

  // Now open and deal with the db

  DB* db;

  Status s = DB::Open(options, db_name_, &db);

  if (!s.ok()) {

    std::cerr << "ERROR " << s.ToString() << std::endl;

    assert(false);

  }

  db_ = std::unique_ptr<DB>(db);

}

/// Accessors

// Number of elements in the list associated with key

//   : throws RedisListException

int RedisLists::Length(const std::string& key) {

  // Extract the string data representing the list.

  std::string data = Get(key);

  // Return the length

  RedisListIterator it(data);

  return it.Length();

}

// Get the element at the specified index in the (list: key)

// Returns <empty> ("") on out-of-bounds

//   : throws RedisListException

bool RedisLists::Index(const std::string& key, int32_t index,

                       std::string* result) {

  // Extract the string data representing the list.

  std::string data = Get(key);

  // Handle REDIS negative indices (from the end); fast iff Length() takes O(1)

  if (index < 0) {

    index = Length(key) - (-index);  // replace (-i) with (N-i).

  }

  // Iterate through the list until the desired index is found.

  int curIndex = 0;

  RedisListIterator it(data);

  while(curIndex < index && !it.Done()) {

    ++curIndex;

    it.Skip();

  }

  // If we actually found the index

  if (curIndex == index && !it.Done()) {

    Slice elem;

    it.GetCurrent(&elem);

    if (result != NULL) {

      *result = elem.ToString();

    }

    return true;

  } else {

    return false;

  }

}

// Return a truncated version of the list.

// First, negative values for first/last are interpreted as "end of list".

// So, if first == -1, then it is re-set to index: (Length(key) - 1)

// Then, return exactly those indices i such that first <= i <= last.

//   : throws RedisListException

std::vector<std::string> RedisLists::Range(const std::string& key,

                                           int32_t first, int32_t last) {

  // Extract the string data representing the list.

  std::string data = Get(key);

  // Handle negative bounds (-1 means last element, etc.)

  int listLen = Length(key);

  if (first < 0) {

    first = listLen - (-first);           // Replace (-x) with (N-x)

  }

  if (last < 0) {

    last = listLen - (-last);

  }

  // Verify bounds (and truncate the range so that it is valid)

  first = std::max(first, 0);

  last = std::min(last, listLen-1);

  int len = std::max(last-first+1, 0);

  // Initialize the resulting list

  std::vector<std::string> result(len);

  // Traverse the list and update the vector

  int curIdx = 0;

  Slice elem;

  for (RedisListIterator it(data); !it.Done() && curIdx <= last; it.Skip()) {

    if (first <= curIdx && curIdx <= last) {

      it.GetCurrent(&elem);

      result[curIdx - first].assign(elem.cdata(), elem.size());

    }

    ++curIdx;

  }

  // Return the result. Might be empty

  return result;

}

// Print the (list: key) out to stdout. For debugging mostly. Public for now.

void RedisLists::Print(const std::string& key) {

  // Extract the string data representing the list.

  std::string data = Get(key);

  // Iterate through the list and print the items

  Slice elem;

  for (RedisListIterator it(data); !it.Done(); it.Skip()) {

    it.GetCurrent(&elem);

    std::cout << "ITEM " << elem.ToString() << std::endl;

  }

  // Now print the byte data

  RedisListIterator it(data);

  std::cout << "==Printing data==" << std::endl;

  std::cout << data.size() << std::endl;

  std::cout << it.Size() << " " << it.Length() << std::endl;

  Slice result = it.WriteResult();

  std::cout << result.data() << std::endl;

  if (true) {

    std::cout << "size: " << result.size() << std::endl;

    const char* val = result.cdata();

    for(size_t i = 0; i < result.size(); ++i) {

      std::cout << static_cast<int>(val[i]) << " " << (val[i] >= 32 ? val[i] : ' ') << std::endl;

    }

    std::cout << std::endl;

  }

}

/// Insert/Update Functions

/// Note: The "real" insert function is private. See below.

// InsertBefore and InsertAfter are simply wrappers around the Insert function.

int RedisLists::InsertBefore(const std::string& key, const std::string& pivot,

                             const std::string& value) {

  return Insert(key, pivot, value, false);

}

int RedisLists::InsertAfter(const std::string& key, const std::string& pivot,

                            const std::string& value) {

  return Insert(key, pivot, value, true);

}

std::string RedisLists::Get(const std::string& key) {

  std::string data;

  auto get_status = db_->Get(get_option_, key, &data);

  if (!get_status.ok() && !get_status.IsNotFound()) {

    CHECK_OK(get_status);

  }

  return data;

}

// Prepend value onto beginning of (list: key)

//   : throws RedisListException

int RedisLists::PushLeft(const std::string& key, const std::string& value) {

  // Get the original list data

  std::string data = Get(key);

  // Construct the result

  RedisListIterator it(data);

  it.Reserve(it.Size() + it.SizeOf(value));

  it.InsertElement(value);

  // Push the data back to the db and return the length

  CHECK_OK(db_->Put(put_option_, key, it.WriteResult()));

  return it.Length();

}

// Append value onto end of (list: key)

// TODO: Make this O(1) time. Might require MergeOperator.

//   : throws RedisListException

int RedisLists::PushRight(const std::string& key, const std::string& value) {

  // Get the original list data

  std::string data = Get(key);

  // Create an iterator to the data and seek to the end.

  RedisListIterator it(data);

  it.Reserve(it.Size() + it.SizeOf(value));

  while (!it.Done()) {

    it.Push();    // Write each element as we go

  }

  // Insert the new element at the current position (the end)

  it.InsertElement(value);

  // Push it back to the db, and return length

  CHECK_OK(db_->Put(put_option_, key, it.WriteResult()));

  return it.Length();

}

// Set (list: key)[idx] = val. Return true on success, false on fail.

//   : throws RedisListException

bool RedisLists::Set(const std::string& key, int32_t index,

                     const std::string& value) {

  // Get the original list data

  std::string data = Get(key);

  // Handle negative index for REDIS (meaning -index from end of list)

  if (index < 0) {

    index = Length(key) - (-index);

  }

  // Iterate through the list until we find the element we want

  int curIndex = 0;

  RedisListIterator it(data);

  it.Reserve(it.Size() + it.SizeOf(value));  // Over-estimate is fine

  while(curIndex < index && !it.Done()) {

    it.Push();

    ++curIndex;

  }

  // If not found, return false (this occurs when index was invalid)

  if (it.Done() || curIndex != index) {

    return false;

  }

  // Write the new element value, and drop the previous element value

  it.InsertElement(value);

  it.Skip();

  // Write the data to the database

  // Check status, since it needs to return true/false guarantee

  Status s = db_->Put(put_option_, key, it.WriteResult());

  // Success

  return s.ok();

}

/// Delete / Remove / Pop functions

// Trim (list: key) so that it will only contain the indices from start..stop

//  Invalid indices will not generate an error, just empty,

//  or the portion of the list that fits in this interval

//   : throws RedisListException

bool RedisLists::Trim(const std::string& key, int32_t start, int32_t stop) {

  // Get the original list data

  std::string data = Get(key);

  // Handle negative indices in REDIS

  int listLen = Length(key);

  if (start < 0) {

    start = listLen - (-start);

  }

  if (stop < 0) {

    stop = listLen - (-stop);

  }

  // Truncate bounds to only fit in the list

  start = std::max(start, 0);

  stop = std::min(stop, listLen-1);

  // Construct an iterator for the list. Drop all undesired elements.

  int curIndex = 0;

  RedisListIterator it(data);

  it.Reserve(it.Size());          // Over-estimate

  while(!it.Done()) {

    // If not within the range, just skip the item (drop it).

    // Otherwise, continue as usual.

    if (start <= curIndex && curIndex <= stop) {

      it.Push();

    } else {

      it.Skip();

    }

    // Increment the current index

    ++curIndex;

  }

  // Write the (possibly empty) result to the database

  Status s = db_->Put(put_option_, key, it.WriteResult());

  // Return true as long as the write succeeded

  return s.ok();

}

// Return and remove the first element in the list (or "" if empty)

//   : throws RedisListException

bool RedisLists::PopLeft(const std::string& key, std::string* result) {

  // Get the original list data

  std::string data = Get(key);

  // Point to first element in the list (if it exists), and get its value/size

  RedisListIterator it(data);

  if (it.Length() > 0) {            // Proceed only if list is non-empty

    Slice elem;

    it.GetCurrent(&elem);           // Store the value of the first element

    it.Reserve(it.Size() - it.SizeOf(elem));

    it.Skip();                      // DROP the first item and move to next

    // Update the db

    CHECK_OK(db_->Put(put_option_, key, it.WriteResult()));

    // Return the value

    if (result != NULL) {

      *result = elem.ToString();

    }

    return true;

  } else {

    return false;

  }

}

// Remove and return the last element in the list (or "" if empty)

// TODO: Make this O(1). Might require MergeOperator.

//   : throws RedisListException

bool RedisLists::PopRight(const std::string& key, std::string* result) {

  // Extract the original list data

  std::string data = Get(key);

  // Construct an iterator to the data and move to last element

  RedisListIterator it(data);

  it.Reserve(it.Size());

  int len = it.Length();

  int curIndex = 0;

  while(curIndex < (len-1) && !it.Done()) {

    it.Push();

    ++curIndex;

  }

  // Extract and drop/skip the last element

  if (curIndex == len-1) {

    assert(!it.Done());         // Sanity check. Should not have ended here.

    // Extract and pop the element

    Slice elem;

    it.GetCurrent(&elem);       // Save value of element.

    it.Skip();                  // Skip the element

    // Write the result to the database

    CHECK_OK(db_->Put(put_option_, key, it.WriteResult()));

    // Return the value

    if (result != NULL) {

      *result = elem.ToString();

    }

    return true;

  } else {

    // Must have been an empty list

    assert(it.Done() && len == 0 && curIndex == 0);

    return false;

  }

}

// Remove the (first or last) "num" occurrences of value in (list: key)

//   : throws RedisListException

int RedisLists::Remove(const std::string& key, int32_t num,

                       const std::string& value) {

  // Negative num ==> RemoveLast; Positive num ==> Remove First

  if (num < 0) {

    return RemoveLast(key, -num, value);

  } else if (num > 0) {

    return RemoveFirst(key, num, value);

  } else {

    return RemoveFirst(key, Length(key), value);

  }

}

// Remove the first "num" occurrences of value in (list: key).

//   : throws RedisListException

int RedisLists::RemoveFirst(const std::string& key, int32_t num,

                            const std::string& value) {

  // Ensure that the number is positive

  assert(num >= 0);

  // Extract the original list data

  std::string data = Get(key);

  // Traverse the list, appending all but the desired occurrences of value

  int numSkipped = 0;         // Keep track of the number of times value is seen

  Slice elem;

  RedisListIterator it(data);

  it.Reserve(it.Size());

  while (!it.Done()) {

    it.GetCurrent(&elem);

    if (elem == value && numSkipped < num) {

      // Drop this item if desired

      it.Skip();

      ++numSkipped;

    } else {

      // Otherwise keep the item and proceed as normal

      it.Push();

    }

  }

  // Put the result back to the database

  CHECK_OK(db_->Put(put_option_, key, it.WriteResult()));

  // Return the number of elements removed

  return numSkipped;

}

// Remove the last "num" occurrences of value in (list: key).

// TODO: I traverse the list 2x. Make faster. Might require MergeOperator.

//   : throws RedisListException

int RedisLists::RemoveLast(const std::string& key, int32_t num,

                           const std::string& value) {

  // Ensure that the number is positive

  assert(num >= 0);

  // Extract the original list data

  std::string data = Get(key);

  // Temporary variable to hold the "current element" in the blocks below

  Slice elem;

  // Count the total number of occurrences of value

  int totalOccs = 0;

  for (RedisListIterator it(data); !it.Done(); it.Skip()) {

    it.GetCurrent(&elem);

    if (elem == value) {

      ++totalOccs;

    }

  }

  // Construct an iterator to the data. Reserve enough space for the result.

  RedisListIterator it(data);

  int bytesRemoved = std::min(num, totalOccs) * it.SizeOf(value);

  it.Reserve(it.Size() - bytesRemoved);

  // Traverse the list, appending all but the desired occurrences of value.

  // Note: "Drop the last k occurrences" is equivalent to

  //  "keep only the first n-k occurrences", where n is total occurrences.

  int numKept = 0;          // Keep track of the number of times value is kept

  while(!it.Done()) {

    it.GetCurrent(&elem);

    // If we are within the deletion range and equal to value, drop it.

    // Otherwise, append/keep/push it.

    if (elem == value) {

      if (numKept < totalOccs - num) {

        it.Push();

        ++numKept;

      } else {

        it.Skip();

      }

    } else {

      // Always append the others

      it.Push();

    }

  }

  // Put the result back to the database

  CHECK_OK(db_->Put(put_option_, key, it.WriteResult()));

  // Return the number of elements removed

  return totalOccs - numKept;

}

/// Private functions

// Insert element value into (list: key), right before/after

//  the first occurrence of pivot

//   : throws RedisListException

int RedisLists::Insert(const std::string& key, const std::string& pivot,

                       const std::string& value, bool insert_after) {

  // Get the original list data

  std::string data = Get(key);

  // Construct an iterator to the data and reserve enough space for result.

  RedisListIterator it(data);

  it.Reserve(it.Size() + it.SizeOf(value));

  // Iterate through the list until we find the element we want

  Slice elem;

  bool found = false;

  while(!it.Done() && !found) {

    it.GetCurrent(&elem);

    // When we find the element, insert the element and mark found

    if (elem == pivot) {                // Found it!

      found = true;

      if (insert_after == true) {       // Skip one more, if inserting after it

        it.Push();

      }

      it.InsertElement(value);

    } else {

      it.Push();

    }

  }

  // Put the data (string) into the database

  if (found) {

    CHECK_OK(db_->Put(put_option_, key, it.WriteResult()));

  }

  // Returns the new (possibly unchanged) length of the list

  return it.Length();

}

}  // namespace rocksdb

#endif  // ROCKSDB_LITE