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