src/content/browser/indexed_db/indexed_db_leveldb_coding.cc

   1 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "content/browser/indexed_db/indexed_db_leveldb_coding.h"
   6
   7 #include <iterator>
   8 #include <limits>
   9
  10 #include "base/logging.h"
  11 #include "base/strings/string16.h"
  12 #include "base/strings/utf_string_conversions.h"
  13 #include "base/sys_byteorder.h"
  14 #include "content/common/indexed_db/indexed_db_key.h"
  15 #include "content/common/indexed_db/indexed_db_key_path.h"
  16
  17 // LevelDB Coding Scheme
  18 // =====================
  19 //
  20 // LevelDB stores key/value pairs. Keys and values are strings of bytes,
  21 // normally of type std::string.
  22 //
  23 // The keys in the backing store are variable-length tuples with different
  24 // types of fields. Each key in the backing store starts with a ternary
  25 // prefix: (database id, object store id, index id). For each, 0 is reserved
  26 // for metadata. See KeyPrefix::Decode() for details of the prefix coding.
  27 //
  28 // The prefix makes sure that data for a specific database, object store, and
  29 // index are grouped together. The locality is important for performance:
  30 // common operations should only need a minimal number of seek operations. For
  31 // example, all the metadata for a database is grouped together so that
  32 // reading that metadata only requires one seek.
  33 //
  34 // Each key type has a class (in square brackets below) which knows how to
  35 // encode, decode, and compare that key type.
  36 //
  37 // Strings (origins, names, etc) are encoded as UTF-16BE.
  38 //
  39 //
  40 // Global metadata
  41 // ---------------
  42 // The prefix is <0, 0, 0>, followed by a metadata type byte:
  43 //
  44 // <0, 0, 0, 0> => backing store schema version [SchemaVersionKey]
  45 // <0, 0, 0, 1> => maximum allocated database [MaxDatabaseIdKey]
  46 // <0, 0, 0, 2> => SerializedScriptValue version [DataVersionKey]
  47 // <0, 0, 0, 3>
  48 //   => Blob journal
  49 //     The format of the journal is: {database_id, blobKey}*.
  50 //     If the blobKey is kAllBlobsKey, the whole database should be deleted.
  51 //     [BlobJournalKey]
  52 // <0, 0, 0, 4> => Live blob journal; same format. [LiveBlobJournalKey]
  53 // <0, 0, 0, 100, database id>
  54 //   => Existence implies the database id is in the free list
  55 //      [DatabaseFreeListKey]
  56 // <0, 0, 0, 201, origin, database name> => Database id [DatabaseNameKey]
  57 //
  58 //
  59 // Database metadata: [DatabaseMetaDataKey]
  60 // ----------------------------------------
  61 // The prefix is <database id, 0, 0> followed by a metadata type byte:
  62 //
  63 // <database id, 0, 0, 0> => origin name
  64 // <database id, 0, 0, 1> => database name
  65 // <database id, 0, 0, 2> => IDB string version data (obsolete)
  66 // <database id, 0, 0, 3> => maximum allocated object store id
  67 // <database id, 0, 0, 4> => IDB integer version (var int)
  68 // <database id, 0, 0, 5> => blob key generator current number
  69 //
  70 //
  71 // Object store metadata: [ObjectStoreMetaDataKey]
  72 // -----------------------------------------------
  73 // The prefix is <database id, 0, 0>, followed by a type byte (50), then the
  74 // object store id (var int), then a metadata type byte.
  75 //
  76 // <database id, 0, 0, 50, object store id, 0> => object store name
  77 // <database id, 0, 0, 50, object store id, 1> => key path
  78 // <database id, 0, 0, 50, object store id, 2> => auto increment flag
  79 // <database id, 0, 0, 50, object store id, 3> => is evictable
  80 // <database id, 0, 0, 50, object store id, 4> => last "version" number
  81 // <database id, 0, 0, 50, object store id, 5> => maximum allocated index id
  82 // <database id, 0, 0, 50, object store id, 6> => has key path flag (obsolete)
  83 // <database id, 0, 0, 50, object store id, 7> => key generator current number
  84 //
  85 // The key path was originally just a string (#1) or null (identified by flag,
  86 // #6). To support null, string, or array the coding is now identified by the
  87 // leading bytes in #1 - see EncodeIDBKeyPath.
  88 //
  89 // The "version" field is used to weed out stale index data. Whenever new
  90 // object store data is inserted, it gets a new "version" number, and new
  91 // index data is written with this number. When the index is used for
  92 // look-ups, entries are validated against the "exists" entries, and records
  93 // with old "version" numbers are deleted when they are encountered in
  94 // GetPrimaryKeyViaIndex, IndexCursorImpl::LoadCurrentRow and
  95 // IndexKeyCursorImpl::LoadCurrentRow.
  96 //
  97 //
  98 // Index metadata: [IndexMetaDataKey]
  99 // ----------------------------------
 100 // The prefix is <database id, 0, 0>, followed by a type byte (100), then the
 101 // object store id (var int), then the index id (var int), then a metadata
 102 // type byte.
 103 //
 104 // <database id, 0, 0, 100, object store id, index id, 0> => index name
 105 // <database id, 0, 0, 100, object store id, index id, 1> => unique flag
 106 // <database id, 0, 0, 100, object store id, index id, 2> => key path
 107 // <database id, 0, 0, 100, object store id, index id, 3> => multi-entry flag
 108 //
 109 //
 110 // Other object store and index metadata
 111 // -------------------------------------
 112 // The prefix is <database id, 0, 0> followed by a type byte. The object
 113 // store and index id are variable length integers, the names are variable
 114 // length strings.
 115 //
 116 // <database id, 0, 0, 150, object store id>
 117 //   => existence implies the object store id is in the free list
 118 //      [ObjectStoreFreeListKey]
 119 // <database id, 0, 0, 151, object store id, index id>
 120 //   => existence implies the index id is in the free list [IndexFreeListKey]
 121 // <database id, 0, 0, 200, object store name>
 122 //   => object store id [ObjectStoreNamesKey]
 123 // <database id, 0, 0, 201, object store id, index name>
 124 //   => index id [IndexNamesKey]
 125 //
 126 //
 127 // Object store data: [ObjectStoreDataKey]
 128 // ---------------------------------------
 129 // The prefix is followed by a type byte and the encoded IDB primary key. The
 130 // data has a "version" prefix followed by the serialized script value.
 131 //
 132 // <database id, object store id, 1, user key>
 133 //   => "version", serialized script value
 134 //
 135 //
 136 // "Exists" entry: [ExistsEntryKey]
 137 // --------------------------------
 138 // The prefix is followed by a type byte and the encoded IDB primary key.
 139 //
 140 // <database id, object store id, 2, user key> => "version"
 141 //
 142 //
 143 // Blob entry table: [BlobEntryKey]
 144 // --------------------------------
 145 //
 146 // The prefix is followed by a type byte and the encoded IDB primary key.
 147 //
 148 // <database id, object store id, 3, user key> => array of IndexedDBBlobInfo
 149 //
 150 //
 151 // Index data
 152 // ----------
 153 // The prefix is followed by a type byte, the encoded IDB index key, a
 154 // "sequence" number (obsolete; var int), and the encoded IDB primary key.
 155 //
 156 // <database id, object store id, index id, index key, sequence number,
 157 //   primary key> => "version", primary key [IndexDataKey]
 158 //
 159 // The sequence number is obsolete; it was used to allow two entries with the
 160 // same user (index) key in non-unique indexes prior to the inclusion of the
 161 // primary key in the data.
 162
 163 using base::StringPiece;
 164 using blink::WebIDBKeyType;
 165 using blink::WebIDBKeyTypeArray;
 166 using blink::WebIDBKeyTypeBinary;
 167 using blink::WebIDBKeyTypeDate;
 168 using blink::WebIDBKeyTypeInvalid;
 169 using blink::WebIDBKeyTypeMin;
 170 using blink::WebIDBKeyTypeNull;
 171 using blink::WebIDBKeyTypeNumber;
 172 using blink::WebIDBKeyTypeString;
 173 using blink::WebIDBKeyPathType;
 174 using blink::WebIDBKeyPathTypeArray;
 175 using blink::WebIDBKeyPathTypeNull;
 176 using blink::WebIDBKeyPathTypeString;
 177
 178 namespace content {
 179
 180 // As most of the IndexedDBKeys and encoded values are short, we
 181 // initialize some std::vectors with a default inline buffer size to reduce
 182 // the memory re-allocations when the std::vectors are appended.
 183 static const size_t kDefaultInlineBufferSize = 32;
 184
 185 static const unsigned char kIndexedDBKeyNullTypeByte = 0;
 186 static const unsigned char kIndexedDBKeyStringTypeByte = 1;
 187 static const unsigned char kIndexedDBKeyDateTypeByte = 2;
 188 static const unsigned char kIndexedDBKeyNumberTypeByte = 3;
 189 static const unsigned char kIndexedDBKeyArrayTypeByte = 4;
 190 static const unsigned char kIndexedDBKeyMinKeyTypeByte = 5;
 191 static const unsigned char kIndexedDBKeyBinaryTypeByte = 6;
 192
 193 static const unsigned char kIndexedDBKeyPathTypeCodedByte1 = 0;
 194 static const unsigned char kIndexedDBKeyPathTypeCodedByte2 = 0;
 195
 196 static const unsigned char kObjectStoreDataIndexId = 1;
 197 static const unsigned char kExistsEntryIndexId = 2;
 198 static const unsigned char kBlobEntryIndexId = 3;
 199
 200 static const unsigned char kSchemaVersionTypeByte = 0;
 201 static const unsigned char kMaxDatabaseIdTypeByte = 1;
 202 static const unsigned char kDataVersionTypeByte = 2;
 203 static const unsigned char kBlobJournalTypeByte = 3;
 204 static const unsigned char kLiveBlobJournalTypeByte = 4;
 205 static const unsigned char kMaxSimpleGlobalMetaDataTypeByte =
 206     5;  // Insert before this and increment.
 207 static const unsigned char kDatabaseFreeListTypeByte = 100;
 208 static const unsigned char kDatabaseNameTypeByte = 201;
 209
 210 static const unsigned char kObjectStoreMetaDataTypeByte = 50;
 211 static const unsigned char kIndexMetaDataTypeByte = 100;
 212 static const unsigned char kObjectStoreFreeListTypeByte = 150;
 213 static const unsigned char kIndexFreeListTypeByte = 151;
 214 static const unsigned char kObjectStoreNamesTypeByte = 200;
 215 static const unsigned char kIndexNamesKeyTypeByte = 201;
 216
 217 static const unsigned char kObjectMetaDataTypeMaximum = 255;
 218 static const unsigned char kIndexMetaDataTypeMaximum = 255;
 219
 220 const unsigned char kMinimumIndexId = 30;
 221
 222 inline void EncodeIntSafely(int64 nParam, int64 max, std::string* into) {
 223   DCHECK_LE(nParam, max);
 224   return EncodeInt(nParam, into);
 225 }
 226
 227 std::string MaxIDBKey() {
 228   std::string ret;
 229   EncodeByte(kIndexedDBKeyNullTypeByte, &ret);
 230   return ret;
 231 }
 232
 233 std::string MinIDBKey() {
 234   std::string ret;
 235   EncodeByte(kIndexedDBKeyMinKeyTypeByte, &ret);
 236   return ret;
 237 }
 238
 239 void EncodeByte(unsigned char value, std::string* into) {
 240   into->push_back(value);
 241 }
 242
 243 void EncodeBool(bool value, std::string* into) {
 244   into->push_back(value ? 1 : 0);
 245 }
 246
 247 void EncodeInt(int64 value, std::string* into) {
 248 #ifndef NDEBUG
 249   // Exercised by unit tests in debug only.
 250   DCHECK_GE(value, 0);
 251 #endif
 252   uint64 n = static_cast<uint64>(value);
 253
 254   do {
 255     unsigned char c = n;
 256     into->push_back(c);
 257     n >>= 8;
 258   } while (n);
 259 }
 260
 261 void EncodeVarInt(int64 value, std::string* into) {
 262 #ifndef NDEBUG
 263   // Exercised by unit tests in debug only.
 264   DCHECK_GE(value, 0);
 265 #endif
 266   uint64 n = static_cast<uint64>(value);
 267
 268   do {
 269     unsigned char c = n & 0x7f;
 270     n >>= 7;
 271     if (n)
 272       c |= 0x80;
 273     into->push_back(c);
 274   } while (n);
 275 }
 276
 277 void EncodeString(const base::string16& value, std::string* into) {
 278   if (value.empty())
 279     return;
 280   // Backing store is UTF-16BE, convert from host endianness.
 281   size_t length = value.length();
 282   size_t current = into->size();
 283   into->resize(into->size() + length * sizeof(base::char16));
 284
 285   const base::char16* src = value.c_str();
 286   base::char16* dst =
 287       reinterpret_cast<base::char16*>(&*into->begin() + current);
 288   for (unsigned i = 0; i < length; ++i)
 289     *dst++ = htons(*src++);
 290 }
 291
 292 void EncodeBinary(const std::string& value, std::string* into) {
 293   EncodeVarInt(value.length(), into);
 294   into->append(value.begin(), value.end());
 295   DCHECK(into->size() >= value.size());
 296 }
 297
 298 void EncodeStringWithLength(const base::string16& value, std::string* into) {
 299   EncodeVarInt(value.length(), into);
 300   EncodeString(value, into);
 301 }
 302
 303 void EncodeDouble(double value, std::string* into) {
 304   // This always has host endianness.
 305   const char* p = reinterpret_cast<char*>(&value);
 306   into->insert(into->end(), p, p + sizeof(value));
 307 }
 308
 309 void EncodeIDBKey(const IndexedDBKey& value, std::string* into) {
 310   size_t previous_size = into->size();
 311   DCHECK(value.IsValid());
 312   switch (value.type()) {
 313     case WebIDBKeyTypeArray: {
 314       EncodeByte(kIndexedDBKeyArrayTypeByte, into);
 315       size_t length = value.array().size();
 316       EncodeVarInt(length, into);
 317       for (size_t i = 0; i < length; ++i)
 318         EncodeIDBKey(value.array()[i], into);
 319       DCHECK_GT(into->size(), previous_size);
 320       return;
 321     }
 322     case WebIDBKeyTypeBinary:
 323       EncodeByte(kIndexedDBKeyBinaryTypeByte, into);
 324       EncodeBinary(value.binary(), into);
 325       DCHECK_GT(into->size(), previous_size);
 326       return;
 327     case WebIDBKeyTypeString:
 328       EncodeByte(kIndexedDBKeyStringTypeByte, into);
 329       EncodeStringWithLength(value.string(), into);
 330       DCHECK_GT(into->size(), previous_size);
 331       return;
 332     case WebIDBKeyTypeDate:
 333       EncodeByte(kIndexedDBKeyDateTypeByte, into);
 334       EncodeDouble(value.date(), into);
 335       DCHECK_EQ(9u, static_cast<size_t>(into->size() - previous_size));
 336       return;
 337     case WebIDBKeyTypeNumber:
 338       EncodeByte(kIndexedDBKeyNumberTypeByte, into);
 339       EncodeDouble(value.number(), into);
 340       DCHECK_EQ(9u, static_cast<size_t>(into->size() - previous_size));
 341       return;
 342     case WebIDBKeyTypeNull:
 343     case WebIDBKeyTypeInvalid:
 344     case WebIDBKeyTypeMin:
 345     default:
 346       NOTREACHED();
 347       EncodeByte(kIndexedDBKeyNullTypeByte, into);
 348       return;
 349   }
 350 }
 351
 352 void EncodeIDBKeyPath(const IndexedDBKeyPath& value, std::string* into) {
 353   // May be typed, or may be a raw string. An invalid leading
 354   // byte is used to identify typed coding. New records are
 355   // always written as typed.
 356   EncodeByte(kIndexedDBKeyPathTypeCodedByte1, into);
 357   EncodeByte(kIndexedDBKeyPathTypeCodedByte2, into);
 358   EncodeByte(static_cast<char>(value.type()), into);
 359   switch (value.type()) {
 360     case WebIDBKeyPathTypeNull:
 361       break;
 362     case WebIDBKeyPathTypeString: {
 363       EncodeStringWithLength(value.string(), into);
 364       break;
 365     }
 366     case WebIDBKeyPathTypeArray: {
 367       const std::vector<base::string16>& array = value.array();
 368       size_t count = array.size();
 369       EncodeVarInt(count, into);
 370       for (size_t i = 0; i < count; ++i) {
 371         EncodeStringWithLength(array[i], into);
 372       }
 373       break;
 374     }
 375   }
 376 }
 377
 378 void EncodeBlobJournal(const BlobJournalType& journal, std::string* into) {
 379   BlobJournalType::const_iterator iter;
 380   for (iter = journal.begin(); iter != journal.end(); ++iter) {
 381     EncodeVarInt(iter->first, into);
 382     EncodeVarInt(iter->second, into);
 383   }
 384 }
 385
 386 bool DecodeByte(StringPiece* slice, unsigned char* value) {
 387   if (slice->empty())
 388     return false;
 389
 390   *value = (*slice)[0];
 391   slice->remove_prefix(1);
 392   return true;
 393 }
 394
 395 bool DecodeBool(StringPiece* slice, bool* value) {
 396   if (slice->empty())
 397     return false;
 398
 399   *value = !!(*slice)[0];
 400   slice->remove_prefix(1);
 401   return true;
 402 }
 403
 404 bool DecodeInt(StringPiece* slice, int64* value) {
 405   if (slice->empty())
 406     return false;
 407
 408   StringPiece::const_iterator it = slice->begin();
 409   int shift = 0;
 410   int64 ret = 0;
 411   while (it != slice->end()) {
 412     unsigned char c = *it++;
 413     ret |= static_cast<int64>(c) << shift;
 414     shift += 8;
 415   }
 416   *value = ret;
 417   slice->remove_prefix(it - slice->begin());
 418   return true;
 419 }
 420
 421 bool DecodeVarInt(StringPiece* slice, int64* value) {
 422   if (slice->empty())
 423     return false;
 424
 425   StringPiece::const_iterator it = slice->begin();
 426   int shift = 0;
 427   int64 ret = 0;
 428   do {
 429     if (it == slice->end())
 430       return false;
 431
 432     unsigned char c = *it;
 433     ret |= static_cast<int64>(c & 0x7f) << shift;
 434     shift += 7;
 435   } while (*it++ & 0x80);
 436   *value = ret;
 437   slice->remove_prefix(it - slice->begin());
 438   return true;
 439 }
 440
 441 bool DecodeString(StringPiece* slice, base::string16* value) {
 442   if (slice->empty()) {
 443     value->clear();
 444     return true;
 445   }
 446
 447   // Backing store is UTF-16BE, convert to host endianness.
 448   DCHECK(!(slice->size() % sizeof(base::char16)));
 449   size_t length = slice->size() / sizeof(base::char16);
 450   base::string16 decoded;
 451   decoded.reserve(length);
 452   const base::char16* encoded =
 453       reinterpret_cast<const base::char16*>(slice->begin());
 454   for (unsigned i = 0; i < length; ++i)
 455     decoded.push_back(ntohs(*encoded++));
 456
 457   *value = decoded;
 458   slice->remove_prefix(length * sizeof(base::char16));
 459   return true;
 460 }
 461
 462 bool DecodeStringWithLength(StringPiece* slice, base::string16* value) {
 463   if (slice->empty())
 464     return false;
 465
 466   int64 length = 0;
 467   if (!DecodeVarInt(slice, &length) || length < 0)
 468     return false;
 469   size_t bytes = length * sizeof(base::char16);
 470   if (slice->size() < bytes)
 471     return false;
 472
 473   StringPiece subpiece(slice->begin(), bytes);
 474   slice->remove_prefix(bytes);
 475   if (!DecodeString(&subpiece, value))
 476     return false;
 477
 478   return true;
 479 }
 480
 481 bool DecodeBinary(StringPiece* slice, std::string* value) {
 482   if (slice->empty())
 483     return false;
 484
 485   int64 length = 0;
 486   if (!DecodeVarInt(slice, &length) || length < 0)
 487     return false;
 488   size_t size = length;
 489   if (slice->size() < size)
 490     return false;
 491
 492   value->assign(slice->begin(), size);
 493   slice->remove_prefix(size);
 494   return true;
 495 }
 496
 497 bool DecodeIDBKey(StringPiece* slice, scoped_ptr<IndexedDBKey>* value) {
 498   if (slice->empty())
 499     return false;
 500
 501   unsigned char type = (*slice)[0];
 502   slice->remove_prefix(1);
 503
 504   switch (type) {
 505     case kIndexedDBKeyNullTypeByte:
 506       *value = make_scoped_ptr(new IndexedDBKey());
 507       return true;
 508
 509     case kIndexedDBKeyArrayTypeByte: {
 510       int64 length = 0;
 511       if (!DecodeVarInt(slice, &length) || length < 0)
 512         return false;
 513       IndexedDBKey::KeyArray array;
 514       while (length--) {
 515         scoped_ptr<IndexedDBKey> key;
 516         if (!DecodeIDBKey(slice, &key))
 517           return false;
 518         array.push_back(*key);
 519       }
 520       *value = make_scoped_ptr(new IndexedDBKey(array));
 521       return true;
 522     }
 523     case kIndexedDBKeyBinaryTypeByte: {
 524       std::string binary;
 525       if (!DecodeBinary(slice, &binary))
 526         return false;
 527       *value = make_scoped_ptr(new IndexedDBKey(binary));
 528       return true;
 529     }
 530     case kIndexedDBKeyStringTypeByte: {
 531       base::string16 s;
 532       if (!DecodeStringWithLength(slice, &s))
 533         return false;
 534       *value = make_scoped_ptr(new IndexedDBKey(s));
 535       return true;
 536     }
 537     case kIndexedDBKeyDateTypeByte: {
 538       double d;
 539       if (!DecodeDouble(slice, &d))
 540         return false;
 541       *value = make_scoped_ptr(new IndexedDBKey(d, WebIDBKeyTypeDate));
 542       return true;
 543     }
 544     case kIndexedDBKeyNumberTypeByte: {
 545       double d;
 546       if (!DecodeDouble(slice, &d))
 547         return false;
 548       *value = make_scoped_ptr(new IndexedDBKey(d, WebIDBKeyTypeNumber));
 549       return true;
 550     }
 551   }
 552
 553   NOTREACHED();
 554   return false;
 555 }
 556
 557 bool DecodeDouble(StringPiece* slice, double* value) {
 558   if (slice->size() < sizeof(*value))
 559     return false;
 560
 561   memcpy(value, slice->begin(), sizeof(*value));
 562   slice->remove_prefix(sizeof(*value));
 563   return true;
 564 }
 565
 566 bool DecodeIDBKeyPath(StringPiece* slice, IndexedDBKeyPath* value) {
 567   // May be typed, or may be a raw string. An invalid leading
 568   // byte sequence is used to identify typed coding. New records are
 569   // always written as typed.
 570   if (slice->size() < 3 || (*slice)[0] != kIndexedDBKeyPathTypeCodedByte1 ||
 571       (*slice)[1] != kIndexedDBKeyPathTypeCodedByte2) {
 572     base::string16 s;
 573     if (!DecodeString(slice, &s))
 574       return false;
 575     *value = IndexedDBKeyPath(s);
 576     return true;
 577   }
 578
 579   slice->remove_prefix(2);
 580   DCHECK(!slice->empty());
 581   WebIDBKeyPathType type = static_cast<WebIDBKeyPathType>((*slice)[0]);
 582   slice->remove_prefix(1);
 583
 584   switch (type) {
 585     case WebIDBKeyPathTypeNull:
 586       DCHECK(slice->empty());
 587       *value = IndexedDBKeyPath();
 588       return true;
 589     case WebIDBKeyPathTypeString: {
 590       base::string16 string;
 591       if (!DecodeStringWithLength(slice, &string))
 592         return false;
 593       DCHECK(slice->empty());
 594       *value = IndexedDBKeyPath(string);
 595       return true;
 596     }
 597     case WebIDBKeyPathTypeArray: {
 598       std::vector<base::string16> array;
 599       int64 count;
 600       if (!DecodeVarInt(slice, &count))
 601         return false;
 602       DCHECK_GE(count, 0);
 603       while (count--) {
 604         base::string16 string;
 605         if (!DecodeStringWithLength(slice, &string))
 606           return false;
 607         array.push_back(string);
 608       }
 609       DCHECK(slice->empty());
 610       *value = IndexedDBKeyPath(array);
 611       return true;
 612     }
 613   }
 614   NOTREACHED();
 615   return false;
 616 }
 617
 618 bool DecodeBlobJournal(StringPiece* slice, BlobJournalType* journal) {
 619   BlobJournalType output;
 620   while (!slice->empty()) {
 621     int64 database_id = -1;
 622     int64 blob_key = -1;
 623     if (!DecodeVarInt(slice, &database_id))
 624       return false;
 625     if (!KeyPrefix::IsValidDatabaseId(database_id))
 626       return false;
 627     if (!DecodeVarInt(slice, &blob_key))
 628       return false;
 629     if (!DatabaseMetaDataKey::IsValidBlobKey(blob_key) &&
 630         (blob_key != DatabaseMetaDataKey::kAllBlobsKey)) {
 631       return false;
 632     }
 633     output.push_back(std::make_pair(database_id, blob_key));
 634   }
 635   journal->swap(output);
 636   return true;
 637 }
 638
 639 bool ConsumeEncodedIDBKey(StringPiece* slice) {
 640   unsigned char type = (*slice)[0];
 641   slice->remove_prefix(1);
 642
 643   switch (type) {
 644     case kIndexedDBKeyNullTypeByte:
 645     case kIndexedDBKeyMinKeyTypeByte:
 646       return true;
 647     case kIndexedDBKeyArrayTypeByte: {
 648       int64 length;
 649       if (!DecodeVarInt(slice, &length))
 650         return false;
 651       while (length--) {
 652         if (!ConsumeEncodedIDBKey(slice))
 653           return false;
 654       }
 655       return true;
 656     }
 657     case kIndexedDBKeyBinaryTypeByte: {
 658       int64 length = 0;
 659       if (!DecodeVarInt(slice, &length) || length < 0)
 660         return false;
 661       if (slice->size() < static_cast<size_t>(length))
 662         return false;
 663       slice->remove_prefix(length);
 664       return true;
 665     }
 666     case kIndexedDBKeyStringTypeByte: {
 667       int64 length = 0;
 668       if (!DecodeVarInt(slice, &length) || length < 0)
 669         return false;
 670       if (slice->size() < static_cast<size_t>(length) * sizeof(base::char16))
 671         return false;
 672       slice->remove_prefix(length * sizeof(base::char16));
 673       return true;
 674     }
 675     case kIndexedDBKeyDateTypeByte:
 676     case kIndexedDBKeyNumberTypeByte:
 677       if (slice->size() < sizeof(double))
 678         return false;
 679       slice->remove_prefix(sizeof(double));
 680       return true;
 681   }
 682   NOTREACHED();
 683   return false;
 684 }
 685
 686 bool ExtractEncodedIDBKey(StringPiece* slice, std::string* result) {
 687   const char* start = slice->begin();
 688   if (!ConsumeEncodedIDBKey(slice))
 689     return false;
 690
 691   if (result)
 692     result->assign(start, slice->begin());
 693   return true;
 694 }
 695
 696 static WebIDBKeyType KeyTypeByteToKeyType(unsigned char type) {
 697   switch (type) {
 698     case kIndexedDBKeyNullTypeByte:
 699       return WebIDBKeyTypeInvalid;
 700     case kIndexedDBKeyArrayTypeByte:
 701       return WebIDBKeyTypeArray;
 702     case kIndexedDBKeyBinaryTypeByte:
 703       return WebIDBKeyTypeBinary;
 704     case kIndexedDBKeyStringTypeByte:
 705       return WebIDBKeyTypeString;
 706     case kIndexedDBKeyDateTypeByte:
 707       return WebIDBKeyTypeDate;
 708     case kIndexedDBKeyNumberTypeByte:
 709       return WebIDBKeyTypeNumber;
 710     case kIndexedDBKeyMinKeyTypeByte:
 711       return WebIDBKeyTypeMin;
 712   }
 713
 714   NOTREACHED();
 715   return WebIDBKeyTypeInvalid;
 716 }
 717
 718 int CompareEncodedStringsWithLength(StringPiece* slice1,
 719                                     StringPiece* slice2,
 720                                     bool* ok) {
 721   int64 len1, len2;
 722   if (!DecodeVarInt(slice1, &len1) || !DecodeVarInt(slice2, &len2)) {
 723     *ok = false;
 724     return 0;
 725   }
 726   DCHECK_GE(len1, 0);
 727   DCHECK_GE(len2, 0);
 728   if (len1 < 0 || len2 < 0) {
 729     *ok = false;
 730     return 0;
 731   }
 732   DCHECK_GE(slice1->size(), len1 * sizeof(base::char16));
 733   DCHECK_GE(slice2->size(), len2 * sizeof(base::char16));
 734   if (slice1->size() < len1 * sizeof(base::char16) ||
 735       slice2->size() < len2 * sizeof(base::char16)) {
 736     *ok = false;
 737     return 0;
 738   }
 739
 740   // Extract the string data, and advance the passed slices.
 741   StringPiece string1(slice1->begin(), len1 * sizeof(base::char16));
 742   StringPiece string2(slice2->begin(), len2 * sizeof(base::char16));
 743   slice1->remove_prefix(len1 * sizeof(base::char16));
 744   slice2->remove_prefix(len2 * sizeof(base::char16));
 745
 746   *ok = true;
 747   // Strings are UTF-16BE encoded, so a simple memcmp is sufficient.
 748   return string1.compare(string2);
 749 }
 750
 751 int CompareEncodedBinary(StringPiece* slice1,
 752                          StringPiece* slice2,
 753                          bool* ok) {
 754   int64 len1, len2;
 755   if (!DecodeVarInt(slice1, &len1) || !DecodeVarInt(slice2, &len2)) {
 756     *ok = false;
 757     return 0;
 758   }
 759   DCHECK_GE(len1, 0);
 760   DCHECK_GE(len2, 0);
 761   if (len1 < 0 || len2 < 0) {
 762     *ok = false;
 763     return 0;
 764   }
 765   size_t size1 = len1;
 766   size_t size2 = len2;
 767
 768   DCHECK_GE(slice1->size(), size1);
 769   DCHECK_GE(slice2->size(), size2);
 770   if (slice1->size() < size1 || slice2->size() < size2) {
 771     *ok = false;
 772     return 0;
 773   }
 774
 775   // Extract the binary data, and advance the passed slices.
 776   StringPiece binary1(slice1->begin(), size1);
 777   StringPiece binary2(slice2->begin(), size2);
 778   slice1->remove_prefix(size1);
 779   slice2->remove_prefix(size2);
 780
 781   *ok = true;
 782   // This is the same as a memcmp()
 783   return binary1.compare(binary2);
 784 }
 785
 786 static int CompareInts(int64 a, int64 b) {
 787 #ifndef NDEBUG
 788   // Exercised by unit tests in debug only.
 789   DCHECK_GE(a, 0);
 790   DCHECK_GE(b, 0);
 791 #endif
 792   int64 diff = a - b;
 793   if (diff < 0)
 794     return -1;
 795   if (diff > 0)
 796     return 1;
 797   return 0;
 798 }
 799
 800 static inline int CompareSizes(size_t a, size_t b) {
 801   if (a > b)
 802     return 1;
 803   if (b > a)
 804     return -1;
 805   return 0;
 806 }
 807
 808 static int CompareTypes(WebIDBKeyType a, WebIDBKeyType b) { return b - a; }
 809
 810 int CompareEncodedIDBKeys(StringPiece* slice_a,
 811                           StringPiece* slice_b,
 812                           bool* ok) {
 813   DCHECK(!slice_a->empty());
 814   DCHECK(!slice_b->empty());
 815   *ok = true;
 816   unsigned char type_a = (*slice_a)[0];
 817   unsigned char type_b = (*slice_b)[0];
 818   slice_a->remove_prefix(1);
 819   slice_b->remove_prefix(1);
 820
 821   if (int x = CompareTypes(KeyTypeByteToKeyType(type_a),
 822                            KeyTypeByteToKeyType(type_b)))
 823     return x;
 824
 825   switch (type_a) {
 826     case kIndexedDBKeyNullTypeByte:
 827     case kIndexedDBKeyMinKeyTypeByte:
 828       // Null type or max type; no payload to compare.
 829       return 0;
 830     case kIndexedDBKeyArrayTypeByte: {
 831       int64 length_a, length_b;
 832       if (!DecodeVarInt(slice_a, &length_a) ||
 833           !DecodeVarInt(slice_b, &length_b)) {
 834         *ok = false;
 835         return 0;
 836       }
 837       for (int64 i = 0; i < length_a && i < length_b; ++i) {
 838         int result = CompareEncodedIDBKeys(slice_a, slice_b, ok);
 839         if (!*ok || result)
 840           return result;
 841       }
 842       return length_a - length_b;
 843     }
 844     case kIndexedDBKeyBinaryTypeByte:
 845       return CompareEncodedBinary(slice_a, slice_b, ok);
 846     case kIndexedDBKeyStringTypeByte:
 847       return CompareEncodedStringsWithLength(slice_a, slice_b, ok);
 848     case kIndexedDBKeyDateTypeByte:
 849     case kIndexedDBKeyNumberTypeByte: {
 850       double d, e;
 851       if (!DecodeDouble(slice_a, &d) || !DecodeDouble(slice_b, &e)) {
 852         *ok = false;
 853         return 0;
 854       }
 855       if (d < e)
 856         return -1;
 857       if (d > e)
 858         return 1;
 859       return 0;
 860     }
 861   }
 862
 863   NOTREACHED();
 864   return 0;
 865 }
 866
 867 namespace {
 868
 869 template <typename KeyType>
 870 int Compare(const StringPiece& a,
 871             const StringPiece& b,
 872             bool only_compare_index_keys,
 873             bool* ok) {
 874   KeyType key_a;
 875   KeyType key_b;
 876
 877   StringPiece slice_a(a);
 878   if (!KeyType::Decode(&slice_a, &key_a)) {
 879     *ok = false;
 880     return 0;
 881   }
 882   StringPiece slice_b(b);
 883   if (!KeyType::Decode(&slice_b, &key_b)) {
 884     *ok = false;
 885     return 0;
 886   }
 887
 888   *ok = true;
 889   return key_a.Compare(key_b);
 890 }
 891
 892 template <typename KeyType>
 893 int CompareSuffix(StringPiece* a,
 894                   StringPiece* b,
 895                   bool only_compare_index_keys,
 896                   bool* ok) {
 897   NOTREACHED();
 898   return 0;
 899 }
 900
 901 template <>
 902 int CompareSuffix<ExistsEntryKey>(StringPiece* slice_a,
 903                                   StringPiece* slice_b,
 904                                   bool only_compare_index_keys,
 905                                   bool* ok) {
 906   DCHECK(!slice_a->empty());
 907   DCHECK(!slice_b->empty());
 908   return CompareEncodedIDBKeys(slice_a, slice_b, ok);
 909 }
 910
 911 template <>
 912 int CompareSuffix<ObjectStoreDataKey>(StringPiece* slice_a,
 913                                       StringPiece* slice_b,
 914                                       bool only_compare_index_keys,
 915                                       bool* ok) {
 916   return CompareEncodedIDBKeys(slice_a, slice_b, ok);
 917 }
 918
 919 template <>
 920 int CompareSuffix<BlobEntryKey>(StringPiece* slice_a,
 921                                 StringPiece* slice_b,
 922                                 bool only_compare_index_keys,
 923                                 bool* ok) {
 924   return CompareEncodedIDBKeys(slice_a, slice_b, ok);
 925 }
 926
 927 template <>
 928 int CompareSuffix<IndexDataKey>(StringPiece* slice_a,
 929                                 StringPiece* slice_b,
 930                                 bool only_compare_index_keys,
 931                                 bool* ok) {
 932   // index key
 933   int result = CompareEncodedIDBKeys(slice_a, slice_b, ok);
 934   if (!*ok || result)
 935     return result;
 936   if (only_compare_index_keys)
 937     return 0;
 938
 939   // sequence number [optional]
 940   int64 sequence_number_a = -1;
 941   int64 sequence_number_b = -1;
 942   if (!slice_a->empty() && !DecodeVarInt(slice_a, &sequence_number_a))
 943       return 0;
 944   if (!slice_b->empty() && !DecodeVarInt(slice_b, &sequence_number_b))
 945       return 0;
 946
 947   if (slice_a->empty() || slice_b->empty())
 948     return CompareSizes(slice_a->size(), slice_b->size());
 949
 950   // primary key [optional]
 951   result = CompareEncodedIDBKeys(slice_a, slice_b, ok);
 952   if (!*ok || result)
 953     return result;
 954
 955   return CompareInts(sequence_number_a, sequence_number_b);
 956 }
 957
 958 int Compare(const StringPiece& a,
 959             const StringPiece& b,
 960             bool only_compare_index_keys,
 961             bool* ok) {
 962   StringPiece slice_a(a);
 963   StringPiece slice_b(b);
 964   KeyPrefix prefix_a;
 965   KeyPrefix prefix_b;
 966   bool ok_a = KeyPrefix::Decode(&slice_a, &prefix_a);
 967   bool ok_b = KeyPrefix::Decode(&slice_b, &prefix_b);
 968   DCHECK(ok_a);
 969   DCHECK(ok_b);
 970   if (!ok_a || !ok_b) {
 971     *ok = false;
 972     return 0;
 973   }
 974
 975   *ok = true;
 976   if (int x = prefix_a.Compare(prefix_b))
 977     return x;
 978
 979   switch (prefix_a.type()) {
 980     case KeyPrefix::GLOBAL_METADATA: {
 981       DCHECK(!slice_a.empty());
 982       DCHECK(!slice_b.empty());
 983
 984       unsigned char type_byte_a;
 985       if (!DecodeByte(&slice_a, &type_byte_a)) {
 986         *ok = false;
 987         return 0;
 988       }
 989
 990       unsigned char type_byte_b;
 991       if (!DecodeByte(&slice_b, &type_byte_b)) {
 992         *ok = false;
 993         return 0;
 994       }
 995
 996       if (int x = type_byte_a - type_byte_b)
 997         return x;
 998       if (type_byte_a < kMaxSimpleGlobalMetaDataTypeByte)
 999         return 0;
1000
1001       // Compare<> is used (which re-decodes the prefix) rather than an
1002       // specialized CompareSuffix<> because metadata is relatively uncommon
1003       // in the database.
1004
1005       if (type_byte_a == kDatabaseFreeListTypeByte) {
1006         // TODO(jsbell): No need to pass only_compare_index_keys through here.
1007         return Compare<DatabaseFreeListKey>(a, b, only_compare_index_keys, ok);
1008       }
1009       if (type_byte_a == kDatabaseNameTypeByte) {
1010         return Compare<DatabaseNameKey>(
1011             a, b, /*only_compare_index_keys*/ false, ok);
1012       }
1013       break;
1014     }
1015
1016     case KeyPrefix::DATABASE_METADATA: {
1017       DCHECK(!slice_a.empty());
1018       DCHECK(!slice_b.empty());
1019
1020       unsigned char type_byte_a;
1021       if (!DecodeByte(&slice_a, &type_byte_a)) {
1022         *ok = false;
1023         return 0;
1024       }
1025
1026       unsigned char type_byte_b;
1027       if (!DecodeByte(&slice_b, &type_byte_b)) {
1028         *ok = false;
1029         return 0;
1030       }
1031
1032       if (int x = type_byte_a - type_byte_b)
1033         return x;
1034       if (type_byte_a < DatabaseMetaDataKey::MAX_SIMPLE_METADATA_TYPE)
1035         return 0;
1036
1037       // Compare<> is used (which re-decodes the prefix) rather than an
1038       // specialized CompareSuffix<> because metadata is relatively uncommon
1039       // in the database.
1040
1041       if (type_byte_a == kObjectStoreMetaDataTypeByte) {
1042         // TODO(jsbell): No need to pass only_compare_index_keys through here.
1043         return Compare<ObjectStoreMetaDataKey>(
1044             a, b, only_compare_index_keys, ok);
1045       }
1046       if (type_byte_a == kIndexMetaDataTypeByte) {
1047         return Compare<IndexMetaDataKey>(
1048             a, b, /*only_compare_index_keys*/ false, ok);
1049       }
1050       if (type_byte_a == kObjectStoreFreeListTypeByte) {
1051         return Compare<ObjectStoreFreeListKey>(
1052             a, b, only_compare_index_keys, ok);
1053       }
1054       if (type_byte_a == kIndexFreeListTypeByte) {
1055         return Compare<IndexFreeListKey>(
1056             a, b, /*only_compare_index_keys*/ false, ok);
1057       }
1058       if (type_byte_a == kObjectStoreNamesTypeByte) {
1059         // TODO(jsbell): No need to pass only_compare_index_keys through here.
1060         return Compare<ObjectStoreNamesKey>(
1061             a, b, only_compare_index_keys, ok);
1062       }
1063       if (type_byte_a == kIndexNamesKeyTypeByte) {
1064         return Compare<IndexNamesKey>(
1065             a, b, /*only_compare_index_keys*/ false, ok);
1066       }
1067       break;
1068     }
1069
1070     case KeyPrefix::OBJECT_STORE_DATA: {
1071       // Provide a stable ordering for invalid data.
1072       if (slice_a.empty() || slice_b.empty())
1073         return CompareSizes(slice_a.size(), slice_b.size());
1074
1075       return CompareSuffix<ObjectStoreDataKey>(
1076           &slice_a, &slice_b, /*only_compare_index_keys*/ false, ok);
1077     }
1078
1079     case KeyPrefix::EXISTS_ENTRY: {
1080       // Provide a stable ordering for invalid data.
1081       if (slice_a.empty() || slice_b.empty())
1082         return CompareSizes(slice_a.size(), slice_b.size());
1083
1084       return CompareSuffix<ExistsEntryKey>(
1085           &slice_a, &slice_b, /*only_compare_index_keys*/ false, ok);
1086     }
1087
1088     case KeyPrefix::BLOB_ENTRY: {
1089       // Provide a stable ordering for invalid data.
1090       if (slice_a.empty() || slice_b.empty())
1091         return CompareSizes(slice_a.size(), slice_b.size());
1092
1093       return CompareSuffix<BlobEntryKey>(
1094           &slice_a, &slice_b, /*only_compare_index_keys*/ false, ok);
1095     }
1096
1097     case KeyPrefix::INDEX_DATA: {
1098       // Provide a stable ordering for invalid data.
1099       if (slice_a.empty() || slice_b.empty())
1100         return CompareSizes(slice_a.size(), slice_b.size());
1101
1102       return CompareSuffix<IndexDataKey>(
1103           &slice_a, &slice_b, only_compare_index_keys, ok);
1104     }
1105
1106     case KeyPrefix::INVALID_TYPE:
1107       break;
1108   }
1109
1110   NOTREACHED();
1111   *ok = false;
1112   return 0;
1113 }
1114
1115 }  // namespace
1116
1117 int Compare(const StringPiece& a,
1118             const StringPiece& b,
1119             bool only_compare_index_keys) {
1120   bool ok;
1121   int result = Compare(a, b, only_compare_index_keys, &ok);
1122   DCHECK(ok);
1123   if (!ok)
1124     return 0;
1125   return result;
1126 }
1127
1128 KeyPrefix::KeyPrefix()
1129     : database_id_(INVALID_TYPE),
1130       object_store_id_(INVALID_TYPE),
1131       index_id_(INVALID_TYPE) {}
1132
1133 KeyPrefix::KeyPrefix(int64 database_id)
1134     : database_id_(database_id), object_store_id_(0), index_id_(0) {
1135   DCHECK(KeyPrefix::IsValidDatabaseId(database_id));
1136 }
1137
1138 KeyPrefix::KeyPrefix(int64 database_id, int64 object_store_id)
1139     : database_id_(database_id),
1140       object_store_id_(object_store_id),
1141       index_id_(0) {
1142   DCHECK(KeyPrefix::IsValidDatabaseId(database_id));
1143   DCHECK(KeyPrefix::IsValidObjectStoreId(object_store_id));
1144 }
1145
1146 KeyPrefix::KeyPrefix(int64 database_id, int64 object_store_id, int64 index_id)
1147     : database_id_(database_id),
1148       object_store_id_(object_store_id),
1149       index_id_(index_id) {
1150   DCHECK(KeyPrefix::IsValidDatabaseId(database_id));
1151   DCHECK(KeyPrefix::IsValidObjectStoreId(object_store_id));
1152   DCHECK(KeyPrefix::IsValidIndexId(index_id));
1153 }
1154
1155 KeyPrefix::KeyPrefix(enum Type type,
1156                      int64 database_id,
1157                      int64 object_store_id,
1158                      int64 index_id)
1159     : database_id_(database_id),
1160       object_store_id_(object_store_id),
1161       index_id_(index_id) {
1162   DCHECK_EQ(type, INVALID_TYPE);
1163   DCHECK(KeyPrefix::IsValidDatabaseId(database_id));
1164   DCHECK(KeyPrefix::IsValidObjectStoreId(object_store_id));
1165 }
1166
1167 KeyPrefix KeyPrefix::CreateWithSpecialIndex(int64 database_id,
1168                                             int64 object_store_id,
1169                                             int64 index_id) {
1170   DCHECK(KeyPrefix::IsValidDatabaseId(database_id));
1171   DCHECK(KeyPrefix::IsValidObjectStoreId(object_store_id));
1172   DCHECK(index_id);
1173   return KeyPrefix(INVALID_TYPE, database_id, object_store_id, index_id);
1174 }
1175
1176 bool KeyPrefix::IsValidDatabaseId(int64 database_id) {
1177   return (database_id > 0) && (database_id < KeyPrefix::kMaxDatabaseId);
1178 }
1179
1180 bool KeyPrefix::IsValidObjectStoreId(int64 object_store_id) {
1181   return (object_store_id > 0) &&
1182          (object_store_id < KeyPrefix::kMaxObjectStoreId);
1183 }
1184
1185 bool KeyPrefix::IsValidIndexId(int64 index_id) {
1186   return (index_id >= kMinimumIndexId) && (index_id < KeyPrefix::kMaxIndexId);
1187 }
1188
1189 bool KeyPrefix::Decode(StringPiece* slice, KeyPrefix* result) {
1190   unsigned char first_byte;
1191   if (!DecodeByte(slice, &first_byte))
1192     return false;
1193
1194   size_t database_id_bytes = ((first_byte >> 5) & 0x7) + 1;
1195   size_t object_store_id_bytes = ((first_byte >> 2) & 0x7) + 1;
1196   size_t index_id_bytes = (first_byte & 0x3) + 1;
1197
1198   if (database_id_bytes + object_store_id_bytes + index_id_bytes >
1199       slice->size())
1200     return false;
1201
1202   {
1203     StringPiece tmp(slice->begin(), database_id_bytes);
1204     if (!DecodeInt(&tmp, &result->database_id_))
1205       return false;
1206   }
1207   slice->remove_prefix(database_id_bytes);
1208   {
1209     StringPiece tmp(slice->begin(), object_store_id_bytes);
1210     if (!DecodeInt(&tmp, &result->object_store_id_))
1211       return false;
1212   }
1213   slice->remove_prefix(object_store_id_bytes);
1214   {
1215     StringPiece tmp(slice->begin(), index_id_bytes);
1216     if (!DecodeInt(&tmp, &result->index_id_))
1217       return false;
1218   }
1219   slice->remove_prefix(index_id_bytes);
1220   return true;
1221 }
1222
1223 std::string KeyPrefix::EncodeEmpty() {
1224   const std::string result(4, 0);
1225   DCHECK(EncodeInternal(0, 0, 0) == std::string(4, 0));
1226   return result;
1227 }
1228
1229 std::string KeyPrefix::Encode() const {
1230   DCHECK(database_id_ != kInvalidId);
1231   DCHECK(object_store_id_ != kInvalidId);
1232   DCHECK(index_id_ != kInvalidId);
1233   return EncodeInternal(database_id_, object_store_id_, index_id_);
1234 }
1235
1236 std::string KeyPrefix::EncodeInternal(int64 database_id,
1237                                       int64 object_store_id,
1238                                       int64 index_id) {
1239   std::string database_id_string;
1240   std::string object_store_id_string;
1241   std::string index_id_string;
1242
1243   EncodeIntSafely(database_id, kMaxDatabaseId, &database_id_string);
1244   EncodeIntSafely(object_store_id, kMaxObjectStoreId, &object_store_id_string);
1245   EncodeIntSafely(index_id, kMaxIndexId, &index_id_string);
1246
1247   DCHECK(database_id_string.size() <= kMaxDatabaseIdSizeBytes);
1248   DCHECK(object_store_id_string.size() <= kMaxObjectStoreIdSizeBytes);
1249   DCHECK(index_id_string.size() <= kMaxIndexIdSizeBytes);
1250
1251   unsigned char first_byte =
1252       (database_id_string.size() - 1) << (kMaxObjectStoreIdSizeBits +
1253                                           kMaxIndexIdSizeBits) |
1254       (object_store_id_string.size() - 1) << kMaxIndexIdSizeBits |
1255       (index_id_string.size() - 1);
1256   COMPILE_ASSERT(kMaxDatabaseIdSizeBits + kMaxObjectStoreIdSizeBits +
1257                          kMaxIndexIdSizeBits ==
1258                      sizeof(first_byte) * 8,
1259                  CANT_ENCODE_IDS);
1260   std::string ret;
1261   ret.reserve(kDefaultInlineBufferSize);
1262   ret.push_back(first_byte);
1263   ret.append(database_id_string);
1264   ret.append(object_store_id_string);
1265   ret.append(index_id_string);
1266
1267   DCHECK_LE(ret.size(), kDefaultInlineBufferSize);
1268   return ret;
1269 }
1270
1271 int KeyPrefix::Compare(const KeyPrefix& other) const {
1272   DCHECK(database_id_ != kInvalidId);
1273   DCHECK(object_store_id_ != kInvalidId);
1274   DCHECK(index_id_ != kInvalidId);
1275
1276   if (database_id_ != other.database_id_)
1277     return CompareInts(database_id_, other.database_id_);
1278   if (object_store_id_ != other.object_store_id_)
1279     return CompareInts(object_store_id_, other.object_store_id_);
1280   if (index_id_ != other.index_id_)
1281     return CompareInts(index_id_, other.index_id_);
1282   return 0;
1283 }
1284
1285 KeyPrefix::Type KeyPrefix::type() const {
1286   DCHECK(database_id_ != kInvalidId);
1287   DCHECK(object_store_id_ != kInvalidId);
1288   DCHECK(index_id_ != kInvalidId);
1289
1290   if (!database_id_)
1291     return GLOBAL_METADATA;
1292   if (!object_store_id_)
1293     return DATABASE_METADATA;
1294   if (index_id_ == kObjectStoreDataIndexId)
1295     return OBJECT_STORE_DATA;
1296   if (index_id_ == kExistsEntryIndexId)
1297     return EXISTS_ENTRY;
1298   if (index_id_ == kBlobEntryIndexId)
1299     return BLOB_ENTRY;
1300   if (index_id_ >= kMinimumIndexId)
1301     return INDEX_DATA;
1302
1303   NOTREACHED();
1304   return INVALID_TYPE;
1305 }
1306
1307 std::string SchemaVersionKey::Encode() {
1308   std::string ret = KeyPrefix::EncodeEmpty();
1309   ret.push_back(kSchemaVersionTypeByte);
1310   return ret;
1311 }
1312
1313 std::string MaxDatabaseIdKey::Encode() {
1314   std::string ret = KeyPrefix::EncodeEmpty();
1315   ret.push_back(kMaxDatabaseIdTypeByte);
1316   return ret;
1317 }
1318
1319 std::string DataVersionKey::Encode() {
1320   std::string ret = KeyPrefix::EncodeEmpty();
1321   ret.push_back(kDataVersionTypeByte);
1322   return ret;
1323 }
1324
1325 std::string BlobJournalKey::Encode() {
1326   std::string ret = KeyPrefix::EncodeEmpty();
1327   ret.push_back(kBlobJournalTypeByte);
1328   return ret;
1329 }
1330
1331 std::string LiveBlobJournalKey::Encode() {
1332   std::string ret = KeyPrefix::EncodeEmpty();
1333   ret.push_back(kLiveBlobJournalTypeByte);
1334   return ret;
1335 }
1336
1337 DatabaseFreeListKey::DatabaseFreeListKey() : database_id_(-1) {}
1338
1339 bool DatabaseFreeListKey::Decode(StringPiece* slice,
1340                                  DatabaseFreeListKey* result) {
1341   KeyPrefix prefix;
1342   if (!KeyPrefix::Decode(slice, &prefix))
1343     return false;
1344   DCHECK(!prefix.database_id_);
1345   DCHECK(!prefix.object_store_id_);
1346   DCHECK(!prefix.index_id_);
1347   unsigned char type_byte = 0;
1348   if (!DecodeByte(slice, &type_byte))
1349     return false;
1350   DCHECK_EQ(type_byte, kDatabaseFreeListTypeByte);
1351   if (!DecodeVarInt(slice, &result->database_id_))
1352     return false;
1353   return true;
1354 }
1355
1356 std::string DatabaseFreeListKey::Encode(int64 database_id) {
1357   std::string ret = KeyPrefix::EncodeEmpty();
1358   ret.push_back(kDatabaseFreeListTypeByte);
1359   EncodeVarInt(database_id, &ret);
1360   return ret;
1361 }
1362
1363 std::string DatabaseFreeListKey::EncodeMaxKey() {
1364   return Encode(std::numeric_limits<int64>::max());
1365 }
1366
1367 int64 DatabaseFreeListKey::DatabaseId() const {
1368   DCHECK_GE(database_id_, 0);
1369   return database_id_;
1370 }
1371
1372 int DatabaseFreeListKey::Compare(const DatabaseFreeListKey& other) const {
1373   DCHECK_GE(database_id_, 0);
1374   return CompareInts(database_id_, other.database_id_);
1375 }
1376
1377 bool DatabaseNameKey::Decode(StringPiece* slice, DatabaseNameKey* result) {
1378   KeyPrefix prefix;
1379   if (!KeyPrefix::Decode(slice, &prefix))
1380     return false;
1381   DCHECK(!prefix.database_id_);
1382   DCHECK(!prefix.object_store_id_);
1383   DCHECK(!prefix.index_id_);
1384   unsigned char type_byte = 0;
1385   if (!DecodeByte(slice, &type_byte))
1386     return false;
1387   DCHECK_EQ(type_byte, kDatabaseNameTypeByte);
1388   if (!DecodeStringWithLength(slice, &result->origin_))
1389     return false;
1390   if (!DecodeStringWithLength(slice, &result->database_name_))
1391     return false;
1392   return true;
1393 }
1394
1395 std::string DatabaseNameKey::Encode(const std::string& origin_identifier,
1396                                     const base::string16& database_name) {
1397   std::string ret = KeyPrefix::EncodeEmpty();
1398   ret.push_back(kDatabaseNameTypeByte);
1399   EncodeStringWithLength(base::ASCIIToUTF16(origin_identifier), &ret);
1400   EncodeStringWithLength(database_name, &ret);
1401   return ret;
1402 }
1403
1404 std::string DatabaseNameKey::EncodeMinKeyForOrigin(
1405     const std::string& origin_identifier) {
1406   return Encode(origin_identifier, base::string16());
1407 }
1408
1409 std::string DatabaseNameKey::EncodeStopKeyForOrigin(
1410     const std::string& origin_identifier) {
1411   // just after origin in collation order
1412   return EncodeMinKeyForOrigin(origin_identifier + '\x01');
1413 }
1414
1415 int DatabaseNameKey::Compare(const DatabaseNameKey& other) {
1416   if (int x = origin_.compare(other.origin_))
1417     return x;
1418   return database_name_.compare(other.database_name_);
1419 }
1420
1421 bool DatabaseMetaDataKey::IsValidBlobKey(int64 blob_key) {
1422   return blob_key >= kBlobKeyGeneratorInitialNumber;
1423 }
1424
1425 const int64 DatabaseMetaDataKey::kAllBlobsKey = 1;
1426 const int64 DatabaseMetaDataKey::kBlobKeyGeneratorInitialNumber = 2;
1427 const int64 DatabaseMetaDataKey::kInvalidBlobKey = -1;
1428
1429 std::string DatabaseMetaDataKey::Encode(int64 database_id,
1430                                         MetaDataType meta_data_type) {
1431   KeyPrefix prefix(database_id);
1432   std::string ret = prefix.Encode();
1433   ret.push_back(meta_data_type);
1434   return ret;
1435 }
1436
1437 ObjectStoreMetaDataKey::ObjectStoreMetaDataKey()
1438     : object_store_id_(-1), meta_data_type_(-1) {}
1439
1440 bool ObjectStoreMetaDataKey::Decode(StringPiece* slice,
1441                                     ObjectStoreMetaDataKey* result) {
1442   KeyPrefix prefix;
1443   if (!KeyPrefix::Decode(slice, &prefix))
1444     return false;
1445   DCHECK(prefix.database_id_);
1446   DCHECK(!prefix.object_store_id_);
1447   DCHECK(!prefix.index_id_);
1448   unsigned char type_byte = 0;
1449   if (!DecodeByte(slice, &type_byte))
1450     return false;
1451   DCHECK_EQ(type_byte, kObjectStoreMetaDataTypeByte);
1452   if (!DecodeVarInt(slice, &result->object_store_id_))
1453     return false;
1454   DCHECK(result->object_store_id_);
1455   if (!DecodeByte(slice, &result->meta_data_type_))
1456     return false;
1457   return true;
1458 }
1459
1460 std::string ObjectStoreMetaDataKey::Encode(int64 database_id,
1461                                            int64 object_store_id,
1462                                            unsigned char meta_data_type) {
1463   KeyPrefix prefix(database_id);
1464   std::string ret = prefix.Encode();
1465   ret.push_back(kObjectStoreMetaDataTypeByte);
1466   EncodeVarInt(object_store_id, &ret);
1467   ret.push_back(meta_data_type);
1468   return ret;
1469 }
1470
1471 std::string ObjectStoreMetaDataKey::EncodeMaxKey(int64 database_id) {
1472   return Encode(database_id,
1473                 std::numeric_limits<int64>::max(),
1474                 kObjectMetaDataTypeMaximum);
1475 }
1476
1477 std::string ObjectStoreMetaDataKey::EncodeMaxKey(int64 database_id,
1478                                                  int64 object_store_id) {
1479   return Encode(database_id, object_store_id, kObjectMetaDataTypeMaximum);
1480 }
1481
1482 int64 ObjectStoreMetaDataKey::ObjectStoreId() const {
1483   DCHECK_GE(object_store_id_, 0);
1484   return object_store_id_;
1485 }
1486 unsigned char ObjectStoreMetaDataKey::MetaDataType() const {
1487   return meta_data_type_;
1488 }
1489
1490 int ObjectStoreMetaDataKey::Compare(const ObjectStoreMetaDataKey& other) {
1491   DCHECK_GE(object_store_id_, 0);
1492   if (int x = CompareInts(object_store_id_, other.object_store_id_))
1493     return x;
1494   return meta_data_type_ - other.meta_data_type_;
1495 }
1496
1497 IndexMetaDataKey::IndexMetaDataKey()
1498     : object_store_id_(-1), index_id_(-1), meta_data_type_(0) {}
1499
1500 bool IndexMetaDataKey::Decode(StringPiece* slice, IndexMetaDataKey* result) {
1501   KeyPrefix prefix;
1502   if (!KeyPrefix::Decode(slice, &prefix))
1503     return false;
1504   DCHECK(prefix.database_id_);
1505   DCHECK(!prefix.object_store_id_);
1506   DCHECK(!prefix.index_id_);
1507   unsigned char type_byte = 0;
1508   if (!DecodeByte(slice, &type_byte))
1509     return false;
1510   DCHECK_EQ(type_byte, kIndexMetaDataTypeByte);
1511   if (!DecodeVarInt(slice, &result->object_store_id_))
1512     return false;
1513   if (!DecodeVarInt(slice, &result->index_id_))
1514     return false;
1515   if (!DecodeByte(slice, &result->meta_data_type_))
1516     return false;
1517   return true;
1518 }
1519
1520 std::string IndexMetaDataKey::Encode(int64 database_id,
1521                                      int64 object_store_id,
1522                                      int64 index_id,
1523                                      unsigned char meta_data_type) {
1524   KeyPrefix prefix(database_id);
1525   std::string ret = prefix.Encode();
1526   ret.push_back(kIndexMetaDataTypeByte);
1527   EncodeVarInt(object_store_id, &ret);
1528   EncodeVarInt(index_id, &ret);
1529   EncodeByte(meta_data_type, &ret);
1530   return ret;
1531 }
1532
1533 std::string IndexMetaDataKey::EncodeMaxKey(int64 database_id,
1534                                            int64 object_store_id) {
1535   return Encode(database_id,
1536                 object_store_id,
1537                 std::numeric_limits<int64>::max(),
1538                 kIndexMetaDataTypeMaximum);
1539 }
1540
1541 std::string IndexMetaDataKey::EncodeMaxKey(int64 database_id,
1542                                            int64 object_store_id,
1543                                            int64 index_id) {
1544   return Encode(
1545       database_id, object_store_id, index_id, kIndexMetaDataTypeMaximum);
1546 }
1547
1548 int IndexMetaDataKey::Compare(const IndexMetaDataKey& other) {
1549   DCHECK_GE(object_store_id_, 0);
1550   DCHECK_GE(index_id_, 0);
1551
1552   if (int x = CompareInts(object_store_id_, other.object_store_id_))
1553     return x;
1554   if (int x = CompareInts(index_id_, other.index_id_))
1555     return x;
1556   return meta_data_type_ - other.meta_data_type_;
1557 }
1558
1559 int64 IndexMetaDataKey::IndexId() const {
1560   DCHECK_GE(index_id_, 0);
1561   return index_id_;
1562 }
1563
1564 ObjectStoreFreeListKey::ObjectStoreFreeListKey() : object_store_id_(-1) {}
1565
1566 bool ObjectStoreFreeListKey::Decode(StringPiece* slice,
1567                                     ObjectStoreFreeListKey* result) {
1568   KeyPrefix prefix;
1569   if (!KeyPrefix::Decode(slice, &prefix))
1570     return false;
1571   DCHECK(prefix.database_id_);
1572   DCHECK(!prefix.object_store_id_);
1573   DCHECK(!prefix.index_id_);
1574   unsigned char type_byte = 0;
1575   if (!DecodeByte(slice, &type_byte))
1576     return false;
1577   DCHECK_EQ(type_byte, kObjectStoreFreeListTypeByte);
1578   if (!DecodeVarInt(slice, &result->object_store_id_))
1579     return false;
1580   return true;
1581 }
1582
1583 std::string ObjectStoreFreeListKey::Encode(int64 database_id,
1584                                            int64 object_store_id) {
1585   KeyPrefix prefix(database_id);
1586   std::string ret = prefix.Encode();
1587   ret.push_back(kObjectStoreFreeListTypeByte);
1588   EncodeVarInt(object_store_id, &ret);
1589   return ret;
1590 }
1591
1592 std::string ObjectStoreFreeListKey::EncodeMaxKey(int64 database_id) {
1593   return Encode(database_id, std::numeric_limits<int64>::max());
1594 }
1595
1596 int64 ObjectStoreFreeListKey::ObjectStoreId() const {
1597   DCHECK_GE(object_store_id_, 0);
1598   return object_store_id_;
1599 }
1600
1601 int ObjectStoreFreeListKey::Compare(const ObjectStoreFreeListKey& other) {
1602   // TODO(jsbell): It may seem strange that we're not comparing database id's,
1603   // but that comparison will have been made earlier.
1604   // We should probably make this more clear, though...
1605   DCHECK_GE(object_store_id_, 0);
1606   return CompareInts(object_store_id_, other.object_store_id_);
1607 }
1608
1609 IndexFreeListKey::IndexFreeListKey() : object_store_id_(-1), index_id_(-1) {}
1610
1611 bool IndexFreeListKey::Decode(StringPiece* slice, IndexFreeListKey* result) {
1612   KeyPrefix prefix;
1613   if (!KeyPrefix::Decode(slice, &prefix))
1614     return false;
1615   DCHECK(prefix.database_id_);
1616   DCHECK(!prefix.object_store_id_);
1617   DCHECK(!prefix.index_id_);
1618   unsigned char type_byte = 0;
1619   if (!DecodeByte(slice, &type_byte))
1620     return false;
1621   DCHECK_EQ(type_byte, kIndexFreeListTypeByte);
1622   if (!DecodeVarInt(slice, &result->object_store_id_))
1623     return false;
1624   if (!DecodeVarInt(slice, &result->index_id_))
1625     return false;
1626   return true;
1627 }
1628
1629 std::string IndexFreeListKey::Encode(int64 database_id,
1630                                      int64 object_store_id,
1631                                      int64 index_id) {
1632   KeyPrefix prefix(database_id);
1633   std::string ret = prefix.Encode();
1634   ret.push_back(kIndexFreeListTypeByte);
1635   EncodeVarInt(object_store_id, &ret);
1636   EncodeVarInt(index_id, &ret);
1637   return ret;
1638 }
1639
1640 std::string IndexFreeListKey::EncodeMaxKey(int64 database_id,
1641                                            int64 object_store_id) {
1642   return Encode(
1643       database_id, object_store_id, std::numeric_limits<int64>::max());
1644 }
1645
1646 int IndexFreeListKey::Compare(const IndexFreeListKey& other) {
1647   DCHECK_GE(object_store_id_, 0);
1648   DCHECK_GE(index_id_, 0);
1649   if (int x = CompareInts(object_store_id_, other.object_store_id_))
1650     return x;
1651   return CompareInts(index_id_, other.index_id_);
1652 }
1653
1654 int64 IndexFreeListKey::ObjectStoreId() const {
1655   DCHECK_GE(object_store_id_, 0);
1656   return object_store_id_;
1657 }
1658
1659 int64 IndexFreeListKey::IndexId() const {
1660   DCHECK_GE(index_id_, 0);
1661   return index_id_;
1662 }
1663
1664 // TODO(jsbell): We never use this to look up object store ids,
1665 // because a mapping is kept in the IndexedDBDatabase. Can the
1666 // mapping become unreliable?  Can we remove this?
1667 bool ObjectStoreNamesKey::Decode(StringPiece* slice,
1668                                  ObjectStoreNamesKey* result) {
1669   KeyPrefix prefix;
1670   if (!KeyPrefix::Decode(slice, &prefix))
1671     return false;
1672   DCHECK(prefix.database_id_);
1673   DCHECK(!prefix.object_store_id_);
1674   DCHECK(!prefix.index_id_);
1675   unsigned char type_byte = 0;
1676   if (!DecodeByte(slice, &type_byte))
1677     return false;
1678   DCHECK_EQ(type_byte, kObjectStoreNamesTypeByte);
1679   if (!DecodeStringWithLength(slice, &result->object_store_name_))
1680     return false;
1681   return true;
1682 }
1683
1684 std::string ObjectStoreNamesKey::Encode(
1685     int64 database_id,
1686     const base::string16& object_store_name) {
1687   KeyPrefix prefix(database_id);
1688   std::string ret = prefix.Encode();
1689   ret.push_back(kObjectStoreNamesTypeByte);
1690   EncodeStringWithLength(object_store_name, &ret);
1691   return ret;
1692 }
1693
1694 int ObjectStoreNamesKey::Compare(const ObjectStoreNamesKey& other) {
1695   return object_store_name_.compare(other.object_store_name_);
1696 }
1697
1698 IndexNamesKey::IndexNamesKey() : object_store_id_(-1) {}
1699
1700 // TODO(jsbell): We never use this to look up index ids, because a mapping
1701 // is kept at a higher level.
1702 bool IndexNamesKey::Decode(StringPiece* slice, IndexNamesKey* result) {
1703   KeyPrefix prefix;
1704   if (!KeyPrefix::Decode(slice, &prefix))
1705     return false;
1706   DCHECK(prefix.database_id_);
1707   DCHECK(!prefix.object_store_id_);
1708   DCHECK(!prefix.index_id_);
1709   unsigned char type_byte = 0;
1710   if (!DecodeByte(slice, &type_byte))
1711     return false;
1712   DCHECK_EQ(type_byte, kIndexNamesKeyTypeByte);
1713   if (!DecodeVarInt(slice, &result->object_store_id_))
1714     return false;
1715   if (!DecodeStringWithLength(slice, &result->index_name_))
1716     return false;
1717   return true;
1718 }
1719
1720 std::string IndexNamesKey::Encode(int64 database_id,
1721                                   int64 object_store_id,
1722                                   const base::string16& index_name) {
1723   KeyPrefix prefix(database_id);
1724   std::string ret = prefix.Encode();
1725   ret.push_back(kIndexNamesKeyTypeByte);
1726   EncodeVarInt(object_store_id, &ret);
1727   EncodeStringWithLength(index_name, &ret);
1728   return ret;
1729 }
1730
1731 int IndexNamesKey::Compare(const IndexNamesKey& other) {
1732   DCHECK_GE(object_store_id_, 0);
1733   if (int x = CompareInts(object_store_id_, other.object_store_id_))
1734     return x;
1735   return index_name_.compare(other.index_name_);
1736 }
1737
1738 ObjectStoreDataKey::ObjectStoreDataKey() {}
1739 ObjectStoreDataKey::~ObjectStoreDataKey() {}
1740
1741 bool ObjectStoreDataKey::Decode(StringPiece* slice,
1742                                 ObjectStoreDataKey* result) {
1743   KeyPrefix prefix;
1744   if (!KeyPrefix::Decode(slice, &prefix))
1745     return false;
1746   DCHECK(prefix.database_id_);
1747   DCHECK(prefix.object_store_id_);
1748   DCHECK_EQ(prefix.index_id_, kSpecialIndexNumber);
1749   if (!ExtractEncodedIDBKey(slice, &result->encoded_user_key_))
1750     return false;
1751   return true;
1752 }
1753
1754 std::string ObjectStoreDataKey::Encode(int64 database_id,
1755                                        int64 object_store_id,
1756                                        const std::string encoded_user_key) {
1757   KeyPrefix prefix(KeyPrefix::CreateWithSpecialIndex(
1758       database_id, object_store_id, kSpecialIndexNumber));
1759   std::string ret = prefix.Encode();
1760   ret.append(encoded_user_key);
1761
1762   return ret;
1763 }
1764
1765 std::string ObjectStoreDataKey::Encode(int64 database_id,
1766                                        int64 object_store_id,
1767                                        const IndexedDBKey& user_key) {
1768   std::string encoded_key;
1769   EncodeIDBKey(user_key, &encoded_key);
1770   return Encode(database_id, object_store_id, encoded_key);
1771 }
1772
1773 scoped_ptr<IndexedDBKey> ObjectStoreDataKey::user_key() const {
1774   scoped_ptr<IndexedDBKey> key;
1775   StringPiece slice(encoded_user_key_);
1776   if (!DecodeIDBKey(&slice, &key)) {
1777     // TODO(jsbell): Return error.
1778   }
1779   return key.Pass();
1780 }
1781
1782 const int64 ObjectStoreDataKey::kSpecialIndexNumber = kObjectStoreDataIndexId;
1783
1784 ExistsEntryKey::ExistsEntryKey() {}
1785 ExistsEntryKey::~ExistsEntryKey() {}
1786
1787 bool ExistsEntryKey::Decode(StringPiece* slice, ExistsEntryKey* result) {
1788   KeyPrefix prefix;
1789   if (!KeyPrefix::Decode(slice, &prefix))
1790     return false;
1791   DCHECK(prefix.database_id_);
1792   DCHECK(prefix.object_store_id_);
1793   DCHECK_EQ(prefix.index_id_, kSpecialIndexNumber);
1794   if (!ExtractEncodedIDBKey(slice, &result->encoded_user_key_))
1795     return false;
1796   return true;
1797 }
1798
1799 std::string ExistsEntryKey::Encode(int64 database_id,
1800                                    int64 object_store_id,
1801                                    const std::string& encoded_key) {
1802   KeyPrefix prefix(KeyPrefix::CreateWithSpecialIndex(
1803       database_id, object_store_id, kSpecialIndexNumber));
1804   std::string ret = prefix.Encode();
1805   ret.append(encoded_key);
1806   return ret;
1807 }
1808
1809 std::string ExistsEntryKey::Encode(int64 database_id,
1810                                    int64 object_store_id,
1811                                    const IndexedDBKey& user_key) {
1812   std::string encoded_key;
1813   EncodeIDBKey(user_key, &encoded_key);
1814   return Encode(database_id, object_store_id, encoded_key);
1815 }
1816
1817 scoped_ptr<IndexedDBKey> ExistsEntryKey::user_key() const {
1818   scoped_ptr<IndexedDBKey> key;
1819   StringPiece slice(encoded_user_key_);
1820   if (!DecodeIDBKey(&slice, &key)) {
1821     // TODO(jsbell): Return error.
1822   }
1823   return key.Pass();
1824 }
1825
1826 const int64 ExistsEntryKey::kSpecialIndexNumber = kExistsEntryIndexId;
1827
1828 bool BlobEntryKey::Decode(StringPiece* slice, BlobEntryKey* result) {
1829   KeyPrefix prefix;
1830   if (!KeyPrefix::Decode(slice, &prefix))
1831     return false;
1832   DCHECK(prefix.database_id_);
1833   DCHECK(prefix.object_store_id_);
1834   DCHECK_EQ(prefix.index_id_, kSpecialIndexNumber);
1835
1836   if (!ExtractEncodedIDBKey(slice, &result->encoded_user_key_))
1837     return false;
1838   result->database_id_ = prefix.database_id_;
1839   result->object_store_id_ = prefix.object_store_id_;
1840
1841   return true;
1842 }
1843
1844 bool BlobEntryKey::FromObjectStoreDataKey(StringPiece* slice,
1845                                           BlobEntryKey* result) {
1846   KeyPrefix prefix;
1847   if (!KeyPrefix::Decode(slice, &prefix))
1848     return false;
1849   DCHECK(prefix.database_id_);
1850   DCHECK(prefix.object_store_id_);
1851   DCHECK_EQ(prefix.index_id_, ObjectStoreDataKey::kSpecialIndexNumber);
1852
1853   if (!ExtractEncodedIDBKey(slice, &result->encoded_user_key_))
1854     return false;
1855   result->database_id_ = prefix.database_id_;
1856   result->object_store_id_ = prefix.object_store_id_;
1857   return true;
1858 }
1859
1860 std::string BlobEntryKey::ReencodeToObjectStoreDataKey(StringPiece* slice) {
1861   // TODO(ericu): We could be more efficient here, since the suffix is the same.
1862   BlobEntryKey key;
1863   if (!Decode(slice, &key))
1864     return std::string();
1865
1866   return ObjectStoreDataKey::Encode(
1867       key.database_id_, key.object_store_id_, key.encoded_user_key_);
1868 }
1869
1870 std::string BlobEntryKey::EncodeMinKeyForObjectStore(int64 database_id,
1871                                                      int64 object_store_id) {
1872   // Our implied encoded_user_key_ here is empty, the lowest possible key.
1873   return Encode(database_id, object_store_id, std::string());
1874 }
1875
1876 std::string BlobEntryKey::EncodeStopKeyForObjectStore(int64 database_id,
1877                                                       int64 object_store_id) {
1878   DCHECK(KeyPrefix::ValidIds(database_id, object_store_id));
1879   KeyPrefix prefix(KeyPrefix::CreateWithSpecialIndex(
1880       database_id, object_store_id, kSpecialIndexNumber + 1));
1881   return prefix.Encode();
1882 }
1883
1884 std::string BlobEntryKey::Encode() const {
1885   DCHECK(!encoded_user_key_.empty());
1886   return Encode(database_id_, object_store_id_, encoded_user_key_);
1887 }
1888
1889 std::string BlobEntryKey::Encode(int64 database_id,
1890                                  int64 object_store_id,
1891                                  const IndexedDBKey& user_key) {
1892   std::string encoded_key;
1893   EncodeIDBKey(user_key, &encoded_key);
1894   return Encode(database_id, object_store_id, encoded_key);
1895 }
1896
1897 std::string BlobEntryKey::Encode(int64 database_id,
1898                                  int64 object_store_id,
1899                                  const std::string& encoded_user_key) {
1900   DCHECK(KeyPrefix::ValidIds(database_id, object_store_id));
1901   KeyPrefix prefix(KeyPrefix::CreateWithSpecialIndex(
1902       database_id, object_store_id, kSpecialIndexNumber));
1903   return prefix.Encode() + encoded_user_key;
1904 }
1905
1906 const int64 BlobEntryKey::kSpecialIndexNumber = kBlobEntryIndexId;
1907
1908 IndexDataKey::IndexDataKey()
1909     : database_id_(-1),
1910       object_store_id_(-1),
1911       index_id_(-1),
1912       sequence_number_(-1) {}
1913
1914 IndexDataKey::~IndexDataKey() {}
1915
1916 bool IndexDataKey::Decode(StringPiece* slice, IndexDataKey* result) {
1917   KeyPrefix prefix;
1918   if (!KeyPrefix::Decode(slice, &prefix))
1919     return false;
1920   DCHECK(prefix.database_id_);
1921   DCHECK(prefix.object_store_id_);
1922   DCHECK_GE(prefix.index_id_, kMinimumIndexId);
1923   result->database_id_ = prefix.database_id_;
1924   result->object_store_id_ = prefix.object_store_id_;
1925   result->index_id_ = prefix.index_id_;
1926   result->sequence_number_ = -1;
1927   result->encoded_primary_key_ = MinIDBKey();
1928
1929   if (!ExtractEncodedIDBKey(slice, &result->encoded_user_key_))
1930     return false;
1931
1932   // [optional] sequence number
1933   if (slice->empty())
1934     return true;
1935   if (!DecodeVarInt(slice, &result->sequence_number_))
1936     return false;
1937
1938   // [optional] primary key
1939   if (slice->empty())
1940     return true;
1941   if (!ExtractEncodedIDBKey(slice, &result->encoded_primary_key_))
1942     return false;
1943   return true;
1944 }
1945
1946 std::string IndexDataKey::Encode(int64 database_id,
1947                                  int64 object_store_id,
1948                                  int64 index_id,
1949                                  const std::string& encoded_user_key,
1950                                  const std::string& encoded_primary_key,
1951                                  int64 sequence_number) {
1952   KeyPrefix prefix(database_id, object_store_id, index_id);
1953   std::string ret = prefix.Encode();
1954   ret.append(encoded_user_key);
1955   EncodeVarInt(sequence_number, &ret);
1956   ret.append(encoded_primary_key);
1957   return ret;
1958 }
1959
1960 std::string IndexDataKey::Encode(int64 database_id,
1961                                  int64 object_store_id,
1962                                  int64 index_id,
1963                                  const IndexedDBKey& user_key) {
1964   std::string encoded_key;
1965   EncodeIDBKey(user_key, &encoded_key);
1966   return Encode(
1967       database_id, object_store_id, index_id, encoded_key, MinIDBKey(), 0);
1968 }
1969
1970 std::string IndexDataKey::Encode(int64 database_id,
1971                                  int64 object_store_id,
1972                                  int64 index_id,
1973                                  const IndexedDBKey& user_key,
1974                                  const IndexedDBKey& user_primary_key) {
1975   std::string encoded_key;
1976   EncodeIDBKey(user_key, &encoded_key);
1977   std::string encoded_primary_key;
1978   EncodeIDBKey(user_primary_key, &encoded_primary_key);
1979   return Encode(database_id,
1980                 object_store_id,
1981                 index_id,
1982                 encoded_key,
1983                 encoded_primary_key,
1984                 0);
1985 }
1986
1987 std::string IndexDataKey::EncodeMinKey(int64 database_id,
1988                                        int64 object_store_id,
1989                                        int64 index_id) {
1990   return Encode(
1991       database_id, object_store_id, index_id, MinIDBKey(), MinIDBKey(), 0);
1992 }
1993
1994 std::string IndexDataKey::EncodeMaxKey(int64 database_id,
1995                                        int64 object_store_id,
1996                                        int64 index_id) {
1997   return Encode(database_id,
1998                 object_store_id,
1999                 index_id,
2000                 MaxIDBKey(),
2001                 MaxIDBKey(),
2002                 std::numeric_limits<int64>::max());
2003 }
2004
2005 int64 IndexDataKey::DatabaseId() const {
2006   DCHECK_GE(database_id_, 0);
2007   return database_id_;
2008 }
2009
2010 int64 IndexDataKey::ObjectStoreId() const {
2011   DCHECK_GE(object_store_id_, 0);
2012   return object_store_id_;
2013 }
2014
2015 int64 IndexDataKey::IndexId() const {
2016   DCHECK_GE(index_id_, 0);
2017   return index_id_;
2018 }
2019
2020 scoped_ptr<IndexedDBKey> IndexDataKey::user_key() const {
2021   scoped_ptr<IndexedDBKey> key;
2022   StringPiece slice(encoded_user_key_);
2023   if (!DecodeIDBKey(&slice, &key)) {
2024     // TODO(jsbell): Return error.
2025   }
2026   return key.Pass();
2027 }
2028
2029 scoped_ptr<IndexedDBKey> IndexDataKey::primary_key() const {
2030   scoped_ptr<IndexedDBKey> key;
2031   StringPiece slice(encoded_primary_key_);
2032   if (!DecodeIDBKey(&slice, &key)) {
2033     // TODO(jsbell): Return error.
2034   }
2035   return key.Pass();
2036 }
2037
2038 }  // namespace content