[BlobAsync] Disk support for blob storage

storage/browser/blob/blob_slice.cc

+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "storage/browser/blob/blob_slice.h"
+
+#include "storage/browser/blob/blob_storage_context.h"
+#include "storage/browser/blob/blob_data_item.h"
+#include "storage/browser/blob/shareable_blob_data_item.h"
+
+namespace storage {
+
+BlobSlice::BlobSlice() {}
+
+BlobSlice::BlobSlice(const InternalBlobData& source,
+                     uint64_t blob_offset,
+                     uint64_t size,
+                     bool done_building)
+    : done_building_(done_building) {
+  const auto& items = source.items();
+  size_t mid;
+  uint64_t offset_from_mid;
+  size_t num_items = items.size();
+  BinarySearch(source, blob_offset, &mid, &offset_from_mid);
+
+  LOG(ERROR) << "doing a slice at " << blob_offset << " with size " << size;
+  first_item_index_ = mid;
+  copying_memory_size_ = 0;
+
+  bool first_item = true;
+  bool last_item_memory_sliced = false;
+  // Read starting from 'mid' and 'offset_from_mid'.
+  for (uint64_t memory_read = 0; mid < num_items && memory_read < size; mid++) {
+    const scoped_refptr<BlobDataItem>& item = items[mid]->item();
+    uint64_t length = item->length();
+    if (length == 0) {
+      continue;
+    }
+    DCHECK_NE(length, std::numeric_limits<uint64_t>::max());
+    DCHECK_NE(length, 0ull);
+
+    last_item_memory_sliced = false;
+    LOG(ERROR) << item->length();
+    bool can_share_item =
+        offset_from_mid == 0 && size - memory_read >= item->length();
+
+    if (can_share_item) {
+      LOG(ERROR) << "we can share";
+      items_.push_back(items[mid]);
+      memory_read += length;
+      first_item = false;
+      continue;
+    }
+
+    uint64_t read_size =
+        std::min(item->length() - offset_from_mid, size - memory_read);
+    memory_read += read_size;
+
+    scoped_refptr<BlobDataItem> data_item;
+    switch (item->type()) {
+      case DataElement::TYPE_BYTES_DESCRIPTION:
+      case DataElement::TYPE_BYTES: {
+        if (first_item) {
+          has_sliced_first_memory_item_ = true;
+          first_item_slice_offset_ = offset_from_mid;
+        }
+        LOG(ERROR) << "we're sliceing a bytes item!";
+        last_item_memory_sliced = true;
+        copying_memory_size_ += read_size;
+        std::unique_ptr<DataElement> element(new DataElement());
+        element->SetToBytesDescription(base::checked_cast<size_t>(read_size));
+        data_item = new BlobDataItem(std::move(element), nullptr);
+      } break;
+      case DataElement::TYPE_FILE: {
+        std::unique_ptr<DataElement> element(new DataElement());
+        element->SetToFilePathRange(item->path(),
+                                    item->offset() + offset_from_mid, read_size,
+                                    item->expected_modification_time());
+        data_item = new BlobDataItem(std::move(element), item->data_handle_);
+      } break;
+      case DataElement::TYPE_FILE_FILESYSTEM: {
+        std::unique_ptr<DataElement> element(new DataElement());
+        element->SetToFileSystemUrlRange(
+            item->filesystem_url(), item->offset() + offset_from_mid, read_size,
+            item->expected_modification_time());
+        data_item = new BlobDataItem(std::move(element), nullptr);
+      } break;
+      case DataElement::TYPE_DISK_CACHE_ENTRY: {
+        std::unique_ptr<DataElement> element(new DataElement());
+        element->SetToDiskCacheEntryRange(item->offset() + offset_from_mid,
+                                          read_size);
+        data_item = new BlobDataItem(std::move(element), item->data_handle_,
+                                     item->disk_cache_entry(),
+                                     item->disk_cache_stream_index(),
+                                     item->disk_cache_side_stream_index());
+      } break;
+      case DataElement::TYPE_BLOB:
+      case DataElement::TYPE_UNKNOWN:
+        CHECK(false) << "Illegal blob item type: " << item->type();
+    }
+    items_.push_back(new ShareableBlobDataItem(
+        BlobStorageContext::GetAndIncrementItemId(), std::move(data_item)));
+    first_item = false;
+    offset_from_mid = 0;
+  }
+  if (last_item_memory_sliced &&
+      !(has_sliced_first_memory_item_ && items_.size() == 1)) {
+    has_sliced_last_memory_item_ = true;
+    last_item_index_ = mid - 1;
+  }
+}
+
+BlobSlice::BlobSlice(BlobSlice&&) = default;
+
+void BlobSlice::BinarySearch(const InternalBlobData& source_blob,
+                             uint64_t blob_offset,
+                             size_t* item_index,
+                             uint64_t* offset_in_item) {
+  DCHECK(item_index != nullptr && offset_in_item != nullptr);
+  const auto& items = source_blob.items();
+  const auto& offsets = source_blob.offsets();
+  size_t mid = 0;

[Marijn Kruisselbrink, 2016/06/29 22:42:21]

Couldn't you write almost this entire method using one of the binary search
methods built in to c++? Something like:

*item_index = std::upper_bound(offsets.begin(), offsets.end(), blob_offset) -
offsets.begin();
*offset_in_item = *item_index == 0 ? blob_offset : blob_offset -
offsets[*item_index - 1];

[dmurph, 2016/07/06 23:44:29]

UR A WIZZARD 'AARY! 
https://youtu.be/kIq-xXsM1-4?t=17

+  uint64_t offset_from_mid = blob_offset;
+  size_t num_items = items.size();
+  if (!offsets.empty()) {
+    size_t low = 0;
+    size_t high = num_items - 1;
+    while (true) {
+      mid = (high + low) / 2;
+      // Note: we don't include the implicit '0' for the first item in offsets.
+      size_t item_offset = (mid == 0 ? 0 : offsets[mid - 1]);
+      offset_from_mid = blob_offset - item_offset;
+      uint64_t next_item_offset = (mid + 1 == num_items ? 0 : offsets[mid]);
+      if (item_offset == blob_offset) {
+        // We found an exact match!
+        break;
+      } else if (item_offset > blob_offset) {
+        high = mid - 1;
+      } else if (mid + 1 == num_items || next_item_offset > blob_offset) {
+        // We're at the last item, or the next offset is greater than the one we
+        // want, so the current item wins.
+        break;
+      } else {
+        low = mid + 1;
+      }
+    }
+  }
+  DCHECK_LT(offset_from_mid, items[mid]->item()->length());
+  *item_index = mid;
+  *offset_in_item = offset_from_mid;
+}
+
+BlobSlice::~BlobSlice() {}
+
+}  // namespace storage