Groonga - fulltext search engine.

[Groonga-commit] groonga/grnxx [master] Rename grnxx::alpha::BlobVector to grnxx::db::BlobVector.

susumu.yata null+****@clear*****
Thu Dec 13 18:21:10 JST 2012

• Previous message: [Groonga-commit] groonga/groonga.github.com [master] doc ja: fix description more precisely about range search by using index
• Next message: [Groonga-commit] groonga/groonga-query-log [master] SizedStatistics: use start_time(Time)#to_f for comparing start_time
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

susumu.yata	2012-12-13 18:21:10 +0900 (Thu, 13 Dec 2012)

  New Revision: f8c2bf19f2732587b3698760f518737862e6563d
  https://github.com/groonga/grnxx/commit/f8c2bf19f2732587b3698760f518737862e6563d

  Log:
    Rename grnxx::alpha::BlobVector to grnxx::db::BlobVector.

  Removed files:
    lib/alpha/blob_vector.cpp
    lib/alpha/blob_vector.hpp
    test/test_alpha_blob_vector.cpp
  Modified files:
    lib/alpha/Makefile.am
    lib/db/blob_vector.cpp
    lib/db/blob_vector.hpp
    test/Makefile.am
    test/test_db_blob_vector.cpp

  Modified: lib/alpha/Makefile.am (+0 -2)
===================================================================
--- lib/alpha/Makefile.am    2012-12-12 14:29:12 +0900 (fefe083)
+++ lib/alpha/Makefile.am    2012-12-13 18:21:10 +0900 (8044c8d)
@@ -1,10 +1,8 @@
 noinst_LTLIBRARIES = libgrnxx_alpha.la
 
 libgrnxx_alpha_la_SOURCES =		\
-	blob_vector.cpp			\
 	sample.cpp
 
 libgrnxx_alpha_includedir = ${includedir}/grnxx/alpha
 libgrnxx_alpha_include_HEADERS =	\
-	blob_vector.hpp			\
 	sample.hpp

  Deleted: lib/alpha/blob_vector.cpp (+0 -469) 100644
===================================================================
--- lib/alpha/blob_vector.cpp    2012-12-12 14:29:12 +0900 (2cd56ce)
+++ /dev/null
@@ -1,469 +0,0 @@
-/*
-  Copyright (C) 2012  Brazil, Inc.
-
-  This library is free software; you can redistribute it and/or
-  modify it under the terms of the GNU Lesser General Public
-  License as published by the Free Software Foundation; either
-  version 2.1 of the License, or (at your option) any later version.
-
-  This library is distributed in the hope that it will be useful,
-  but WITHOUT ANY WARRANTY; without even the implied warranty of
-  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-  Lesser General Public License for more details.
-
-  You should have received a copy of the GNU Lesser General Public
-  License along with this library; if not, write to the Free Software
-  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
-*/
-#include "blob_vector.hpp"
-
-#include "../exception.hpp"
-#include "../lock.hpp"
-#include "../logger.hpp"
-
-namespace grnxx {
-namespace alpha {
-
-BlobVectorCreate BLOB_VECTOR_CREATE;
-BlobVectorOpen BLOB_VECTOR_OPEN;
-
-BlobVectorHeader::BlobVectorHeader(uint32_t table_block_id)
-  : table_block_id_(table_block_id),
-    value_store_block_id_(io::BLOCK_INVALID_ID),
-    index_store_block_id_(io::BLOCK_INVALID_ID),
-    next_page_id_(0),
-    next_value_offset_(0),
-    latest_frozen_page_id_(BLOB_VECTOR_INVALID_PAGE_ID),
-    latest_large_value_block_id_(io::BLOCK_INVALID_ID),
-    inter_process_mutex_(MUTEX_UNLOCKED) {}
-
-StringBuilder &BlobVectorHeader::write_to(StringBuilder &builder) const {
-  if (!builder) {
-    return builder;
-  }
-
-  builder << "{ table_block_id = " << table_block_id_
-          << ", value_store_block_id = " << value_store_block_id_
-          << ", index_store_block_id = " << index_store_block_id_
-          << ", next_page_id = " << next_page_id_
-          << ", next_value_offset = " << next_value_offset_
-          << ", latest_large_value_block_id = " << latest_large_value_block_id_
-          << ", inter_process_mutex = " << inter_process_mutex_;
-  return builder << " }";
-}
-
-std::unique_ptr<BlobVectorImpl> BlobVectorImpl::create(io::Pool pool) {
-  std::unique_ptr<BlobVectorImpl> vector(new (std::nothrow) BlobVectorImpl);
-  if (!vector) {
-    GRNXX_ERROR() << "new grnxx::io::VectorImpl failed";
-    GRNXX_THROW();
-  }
-  vector->create_vector(pool);
-  return vector;
-}
-
-std::unique_ptr<BlobVectorImpl> BlobVectorImpl::open(io::Pool pool,
-                                                     uint32_t block_id) {
-  std::unique_ptr<BlobVectorImpl> vector(new (std::nothrow) BlobVectorImpl);
-  if (!vector) {
-    GRNXX_ERROR() << "new grnxx::io::VectorImpl failed";
-    GRNXX_THROW();
-  }
-  vector->open_vector(pool, block_id);
-  return vector;
-}
-
-void BlobVectorImpl::set_value(uint64_t id, const Blob &value) {
-  const BlobVectorCell new_cell = create_value(value);
-  BlobVectorCell old_cell;
-  try {
-    do {
-      old_cell = table_[id];
-    } while (!atomic_compare_and_swap(old_cell, new_cell, &table_[id]));
-  } catch (...) {
-    // The new value is freed on failure.
-    free_value(new_cell);
-    throw;
-  }
-  // The old value is freed on success.
-  free_value(old_cell);
-}
-
-void BlobVectorImpl::append(uint64_t id, const Blob &value) {
-  if (!value || (value.length() == 0)) {
-    return;
-  }
-
-  for ( ; ; ) {
-    const BlobVectorCell old_cell = table_[id];
-    const Blob old_value = get_value(old_cell);
-    const BlobVectorCell new_cell = join_values(old_value, value);
-    if (atomic_compare_and_swap(old_cell, new_cell, &table_[id])) {
-      // The old value is freed on success.
-      free_value(old_cell);
-      break;
-    } else {
-      // The new value is freed on failure.
-      free_value(new_cell);
-    }
-  }
-}
-
-void BlobVectorImpl::prepend(uint64_t id, const Blob &value) {
-  if (!value || (value.length() == 0)) {
-    return;
-  }
-
-  for ( ; ; ) {
-    const BlobVectorCell old_cell = table_[id];
-    const Blob old_value = get_value(old_cell);
-    const BlobVectorCell new_cell = join_values(value, old_value);
-    if (atomic_compare_and_swap(old_cell, new_cell, &table_[id])) {
-      // The old value is freed on success.
-      free_value(old_cell);
-      break;
-    } else {
-      // The new value is freed on failure.
-      free_value(new_cell);
-    }
-  }
-}
-
-StringBuilder &BlobVectorImpl::write_to(StringBuilder &builder) const {
-  if (!builder) {
-    return builder;
-  }
-
-  builder << "{ pool = " << pool_.path()
-          << ", block_info = " << *block_info_
-          << ", header = " << *header_
-          << ", inter_thread_mutex = " << inter_thread_mutex_;
-  return builder << " }";
-}
-
-void BlobVectorImpl::unlink(io::Pool pool, uint32_t block_id) {
-  std::unique_ptr<BlobVectorImpl> vector =
-      BlobVectorImpl::open(pool, block_id);
-
-  if (vector->header_->latest_large_value_block_id() != io::BLOCK_INVALID_ID) {
-    uint32_t block_id = vector->header_->latest_large_value_block_id();
-    do {
-      auto value_header = static_cast<const BlobVectorValueHeader *>(
-          pool.get_block_address(block_id));
-      const uint32_t prev_block_id = value_header->prev_value_block_id();
-      pool.free_block(block_id);
-      block_id = prev_block_id;
-    } while (block_id != vector->header_->latest_large_value_block_id());
-  }
-  BlobVectorTable::unlink(pool, vector->header_->table_block_id());
-  pool.free_block(vector->block_info_->id());
-}
-
-BlobVectorImpl::BlobVectorImpl()
-  : pool_(),
-    block_info_(nullptr),
-    header_(nullptr),
-    recycler_(nullptr),
-    table_(),
-    value_store_(),
-    index_store_(),
-    inter_thread_mutex_(MUTEX_UNLOCKED) {}
-
-void BlobVectorImpl::create_vector(io::Pool pool) {
-  pool_ = pool;
-  block_info_ = pool.create_block(sizeof(BlobVectorHeader));
-
-  try {
-    table_.create(pool_, BlobVectorCell::null_value());
-  } catch (...) {
-    pool_.free_block(*block_info_);
-    throw;
-  }
-
-  void * const block_address = pool_.get_block_address(*block_info_);
-  header_ = static_cast<BlobVectorHeader *>(block_address);
-  *header_ = BlobVectorHeader(table_.block_id());
-
-  recycler_ = pool.mutable_recycler();
-}
-
-void BlobVectorImpl::open_vector(io::Pool pool, uint32_t block_id) {
-  pool_ = pool;
-  block_info_ = pool.get_block_info(block_id);
-  if (block_info_->size() < sizeof(BlobVectorHeader)) {
-    GRNXX_ERROR() << "invalid argument: block_info = " << *block_info_
-                  << ", header_size = " << sizeof(BlobVectorHeader);
-    GRNXX_THROW();
-  }
-
-  void * const block_address = pool_.get_block_address(*block_info_);
-  header_ = static_cast<BlobVectorHeader *>(block_address);
-
-  // TODO: Check the format!
-
-  recycler_ = pool.mutable_recycler();
-
-  // Open the core table.
-  table_.open(pool, header_->table_block_id());
-}
-
-Blob BlobVectorImpl::get_value(BlobVectorCell cell) {
-  switch (cell.type()) {
-    case BLOB_VECTOR_NULL: {
-      return Blob(nullptr);
-    }
-    case BLOB_VECTOR_SMALL: {
-      return Blob(cell);
-    }
-    case BLOB_VECTOR_MEDIUM: {
-      if (!value_store_) {
-        Lock lock(mutable_inter_thread_mutex());
-        if (!value_store_) {
-          value_store_.open(pool_, header_->value_store_block_id());
-        }
-      }
-      return Blob(&value_store_[cell.offset()], cell.medium_length());
-    }
-    case BLOB_VECTOR_LARGE: {
-      const auto value_header = static_cast<const BlobVectorValueHeader *>(
-          pool_.get_block_address(cell.block_id()));
-      return Blob(value_header + 1, value_header->length());
-    }
-    default: {
-      GRNXX_ERROR() << "invalid value type";
-      GRNXX_THROW();
-    }
-  }
-}
-
-BlobVectorCell BlobVectorImpl::create_value(const Blob &value) {
-  if (!value) {
-    return BlobVectorCell::null_value();
-  }
-
-  BlobVectorCell cell;
-  void *address;
-  if (value.length() < BLOB_VECTOR_MEDIUM_VALUE_MIN_LENGTH) {
-    address = create_small_value(value.length(), &cell);
-  } else if (value.length() < BLOB_VECTOR_LARGE_VALUE_MIN_LENGTH) {
-    address = create_medium_value(value.length(), &cell);
-  } else {
-    address = create_large_value(value.length(), &cell);
-  }
-  std::memcpy(address, value.address(), value.length());
-  return cell;
-}
-
-BlobVectorCell BlobVectorImpl::join_values(const Blob &lhs, const Blob &rhs) {
-  const uint64_t length = lhs.length() + rhs.length();
-  BlobVectorCell cell;
-  void *address;
-  if (length < BLOB_VECTOR_MEDIUM_VALUE_MIN_LENGTH) {
-    address = create_small_value(length, &cell);
-  } else if (length < BLOB_VECTOR_LARGE_VALUE_MIN_LENGTH) {
-    address = create_medium_value(length, &cell);
-  } else {
-    address = create_large_value(length, &cell);
-  }
-  std::memcpy(address, lhs.address(), lhs.length());
-  std::memcpy(static_cast<char *>(address) + lhs.length(),
-              rhs.address(), rhs.length());
-  return cell;
-}
-
-void *BlobVectorImpl::create_small_value(uint64_t length,
-                                         BlobVectorCell *cell) {
-  *cell = BlobVectorCell::small_value(length);
-  return cell->value();
-}
-
-void *BlobVectorImpl::create_medium_value(uint64_t length,
-                                          BlobVectorCell *cell) {
-  Lock lock(mutable_inter_thread_mutex());
-
-  if (!value_store_) {
-    if (header_->value_store_block_id() == io::BLOCK_INVALID_ID) {
-      Lock lock(mutable_inter_process_mutex());
-      if (header_->value_store_block_id() == io::BLOCK_INVALID_ID) {
-        value_store_.create(pool_);
-        header_->set_value_store_block_id(value_store_.block_id());
-      }
-    }
-    if (!value_store_) {
-      value_store_.open(pool_, header_->value_store_block_id());
-    }
-  }
-
-  if (!index_store_) {
-    if (header_->index_store_block_id() == io::BLOCK_INVALID_ID) {
-      Lock lock(mutable_inter_process_mutex());
-      if (header_->index_store_block_id() == io::BLOCK_INVALID_ID) {
-        index_store_.create(pool_, BlobVectorPageInfo());
-        header_->set_index_store_block_id(index_store_.block_id());
-      }
-    }
-    if (!index_store_) {
-      index_store_.open(pool_, header_->index_store_block_id());
-    }
-  }
-
-  // Unfreeze the oldest frozen page for reuse.
-  unfreeze_oldest_frozen_page();
-
-  uint64_t offset = header_->next_value_offset();
-  const uint64_t offset_in_page =
-      ((offset - 1) & (BLOB_VECTOR_VALUE_STORE_PAGE_SIZE - 1)) + 1;
-  const uint64_t size_left_in_page =
-      BLOB_VECTOR_VALUE_STORE_PAGE_SIZE - offset_in_page;
-
-  // Reserve a new page if there is not enough space in the current page.
-  if (length > size_left_in_page) {
-    if (offset != 0) {
-      // Freeze the current page if it is empty.
-      const uint32_t page_id = static_cast<uint32_t>(
-          (offset - 1) >> BLOB_VECTOR_VALUE_STORE_PAGE_SIZE_BITS);
-      if (index_store_[page_id].num_values() == 0) {
-        freeze_page(page_id);
-      }
-    }
-
-    const uint32_t page_id = header_->next_page_id();
-    offset = static_cast<uint64_t>(
-        page_id << BLOB_VECTOR_VALUE_STORE_PAGE_SIZE_BITS);
-    if (index_store_[page_id].next_page_id() != BLOB_VECTOR_INVALID_PAGE_ID) {
-      header_->set_next_page_id(index_store_[page_id].next_page_id());
-    } else {
-      header_->set_next_page_id(page_id + 1);
-    }
-    index_store_[page_id].set_num_values(0);
-  }
-  header_->set_next_value_offset(offset + length);
-
-  const uint32_t page_id = static_cast<uint32_t>(
-      offset >> BLOB_VECTOR_VALUE_STORE_PAGE_SIZE_BITS);
-  index_store_[page_id].set_num_values(index_store_[page_id].num_values() + 1);
-
-  *cell = BlobVectorCell::medium_value(offset, length);
-  return &value_store_[offset];
-}
-
-void *BlobVectorImpl::create_large_value(uint64_t length,
-                                         BlobVectorCell *cell) {
-  const io::BlockInfo *block_info =
-      pool_.create_block(sizeof(BlobVectorValueHeader) + length);
-  auto value_header = static_cast<BlobVectorValueHeader *>(
-      pool_.get_block_address(*block_info));
-  value_header->set_length(length);
-  register_large_value(block_info->id(), value_header);
-  *cell = BlobVectorCell::large_value(block_info->id());
-  return value_header + 1;
-}
-
-void BlobVectorImpl::free_value(BlobVectorCell cell) {
-  switch (cell.type()) {
-    case BLOB_VECTOR_NULL:
-    case BLOB_VECTOR_SMALL: {
-      break;
-    }
-    case BLOB_VECTOR_MEDIUM: {
-      Lock lock(mutable_inter_thread_mutex());
-
-      const uint32_t page_id = static_cast<uint32_t>(
-          cell.offset() >> BLOB_VECTOR_VALUE_STORE_PAGE_SIZE_BITS);
-      index_store_[page_id].set_num_values(
-          index_store_[page_id].num_values() - 1);
-      if (index_store_[page_id].num_values() == 0) {
-        const uint32_t current_page_id =
-            static_cast<uint32_t>(header_->next_value_offset()
-                                  >> BLOB_VECTOR_VALUE_STORE_PAGE_SIZE_BITS);
-        if (page_id != current_page_id) {
-          freeze_page(page_id);
-        }
-      }
-      break;
-    }
-    case BLOB_VECTOR_LARGE: {
-      const io::BlockInfo * const block_info =
-          pool_.get_block_info(cell.block_id());
-      unregister_large_value(block_info->id(),
-          static_cast<BlobVectorValueHeader *>(
-              pool_.get_block_address(*block_info)));
-      pool_.free_block(*block_info);
-      break;
-    }
-  }
-}
-
-void BlobVectorImpl::register_large_value(uint32_t block_id,
-    BlobVectorValueHeader *value_header) {
-  Lock lock(mutable_inter_process_mutex());
-  if (header_->latest_large_value_block_id() == io::BLOCK_INVALID_ID) {
-    value_header->set_next_value_block_id(block_id);
-    value_header->set_prev_value_block_id(block_id);
-  } else {
-    const uint32_t prev_id = header_->latest_large_value_block_id();
-    auto prev_header = static_cast<BlobVectorValueHeader *>(
-        pool_.get_block_address(prev_id));
-    const uint32_t next_id = prev_header->next_value_block_id();
-    auto next_header = static_cast<BlobVectorValueHeader *>(
-        pool_.get_block_address(next_id));
-    value_header->set_next_value_block_id(next_id);
-    value_header->set_prev_value_block_id(prev_id);
-    prev_header->set_next_value_block_id(block_id);
-    next_header->set_prev_value_block_id(block_id);
-  }
-  header_->set_latest_large_value_block_id(block_id);
-}
-
-void BlobVectorImpl::unregister_large_value(uint32_t block_id,
-    BlobVectorValueHeader *value_header) {
-  Lock lock(mutable_inter_process_mutex());
-  const uint32_t next_id = value_header->next_value_block_id();
-  const uint32_t prev_id = value_header->prev_value_block_id();
-  auto next_header = static_cast<BlobVectorValueHeader *>(
-      pool_.get_block_address(next_id));
-  auto prev_header = static_cast<BlobVectorValueHeader *>(
-      pool_.get_block_address(prev_id));
-  next_header->set_prev_value_block_id(prev_id);
-  prev_header->set_next_value_block_id(next_id);
-  if (block_id == header_->latest_large_value_block_id()) {
-    header_->set_latest_large_value_block_id(prev_id);
-  }
-}
-
-void BlobVectorImpl::freeze_page(uint32_t page_id) {
-  BlobVectorPageInfo &page_info = index_store_[page_id];
-  if (header_->latest_frozen_page_id() != BLOB_VECTOR_INVALID_PAGE_ID) {
-    BlobVectorPageInfo &latest_frozen_page_info =
-        index_store_[header_->latest_frozen_page_id()];
-    page_info.set_next_page_id(latest_frozen_page_info.next_page_id());
-    latest_frozen_page_info.set_next_page_id(page_id);
-  } else {
-    page_info.set_next_page_id(page_id);
-  }
-  page_info.set_stamp(recycler_->stamp());
-  header_->set_latest_frozen_page_id(page_id);
-}
-
-void BlobVectorImpl::unfreeze_oldest_frozen_page() {
-  if (header_->latest_frozen_page_id() != BLOB_VECTOR_INVALID_PAGE_ID) {
-    BlobVectorPageInfo &latest_frozen_page_info =
-        index_store_[header_->latest_frozen_page_id()];
-    const uint32_t oldest_frozen_page_id =
-        latest_frozen_page_info.next_page_id();
-    BlobVectorPageInfo &oldest_frozen_page_info =
-        index_store_[oldest_frozen_page_id];
-    if (recycler_->check(oldest_frozen_page_info.stamp())) {
-      latest_frozen_page_info.set_next_page_id(
-          oldest_frozen_page_info.next_page_id());
-      oldest_frozen_page_info.set_next_page_id(header_->next_page_id());
-      header_->set_next_page_id(oldest_frozen_page_id);
-      if (oldest_frozen_page_id == header_->latest_frozen_page_id()) {
-        header_->set_latest_frozen_page_id(BLOB_VECTOR_INVALID_PAGE_ID);
-      }
-    }
-  }
-}
-
-}  // namespace alpha
-}  // namespace grnxx

  Deleted: lib/alpha/blob_vector.hpp (+0 -551) 100644
