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