code.vuplus.com Git - vuplus_webkit/blob - Source/WebCore/storage/IDBLevelDBCoding.cpp

   1 /*
   2  * Copyright (C) 2011 Google Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * 1.  Redistributions of source code must retain the above copyright
   9  *     notice, this list of conditions and the following disclaimer.
  10  * 2.  Redistributions in binary form must reproduce the above copyright
  11  *     notice, this list of conditions and the following disclaimer in the
  12  *     documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
  15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  16  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  17  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
  18  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  19  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  20  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  21  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  23  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "IDBLevelDBCoding.h"
  28
  29 #if ENABLE(INDEXED_DATABASE)
  30 #if ENABLE(LEVELDB)
  31
  32 #include "IDBKey.h"
  33 #include "LevelDBSlice.h"
  34 #include <wtf/text/StringBuilder.h>
  35
  36 // LevelDB stores key/value pairs. Keys and values are strings of bytes, normally of type Vector<char>.
  37 //
  38 // The keys in the backing store are variable-length tuples with different types
  39 // of fields. Each key in the backing store starts with a ternary prefix: (database id, object store id, index id). For each, 0 is reserved for meta-data.
  40 // The prefix makes sure that data for a specific database, object store, and index are grouped together. The locality is important for performance: common
  41 // operations should only need a minimal number of seek operations. For example, all the meta-data for a database is grouped together so that reading that
  42 // meta-data only requires one seek.
  43 //
  44 // Each key type has a class (in square brackets below) which knows how to encode, decode, and compare that key type.
  45 //
  46 // Global meta-data have keys with prefix (0,0,0), followed by a type byte:
  47 //
  48 //     <0, 0, 0, 0>                                           => IndexedDB/LevelDB schema version (0 for now) [SchemaVersionKey]
  49 //     <0, 0, 0, 1>                                           => The maximum database id ever allocated [MaxDatabaseIdKey]
  50 //     <0, 0, 0, 100, database id>                            => Existence implies the database id is in the free list [DatabaseFreeListKey]
  51 //     <0, 0, 0, 201, utf16 origin name, utf16 database name> => Database id [DatabaseNameKey]
  52 //
  53 //
  54 // Database meta-data:
  55 //
  56 //     Again, the prefix is followed by a type byte.
  57 //
  58 //     <database id, 0, 0, 0> => utf16 origin name [DatabaseMetaDataKey]
  59 //     <database id, 0, 0, 1> => utf16 database name [DatabaseMetaDataKey]
  60 //     <database id, 0, 0, 2> => utf16 user version data [DatabaseMetaDataKey]
  61 //     <database id, 0, 0, 3> => maximum object store id ever allocated [DatabaseMetaDataKey]
  62 //
  63 //
  64 // Object store meta-data:
  65 //
  66 //     The prefix is followed by a type byte, then a variable-length integer, and then another variable-length integer (FIXME: this should be a byte).
  67 //
  68 //     <database id, 0, 0, 50, object store id, 0> => utf16 object store name [ObjectStoreMetaDataKey]
  69 //     <database id, 0, 0, 50, object store id, 1> => utf16 key path [ObjectStoreMetaDataKey]
  70 //     <database id, 0, 0, 50, object store id, 2> => has auto increment [ObjectStoreMetaDataKey]
  71 //     <database id, 0, 0, 50, object store id, 3> => is evictable [ObjectStoreMetaDataKey]
  72 //     <database id, 0, 0, 50, object store id, 4> => last "version" number [ObjectStoreMetaDataKey]
  73 //     <database id, 0, 0, 50, object store id, 5> => maximum index id ever allocated [ObjectStoreMetaDataKey]
  74 //
  75 //
  76 // Index meta-data:
  77 //
  78 //     The prefix is followed by a type byte, then two variable-length integers, and then another type byte.
  79 //
  80 //     <database id, 0, 0, 100, object store id, index id, 0> => utf16 index name [IndexMetaDataKey]
  81 //     <database id, 0, 0, 100, object store id, index id, 1> => are index keys unique [IndexMetaDataKey]
  82 //     <database id, 0, 0, 100, object store id, index id, 2> => utf16 key path [IndexMetaDataKey]
  83 //
  84 //
  85 // Other object store and index meta-data:
  86 //
  87 //     The prefix is followed by a type byte. The object store and index id are variable length integers, the utf16 strings are variable length strings.
  88 //
  89 //     <database id, 0, 0, 150, object store id>                   => existence implies the object store id is in the free list [ObjectStoreFreeListKey]
  90 //     <database id, 0, 0, 151, object store id, index id>         => existence implies the index id is in the free list [IndexFreeListKey]
  91 //     <database id, 0, 0, 200, utf16 object store name>           => object store id [ObjectStoreNamesKey]
  92 //     <database id, 0, 0, 201, object store id, utf16 index name> => index id [IndexNamesKey]
  93 //
  94 //
  95 // Object store data:
  96 //
  97 //     The prefix is followed by a type byte. The user key is an encoded IDBKey.
  98 //
  99 //     <database id, object store id, 1, user key> => "version", serialized script value [ObjectStoreDataKey]
 100 //
 101 //
 102 // "Exists" entry:
 103 //
 104 //     The prefix is followed by a type byte. The user key is an encoded IDBKey.
 105 //
 106 //     <database id, object store id, 2, user key> => "version" [ExistsEntryKey]
 107 //
 108 //
 109 // Index data:
 110 //
 111 //     The prefix is followed by a type byte. The user key is an encoded IDBKey. The sequence number is a variable length integer.
 112 //
 113 //     <database id, object store id, index id, user key, sequence number> => "version", user key [IndexDataKey]
 114 //
 115 //     (The sequence number is used to allow two entries with the same user key
 116 //     in non-unique indexes. The "version" field is used to weed out stale
 117 //     index data. Whenever new object store data is inserted, it gets a new
 118 //     "version" number, and new index data is written with this number. When
 119 //     the index is used for look-ups, entries are validated against the
 120 //     "exists" entries, and records with old "version" numbers are deleted
 121 //     when they are encountered in getPrimaryKeyViaIndex,
 122 //     IndexCursorImpl::loadCurrentRow, and IndexKeyCursorImpl::loadCurrentRow).
 123
 124 namespace WebCore {
 125 namespace IDBLevelDBCoding {
 126
 127 static const unsigned char kIDBKeyNullTypeByte = 0;
 128 static const unsigned char kIDBKeyStringTypeByte = 1;
 129 static const unsigned char kIDBKeyDateTypeByte = 2;
 130 static const unsigned char kIDBKeyNumberTypeByte = 3;
 131 static const unsigned char kIDBKeyMinKeyTypeByte = 4;
 132
 133 static const unsigned char kObjectStoreDataIndexId = 1;
 134 static const unsigned char kExistsEntryIndexId = 2;
 135
 136 static const unsigned char kSchemaVersionTypeByte = 0;
 137 static const unsigned char kMaxDatabaseIdTypeByte = 1;
 138 static const unsigned char kDatabaseFreeListTypeByte = 100;
 139 static const unsigned char kDatabaseNameTypeByte = 201;
 140
 141 static const unsigned char kObjectStoreMetaDataTypeByte = 50;
 142 static const unsigned char kIndexMetaDataTypeByte = 100;
 143 static const unsigned char kObjectStoreFreeListTypeByte = 150;
 144 static const unsigned char kIndexFreeListTypeByte = 151;
 145 static const unsigned char kObjectStoreNamesTypeByte = 200;
 146 static const unsigned char kIndexNamesKeyTypeByte = 201;
 147
 148 #ifndef INT64_MAX
 149 #define INT64_MAX 0x7fffffffffffffffLL
 150 #endif
 151 #ifndef INT32_MAX
 152 #define INT32_MAX 0x7fffffffL
 153 #endif
 154
 155
 156 Vector<char> encodeByte(unsigned char c)
 157 {
 158     Vector<char> v;
 159     v.append(c);
 160     return v;
 161 }
 162
 163 Vector<char> maxIDBKey()
 164 {
 165     return encodeByte(kIDBKeyNullTypeByte);
 166 }
 167
 168 Vector<char> minIDBKey()
 169 {
 170     return encodeByte(kIDBKeyMinKeyTypeByte);
 171 }
 172
 173 Vector<char> encodeInt(int64_t n)
 174 {
 175     ASSERT(n >= 0);
 176     Vector<char> ret; // FIXME: Size this at creation.
 177
 178     do {
 179         unsigned char c = n;
 180         ret.append(c);
 181         n >>= 8;
 182     } while (n);
 183
 184     return ret;
 185 }
 186
 187 int64_t decodeInt(const char* begin, const char* end)
 188 {
 189     ASSERT(begin <= end);
 190     int64_t ret = 0;
 191
 192     int shift = 0;
 193     while (begin < end) {
 194         unsigned char c = *begin++;
 195         ret |= static_cast<int64_t>(c) << shift;
 196         shift += 8;
 197     }
 198
 199     return ret;
 200 }
 201
 202 static int compareInts(int64_t a, int64_t b)
 203 {
 204     ASSERT(a >= 0);
 205     ASSERT(b >= 0);
 206
 207     int64_t diff = a - b;
 208     if (diff < 0)
 209         return -1;
 210     if (diff > 0)
 211         return 1;
 212     return 0;
 213 }
 214
 215 Vector<char> encodeVarInt(int64_t n)
 216 {
 217     Vector<char> ret; // FIXME: Size this at creation.
 218
 219     do {
 220         unsigned char c = n & 0x7f;
 221         n >>= 7;
 222         if (n)
 223             c |= 0x80;
 224         ret.append(c);
 225     } while (n);
 226
 227     return ret;
 228 }
 229
 230 const char* decodeVarInt(const char *p, const char* limit, int64_t& foundInt)
 231 {
 232     ASSERT(limit >= p);
 233     foundInt = 0;
 234     int shift = 0;
 235
 236     do {
 237         if (p >= limit)
 238             return 0;
 239
 240         unsigned char c = *p;
 241         foundInt |= static_cast<int64_t>(c & 0x7f) << shift;
 242         shift += 7;
 243     } while (*p++ & 0x80);
 244     return p;
 245 }
 246
 247 Vector<char> encodeString(const String& s)
 248 {
 249     Vector<char> ret; // FIXME: Size this at creation.
 250
 251     for (unsigned i = 0; i < s.length(); ++i) {
 252         UChar u = s[i];
 253         unsigned char hi = u >> 8;
 254         unsigned char lo = u;
 255         ret.append(hi);
 256         ret.append(lo);
 257     }
 258
 259     return ret;
 260 }
 261
 262 String decodeString(const char* p, const char* end)
 263 {
 264     ASSERT(end >= p);
 265     ASSERT(!((end - p) % 2));
 266
 267     size_t len = (end - p) / 2;
 268     StringBuilder result;
 269     result.reserveCapacity(len);
 270
 271     for (size_t i = 0; i < len; ++i) {
 272         unsigned char hi = *p++;
 273         unsigned char lo = *p++;
 274
 275         result.append(static_cast<UChar>((hi << 8) | lo));
 276     }
 277
 278     return result.toString();
 279 }
 280
 281 Vector<char> encodeStringWithLength(const String& s)
 282 {
 283     Vector<char> ret = encodeVarInt(s.length());
 284     ret.append(encodeString(s));
 285     return ret;
 286 }
 287
 288 const char* decodeStringWithLength(const char* p, const char* limit, String& foundString)
 289 {
 290     ASSERT(limit >= p);
 291     int64_t len;
 292     p = decodeVarInt(p, limit, len);
 293     if (!p)
 294         return 0;
 295     if (p + len * 2 > limit)
 296         return 0;
 297
 298     foundString = decodeString(p, p + len * 2);
 299     p += len * 2;
 300     return p;
 301 }
 302
 303 Vector<char> encodeDouble(double x)
 304 {
 305     // FIXME: It would be nice if we could be byte order independent.
 306     const char* p = reinterpret_cast<char*>(&x);
 307     Vector<char> v;
 308     v.append(p, sizeof(x));
 309     ASSERT(v.size() == sizeof(x));
 310     return v;
 311 }
 312
 313 const char* decodeDouble(const char* p, const char* limit, double* d)
 314 {
 315     if (p + sizeof(*d) > limit)
 316         return 0;
 317
 318     char* x = reinterpret_cast<char*>(d);
 319     for (size_t i = 0; i < sizeof(*d); ++i)
 320         *x++ = *p++;
 321     return p;
 322 }
 323
 324 Vector<char> encodeIDBKey(const IDBKey& key)
 325 {
 326     Vector<char> ret;
 327
 328     switch (key.type()) {
 329     case IDBKey::NullType:
 330         return encodeByte(kIDBKeyNullTypeByte);
 331     case IDBKey::StringType:
 332         ret = encodeByte(kIDBKeyStringTypeByte);
 333         ret.append(encodeStringWithLength(key.string()));
 334         return ret;
 335     case IDBKey::DateType:
 336         ret = encodeByte(kIDBKeyDateTypeByte);
 337         ret.append(encodeDouble(key.date()));
 338         ASSERT(ret.size() == 9);
 339         return ret;
 340     case IDBKey::NumberType:
 341         ret = encodeByte(kIDBKeyNumberTypeByte);
 342         ret.append(encodeDouble(key.number()));
 343         ASSERT(ret.size() == 9);
 344         return ret;
 345     }
 346
 347     ASSERT_NOT_REACHED();
 348     return Vector<char>();
 349 }
 350
 351 const char* decodeIDBKey(const char* p, const char* limit, RefPtr<IDBKey>& foundKey)
 352 {
 353     ASSERT(limit >= p);
 354     if (p >= limit)
 355         return 0;
 356
 357     unsigned char type = *p++;
 358     String s;
 359     double d;
 360
 361     switch (type) {
 362     case kIDBKeyNullTypeByte:
 363         // Null.
 364         foundKey = IDBKey::createNull();
 365         return p;
 366     case kIDBKeyStringTypeByte:
 367         // String.
 368         p = decodeStringWithLength(p, limit, s);
 369         if (!p)
 370             return 0;
 371         foundKey = IDBKey::createString(s);
 372         return p;
 373     case kIDBKeyDateTypeByte:
 374         // Date.
 375         p = decodeDouble(p, limit, &d);
 376         if (!p)
 377             return 0;
 378         foundKey = IDBKey::createDate(d);
 379         return p;
 380     case kIDBKeyNumberTypeByte:
 381         // Number.
 382         p = decodeDouble(p, limit, &d);
 383         if (!p)
 384             return 0;
 385         foundKey = IDBKey::createNumber(d);
 386         return p;
 387     }
 388
 389     ASSERT_NOT_REACHED();
 390     return 0;
 391 }
 392
 393 const char* extractEncodedIDBKey(const char* start, const char* limit, Vector<char>* result)
 394 {
 395     const char* p = start;
 396     if (p >= limit)
 397         return 0;
 398
 399     unsigned char type = *p++;
 400
 401     int64_t stringLen;
 402
 403     switch (type) {
 404     case kIDBKeyNullTypeByte:
 405     case kIDBKeyMinKeyTypeByte:
 406         *result = encodeByte(type);
 407         return p;
 408     case kIDBKeyStringTypeByte:
 409         // String.
 410         p = decodeVarInt(p, limit, stringLen);
 411         if (!p)
 412             return 0;
 413         if (p + stringLen * 2 > limit)
 414             return 0;
 415         result->clear();
 416         result->append(start, p - start + stringLen * 2);
 417         return p + stringLen * 2;
 418     case kIDBKeyDateTypeByte:
 419     case kIDBKeyNumberTypeByte:
 420         // Date or number.
 421         if (p + sizeof(double) > limit)
 422             return 0;
 423         result->clear();
 424         result->append(start, 1 + sizeof(double));
 425         return p + sizeof(double);
 426     }
 427     ASSERT_NOT_REACHED();
 428     return 0;
 429 }
 430
 431 int compareEncodedIDBKeys(const Vector<char>& keyA, const Vector<char>& keyB)
 432 {
 433     ASSERT(keyA.size() >= 1);
 434     ASSERT(keyB.size() >= 1);
 435
 436     const char* p = keyA.data();
 437     const char* limitA = p + keyA.size();
 438     const char* q = keyB.data();
 439     const char* limitB = q + keyB.size();
 440
 441     unsigned char typeA = *p++;
 442     unsigned char typeB = *q++;
 443
 444     String s, t;
 445     double d, e;
 446
 447     if (int x = typeB - typeA) // FIXME: Note the subtleness!
 448         return x;
 449
 450     switch (typeA) {
 451     case kIDBKeyNullTypeByte:
 452     case kIDBKeyMinKeyTypeByte:
 453         // Null type or max type; no payload to compare.
 454         return 0;
 455     case kIDBKeyStringTypeByte:
 456         // String type.
 457         p = decodeStringWithLength(p, limitA, s); // FIXME: Compare without actually decoding the String!
 458         ASSERT(p);
 459         q = decodeStringWithLength(q, limitB, t);
 460         ASSERT(q);
 461         return codePointCompare(s, t);
 462     case kIDBKeyDateTypeByte:
 463     case kIDBKeyNumberTypeByte:
 464         // Date or number.
 465         p = decodeDouble(p, limitA, &d);
 466         ASSERT(p);
 467         q = decodeDouble(q, limitB, &e);
 468         ASSERT(q);
 469         if (d < e)
 470             return -1;
 471         if (d > e)
 472             return 1;
 473         return 0;
 474     }
 475
 476     ASSERT_NOT_REACHED();
 477     return 0;
 478 }
 479
 480 namespace {
 481 template<typename KeyType>
 482 int decodeAndCompare(const LevelDBSlice& a, const LevelDBSlice& b)
 483 {
 484     KeyType keyA;
 485     KeyType keyB;
 486
 487     const char* ptrA = KeyType::decode(a.begin(), a.end(), &keyA);
 488     ASSERT_UNUSED(ptrA, ptrA);
 489     const char* ptrB = KeyType::decode(b.begin(), b.end(), &keyB);
 490     ASSERT_UNUSED(ptrB, ptrB);
 491
 492     return keyA.compare(keyB);
 493 }
 494 }
 495
 496 int compare(const LevelDBSlice& a, const LevelDBSlice& b, bool indexKeys)
 497 {
 498     const char* ptrA = a.begin();
 499     const char* ptrB = b.begin();
 500     const char* endA = a.end();
 501     const char* endB = b.end();
 502
 503     KeyPrefix prefixA;
 504     KeyPrefix prefixB;
 505
 506     ptrA = KeyPrefix::decode(ptrA, endA, &prefixA);
 507     ptrB = KeyPrefix::decode(ptrB, endB, &prefixB);
 508     ASSERT(ptrA);
 509     ASSERT(ptrB);
 510
 511     if (int x = prefixA.compare(prefixB))
 512         return x;
 513
 514     if (prefixA.type() == KeyPrefix::kGlobalMetaData) {
 515         ASSERT(ptrA != endA);
 516         ASSERT(ptrB != endB);
 517
 518         unsigned char typeByteA = *ptrA++;
 519         unsigned char typeByteB = *ptrB++;
 520
 521         if (int x = typeByteA - typeByteB)
 522             return x;
 523
 524         if (typeByteA <= 1)
 525             return 0;
 526         if (typeByteA == kDatabaseFreeListTypeByte)
 527             return decodeAndCompare<DatabaseFreeListKey>(a, b);
 528         if (typeByteA == kDatabaseNameTypeByte)
 529             return decodeAndCompare<DatabaseNameKey>(a, b);
 530     }
 531
 532     if (prefixA.type() == KeyPrefix::kDatabaseMetaData) {
 533         ASSERT(ptrA != endA);
 534         ASSERT(ptrB != endB);
 535
 536         unsigned char typeByteA = *ptrA++;
 537         unsigned char typeByteB = *ptrB++;
 538
 539         if (int x = typeByteA - typeByteB)
 540             return x;
 541
 542         if (typeByteA <= 3)
 543             return 0;
 544
 545         if (typeByteA == kObjectStoreMetaDataTypeByte)
 546             return decodeAndCompare<ObjectStoreMetaDataKey>(a, b);
 547         if (typeByteA == kIndexMetaDataTypeByte)
 548             return decodeAndCompare<IndexMetaDataKey>(a, b);
 549         if (typeByteA == kObjectStoreFreeListTypeByte)
 550             return decodeAndCompare<ObjectStoreFreeListKey>(a, b);
 551         if (typeByteA == kIndexFreeListTypeByte)
 552             return decodeAndCompare<IndexFreeListKey>(a, b);
 553         if (typeByteA == kObjectStoreNamesTypeByte)
 554             return decodeAndCompare<ObjectStoreNamesKey>(a, b);
 555         if (typeByteA == kIndexNamesKeyTypeByte)
 556             return decodeAndCompare<IndexNamesKey>(a, b);
 557
 558         return 0;
 559         ASSERT_NOT_REACHED();
 560     }
 561
 562     if (prefixA.type() == KeyPrefix::kObjectStoreData) {
 563         if (ptrA == endA && ptrB == endB)
 564             return 0;
 565         if (ptrA == endA)
 566             return -1;
 567         if (ptrB == endB)
 568             return 1; // FIXME: This case of non-existing user keys should not have to be handled this way.
 569
 570         return decodeAndCompare<ObjectStoreDataKey>(a, b);
 571     }
 572     if (prefixA.type() == KeyPrefix::kExistsEntry) {
 573         if (ptrA == endA && ptrB == endB)
 574             return 0;
 575         if (ptrA == endA)
 576             return -1;
 577         if (ptrB == endB)
 578             return 1; // FIXME: This case of non-existing user keys should not have to be handled this way.
 579
 580         return decodeAndCompare<ExistsEntryKey>(a, b);
 581     }
 582     if (prefixA.type() == KeyPrefix::kIndexData) {
 583         if (ptrA == endA && ptrB == endB)
 584             return 0;
 585         if (ptrA == endA)
 586             return -1;
 587         if (ptrB == endB)
 588             return 1; // FIXME: This case of non-existing user keys should not have to be handled this way.
 589
 590         IndexDataKey indexDataKeyA;
 591         IndexDataKey indexDataKeyB;
 592
 593         ptrA = IndexDataKey::decode(a.begin(), endA, &indexDataKeyA);
 594         ptrB = IndexDataKey::decode(b.begin(), endB, &indexDataKeyB);
 595         ASSERT(ptrA);
 596         ASSERT(ptrB);
 597
 598         bool ignoreSequenceNumber = indexKeys;
 599         return indexDataKeyA.compare(indexDataKeyB, ignoreSequenceNumber);
 600     }
 601
 602     ASSERT_NOT_REACHED();
 603     return 0;
 604 }
 605
 606
 607 KeyPrefix::KeyPrefix()
 608     : m_databaseId(kInvalidType)
 609     , m_objectStoreId(kInvalidType)
 610     , m_indexId(kInvalidType)
 611 {
 612 }
 613
 614 KeyPrefix::KeyPrefix(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
 615     : m_databaseId(databaseId)
 616     , m_objectStoreId(objectStoreId)
 617     , m_indexId(indexId)
 618 {
 619 }
 620
 621 const char* KeyPrefix::decode(const char* start, const char* limit, KeyPrefix* result)
 622 {
 623     if (start == limit)
 624         return 0;
 625
 626     unsigned char firstByte = *start++;
 627
 628     int databaseIdBytes = ((firstByte >> 5) & 0x7) + 1;
 629     int objectStoreIdBytes = ((firstByte >> 2) & 0x7) + 1;
 630     int indexIdBytes = (firstByte & 0x3) + 1;
 631
 632     if (start + databaseIdBytes + objectStoreIdBytes + indexIdBytes > limit)
 633         return 0;
 634
 635     result->m_databaseId = decodeInt(start, start + databaseIdBytes);
 636     start += databaseIdBytes;
 637     result->m_objectStoreId = decodeInt(start, start + objectStoreIdBytes);
 638     start += objectStoreIdBytes;
 639     result->m_indexId = decodeInt(start, start + indexIdBytes);
 640     start += indexIdBytes;
 641
 642     return start;
 643 }
 644
 645 Vector<char> KeyPrefix::encode() const
 646 {
 647     ASSERT(m_databaseId != kInvalidId);
 648     ASSERT(m_objectStoreId != kInvalidId);
 649     ASSERT(m_indexId != kInvalidId);
 650
 651     Vector<char> databaseIdString = encodeInt(m_databaseId);
 652     Vector<char> objectStoreIdString = encodeInt(m_objectStoreId);
 653     Vector<char> indexIdString = encodeInt(m_indexId);
 654
 655     ASSERT(databaseIdString.size() <= 8);
 656     ASSERT(objectStoreIdString.size() <= 8);
 657     ASSERT(indexIdString.size() <= 4);
 658
 659
 660     unsigned char firstByte = (databaseIdString.size() - 1) << 5 | (objectStoreIdString.size() - 1) << 2 | (indexIdString.size() - 1);
 661     Vector<char> ret;
 662     ret.append(firstByte);
 663     ret.append(databaseIdString);
 664     ret.append(objectStoreIdString);
 665     ret.append(indexIdString);
 666
 667     return ret;
 668 }
 669
 670 int KeyPrefix::compare(const KeyPrefix& other) const
 671 {
 672     ASSERT(m_databaseId != kInvalidId);
 673     ASSERT(m_objectStoreId != kInvalidId);
 674     ASSERT(m_indexId != kInvalidId);
 675
 676     if (m_databaseId != other.m_databaseId)
 677         return compareInts(m_databaseId, other.m_databaseId);
 678     if (m_objectStoreId != other.m_objectStoreId)
 679         return compareInts(m_objectStoreId, other.m_objectStoreId);
 680     if (m_indexId != other.m_indexId)
 681         return compareInts(m_indexId, other.m_indexId);
 682     return 0;
 683 }
 684
 685 KeyPrefix::Type KeyPrefix::type() const
 686 {
 687     ASSERT(m_databaseId != kInvalidId);
 688     ASSERT(m_objectStoreId != kInvalidId);
 689     ASSERT(m_indexId != kInvalidId);
 690
 691     if (!m_databaseId)
 692         return kGlobalMetaData;
 693     if (!m_objectStoreId)
 694         return kDatabaseMetaData;
 695     if (m_indexId == kObjectStoreDataIndexId)
 696         return kObjectStoreData;
 697     if (m_indexId == kExistsEntryIndexId)
 698         return kExistsEntry;
 699     if (m_indexId >= kMinimumIndexId)
 700         return kIndexData;
 701
 702     ASSERT_NOT_REACHED();
 703     return kInvalidType;
 704 }
 705
 706 Vector<char> SchemaVersionKey::encode()
 707 {
 708     KeyPrefix prefix(0, 0, 0);
 709     Vector<char> ret = prefix.encode();
 710     ret.append(encodeByte(kSchemaVersionTypeByte));
 711     return ret;
 712 }
 713
 714 Vector<char> MaxDatabaseIdKey::encode()
 715 {
 716     KeyPrefix prefix(0, 0, 0);
 717     Vector<char> ret = prefix.encode();
 718     ret.append(encodeByte(kMaxDatabaseIdTypeByte));
 719     return ret;
 720 }
 721
 722 DatabaseFreeListKey::DatabaseFreeListKey()
 723     : m_databaseId(-1)
 724 {
 725 }
 726
 727 const char* DatabaseFreeListKey::decode(const char* start, const char* limit, DatabaseFreeListKey* result)
 728 {
 729     KeyPrefix prefix;
 730     const char *p = KeyPrefix::decode(start, limit, &prefix);
 731     if (!p)
 732         return 0;
 733     ASSERT(!prefix.m_databaseId);
 734     ASSERT(!prefix.m_objectStoreId);
 735     ASSERT(!prefix.m_indexId);
 736     if (p == limit)
 737         return 0;
 738     unsigned char typeByte = *p++;
 739     ASSERT_UNUSED(typeByte, typeByte == kDatabaseFreeListTypeByte);
 740     if (p == limit)
 741         return 0;
 742     return decodeVarInt(p, limit, result->m_databaseId);
 743 }
 744
 745 Vector<char> DatabaseFreeListKey::encode(int64_t databaseId)
 746 {
 747     KeyPrefix prefix(0, 0, 0);
 748     Vector<char> ret = prefix.encode();
 749     ret.append(encodeByte(kDatabaseFreeListTypeByte));
 750     ret.append(encodeVarInt(databaseId));
 751     return ret;
 752 }
 753
 754 Vector<char> DatabaseFreeListKey::encodeMaxKey()
 755 {
 756     return encode(INT64_MAX);
 757 }
 758
 759 int64_t DatabaseFreeListKey::databaseId() const
 760 {
 761     ASSERT(m_databaseId >= 0);
 762     return m_databaseId;
 763 }
 764
 765 int DatabaseFreeListKey::compare(const DatabaseFreeListKey& other) const
 766 {
 767     ASSERT(m_databaseId >= 0);
 768     return compareInts(m_databaseId, other.m_databaseId);
 769 }
 770
 771 const char* DatabaseNameKey::decode(const char* start, const char* limit, DatabaseNameKey* result)
 772 {
 773     KeyPrefix prefix;
 774     const char* p = KeyPrefix::decode(start, limit, &prefix);
 775     if (!p)
 776         return p;
 777     ASSERT(!prefix.m_databaseId);
 778     ASSERT(!prefix.m_objectStoreId);
 779     ASSERT(!prefix.m_indexId);
 780     if (p == limit)
 781         return 0;
 782     unsigned char typeByte = *p++;
 783     ASSERT_UNUSED(typeByte, typeByte == kDatabaseNameTypeByte);
 784     if (p == limit)
 785         return 0;
 786     p = decodeStringWithLength(p, limit, result->m_origin);
 787     if (!p)
 788         return 0;
 789     return decodeStringWithLength(p, limit, result->m_databaseName);
 790 }
 791
 792 Vector<char> DatabaseNameKey::encode(const String& origin, const String& databaseName)
 793 {
 794     KeyPrefix prefix(0, 0, 0);
 795     Vector<char> ret = prefix.encode();
 796     ret.append(encodeByte(kDatabaseNameTypeByte));
 797     ret.append(encodeStringWithLength(origin));
 798     ret.append(encodeStringWithLength(databaseName));
 799     return ret;
 800 }
 801
 802 int DatabaseNameKey::compare(const DatabaseNameKey& other)
 803 {
 804     if (int x = codePointCompare(m_origin, other.m_origin))
 805         return x;
 806     return codePointCompare(m_databaseName, other.m_databaseName);
 807 }
 808
 809 Vector<char> DatabaseMetaDataKey::encode(int64_t databaseId, MetaDataType metaDataType)
 810 {
 811     KeyPrefix prefix(databaseId, 0, 0);
 812     Vector<char> ret = prefix.encode();
 813     ret.append(encodeByte(metaDataType));
 814     return ret;
 815 }
 816
 817 ObjectStoreMetaDataKey::ObjectStoreMetaDataKey()
 818     : m_objectStoreId(-1)
 819     , m_metaDataType(-1)
 820 {
 821 }
 822
 823 const char* ObjectStoreMetaDataKey::decode(const char* start, const char* limit, ObjectStoreMetaDataKey* result)
 824 {
 825     KeyPrefix prefix;
 826     const char* p = KeyPrefix::decode(start, limit, &prefix);
 827     if (!p)
 828         return 0;
 829     ASSERT(prefix.m_databaseId);
 830     ASSERT(!prefix.m_objectStoreId);
 831     ASSERT(!prefix.m_indexId);
 832     if (p == limit)
 833         return 0;
 834     unsigned char typeByte = *p++;
 835     ASSERT_UNUSED(typeByte, typeByte == kObjectStoreMetaDataTypeByte);
 836     if (p == limit)
 837         return 0;
 838     p = decodeVarInt(p, limit, result->m_objectStoreId);
 839     if (!p)
 840         return 0;
 841     ASSERT(result->m_objectStoreId);
 842     if (p == limit)
 843         return 0;
 844     return decodeVarInt(p, limit, result->m_metaDataType);
 845 }
 846
 847 Vector<char> ObjectStoreMetaDataKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t metaDataType)
 848 {
 849     KeyPrefix prefix(databaseId, 0, 0);
 850     Vector<char> ret = prefix.encode();
 851     ret.append(encodeByte(kObjectStoreMetaDataTypeByte));
 852     ret.append(encodeVarInt(objectStoreId));
 853     ret.append(encodeVarInt(metaDataType));
 854     return ret;
 855 }
 856
 857 Vector<char> ObjectStoreMetaDataKey::encodeMaxKey(int64_t databaseId)
 858 {
 859     return encode(databaseId, INT64_MAX, INT64_MAX);
 860 }
 861
 862 int64_t ObjectStoreMetaDataKey::objectStoreId() const
 863 {
 864     ASSERT(m_objectStoreId >= 0);
 865     return m_objectStoreId;
 866 }
 867 int64_t ObjectStoreMetaDataKey::metaDataType() const
 868 {
 869     ASSERT(m_metaDataType >= 0);
 870     return m_metaDataType;
 871 }
 872
 873 int ObjectStoreMetaDataKey::compare(const ObjectStoreMetaDataKey& other)
 874 {
 875     ASSERT(m_objectStoreId >= 0);
 876     ASSERT(m_metaDataType >= 0);
 877     if (int x = compareInts(m_objectStoreId, other.m_objectStoreId))
 878         return x;
 879     return m_metaDataType - other.m_metaDataType;
 880 }
 881
 882 IndexMetaDataKey::IndexMetaDataKey()
 883     : m_objectStoreId(-1)
 884     , m_indexId(-1)
 885     , m_metaDataType(0)
 886 {
 887 }
 888
 889 const char* IndexMetaDataKey::decode(const char* start, const char* limit, IndexMetaDataKey* result)
 890 {
 891     KeyPrefix prefix;
 892     const char* p = KeyPrefix::decode(start, limit, &prefix);
 893     if (!p)
 894         return 0;
 895     ASSERT(prefix.m_databaseId);
 896     ASSERT(!prefix.m_objectStoreId);
 897     ASSERT(!prefix.m_indexId);
 898     if (p == limit)
 899         return 0;
 900     unsigned char typeByte = *p++;
 901     ASSERT_UNUSED(typeByte, typeByte == kIndexMetaDataTypeByte);
 902     if (p == limit)
 903         return 0;
 904     p = decodeVarInt(p, limit, result->m_objectStoreId);
 905     if (!p)
 906         return 0;
 907     p = decodeVarInt(p, limit, result->m_indexId);
 908     if (!p)
 909         return 0;
 910     if (p == limit)
 911         return 0;
 912     result->m_metaDataType = *p++;
 913     return p;
 914 }
 915
 916 Vector<char> IndexMetaDataKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId, unsigned char metaDataType)
 917 {
 918     KeyPrefix prefix(databaseId, 0, 0);
 919     Vector<char> ret = prefix.encode();
 920     ret.append(encodeByte(kIndexMetaDataTypeByte));
 921     ret.append(encodeVarInt(objectStoreId));
 922     ret.append(encodeVarInt(indexId));
 923     ret.append(encodeByte(metaDataType));
 924     return ret;
 925 }
 926
 927 Vector<char> IndexMetaDataKey::encodeMaxKey(int64_t databaseId, int64_t objectStoreId)
 928 {
 929     return encode(databaseId, objectStoreId, INT64_MAX, 255);
 930 }
 931
 932 int IndexMetaDataKey::compare(const IndexMetaDataKey& other)
 933 {
 934     ASSERT(m_objectStoreId >= 0);
 935     ASSERT(m_indexId >= 0);
 936
 937     if (int x = compareInts(m_objectStoreId, other.m_objectStoreId))
 938         return x;
 939     if (int x = compareInts(m_indexId, other.m_indexId))
 940         return x;
 941     return m_metaDataType - other.m_metaDataType;
 942 }
 943
 944 int64_t IndexMetaDataKey::indexId() const
 945 {
 946     ASSERT(m_indexId >= 0);
 947     return m_indexId;
 948 }
 949
 950 ObjectStoreFreeListKey::ObjectStoreFreeListKey()
 951     : m_objectStoreId(-1)
 952 {
 953 }
 954
 955 const char* ObjectStoreFreeListKey::decode(const char* start, const char* limit, ObjectStoreFreeListKey* result)
 956 {
 957     KeyPrefix prefix;
 958     const char *p = KeyPrefix::decode(start, limit, &prefix);
 959     if (!p)
 960         return 0;
 961     ASSERT(prefix.m_databaseId);
 962     ASSERT(!prefix.m_objectStoreId);
 963     ASSERT(!prefix.m_indexId);
 964     if (p == limit)
 965         return 0;
 966     unsigned char typeByte = *p++;
 967     ASSERT_UNUSED(typeByte, typeByte == kObjectStoreFreeListTypeByte);
 968     if (p == limit)
 969         return 0;
 970     return decodeVarInt(p, limit, result->m_objectStoreId);
 971 }
 972
 973 Vector<char> ObjectStoreFreeListKey::encode(int64_t databaseId, int64_t objectStoreId)
 974 {
 975     KeyPrefix prefix(databaseId, 0, 0);
 976     Vector<char> ret = prefix.encode();
 977     ret.append(encodeByte(kObjectStoreFreeListTypeByte));
 978     ret.append(encodeVarInt(objectStoreId));
 979     return ret;
 980 }
 981
 982 Vector<char> ObjectStoreFreeListKey::encodeMaxKey(int64_t databaseId)
 983 {
 984     return encode(databaseId, INT64_MAX);
 985 }
 986
 987 int64_t ObjectStoreFreeListKey::objectStoreId() const
 988 {
 989     ASSERT(m_objectStoreId >= 0);
 990     return m_objectStoreId;
 991 }
 992
 993 int ObjectStoreFreeListKey::compare(const ObjectStoreFreeListKey& other)
 994 {
 995     // FIXME: It may seem strange that we're not comparing database id's,
 996     // but that comparison will have been made earlier.
 997     // We should probably make this more clear, though...
 998     ASSERT(m_objectStoreId >= 0);
 999     return compareInts(m_objectStoreId, other.m_objectStoreId);
1000 }
1001
1002 IndexFreeListKey::IndexFreeListKey()
1003     : m_objectStoreId(-1)
1004     , m_indexId(-1)
1005 {
1006 }
1007
1008 const char* IndexFreeListKey::decode(const char* start, const char* limit, IndexFreeListKey* result)
1009 {
1010     KeyPrefix prefix;
1011     const char* p = KeyPrefix::decode(start, limit, &prefix);
1012     if (!p)
1013         return 0;
1014     ASSERT(prefix.m_databaseId);
1015     ASSERT(!prefix.m_objectStoreId);
1016     ASSERT(!prefix.m_indexId);
1017     if (p == limit)
1018         return 0;
1019     unsigned char typeByte = *p++;
1020     ASSERT_UNUSED(typeByte, typeByte == kIndexFreeListTypeByte);
1021     if (p == limit)
1022         return 0;
1023     p = decodeVarInt(p, limit, result->m_objectStoreId);
1024     if (!p)
1025         return 0;
1026     return decodeVarInt(p, limit, result->m_indexId);
1027 }
1028
1029 Vector<char> IndexFreeListKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
1030 {
1031     KeyPrefix prefix(databaseId, 0, 0);
1032     Vector<char> ret = prefix.encode();
1033     ret.append(encodeByte(kIndexFreeListTypeByte));
1034     ret.append(encodeVarInt(objectStoreId));
1035     ret.append(encodeVarInt(indexId));
1036     return ret;
1037 }
1038
1039 Vector<char> IndexFreeListKey::encodeMaxKey(int64_t databaseId, int64_t objectStoreId)
1040 {
1041     return encode(databaseId, objectStoreId, INT64_MAX);
1042 }
1043
1044 int IndexFreeListKey::compare(const IndexFreeListKey& other)
1045 {
1046     ASSERT(m_objectStoreId >= 0);
1047     ASSERT(m_indexId >= 0);
1048     if (int x = compareInts(m_objectStoreId, other.m_objectStoreId))
1049         return x;
1050     return compareInts(m_indexId, other.m_indexId);
1051 }
1052
1053 int64_t IndexFreeListKey::objectStoreId() const
1054 {
1055     ASSERT(m_objectStoreId >= 0);
1056     return m_objectStoreId;
1057 }
1058
1059 int64_t IndexFreeListKey::indexId() const
1060 {
1061     ASSERT(m_indexId >= 0);
1062     return m_indexId;
1063 }
1064
1065 // FIXME: We never use this to look up object store ids, because a mapping
1066 // is kept in the IDBDatabaseBackendImpl. Can the mapping become unreliable?
1067 // Can we remove this?
1068 const char* ObjectStoreNamesKey::decode(const char* start, const char* limit, ObjectStoreNamesKey* result)
1069 {
1070     KeyPrefix prefix;
1071     const char* p = KeyPrefix::decode(start, limit, &prefix);
1072     if (!p)
1073         return 0;
1074     ASSERT(prefix.m_databaseId);
1075     ASSERT(!prefix.m_objectStoreId);
1076     ASSERT(!prefix.m_indexId);
1077     if (p == limit)
1078         return 0;
1079     unsigned char typeByte = *p++;
1080     ASSERT_UNUSED(typeByte, typeByte == kObjectStoreNamesTypeByte);
1081     return decodeStringWithLength(p, limit, result->m_objectStoreName);
1082 }
1083
1084 Vector<char> ObjectStoreNamesKey::encode(int64_t databaseId, const String& objectStoreName)
1085 {
1086     KeyPrefix prefix(databaseId, 0, 0);
1087     Vector<char> ret = prefix.encode();
1088     ret.append(encodeByte(kObjectStoreNamesTypeByte));
1089     ret.append(encodeStringWithLength(objectStoreName));
1090     return ret;
1091 }
1092
1093 int ObjectStoreNamesKey::compare(const ObjectStoreNamesKey& other)
1094 {
1095     return codePointCompare(m_objectStoreName, other.m_objectStoreName);
1096 }
1097
1098 IndexNamesKey::IndexNamesKey()
1099     : m_objectStoreId(-1)
1100 {
1101 }
1102
1103 // FIXME: We never use this to look up index ids, because a mapping
1104 // is kept at a higher level.
1105 const char* IndexNamesKey::decode(const char* start, const char* limit, IndexNamesKey* result)
1106 {
1107     KeyPrefix prefix;
1108     const char* p = KeyPrefix::decode(start, limit, &prefix);
1109     if (!p)
1110         return 0;
1111     ASSERT(prefix.m_databaseId);
1112     ASSERT(!prefix.m_objectStoreId);
1113     ASSERT(!prefix.m_indexId);
1114     if (p == limit)
1115         return 0;
1116     unsigned char typeByte = *p++;
1117     ASSERT_UNUSED(typeByte, typeByte == kIndexNamesKeyTypeByte);
1118     if (p == limit)
1119         return 0;
1120     p = decodeVarInt(p, limit, result->m_objectStoreId);
1121     if (!p)
1122         return 0;
1123     return decodeStringWithLength(p, limit, result->m_indexName);
1124 }
1125
1126 Vector<char> IndexNamesKey::encode(int64_t databaseId, int64_t objectStoreId, const String& indexName)
1127 {
1128     KeyPrefix prefix(databaseId, 0, 0);
1129     Vector<char> ret = prefix.encode();
1130     ret.append(encodeByte(kIndexNamesKeyTypeByte));
1131     ret.append(encodeVarInt(objectStoreId));
1132     ret.append(encodeStringWithLength(indexName));
1133     return ret;
1134 }
1135
1136 int IndexNamesKey::compare(const IndexNamesKey& other)
1137 {
1138     ASSERT(m_objectStoreId >= 0);
1139     if (int x = compareInts(m_objectStoreId, other.m_objectStoreId))
1140         return x;
1141     return codePointCompare(m_indexName, other.m_indexName);
1142 }
1143
1144 const char* ObjectStoreDataKey::decode(const char* start, const char* end, ObjectStoreDataKey* result)
1145 {
1146     KeyPrefix prefix;
1147     const char* p = KeyPrefix::decode(start, end, &prefix);
1148     if (!p)
1149         return 0;
1150     ASSERT(prefix.m_databaseId);
1151     ASSERT(prefix.m_objectStoreId);
1152     ASSERT(prefix.m_indexId == kSpecialIndexNumber);
1153     if (p == end)
1154         return 0;
1155     return extractEncodedIDBKey(p, end, &result->m_encodedUserKey);
1156 }
1157
1158 Vector<char> ObjectStoreDataKey::encode(int64_t databaseId, int64_t objectStoreId, const Vector<char> encodedUserKey)
1159 {
1160     KeyPrefix prefix(databaseId, objectStoreId, kSpecialIndexNumber);
1161     Vector<char> ret = prefix.encode();
1162     ret.append(encodedUserKey);
1163
1164     return ret;
1165 }
1166
1167 Vector<char> ObjectStoreDataKey::encode(int64_t databaseId, int64_t objectStoreId, const IDBKey& userKey)
1168 {
1169     return encode(databaseId, objectStoreId, encodeIDBKey(userKey));
1170 }
1171
1172 int ObjectStoreDataKey::compare(const ObjectStoreDataKey& other)
1173 {
1174     return compareEncodedIDBKeys(m_encodedUserKey, other.m_encodedUserKey);
1175 }
1176
1177 PassRefPtr<IDBKey> ObjectStoreDataKey::userKey() const
1178 {
1179     RefPtr<IDBKey> key;
1180     decodeIDBKey(m_encodedUserKey.begin(), m_encodedUserKey.end(), key);
1181     return key;
1182 }
1183
1184 const int64_t ObjectStoreDataKey::kSpecialIndexNumber = kObjectStoreDataIndexId;
1185
1186 const char* ExistsEntryKey::decode(const char* start, const char* end, ExistsEntryKey* result)
1187 {
1188     KeyPrefix prefix;
1189     const char* p = KeyPrefix::decode(start, end, &prefix);
1190     if (!p)
1191         return 0;
1192     ASSERT(prefix.m_databaseId);
1193     ASSERT(prefix.m_objectStoreId);
1194     ASSERT(prefix.m_indexId == kSpecialIndexNumber);
1195     if (p == end)
1196         return 0;
1197     return extractEncodedIDBKey(p, end, &result->m_encodedUserKey);
1198 }
1199
1200 Vector<char> ExistsEntryKey::encode(int64_t databaseId, int64_t objectStoreId, const Vector<char>& encodedKey)
1201 {
1202     KeyPrefix prefix(databaseId, objectStoreId, kSpecialIndexNumber);
1203     Vector<char> ret = prefix.encode();
1204     ret.append(encodedKey);
1205     return ret;
1206 }
1207
1208 Vector<char> ExistsEntryKey::encode(int64_t databaseId, int64_t objectStoreId, const IDBKey& userKey)
1209 {
1210     return encode(databaseId, objectStoreId, encodeIDBKey(userKey));
1211 }
1212
1213 int ExistsEntryKey::compare(const ExistsEntryKey& other)
1214 {
1215     return compareEncodedIDBKeys(m_encodedUserKey, other.m_encodedUserKey);
1216 }
1217
1218 PassRefPtr<IDBKey> ExistsEntryKey::userKey() const
1219 {
1220     RefPtr<IDBKey> key;
1221     decodeIDBKey(m_encodedUserKey.begin(), m_encodedUserKey.end(), key);
1222     return key;
1223 }
1224
1225 const int64_t ExistsEntryKey::kSpecialIndexNumber = kExistsEntryIndexId;
1226
1227 IndexDataKey::IndexDataKey()
1228     : m_databaseId(-1)
1229     , m_objectStoreId(-1)
1230     , m_indexId(-1)
1231     , m_sequenceNumber(-1)
1232 {
1233 }
1234
1235 const char* IndexDataKey::decode(const char* start, const char* limit, IndexDataKey* result)
1236 {
1237     KeyPrefix prefix;
1238     const char* p = KeyPrefix::decode(start, limit, &prefix);
1239     if (!p)
1240         return 0;
1241     ASSERT(prefix.m_databaseId);
1242     ASSERT(prefix.m_objectStoreId);
1243     ASSERT(prefix.m_indexId >= kMinimumIndexId);
1244     result->m_databaseId = prefix.m_databaseId;
1245     result->m_objectStoreId = prefix.m_objectStoreId;
1246     result->m_indexId = prefix.m_indexId;
1247     p = extractEncodedIDBKey(p, limit, &result->m_encodedUserKey);
1248     if (!p)
1249         return 0;
1250     if (p == limit) {
1251         result->m_sequenceNumber = -1; // FIXME: We should change it so that all keys have a sequence number. Shouldn't need to handle this case.
1252         return p;
1253     }
1254     return decodeVarInt(p, limit, result->m_sequenceNumber);
1255 }
1256
1257 Vector<char> IndexDataKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const Vector<char>& encodedUserKey, int64_t sequenceNumber)
1258 {
1259     KeyPrefix prefix(databaseId, objectStoreId, indexId);
1260     Vector<char> ret = prefix.encode();
1261     ret.append(encodedUserKey);
1262     ret.append(encodeVarInt(sequenceNumber));
1263     return ret;
1264 }
1265
1266 Vector<char> IndexDataKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& userKey, int64_t sequenceNumber)
1267 {
1268     return encode(databaseId, objectStoreId, indexId, encodeIDBKey(userKey), sequenceNumber);
1269 }
1270
1271 Vector<char> IndexDataKey::encodeMaxKey(int64_t databaseId, int64_t objectStoreId)
1272 {
1273     return encode(databaseId, objectStoreId, INT32_MAX, maxIDBKey(), INT64_MAX);
1274 }
1275
1276 int IndexDataKey::compare(const IndexDataKey& other, bool ignoreSequenceNumber)
1277 {
1278     ASSERT(m_databaseId >= 0);
1279     ASSERT(m_objectStoreId >= 0);
1280     ASSERT(m_indexId >= 0);
1281     if (int x = compareEncodedIDBKeys(m_encodedUserKey, other.m_encodedUserKey))
1282         return x;
1283     if (ignoreSequenceNumber)
1284         return 0;
1285     return compareInts(m_sequenceNumber, other.m_sequenceNumber);
1286 }
1287
1288 int64_t IndexDataKey::databaseId() const
1289 {
1290     ASSERT(m_databaseId >= 0);
1291     return m_databaseId;
1292 }
1293
1294 int64_t IndexDataKey::objectStoreId() const
1295 {
1296     ASSERT(m_objectStoreId >= 0);
1297     return m_objectStoreId;
1298 }
1299
1300 int64_t IndexDataKey::indexId() const
1301 {
1302     ASSERT(m_indexId >= 0);
1303     return m_indexId;
1304 }
1305
1306 PassRefPtr<IDBKey> IndexDataKey::userKey() const
1307 {
1308     RefPtr<IDBKey> key;
1309     decodeIDBKey(m_encodedUserKey.begin(), m_encodedUserKey.end(), key);
1310     return key;
1311 }
1312
1313 } // namespace IDBLevelDBCoding
1314 } // namespace WebCore
1315
1316 #endif // ENABLE(LEVELDB)
1317 #endif // ENABLE(INDEXED_DATABASE)