===================================================================
--- lib/alpha/blob_vector.hpp    2012-12-12 14:29:12 +0900 (c4fe8f2)
+++ /dev/null
@@ -1,551 +0,0 @@
-/*
-  Copyright (C) 2012  Brazil, Inc.
-
-  This library is free software; you can redistribute it and/or
-  modify it under the terms of the GNU Lesser General Public
-  License as published by the Free Software Foundation; either
-  version 2.1 of the License, or (at your option) any later version.
-
-  This library is distributed in the hope that it will be useful,
-  but WITHOUT ANY WARRANTY; without even the implied warranty of
-  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-  Lesser General Public License for more details.
-
-  You should have received a copy of the GNU Lesser General Public
-  License along with this library; if not, write to the Free Software
-  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
-*/
-#ifndef GRNXX_ALPHA_BLOB_VECTOR_HPP
-#define GRNXX_ALPHA_BLOB_VECTOR_HPP
-
-#include "../db/vector.hpp"
-
-namespace grnxx {
-namespace alpha {
-
-using namespace grnxx::db;
-
-constexpr uint64_t BLOB_VECTOR_MAX_ID = uint64_t(1) << 40;
-
-constexpr uint32_t BLOB_VECTOR_INVALID_PAGE_ID = 0xFFFFFFFFU;
-
-constexpr uint64_t BLOB_VECTOR_SMALL_VALUE_MAX_LENGTH  = 7;
-
-constexpr uint64_t BLOB_VECTOR_MEDIUM_VALUE_MIN_LENGTH =
-    BLOB_VECTOR_SMALL_VALUE_MAX_LENGTH + 1;
-constexpr uint64_t BLOB_VECTOR_MEDIUM_VALUE_MAX_LENGTH = 65535;
-
-constexpr uint64_t BLOB_VECTOR_LARGE_VALUE_MIN_LENGTH  =
-    BLOB_VECTOR_MEDIUM_VALUE_MAX_LENGTH + 1;
-
-constexpr uint8_t  BLOB_VECTOR_UNIT_SIZE_BITS  = 3;
-constexpr uint64_t BLOB_VECTOR_UNIT_SIZE       =
-    uint64_t(1) << BLOB_VECTOR_UNIT_SIZE_BITS;
-
-constexpr uint8_t  BLOB_VECTOR_VALUE_STORE_PAGE_SIZE_BITS            = 19;
-constexpr uint8_t  BLOB_VECTOR_VALUE_STORE_TABLE_SIZE_BITS           = 12;
-constexpr uint8_t  BLOB_VECTOR_VALUE_STORE_SECONDARY_TABLE_SIZE_BITS = 16;
-
-constexpr uint64_t BLOB_VECTOR_VALUE_STORE_PAGE_SIZE            =
-    uint64_t(1) << BLOB_VECTOR_VALUE_STORE_PAGE_SIZE_BITS;
-constexpr uint64_t BLOB_VECTOR_VALUE_STORE_TABLE_SIZE           =
-    uint64_t(1) << BLOB_VECTOR_VALUE_STORE_TABLE_SIZE_BITS;
-constexpr uint64_t BLOB_VECTOR_VALUE_STORE_SECONDARY_TABLE_SIZE =
-    uint64_t(1) << BLOB_VECTOR_VALUE_STORE_SECONDARY_TABLE_SIZE_BITS;
-
-extern class BlobVectorCreate {} BLOB_VECTOR_CREATE;
-extern class BlobVectorOpen {} BLOB_VECTOR_OPEN;
-
-class BlobVectorHeader {
- public:
-  explicit BlobVectorHeader(uint32_t table_block_id);
-
-  uint32_t table_block_id() const {
-    return table_block_id_;
-  }
-  uint32_t value_store_block_id() const {
-    return value_store_block_id_;
-  }
-  uint32_t index_store_block_id() const {
-    return index_store_block_id_;
-  }
-  uint32_t next_page_id() const {
-    return next_page_id_;
-  }
-  uint64_t next_value_offset() const {
-    return next_value_offset_;
-  }
-  uint32_t latest_frozen_page_id() const {
-    return latest_frozen_page_id_;
-  }
-  uint32_t latest_large_value_block_id() const {
-    return latest_large_value_block_id_;
-  }
-
-  void set_value_store_block_id(uint32_t value) {
-    value_store_block_id_ = value;
-  }
-  void set_index_store_block_id(uint32_t value) {
-    index_store_block_id_ = value;
-  }
-  void set_next_page_id(uint32_t value) {
-    next_page_id_ = value;
-  }
-  void set_next_value_offset(uint64_t value) {
-    next_value_offset_ = value;
-  }
-  void set_latest_frozen_page_id(uint32_t value) {
-    latest_frozen_page_id_ = value;
-  }
-  void set_latest_large_value_block_id(uint32_t value) {
-    latest_large_value_block_id_ = value;
-  }
-
-  Mutex *mutable_inter_process_mutex() {
-    return &inter_process_mutex_;
-  }
-
-  StringBuilder &write_to(StringBuilder &builder) const;
-
- private:
-  uint32_t table_block_id_;
-  uint32_t value_store_block_id_;
-  uint32_t index_store_block_id_;
-  uint32_t next_page_id_;
-  uint64_t next_value_offset_;
-  uint32_t latest_frozen_page_id_;
-  uint32_t latest_large_value_block_id_;
-  Mutex inter_process_mutex_;
-};
-
-inline StringBuilder &operator<<(StringBuilder &builder,
-                                 const BlobVectorHeader &header) {
-  return header.write_to(builder);
-}
-
-enum BlobVectorValueType : uint8_t {
-  BLOB_VECTOR_NULL   = 0x00,
-  BLOB_VECTOR_SMALL  = 0x10,
-  BLOB_VECTOR_MEDIUM = 0x20,
-  BLOB_VECTOR_LARGE  = 0x30
-};
-
-constexpr uint8_t BLOB_VECTOR_TYPE_MASK = 0x30;
-
-class BlobVectorPageInfo {
- public:
-  BlobVectorPageInfo()
-    : next_page_id_(BLOB_VECTOR_INVALID_PAGE_ID), stamp_(0), reserved_(0) {}
-
-  uint32_t next_page_id() const {
-    return next_page_id_;
-  }
-  uint32_t num_values() const {
-    return num_values_;
-  }
-  uint16_t stamp() const {
-    return reserved_;
-  }
-
-  void set_next_page_id(uint32_t value) {
-    next_page_id_ = value;
-  }
-  void set_num_values(uint32_t value) {
-    num_values_ = value;
-  }
-  void set_stamp(uint16_t value) {
-    stamp_ = value;
-  }
-
- private:
-  union {
-    uint32_t next_page_id_;
-    uint32_t num_values_;
-  };
-  uint16_t stamp_;
-  uint16_t reserved_;
-};
-
-class BlobVectorValueHeader {
- public:
-  uint64_t length() const {
-    return length_;
-  }
-  uint32_t next_value_block_id() const {
-    return next_value_block_id_;
-  }
-  uint32_t prev_value_block_id() const {
-    return prev_value_block_id_;
-  }
-
-  void set_length(uint64_t value) {
-    length_ = value;
-  }
-  void set_next_value_block_id(uint32_t value) {
-    next_value_block_id_ = value;
-  }
-  void set_prev_value_block_id(uint32_t value) {
-    prev_value_block_id_ = value;
-  }
-
- private:
-  uint64_t length_;
-  uint32_t next_value_block_id_;
-  uint32_t prev_value_block_id_;
-};
-
-const uint8_t BLOB_VECTOR_CELL_FLAGS_MASK = 0xF0;
-
-class BlobVectorCell {
- public:
-  BlobVectorCell() = default;
-  explicit BlobVectorCell(std::nullptr_t) : qword_(0) {}
-
-  static BlobVectorCell null_value() {
-    return BlobVectorCell(nullptr);
-  }
-  static BlobVectorCell small_value(uint64_t length) {
-    BlobVectorCell cell(nullptr);
-    cell.bytes_[0] = BLOB_VECTOR_SMALL | static_cast<uint8_t>(length);
-    return cell;
-  }
-  static BlobVectorCell medium_value(uint64_t offset, uint64_t length) {
-    BlobVectorCell cell;
-    cell.bytes_[0] = BLOB_VECTOR_MEDIUM | static_cast<uint8_t>(offset >> 40);
-    cell.bytes_[1] = static_cast<uint8_t>(offset >> 32);
-    cell.words_[1] = static_cast<uint16_t>(length);
-    cell.dwords_[1] = static_cast<uint32_t>(offset);
-    return cell;
-  }
-  static BlobVectorCell large_value(uint32_t block_id) {
-    BlobVectorCell cell(nullptr);
-    cell.bytes_[0] = BLOB_VECTOR_LARGE;
-    cell.dwords_[1] = block_id;
-    return cell;
-  }
-
-  BlobVectorValueType type() const {
-    Flags flags;
-    flags.byte = flags_.byte & BLOB_VECTOR_TYPE_MASK;
-    return flags.type;
-  }
-
-  // Accessors to small values.
-  uint64_t small_length() const {
-    return bytes_[0] & ~BLOB_VECTOR_CELL_FLAGS_MASK;
-  }
-  const void *value() const {
-    return &bytes_[1];
-  }
-  void *value() {
-    return &bytes_[1];
-  }
-
-  // Accessors to medium values.
-  uint64_t medium_length() const {
-    return words_[1];
-  }
-  uint64_t offset() const {
-    return (static_cast<uint64_t>(bytes_[0] &
-                                  ~BLOB_VECTOR_CELL_FLAGS_MASK) << 40) |
-           (static_cast<uint64_t>(bytes_[1]) << 32) | dwords_[1];
-  }
-
-  // Accessors to large values.
-  uint32_t block_id() const {
-    return dwords_[1];
-  }
-
- private:
-  union Flags {
-    uint8_t byte;
-    BlobVectorValueType type;
-  };
-
-  union {
-    Flags flags_;
-    uint8_t bytes_[8];
-    uint16_t words_[4];
-    uint32_t dwords_[2];
-    uint64_t qword_;
-  };
-};
-
-static_assert(sizeof(BlobVectorCell) == sizeof(uint64_t),
-              "sizeof(BlobVectorCell) != sizeof(uint64_t)");
-
-class Blob {
- public:
-  Blob() : address_(nullptr), length_(0), cell_() {}
-  explicit Blob(std::nullptr_t) : address_(nullptr), length_(0), cell_() {}
-  Blob(const void *address, uint64_t length)
-    : address_(address), length_(length), cell_() {}
-  explicit Blob(BlobVectorCell small_value_cell)
-    : address_(), length_(), cell_(small_value_cell) {
-    address_ = cell_.value();
-    length_ = cell_.small_length();
-  }
-
-  // Note: address_ refers to the own value if it is small.
-  Blob(const Blob &rhs) : address_(), length_(rhs.length_), cell_(rhs.cell_) {
-    if (rhs.address() == rhs.cell_.value()) {
-      address_ = cell_.value();
-    } else {
-      address_ = rhs.address_;
-    }
-  }
-  Blob &operator=(const Blob &rhs) {
-    length_ = rhs.length_;
-    cell_ = rhs.cell_;
-    if (rhs.address() == rhs.cell_.value()) {
-      address_ = cell_.value();
-    } else {
-      address_ = rhs.address_;
-    }
-    return *this;
-  }
-
-  Blob &operator=(std::nullptr_t) {
-    return *this = Blob(nullptr);
-  }
-
-  explicit operator bool() const {
-    return static_cast<bool>(address_);
-  }
-
-  const void *address() const {
-    return address_;
-  }
-  uint64_t length() const {
-    return length_;
-  }
-
-  void set_address(const void *value) {
-    address_ = value;
-  }
-  void set_length(uint64_t value) {
-    length_ = value;
-  }
-
- private:
-  const void *address_;
-  uint64_t length_;
-  BlobVectorCell cell_;
-};
-
-class BlobVector;
-
-class BlobRef {
- public:
-  BlobRef(BlobVector *vector, uint64_t id) : vector_(*vector), id_(id) {}
-
-  operator Blob() const {
-    return get();
-  }
-
-  BlobRef &operator=(std::nullptr_t) {
-    set(nullptr);
-    return *this;
-  }
-  BlobRef &operator=(const Blob &value) {
-    set(value);
-    return *this;
-  }
-
-  Blob get() const;
-  void set(std::nullptr_t) {
-    set(Blob(nullptr));
-  }
-  void set(const Blob &value);
-  void set(const void *ptr, uint64_t length) {
-    set(Blob(ptr, length));
-  }
-
-  void append(const Blob &value);
-  void append(const void *ptr, uint64_t length) {
-    append(Blob(ptr, length));
-  }
-  void prepend(const Blob &value);
-  void prepend(const void *ptr, uint64_t length) {
-    prepend(Blob(ptr, length));
-  }
-
- private:
-  BlobVector &vector_;
-  uint64_t id_;
-};
-
-typedef Vector<BlobVectorCell> BlobVectorTable;
-
-typedef Vector<char, BLOB_VECTOR_VALUE_STORE_PAGE_SIZE,
-                     BLOB_VECTOR_VALUE_STORE_TABLE_SIZE,
-                     BLOB_VECTOR_VALUE_STORE_SECONDARY_TABLE_SIZE>
-BlobVectorValueStore;
-
-typedef Vector<BlobVectorPageInfo,
-               BLOB_VECTOR_VALUE_STORE_TABLE_SIZE,
-               BLOB_VECTOR_VALUE_STORE_SECONDARY_TABLE_SIZE>
-BlobVectorIndexStore;
-
-class BlobVectorImpl {
- public:
-  static std::unique_ptr<BlobVectorImpl> create(io::Pool pool);
-  static std::unique_ptr<BlobVectorImpl> open(io::Pool pool,
-                                              uint32_t block_id);
-
-  Blob get_value(uint64_t id) {
-    return get_value(table_[id]);
-  }
-  void set_value(uint64_t id, const Blob &value);
-
-  void append(uint64_t id, const Blob &value);
-  void prepend(uint64_t id, const Blob &value);
-
-  uint32_t block_id() const {
-    return block_info_->id();
-  }
-
-  StringBuilder &write_to(StringBuilder &builder) const;
-
-  static void unlink(io::Pool pool, uint32_t block_id);
-
- private:
-  io::Pool pool_;
-  const io::BlockInfo *block_info_;
-  BlobVectorHeader *header_;
-  Recycler *recycler_;
-  BlobVectorTable table_;
-  BlobVectorValueStore value_store_;
-  BlobVectorIndexStore index_store_;
-  Mutex inter_thread_mutex_;
-
-  BlobVectorImpl();
-
-  void create_vector(io::Pool pool);
-  void open_vector(io::Pool pool, uint32_t block_id);
-
-  Blob get_value(BlobVectorCell cell);
-
-  inline BlobVectorCell create_value(const Blob &value);
-  inline BlobVectorCell join_values(const Blob &lhs, const Blob &rhs);
-
-  inline void *create_small_value(uint64_t length, BlobVectorCell *cell);
-  inline void *create_medium_value(uint64_t length, BlobVectorCell *cell);
-  inline void *create_large_value(uint64_t length, BlobVectorCell *cell);
-
-  void free_value(BlobVectorCell cell);
-
-  void register_large_value(uint32_t block_id,
-                            BlobVectorValueHeader *value_header);
-  void unregister_large_value(uint32_t block_id,
-                              BlobVectorValueHeader *value_header);
-
-  void freeze_page(uint32_t page_id);
-  void unfreeze_oldest_frozen_page();
-
-  Mutex *mutable_inter_thread_mutex() {
-    return &inter_thread_mutex_;
-  }
-  Mutex *mutable_inter_process_mutex() {
-    return header_->mutable_inter_process_mutex();
-  }
-};
-
-inline StringBuilder &operator<<(StringBuilder &builder,
-                                 const BlobVectorImpl &vector) {
-  return vector.write_to(builder);
-}
-
-class BlobVector {
- public:
-  BlobVector() = default;
-  BlobVector(const BlobVectorCreate &, io::Pool pool)
-    : impl_(BlobVectorImpl::create(pool)) {}
-  BlobVector(const BlobVectorOpen &, io::Pool pool, uint32_t block_id)
-    : impl_(BlobVectorImpl::open(pool, block_id)) {}
-
-  explicit operator bool() const {
-    return static_cast<bool>(impl_);
-  }
-
-  void create(io::Pool pool) {
-    *this = BlobVector(BLOB_VECTOR_CREATE, pool);
-  }
-  void open(io::Pool pool, uint32_t block_id) {
-    *this = BlobVector(BLOB_VECTOR_OPEN, pool, block_id);
-  }
-  void close() {
-    *this = BlobVector();
-  }
-
-  BlobRef operator[](uint64_t id) {
-    return BlobRef(this, id);
-  }
-
-  Blob get_value(uint64_t id) {
-    return impl_->get_value(id);
-  }
-  void set_value(uint64_t id, const Blob &value) {
-    impl_->set_value(id, value);
-  }
-
-  void append(uint64_t id, const Blob &value) {
-    impl_->append(id, value);
-  }
-  void prepend(uint64_t id, const Blob &value) {
-    impl_->prepend(id, value);
-  }
-
-  uint32_t block_id() const {
-    return impl_->block_id();
-  }
-
-  void swap(BlobVector &rhs) {
-    impl_.swap(rhs.impl_);
-  }
-
-  StringBuilder &write_to(StringBuilder &builder) const {
-    return impl_ ? impl_->write_to(builder) : (builder << "n/a");
-  }
-
-  static constexpr uint64_t max_id() {
-    return BLOB_VECTOR_MAX_ID;
-  }
-
-  static void unlink(io::Pool pool, uint32_t block_id) {
-    BlobVectorImpl::unlink(pool, block_id);
-  }
-
- private:
-  std::shared_ptr<BlobVectorImpl> impl_;
-};
-
-inline void swap(BlobVector &lhs, BlobVector &rhs) {
-  lhs.swap(rhs);
-}
-
-inline StringBuilder &operator<<(StringBuilder &builder,
-                                 const BlobVector &vector) {
-  return vector.write_to(builder);
-}
-
-inline Blob BlobRef::get() const {
-  return vector_.get_value(id_);
-}
-
-inline void BlobRef::set(const Blob &value) {
-  vector_.set_value(id_, value);
-}
-
-inline void BlobRef::append(const Blob &value) {
-  vector_.append(id_, value);
-}
-
-inline void BlobRef::prepend(const Blob &value) {
-  vector_.prepend(id_, value);
-}
-
-}  // namespace alpha
-}  // namespace grnxx
-
-#endif  // GRNXX_ALPHA_BLOB_VECTOR_HPP

  Modified: lib/db/blob_vector.cpp (+324 -673)
===================================================================
--- lib/db/blob_vector.cpp    2012-12-12 14:29:12 +0900 (09a4875)
+++ lib/db/blob_vector.cpp    2012-12-13 18:21:10 +0900 (a0564f8)
@@ -17,212 +17,164 @@
 */
 #include "blob_vector.hpp"
 
-#include <ostream>
-
 #include "../exception.hpp"
-#include "../logger.hpp"
 #include "../lock.hpp"
