20f45ab5f9a4fd54be517011de69f52b734ec726
[WebKit-https.git] / 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 USE(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 //     <database id, 0, 0, 50, object store id, 6> => has key path (vs. null) [ObjectStoreMetaDataKey]
75 //
76 //
77 // Index meta-data:
78 //
79 //     The prefix is followed by a type byte, then two variable-length integers, and then another type byte.
80 //
81 //     <database id, 0, 0, 100, object store id, index id, 0> => utf16 index name [IndexMetaDataKey]
82 //     <database id, 0, 0, 100, object store id, index id, 1> => are index keys unique [IndexMetaDataKey]
83 //     <database id, 0, 0, 100, object store id, index id, 2> => utf16 key path [IndexMetaDataKey]
84 //
85 //
86 // Other object store and index meta-data:
87 //
88 //     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.
89 //
90 //     <database id, 0, 0, 150, object store id>                   => existence implies the object store id is in the free list [ObjectStoreFreeListKey]
91 //     <database id, 0, 0, 151, object store id, index id>         => existence implies the index id is in the free list [IndexFreeListKey]
92 //     <database id, 0, 0, 200, utf16 object store name>           => object store id [ObjectStoreNamesKey]
93 //     <database id, 0, 0, 201, object store id, utf16 index name> => index id [IndexNamesKey]
94 //
95 //
96 // Object store data:
97 //
98 //     The prefix is followed by a type byte. The user key is an encoded IDBKey.
99 //
100 //     <database id, object store id, 1, user key> => "version", serialized script value [ObjectStoreDataKey]
101 //
102 //
103 // "Exists" entry:
104 //
105 //     The prefix is followed by a type byte. The user key is an encoded IDBKey.
106 //
107 //     <database id, object store id, 2, user key> => "version" [ExistsEntryKey]
108 //
109 //
110 // Index data:
111 //
112 //     The prefix is followed by a type byte. The user key is an encoded IDBKey. The sequence number is a variable length integer.
113 //
114 //     <database id, object store id, index id, user key, sequence number> => "version", user key [IndexDataKey]
115 //
116 //     (The sequence number is used to allow two entries with the same user key
117 //     in non-unique indexes. The "version" field is used to weed out stale
118 //     index data. Whenever new object store data is inserted, it gets a new
119 //     "version" number, and new index data is written with this number. When
120 //     the index is used for look-ups, entries are validated against the
121 //     "exists" entries, and records with old "version" numbers are deleted
122 //     when they are encountered in getPrimaryKeyViaIndex,
123 //     IndexCursorImpl::loadCurrentRow, and IndexKeyCursorImpl::loadCurrentRow).
124
125 namespace WebCore {
126 namespace IDBLevelDBCoding {
127
128 static const unsigned char kIDBKeyNullTypeByte = 0;
129 static const unsigned char kIDBKeyStringTypeByte = 1;
130 static const unsigned char kIDBKeyDateTypeByte = 2;
131 static const unsigned char kIDBKeyNumberTypeByte = 3;
132 static const unsigned char kIDBKeyArrayTypeByte = 4;
133 static const unsigned char kIDBKeyMinKeyTypeByte = 5;
134
135 static const unsigned char kObjectStoreDataIndexId = 1;
136 static const unsigned char kExistsEntryIndexId = 2;
137
138 static const unsigned char kSchemaVersionTypeByte = 0;
139 static const unsigned char kMaxDatabaseIdTypeByte = 1;
140 static const unsigned char kDatabaseFreeListTypeByte = 100;
141 static const unsigned char kDatabaseNameTypeByte = 201;
142
143 static const unsigned char kObjectStoreMetaDataTypeByte = 50;
144 static const unsigned char kIndexMetaDataTypeByte = 100;
145 static const unsigned char kObjectStoreFreeListTypeByte = 150;
146 static const unsigned char kIndexFreeListTypeByte = 151;
147 static const unsigned char kObjectStoreNamesTypeByte = 200;
148 static const unsigned char kIndexNamesKeyTypeByte = 201;
149
150 #ifndef INT64_MAX
151 #define INT64_MAX 0x7fffffffffffffffLL
152 #endif
153 #ifndef INT32_MAX
154 #define INT32_MAX 0x7fffffffL
155 #endif
156
157
158 Vector<char> encodeByte(unsigned char c)
159 {
160     Vector<char> v;
161     v.append(c);
162     return v;
163 }
164
165 Vector<char> maxIDBKey()
166 {
167     return encodeByte(kIDBKeyNullTypeByte);
168 }
169
170 Vector<char> minIDBKey()
171 {
172     return encodeByte(kIDBKeyMinKeyTypeByte);
173 }
174
175 Vector<char> encodeInt(int64_t n)
176 {
177     ASSERT(n >= 0);
178     Vector<char> ret; // FIXME: Size this at creation.
179
180     do {
181         unsigned char c = n;
182         ret.append(c);
183         n >>= 8;
184     } while (n);
185
186     return ret;
187 }
188
189 int64_t decodeInt(const char* begin, const char* end)
190 {
191     ASSERT(begin <= end);
192     int64_t ret = 0;
193
194     int shift = 0;
195     while (begin < end) {
196         unsigned char c = *begin++;
197         ret |= static_cast<int64_t>(c) << shift;
198         shift += 8;
199     }
200
201     return ret;
202 }
203
204 static int compareInts(int64_t a, int64_t b)
205 {
206     ASSERT(a >= 0);
207     ASSERT(b >= 0);
208
209     int64_t diff = a - b;
210     if (diff < 0)
211         return -1;
212     if (diff > 0)
213         return 1;
214     return 0;
215 }
216
217 Vector<char> encodeVarInt(int64_t n)
218 {
219     Vector<char> ret; // FIXME: Size this at creation.
220
221     do {
222         unsigned char c = n & 0x7f;
223         n >>= 7;
224         if (n)
225             c |= 0x80;
226         ret.append(c);
227     } while (n);
228
229     return ret;
230 }
231
232 const char* decodeVarInt(const char *p, const char* limit, int64_t& foundInt)
233 {
234     ASSERT(limit >= p);
235     foundInt = 0;
236     int shift = 0;
237
238     do {
239         if (p >= limit)
240             return 0;
241
242         unsigned char c = *p;
243         foundInt |= static_cast<int64_t>(c & 0x7f) << shift;
244         shift += 7;
245     } while (*p++ & 0x80);
246     return p;
247 }
248
249 Vector<char> encodeString(const String& s)
250 {
251     Vector<char> ret; // FIXME: Size this at creation.
252
253     for (unsigned i = 0; i < s.length(); ++i) {
254         UChar u = s[i];
255         unsigned char hi = u >> 8;
256         unsigned char lo = u;
257         ret.append(hi);
258         ret.append(lo);
259     }
260
261     return ret;
262 }
263
264 String decodeString(const char* p, const char* end)
265 {
266     ASSERT(end >= p);
267     ASSERT(!((end - p) % 2));
268
269     size_t len = (end - p) / 2;
270     StringBuilder result;
271     result.reserveCapacity(len);
272
273     for (size_t i = 0; i < len; ++i) {
274         unsigned char hi = *p++;
275         unsigned char lo = *p++;
276
277         result.append(static_cast<UChar>((hi << 8) | lo));
278     }
279
280     return result.toString();
281 }
282
283 Vector<char> encodeStringWithLength(const String& s)
284 {
285     Vector<char> ret = encodeVarInt(s.length());
286     ret.append(encodeString(s));
287     return ret;
288 }
289
290 const char* decodeStringWithLength(const char* p, const char* limit, String& foundString)
291 {
292     ASSERT(limit >= p);
293     int64_t len;
294     p = decodeVarInt(p, limit, len);
295     if (!p)
296         return 0;
297     if (p + len * 2 > limit)
298         return 0;
299
300     foundString = decodeString(p, p + len * 2);
301     p += len * 2;
302     return p;
303 }
304
305 int compareEncodedStringsWithLength(const char*& p, const char* limitP, const char*& q, const char* limitQ)
306 {
307     ASSERT(&p != &q);
308     ASSERT(limitP >= p);
309     ASSERT(limitQ >= q);
310     int64_t lenP, lenQ;
311     p = decodeVarInt(p, limitP, lenP);
312     q = decodeVarInt(q, limitQ, lenQ);
313     ASSERT(p && q);
314     ASSERT(lenP >= 0);
315     ASSERT(lenQ >= 0);
316     ASSERT(p + lenP * 2 <= limitP);
317     ASSERT(q + lenQ * 2 <= limitQ);
318
319     const char* startP = p;
320     const char* startQ = q;
321     p += lenP * 2;
322     q += lenQ * 2;
323
324     if (p > limitP || q > limitQ)
325         return 0;
326
327     const size_t lmin = static_cast<size_t>(lenP < lenQ ? lenP : lenQ);
328     if (int x = memcmp(startP, startQ, lmin * 2))
329         return x;
330
331     if (lenP == lenQ)
332         return 0;
333
334     return (lenP > lenQ) ? 1 : -1;
335 }
336
337 Vector<char> encodeDouble(double x)
338 {
339     // FIXME: It would be nice if we could be byte order independent.
340     const char* p = reinterpret_cast<char*>(&x);
341     Vector<char> v;
342     v.append(p, sizeof(x));
343     ASSERT(v.size() == sizeof(x));
344     return v;
345 }
346
347 const char* decodeDouble(const char* p, const char* limit, double* d)
348 {
349     if (p + sizeof(*d) > limit)
350         return 0;
351
352     char* x = reinterpret_cast<char*>(d);
353     for (size_t i = 0; i < sizeof(*d); ++i)
354         *x++ = *p++;
355     return p;
356 }
357
358 Vector<char> encodeIDBKey(const IDBKey& key)
359 {
360     Vector<char> ret;
361     encodeIDBKey(key, ret);
362     return ret;
363 }
364
365 void encodeIDBKey(const IDBKey& key, Vector<char>& into)
366 {
367     size_t previousSize = into.size();
368     switch (key.type()) {
369     case IDBKey::InvalidType:
370     case IDBKey::MinType:
371         ASSERT_NOT_REACHED();
372         into.append(encodeByte(kIDBKeyNullTypeByte));
373         return;
374     case IDBKey::ArrayType:
375         {
376             into.append(encodeByte(kIDBKeyArrayTypeByte));
377             size_t length = key.array().size();
378             into.append(encodeVarInt(length));
379             for (size_t i = 0; i < length; ++i)
380                 encodeIDBKey(*key.array()[i], into);
381             ASSERT_UNUSED(previousSize, into.size() > previousSize);
382             return;
383         }
384     case IDBKey::StringType:
385         into.append(encodeByte(kIDBKeyStringTypeByte));
386         into.append(encodeStringWithLength(key.string()));
387         ASSERT_UNUSED(previousSize, into.size() > previousSize);
388         return;
389     case IDBKey::DateType:
390         into.append(encodeByte(kIDBKeyDateTypeByte));
391         into.append(encodeDouble(key.date()));
392         ASSERT_UNUSED(previousSize, into.size() - previousSize == 9);
393         return;
394     case IDBKey::NumberType:
395         into.append(encodeByte(kIDBKeyNumberTypeByte));
396         into.append(encodeDouble(key.number()));
397         ASSERT_UNUSED(previousSize, into.size() - previousSize == 9);
398         return;
399     }
400
401     ASSERT_NOT_REACHED();
402 }
403
404
405 const char* decodeIDBKey(const char* p, const char* limit, RefPtr<IDBKey>& foundKey)
406 {
407     ASSERT(limit >= p);
408     if (p >= limit)
409         return 0;
410
411     unsigned char type = *p++;
412
413     switch (type) {
414     case kIDBKeyNullTypeByte:
415         foundKey = IDBKey::createInvalid();
416         return p;
417
418     case kIDBKeyArrayTypeByte:
419         {
420             int64_t length;
421             p = decodeVarInt(p, limit, length);
422             if (!p)
423                 return 0;
424             if (length < 0)
425                 return 0;
426             IDBKey::KeyArray array;
427             while (length--) {
428                 RefPtr<IDBKey> key;
429                 p = decodeIDBKey(p, limit, key);
430                 if (!p)
431                     return 0;
432                 array.append(key);
433             }
434             foundKey = IDBKey::createArray(array);
435             return p;
436         }
437     case kIDBKeyStringTypeByte:
438         {
439             String s;
440             p = decodeStringWithLength(p, limit, s);
441             if (!p)
442                 return 0;
443             foundKey = IDBKey::createString(s);
444             return p;
445         }
446     case kIDBKeyDateTypeByte:
447         {
448             double d;
449             p = decodeDouble(p, limit, &d);
450             if (!p)
451                 return 0;
452             foundKey = IDBKey::createDate(d);
453             return p;
454         }
455     case kIDBKeyNumberTypeByte:
456         {
457             double d;
458             p = decodeDouble(p, limit, &d);
459             if (!p)
460                 return 0;
461             foundKey = IDBKey::createNumber(d);
462             return p;
463         }
464     }
465
466     ASSERT_NOT_REACHED();
467     return 0;
468 }
469
470 const char* extractEncodedIDBKey(const char* start, const char* limit, Vector<char>* result)
471 {
472     ASSERT(result);
473     const char* p = start;
474     if (p >= limit)
475         return 0;
476
477     unsigned char type = *p++;
478
479     switch (type) {
480     case kIDBKeyNullTypeByte:
481     case kIDBKeyMinKeyTypeByte:
482         *result = encodeByte(type);
483         return p;
484     case kIDBKeyArrayTypeByte:
485         {
486             int64_t length;
487             p = decodeVarInt(p, limit, length);
488             if (!p)
489                 return 0;
490             if (length < 0)
491                 return 0;
492             result->clear();
493             result->append(start, p - start);
494             while (length--) {
495                 Vector<char> subkey;
496                 p = extractEncodedIDBKey(p, limit, &subkey);
497                 if (!p)
498                     return 0;
499                 result->append(subkey);
500             }
501             return p;
502         }
503     case kIDBKeyStringTypeByte:
504         {
505             int64_t length;
506             p = decodeVarInt(p, limit, length);
507             if (!p)
508                 return 0;
509             if (p + length * 2 > limit)
510                 return 0;
511             result->clear();
512             result->append(start, p - start + length * 2);
513             return p + length * 2;
514         }
515     case kIDBKeyDateTypeByte:
516     case kIDBKeyNumberTypeByte:
517         if (p + sizeof(double) > limit)
518             return 0;
519         result->clear();
520         result->append(start, 1 + sizeof(double));
521         return p + sizeof(double);
522     }
523     ASSERT_NOT_REACHED();
524     return 0;
525 }
526
527 static IDBKey::Type keyTypeByteToKeyType(unsigned char type)
528 {
529     switch (type) {
530     case kIDBKeyNullTypeByte:
531         return IDBKey::InvalidType;
532     case kIDBKeyArrayTypeByte:
533         return IDBKey::ArrayType;
534     case kIDBKeyStringTypeByte:
535         return IDBKey::StringType;
536     case kIDBKeyDateTypeByte:
537         return IDBKey::DateType;
538     case kIDBKeyNumberTypeByte:
539         return IDBKey::NumberType;
540     case kIDBKeyMinKeyTypeByte:
541         return IDBKey::MinType;
542     }
543
544     ASSERT_NOT_REACHED();
545     return IDBKey::InvalidType;
546 }
547
548 int compareEncodedIDBKeys(const char*& p, const char* limitA, const char*& q, const char* limitB)
549 {
550     ASSERT(&p != &q);
551     ASSERT(p < limitA);
552     ASSERT(q < limitB);
553     unsigned char typeA = *p++;
554     unsigned char typeB = *q++;
555
556     if (int x = IDBKey::compareTypes(keyTypeByteToKeyType(typeA), keyTypeByteToKeyType(typeB)))
557         return x;
558
559     switch (typeA) {
560     case kIDBKeyNullTypeByte:
561     case kIDBKeyMinKeyTypeByte:
562         // Null type or max type; no payload to compare.
563         return 0;
564     case kIDBKeyArrayTypeByte:
565         {
566             int64_t lengthA, lengthB;
567             p = decodeVarInt(p, limitA, lengthA);
568             if (!p)
569                 return 0;
570             q = decodeVarInt(q, limitB, lengthB);
571             if (!q)
572                 return 0;
573             if (lengthA < 0 || lengthB < 0)
574                 return 0;
575             for (int64_t i = 0; i < lengthA && i < lengthB; ++i) {
576                 if (int cmp = compareEncodedIDBKeys(p, limitA, q, limitB))
577                     return cmp;
578             }
579             if (lengthA < lengthB)
580                 return -1;
581             if (lengthA > lengthB)
582                 return 1;
583             return 0;
584         }
585     case kIDBKeyStringTypeByte:
586         return compareEncodedStringsWithLength(p, limitA, q, limitB);
587     case kIDBKeyDateTypeByte:
588     case kIDBKeyNumberTypeByte:
589         {
590             double d, e;
591             p = decodeDouble(p, limitA, &d);
592             ASSERT(p);
593             q = decodeDouble(q, limitB, &e);
594             ASSERT(q);
595             if (d < e)
596                 return -1;
597             if (d > e)
598                 return 1;
599             return 0;
600         }
601     }
602
603     ASSERT_NOT_REACHED();
604     return 0;
605 }
606
607 int compareEncodedIDBKeys(const Vector<char>& keyA, const Vector<char>& keyB)
608 {
609     ASSERT(keyA.size() >= 1);
610     ASSERT(keyB.size() >= 1);
611
612     const char* p = keyA.data();
613     const char* limitA = p + keyA.size();
614     const char* q = keyB.data();
615     const char* limitB = q + keyB.size();
616
617     return compareEncodedIDBKeys(p, limitA, q, limitB);
618 }
619
620 namespace {
621 template<typename KeyType>
622 int decodeAndCompare(const LevelDBSlice& a, const LevelDBSlice& b)
623 {
624     KeyType keyA;
625     KeyType keyB;
626
627     const char* ptrA = KeyType::decode(a.begin(), a.end(), &keyA);
628     ASSERT_UNUSED(ptrA, ptrA);
629     const char* ptrB = KeyType::decode(b.begin(), b.end(), &keyB);
630     ASSERT_UNUSED(ptrB, ptrB);
631
632     return keyA.compare(keyB);
633 }
634 }
635
636 int compare(const LevelDBSlice& a, const LevelDBSlice& b, bool indexKeys)
637 {
638     const char* ptrA = a.begin();
639     const char* ptrB = b.begin();
640     const char* endA = a.end();
641     const char* endB = b.end();
642
643     KeyPrefix prefixA;
644     KeyPrefix prefixB;
645
646     ptrA = KeyPrefix::decode(ptrA, endA, &prefixA);
647     ptrB = KeyPrefix::decode(ptrB, endB, &prefixB);
648     ASSERT(ptrA);
649     ASSERT(ptrB);
650
651     if (int x = prefixA.compare(prefixB))
652         return x;
653
654     if (prefixA.type() == KeyPrefix::kGlobalMetaData) {
655         ASSERT(ptrA != endA);
656         ASSERT(ptrB != endB);
657
658         unsigned char typeByteA = *ptrA++;
659         unsigned char typeByteB = *ptrB++;
660
661         if (int x = typeByteA - typeByteB)
662             return x;
663
664         if (typeByteA <= 1)
665             return 0;
666         if (typeByteA == kDatabaseFreeListTypeByte)
667             return decodeAndCompare<DatabaseFreeListKey>(a, b);
668         if (typeByteA == kDatabaseNameTypeByte)
669             return decodeAndCompare<DatabaseNameKey>(a, b);
670     }
671
672     if (prefixA.type() == KeyPrefix::kDatabaseMetaData) {
673         ASSERT(ptrA != endA);
674         ASSERT(ptrB != endB);
675
676         unsigned char typeByteA = *ptrA++;
677         unsigned char typeByteB = *ptrB++;
678
679         if (int x = typeByteA - typeByteB)
680             return x;
681
682         if (typeByteA <= 3)
683             return 0;
684
685         if (typeByteA == kObjectStoreMetaDataTypeByte)
686             return decodeAndCompare<ObjectStoreMetaDataKey>(a, b);
687         if (typeByteA == kIndexMetaDataTypeByte)
688             return decodeAndCompare<IndexMetaDataKey>(a, b);
689         if (typeByteA == kObjectStoreFreeListTypeByte)
690             return decodeAndCompare<ObjectStoreFreeListKey>(a, b);
691         if (typeByteA == kIndexFreeListTypeByte)
692             return decodeAndCompare<IndexFreeListKey>(a, b);
693         if (typeByteA == kObjectStoreNamesTypeByte)
694             return decodeAndCompare<ObjectStoreNamesKey>(a, b);
695         if (typeByteA == kIndexNamesKeyTypeByte)
696             return decodeAndCompare<IndexNamesKey>(a, b);
697
698         return 0;
699         ASSERT_NOT_REACHED();
700     }
701
702     if (prefixA.type() == KeyPrefix::kObjectStoreData) {
703         if (ptrA == endA && ptrB == endB)
704             return 0;
705         if (ptrA == endA)
706             return -1;
707         if (ptrB == endB)
708             return 1; // FIXME: This case of non-existing user keys should not have to be handled this way.
709
710         return decodeAndCompare<ObjectStoreDataKey>(a, b);
711     }
712     if (prefixA.type() == KeyPrefix::kExistsEntry) {
713         if (ptrA == endA && ptrB == endB)
714             return 0;
715         if (ptrA == endA)
716             return -1;
717         if (ptrB == endB)
718             return 1; // FIXME: This case of non-existing user keys should not have to be handled this way.
719
720         return decodeAndCompare<ExistsEntryKey>(a, b);
721     }
722     if (prefixA.type() == KeyPrefix::kIndexData) {
723         if (ptrA == endA && ptrB == endB)
724             return 0;
725         if (ptrA == endA)
726             return -1;
727         if (ptrB == endB)
728             return 1; // FIXME: This case of non-existing user keys should not have to be handled this way.
729
730         IndexDataKey indexDataKeyA;
731         IndexDataKey indexDataKeyB;
732
733         ptrA = IndexDataKey::decode(a.begin(), endA, &indexDataKeyA);
734         ptrB = IndexDataKey::decode(b.begin(), endB, &indexDataKeyB);
735         ASSERT(ptrA);
736         ASSERT(ptrB);
737
738         bool ignoreSequenceNumber = indexKeys;
739         return indexDataKeyA.compare(indexDataKeyB, ignoreSequenceNumber);
740     }
741
742     ASSERT_NOT_REACHED();
743     return 0;
744 }
745
746
747 KeyPrefix::KeyPrefix()
748     : m_databaseId(kInvalidType)
749     , m_objectStoreId(kInvalidType)
750     , m_indexId(kInvalidType)
751 {
752 }
753
754 KeyPrefix::KeyPrefix(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
755     : m_databaseId(databaseId)
756     , m_objectStoreId(objectStoreId)
757     , m_indexId(indexId)
758 {
759 }
760
761 const char* KeyPrefix::decode(const char* start, const char* limit, KeyPrefix* result)
762 {
763     if (start == limit)
764         return 0;
765
766     unsigned char firstByte = *start++;
767
768     int databaseIdBytes = ((firstByte >> 5) & 0x7) + 1;
769     int objectStoreIdBytes = ((firstByte >> 2) & 0x7) + 1;
770     int indexIdBytes = (firstByte & 0x3) + 1;
771
772     if (start + databaseIdBytes + objectStoreIdBytes + indexIdBytes > limit)
773         return 0;
774
775     result->m_databaseId = decodeInt(start, start + databaseIdBytes);
776     start += databaseIdBytes;
777     result->m_objectStoreId = decodeInt(start, start + objectStoreIdBytes);
778     start += objectStoreIdBytes;
779     result->m_indexId = decodeInt(start, start + indexIdBytes);
780     start += indexIdBytes;
781
782     return start;
783 }
784
785 Vector<char> KeyPrefix::encode() const
786 {
787     ASSERT(m_databaseId != kInvalidId);
788     ASSERT(m_objectStoreId != kInvalidId);
789     ASSERT(m_indexId != kInvalidId);
790
791     Vector<char> databaseIdString = encodeInt(m_databaseId);
792     Vector<char> objectStoreIdString = encodeInt(m_objectStoreId);
793     Vector<char> indexIdString = encodeInt(m_indexId);
794
795     ASSERT(databaseIdString.size() <= 8);
796     ASSERT(objectStoreIdString.size() <= 8);
797     ASSERT(indexIdString.size() <= 4);
798
799
800     unsigned char firstByte = (databaseIdString.size() - 1) << 5 | (objectStoreIdString.size() - 1) << 2 | (indexIdString.size() - 1);
801     Vector<char> ret;
802     ret.append(firstByte);
803     ret.append(databaseIdString);
804     ret.append(objectStoreIdString);
805     ret.append(indexIdString);
806
807     return ret;
808 }
809
810 int KeyPrefix::compare(const KeyPrefix& other) const
811 {
812     ASSERT(m_databaseId != kInvalidId);
813     ASSERT(m_objectStoreId != kInvalidId);
814     ASSERT(m_indexId != kInvalidId);
815
816     if (m_databaseId != other.m_databaseId)
817         return compareInts(m_databaseId, other.m_databaseId);
818     if (m_objectStoreId != other.m_objectStoreId)
819         return compareInts(m_objectStoreId, other.m_objectStoreId);
820     if (m_indexId != other.m_indexId)
821         return compareInts(m_indexId, other.m_indexId);
822     return 0;
823 }
824
825 KeyPrefix::Type KeyPrefix::type() const
826 {
827     ASSERT(m_databaseId != kInvalidId);
828     ASSERT(m_objectStoreId != kInvalidId);
829     ASSERT(m_indexId != kInvalidId);
830
831     if (!m_databaseId)
832         return kGlobalMetaData;
833     if (!m_objectStoreId)
834         return kDatabaseMetaData;
835     if (m_indexId == kObjectStoreDataIndexId)
836         return kObjectStoreData;
837     if (m_indexId == kExistsEntryIndexId)
838         return kExistsEntry;
839     if (m_indexId >= kMinimumIndexId)
840         return kIndexData;
841
842     ASSERT_NOT_REACHED();
843     return kInvalidType;
844 }
845
846 Vector<char> SchemaVersionKey::encode()
847 {
848     KeyPrefix prefix(0, 0, 0);
849     Vector<char> ret = prefix.encode();
850     ret.append(encodeByte(kSchemaVersionTypeByte));
851     return ret;
852 }
853
854 Vector<char> MaxDatabaseIdKey::encode()
855 {
856     KeyPrefix prefix(0, 0, 0);
857     Vector<char> ret = prefix.encode();
858     ret.append(encodeByte(kMaxDatabaseIdTypeByte));
859     return ret;
860 }
861
862 DatabaseFreeListKey::DatabaseFreeListKey()
863     : m_databaseId(-1)
864 {
865 }
866
867 const char* DatabaseFreeListKey::decode(const char* start, const char* limit, DatabaseFreeListKey* result)
868 {
869     KeyPrefix prefix;
870     const char *p = KeyPrefix::decode(start, limit, &prefix);
871     if (!p)
872         return 0;
873     ASSERT(!prefix.m_databaseId);
874     ASSERT(!prefix.m_objectStoreId);
875     ASSERT(!prefix.m_indexId);
876     if (p == limit)
877         return 0;
878     unsigned char typeByte = *p++;
879     ASSERT_UNUSED(typeByte, typeByte == kDatabaseFreeListTypeByte);
880     if (p == limit)
881         return 0;
882     return decodeVarInt(p, limit, result->m_databaseId);
883 }
884
885 Vector<char> DatabaseFreeListKey::encode(int64_t databaseId)
886 {
887     KeyPrefix prefix(0, 0, 0);
888     Vector<char> ret = prefix.encode();
889     ret.append(encodeByte(kDatabaseFreeListTypeByte));
890     ret.append(encodeVarInt(databaseId));
891     return ret;
892 }
893
894 Vector<char> DatabaseFreeListKey::encodeMaxKey()
895 {
896     return encode(INT64_MAX);
897 }
898
899 int64_t DatabaseFreeListKey::databaseId() const
900 {
901     ASSERT(m_databaseId >= 0);
902     return m_databaseId;
903 }
904
905 int DatabaseFreeListKey::compare(const DatabaseFreeListKey& other) const
906 {
907     ASSERT(m_databaseId >= 0);
908     return compareInts(m_databaseId, other.m_databaseId);
909 }
910
911 const char* DatabaseNameKey::decode(const char* start, const char* limit, DatabaseNameKey* result)
912 {
913     KeyPrefix prefix;
914     const char* p = KeyPrefix::decode(start, limit, &prefix);
915     if (!p)
916         return p;
917     ASSERT(!prefix.m_databaseId);
918     ASSERT(!prefix.m_objectStoreId);
919     ASSERT(!prefix.m_indexId);
920     if (p == limit)
921         return 0;
922     unsigned char typeByte = *p++;
923     ASSERT_UNUSED(typeByte, typeByte == kDatabaseNameTypeByte);
924     if (p == limit)
925         return 0;
926     p = decodeStringWithLength(p, limit, result->m_origin);
927     if (!p)
928         return 0;
929     return decodeStringWithLength(p, limit, result->m_databaseName);
930 }
931
932 Vector<char> DatabaseNameKey::encode(const String& origin, const String& databaseName)
933 {
934     KeyPrefix prefix(0, 0, 0);
935     Vector<char> ret = prefix.encode();
936     ret.append(encodeByte(kDatabaseNameTypeByte));
937     ret.append(encodeStringWithLength(origin));
938     ret.append(encodeStringWithLength(databaseName));
939     return ret;
940 }
941
942 Vector<char> DatabaseNameKey::encodeMinKeyForOrigin(const String& origin)
943 {
944     return encode(origin, "");
945 }
946
947 Vector<char> DatabaseNameKey::encodeStopKeyForOrigin(const String& origin)
948 {
949     // just after origin in collation order
950     return encodeMinKeyForOrigin(origin + "\x01");
951 }
952
953 int DatabaseNameKey::compare(const DatabaseNameKey& other)
954 {
955     if (int x = codePointCompare(m_origin, other.m_origin))
956         return x;
957     return codePointCompare(m_databaseName, other.m_databaseName);
958 }
959
960 Vector<char> DatabaseMetaDataKey::encode(int64_t databaseId, MetaDataType metaDataType)
961 {
962     KeyPrefix prefix(databaseId, 0, 0);
963     Vector<char> ret = prefix.encode();
964     ret.append(encodeByte(metaDataType));
965     return ret;
966 }
967
968 ObjectStoreMetaDataKey::ObjectStoreMetaDataKey()
969     : m_objectStoreId(-1)
970     , m_metaDataType(-1)
971 {
972 }
973
974 const char* ObjectStoreMetaDataKey::decode(const char* start, const char* limit, ObjectStoreMetaDataKey* result)
975 {
976     KeyPrefix prefix;
977     const char* p = KeyPrefix::decode(start, limit, &prefix);
978     if (!p)
979         return 0;
980     ASSERT(prefix.m_databaseId);
981     ASSERT(!prefix.m_objectStoreId);
982     ASSERT(!prefix.m_indexId);
983     if (p == limit)
984         return 0;
985     unsigned char typeByte = *p++;
986     ASSERT_UNUSED(typeByte, typeByte == kObjectStoreMetaDataTypeByte);
987     if (p == limit)
988         return 0;
989     p = decodeVarInt(p, limit, result->m_objectStoreId);
990     if (!p)
991         return 0;
992     ASSERT(result->m_objectStoreId);
993     if (p == limit)
994         return 0;
995     return decodeVarInt(p, limit, result->m_metaDataType);
996 }
997
998 Vector<char> ObjectStoreMetaDataKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t metaDataType)
999 {
1000     KeyPrefix prefix(databaseId, 0, 0);
1001     Vector<char> ret = prefix.encode();
1002     ret.append(encodeByte(kObjectStoreMetaDataTypeByte));
1003     ret.append(encodeVarInt(objectStoreId));
1004     ret.append(encodeVarInt(metaDataType));
1005     return ret;
1006 }
1007
1008 Vector<char> ObjectStoreMetaDataKey::encodeMaxKey(int64_t databaseId)
1009 {
1010     return encode(databaseId, INT64_MAX, INT64_MAX);
1011 }
1012
1013 Vector<char> ObjectStoreMetaDataKey::encodeMaxKey(int64_t databaseId, int64_t objectStoreId)
1014 {
1015     return encode(databaseId, objectStoreId, INT64_MAX);
1016 }
1017
1018 int64_t ObjectStoreMetaDataKey::objectStoreId() const
1019 {
1020     ASSERT(m_objectStoreId >= 0);
1021     return m_objectStoreId;
1022 }
1023 int64_t ObjectStoreMetaDataKey::metaDataType() const
1024 {
1025     ASSERT(m_metaDataType >= 0);
1026     return m_metaDataType;
1027 }
1028
1029 int ObjectStoreMetaDataKey::compare(const ObjectStoreMetaDataKey& other)
1030 {
1031     ASSERT(m_objectStoreId >= 0);
1032     ASSERT(m_metaDataType >= 0);
1033     if (int x = compareInts(m_objectStoreId, other.m_objectStoreId))
1034         return x;
1035     return m_metaDataType - other.m_metaDataType;
1036 }
1037
1038 IndexMetaDataKey::IndexMetaDataKey()
1039     : m_objectStoreId(-1)
1040     , m_indexId(-1)
1041     , m_metaDataType(0)
1042 {
1043 }
1044
1045 const char* IndexMetaDataKey::decode(const char* start, const char* limit, IndexMetaDataKey* result)
1046 {
1047     KeyPrefix prefix;
1048     const char* p = KeyPrefix::decode(start, limit, &prefix);
1049     if (!p)
1050         return 0;
1051     ASSERT(prefix.m_databaseId);
1052     ASSERT(!prefix.m_objectStoreId);
1053     ASSERT(!prefix.m_indexId);
1054     if (p == limit)
1055         return 0;
1056     unsigned char typeByte = *p++;
1057     ASSERT_UNUSED(typeByte, typeByte == kIndexMetaDataTypeByte);
1058     if (p == limit)
1059         return 0;
1060     p = decodeVarInt(p, limit, result->m_objectStoreId);
1061     if (!p)
1062         return 0;
1063     p = decodeVarInt(p, limit, result->m_indexId);
1064     if (!p)
1065         return 0;
1066     if (p == limit)
1067         return 0;
1068     result->m_metaDataType = *p++;
1069     return p;
1070 }
1071
1072 Vector<char> IndexMetaDataKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId, unsigned char metaDataType)
1073 {
1074     KeyPrefix prefix(databaseId, 0, 0);
1075     Vector<char> ret = prefix.encode();
1076     ret.append(encodeByte(kIndexMetaDataTypeByte));
1077     ret.append(encodeVarInt(objectStoreId));
1078     ret.append(encodeVarInt(indexId));
1079     ret.append(encodeByte(metaDataType));
1080     return ret;
1081 }
1082
1083 Vector<char> IndexMetaDataKey::encodeMaxKey(int64_t databaseId, int64_t objectStoreId)
1084 {
1085     return encode(databaseId, objectStoreId, INT64_MAX, 255);
1086 }
1087
1088 int IndexMetaDataKey::compare(const IndexMetaDataKey& other)
1089 {
1090     ASSERT(m_objectStoreId >= 0);
1091     ASSERT(m_indexId >= 0);
1092
1093     if (int x = compareInts(m_objectStoreId, other.m_objectStoreId))
1094         return x;
1095     if (int x = compareInts(m_indexId, other.m_indexId))
1096         return x;
1097     return m_metaDataType - other.m_metaDataType;
1098 }
1099
1100 int64_t IndexMetaDataKey::indexId() const
1101 {
1102     ASSERT(m_indexId >= 0);
1103     return m_indexId;
1104 }
1105
1106 ObjectStoreFreeListKey::ObjectStoreFreeListKey()
1107     : m_objectStoreId(-1)
1108 {
1109 }
1110
1111 const char* ObjectStoreFreeListKey::decode(const char* start, const char* limit, ObjectStoreFreeListKey* result)
1112 {
1113     KeyPrefix prefix;
1114     const char *p = KeyPrefix::decode(start, limit, &prefix);
1115     if (!p)
1116         return 0;
1117     ASSERT(prefix.m_databaseId);
1118     ASSERT(!prefix.m_objectStoreId);
1119     ASSERT(!prefix.m_indexId);
1120     if (p == limit)
1121         return 0;
1122     unsigned char typeByte = *p++;
1123     ASSERT_UNUSED(typeByte, typeByte == kObjectStoreFreeListTypeByte);
1124     if (p == limit)
1125         return 0;
1126     return decodeVarInt(p, limit, result->m_objectStoreId);
1127 }
1128
1129 Vector<char> ObjectStoreFreeListKey::encode(int64_t databaseId, int64_t objectStoreId)
1130 {
1131     KeyPrefix prefix(databaseId, 0, 0);
1132     Vector<char> ret = prefix.encode();
1133     ret.append(encodeByte(kObjectStoreFreeListTypeByte));
1134     ret.append(encodeVarInt(objectStoreId));
1135     return ret;
1136 }
1137
1138 Vector<char> ObjectStoreFreeListKey::encodeMaxKey(int64_t databaseId)
1139 {
1140     return encode(databaseId, INT64_MAX);
1141 }
1142
1143 int64_t ObjectStoreFreeListKey::objectStoreId() const
1144 {
1145     ASSERT(m_objectStoreId >= 0);
1146     return m_objectStoreId;
1147 }
1148
1149 int ObjectStoreFreeListKey::compare(const ObjectStoreFreeListKey& other)
1150 {
1151     // FIXME: It may seem strange that we're not comparing database id's,
1152     // but that comparison will have been made earlier.
1153     // We should probably make this more clear, though...
1154     ASSERT(m_objectStoreId >= 0);
1155     return compareInts(m_objectStoreId, other.m_objectStoreId);
1156 }
1157
1158 IndexFreeListKey::IndexFreeListKey()
1159     : m_objectStoreId(-1)
1160     , m_indexId(-1)
1161 {
1162 }
1163
1164 const char* IndexFreeListKey::decode(const char* start, const char* limit, IndexFreeListKey* result)
1165 {
1166     KeyPrefix prefix;
1167     const char* p = KeyPrefix::decode(start, limit, &prefix);
1168     if (!p)
1169         return 0;
1170     ASSERT(prefix.m_databaseId);
1171     ASSERT(!prefix.m_objectStoreId);
1172     ASSERT(!prefix.m_indexId);
1173     if (p == limit)
1174         return 0;
1175     unsigned char typeByte = *p++;
1176     ASSERT_UNUSED(typeByte, typeByte == kIndexFreeListTypeByte);
1177     if (p == limit)
1178         return 0;
1179     p = decodeVarInt(p, limit, result->m_objectStoreId);
1180     if (!p)
1181         return 0;
1182     return decodeVarInt(p, limit, result->m_indexId);
1183 }
1184
1185 Vector<char> IndexFreeListKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
1186 {
1187     KeyPrefix prefix(databaseId, 0, 0);
1188     Vector<char> ret = prefix.encode();
1189     ret.append(encodeByte(kIndexFreeListTypeByte));
1190     ret.append(encodeVarInt(objectStoreId));
1191     ret.append(encodeVarInt(indexId));
1192     return ret;
1193 }
1194
1195 Vector<char> IndexFreeListKey::encodeMaxKey(int64_t databaseId, int64_t objectStoreId)
1196 {
1197     return encode(databaseId, objectStoreId, INT64_MAX);
1198 }
1199
1200 int IndexFreeListKey::compare(const IndexFreeListKey& other)
1201 {
1202     ASSERT(m_objectStoreId >= 0);
1203     ASSERT(m_indexId >= 0);
1204     if (int x = compareInts(m_objectStoreId, other.m_objectStoreId))
1205         return x;
1206     return compareInts(m_indexId, other.m_indexId);
1207 }
1208
1209 int64_t IndexFreeListKey::objectStoreId() const
1210 {
1211     ASSERT(m_objectStoreId >= 0);
1212     return m_objectStoreId;
1213 }
1214
1215 int64_t IndexFreeListKey::indexId() const
1216 {
1217     ASSERT(m_indexId >= 0);
1218     return m_indexId;
1219 }
1220
1221 // FIXME: We never use this to look up object store ids, because a mapping
1222 // is kept in the IDBDatabaseBackendImpl. Can the mapping become unreliable?
1223 // Can we remove this?
1224 const char* ObjectStoreNamesKey::decode(const char* start, const char* limit, ObjectStoreNamesKey* result)
1225 {
1226     KeyPrefix prefix;
1227     const char* p = KeyPrefix::decode(start, limit, &prefix);
1228     if (!p)
1229         return 0;
1230     ASSERT(prefix.m_databaseId);
1231     ASSERT(!prefix.m_objectStoreId);
1232     ASSERT(!prefix.m_indexId);
1233     if (p == limit)
1234         return 0;
1235     unsigned char typeByte = *p++;
1236     ASSERT_UNUSED(typeByte, typeByte == kObjectStoreNamesTypeByte);
1237     return decodeStringWithLength(p, limit, result->m_objectStoreName);
1238 }
1239
1240 Vector<char> ObjectStoreNamesKey::encode(int64_t databaseId, const String& objectStoreName)
1241 {
1242     KeyPrefix prefix(databaseId, 0, 0);
1243     Vector<char> ret = prefix.encode();
1244     ret.append(encodeByte(kObjectStoreNamesTypeByte));
1245     ret.append(encodeStringWithLength(objectStoreName));
1246     return ret;
1247 }
1248
1249 int ObjectStoreNamesKey::compare(const ObjectStoreNamesKey& other)
1250 {
1251     return codePointCompare(m_objectStoreName, other.m_objectStoreName);
1252 }
1253
1254 IndexNamesKey::IndexNamesKey()
1255     : m_objectStoreId(-1)
1256 {
1257 }
1258
1259 // FIXME: We never use this to look up index ids, because a mapping
1260 // is kept at a higher level.
1261 const char* IndexNamesKey::decode(const char* start, const char* limit, IndexNamesKey* result)
1262 {
1263     KeyPrefix prefix;
1264     const char* p = KeyPrefix::decode(start, limit, &prefix);
1265     if (!p)
1266         return 0;
1267     ASSERT(prefix.m_databaseId);
1268     ASSERT(!prefix.m_objectStoreId);
1269     ASSERT(!prefix.m_indexId);
1270     if (p == limit)
1271         return 0;
1272     unsigned char typeByte = *p++;
1273     ASSERT_UNUSED(typeByte, typeByte == kIndexNamesKeyTypeByte);
1274     if (p == limit)
1275         return 0;
1276     p = decodeVarInt(p, limit, result->m_objectStoreId);
1277     if (!p)
1278         return 0;
1279     return decodeStringWithLength(p, limit, result->m_indexName);
1280 }
1281
1282 Vector<char> IndexNamesKey::encode(int64_t databaseId, int64_t objectStoreId, const String& indexName)
1283 {
1284     KeyPrefix prefix(databaseId, 0, 0);
1285     Vector<char> ret = prefix.encode();
1286     ret.append(encodeByte(kIndexNamesKeyTypeByte));
1287     ret.append(encodeVarInt(objectStoreId));
1288     ret.append(encodeStringWithLength(indexName));
1289     return ret;
1290 }
1291
1292 int IndexNamesKey::compare(const IndexNamesKey& other)
1293 {
1294     ASSERT(m_objectStoreId >= 0);
1295     if (int x = compareInts(m_objectStoreId, other.m_objectStoreId))
1296         return x;
1297     return codePointCompare(m_indexName, other.m_indexName);
1298 }
1299
1300 const char* ObjectStoreDataKey::decode(const char* start, const char* end, ObjectStoreDataKey* result)
1301 {
1302     KeyPrefix prefix;
1303     const char* p = KeyPrefix::decode(start, end, &prefix);
1304     if (!p)
1305         return 0;
1306     ASSERT(prefix.m_databaseId);
1307     ASSERT(prefix.m_objectStoreId);
1308     ASSERT(prefix.m_indexId == kSpecialIndexNumber);
1309     if (p == end)
1310         return 0;
1311     return extractEncodedIDBKey(p, end, &result->m_encodedUserKey);
1312 }
1313
1314 Vector<char> ObjectStoreDataKey::encode(int64_t databaseId, int64_t objectStoreId, const Vector<char> encodedUserKey)
1315 {
1316     KeyPrefix prefix(databaseId, objectStoreId, kSpecialIndexNumber);
1317     Vector<char> ret = prefix.encode();
1318     ret.append(encodedUserKey);
1319
1320     return ret;
1321 }
1322
1323 Vector<char> ObjectStoreDataKey::encode(int64_t databaseId, int64_t objectStoreId, const IDBKey& userKey)
1324 {
1325     return encode(databaseId, objectStoreId, encodeIDBKey(userKey));
1326 }
1327
1328 int ObjectStoreDataKey::compare(const ObjectStoreDataKey& other)
1329 {
1330     return compareEncodedIDBKeys(m_encodedUserKey, other.m_encodedUserKey);
1331 }
1332
1333 PassRefPtr<IDBKey> ObjectStoreDataKey::userKey() const
1334 {
1335     RefPtr<IDBKey> key;
1336     decodeIDBKey(m_encodedUserKey.begin(), m_encodedUserKey.end(), key);
1337     return key;
1338 }
1339
1340 const int64_t ObjectStoreDataKey::kSpecialIndexNumber = kObjectStoreDataIndexId;
1341
1342 const char* ExistsEntryKey::decode(const char* start, const char* end, ExistsEntryKey* result)
1343 {
1344     KeyPrefix prefix;
1345     const char* p = KeyPrefix::decode(start, end, &prefix);
1346     if (!p)
1347         return 0;
1348     ASSERT(prefix.m_databaseId);
1349     ASSERT(prefix.m_objectStoreId);
1350     ASSERT(prefix.m_indexId == kSpecialIndexNumber);
1351     if (p == end)
1352         return 0;
1353     return extractEncodedIDBKey(p, end, &result->m_encodedUserKey);
1354 }
1355
1356 Vector<char> ExistsEntryKey::encode(int64_t databaseId, int64_t objectStoreId, const Vector<char>& encodedKey)
1357 {
1358     KeyPrefix prefix(databaseId, objectStoreId, kSpecialIndexNumber);
1359     Vector<char> ret = prefix.encode();
1360     ret.append(encodedKey);
1361     return ret;
1362 }
1363
1364 Vector<char> ExistsEntryKey::encode(int64_t databaseId, int64_t objectStoreId, const IDBKey& userKey)
1365 {
1366     return encode(databaseId, objectStoreId, encodeIDBKey(userKey));
1367 }
1368
1369 int ExistsEntryKey::compare(const ExistsEntryKey& other)
1370 {
1371     return compareEncodedIDBKeys(m_encodedUserKey, other.m_encodedUserKey);
1372 }
1373
1374 PassRefPtr<IDBKey> ExistsEntryKey::userKey() const
1375 {
1376     RefPtr<IDBKey> key;
1377     decodeIDBKey(m_encodedUserKey.begin(), m_encodedUserKey.end(), key);
1378     return key;
1379 }
1380
1381 const int64_t ExistsEntryKey::kSpecialIndexNumber = kExistsEntryIndexId;
1382
1383 IndexDataKey::IndexDataKey()
1384     : m_databaseId(-1)
1385     , m_objectStoreId(-1)
1386     , m_indexId(-1)
1387     , m_sequenceNumber(-1)
1388 {
1389 }
1390
1391 const char* IndexDataKey::decode(const char* start, const char* limit, IndexDataKey* result)
1392 {
1393     KeyPrefix prefix;
1394     const char* p = KeyPrefix::decode(start, limit, &prefix);
1395     if (!p)
1396         return 0;
1397     ASSERT(prefix.m_databaseId);
1398     ASSERT(prefix.m_objectStoreId);
1399     ASSERT(prefix.m_indexId >= kMinimumIndexId);
1400     result->m_databaseId = prefix.m_databaseId;
1401     result->m_objectStoreId = prefix.m_objectStoreId;
1402     result->m_indexId = prefix.m_indexId;
1403     p = extractEncodedIDBKey(p, limit, &result->m_encodedUserKey);
1404     if (!p)
1405         return 0;
1406     if (p == limit) {
1407         result->m_sequenceNumber = -1; // FIXME: We should change it so that all keys have a sequence number. Shouldn't need to handle this case.
1408         return p;
1409     }
1410     return decodeVarInt(p, limit, result->m_sequenceNumber);
1411 }
1412
1413 Vector<char> IndexDataKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const Vector<char>& encodedUserKey, int64_t sequenceNumber)
1414 {
1415     KeyPrefix prefix(databaseId, objectStoreId, indexId);
1416     Vector<char> ret = prefix.encode();
1417     ret.append(encodedUserKey);
1418     ret.append(encodeVarInt(sequenceNumber));
1419     return ret;
1420 }
1421
1422 Vector<char> IndexDataKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& userKey, int64_t sequenceNumber)
1423 {
1424     return encode(databaseId, objectStoreId, indexId, encodeIDBKey(userKey), sequenceNumber);
1425 }
1426
1427 Vector<char> IndexDataKey::encodeMaxKey(int64_t databaseId, int64_t objectStoreId)
1428 {
1429     return encode(databaseId, objectStoreId, INT32_MAX, maxIDBKey(), INT64_MAX);
1430 }
1431
1432 int IndexDataKey::compare(const IndexDataKey& other, bool ignoreSequenceNumber)
1433 {
1434     ASSERT(m_databaseId >= 0);
1435     ASSERT(m_objectStoreId >= 0);
1436     ASSERT(m_indexId >= 0);
1437     if (int x = compareEncodedIDBKeys(m_encodedUserKey, other.m_encodedUserKey))
1438         return x;
1439     if (ignoreSequenceNumber)
1440         return 0;
1441     return compareInts(m_sequenceNumber, other.m_sequenceNumber);
1442 }
1443
1444 int64_t IndexDataKey::databaseId() const
1445 {
1446     ASSERT(m_databaseId >= 0);
1447     return m_databaseId;
1448 }
1449
1450 int64_t IndexDataKey::objectStoreId() const
1451 {
1452     ASSERT(m_objectStoreId >= 0);
1453     return m_objectStoreId;
1454 }
1455
1456 int64_t IndexDataKey::indexId() const
1457 {
1458     ASSERT(m_indexId >= 0);
1459     return m_indexId;
1460 }
1461
1462 PassRefPtr<IDBKey> IndexDataKey::userKey() const
1463 {
1464     RefPtr<IDBKey> key;
1465     decodeIDBKey(m_encodedUserKey.begin(), m_encodedUserKey.end(), key);
1466     return key;
1467 }
1468
1469 } // namespace IDBLevelDBCoding
1470 } // namespace WebCore
1471
1472 #endif // USE(LEVELDB)
1473 #endif // ENABLE(INDEXED_DATABASE)