+#include "../logger.hpp"
 
 namespace grnxx {
 namespace db {
 
-void BlobVectorHeader::initialize(uint32_t cells_block_id,
-                                  Duration frozen_duration) {
-  std::memset(this, 0, sizeof(*this));
-
-  cells_block_id_ = cells_block_id;
-  frozen_duration_ = frozen_duration;
+BlobVectorCreate BLOB_VECTOR_CREATE;
+BlobVectorOpen BLOB_VECTOR_OPEN;
 
-  for (uint32_t i = 0; i < BLOB_VECTOR_MEDIUM_VALUE_STORES_NUM; ++i) {
-    medium_value_store_block_ids_[i] = io::BLOCK_INVALID_ID;
-  }
+BlobVectorHeader::BlobVectorHeader(uint32_t table_block_id)
+  : table_block_id_(table_block_id),
+    value_store_block_id_(io::BLOCK_INVALID_ID),
+    index_store_block_id_(io::BLOCK_INVALID_ID),
+    next_page_id_(0),
+    next_value_offset_(0),
+    latest_frozen_page_id_(BLOB_VECTOR_INVALID_PAGE_ID),
+    latest_large_value_block_id_(io::BLOCK_INVALID_ID),
+    inter_process_mutex_(MUTEX_UNLOCKED) {}
 
-  large_value_store_block_id_ = io::BLOCK_INVALID_ID;
-  rearmost_large_value_offset_ = BLOB_VECTOR_LARGE_VALUE_INVALID_OFFSET;
-  latest_frozen_large_value_offset_ = BLOB_VECTOR_LARGE_VALUE_INVALID_OFFSET;
-  for (uint32_t i = 0; i < BLOB_VECTOR_LARGE_VALUE_LISTS_NUM; ++i) {
-    oldest_idle_large_value_offsets_[i] =
-        BLOB_VECTOR_LARGE_VALUE_INVALID_OFFSET;
+StringBuilder &BlobVectorHeader::write_to(StringBuilder &builder) const {
+  if (!builder) {
+    return builder;
   }
 
-  inter_process_mutex_.unlock();
-  medium_value_store_mutex_.unlock();
-  large_value_store_mutex_.unlock();
-}
-
-BlobVector::BlobVector()
-  : pool_(),
-    block_info_(nullptr),
-    header_(nullptr),
-    recycler_(nullptr),
-    cells_(),
-    medium_value_stores_(),
-    large_value_store_(),
-    inter_thread_mutex_(MUTEX_UNLOCKED) {}
-
-BlobVector::~BlobVector() {}
-
-BlobVector::BlobVector(BlobVector &&rhs)
-  : pool_(std::move(rhs.pool_)),
-    block_info_(std::move(rhs.block_info_)),
-    header_(std::move(rhs.header_)),
-    recycler_(std::move(rhs.recycler_)),
-    cells_(std::move(rhs.cells_)),
-    medium_value_stores_(std::move(rhs.medium_value_stores_)),
-    large_value_store_(std::move(rhs.large_value_store_)),
-    inter_thread_mutex_(std::move(rhs.inter_thread_mutex_)) {}
-
-BlobVector &BlobVector::operator=(BlobVector &&rhs) {
-  pool_ = std::move(rhs.pool_);
-  block_info_ = std::move(rhs.block_info_);
-  header_ = std::move(rhs.header_);
-  recycler_ = std::move(rhs.recycler_);
-  cells_ = std::move(rhs.cells_);
-  medium_value_stores_ = std::move(rhs.medium_value_stores_);
-  large_value_store_ = std::move(rhs.large_value_store_);
-  inter_thread_mutex_ = std::move(rhs.inter_thread_mutex_);
-  return *this;
+  builder << "{ table_block_id = " << table_block_id_
+          << ", value_store_block_id = " << value_store_block_id_
+          << ", index_store_block_id = " << index_store_block_id_
+          << ", next_page_id = " << next_page_id_
+          << ", next_value_offset = " << next_value_offset_
+          << ", latest_large_value_block_id = " << latest_large_value_block_id_
+          << ", inter_process_mutex = " << inter_process_mutex_;
+  return builder << " }";
 }
 
-void BlobVector::create(io::Pool pool) {
-  if (!pool) {
-    GRNXX_ERROR() << "invalid argument: pool = " << pool;
+std::unique_ptr<BlobVectorImpl> BlobVectorImpl::create(io::Pool pool) {
+  std::unique_ptr<BlobVectorImpl> vector(new (std::nothrow) BlobVectorImpl);
+  if (!vector) {
+    GRNXX_ERROR() << "new grnxx::io::VectorImpl failed";
     GRNXX_THROW();
   }
-
-  BlobVector new_vector;
-  new_vector.create_vector(pool);
-  *this = std::move(new_vector);
+  vector->create_vector(pool);
+  return vector;
 }
 
-void BlobVector::open(io::Pool pool, uint32_t block_id) {
-  if (!pool) {
-    GRNXX_ERROR() << "invalid argument: pool = " << pool;
+std::unique_ptr<BlobVectorImpl> BlobVectorImpl::open(io::Pool pool,
+                                                     uint32_t block_id) {
+  std::unique_ptr<BlobVectorImpl> vector(new (std::nothrow) BlobVectorImpl);
+  if (!vector) {
+    GRNXX_ERROR() << "new grnxx::io::VectorImpl failed";
     GRNXX_THROW();
   }
-
-  BlobVector new_vector;
-  new_vector.open_vector(pool, block_id);
-  *this = std::move(new_vector);
+  vector->open_vector(pool, block_id);
+  return vector;
 }
 
-void BlobVector::close() {
-  if (!is_open()) {
-    GRNXX_ERROR() << "failed to close vector";
-    GRNXX_THROW();
+void BlobVectorImpl::set_value(uint64_t id, const Blob &value) {
+  const BlobVectorCell new_cell = create_value(value);
+  BlobVectorCell old_cell;
+  try {
+    do {
+      old_cell = table_[id];
+    } while (!atomic_compare_and_swap(old_cell, new_cell, &table_[id]));
+  } catch (...) {
+    // The new value is freed on failure.
+    free_value(new_cell);
+    throw;
   }
-  *this = BlobVector();
+  // The old value is freed on success.
+  free_value(old_cell);
 }
 
-const void *BlobVector::get_value_address(uint64_t id, uint64_t *length) {
-  const BlobVectorCell cell = cells_[id];
-  switch (cell.value_type()) {
-    case BLOB_VECTOR_SMALL_VALUE: {
-      if (length) {
-        *length = cell.small_value_cell().length();
-      }
-      // FIXME: the cell might be updated by other threads and processes.
-      return cells_[id].small_value_cell().value();
-    }
-    case BLOB_VECTOR_MEDIUM_VALUE: {
-      if (length) {
-        *length = cell.medium_value_cell().length();
-      }
-      const uint8_t store_id = cell.medium_value_cell().store_id();
-      const uint64_t offset = cell.medium_value_cell().offset();
-      BlobVectorMediumValueStore &store = medium_value_stores_[store_id];
-      if (!store) {
-        open_medium_value_store(store_id);
-      }
-      return &store[offset];
-    }
-    case BLOB_VECTOR_LARGE_VALUE: {
-      if (length) {
-        *length = cell.large_value_cell().length();
-      }
-      const uint64_t offset = cell.large_value_cell().offset();
-      if (!large_value_store_) {
-        open_large_value_store();
-      }
-      return get_large_value_header(offset)->value();
-    }
-    case BLOB_VECTOR_HUGE_VALUE: {
-      void *block_address =
-          pool_.get_block_address(cell.huge_value_cell().block_id());
-      if (length) {
-        *length = *static_cast<uint64_t *>(block_address);
-      }
-      return static_cast<uint64_t *>(block_address) + 1;
-    }
-    default: {
-      GRNXX_ERROR() << "invalid value type";
-      GRNXX_THROW();
+void BlobVectorImpl::append(uint64_t id, const Blob &value) {
+  if (!value || (value.length() == 0)) {
+    return;
+  }
+
+  for ( ; ; ) {
+    const BlobVectorCell old_cell = table_[id];
+    const Blob old_value = get_value(old_cell);
+    const BlobVectorCell new_cell = join_values(old_value, value);
+    if (atomic_compare_and_swap(old_cell, new_cell, &table_[id])) {
+      // The old value is freed on success.
+      free_value(old_cell);
+      break;
+    } else {
+      // The new value is freed on failure.
+      free_value(new_cell);
     }
   }
 }
 
-void BlobVector::set_value(uint64_t id, const void *ptr, uint64_t length) {
-  if (!ptr && (length != 0)) {
-    GRNXX_ERROR() << "invalid arguments: ptr = " << ptr
-                  << ", length = " << length;
-    GRNXX_THROW();
+void BlobVectorImpl::prepend(uint64_t id, const Blob &value) {
+  if (!value || (value.length() == 0)) {
+    return;
   }
 
-  BlobVectorCell new_cell;
-  if (length <= BLOB_VECTOR_SMALL_VALUE_LENGTH_MAX) {
-    new_cell = create_small_value_cell(ptr, length);
-  } else if (length <= BLOB_VECTOR_MEDIUM_VALUE_LENGTH_MAX) {
-    new_cell = create_medium_value_cell(ptr, length);
-  } else if (length <= BLOB_VECTOR_LARGE_VALUE_LENGTH_MAX) {
-    new_cell = create_large_value_cell(ptr, length);
-  } else {
-    new_cell = create_huge_value_cell(ptr, length);
+  for ( ; ; ) {
+    const BlobVectorCell old_cell = table_[id];
+    const Blob old_value = get_value(old_cell);
+    const BlobVectorCell new_cell = join_values(value, old_value);
+    if (atomic_compare_and_swap(old_cell, new_cell, &table_[id])) {
+      // The old value is freed on success.
+      free_value(old_cell);
+      break;
+    } else {
+      // The new value is freed on failure.
+      free_value(new_cell);
+    }
   }
+}
 
-  // The old cell is replaced with the new one.
-  // Then, the resources allocated to the old cell are freed.
-  BlobVectorCell old_cell;
-  try {
-    do {
-      old_cell = cells_[id];
-    } while (!atomic_compare_and_swap(old_cell, new_cell, &cells_[id]));
-  } catch (...) {
-    free_value(new_cell);
-    throw;
+StringBuilder &BlobVectorImpl::write_to(StringBuilder &builder) const {
+  if (!builder) {
+    return builder;
   }
-  free_value(old_cell);
-}
 
-void BlobVector::swap(BlobVector &rhs) {
-  using std::swap;
-  swap(pool_, rhs.pool_);
-  swap(block_info_, rhs.block_info_);
-  swap(header_, rhs.header_);
-  swap(recycler_, rhs.recycler_);
-  swap(cells_, rhs.cells_);
-  swap(medium_value_stores_, rhs.medium_value_stores_);
-  swap(large_value_store_, rhs.large_value_store_);
-  swap(inter_thread_mutex_, rhs.inter_thread_mutex_);
+  builder << "{ pool = " << pool_.path()
+          << ", block_info = " << *block_info_
+          << ", header = " << *header_
+          << ", inter_thread_mutex = " << inter_thread_mutex_;
+  return builder << " }";
 }
 
-void BlobVector::unlink(io::Pool pool, uint32_t block_id) {
-  if (!pool) {
-    GRNXX_ERROR() << "invalid argument: pool = " << pool;
-    GRNXX_THROW();
-  }
-
-  BlobVector vector;
-  vector.open(pool, block_id);
+void BlobVectorImpl::unlink(io::Pool pool, uint32_t block_id) {
+  std::unique_ptr<BlobVectorImpl> vector =
+      BlobVectorImpl::open(pool, block_id);
 
-  // TODO
+  if (vector->header_->latest_large_value_block_id() != io::BLOCK_INVALID_ID) {
+    uint32_t block_id = vector->header_->latest_large_value_block_id();
+    do {
+      auto value_header = static_cast<const BlobVectorValueHeader *>(
+          pool.get_block_address(block_id));
+      const uint32_t prev_block_id = value_header->prev_value_block_id();
+      pool.free_block(block_id);
+      block_id = prev_block_id;
+    } while (block_id != vector->header_->latest_large_value_block_id());
+  }
+  BlobVectorTable::unlink(pool, vector->header_->table_block_id());
+  pool.free_block(vector->block_info_->id());
 }
 
-void BlobVector::create_vector(io::Pool pool) {
+BlobVectorImpl::BlobVectorImpl()
+  : pool_(),
+    block_info_(nullptr),
+    header_(nullptr),
+    recycler_(nullptr),
+    table_(),
+    value_store_(),
+    index_store_(),
+    inter_thread_mutex_(MUTEX_UNLOCKED) {}
+
+void BlobVectorImpl::create_vector(io::Pool pool) {
   pool_ = pool;
   block_info_ = pool.create_block(sizeof(BlobVectorHeader));
 
   try {
-    cells_.create(pool_, BlobVectorCell());
+    table_.create(pool_, BlobVectorCell::null_value());
   } catch (...) {
     pool_.free_block(*block_info_);
     throw;
@@ -230,12 +182,12 @@ void BlobVector::create_vector(io::Pool pool) {
 
   void * const block_address = pool_.get_block_address(*block_info_);
   header_ = static_cast<BlobVectorHeader *>(block_address);
-  header_->initialize(cells_.block_id(), pool.options().frozen_duration());
+  *header_ = BlobVectorHeader(table_.block_id());
 
   recycler_ = pool.mutable_recycler();
 }
 
-void BlobVector::open_vector(io::Pool pool, uint32_t block_id) {
+void BlobVectorImpl::open_vector(io::Pool pool, uint32_t block_id) {
   pool_ = pool;
   block_info_ = pool.get_block_info(block_id);
   if (block_info_->size() < sizeof(BlobVectorHeader)) {
@@ -247,571 +199,270 @@ void BlobVector::open_vector(io::Pool pool, uint32_t block_id) {
   void * const block_address = pool_.get_block_address(*block_info_);
   header_ = static_cast<BlobVectorHeader *>(block_address);
 
-  // TODO: check the header!
+  // TODO: Check the format!
 
   recycler_ = pool.mutable_recycler();
 
   // Open the core table.
-  cells_.open(pool, header_->cells_block_id());
+  table_.open(pool, header_->table_block_id());
 }
 
-BlobVectorSmallValueCell BlobVector::create_small_value_cell(
-    const void *ptr, uint64_t length) {
-  return BlobVectorSmallValueCell(ptr, length);
-}
-
-BlobVectorMediumValueCell BlobVector::create_medium_value_cell(
-    const void *ptr, uint64_t length) {
-  const uint8_t store_id = get_store_id(length);
-  BlobVectorMediumValueStore &store = medium_value_stores_[store_id];
-  if (!store) {
-    open_medium_value_store(store_id);
-  }
-
-  uint64_t offset;
-  {
-    Lock lock(header_->mutable_medium_value_store_mutex());
-
-    // TODO: Reuse.
-
-    offset = header_->medium_value_store_next_offsets(store_id);
-    if (offset > store.max_id()) {
-      GRNXX_ERROR() << "store is full: offset = " << offset
-                    << ", max_id = " << store.max_id();
-      GRNXX_THROW();
+Blob BlobVectorImpl::get_value(BlobVectorCell cell) {
+  switch (cell.type()) {
+    case BLOB_VECTOR_NULL: {
+      return Blob(nullptr);
     }
-    header_->set_medium_value_store_next_offsets(store_id,
-        offset + (1 << (store_id + BLOB_VECTOR_MEDIUM_VALUE_UNIT_SIZE_BITS)));
-  }
-
-  std::memcpy(&store[offset], ptr, length);
-  return BlobVectorMediumValueCell(store_id, offset, length);
-}
-
-BlobVectorLargeValueCell BlobVector::create_large_value_cell(
-    const void *ptr, uint64_t length) {
-  typedef BlobVectorLargeValueHeader ValueHeader;
-
-  if (!large_value_store_) {
-    open_large_value_store();
-  }
-
-  const uint64_t capacity = ~(BLOB_VECTOR_LARGE_VALUE_UNIT_SIZE - 1) &
-      (length + (BLOB_VECTOR_LARGE_VALUE_UNIT_SIZE - 1));
-  const uint64_t required_size = sizeof(ValueHeader) + capacity;
-
-  uint64_t offset;
-  {
-    Lock lock(header_->mutable_large_value_store_mutex());
-
-    unfreeze_frozen_large_values();
-
-    uint8_t list_id = get_list_id(capacity - 1);
-    for (++list_id ; list_id < BLOB_VECTOR_LARGE_VALUE_LISTS_NUM; ++list_id) {
-      if (header_->oldest_idle_large_value_offsets(list_id) !=
-          BLOB_VECTOR_LARGE_VALUE_INVALID_OFFSET) {
-        offset = header_->oldest_idle_large_value_offsets(list_id);
-        break;
-      }
+    case BLOB_VECTOR_SMALL: {
+      return Blob(cell);
     }
-
-    if (list_id < BLOB_VECTOR_LARGE_VALUE_LISTS_NUM) {
-      auto header = get_large_value_header(offset);
-      if (header->capacity() > capacity) {
-        divide_idle_large_value(offset, capacity);
-      } else {
-        unregister_idle_large_value(offset);
-        header->set_type(BLOB_VECTOR_ACTIVE_VALUE);
-      }
-    } else {
-      BlobVectorLargeValueFlags flags = BlobVectorLargeValueFlags::none();
-      uint64_t prev_capacity = 0;
-
-      const uint64_t prev_offset = header_->rearmost_large_value_offset();
-      ValueHeader *prev_header = nullptr;
-      if (prev_offset == BLOB_VECTOR_LARGE_VALUE_INVALID_OFFSET) {
-        offset = 0;
-      } else {
-        prev_header = get_large_value_header(prev_offset);
-        offset = prev_offset + prev_header->capacity() + sizeof(ValueHeader);
-
-        const uint64_t size_left = BLOB_VECTOR_LARGE_VALUE_STORE_PAGE_SIZE
-            - (offset & (BLOB_VECTOR_LARGE_VALUE_STORE_PAGE_SIZE - 1));
-        if (size_left < required_size) {
-          auto header = get_large_value_header(offset);
-          header->initialize(BLOB_VECTOR_IDLE_VALUE,
-                             BLOB_VECTOR_LARGE_VALUE_HAS_PREV,
-                             size_left - sizeof(ValueHeader),
-                             prev_header->capacity());
-          prev_header->set_flags(
-              prev_header->flags() | BLOB_VECTOR_LARGE_VALUE_HAS_NEXT);
-          header_->set_rearmost_large_value_offset(offset);
-          register_idle_large_value(offset);
-          offset += size_left;
-        } else if (size_left < BLOB_VECTOR_LARGE_VALUE_STORE_PAGE_SIZE) {
-          flags |= BLOB_VECTOR_LARGE_VALUE_HAS_PREV;
-          prev_capacity = prev_header->capacity();
+    case BLOB_VECTOR_MEDIUM: {
+      if (!value_store_) {
+        Lock lock(mutable_inter_thread_mutex());
+        if (!value_store_) {
+          value_store_.open(pool_, header_->value_store_block_id());
         }
       }
-
-      auto header = get_large_value_header(offset);
-      header->initialize(BLOB_VECTOR_ACTIVE_VALUE,
-                         flags, capacity, prev_capacity);
-      if (flags & BLOB_VECTOR_LARGE_VALUE_HAS_PREV) {
-        prev_header->set_flags(
-            prev_header->flags() | BLOB_VECTOR_LARGE_VALUE_HAS_NEXT);
-      }
-      header_->set_rearmost_large_value_offset(offset);
-    }
-  }
-
-  std::memcpy(get_large_value_header(offset)->value(), ptr, length);
-  return BlobVectorLargeValueCell(offset, length);
-}
-
-BlobVectorHugeValueCell BlobVector::create_huge_value_cell(
-    const void *ptr, uint64_t length) {
-  const io::BlockInfo *block_info =
-      pool_.create_block(sizeof(uint64_t) + length);
-  void * const block_address = pool_.get_block_address(*block_info);
-  *static_cast<uint64_t *>(block_address) = length;
-  std::memcpy(static_cast<uint64_t *>(block_address) + 1, ptr, length);
-  return BlobVectorHugeValueCell(block_info->id());
-}
-
-void BlobVector::free_value(BlobVectorCell cell) {
-  switch (cell.value_type()) {
-    case BLOB_VECTOR_SMALL_VALUE: {
-      // Nothing to do.
-      break;
-    }
-    case BLOB_VECTOR_MEDIUM_VALUE: {
-      // TODO
-      break;
-    }
-    case BLOB_VECTOR_LARGE_VALUE: {
-      typedef BlobVectorLargeValueHeader ValueHeader;
-      Lock lock(header_->mutable_large_value_store_mutex());
-      if (!large_value_store_) {
-        open_large_value_store();
-      }
-      const uint64_t offset = cell.large_value_cell().offset();
-      ValueHeader * const header = get_large_value_header(offset);
-      header->set_frozen_stamp(recycler_->stamp());
-      header->set_type(BLOB_VECTOR_FROZEN_VALUE);
-      const uint64_t latest_offset =
-          header_->latest_frozen_large_value_offset();
-      if (latest_offset == BLOB_VECTOR_LARGE_VALUE_INVALID_OFFSET) {
-        header->set_next_offset(offset);
-      } else {
-        ValueHeader * const latest_header =
-            get_large_value_header(header_->latest_frozen_large_value_offset());
-        header->set_next_offset(latest_header->next_offset());
-        latest_header->set_next_offset(offset);
-      }
-      header_->set_latest_frozen_large_value_offset(offset);
-      break;
+      return Blob(&value_store_[cell.offset()], cell.medium_length());
     }
-    case BLOB_VECTOR_HUGE_VALUE: {
-      pool_.free_block(cell.huge_value_cell().block_id());
-      break;
+    case BLOB_VECTOR_LARGE: {
+      const auto value_header = static_cast<const BlobVectorValueHeader *>(
+          pool_.get_block_address(cell.block_id()));
+      return Blob(value_header + 1, value_header->length());
     }
-  }
-}
-
-void BlobVector::open_medium_value_store(uint8_t store_id) {
-  Lock inter_thread_lock(&inter_thread_mutex_);
-  BlobVectorMediumValueStore &store = medium_value_stores_[store_id];
-  if (!store) {
-    if (header_->medium_value_store_block_ids(store_id) ==
-        io::BLOCK_INVALID_ID) {
-      Lock inter_process_lock(header_->mutable_inter_process_mutex());
-      if (header_->medium_value_store_block_ids(store_id) ==
-          io::BLOCK_INVALID_ID) {
-        store.create(pool_);
-        header_->set_medium_value_store_block_ids(store_id, store.block_id());
-      }
-    }
-    if (!store) {
-      store.open(pool_, header_->medium_value_store_block_ids(store_id));
-    }
-  }
-}
-
-void BlobVector::open_large_value_store() {
-  Lock inter_thread_lock(&inter_thread_mutex_);
-  if (!large_value_store_) {
-    if (header_->large_value_store_block_id() == io::BLOCK_INVALID_ID) {
-      Lock inter_process_lock(header_->mutable_inter_process_mutex());
-      if (header_->large_value_store_block_id() == io::BLOCK_INVALID_ID) {
-        large_value_store_.create(pool_);
-        header_->set_large_value_store_block_id(large_value_store_.block_id());
-      }
-    }
-    if (!large_value_store_) {
-      large_value_store_.open(pool_, header_->large_value_store_block_id());
-    }
-  }
-}
-
-void BlobVector::unfreeze_frozen_large_values() {
-  if (header_->latest_frozen_large_value_offset() !=
-      BLOB_VECTOR_LARGE_VALUE_INVALID_OFFSET) {
-    auto latest_frozen_value_header =
-        get_large_value_header(header_->latest_frozen_large_value_offset());
-    for (int i = 0; i < 5; ++i) {
-      const uint64_t oldest_frozen_value_offset =
-          latest_frozen_value_header->next_offset();
-      auto oldest_frozen_value_header =
-          get_large_value_header(oldest_frozen_value_offset);
-      if (!recycler_->check(oldest_frozen_value_header->frozen_stamp())) {
-        break;
-      }
-      latest_frozen_value_header->set_next_offset(
-          oldest_frozen_value_header->next_offset());
-      oldest_frozen_value_header->set_type(BLOB_VECTOR_IDLE_VALUE);
-      register_idle_large_value(oldest_frozen_value_offset);
-      merge_idle_large_values(oldest_frozen_value_offset);
-      if (latest_frozen_value_header == oldest_frozen_value_header) {
-        header_->set_latest_frozen_large_value_offset(
-            BLOB_VECTOR_LARGE_VALUE_INVALID_OFFSET);
-        break;
-      }
-    }
-  }
-}
-
-void BlobVector::divide_idle_large_value(uint64_t offset, uint64_t capacity) {
-  typedef BlobVectorLargeValueHeader ValueHeader;
-
-  unregister_idle_large_value(offset);
-
-  const uint64_t next_offset = offset + capacity + sizeof(ValueHeader);
-  auto header = get_large_value_header(offset);
-  auto next_header = get_large_value_header(next_offset);
-  next_header->initialize(BLOB_VECTOR_IDLE_VALUE,
-                          BLOB_VECTOR_LARGE_VALUE_HAS_PREV |
-                          (header->flags() & BLOB_VECTOR_LARGE_VALUE_HAS_NEXT),
-                          header->capacity() - capacity - sizeof(ValueHeader),
-                          capacity);
-
-  if (header->flags() & BLOB_VECTOR_LARGE_VALUE_HAS_NEXT) {
-    const uint64_t next_next_offset =
-        offset + header->capacity() + sizeof(ValueHeader);
-    auto next_next_header = get_large_value_header(next_next_offset);
-    next_next_header->set_prev_capacity(next_header->capacity());
-  }
-
-  header->set_type(BLOB_VECTOR_ACTIVE_VALUE);
-  header->set_flags(header->flags() | BLOB_VECTOR_LARGE_VALUE_HAS_NEXT);
-  header->set_capacity(capacity);
-
-  register_idle_large_value(next_offset);
-
-  if (offset == header_->rearmost_large_value_offset()) {
-    header_->set_rearmost_large_value_offset(next_offset);
-  }
-}
-
-void BlobVector::merge_idle_large_values(uint64_t offset) {
-  typedef BlobVectorLargeValueHeader ValueHeader;
-
-  auto header = get_large_value_header(offset);
-  if (header->flags() & BLOB_VECTOR_LARGE_VALUE_HAS_NEXT) {
-    const uint64_t next_offset =
-        offset + header->capacity() + sizeof(ValueHeader);
-    auto next_header = get_large_value_header(next_offset);
-    if (next_header->type() == BLOB_VECTOR_IDLE_VALUE) {
-      merge_idle_large_values(offset, next_offset);
-    }
-  }
-  if (header->flags() & BLOB_VECTOR_LARGE_VALUE_HAS_PREV) {
-    const uint64_t prev_offset =
-        offset - header->prev_capacity() - sizeof(ValueHeader);
-    auto prev_header = get_large_value_header(prev_offset);
-    if (prev_header->type() == BLOB_VECTOR_IDLE_VALUE) {
-      merge_idle_large_values(prev_offset, offset);
+    default: {
+      GRNXX_ERROR() << "invalid value type";
+      GRNXX_THROW();
     }
   }
 }
 
-void BlobVector::merge_idle_large_values(uint64_t offset, uint64_t next_offset) {
-  typedef BlobVectorLargeValueHeader ValueHeader;
-
-  unregister_idle_large_value(offset);
-  unregister_idle_large_value(next_offset);
-
-  auto header = get_large_value_header(offset);
-  auto next_header = get_large_value_header(next_offset);
-
-  header->set_flags((header->flags() & BLOB_VECTOR_LARGE_VALUE_HAS_PREV) |
-                    (next_header->flags() & BLOB_VECTOR_LARGE_VALUE_HAS_NEXT));
-  header->set_capacity(
-      header->capacity() + next_header->capacity() + sizeof(ValueHeader));
-
-  if (next_header->flags() & BLOB_VECTOR_LARGE_VALUE_HAS_NEXT) {
-    const uint64_t next_next_offset =
-        next_offset + next_header->capacity() + sizeof(ValueHeader);
-    auto next_next_header = get_large_value_header(next_next_offset);
-    next_next_header->set_prev_capacity(header->capacity());
+BlobVectorCell BlobVectorImpl::create_value(const Blob &value) {
+  if (!value) {
+    return BlobVectorCell::null_value();
   }
 
-  register_idle_large_value(offset);
-
-  if (next_offset == header_->rearmost_large_value_offset()) {
-    header_->set_rearmost_large_value_offset(offset);
-  }
-}
-
-void BlobVector::register_idle_large_value(uint64_t offset) {
-  auto header = get_large_value_header(offset);
-  if (header->capacity() < BLOB_VECTOR_LARGE_VALUE_LENGTH_MIN) {
-    return;
-  }
-  const uint8_t list_id = get_list_id(header->capacity());
-  const uint64_t oldest_idle_value_offset =
-      header_->oldest_idle_large_value_offsets(list_id);
-  if (oldest_idle_value_offset == BLOB_VECTOR_LARGE_VALUE_INVALID_OFFSET) {
-    header->set_next_offset(offset);
-    header->set_prev_offset(offset);
-    header_->set_oldest_idle_large_value_offsets(list_id, offset);
+  BlobVectorCell cell;
+  void *address;
+  if (value.length() < BLOB_VECTOR_MEDIUM_VALUE_MIN_LENGTH) {
+    address = create_small_value(value.length(), &cell);
+  } else if (value.length() < BLOB_VECTOR_LARGE_VALUE_MIN_LENGTH) {
+    address = create_medium_value(value.length(), &cell);
   } else {
-    auto next_header = get_large_value_header(oldest_idle_value_offset);
-    auto prev_header = get_large_value_header(next_header->prev_offset());
-    header->set_next_offset(oldest_idle_value_offset);
-    header->set_prev_offset(next_header->prev_offset());
-    prev_header->set_next_offset(offset);
-    next_header->set_prev_offset(offset);
+    address = create_large_value(value.length(), &cell);
   }
+  std::memcpy(address, value.address(), value.length());
+  return cell;
 }
 
-void BlobVector::unregister_idle_large_value(uint64_t offset) {
-  auto header = get_large_value_header(offset);
-  if (header->capacity() < BLOB_VECTOR_LARGE_VALUE_LENGTH_MIN) {
-    return;
-  }
-  const uint8_t list_id = get_list_id(header->capacity());
-  if (offset == header->next_offset()) {
-    header_->set_oldest_idle_large_value_offsets(
-        list_id, BLOB_VECTOR_LARGE_VALUE_INVALID_OFFSET);
+BlobVectorCell BlobVectorImpl::join_values(const Blob &lhs, const Blob &rhs) {
+  const uint64_t length = lhs.length() + rhs.length();
+  BlobVectorCell cell;
+  void *address;
+  if (length < BLOB_VECTOR_MEDIUM_VALUE_MIN_LENGTH) {
+    address = create_small_value(length, &cell);
+  } else if (length < BLOB_VECTOR_LARGE_VALUE_MIN_LENGTH) {
+    address = create_medium_value(length, &cell);
   } else {
-    auto next_header = get_large_value_header(header->next_offset());
-    auto prev_header = get_large_value_header(header->prev_offset());
-    next_header->set_prev_offset(header->prev_offset());
-    prev_header->set_next_offset(header->next_offset());
-    if (offset == header_->oldest_idle_large_value_offsets(list_id)) {
-      header_->set_oldest_idle_large_value_offsets(
-          list_id, header->next_offset());
-    }
+    address = create_large_value(length, &cell);
   }
+  std::memcpy(address, lhs.address(), lhs.length());
+  std::memcpy(static_cast<char *>(address) + lhs.length(),
+              rhs.address(), rhs.length());
+  return cell;
 }
 
-StringBuilder &operator<<(StringBuilder &builder, BlobVectorLargeValueType type) {
-  switch (type) {
-    case BLOB_VECTOR_ACTIVE_VALUE: {
-      return builder << "BLOB_VECTOR_ACTIVE_VALUE";
-    }
-    case BLOB_VECTOR_FROZEN_VALUE: {
-      return builder << "BLOB_VECTOR_FROZEN_VALUE";
-    }
-    case BLOB_VECTOR_IDLE_VALUE: {
-      return builder << "BLOB_VECTOR_IDLE_VALUE";
-    }
-    default: {
-      return builder << "n/a";
-    }
- }
+void *BlobVectorImpl::create_small_value(uint64_t length,
+                                         BlobVectorCell *cell) {
+  *cell = BlobVectorCell::small_value(length);
+  return cell->value();
 }
 
-StringBuilder &operator<<(StringBuilder &builder, BlobVectorLargeValueFlags flags) {
-  if (!builder) {
-    return builder;
-  }
+void *BlobVectorImpl::create_medium_value(uint64_t length,
+                                          BlobVectorCell *cell) {
+  Lock lock(mutable_inter_thread_mutex());
 
-  if (flags) {
-    bool is_first = true;
-    if (flags & BLOB_VECTOR_LARGE_VALUE_HAS_NEXT) {
-      builder << "BLOB_VECTOR_LARGE_VALUE_HAS_NEXT";
-      is_first = false;
-    }
-    if (flags & BLOB_VECTOR_LARGE_VALUE_HAS_PREV) {
-      if (!is_first) {
-        builder << " | ";
+  if (!value_store_) {
+    if (header_->value_store_block_id() == io::BLOCK_INVALID_ID) {
+      Lock lock(mutable_inter_process_mutex());
+      if (header_->value_store_block_id() == io::BLOCK_INVALID_ID) {
+        value_store_.create(pool_);
+        header_->set_value_store_block_id(value_store_.block_id());
       }
-      builder << "BLOB_VECTOR_LARGE_VALUE_HAS_PREV";
     }
-    return builder;
-  } else {
-    return builder << "0";
+    if (!value_store_) {
+      value_store_.open(pool_, header_->value_store_block_id());
+    }
   }
-}
 
-StringBuilder &operator<<(StringBuilder &builder, BlobVectorValueType type) {
-  switch (type) {
-    case BLOB_VECTOR_SMALL_VALUE: {
-      return builder << "BLOB_VECTOR_SMALL_VALUE";
-    }
-    case BLOB_VECTOR_MEDIUM_VALUE: {
-      return builder << "BLOB_VECTOR_MEDIUM_VALUE";
-    }
-    case BLOB_VECTOR_LARGE_VALUE: {
-      return builder << "BLOB_VECTOR_LARGE_VALUE";
-    }
-    case BLOB_VECTOR_HUGE_VALUE: {
-      return builder << "BLOB_VECTOR_HUGE_VALUE";
+  if (!index_store_) {
+    if (header_->index_store_block_id() == io::BLOCK_INVALID_ID) {
+      Lock lock(mutable_inter_process_mutex());
+      if (header_->index_store_block_id() == io::BLOCK_INVALID_ID) {
+        index_store_.create(pool_, BlobVectorPageInfo());
+        header_->set_index_store_block_id(index_store_.block_id());
+      }
     }
-    default: {
-      return builder << "n/a";
+    if (!index_store_) {
+      index_store_.open(pool_, header_->index_store_block_id());
     }
   }
-}
 
-StringBuilder &operator<<(StringBuilder &builder, BlobVectorCellFlags flags) {
-  BlobVectorCellFlags clone = flags;
-  clone.flags &= BLOB_VECTOR_VALUE_TYPE_MASK;
-  return builder << clone.value_type;
-}
+  // Unfreeze the oldest frozen page for reuse.
+  unfreeze_oldest_frozen_page();
 
-StringBuilder &BlobVectorHeader::write_to(StringBuilder &builder) const {
-  if (!builder) {
-    return builder;
-  }
+  uint64_t offset = header_->next_value_offset();
+  const uint64_t offset_in_page =
+      ((offset - 1) & (BLOB_VECTOR_VALUE_STORE_PAGE_SIZE - 1)) + 1;
+  const uint64_t size_left_in_page =
+      BLOB_VECTOR_VALUE_STORE_PAGE_SIZE - offset_in_page;
 
-  builder << "{ cells_block_id = " << cells_block_id_;
-
-  builder << ", medium_value_store_block_ids = ";
-  bool is_empty = true;
-  for (uint32_t i = 0; i < BLOB_VECTOR_MEDIUM_VALUE_STORES_NUM; ++i) {
-    if (medium_value_store_block_ids_[i] != io::BLOCK_INVALID_ID) {
-      if (is_empty) {
-        builder << "{ ";
-        is_empty = false;
-      } else {
-        builder << ", ";
+  // Reserve a new page if there is not enough space in the current page.
+  if (length > size_left_in_page) {
+    if (offset != 0) {
+      // Freeze the current page if it is empty.
+      const uint32_t page_id = static_cast<uint32_t>(
+          (offset - 1) >> BLOB_VECTOR_VALUE_STORE_PAGE_SIZE_BITS);
+      if (index_store_[page_id].num_values() == 0) {
+        freeze_page(page_id);
       }
-      builder << '[' << i << "] = " << medium_value_store_block_ids_[i];
     }
-  }
-  builder << (is_empty ? "{}" : " }");
-
-  builder << ", medium_value_store_next_offsets = ";
-  is_empty = true;
-  for (uint32_t i = 0; i < BLOB_VECTOR_MEDIUM_VALUE_STORES_NUM; ++i) {
-    if (medium_value_store_next_offsets_[i] != 0) {
-      if (is_empty) {
-        builder << "{ ";
-        is_empty = false;
-      } else {
-        builder << ", ";
-      }
-      builder << '[' << i << "] = " << medium_value_store_next_offsets_[i];
-    }
-  }
-  builder << (is_empty ? "{}" : " }");
-
-  builder << ", large_value_store_block_id = " << large_value_store_block_id_
-          << ", rearmost_large_value_offset = " << rearmost_large_value_offset_
-          << ", latest_frozen_large_value_offset = "
-          << latest_frozen_large_value_offset_;
-
-  builder << ", oldest_idle_large_value_offsets = ";
-  is_empty = true;
-  for (uint32_t i = 0; i < BLOB_VECTOR_LARGE_VALUE_LISTS_NUM; ++i) {
-    if (oldest_idle_large_value_offsets_[i] !=
-        BLOB_VECTOR_LARGE_VALUE_INVALID_OFFSET) {
-      if (is_empty) {
-        builder << "{ ";
-        is_empty = false;
-      } else {
-        builder << ", ";
-      }
-      builder << '[' << i << "] = " << oldest_idle_large_value_offsets_[i];
-    }
-  }
-  builder << (is_empty ? "{}" : " }");
-
-  builder << ", inter_process_mutex = " << inter_process_mutex_
-          << ", large_value_store_mutex = " << large_value_store_mutex_;
-  return builder << " }";
-}
 
-StringBuilder &BlobVectorLargeValueHeader::write_to(StringBuilder &builder) const {
-  if (!builder) {
-    return builder;
+    const uint32_t page_id = header_->next_page_id();
+    offset = static_cast<uint64_t>(
+        page_id << BLOB_VECTOR_VALUE_STORE_PAGE_SIZE_BITS);
+    if (index_store_[page_id].next_page_id() != BLOB_VECTOR_INVALID_PAGE_ID) {
+      header_->set_next_page_id(index_store_[page_id].next_page_id());
+    } else {
+      header_->set_next_page_id(page_id + 1);
+    }
+    index_store_[page_id].set_num_values(0);
   }
+  header_->set_next_value_offset(offset + length);
 
-  builder << "{ type = " << type()
-          << ", flags = " << flags()
-          << ", capacity = " << capacity()
-          << ", prev_capacity = " << prev_capacity();
+  const uint32_t page_id = static_cast<uint32_t>(
+      offset >> BLOB_VECTOR_VALUE_STORE_PAGE_SIZE_BITS);
+  index_store_[page_id].set_num_values(index_store_[page_id].num_values() + 1);
 
-  switch (type()) {
-    case BLOB_VECTOR_ACTIVE_VALUE: {
-      break;
-    }
-    case BLOB_VECTOR_FROZEN_VALUE: {
-      builder << ", next_offset = " << next_offset()
-              << ", frozen_stamp = " << frozen_stamp();
-      break;
-    }
-    case BLOB_VECTOR_IDLE_VALUE: {
-      builder << ", next_offset = " << next_offset()
-              << ", prev_offset = " << prev_offset();
-      break;
-    }
-  }
-  return builder << " }";
+  *cell = BlobVectorCell::medium_value(offset, length);
+  return &value_store_[offset];
 }
 
-StringBuilder &BlobVectorCell::write_to(StringBuilder &builder) const {
-  if (!builder) {
-    return builder;
-  }
-
-  builder << "{ value_type = " << value_type();
-  switch (value_type()) {
-    case BLOB_VECTOR_SMALL_VALUE: {
-      builder << ", length = " << small_value_cell().length();
-      break;
-    }
-    case BLOB_VECTOR_MEDIUM_VALUE: {
-      builder << ", store_id = " << medium_value_cell().store_id()
-              << ", capacity = " << medium_value_cell().capacity()
-              << ", length = " << medium_value_cell().length()
-              << ", offset = " << medium_value_cell().offset();
+void *BlobVectorImpl::create_large_value(uint64_t length,
+                                         BlobVectorCell *cell) {
+  const io::BlockInfo *block_info =
+      pool_.create_block(sizeof(BlobVectorValueHeader) + length);
+  auto value_header = static_cast<BlobVectorValueHeader *>(
+      pool_.get_block_address(*block_info));
+  value_header->set_length(length);
+  register_large_value(block_info->id(), value_header);
+  *cell = BlobVectorCell::large_value(block_info->id());
+  return value_header + 1;
+}
+
+void BlobVectorImpl::free_value(BlobVectorCell cell) {
+  switch (cell.type()) {
+    case BLOB_VECTOR_NULL:
+    case BLOB_VECTOR_SMALL: {
       break;
     }
-    case BLOB_VECTOR_LARGE_VALUE: {
-      builder << ", length = " << large_value_cell().length()
-              << ", offset = " << large_value_cell().offset();
+    case BLOB_VECTOR_MEDIUM: {
+      Lock lock(mutable_inter_thread_mutex());
+
+      const uint32_t page_id = static_cast<uint32_t>(
+          cell.offset() >> BLOB_VECTOR_VALUE_STORE_PAGE_SIZE_BITS);
+      index_store_[page_id].set_num_values(
+          index_store_[page_id].num_values() - 1);
+      if (index_store_[page_id].num_values() == 0) {
+        const uint32_t current_page_id =
+            static_cast<uint32_t>(header_->next_value_offset()
+                                  >> BLOB_VECTOR_VALUE_STORE_PAGE_SIZE_BITS);
+        if (page_id != current_page_id) {
+          freeze_page(page_id);
+        }
+      }
       break;
     }
-    case BLOB_VECTOR_HUGE_VALUE: {
-      builder << ", block_id = " << huge_value_cell().block_id();
+    case BLOB_VECTOR_LARGE: {
+      const io::BlockInfo * const block_info =
+          pool_.get_block_info(cell.block_id());
+      unregister_large_value(block_info->id(),
+          static_cast<BlobVectorValueHeader *>(
+              pool_.get_block_address(*block_info)));
+      pool_.free_block(*block_info);
       break;
     }
   }
-  return builder << " }";
 }
 
-StringBuilder &BlobVector::write_to(StringBuilder &builder) const {
-  if (!builder) {
-    return builder;
-  }
-
-  if (!is_open()) {
-    return builder << "n/a";
-  }
-
-  builder << "{ pool = " << pool_.path()
-          << ", block_info = " << *block_info_
-          << ", header = ";
-  if (header_) {
-    builder << *header_;
+void BlobVectorImpl::register_large_value(uint32_t block_id,
+    BlobVectorValueHeader *value_header) {
+  Lock lock(mutable_inter_process_mutex());
+  if (header_->latest_large_value_block_id() == io::BLOCK_INVALID_ID) {
+    value_header->set_next_value_block_id(block_id);
+    value_header->set_prev_value_block_id(block_id);
   } else {
-    builder << "n/a";
+    const uint32_t prev_id = header_->latest_large_value_block_id();
+    auto prev_header = static_cast<BlobVectorValueHeader *>(
+        pool_.get_block_address(prev_id));
+    const uint32_t next_id = prev_header->next_value_block_id();
+    auto next_header = static_cast<BlobVectorValueHeader *>(
+        pool_.get_block_address(next_id));
+    value_header->set_next_value_block_id(next_id);
+    value_header->set_prev_value_block_id(prev_id);
+    prev_header->set_next_value_block_id(block_id);
+    next_header->set_prev_value_block_id(block_id);
+  }
+  header_->set_latest_large_value_block_id(block_id);
+}
+
+void BlobVectorImpl::unregister_large_value(uint32_t block_id,
+    BlobVectorValueHeader *value_header) {
+  Lock lock(mutable_inter_process_mutex());
+  const uint32_t next_id = value_header->next_value_block_id();
+  const uint32_t prev_id = value_header->prev_value_block_id();
+  auto next_header = static_cast<BlobVectorValueHeader *>(
+      pool_.get_block_address(next_id));
+  auto prev_header = static_cast<BlobVectorValueHeader *>(
+      pool_.get_block_address(prev_id));
+  next_header->set_prev_value_block_id(prev_id);
+  prev_header->set_next_value_block_id(next_id);
+  if (block_id == header_->latest_large_value_block_id()) {
+    header_->set_latest_large_value_block_id(prev_id);
+  }
+}
+
+void BlobVectorImpl::freeze_page(uint32_t page_id) {
+  BlobVectorPageInfo &page_info = index_store_[page_id];
+  if (header_->latest_frozen_page_id() != BLOB_VECTOR_INVALID_PAGE_ID) {
+    BlobVectorPageInfo &latest_frozen_page_info =
+        index_store_[header_->latest_frozen_page_id()];
+    page_info.set_next_page_id(latest_frozen_page_info.next_page_id());
+    latest_frozen_page_info.set_next_page_id(page_id);
+  } else {
+    page_info.set_next_page_id(page_id);
+  }
+  page_info.set_stamp(recycler_->stamp());
+  header_->set_latest_frozen_page_id(page_id);
+}
+
+void BlobVectorImpl::unfreeze_oldest_frozen_page() {
+  if (header_->latest_frozen_page_id() != BLOB_VECTOR_INVALID_PAGE_ID) {
+    BlobVectorPageInfo &latest_frozen_page_info =
+        index_store_[header_->latest_frozen_page_id()];
+    const uint32_t oldest_frozen_page_id =
+        latest_frozen_page_info.next_page_id();
+    BlobVectorPageInfo &oldest_frozen_page_info =
+        index_store_[oldest_frozen_page_id];
+    if (recycler_->check(oldest_frozen_page_info.stamp())) {
+      latest_frozen_page_info.set_next_page_id(
+          oldest_frozen_page_info.next_page_id());
+      oldest_frozen_page_info.set_next_page_id(header_->next_page_id());
+      header_->set_next_page_id(oldest_frozen_page_id);
+      if (oldest_frozen_page_id == header_->latest_frozen_page_id()) {
+        header_->set_latest_frozen_page_id(BLOB_VECTOR_INVALID_PAGE_ID);
+      }
+    }
   }
-  return builder << ", inter_thread_mutex = " << inter_thread_mutex_ << " }";
 }
 
 }  // namespace db

  Modified: lib/db/blob_vector.hpp (+377 -382)
===================================================================
--- lib/db/blob_vector.hpp    2012-12-12 14:29:12 +0900 (861ea53)
+++ lib/db/blob_vector.hpp    2012-12-13 18:21:10 +0900 (6026f09)
@@ -18,451 +18,391 @@
 #ifndef GRNXX_DB_BLOB_VECTOR_HPP
 #define GRNXX_DB_BLOB_VECTOR_HPP
 
-#include <array>
-
 #include "vector.hpp"
 
 namespace grnxx {
 namespace db {
 
-const uint64_t BLOB_VECTOR_SMALL_VALUE_LENGTH_MAX  = 7;
-
-const uint64_t BLOB_VECTOR_MEDIUM_VALUE_LENGTH_MIN =
-    BLOB_VECTOR_SMALL_VALUE_LENGTH_MAX + 1;
-const uint64_t BLOB_VECTOR_MEDIUM_VALUE_LENGTH_MAX = 64;
-
-const uint64_t BLOB_VECTOR_LARGE_VALUE_LENGTH_MIN  =
-    BLOB_VECTOR_MEDIUM_VALUE_LENGTH_MAX + 1;
-const uint64_t BLOB_VECTOR_LARGE_VALUE_LENGTH_MAX  = 65535;
-
-const uint64_t BLOB_VECTOR_HUGE_VALUE_LENGTH_MIN  =
-    BLOB_VECTOR_LARGE_VALUE_LENGTH_MAX + 1;
-
-// 8, 16, 32, and 64 bytes (4 size types).
-const uint8_t  BLOB_VECTOR_MEDIUM_VALUE_STORES_NUM   = 4;
-const uint8_t  BLOB_VECTOR_MEDIUM_VALUE_UNIT_SIZE_BITS = 3;
-
-const uint8_t  BLOB_VECTOR_LARGE_VALUE_UNIT_SIZE_BITS  = 4;
-const uint64_t BLOB_VECTOR_LARGE_VALUE_UNIT_SIZE       =
-    uint64_t(1) << BLOB_VECTOR_LARGE_VALUE_UNIT_SIZE_BITS;
-const uint8_t  BLOB_VECTOR_LARGE_VALUE_STORE_SIZE_BITS = 44;
-const uint64_t BLOB_VECTOR_LARGE_VALUE_STORE_SIZE      =
-    uint64_t(1) << BLOB_VECTOR_LARGE_VALUE_STORE_SIZE_BITS;
-const uint64_t BLOB_VECTOR_LARGE_VALUE_INVALID_OFFSET  =
-    BLOB_VECTOR_LARGE_VALUE_STORE_SIZE - BLOB_VECTOR_LARGE_VALUE_UNIT_SIZE;
-const uint8_t  BLOB_VECTOR_LARGE_VALUE_LISTS_NUM       = 16;
-
-// The settings of stores for medium values.
-const uint8_t  BLOB_VECTOR_MEDIUM_VALUE_STORE_PAGE_SIZE_BITS            = 18;
-const uint8_t  BLOB_VECTOR_MEDIUM_VALUE_STORE_TABLE_SIZE_BITS           = 12;
-const uint8_t  BLOB_VECTOR_MEDIUM_VALUE_STORE_SECONDARY_TABLE_SIZE_BITS = 16;
-
-const uint64_t BLOB_VECTOR_MEDIUM_VALUE_STORE_PAGE_SIZE            =
-    uint64_t(1) << BLOB_VECTOR_MEDIUM_VALUE_STORE_PAGE_SIZE_BITS;
-const uint64_t BLOB_VECTOR_MEDIUM_VALUE_STORE_TABLE_SIZE           =
-    uint64_t(1) << BLOB_VECTOR_MEDIUM_VALUE_STORE_TABLE_SIZE_BITS;
-const uint64_t BLOB_VECTOR_MEDIUM_VALUE_STORE_SECONDARY_TABLE_SIZE =
-    uint64_t(1) << BLOB_VECTOR_MEDIUM_VALUE_STORE_SECONDARY_TABLE_SIZE_BITS;
-
-typedef Vector<char, BLOB_VECTOR_MEDIUM_VALUE_STORE_PAGE_SIZE,
-                     BLOB_VECTOR_MEDIUM_VALUE_STORE_TABLE_SIZE,
-                     BLOB_VECTOR_MEDIUM_VALUE_STORE_SECONDARY_TABLE_SIZE>
-BlobVectorMediumValueStore;
-
-// The settings of the store for large values.
-const uint8_t  BLOB_VECTOR_LARGE_VALUE_STORE_PAGE_SIZE_BITS            = 19;
-const uint8_t  BLOB_VECTOR_LARGE_VALUE_STORE_TABLE_SIZE_BITS           = 12;
-const uint8_t  BLOB_VECTOR_LARGE_VALUE_STORE_SECONDARY_TABLE_SIZE_BITS = 16;
-
-const uint64_t BLOB_VECTOR_LARGE_VALUE_STORE_PAGE_SIZE            =
-    uint64_t(1) << BLOB_VECTOR_LARGE_VALUE_STORE_PAGE_SIZE_BITS;
-const uint64_t BLOB_VECTOR_LARGE_VALUE_STORE_TABLE_SIZE           =
-    uint64_t(1) << BLOB_VECTOR_LARGE_VALUE_STORE_TABLE_SIZE_BITS;
-const uint64_t BLOB_VECTOR_LARGE_VALUE_STORE_SECONDARY_TABLE_SIZE =
-    uint64_t(1) << BLOB_VECTOR_LARGE_VALUE_STORE_SECONDARY_TABLE_SIZE_BITS;
-
-typedef Vector<char, BLOB_VECTOR_LARGE_VALUE_STORE_PAGE_SIZE,
-                     BLOB_VECTOR_LARGE_VALUE_STORE_TABLE_SIZE,
-                     BLOB_VECTOR_LARGE_VALUE_STORE_SECONDARY_TABLE_SIZE>
-BlobVectorLargeValueStore;
+constexpr uint64_t BLOB_VECTOR_MAX_ID = uint64_t(1) << 40;
+
+constexpr uint32_t BLOB_VECTOR_INVALID_PAGE_ID = 0xFFFFFFFFU;
+
+constexpr uint64_t BLOB_VECTOR_SMALL_VALUE_MAX_LENGTH  = 7;
+
+constexpr uint64_t BLOB_VECTOR_MEDIUM_VALUE_MIN_LENGTH =
+    BLOB_VECTOR_SMALL_VALUE_MAX_LENGTH + 1;
+constexpr uint64_t BLOB_VECTOR_MEDIUM_VALUE_MAX_LENGTH = 65535;
+
+constexpr uint64_t BLOB_VECTOR_LARGE_VALUE_MIN_LENGTH  =
+    BLOB_VECTOR_MEDIUM_VALUE_MAX_LENGTH + 1;
+
+constexpr uint8_t  BLOB_VECTOR_UNIT_SIZE_BITS  = 3;
+constexpr uint64_t BLOB_VECTOR_UNIT_SIZE       =
+    uint64_t(1) << BLOB_VECTOR_UNIT_SIZE_BITS;
+
+constexpr uint8_t  BLOB_VECTOR_VALUE_STORE_PAGE_SIZE_BITS            = 19;
+constexpr uint8_t  BLOB_VECTOR_VALUE_STORE_TABLE_SIZE_BITS           = 12;
+constexpr uint8_t  BLOB_VECTOR_VALUE_STORE_SECONDARY_TABLE_SIZE_BITS = 16;
+
+constexpr uint64_t BLOB_VECTOR_VALUE_STORE_PAGE_SIZE            =
+    uint64_t(1) << BLOB_VECTOR_VALUE_STORE_PAGE_SIZE_BITS;
+constexpr uint64_t BLOB_VECTOR_VALUE_STORE_TABLE_SIZE           =
+    uint64_t(1) << BLOB_VECTOR_VALUE_STORE_TABLE_SIZE_BITS;
+constexpr uint64_t BLOB_VECTOR_VALUE_STORE_SECONDARY_TABLE_SIZE =
+    uint64_t(1) << BLOB_VECTOR_VALUE_STORE_SECONDARY_TABLE_SIZE_BITS;
+
+extern class BlobVectorCreate {} BLOB_VECTOR_CREATE;
+extern class BlobVectorOpen {} BLOB_VECTOR_OPEN;
 
 class BlobVectorHeader {
  public:
-  void initialize(uint32_t cells_block_id, Duration frozen_duration);
+  explicit BlobVectorHeader(uint32_t table_block_id);
 
-  uint32_t cells_block_id() const {
-    return cells_block_id_;
-  }
-  Duration frozen_duration() const {
-    return frozen_duration_;
+  uint32_t table_block_id() const {
+    return table_block_id_;
   }
-  uint32_t medium_value_store_block_ids(uint8_t store_id) const {
-    return medium_value_store_block_ids_[store_id];
+  uint32_t value_store_block_id() const {
+    return value_store_block_id_;
   }
-  uint64_t medium_value_store_next_offsets(uint8_t store_id) const {
-    return medium_value_store_next_offsets_[store_id];
+  uint32_t index_store_block_id() const {
+    return index_store_block_id_;
   }
-  uint32_t large_value_store_block_id() const {
-    return large_value_store_block_id_;
+  uint32_t next_page_id() const {
+    return next_page_id_;
   }
-  uint64_t rearmost_large_value_offset() const {
-    return rearmost_large_value_offset_;
+  uint64_t next_value_offset() const {
+    return next_value_offset_;
   }
-  uint64_t latest_frozen_large_value_offset() const {
-    return latest_frozen_large_value_offset_;
+  uint32_t latest_frozen_page_id() const {
+    return latest_frozen_page_id_;
   }
-  uint64_t oldest_idle_large_value_offsets(uint8_t list_id) const {
-    return oldest_idle_large_value_offsets_[list_id];
+  uint32_t latest_large_value_block_id() const {
+    return latest_large_value_block_id_;
   }
 
-  void set_medium_value_store_block_ids(uint8_t store_id, uint32_t value) {
-    medium_value_store_block_ids_[store_id] = value;
+  void set_value_store_block_id(uint32_t value) {
+    value_store_block_id_ = value;
   }
-  void set_medium_value_store_next_offsets(uint8_t store_id, uint64_t value) {
-    medium_value_store_next_offsets_[store_id] = value;
+  void set_index_store_block_id(uint32_t value) {
+    index_store_block_id_ = value;
   }
-  void set_large_value_store_block_id(uint32_t value) {
-    large_value_store_block_id_ = value;
+  void set_next_page_id(uint32_t value) {
+    next_page_id_ = value;
   }
-  void set_rearmost_large_value_offset(uint64_t value) {
-    rearmost_large_value_offset_ = value;
+  void set_next_value_offset(uint64_t value) {
+    next_value_offset_ = value;
   }
-  void set_latest_frozen_large_value_offset(uint64_t value) {
-    latest_frozen_large_value_offset_ = value;
+  void set_latest_frozen_page_id(uint32_t value) {
+    latest_frozen_page_id_ = value;
   }
-  void set_oldest_idle_large_value_offsets(uint8_t list_id, uint64_t value) {
-    oldest_idle_large_value_offsets_[list_id] = value;
+  void set_latest_large_value_block_id(uint32_t value) {
+    latest_large_value_block_id_ = value;
   }
 
   Mutex *mutable_inter_process_mutex() {
     return &inter_process_mutex_;
   }
-  Mutex *mutable_medium_value_store_mutex() {
-    return &medium_value_store_mutex_;
-  }
-  Mutex *mutable_large_value_store_mutex() {
-    return &large_value_store_mutex_;
-  }
 
   StringBuilder &write_to(StringBuilder &builder) const;
 
  private:
-  uint32_t cells_block_id_;
-  Duration frozen_duration_;
-  uint32_t medium_value_store_block_ids_[BLOB_VECTOR_MEDIUM_VALUE_STORES_NUM];
-  uint64_t medium_value_store_next_offsets_[BLOB_VECTOR_MEDIUM_VALUE_STORES_NUM];
-  uint32_t large_value_store_block_id_;
-  uint64_t rearmost_large_value_offset_;
-  uint64_t latest_frozen_large_value_offset_;
-  uint64_t oldest_idle_large_value_offsets_[BLOB_VECTOR_LARGE_VALUE_LISTS_NUM];
+  uint32_t table_block_id_;
+  uint32_t value_store_block_id_;
+  uint32_t index_store_block_id_;
+  uint32_t next_page_id_;
+  uint64_t next_value_offset_;
+  uint32_t latest_frozen_page_id_;
+  uint32_t latest_large_value_block_id_;
   Mutex inter_process_mutex_;
-  Mutex medium_value_store_mutex_;
-  Mutex large_value_store_mutex_;
 };
 
-enum BlobVectorLargeValueType : uint8_t {
-  BLOB_VECTOR_ACTIVE_VALUE  = 0x00,
-  BLOB_VECTOR_FROZEN_VALUE  = 0x01,
-  BLOB_VECTOR_IDLE_VALUE    = 0x02
-};
+inline StringBuilder &operator<<(StringBuilder &builder,
+                                 const BlobVectorHeader &header) {
+  return header.write_to(builder);
+}
 
-class BlobVectorLargeValueFlagsIdentifier;
-typedef FlagsImpl<BlobVectorLargeValueFlagsIdentifier, uint8_t>
-    BlobVectorLargeValueFlags;
+enum BlobVectorValueType : uint8_t {
+  BLOB_VECTOR_NULL   = 0x00,
+  BLOB_VECTOR_SMALL  = 0x10,
+  BLOB_VECTOR_MEDIUM = 0x20,
+  BLOB_VECTOR_LARGE  = 0x30
+};
 
-const BlobVectorLargeValueFlags BLOB_VECTOR_LARGE_VALUE_HAS_NEXT =
-    BlobVectorLargeValueFlags::define(0x01);
-const BlobVectorLargeValueFlags BLOB_VECTOR_LARGE_VALUE_HAS_PREV =
-    BlobVectorLargeValueFlags::define(0x02);
+constexpr uint8_t BLOB_VECTOR_TYPE_MASK = 0x30;
 
-class BlobVectorLargeValueHeader {
+class BlobVectorPageInfo {
  public:
-  void initialize(BlobVectorLargeValueType type,
-                  BlobVectorLargeValueFlags flags,
-                  uint64_t capacity,
-                  uint64_t prev_capacity) {
-    set_type(type);
-    set_flags(flags);
-    set_capacity(capacity);
-    set_prev_capacity(prev_capacity);
-    next_offset_high_ = 0;
-    prev_offset_high_ = 0;
-    next_offset_low_ = 0;
-    prev_offset_low_ = 0;
-  }
+  BlobVectorPageInfo()
+    : next_page_id_(BLOB_VECTOR_INVALID_PAGE_ID), stamp_(0), reserved_(0) {}
 
-  void *value() {
-    return this + 1;
-  }
-
-  BlobVectorLargeValueType type() const {
-    return type_;
-  }
-  BlobVectorLargeValueFlags flags() const {
-    return flags_;
-  }
-  uint64_t capacity() const {
-    return static_cast<uint64_t>(capacity_)
-         << BLOB_VECTOR_LARGE_VALUE_UNIT_SIZE_BITS;
+  uint32_t next_page_id() const {
+    return next_page_id_;
   }
-  uint64_t prev_capacity() const {
-    return static_cast<uint64_t>(prev_capacity_)
-         << BLOB_VECTOR_LARGE_VALUE_UNIT_SIZE_BITS;
+  uint32_t num_values() const {
+    return num_values_;
   }
-  uint64_t next_offset() const {
-    return ((static_cast<uint64_t>(next_offset_high_) << 32) |
-            next_offset_low_) << BLOB_VECTOR_LARGE_VALUE_UNIT_SIZE_BITS;
-  }
-  uint64_t prev_offset() const {
-    return ((static_cast<uint64_t>(prev_offset_high_) << 32) |
-            prev_offset_low_) << BLOB_VECTOR_LARGE_VALUE_UNIT_SIZE_BITS;
-  }
-  uint16_t frozen_stamp() const {
-    return static_cast<uint16_t>(frozen_stamp_);
+  uint16_t stamp() const {
+    return reserved_;
   }
 
-  void set_type(BlobVectorLargeValueType value) {
-    type_ = value;
-  }
-  void set_flags(BlobVectorLargeValueFlags value) {
-    flags_ = value;
-  }
-  void set_capacity(uint64_t value) {
-    capacity_ = static_cast<uint16_t>(
-        value >> BLOB_VECTOR_LARGE_VALUE_UNIT_SIZE_BITS);
-  }
-  void set_prev_capacity(uint64_t value) {
-    prev_capacity_ = static_cast<uint16_t>(
-        value >> BLOB_VECTOR_LARGE_VALUE_UNIT_SIZE_BITS);
+  void set_next_page_id(uint32_t value) {
+    next_page_id_ = value;
   }
-  void set_next_offset(uint64_t value) {
-    value >>= BLOB_VECTOR_LARGE_VALUE_UNIT_SIZE_BITS;
-    next_offset_high_ = static_cast<uint8_t>(value >> 32);
-    next_offset_low_ = static_cast<uint32_t>(value);
+  void set_num_values(uint32_t value) {
+    num_values_ = value;
   }
-  void set_prev_offset(uint64_t value) {
-    value >>= BLOB_VECTOR_LARGE_VALUE_UNIT_SIZE_BITS;
-    prev_offset_high_ = static_cast<uint8_t>(value >> 32);
-    prev_offset_low_ = static_cast<uint32_t>(value);
+  void set_stamp(uint16_t value) {
+    stamp_ = value;
   }
-  void set_frozen_stamp(uint16_t value) {
-    frozen_stamp_ = value;
-  }
-
-  StringBuilder &write_to(StringBuilder &builder) const;
 
  private:
-  BlobVectorLargeValueType type_;
-  BlobVectorLargeValueFlags flags_;
-  uint16_t capacity_;
-  uint16_t prev_capacity_;
-  uint8_t next_offset_high_;
-  uint8_t prev_offset_high_;
-  uint32_t next_offset_low_;
   union {
-    uint32_t frozen_stamp_;
-    uint32_t prev_offset_low_;
+    uint32_t next_page_id_;
+    uint32_t num_values_;
   };
+  uint16_t stamp_;
+  uint16_t reserved_;
 };
 
-enum BlobVectorValueType : uint8_t {
-  BLOB_VECTOR_SMALL_VALUE  = 0x00,
-  BLOB_VECTOR_MEDIUM_VALUE = 0x01,
-  BLOB_VECTOR_LARGE_VALUE  = 0x02,
-  BLOB_VECTOR_HUGE_VALUE   = 0x03
-};
-
-const uint8_t BLOB_VECTOR_VALUE_TYPE_MASK = 0x03;
-
-union BlobVectorCellFlags {
-  uint8_t flags;
-  BlobVectorValueType value_type;
-};
-
-class BlobVectorSmallValueCell {
+class BlobVectorValueHeader {
  public:
-  BlobVectorSmallValueCell(const void *ptr, uint64_t length)
-    : flags_and_length_(BLOB_VECTOR_SMALL_VALUE |
-                        (static_cast<uint8_t>(length) << 5)),
-      value_() {
-    std::memcpy(value_, ptr, length);
+  uint64_t length() const {
+    return length_;
+  }
+  uint32_t next_value_block_id() const {
+    return next_value_block_id_;
+  }
+  uint32_t prev_value_block_id() const {
+    return prev_value_block_id_;
   }
 
-  uint64_t length() const {
-    return flags_and_length_ >> 5;
+  void set_length(uint64_t value) {
+    length_ = value;
   }
-  const void *value() const {
-    return value_;
+  void set_next_value_block_id(uint32_t value) {
+    next_value_block_id_ = value;
+  }
+  void set_prev_value_block_id(uint32_t value) {
+    prev_value_block_id_ = value;
   }
 
  private:
-  uint8_t flags_and_length_;
-  uint8_t value_[7];
+  uint64_t length_;
+  uint32_t next_value_block_id_;
+  uint32_t prev_value_block_id_;
 };
 
-class BlobVectorMediumValueCell {
+const uint8_t BLOB_VECTOR_CELL_FLAGS_MASK = 0xF0;
+
+class BlobVectorCell {
  public:
-  BlobVectorMediumValueCell(uint8_t store_id, uint64_t offset, uint64_t length)
-    : flags_(BLOB_VECTOR_MEDIUM_VALUE),
-      store_id_(store_id),
-      length_(static_cast<uint8_t>(length)),
-      offset_high_(static_cast<uint8_t>(
-          offset >> (32 + store_id + BLOB_VECTOR_MEDIUM_VALUE_UNIT_SIZE_BITS))),
-      offset_low_(static_cast<uint32_t>(
-          offset >> (store_id + BLOB_VECTOR_MEDIUM_VALUE_UNIT_SIZE_BITS))) {}
+  BlobVectorCell() = default;
+  explicit BlobVectorCell(std::nullptr_t) : qword_(0) {}
 
-  uint8_t store_id() const {
-    return store_id_;
+  static BlobVectorCell null_value() {
+    return BlobVectorCell(nullptr);
   }
-  uint64_t capacity() const {
-    return uint64_t(8) << store_id_;
+  static BlobVectorCell small_value(uint64_t length) {
+    BlobVectorCell cell(nullptr);
+    cell.bytes_[0] = BLOB_VECTOR_SMALL | static_cast<uint8_t>(length);
+    return cell;
   }
-  uint64_t length() const {
-    return length_;
+  static BlobVectorCell medium_value(uint64_t offset, uint64_t length) {
+    BlobVectorCell cell;
+    cell.bytes_[0] = BLOB_VECTOR_MEDIUM | static_cast<uint8_t>(offset >> 40);
+    cell.bytes_[1] = static_cast<uint8_t>(offset >> 32);
+    cell.words_[1] = static_cast<uint16_t>(length);
+    cell.dwords_[1] = static_cast<uint32_t>(offset);
+    return cell;
   }
-  uint64_t offset() const {
-    return ((static_cast<uint64_t>(offset_high_) << 32) | offset_low_)
-        << (store_id_ + BLOB_VECTOR_MEDIUM_VALUE_UNIT_SIZE_BITS);
+  static BlobVectorCell large_value(uint32_t block_id) {
+    BlobVectorCell cell(nullptr);
+    cell.bytes_[0] = BLOB_VECTOR_LARGE;
+    cell.dwords_[1] = block_id;
+    return cell;
   }
 
- private:
-  uint8_t flags_;
-  uint8_t store_id_;
-  uint8_t length_;
-  uint8_t offset_high_;
-  uint32_t offset_low_;
-};
+  BlobVectorValueType type() const {
+    Flags flags;
+    flags.byte = flags_.byte & BLOB_VECTOR_TYPE_MASK;
+    return flags.type;
+  }
 
-class BlobVectorLargeValueCell {
- public:
-  BlobVectorLargeValueCell(uint64_t offset, uint64_t length)
-    : flags_(BLOB_VECTOR_LARGE_VALUE),
-      offset_high_(static_cast<uint8_t>(offset >> 32)),
-      length_(static_cast<uint16_t>(length)),
-      offset_low_(static_cast<uint32_t>(offset)) {}
+  // Accessors to small values.
+  uint64_t small_length() const {
+    return bytes_[0] & ~BLOB_VECTOR_CELL_FLAGS_MASK;
+  }
+  const void *value() const {
+    return &bytes_[1];
+  }
+  void *value() {
+    return &bytes_[1];
+  }
 
-  uint64_t length() const {
-    return length_;
+  // Accessors to medium values.
+  uint64_t medium_length() const {
+    return words_[1];
   }
   uint64_t offset() const {
-    return (static_cast<uint64_t>(offset_high_) << 32) | offset_low_;
+    return (static_cast<uint64_t>(bytes_[0] &
+                                  ~BLOB_VECTOR_CELL_FLAGS_MASK) << 40) |
+           (static_cast<uint64_t>(bytes_[1]) << 32) | dwords_[1];
+  }
+
+  // Accessors to large values.
+  uint32_t block_id() const {
+    return dwords_[1];
   }
 
  private:
-  uint8_t flags_;
-  uint8_t offset_high_;
-  uint16_t length_;
-  uint32_t offset_low_;
+  union Flags {
+    uint8_t byte;
+    BlobVectorValueType type;
+  };
+
+  union {
+    Flags flags_;
+    uint8_t bytes_[8];
+    uint16_t words_[4];
+    uint32_t dwords_[2];
+    uint64_t qword_;
+  };
 };
 
-class BlobVectorHugeValueCell {
+static_assert(sizeof(BlobVectorCell) == sizeof(uint64_t),
+              "sizeof(BlobVectorCell) != sizeof(uint64_t)");
+
+class Blob {
  public:
-  explicit BlobVectorHugeValueCell(uint32_t block_id)
-    : flags_(BLOB_VECTOR_HUGE_VALUE), reserved_(), block_id_(block_id) {
-    std::memset(reserved_, 0, sizeof(reserved_));
+  Blob() : address_(nullptr), length_(0), cell_() {}
+  explicit Blob(std::nullptr_t) : address_(nullptr), length_(0), cell_() {}
+  Blob(const void *address, uint64_t length)
+    : address_(address), length_(length), cell_() {}
+  explicit Blob(BlobVectorCell small_value_cell)
+    : address_(), length_(), cell_(small_value_cell) {
+    address_ = cell_.value();
+    length_ = cell_.small_length();
+  }
+
+  // Note: address_ refers to the own value if it is small.
+  Blob(const Blob &rhs) : address_(), length_(rhs.length_), cell_(rhs.cell_) {
+    if (rhs.address() == rhs.cell_.value()) {
+      address_ = cell_.value();
+    } else {
+      address_ = rhs.address_;
+    }
+  }
+  Blob &operator=(const Blob &rhs) {
+    length_ = rhs.length_;
+    cell_ = rhs.cell_;
+    if (rhs.address() == rhs.cell_.value()) {
+      address_ = cell_.value();
+    } else {
+      address_ = rhs.address_;
+    }
+    return *this;
   }
 
-  uint32_t block_id() const {
-    return block_id_;
+  Blob &operator=(std::nullptr_t) {
+    return *this = Blob(nullptr);
+  }
+
+  explicit operator bool() const {
+    return static_cast<bool>(address_);
+  }
+
+  const void *address() const {
+    return address_;
+  }
+  uint64_t length() const {
+    return length_;
+  }
+
+  void set_address(const void *value) {
+    address_ = value;
+  }
+  void set_length(uint64_t value) {
+    length_ = value;
   }
 
  private:
-  uint8_t flags_;
-  uint8_t reserved_[3];
-  uint32_t block_id_;
+  const void *address_;
+  uint64_t length_;
+  BlobVectorCell cell_;
 };
 
-class BlobVectorCell {
+class BlobVector;
+
+class BlobRef {
  public:
-  BlobVectorCell() : cell_(0) {}
-  ~BlobVectorCell() {}
+  BlobRef(BlobVector *vector, uint64_t id) : vector_(*vector), id_(id) {}
 
-  BlobVectorCell(const BlobVectorCell &rhs) : cell_(rhs.cell_) {}
-  BlobVectorCell &operator=(const BlobVectorCell &rhs) {
-    cell_ = rhs.cell_;
-    return *this;
-  }
-  BlobVectorCell &operator=(const BlobVectorSmallValueCell &rhs) {
-    small_value_cell_ = rhs;
-    return *this;
-  }
-  BlobVectorCell &operator=(const BlobVectorMediumValueCell &rhs) {
-    medium_value_cell_ = rhs;
-    return *this;
+  operator Blob() const {
+    return get();
   }
-  BlobVectorCell &operator=(const BlobVectorLargeValueCell &rhs) {
-    large_value_cell_ = rhs;
+
+  BlobRef &operator=(std::nullptr_t) {
+    set(nullptr);
     return *this;
   }
-  BlobVectorCell &operator=(const BlobVectorHugeValueCell &rhs) {
-    huge_value_cell_ = rhs;
+  BlobRef &operator=(const Blob &value) {
+    set(value);
     return *this;
   }
 
-  BlobVectorValueType value_type() const {
-    BlobVectorCellFlags clone = flags_;
-    clone.flags &= BLOB_VECTOR_VALUE_TYPE_MASK;
-    return clone.value_type;
-  }
-
-  const BlobVectorSmallValueCell &small_value_cell() const {
-    return small_value_cell_;
+  Blob get() const;
+  void set(std::nullptr_t) {
+    set(Blob(nullptr));
   }
-  const BlobVectorMediumValueCell &medium_value_cell() const {
-    return medium_value_cell_;
+  void set(const Blob &value);
+  void set(const void *ptr, uint64_t length) {
+    set(Blob(ptr, length));
   }
-  const BlobVectorLargeValueCell &large_value_cell() const {
-    return large_value_cell_;
+
+  void append(const Blob &value);
+  void append(const void *ptr, uint64_t length) {
+    append(Blob(ptr, length));
   }
-  const BlobVectorHugeValueCell &huge_value_cell() const {
-    return huge_value_cell_;
+  void prepend(const Blob &value);
+  void prepend(const void *ptr, uint64_t length) {
+    prepend(Blob(ptr, length));
   }
 
-  StringBuilder &write_to(StringBuilder &builder) const;
-
  private:
-  union {
-    uint64_t cell_;
-    BlobVectorCellFlags flags_;
-    BlobVectorSmallValueCell small_value_cell_;
-    BlobVectorMediumValueCell medium_value_cell_;
-    BlobVectorLargeValueCell large_value_cell_;
-    BlobVectorHugeValueCell huge_value_cell_;
-  };
+  BlobVector &vector_;
+  uint64_t id_;
 };
 
-class BlobVector {
- public:
-  BlobVector();
-  ~BlobVector();
+typedef Vector<BlobVectorCell> BlobVectorTable;
 
-  BlobVector(BlobVector &&rhs);
-  BlobVector &operator=(BlobVector &&rhs);
+typedef Vector<char, BLOB_VECTOR_VALUE_STORE_PAGE_SIZE,
+                     BLOB_VECTOR_VALUE_STORE_TABLE_SIZE,
+                     BLOB_VECTOR_VALUE_STORE_SECONDARY_TABLE_SIZE>
+BlobVectorValueStore;
 
-  bool is_open() const {
-    return static_cast<bool>(pool_);
-  }
+typedef Vector<BlobVectorPageInfo,
+               BLOB_VECTOR_VALUE_STORE_TABLE_SIZE,
+               BLOB_VECTOR_VALUE_STORE_SECONDARY_TABLE_SIZE>
+BlobVectorIndexStore;
 
-  void create(io::Pool pool);
-  void open(io::Pool pool, uint32_t block_id);
-  void close();
+class BlobVectorImpl {
+ public:
+  static std::unique_ptr<BlobVectorImpl> create(io::Pool pool);
+  static std::unique_ptr<BlobVectorImpl> open(io::Pool pool,
+                                              uint32_t block_id);
 
-  const void *get_value_address(uint64_t id, uint64_t *length = nullptr);
-  void set_value(uint64_t id, const void *ptr, uint64_t length);
+  Blob get_value(uint64_t id) {
+    return get_value(table_[id]);
+  }
+  void set_value(uint64_t id, const Blob &value);
 
-  // TODO
-//  void append(uint64_t id, const void *ptr, uint64_t length);
-//  void prepend(uint64_t id, const void *ptr, uint64_t length);
+  void append(uint64_t id, const Blob &value);
+  void prepend(uint64_t id, const Blob &value);
 
   uint32_t block_id() const {
-    return is_open() ? block_info_->id() : io::BLOCK_INVALID_ID;
-  }
-  uint64_t id_max() const {
-    return cells_.max_id();
+    return block_info_->id();
   }
 
-  void swap(BlobVector &rhs);
-
   StringBuilder &write_to(StringBuilder &builder) const;
 
   static void unlink(io::Pool pool, uint32_t block_id);
@@ -472,80 +412,135 @@ class BlobVector {
   const io::BlockInfo *block_info_;
   BlobVectorHeader *header_;
   Recycler *recycler_;
-  Vector<BlobVectorCell> cells_;
-  std::array<BlobVectorMediumValueStore,
-             BLOB_VECTOR_MEDIUM_VALUE_STORES_NUM> medium_value_stores_;
-  BlobVectorLargeValueStore large_value_store_;
+  BlobVectorTable table_;
+  BlobVectorValueStore value_store_;
+  BlobVectorIndexStore index_store_;
   Mutex inter_thread_mutex_;
 
+  BlobVectorImpl();
+
   void create_vector(io::Pool pool);
   void open_vector(io::Pool pool, uint32_t block_id);
 
-  BlobVectorSmallValueCell create_small_value_cell(
-      const void *ptr, uint64_t length);
-  BlobVectorMediumValueCell create_medium_value_cell(
-      const void *ptr, uint64_t length);
-  BlobVectorLargeValueCell create_large_value_cell(
-      const void *ptr, uint64_t length);
-  BlobVectorHugeValueCell create_huge_value_cell(
-      const void *ptr, uint64_t length);
+  Blob get_value(BlobVectorCell cell);
+
+  inline BlobVectorCell create_value(const Blob &value);
+  inline BlobVectorCell join_values(const Blob &lhs, const Blob &rhs);
+
+  inline void *create_small_value(uint64_t length, BlobVectorCell *cell);
+  inline void *create_medium_value(uint64_t length, BlobVectorCell *cell);
+  inline void *create_large_value(uint64_t length, BlobVectorCell *cell);
 
   void free_value(BlobVectorCell cell);
 
-  void open_medium_value_store(uint8_t store_id);
-  void open_large_value_store();
+  void register_large_value(uint32_t block_id,
+                            BlobVectorValueHeader *value_header);
+  void unregister_large_value(uint32_t block_id,
+                              BlobVectorValueHeader *value_header);
+
+  void freeze_page(uint32_t page_id);
+  void unfreeze_oldest_frozen_page();
+
+  Mutex *mutable_inter_thread_mutex() {
+    return &inter_thread_mutex_;
+  }
+  Mutex *mutable_inter_process_mutex() {
+    return header_->mutable_inter_process_mutex();
+  }
+};
+
+inline StringBuilder &operator<<(StringBuilder &builder,
+                                 const BlobVectorImpl &vector) {
+  return vector.write_to(builder);
+}
+
+class BlobVector {
+ public:
+  BlobVector() = default;
+  BlobVector(const BlobVectorCreate &, io::Pool pool)
+    : impl_(BlobVectorImpl::create(pool)) {}
+  BlobVector(const BlobVectorOpen &, io::Pool pool, uint32_t block_id)
+    : impl_(BlobVectorImpl::open(pool, block_id)) {}
+
+  explicit operator bool() const {
+    return static_cast<bool>(impl_);
+  }
+
+  void create(io::Pool pool) {
+    *this = BlobVector(BLOB_VECTOR_CREATE, pool);
+  }
+  void open(io::Pool pool, uint32_t block_id) {
+    *this = BlobVector(BLOB_VECTOR_OPEN, pool, block_id);
+  }
+  void close() {
+    *this = BlobVector();
+  }
+
+  BlobRef operator[](uint64_t id) {
+    return BlobRef(this, id);
+  }
 
-  void unfreeze_frozen_large_values();
+  Blob get_value(uint64_t id) {
+    return impl_->get_value(id);
+  }
+  void set_value(uint64_t id, const Blob &value) {
+    impl_->set_value(id, value);
+  }
 
-  void divide_idle_large_value(uint64_t offset, uint64_t capacity);
-  void merge_idle_large_values(uint64_t offset);
-  void merge_idle_large_values(uint64_t offset, uint64_t next_offset);
+  void append(uint64_t id, const Blob &value) {
+    impl_->append(id, value);
+  }
+  void prepend(uint64_t id, const Blob &value) {
+    impl_->prepend(id, value);
+  }
 
-  void register_idle_large_value(uint64_t offset);
-  void unregister_idle_large_value(uint64_t offset);
+  uint32_t block_id() const {
+    return impl_->block_id();
+  }
 
-  uint8_t get_store_id(uint64_t capacity) {
-    return bit_scan_reverse(capacity - 1)
-        - (BLOB_VECTOR_MEDIUM_VALUE_UNIT_SIZE_BITS - 1);
+  void swap(BlobVector &rhs) {
+    impl_.swap(rhs.impl_);
   }
-  uint8_t get_list_id(uint64_t capacity) {
-    return bit_scan_reverse(
-        (capacity >> BLOB_VECTOR_LARGE_VALUE_UNIT_SIZE_BITS) | 1);
+
+  StringBuilder &write_to(StringBuilder &builder) const {
+    return impl_ ? impl_->write_to(builder) : (builder << "n/a");
   }
 
-  BlobVectorLargeValueHeader *get_large_value_header(uint64_t offset) {
-    return reinterpret_cast<BlobVectorLargeValueHeader *>(
-        &large_value_store_[offset]);
+  static constexpr uint64_t max_id() {
+    return BLOB_VECTOR_MAX_ID;
   }
 
-  BlobVector(const BlobVector &);
-  BlobVector &operator=(const BlobVector &);
+  static void unlink(io::Pool pool, uint32_t block_id) {
+    BlobVectorImpl::unlink(pool, block_id);
+  }
+
+ private:
+  std::shared_ptr<BlobVectorImpl> impl_;
 };
 
 inline void swap(BlobVector &lhs, BlobVector &rhs) {
   lhs.swap(rhs);
 }
 
-StringBuilder &operator<<(StringBuilder &builder, BlobVectorLargeValueType type);
-StringBuilder &operator<<(StringBuilder &builder, BlobVectorLargeValueFlags flags);
-StringBuilder &operator<<(StringBuilder &builder, BlobVectorValueType type);
-StringBuilder &operator<<(StringBuilder &builder, BlobVectorCellFlags flags);
-
 inline StringBuilder &operator<<(StringBuilder &builder,
-                                 const BlobVectorHeader &header) {
-  return header.write_to(builder);
+                                 const BlobVector &vector) {
+  return vector.write_to(builder);
 }
-inline StringBuilder &operator<<(StringBuilder &builder,
-                                 const BlobVectorLargeValueHeader &header) {
-  return header.write_to(builder);
+
+inline Blob BlobRef::get() const {
+  return vector_.get_value(id_);
 }
-inline StringBuilder &operator<<(StringBuilder &builder,
-                                 const BlobVectorCell &cell) {
-  return cell.write_to(builder);
+
+inline void BlobRef::set(const Blob &value) {
+  vector_.set_value(id_, value);
 }
-inline StringBuilder &operator<<(StringBuilder &builder,
-                                 const BlobVector &vector) {
-  return vector.write_to(builder);
+
+inline void BlobRef::append(const Blob &value) {
+  vector_.append(id_, value);
+}
+
+inline void BlobRef::prepend(const Blob &value) {
+  vector_.prepend(id_, value);
 }
 
 }  // namespace db

  Modified: test/Makefile.am (+0 -4)
===================================================================
--- test/Makefile.am    2012-12-12 14:29:12 +0900 (19b5add)
+++ test/Makefile.am    2012-12-13 18:21:10 +0900 (248074b)
@@ -1,7 +1,6 @@
 AM_CXXFLAGS = -I../lib
 
 TESTS =				\
-	test_alpha_blob_vector	\
 	test_backtrace		\
 	test_db_array		\
 	test_db_blob_vector	\
@@ -29,9 +28,6 @@ TESTS =				\
 
 check_PROGRAMS = $(TESTS)
 
-test_alpha_blob_vector_SOURCES = test_alpha_blob_vector.cpp
-test_alpha_blob_vector_LDADD = ../lib/libgrnxx.la
-
 test_backtrace_SOURCES = test_backtrace.cpp
 test_backtrace_LDADD = ../lib/libgrnxx.la
 

  Deleted: test/test_alpha_blob_vector.cpp (+0 -360) 100644
===================================================================
--- test/test_alpha_blob_vector.cpp    2012-12-12 14:29:12 +0900 (4da48a1)
+++ /dev/null
@@ -1,360 +0,0 @@
-/*
-  Copyright (C) 2012  Brazil, Inc.
-
-  This library is free software; you can redistribute it and/or
-  modify it under the terms of the GNU Lesser General Public
-  License as published by the Free Software Foundation; either
-  version 2.1 of the License, or (at your option) any later version.
-
-  This library is distributed in the hope that it will be useful,
-  but WITHOUT ANY WARRANTY; without even the implied warranty of
-  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-  Lesser General Public License for more details.
-
-  You should have received a copy of the GNU Lesser General Public
-  License along with this library; if not, write to the Free Software
-  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
-*/
-#include <algorithm>
-#include <cassert>
-#include <random>
-#include <vector>
-
-#include "alpha/blob_vector.hpp"
-#include "logger.hpp"
-#include "time.hpp"
-
-void test_basics() {
-  grnxx::io::Pool::unlink_if_exists("temp.grn");
-
-  grnxx::io::Pool pool(grnxx::io::POOL_CREATE, "temp.grn");
-
-  grnxx::alpha::BlobVector vector(grnxx::alpha::BLOB_VECTOR_CREATE, pool);
-
-  GRNXX_NOTICE() << "blob_vector = " << vector;
-
-  assert(vector.block_id() == 0);
-  assert(!vector.get_value(0));
-
-  grnxx::alpha::BlobVector vector2;
-
-  vector.swap(vector2);
-  vector2.swap(vector);
-
-  assert(vector.block_id() == 0);
-
-  std::string values[5];
-  values[0].resize(0);
-  values[1].resize(1 << 2, 'S');
-  values[2].resize(1 << 4, 'M');
-  values[3].resize(1 << 12, 'M');
-  values[4].resize(1 << 20, 'L');
-
-  vector[0].set(values[0].c_str(), values[0].length());
-  vector[1000].set(values[1].c_str(), values[1].length());
-  vector[1000000].set(values[2].c_str(), values[2].length());
-  vector[1000000000].set(values[3].c_str(), values[3].length());
-  vector[1000000000000ULL].set(values[4].c_str(), values[4].length());
-
-  grnxx::alpha::Blob blob;
-
-  assert(blob = vector[0]);
-  assert(blob.length() == values[0].length());
-  assert(std::memcmp(blob.address(), values[0].c_str(), blob.length()) == 0);
-  assert(blob = vector[1000]);
-  assert(blob.length() == values[1].length());
-  assert(std::memcmp(blob.address(), values[1].c_str(), blob.length()) == 0);
-  assert(blob = vector[1000000]);
-  assert(blob.length() == values[2].length());
-  assert(std::memcmp(blob.address(), values[2].c_str(), blob.length()) == 0);
-  assert(blob = vector[1000000000]);
-  assert(blob.length() == values[3].length());
-  assert(std::memcmp(blob.address(), values[3].c_str(), blob.length()) == 0);
-  assert(blob = vector[1000000000000ULL]);
-  assert(blob.length() == values[4].length());
-  assert(std::memcmp(blob.address(), values[4].c_str(), blob.length()) == 0);
-
-  std::uint32_t block_id = vector.block_id();
-
-  vector.close();
-  pool.close();
-
-  pool.open(grnxx::io::POOL_OPEN, "temp.grn");
-  vector.open(pool, block_id);
-
-  GRNXX_NOTICE() << "blob_vector = " << vector;
-
-  assert(blob = vector[0]);
-  assert(blob.length() == values[0].length());
-  assert(std::memcmp(blob.address(), values[0].c_str(), blob.length()) == 0);
-  assert(blob = vector[1000]);
-  assert(blob.length() == values[1].length());
-  assert(std::memcmp(blob.address(), values[1].c_str(), blob.length()) == 0);
-  assert(blob = vector[1000000]);
-  assert(blob.length() == values[2].length());
-  assert(std::memcmp(blob.address(), values[2].c_str(), blob.length()) == 0);
-  assert(blob = vector[1000000000]);
-  assert(blob.length() == values[3].length());
-  assert(std::memcmp(blob.address(), values[3].c_str(), blob.length()) == 0);
-  assert(blob = vector[1000000000000ULL]);
-  assert(blob.length() == values[4].length());
-  assert(std::memcmp(blob.address(), values[4].c_str(), blob.length()) == 0);
-
-  vector[0] = grnxx::alpha::Blob("banana", 6);
-  blob = vector[0];
-  assert(blob);
-  assert(blob.length() == 6);
-  assert(std::memcmp(blob.address(), "banana", 6) == 0);
-
-  vector[0] = grnxx::alpha::Blob("xyz", 3);
-  assert(std::memcmp(blob.address(), "banana", 6) == 0);
-
-  grnxx::alpha::Blob blob2 = blob;
-  blob = nullptr;
-  assert(blob2);
-  assert(blob2.length() == 6);
-  assert(std::memcmp(blob2.address(), "banana", 6) == 0);
-
-  vector[0] = nullptr;
-  blob = vector[0];
-  assert(!blob);
-
-  vector[0].append("ABC", 3);
-  blob = vector[0];
-  assert(blob.length() == 3);
-  assert(std::memcmp(blob.address(), "ABC", 3) == 0);
-
-  vector[0].append("XYZ", 3);
-  blob = vector[0];
-  assert(blob.length() == 6);
-  assert(std::memcmp(blob.address(), "ABCXYZ", 6) == 0);
-
-  vector[0].prepend("123", 3);
-  blob = vector[0];
-  assert(blob.length() == 9);
-  assert(std::memcmp(blob.address(), "123ABCXYZ", 9) == 0);
-
-  vector.close();
-  pool.close();
-
-  grnxx::io::Pool::unlink_if_exists("temp.grn");
-}
-
-void test_sequential_access(int num_loops,
-                            std::size_t num_values,
-                            std::size_t min_value_length,
-                            std::size_t max_value_length) {
-  std::mt19937 random;
-
-  grnxx::io::PoolOptions options;
-  options.set_frozen_duration(grnxx::Duration(0));
-  grnxx::io::Pool pool(grnxx::io::POOL_TEMPORARY, "temp.grn", options);
-  grnxx::alpha::BlobVector vector(grnxx::alpha::BLOB_VECTOR_CREATE, pool);
-
-  for (int loop_id = 0; loop_id < num_loops; ++loop_id) {
-    std::vector<std::string> values(num_values);
-    for (std::size_t i = 0; i < values.size(); ++i) {
-      const size_t length = min_value_length
-          + (random() % (max_value_length - min_value_length + 1));
-      values[i].resize(length, '0' + (random() % 10));
-      if (length != 0) {
-        values[i][0] = 'a' + (random() % 26);
-        values[i][length - 1] = 'A' + (random() % 26);
-      }
-    }
-
-    for (std::size_t i = 0; i < values.size(); ++i) {
-      vector[i].set(values[i].c_str(), values[i].length());
-      grnxx::alpha::Blob blob = vector[i];
-      assert(blob);
-      assert(blob.length() == values[i].length());
-      assert(std::memcmp(blob.address(), values[i].c_str(),
-                         blob.length()) == 0);
-    }
-
-    for (std::size_t i = 0; i < values.size(); ++i) {
-      grnxx::alpha::Blob blob = vector[i];
-      assert(blob);
-      assert(blob.length() == values[i].length());
-      assert(std::memcmp(blob.address(), values[i].c_str(),
-                         blob.length()) == 0);
-    }
-
-    GRNXX_NOTICE() << "total_size = " << pool.header().total_size();
-  }
-}
-
-void test_random_access(int num_loops,
-                        std::size_t num_values,
-                        std::size_t min_value_length,
-                        std::size_t max_value_length) {
-  std::mt19937 random;
-
-  grnxx::io::PoolOptions options;
-  options.set_frozen_duration(grnxx::Duration(0));
-  grnxx::io::Pool pool(grnxx::io::POOL_TEMPORARY, "temp.grn", options);
-  grnxx::alpha::BlobVector vector(grnxx::alpha::BLOB_VECTOR_CREATE, pool);
-
-  std::vector<std::uint32_t> ids(num_values);
-  for (std::size_t i = 0; i < ids.size(); ++i) {
-    ids[i] = static_cast<std::uint32_t>(i);
-  }
-
-  for (int loop_id = 0; loop_id < num_loops; ++loop_id) {
-    std::random_shuffle(ids.begin(), ids.end());
-
-    std::vector<std::string> values(num_values);
-    for (std::size_t i = 0; i < values.size(); ++i) {
-      const size_t length = min_value_length
-          + (random() % (max_value_length - min_value_length + 1));
-      values[i].resize(length);
-      for (std::size_t j = 0; j < length; ++j) {
-        values[i][j] = 'A' + (random() % 26);
-      }
-    }
-
-    for (std::size_t i = 0; i < values.size(); ++i) {
-      vector[ids[i]].set(values[i].c_str(), values[i].length());
-      grnxx::alpha::Blob blob = vector[ids[i]];
-      assert(blob);
-      assert(blob.length() == values[i].length());
-      assert(std::memcmp(blob.address(), values[i].c_str(),
-                         blob.length()) == 0);
-    }
-
-    for (std::size_t i = 0; i < values.size(); ++i) {
-      grnxx::alpha::Blob blob = vector[ids[i]];
-      assert(blob);
-      assert(blob.length() == values[i].length());
-      assert(std::memcmp(blob.address(), values[i].c_str(),
-                         blob.length()) == 0);
-    }
-
-    GRNXX_NOTICE() << "total_size = " << pool.header().total_size();
-  }
-}
-
-void test_access_patterns(int num_loops,
-                          std::size_t num_values,
-                          std::size_t min_value_length,
-                          std::size_t max_value_length) {
-  GRNXX_NOTICE() << "num_loops = " << num_loops
-                 << ", num_values = " << num_values
-                 << ", min_value_length = " << min_value_length
-                 << ", max_value_length = " << max_value_length;
-
-  test_sequential_access(num_loops, num_values,
-                         min_value_length, max_value_length);
-  test_random_access(num_loops, num_values,
-                     min_value_length, max_value_length);
-}
-
-void test_small_values() {
-  test_access_patterns(3, 1 << 17,
-                       0,
-                       grnxx::alpha::BLOB_VECTOR_SMALL_VALUE_MAX_LENGTH);
-}
-
-void test_medium_values() {
-  test_access_patterns(3, 1 << 14,
-                       grnxx::alpha::BLOB_VECTOR_MEDIUM_VALUE_MIN_LENGTH,
-                       1 << 10);
-  test_access_patterns(3, 1 << 8,
-                       1 << 10,
-                       grnxx::alpha::BLOB_VECTOR_MEDIUM_VALUE_MAX_LENGTH);
-}
-
-void test_large_values() {
-  test_access_patterns(3, 1 << 6,
-                       grnxx::alpha::BLOB_VECTOR_LARGE_VALUE_MIN_LENGTH,
-                       grnxx::alpha::BLOB_VECTOR_LARGE_VALUE_MIN_LENGTH * 2);
-}
-
-void test_reuse(bool enable_reuse) {
-  const uint32_t NUM_LOOPS = 3;
-  const uint32_t NUM_VALUES = 1 << 14;
-  const uint32_t MAX_LENGTH = 1024;
-
-  GRNXX_NOTICE() << "enable_reuse = " << enable_reuse;
-
-  std::mt19937 random;
-
-  grnxx::io::PoolOptions options;
-  options.set_frozen_duration(
-      enable_reuse ? grnxx::Duration(0) : grnxx::Duration::days(1));
-  grnxx::io::Pool pool(grnxx::io::POOL_TEMPORARY, "temp.grn", options);
-  grnxx::alpha::BlobVector vector(grnxx::alpha::BLOB_VECTOR_CREATE, pool);
-
-  std::string value(MAX_LENGTH, 'X');
-
-  for (uint32_t loop_id = 0; loop_id < NUM_LOOPS; ++loop_id) {
-    for (uint32_t i = 0; i < NUM_VALUES; ++i) {
-      vector[0] = grnxx::alpha::Blob(&value[0], random() % MAX_LENGTH);
-    }
-    GRNXX_NOTICE() << "total_size = " << pool.header().total_size();
-  }
-}
-
-void test_mixed() {
-  const uint32_t NUM_LOOPS = 3;
-  const uint32_t NUM_VALUES = 1 << 11;
-  const uint32_t VECTOR_SIZE = 1 << 10;
-
-  std::mt19937 random;
-
-  grnxx::io::Pool pool(grnxx::io::POOL_TEMPORARY, "temp.grn");
-  grnxx::alpha::BlobVector vector(grnxx::alpha::BLOB_VECTOR_CREATE, pool);
-
-  std::string value(grnxx::alpha::BLOB_VECTOR_LARGE_VALUE_MIN_LENGTH, 'X');
-
-  for (uint32_t loop_id = 0; loop_id < NUM_LOOPS; ++loop_id) {
-    for (uint32_t i = 0; i < NUM_VALUES; ++i) {
-      const uint32_t value_id = random() % VECTOR_SIZE;
-      switch (random() & 3) {
-        case 0: {
-          vector[value_id] = nullptr;
-          break;
-        }
-        case 1: {
-          const uint32_t value_length =
-              random() % (grnxx::alpha::BLOB_VECTOR_SMALL_VALUE_MAX_LENGTH + 1);
-          vector[value_id] = grnxx::alpha::Blob(&value[0], value_length);
-          break;
-        }
-        case 2: {
-          const uint32_t value_length_range =
-              grnxx::alpha::BLOB_VECTOR_MEDIUM_VALUE_MAX_LENGTH
-              - grnxx::alpha::BLOB_VECTOR_MEDIUM_VALUE_MIN_LENGTH + 1;
-          const uint32_t value_length = (random() % value_length_range)
-              + grnxx::alpha::BLOB_VECTOR_MEDIUM_VALUE_MIN_LENGTH;
-          vector[value_id] = grnxx::alpha::Blob(&value[0], value_length);
-          break;
-        }
-        case 3: {
-          vector[value_id] = grnxx::alpha::Blob(&value[0], value.length());
-          break;
-        }
-      }
-    }
-    GRNXX_NOTICE() << "total_size = " << pool.header().total_size();
-  }
-}
-
-int main() {
-  grnxx::Logger::set_flags(grnxx::LOGGER_WITH_ALL |
-                           grnxx::LOGGER_ENABLE_COUT);
-  grnxx::Logger::set_max_level(grnxx::NOTICE_LOGGER);
-
-  test_basics();
-
-  test_small_values();
-  test_medium_values();
-  test_large_values();
-
-  test_reuse(false);
-  test_reuse(true);
-
-  test_mixed();
-
-  return 0;
-}

  Modified: test/test_db_blob_vector.cpp (+239 -184)
===================================================================
--- test/test_db_blob_vector.cpp    2012-12-12 14:29:12 +0900 (5939cd1)
+++ test/test_db_blob_vector.cpp    2012-12-13 18:21:10 +0900 (24d5538)
@@ -15,11 +15,10 @@
   License along with this library; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 */
+#include <algorithm>
 #include <cassert>
-#include <cstdlib>
 #include <random>
 #include <vector>
-#include <unordered_map>
 
 #include "db/blob_vector.hpp"
 #include "logger.hpp"
@@ -30,12 +29,12 @@ void test_basics() {
 
   grnxx::io::Pool pool(grnxx::io::POOL_CREATE, "temp.grn");
 
-  grnxx::db::BlobVector vector;
-  vector.create(pool);
+  grnxx::db::BlobVector vector(grnxx::db::BLOB_VECTOR_CREATE, pool);
 
   GRNXX_NOTICE() << "blob_vector = " << vector;
 
   assert(vector.block_id() == 0);
+  assert(!vector.get_value(0));
 
   grnxx::db::BlobVector vector2;
 
@@ -48,32 +47,32 @@ void test_basics() {
   values[0].resize(0);
   values[1].resize(1 << 2, 'S');
   values[2].resize(1 << 4, 'M');
-  values[3].resize(1 << 12, 'L');
-  values[4].resize(1 << 20, 'H');
-
-  vector.set_value(0, values[0].c_str(), values[0].length());
-  vector.set_value(1000, values[1].c_str(), values[1].length());
-  vector.set_value(1000000, values[2].c_str(), values[2].length());
-  vector.set_value(1000000000, values[3].c_str(), values[3].length());
-  vector.set_value(1000000000000ULL, values[4].c_str(), values[4].length());
-
-  std::uint64_t length = 0;
-
-  assert(std::memcmp(vector.get_value_address(0, &length),
-                     values[0].c_str(), values[0].length()) == 0);
-  assert(length == values[0].length());
-  assert(std::memcmp(vector.get_value_address(1000, &length),
-                     values[1].c_str(), values[1].length()) == 0);
-  assert(length == values[1].length());
-  assert(std::memcmp(vector.get_value_address(1000000, &length),
-                     values[2].c_str(), values[2].length()) == 0);
-  assert(length == values[2].length());
-  assert(std::memcmp(vector.get_value_address(1000000000, &length),
-                     values[3].c_str(), values[3].length()) == 0);
-  assert(length == values[3].length());
-  assert(std::memcmp(vector.get_value_address(1000000000000ULL, &length),
-                     values[4].c_str(), values[4].length()) == 0);
-  assert(length == values[4].length());
+  values[3].resize(1 << 12, 'M');
+  values[4].resize(1 << 20, 'L');
+
+  vector[0].set(values[0].c_str(), values[0].length());
+  vector[1000].set(values[1].c_str(), values[1].length());
+  vector[1000000].set(values[2].c_str(), values[2].length());
+  vector[1000000000].set(values[3].c_str(), values[3].length());
+  vector[1000000000000ULL].set(values[4].c_str(), values[4].length());
+
+  grnxx::db::Blob blob;
+
+  assert(blob = vector[0]);
+  assert(blob.length() == values[0].length());
+  assert(std::memcmp(blob.address(), values[0].c_str(), blob.length()) == 0);
+  assert(blob = vector[1000]);
+  assert(blob.length() == values[1].length());
+  assert(std::memcmp(blob.address(), values[1].c_str(), blob.length()) == 0);
+  assert(blob = vector[1000000]);
+  assert(blob.length() == values[2].length());
+  assert(std::memcmp(blob.address(), values[2].c_str(), blob.length()) == 0);
+  assert(blob = vector[1000000000]);
+  assert(blob.length() == values[3].length());
+  assert(std::memcmp(blob.address(), values[3].c_str(), blob.length()) == 0);
+  assert(blob = vector[1000000000000ULL]);
+  assert(blob.length() == values[4].length());
+  assert(std::memcmp(blob.address(), values[4].c_str(), blob.length()) == 0);
 
   std::uint32_t block_id = vector.block_id();
 
@@ -85,21 +84,55 @@ void test_basics() {
 
   GRNXX_NOTICE() << "blob_vector = " << vector;
 
-  assert(std::memcmp(vector.get_value_address(0, &length),
-                     values[0].c_str(), values[0].length()) == 0);
-  assert(length == values[0].length());
-  assert(std::memcmp(vector.get_value_address(1000, &length),
-                     values[1].c_str(), values[1].length()) == 0);
-  assert(length == values[1].length());
-  assert(std::memcmp(vector.get_value_address(1000000, &length),
-                     values[2].c_str(), values[2].length()) == 0);
-  assert(length == values[2].length());
-  assert(std::memcmp(vector.get_value_address(1000000000, &length),
-                     values[3].c_str(), values[3].length()) == 0);
-  assert(length == values[3].length());
-  assert(std::memcmp(vector.get_value_address(1000000000000ULL, &length),
-                     values[4].c_str(), values[4].length()) == 0);
-  assert(length == values[4].length());
+  assert(blob = vector[0]);
+  assert(blob.length() == values[0].length());
+  assert(std::memcmp(blob.address(), values[0].c_str(), blob.length()) == 0);
+  assert(blob = vector[1000]);
+  assert(blob.length() == values[1].length());
+  assert(std::memcmp(blob.address(), values[1].c_str(), blob.length()) == 0);
+  assert(blob = vector[1000000]);
+  assert(blob.length() == values[2].length());
+  assert(std::memcmp(blob.address(), values[2].c_str(), blob.length()) == 0);
+  assert(blob = vector[1000000000]);
+  assert(blob.length() == values[3].length());
+  assert(std::memcmp(blob.address(), values[3].c_str(), blob.length()) == 0);
+  assert(blob = vector[1000000000000ULL]);
+  assert(blob.length() == values[4].length());
+  assert(std::memcmp(blob.address(), values[4].c_str(), blob.length()) == 0);
+
+  vector[0] = grnxx::db::Blob("banana", 6);
+  blob = vector[0];
+  assert(blob);
+  assert(blob.length() == 6);
+  assert(std::memcmp(blob.address(), "banana", 6) == 0);
+
+  vector[0] = grnxx::db::Blob("xyz", 3);
+  assert(std::memcmp(blob.address(), "banana", 6) == 0);
+
+  grnxx::db::Blob blob2 = blob;
+  blob = nullptr;
+  assert(blob2);
+  assert(blob2.length() == 6);
+  assert(std::memcmp(blob2.address(), "banana", 6) == 0);
+
+  vector[0] = nullptr;
+  blob = vector[0];
+  assert(!blob);
+
+  vector[0].append("ABC", 3);
+  blob = vector[0];
+  assert(blob.length() == 3);
+  assert(std::memcmp(blob.address(), "ABC", 3) == 0);
+
+  vector[0].append("XYZ", 3);
+  blob = vector[0];
+  assert(blob.length() == 6);
+  assert(std::memcmp(blob.address(), "ABCXYZ", 6) == 0);
+
+  vector[0].prepend("123", 3);
+  blob = vector[0];
+  assert(blob.length() == 9);
+  assert(std::memcmp(blob.address(), "123ABCXYZ", 9) == 0);
 
   vector.close();
   pool.close();
@@ -107,180 +140,203 @@ void test_basics() {
   grnxx::io::Pool::unlink_if_exists("temp.grn");
 }
 
-void test_random_values(std::size_t num_values,
-                        std::size_t min_value_length,
-                        std::size_t max_value_length) {
+void test_sequential_access(int num_loops,
+                            std::size_t num_values,
+                            std::size_t min_value_length,
+                            std::size_t max_value_length) {
   std::mt19937 random;
 
-  std::vector<std::string> values(num_values);
-  for (std::size_t i = 0; i < values.size(); ++i) {
-    const size_t length = min_value_length
-        + (random() % (max_value_length - min_value_length + 1));
-    values[i].resize(length);
-    for (std::uint32_t j = 0; j < length; ++j) {
-      values[i][j] = 'A' + (random() % 26);
+  grnxx::io::PoolOptions options;
+  options.set_frozen_duration(grnxx::Duration(0));
+  grnxx::io::Pool pool(grnxx::io::POOL_TEMPORARY, "temp.grn", options);
+  grnxx::db::BlobVector vector(grnxx::db::BLOB_VECTOR_CREATE, pool);
+
+  for (int loop_id = 0; loop_id < num_loops; ++loop_id) {
+    std::vector<std::string> values(num_values);
+    for (std::size_t i = 0; i < values.size(); ++i) {
+      const size_t length = min_value_length
+          + (random() % (max_value_length - min_value_length + 1));
+      values[i].resize(length, '0' + (random() % 10));
+      if (length != 0) {
+        values[i][0] = 'a' + (random() % 26);
+        values[i][length - 1] = 'A' + (random() % 26);
+      }
     }
-  }
 
-  grnxx::io::Pool pool(grnxx::io::POOL_TEMPORARY, "temp.grn");
+    for (std::size_t i = 0; i < values.size(); ++i) {
+      vector[i].set(values[i].c_str(), values[i].length());
+      grnxx::db::Blob blob = vector[i];
+      assert(blob);
+      assert(blob.length() == values[i].length());
+      assert(std::memcmp(blob.address(), values[i].c_str(),
+                         blob.length()) == 0);
+    }
 
-  grnxx::db::BlobVector vector;
-  vector.create(pool);
+    for (std::size_t i = 0; i < values.size(); ++i) {
+      grnxx::db::Blob blob = vector[i];
+      assert(blob);
+      assert(blob.length() == values[i].length());
+      assert(std::memcmp(blob.address(), values[i].c_str(),
+                         blob.length()) == 0);
+    }
 
-  for (std::size_t i = 0; i < values.size(); ++i) {
-    vector.set_value(i, values[i].c_str(), values[i].length());
+    GRNXX_NOTICE() << "total_size = " << pool.header().total_size();
+  }
+}
 
-    std::uint64_t length;
-    const char *address =
-        static_cast<const char *>(vector.get_value_address(i, &length));
+void test_random_access(int num_loops,
+                        std::size_t num_values,
+                        std::size_t min_value_length,
+                        std::size_t max_value_length) {
+  std::mt19937 random;
 
-    assert(length == values[i].length());
-    assert(std::memcmp(address, values[i].c_str(), length) == 0);
+  grnxx::io::PoolOptions options;
+  options.set_frozen_duration(grnxx::Duration(0));
+  grnxx::io::Pool pool(grnxx::io::POOL_TEMPORARY, "temp.grn", options);
+  grnxx::db::BlobVector vector(grnxx::db::BLOB_VECTOR_CREATE, pool);
+
+  std::vector<std::uint32_t> ids(num_values);
+  for (std::size_t i = 0; i < ids.size(); ++i) {
+    ids[i] = static_cast<std::uint32_t>(i);
   }
 
-  for (std::size_t i = 0; i < values.size(); ++i) {
-    std::uint64_t length;
-    const char *address =
-        static_cast<const char *>(vector.get_value_address(i, &length));
+  for (int loop_id = 0; loop_id < num_loops; ++loop_id) {
+    std::random_shuffle(ids.begin(), ids.end());
+
+    std::vector<std::string> values(num_values);
+    for (std::size_t i = 0; i < values.size(); ++i) {
+      const size_t length = min_value_length
+          + (random() % (max_value_length - min_value_length + 1));
+      values[i].resize(length);
+      for (std::size_t j = 0; j < length; ++j) {
+        values[i][j] = 'A' + (random() % 26);
+      }
+    }
+
+    for (std::size_t i = 0; i < values.size(); ++i) {
+      vector[ids[i]].set(values[i].c_str(), values[i].length());
+      grnxx::db::Blob blob = vector[ids[i]];
+      assert(blob);
+      assert(blob.length() == values[i].length());
+      assert(std::memcmp(blob.address(), values[i].c_str(),
+                         blob.length()) == 0);
+    }
+
+    for (std::size_t i = 0; i < values.size(); ++i) {
+      grnxx::db::Blob blob = vector[ids[i]];
+      assert(blob);
+      assert(blob.length() == values[i].length());
+      assert(std::memcmp(blob.address(), values[i].c_str(),
+                         blob.length()) == 0);
+    }
 
-    assert(length == values[i].length());
-    assert(std::memcmp(address, values[i].c_str(), length) == 0);
+    GRNXX_NOTICE() << "total_size = " << pool.header().total_size();
   }
+}
 
-  GRNXX_NOTICE() << "pool = " << pool;
-  GRNXX_NOTICE() << "blob_vector = " << vector;
+void test_access_patterns(int num_loops,
+                          std::size_t num_values,
+                          std::size_t min_value_length,
+                          std::size_t max_value_length) {
+  GRNXX_NOTICE() << "num_loops = " << num_loops
+                 << ", num_values = " << num_values
+                 << ", min_value_length = " << min_value_length
+                 << ", max_value_length = " << max_value_length;
+
+  test_sequential_access(num_loops, num_values,
+                         min_value_length, max_value_length);
+  test_random_access(num_loops, num_values,
+                     min_value_length, max_value_length);
 }
 
 void test_small_values() {
-  test_random_values(1 << 20,
-                     0,
-                     grnxx::db::BLOB_VECTOR_SMALL_VALUE_LENGTH_MAX);
+  test_access_patterns(3, 1 << 17,
+                       0,
+                       grnxx::db::BLOB_VECTOR_SMALL_VALUE_MAX_LENGTH);
 }
 
 void test_medium_values() {
-  test_random_values(1 << 16,
-                     grnxx::db::BLOB_VECTOR_MEDIUM_VALUE_LENGTH_MIN,
-                     grnxx::db::BLOB_VECTOR_MEDIUM_VALUE_LENGTH_MAX);
+  test_access_patterns(3, 1 << 14,
+                       grnxx::db::BLOB_VECTOR_MEDIUM_VALUE_MIN_LENGTH,
+                       1 << 10);
+  test_access_patterns(3, 1 << 8,
+                       1 << 10,
+                       grnxx::db::BLOB_VECTOR_MEDIUM_VALUE_MAX_LENGTH);
 }
 
 void test_large_values() {
-  test_random_values(1 << 8,
-                     grnxx::db::BLOB_VECTOR_LARGE_VALUE_LENGTH_MIN,
-                     grnxx::db::BLOB_VECTOR_LARGE_VALUE_LENGTH_MAX);
+  test_access_patterns(3, 1 << 6,
+                       grnxx::db::BLOB_VECTOR_LARGE_VALUE_MIN_LENGTH,
+                       grnxx::db::BLOB_VECTOR_LARGE_VALUE_MIN_LENGTH * 2);
 }
 
-void test_huge_values() {
-  test_random_values(1 << 6,
-                     grnxx::db::BLOB_VECTOR_HUGE_VALUE_LENGTH_MIN,
-                     grnxx::db::BLOB_VECTOR_HUGE_VALUE_LENGTH_MIN * 4);
-}
+void test_reuse(bool enable_reuse) {
+  const uint32_t NUM_LOOPS = 3;
+  const uint32_t NUM_VALUES = 1 << 14;
+  const uint32_t MAX_LENGTH = 1024;
 
-void test_random_updates(grnxx::Duration frozen_duration) {
-  std::mt19937 random;
+  GRNXX_NOTICE() << "enable_reuse = " << enable_reuse;
 
-  std::unordered_map<std::uint64_t, std::string> map;
+  std::mt19937 random;
 
   grnxx::io::PoolOptions options;
-  options.set_frozen_duration(frozen_duration);
-
+  options.set_frozen_duration(
+      enable_reuse ? grnxx::Duration(0) : grnxx::Duration::days(1));
   grnxx::io::Pool pool(grnxx::io::POOL_TEMPORARY, "temp.grn", options);
+  grnxx::db::BlobVector vector(grnxx::db::BLOB_VECTOR_CREATE, pool);
 
-  grnxx::db::BlobVector vector;
-  vector.create(pool);
+  std::string value(MAX_LENGTH, 'X');
 
-  const std::uint8_t  LENGTH_BITS_MIN = 3;
-  const std::uint8_t  LENGTH_BITS_MAX = 10;
-  const std::uint32_t LOOP_COUNT = 1 << 16;
-  const std::uint32_t ID_MASK = (LOOP_COUNT >> 4) - 1;
-
-  std::string query;
-  for (std::uint32_t i = 0; i < LOOP_COUNT; ++i) {
-    const std::uint64_t id = random() & ID_MASK;
-
-    std::uint64_t length;
-    const char *address =
-        static_cast<const char *>(vector.get_value_address(id, &length));
-
-    auto it = map.find(id);
-    if (it == map.end()) {
-      assert(length == 0);
-    } else {
-      assert(length == it->second.length());
-      assert(std::memcmp(address, it->second.c_str(), length) == 0);
+  for (uint32_t loop_id = 0; loop_id < NUM_LOOPS; ++loop_id) {
+    for (uint32_t i = 0; i < NUM_VALUES; ++i) {
+      vector[0] = grnxx::db::Blob(&value[0], random() % MAX_LENGTH);
     }
-
-    const size_t query_length_bits = LENGTH_BITS_MIN
-        + (random() % (LENGTH_BITS_MAX - LENGTH_BITS_MIN + 1));
-    const size_t query_length = random() & ((1 << query_length_bits) - 1);
-    query.resize(query_length);
-    for (std::uint32_t j = 0; j < query_length; ++j) {
-      query[j] = 'A' + (random() % 26);
-    }
-
-    vector.set_value(id, query.c_str(), query.length());
-    map[id] = query;
+    GRNXX_NOTICE() << "total_size = " << pool.header().total_size();
   }
-
-  for (auto it = map.begin(); it != map.end(); ++it) {
-    const uint64_t key = it->first;
-    const std::string &value = it->second;
-
-    std::uint64_t length;
-    const char *address =
-        static_cast<const char *>(vector.get_value_address(key, &length));
-
-    assert(length == value.length());
-    assert(std::memcmp(address, value.c_str(), length) == 0);
-  }
-
-  GRNXX_NOTICE() << "pool = " << pool;
-  GRNXX_NOTICE() << "blob_vector = " << vector;
-}
-
-void test_rewrite() {
-  test_random_updates(grnxx::Duration::days(1));
 }
 
-void test_reuse() {
-  test_random_updates(grnxx::Duration(0));
-}
+void test_mixed() {
+  const uint32_t NUM_LOOPS = 3;
+  const uint32_t NUM_VALUES = 1 << 11;
+  const uint32_t VECTOR_SIZE = 1 << 10;
 
-void test_random() {
   std::mt19937 random;
 
-  std::vector<std::string> values(1 << 10);
-  for (std::size_t i = 0; i < values.size(); ++i) {
-    const std::uint32_t length_bits = 4 + (random() % 14);
-    const std::uint32_t length = random() & ((1 << length_bits) - 1);
-    values[i].resize(length);
-    for (std::uint32_t j = 0; j < length; ++j) {
-      values[i][j] = 'A' + (random() % 26);
-    }
-  }
-
   grnxx::io::Pool pool(grnxx::io::POOL_TEMPORARY, "temp.grn");
-
-  grnxx::db::BlobVector vector;
-  vector.create(pool);
-
-  for (std::size_t i = 0; i < values.size(); ++i) {
-    vector.set_value(i, values[i].c_str(), values[i].length());
-
-    std::uint64_t length;
-    const char *address =
-        static_cast<const char *>(vector.get_value_address(i, &length));
-
-    assert(length == values[i].length());
-    assert(std::memcmp(address, values[i].c_str(), length) == 0);
-  }
-
-  for (std::size_t i = 0; i < values.size(); ++i) {
-    std::uint64_t length;
-    const char *address =
-        static_cast<const char *>(vector.get_value_address(i, &length));
-
-    assert(length == values[i].length());
-    assert(std::memcmp(address, values[i].c_str(), length) == 0);
+  grnxx::db::BlobVector vector(grnxx::db::BLOB_VECTOR_CREATE, pool);
+
+  std::string value(grnxx::db::BLOB_VECTOR_LARGE_VALUE_MIN_LENGTH, 'X');
+
+  for (uint32_t loop_id = 0; loop_id < NUM_LOOPS; ++loop_id) {
+    for (uint32_t i = 0; i < NUM_VALUES; ++i) {
+      const uint32_t value_id = random() % VECTOR_SIZE;
+      switch (random() & 3) {
+        case 0: {
+          vector[value_id] = nullptr;
+          break;
+        }
+        case 1: {
+          const uint32_t value_length =
+              random() % (grnxx::db::BLOB_VECTOR_SMALL_VALUE_MAX_LENGTH + 1);
+          vector[value_id] = grnxx::db::Blob(&value[0], value_length);
+          break;
+        }
+        case 2: {
+          const uint32_t value_length_range =
+              grnxx::db::BLOB_VECTOR_MEDIUM_VALUE_MAX_LENGTH
+              - grnxx::db::BLOB_VECTOR_MEDIUM_VALUE_MIN_LENGTH + 1;
+          const uint32_t value_length = (random() % value_length_range)
+              + grnxx::db::BLOB_VECTOR_MEDIUM_VALUE_MIN_LENGTH;
+          vector[value_id] = grnxx::db::Blob(&value[0], value_length);
+          break;
+        }
+        case 3: {
+          vector[value_id] = grnxx::db::Blob(&value[0], value.length());
+          break;
+        }
+      }
+    }
+    GRNXX_NOTICE() << "total_size = " << pool.header().total_size();
   }
 }
 
@@ -294,12 +350,11 @@ int main() {
   test_small_values();
   test_medium_values();
   test_large_values();
-  test_huge_values();
 
-  test_rewrite();
-  test_reuse();
+  test_reuse(false);
+  test_reuse(true);
 
-  test_random();
+  test_mixed();
 
   return 0;
 }

• Previous message: [Groonga-commit] groonga/groonga.github.com [master] doc ja: fix description more precisely about range search by using index
• Next message: [Groonga-commit] groonga/groonga-query-log [master] SizedStatistics: use start_time(Time)#to_f for comparing start_time
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]