Replace static_cast<SVGStyledElement> with toSVGStyledElement()
[WebKit-https.git] / Source / WebCore / Modules / indexeddb / 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 "IDBKeyPath.h"
34 #include "LevelDBSlice.h"
35 #include <wtf/ByteOrder.h>
36 #include <wtf/text/StringBuilder.h>
37
38 // LevelDB stores key/value pairs. Keys and values are strings of bytes, normally of type Vector<char>.
39 //
40 // The keys in the backing store are variable-length tuples with different types
41 // 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.
42 // The prefix makes sure that data for a specific database, object store, and index are grouped together. The locality is important for performance: common
43 // 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
44 // meta-data only requires one seek.
45 //
46 // Each key type has a class (in square brackets below) which knows how to encode, decode, and compare that key type.
47 //
48 // Global meta-data have keys with prefix (0,0,0), followed by a type byte:
49 //
50 //     <0, 0, 0, 0>                                           => IndexedDB/LevelDB schema version [SchemaVersionKey]
51 //     <0, 0, 0, 1>                                           => The maximum database id ever allocated [MaxDatabaseIdKey]
52 //     <0, 0, 0, 2>                                           => SerializedScriptValue version [DataVersionKey]
53 //     <0, 0, 0, 100, database id>                            => Existence implies the database id is in the free list [DatabaseFreeListKey]
54 //     <0, 0, 0, 201, utf16 origin name, utf16 database name> => Database id [DatabaseNameKey]
55 //
56 //
57 // Database meta-data:
58 //
59 //     Again, the prefix is followed by a type byte.
60 //
61 //     <database id, 0, 0, 0> => utf16 origin name [DatabaseMetaDataKey]
62 //     <database id, 0, 0, 1> => utf16 database name [DatabaseMetaDataKey]
63 //     <database id, 0, 0, 2> => utf16 user version data [DatabaseMetaDataKey]
64 //     <database id, 0, 0, 3> => maximum object store id ever allocated [DatabaseMetaDataKey]
65 //     <database id, 0, 0, 4> => user integer version (var int) [DatabaseMetaDataKey]
66 //
67 //
68 // Object store meta-data:
69 //
70 //     The prefix is followed by a type byte, then a variable-length integer, and then another type byte.
71 //
72 //     <database id, 0, 0, 50, object store id, 0> => utf16 object store name [ObjectStoreMetaDataKey]
73 //     <database id, 0, 0, 50, object store id, 1> => utf16 key path [ObjectStoreMetaDataKey]
74 //     <database id, 0, 0, 50, object store id, 2> => has auto increment [ObjectStoreMetaDataKey]
75 //     <database id, 0, 0, 50, object store id, 3> => is evictable [ObjectStoreMetaDataKey]
76 //     <database id, 0, 0, 50, object store id, 4> => last "version" number [ObjectStoreMetaDataKey]
77 //     <database id, 0, 0, 50, object store id, 5> => maximum index id ever allocated [ObjectStoreMetaDataKey]
78 //     <database id, 0, 0, 50, object store id, 6> => has key path (vs. null) [ObjectStoreMetaDataKey]
79 //     <database id, 0, 0, 50, object store id, 7> => key generator current number [ObjectStoreMetaDataKey]
80 //
81 //
82 // Index meta-data:
83 //
84 //     The prefix is followed by a type byte, then two variable-length integers, and then another type byte.
85 //
86 //     <database id, 0, 0, 100, object store id, index id, 0> => utf16 index name [IndexMetaDataKey]
87 //     <database id, 0, 0, 100, object store id, index id, 1> => are index keys unique [IndexMetaDataKey]
88 //     <database id, 0, 0, 100, object store id, index id, 2> => utf16 key path [IndexMetaDataKey]
89 //     <database id, 0, 0, 100, object store id, index id, 3> => is index multi-entry [IndexMetaDataKey]
90 //
91 //
92 // Other object store and index meta-data:
93 //
94 //     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.
95 //
96 //     <database id, 0, 0, 150, object store id>                   => existence implies the object store id is in the free list [ObjectStoreFreeListKey]
97 //     <database id, 0, 0, 151, object store id, index id>         => existence implies the index id is in the free list [IndexFreeListKey]
98 //     <database id, 0, 0, 200, utf16 object store name>           => object store id [ObjectStoreNamesKey]
99 //     <database id, 0, 0, 201, object store id, utf16 index name> => index id [IndexNamesKey]
100 //
101 //
102 // Object store data:
103 //
104 //     The prefix is followed by a type byte. The user key is an encoded IDBKey.
105 //
106 //     <database id, object store id, 1, user key> => "version", serialized script value [ObjectStoreDataKey]
107 //
108 //
109 // "Exists" entry:
110 //
111 //     The prefix is followed by a type byte. The user key is an encoded IDBKey.
112 //
113 //     <database id, object store id, 2, user key> => "version" [ExistsEntryKey]
114 //
115 //
116 // Index data:
117 //
118 //     The prefix is followed by a type byte. The index key is an encoded IDBKey. The sequence number is a variable length integer.
119 //     The primary key is an encoded IDBKey.
120 //
121 //     <database id, object store id, index id, index key, sequence number, primary key> => "version", primary key [IndexDataKey]
122 //
123 //     (The sequence number is obsolete; it was used to allow two entries with
124 //     the same user (index) key in non-unique indexes prior to the inclusion of
125 //     the primary key in the data. The "version" field is used to weed out stale
126 //     index data. Whenever new object store data is inserted, it gets a new
127 //     "version" number, and new index data is written with this number. When
128 //     the index is used for look-ups, entries are validated against the
129 //     "exists" entries, and records with old "version" numbers are deleted
130 //     when they are encountered in getPrimaryKeyViaIndex,
131 //     IndexCursorImpl::loadCurrentRow, and IndexKeyCursorImpl::loadCurrentRow).
132
133 namespace WebCore {
134 namespace IDBLevelDBCoding {
135
136 #ifndef INT64_MAX
137 #define INT64_MAX 0x7fffffffffffffffLL
138 #endif
139 #ifndef INT32_MAX
140 #define INT32_MAX 0x7fffffffL
141 #endif
142
143 static const unsigned char IDBKeyNullTypeByte = 0;
144 static const unsigned char IDBKeyStringTypeByte = 1;
145 static const unsigned char IDBKeyDateTypeByte = 2;
146 static const unsigned char IDBKeyNumberTypeByte = 3;
147 static const unsigned char IDBKeyArrayTypeByte = 4;
148 static const unsigned char IDBKeyMinKeyTypeByte = 5;
149
150 static const unsigned char IDBKeyPathTypeCodedByte1 = 0;
151 static const unsigned char IDBKeyPathTypeCodedByte2 = 0;
152
153 static const unsigned char ObjectStoreDataIndexId = 1;
154 static const unsigned char ExistsEntryIndexId = 2;
155
156 static const unsigned char SchemaVersionTypeByte = 0;
157 static const unsigned char MaxDatabaseIdTypeByte = 1;
158 static const unsigned char DataVersionTypeByte = 2;
159 static const unsigned char MaxSimpleGlobalMetaDataTypeByte = 3; // Insert before this and increment.
160 static const unsigned char DatabaseFreeListTypeByte = 100;
161 static const unsigned char DatabaseNameTypeByte = 201;
162
163 static const unsigned char ObjectStoreMetaDataTypeByte = 50;
164 static const unsigned char IndexMetaDataTypeByte = 100;
165 static const unsigned char ObjectStoreFreeListTypeByte = 150;
166 static const unsigned char IndexFreeListTypeByte = 151;
167 static const unsigned char ObjectStoreNamesTypeByte = 200;
168 static const unsigned char IndexNamesKeyTypeByte = 201;
169
170 static const unsigned char ObjectMetaDataTypeMaximum = 255;
171 static const unsigned char IndexMetaDataTypeMaximum = 255;
172
173 Vector<char> encodeByte(unsigned char c)
174 {
175     Vector<char, DefaultInlineBufferSize> v;
176     v.append(c);
177
178     ASSERT(v.size() <= DefaultInlineBufferSize);
179     return v;
180 }
181
182 const char* decodeByte(const char* p, const char* limit, unsigned char& foundChar)
183 {
184     if (p >= limit)
185         return 0;
186
187     foundChar = *p++;
188     return p;
189 }
190
191 Vector<char> maxIDBKey()
192 {
193     return encodeByte(IDBKeyNullTypeByte);
194 }
195
196 Vector<char> minIDBKey()
197 {
198     return encodeByte(IDBKeyMinKeyTypeByte);
199 }
200
201 Vector<char> encodeBool(bool b)
202 {
203     Vector<char, DefaultInlineBufferSize> ret;
204     ret.append(b ? 1 : 0);
205
206     ASSERT(ret.size() <= DefaultInlineBufferSize);
207     return ret;
208 }
209
210 bool decodeBool(const char* begin, const char* end)
211 {
212     ASSERT(begin < end);
213     return *begin;
214 }
215
216 Vector<char> encodeInt(int64_t nParam)
217 {
218     ASSERT(nParam >= 0);
219     uint64_t n = static_cast<uint64_t>(nParam);
220     Vector<char, DefaultInlineBufferSize> ret;
221
222     do {
223         unsigned char c = n;
224         ret.append(c);
225         n >>= 8;
226     } while (n);
227
228     ASSERT(ret.size() <= DefaultInlineBufferSize);
229     return ret;
230 }
231
232 int64_t decodeInt(const char* begin, const char* end)
233 {
234     ASSERT(begin <= end);
235     int64_t ret = 0;
236
237     int shift = 0;
238     while (begin < end) {
239         unsigned char c = *begin++;
240         ret |= static_cast<int64_t>(c) << shift;
241         shift += 8;
242     }
243
244     return ret;
245 }
246
247 static int compareInts(int64_t a, int64_t b)
248 {
249     ASSERT(a >= 0);
250     ASSERT(b >= 0);
251
252     int64_t diff = a - b;
253     if (diff < 0)
254         return -1;
255     if (diff > 0)
256         return 1;
257     return 0;
258 }
259
260 Vector<char> encodeVarInt(int64_t nParam)
261 {
262     ASSERT(nParam >= 0);
263     uint64_t n = static_cast<uint64_t>(nParam);
264     Vector<char, DefaultInlineBufferSize> ret;
265
266     do {
267         unsigned char c = n & 0x7f;
268         n >>= 7;
269         if (n)
270             c |= 0x80;
271         ret.append(c);
272     } while (n);
273
274     ASSERT(ret.size() <= DefaultInlineBufferSize);
275     return ret;
276 }
277
278 const char* decodeVarInt(const char* p, const char* limit, int64_t& foundInt)
279 {
280     ASSERT(limit >= p);
281     foundInt = 0;
282     int shift = 0;
283
284     do {
285         if (p >= limit)
286             return 0;
287
288         unsigned char c = *p;
289         foundInt |= static_cast<int64_t>(c & 0x7f) << shift;
290         shift += 7;
291     } while (*p++ & 0x80);
292     return p;
293 }
294
295 Vector<char> encodeString(const String& s)
296 {
297     // Backing store is UTF-16BE, convert from host endianness.
298     size_t length = s.length();
299     Vector<char> ret(length * sizeof(UChar));
300
301     const UChar* src = s.characters();
302     UChar* dst = reinterpret_cast<UChar*>(ret.data());
303     for (unsigned i = 0; i < length; ++i)
304         *dst++ = htons(*src++);
305
306     return ret;
307 }
308
309 String decodeString(const char* start, const char* end)
310 {
311     // Backing store is UTF-16BE, convert to host endianness.
312     ASSERT(end >= start);
313     ASSERT(!((end - start) % sizeof(UChar)));
314
315     size_t length = (end - start) / sizeof(UChar);
316     Vector<UChar> buffer(length);
317
318     const UChar* src = reinterpret_cast<const UChar*>(start);
319     UChar* dst = buffer.data();
320     for (unsigned i = 0; i < length; ++i)
321         *dst++ = ntohs(*src++);
322
323     return String::adopt(buffer);
324 }
325
326 Vector<char> encodeStringWithLength(const String& s)
327 {
328     Vector<char> ret = encodeVarInt(s.length());
329     ret.append(encodeString(s));
330     return ret;
331 }
332
333 const char* decodeStringWithLength(const char* p, const char* limit, String& foundString)
334 {
335     ASSERT(limit >= p);
336     int64_t len;
337     p = decodeVarInt(p, limit, len);
338     if (!p || len < 0 || p + len * 2 > limit)
339         return 0;
340
341     foundString = decodeString(p, p + len * 2);
342     p += len * 2;
343     return p;
344 }
345
346 int compareEncodedStringsWithLength(const char*& p, const char* limitP, const char*& q, const char* limitQ, bool& ok)
347 {
348     ASSERT(&p != &q);
349     ASSERT(limitP >= p);
350     ASSERT(limitQ >= q);
351     int64_t lenP, lenQ;
352     p = decodeVarInt(p, limitP, lenP);
353     q = decodeVarInt(q, limitQ, lenQ);
354     if (!p || !q || lenP < 0 || lenQ < 0) {
355         ok = false;
356         return 0;
357     }
358     ASSERT(p && q);
359     ASSERT(lenP >= 0);
360     ASSERT(lenQ >= 0);
361     ASSERT(p + lenP * 2 <= limitP);
362     ASSERT(q + lenQ * 2 <= limitQ);
363
364     const char* startP = p;
365     const char* startQ = q;
366     p += lenP * 2;
367     q += lenQ * 2;
368
369     if (p > limitP || q > limitQ) {
370         ok = false;
371         return 0;
372     }
373
374     ok = true;
375     const size_t lmin = static_cast<size_t>(lenP < lenQ ? lenP : lenQ);
376     if (int x = memcmp(startP, startQ, lmin * 2))
377         return x;
378
379     if (lenP == lenQ)
380         return 0;
381
382     return (lenP > lenQ) ? 1 : -1;
383 }
384
385 Vector<char> encodeDouble(double x)
386 {
387     // FIXME: It would be nice if we could be byte order independent.
388     const char* p = reinterpret_cast<char*>(&x);
389     Vector<char, DefaultInlineBufferSize> v;
390     v.append(p, sizeof(x));
391
392     ASSERT(v.size() <= DefaultInlineBufferSize);
393     return v;
394 }
395
396 const char* decodeDouble(const char* p, const char* limit, double* d)
397 {
398     if (p + sizeof(*d) > limit)
399         return 0;
400
401     char* x = reinterpret_cast<char*>(d);
402     for (size_t i = 0; i < sizeof(*d); ++i)
403         *x++ = *p++;
404     return p;
405 }
406
407 Vector<char> encodeIDBKey(const IDBKey& key)
408 {
409     Vector<char, DefaultInlineBufferSize> ret;
410     encodeIDBKey(key, ret);
411     return ret;
412 }
413
414 void encodeIDBKey(const IDBKey& key, Vector<char, DefaultInlineBufferSize>& into)
415 {
416     size_t previousSize = into.size();
417     ASSERT(key.isValid());
418     switch (key.type()) {
419     case IDBKey::InvalidType:
420     case IDBKey::MinType:
421         ASSERT_NOT_REACHED();
422         into.append(encodeByte(IDBKeyNullTypeByte));
423         return;
424     case IDBKey::ArrayType: {
425         into.append(encodeByte(IDBKeyArrayTypeByte));
426         size_t length = key.array().size();
427         into.append(encodeVarInt(length));
428         for (size_t i = 0; i < length; ++i)
429             encodeIDBKey(*key.array()[i], into);
430         ASSERT_UNUSED(previousSize, into.size() > previousSize);
431         return;
432     }
433     case IDBKey::StringType:
434         into.append(encodeByte(IDBKeyStringTypeByte));
435         into.append(encodeStringWithLength(key.string()));
436         ASSERT_UNUSED(previousSize, into.size() > previousSize);
437         return;
438     case IDBKey::DateType:
439         into.append(encodeByte(IDBKeyDateTypeByte));
440         into.append(encodeDouble(key.date()));
441         ASSERT_UNUSED(previousSize, into.size() - previousSize == 9);
442         return;
443     case IDBKey::NumberType:
444         into.append(encodeByte(IDBKeyNumberTypeByte));
445         into.append(encodeDouble(key.number()));
446         ASSERT_UNUSED(previousSize, into.size() - previousSize == 9);
447         return;
448     }
449
450     ASSERT_NOT_REACHED();
451 }
452
453
454 const char* decodeIDBKey(const char* p, const char* limit, RefPtr<IDBKey>& foundKey)
455 {
456     ASSERT(limit >= p);
457     if (p >= limit)
458         return 0;
459
460     unsigned char type = *p++;
461
462     switch (type) {
463     case IDBKeyNullTypeByte:
464         foundKey = IDBKey::createInvalid();
465         return p;
466
467     case IDBKeyArrayTypeByte: {
468         int64_t length;
469         p = decodeVarInt(p, limit, length);
470         if (!p || length < 0)
471             return 0;
472         IDBKey::KeyArray array;
473         while (length--) {
474             RefPtr<IDBKey> key;
475             p = decodeIDBKey(p, limit, key);
476             if (!p)
477                 return 0;
478             array.append(key);
479         }
480         foundKey = IDBKey::createArray(array);
481         return p;
482     }
483     case IDBKeyStringTypeByte: {
484         String s;
485         p = decodeStringWithLength(p, limit, s);
486         if (!p)
487             return 0;
488         foundKey = IDBKey::createString(s);
489         return p;
490     }
491     case IDBKeyDateTypeByte: {
492         double d;
493         p = decodeDouble(p, limit, &d);
494         if (!p)
495             return 0;
496         foundKey = IDBKey::createDate(d);
497         return p;
498     }
499     case IDBKeyNumberTypeByte: {
500         double d;
501         p = decodeDouble(p, limit, &d);
502         if (!p)
503             return 0;
504         foundKey = IDBKey::createNumber(d);
505         return p;
506     }
507     }
508
509     ASSERT_NOT_REACHED();
510     return 0;
511 }
512
513 const char* extractEncodedIDBKey(const char* start, const char* limit, Vector<char>* result = 0)
514 {
515     const char* p = start;
516     if (p >= limit)
517         return 0;
518
519     unsigned char type = *p++;
520
521     switch (type) {
522     case IDBKeyNullTypeByte:
523     case IDBKeyMinKeyTypeByte:
524         break;
525     case IDBKeyArrayTypeByte: {
526         int64_t length;
527         p = decodeVarInt(p, limit, length);
528         if (!p || length < 0)
529             return 0;
530         while (length--) {
531             p = extractEncodedIDBKey(p, limit);
532             if (!p)
533                 return 0;
534         }
535         break;
536     }
537     case IDBKeyStringTypeByte: {
538         int64_t length;
539         p = decodeVarInt(p, limit, length);
540         if (!p || length < 0 || p + length * 2 > limit)
541             return 0;
542         p += length * 2;
543         break;
544     }
545     case IDBKeyDateTypeByte:
546     case IDBKeyNumberTypeByte:
547         if (p + sizeof(double) > limit)
548             return 0;
549         p += sizeof(double);
550         break;
551     }
552
553     if (result) {
554         ASSERT(p);
555         ASSERT(p <= limit);
556         result->clear();
557         result->append(start, p - start);
558     }
559
560     return p;
561 }
562
563 static IDBKey::Type keyTypeByteToKeyType(unsigned char type)
564 {
565     switch (type) {
566     case IDBKeyNullTypeByte:
567         return IDBKey::InvalidType;
568     case IDBKeyArrayTypeByte:
569         return IDBKey::ArrayType;
570     case IDBKeyStringTypeByte:
571         return IDBKey::StringType;
572     case IDBKeyDateTypeByte:
573         return IDBKey::DateType;
574     case IDBKeyNumberTypeByte:
575         return IDBKey::NumberType;
576     case IDBKeyMinKeyTypeByte:
577         return IDBKey::MinType;
578     }
579
580     ASSERT_NOT_REACHED();
581     return IDBKey::InvalidType;
582 }
583
584 int compareEncodedIDBKeys(const char*& ptrA, const char* limitA, const char*& ptrB, const char* limitB, bool& ok)
585 {
586     ok = true;
587     ASSERT(&ptrA != &ptrB);
588     ASSERT(ptrA < limitA);
589     ASSERT(ptrB < limitB);
590     unsigned char typeA = *ptrA++;
591     unsigned char typeB = *ptrB++;
592
593     if (int x = IDBKey::compareTypes(keyTypeByteToKeyType(typeA), keyTypeByteToKeyType(typeB)))
594         return x;
595
596     switch (typeA) {
597     case IDBKeyNullTypeByte:
598     case IDBKeyMinKeyTypeByte:
599         // Null type or max type; no payload to compare.
600         return 0;
601     case IDBKeyArrayTypeByte: {
602         int64_t lengthA, lengthB;
603         ptrA = decodeVarInt(ptrA, limitA, lengthA);
604         ptrB = decodeVarInt(ptrB, limitB, lengthB);
605         if (!ptrA || !ptrB || lengthA < 0 || lengthB < 0) {
606             ok = false;
607             return 0;
608         }
609         for (int64_t i = 0; i < lengthA && i < lengthB; ++i) {
610             int result = compareEncodedIDBKeys(ptrA, limitA, ptrB, limitB, ok);
611             if (!ok || result)
612                 return result;
613         }
614         if (lengthA < lengthB)
615             return -1;
616         if (lengthA > lengthB)
617             return 1;
618         return 0;
619     }
620     case IDBKeyStringTypeByte:
621         return compareEncodedStringsWithLength(ptrA, limitA, ptrB, limitB, ok);
622     case IDBKeyDateTypeByte:
623     case IDBKeyNumberTypeByte: {
624         double d, e;
625         ptrA = decodeDouble(ptrA, limitA, &d);
626         ptrB = decodeDouble(ptrB, limitB, &e);
627         ASSERT(ptrA);
628         ASSERT(ptrB);
629         if (!ptrA || !ptrB) {
630             ok = false;
631             return 0;
632         }
633         if (d < e)
634             return -1;
635         if (d > e)
636             return 1;
637         return 0;
638     }
639     }
640
641     ASSERT_NOT_REACHED();
642     return 0;
643 }
644
645 int compareEncodedIDBKeys(const Vector<char>& keyA, const Vector<char>& keyB, bool& ok)
646 {
647     ASSERT(keyA.size() >= 1);
648     ASSERT(keyB.size() >= 1);
649
650     const char* ptrA = keyA.data();
651     const char* limitA = ptrA + keyA.size();
652     const char* ptrB = keyB.data();
653     const char* limitB = ptrB + keyB.size();
654
655     return compareEncodedIDBKeys(ptrA, limitA, ptrB, limitB, ok);
656 }
657
658 Vector<char> encodeIDBKeyPath(const IDBKeyPath& keyPath)
659 {
660     // May be typed, or may be a raw string. An invalid leading
661     // byte is used to identify typed coding. New records are
662     // always written as typed.
663     Vector<char, DefaultInlineBufferSize> ret;
664     ret.append(IDBKeyPathTypeCodedByte1);
665     ret.append(IDBKeyPathTypeCodedByte2);
666     ret.append(static_cast<char>(keyPath.type()));
667     switch (keyPath.type()) {
668     case IDBKeyPath::NullType:
669         break;
670     case IDBKeyPath::StringType:
671         ret.append(encodeStringWithLength(keyPath.string()));
672         break;
673     case IDBKeyPath::ArrayType: {
674         const Vector<String>& array = keyPath.array();
675         size_t count = array.size();
676         ret.append(encodeVarInt(count));
677         for (size_t i = 0; i < count; ++i)
678             ret.append(encodeStringWithLength(array[i]));
679         break;
680     }
681     }
682     return ret;
683 }
684
685 IDBKeyPath decodeIDBKeyPath(const char* p, const char* limit)
686 {
687     // May be typed, or may be a raw string. An invalid leading
688     // byte sequence is used to identify typed coding. New records are
689     // always written as typed.
690     if (p == limit || (limit - p >= 2 && (*p != IDBKeyPathTypeCodedByte1 || *(p + 1) != IDBKeyPathTypeCodedByte2)))
691         return IDBKeyPath(decodeString(p, limit));
692     p += 2;
693
694     ASSERT(p != limit);
695     IDBKeyPath::Type type = static_cast<IDBKeyPath::Type>(*p++);
696     switch (type) {
697     case IDBKeyPath::NullType:
698         ASSERT(p == limit);
699         return IDBKeyPath();
700     case IDBKeyPath::StringType: {
701         String string;
702         p = decodeStringWithLength(p, limit, string);
703         ASSERT(p == limit);
704         return IDBKeyPath(string);
705     }
706     case IDBKeyPath::ArrayType: {
707         Vector<String> array;
708         int64_t count;
709         p = decodeVarInt(p, limit, count);
710         ASSERT(p);
711         ASSERT(count >= 0);
712         while (count--) {
713             String string;
714             p = decodeStringWithLength(p, limit, string);
715             ASSERT(p);
716             array.append(string);
717         }
718         ASSERT(p == limit);
719         return IDBKeyPath(array);
720     }
721     }
722     ASSERT_NOT_REACHED();
723     return IDBKeyPath();
724 }
725
726 namespace {
727
728 template<typename KeyType>
729 int compare(const LevelDBSlice& a, const LevelDBSlice& b, bool ignoreDuplicates, bool& ok)
730 {
731     KeyType keyA;
732     KeyType keyB;
733
734     const char* ptrA = KeyType::decode(a.begin(), a.end(), &keyA);
735     ASSERT(ptrA);
736     if (!ptrA) {
737         ok = false;
738         return 0;
739     }
740     const char* ptrB = KeyType::decode(b.begin(), b.end(), &keyB);
741     ASSERT(ptrB);
742     if (!ptrB) {
743         ok = false;
744         return 0;
745     }
746
747     ok = true;
748     return keyA.compare(keyB);
749 }
750
751 template<>
752 int compare<ExistsEntryKey>(const LevelDBSlice& a, const LevelDBSlice& b, bool ignoreDuplicates, bool& ok)
753 {
754     KeyPrefix prefixA;
755     KeyPrefix prefixB;
756     const char* ptrA = KeyPrefix::decode(a.begin(), a.end(), &prefixA);
757     const char* ptrB = KeyPrefix::decode(b.begin(), b.end(), &prefixB);
758     ASSERT(ptrA);
759     ASSERT(ptrB);
760     ASSERT(prefixA.m_databaseId);
761     ASSERT(prefixA.m_objectStoreId);
762     ASSERT(prefixA.m_indexId == ExistsEntryKey::SpecialIndexNumber);
763     ASSERT(prefixB.m_databaseId);
764     ASSERT(prefixB.m_objectStoreId);
765     ASSERT(prefixB.m_indexId == ExistsEntryKey::SpecialIndexNumber);
766     ASSERT(ptrA != a.end());
767     ASSERT(ptrB != b.end());
768     // Prefixes are not compared - it is assumed this was already done.
769     ASSERT(!prefixA.compare(prefixB));
770
771     return compareEncodedIDBKeys(ptrA, a.end(), ptrB, b.end(), ok);
772 }
773
774 template<>
775 int compare<ObjectStoreDataKey>(const LevelDBSlice& a, const LevelDBSlice& b, bool ignoreDuplicates, bool& ok)
776 {
777     KeyPrefix prefixA;
778     KeyPrefix prefixB;
779     const char* ptrA = KeyPrefix::decode(a.begin(), a.end(), &prefixA);
780     const char* ptrB = KeyPrefix::decode(b.begin(), b.end(), &prefixB);
781     ASSERT(ptrA);
782     ASSERT(ptrB);
783     ASSERT(prefixA.m_databaseId);
784     ASSERT(prefixA.m_objectStoreId);
785     ASSERT(prefixA.m_indexId == ObjectStoreDataKey::SpecialIndexNumber);
786     ASSERT(prefixB.m_databaseId);
787     ASSERT(prefixB.m_objectStoreId);
788     ASSERT(prefixB.m_indexId == ObjectStoreDataKey::SpecialIndexNumber);
789     ASSERT(ptrA != a.end());
790     ASSERT(ptrB != b.end());
791     // Prefixes are not compared - it is assumed this was already done.
792     ASSERT(!prefixA.compare(prefixB));
793
794     return compareEncodedIDBKeys(ptrA, a.end(), ptrB, b.end(), ok);
795 }
796
797 template<>
798 int compare<IndexDataKey>(const LevelDBSlice& a, const LevelDBSlice& b, bool ignoreDuplicates, bool& ok)
799 {
800     KeyPrefix prefixA;
801     KeyPrefix prefixB;
802     const char* ptrA = KeyPrefix::decode(a.begin(), a.end(), &prefixA);
803     const char* ptrB = KeyPrefix::decode(b.begin(), b.end(), &prefixB);
804     ASSERT(ptrA);
805     ASSERT(ptrB);
806     ASSERT(prefixA.m_databaseId);
807     ASSERT(prefixA.m_objectStoreId);
808     ASSERT(prefixA.m_indexId >= MinimumIndexId);
809     ASSERT(prefixB.m_databaseId);
810     ASSERT(prefixB.m_objectStoreId);
811     ASSERT(prefixB.m_indexId >= MinimumIndexId);
812     ASSERT(ptrA != a.end());
813     ASSERT(ptrB != b.end());
814     // Prefixes are not compared - it is assumed this was already done.
815     ASSERT(!prefixA.compare(prefixB));
816
817     // index key
818     int result = compareEncodedIDBKeys(ptrA, a.end(), ptrB, b.end(), ok);
819     if (!ok || result)
820         return result;
821     if (ignoreDuplicates)
822         return 0;
823
824     // sequence number [optional]
825     int64_t sequenceNumberA = -1;
826     int64_t sequenceNumberB = -1;
827     if (ptrA != a.end())
828         ptrA = decodeVarInt(ptrA, a.end(), sequenceNumberA);
829     if (ptrB != b.end())
830         ptrB = decodeVarInt(ptrB, b.end(), sequenceNumberB);
831
832     // primary key [optional]
833     if (!ptrA || !ptrB)
834         return 0;
835     if (ptrA == a.end() && ptrB == b.end())
836         return 0;
837     if (ptrA == a.end())
838         return -1;
839     if (ptrB == b.end())
840         return 1;
841
842     result = compareEncodedIDBKeys(ptrA, a.end(), ptrB, b.end(), ok);
843     if (!ok || result)
844         return result;
845
846     return compareInts(sequenceNumberA, sequenceNumberB);
847 }
848
849 int compare(const LevelDBSlice& a, const LevelDBSlice& b, bool indexKeys, bool& ok)
850 {
851     const char* ptrA = a.begin();
852     const char* ptrB = b.begin();
853     const char* endA = a.end();
854     const char* endB = b.end();
855
856     KeyPrefix prefixA;
857     KeyPrefix prefixB;
858
859     ptrA = KeyPrefix::decode(ptrA, endA, &prefixA);
860     ptrB = KeyPrefix::decode(ptrB, endB, &prefixB);
861     ASSERT(ptrA);
862     ASSERT(ptrB);
863     if (!ptrA || !ptrB) {
864         ok = false;
865         return 0;
866     }
867
868     ok = true;
869     if (int x = prefixA.compare(prefixB))
870         return x;
871
872     if (prefixA.type() == KeyPrefix::GlobalMetaData) {
873         ASSERT(ptrA != endA);
874         ASSERT(ptrB != endB);
875
876         unsigned char typeByteA = *ptrA++;
877         unsigned char typeByteB = *ptrB++;
878
879         if (int x = typeByteA - typeByteB)
880             return x;
881         if (typeByteA < MaxSimpleGlobalMetaDataTypeByte)
882             return 0;
883
884         const bool ignoreDuplicates = false;
885         if (typeByteA == DatabaseFreeListTypeByte)
886             return compare<DatabaseFreeListKey>(a, b, ignoreDuplicates, ok);
887         if (typeByteA == DatabaseNameTypeByte)
888             return compare<DatabaseNameKey>(a, b, ignoreDuplicates, ok);
889     }
890
891     if (prefixA.type() == KeyPrefix::DatabaseMetaData) {
892         ASSERT(ptrA != endA);
893         ASSERT(ptrB != endB);
894
895         unsigned char typeByteA = *ptrA++;
896         unsigned char typeByteB = *ptrB++;
897
898         if (int x = typeByteA - typeByteB)
899             return x;
900         if (typeByteA < DatabaseMetaDataKey::MaxSimpleMetaDataType)
901             return 0;
902
903         const bool ignoreDuplicates = false;
904         if (typeByteA == ObjectStoreMetaDataTypeByte)
905             return compare<ObjectStoreMetaDataKey>(a, b, ignoreDuplicates, ok);
906         if (typeByteA == IndexMetaDataTypeByte)
907             return compare<IndexMetaDataKey>(a, b, ignoreDuplicates, ok);
908         if (typeByteA == ObjectStoreFreeListTypeByte)
909             return compare<ObjectStoreFreeListKey>(a, b, ignoreDuplicates, ok);
910         if (typeByteA == IndexFreeListTypeByte)
911             return compare<IndexFreeListKey>(a, b, ignoreDuplicates, ok);
912         if (typeByteA == ObjectStoreNamesTypeByte)
913             return compare<ObjectStoreNamesKey>(a, b, ignoreDuplicates, ok);
914         if (typeByteA == IndexNamesKeyTypeByte)
915             return compare<IndexNamesKey>(a, b, ignoreDuplicates, ok);
916     }
917
918     if (prefixA.type() == KeyPrefix::ObjectStoreData) {
919         if (ptrA == endA && ptrB == endB)
920             return 0;
921         if (ptrA == endA)
922             return -1;
923         if (ptrB == endB)
924             return 1; // FIXME: This case of non-existing user keys should not have to be handled this way.
925
926         const bool ignoreDuplicates = false;
927         return compare<ObjectStoreDataKey>(a, b, ignoreDuplicates, ok);
928     }
929     if (prefixA.type() == KeyPrefix::ExistsEntry) {
930         if (ptrA == endA && ptrB == endB)
931             return 0;
932         if (ptrA == endA)
933             return -1;
934         if (ptrB == endB)
935             return 1; // FIXME: This case of non-existing user keys should not have to be handled this way.
936
937         const bool ignoreDuplicates = false;
938         return compare<ExistsEntryKey>(a, b, ignoreDuplicates, ok);
939     }
940     if (prefixA.type() == KeyPrefix::IndexData) {
941         if (ptrA == endA && ptrB == endB)
942             return 0;
943         if (ptrA == endA)
944             return -1;
945         if (ptrB == endB)
946             return 1; // FIXME: This case of non-existing user keys should not have to be handled this way.
947
948         bool ignoreDuplicates = indexKeys;
949         return compare<IndexDataKey>(a, b, ignoreDuplicates, ok);
950     }
951
952     ASSERT_NOT_REACHED();
953     ok = false;
954     return 0;
955 }
956
957 }
958
959 int compare(const LevelDBSlice& a, const LevelDBSlice& b, bool indexKeys)
960 {
961     bool ok;
962     int result = compare(a, b, indexKeys, ok);
963     ASSERT(ok);
964     if (!ok)
965         return 0;
966     return result;
967 }
968
969 KeyPrefix::KeyPrefix()
970     : m_databaseId(InvalidType)
971     , m_objectStoreId(InvalidType)
972     , m_indexId(InvalidType)
973 {
974 }
975
976 KeyPrefix::KeyPrefix(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
977     : m_databaseId(databaseId)
978     , m_objectStoreId(objectStoreId)
979     , m_indexId(indexId)
980 {
981 }
982
983 const char* KeyPrefix::decode(const char* start, const char* limit, KeyPrefix* result)
984 {
985     if (start == limit)
986         return 0;
987
988     unsigned char firstByte = *start++;
989
990     int databaseIdBytes = ((firstByte >> 5) & 0x7) + 1;
991     int objectStoreIdBytes = ((firstByte >> 2) & 0x7) + 1;
992     int indexIdBytes = (firstByte & 0x3) + 1;
993
994     if (start + databaseIdBytes + objectStoreIdBytes + indexIdBytes > limit)
995         return 0;
996
997     result->m_databaseId = decodeInt(start, start + databaseIdBytes);
998     start += databaseIdBytes;
999     result->m_objectStoreId = decodeInt(start, start + objectStoreIdBytes);
1000     start += objectStoreIdBytes;
1001     result->m_indexId = decodeInt(start, start + indexIdBytes);
1002     start += indexIdBytes;
1003
1004     return start;
1005 }
1006
1007 Vector<char> KeyPrefix::encode() const
1008 {
1009     ASSERT(m_databaseId != InvalidId);
1010     ASSERT(m_objectStoreId != InvalidId);
1011     ASSERT(m_indexId != InvalidId);
1012
1013     Vector<char> databaseIdString = encodeInt(m_databaseId);
1014     Vector<char> objectStoreIdString = encodeInt(m_objectStoreId);
1015     Vector<char> indexIdString = encodeInt(m_indexId);
1016
1017     ASSERT(databaseIdString.size() <= 8);
1018     ASSERT(objectStoreIdString.size() <= 8);
1019     ASSERT(indexIdString.size() <= 4);
1020
1021
1022     unsigned char firstByte = (databaseIdString.size() - 1) << 5 | (objectStoreIdString.size() - 1) << 2 | (indexIdString.size() - 1);
1023     Vector<char, DefaultInlineBufferSize> ret;
1024     ret.append(firstByte);
1025     ret.append(databaseIdString);
1026     ret.append(objectStoreIdString);
1027     ret.append(indexIdString);
1028
1029     ASSERT(ret.size() <= DefaultInlineBufferSize);
1030     return ret;
1031 }
1032
1033 int KeyPrefix::compare(const KeyPrefix& other) const
1034 {
1035     ASSERT(m_databaseId != InvalidId);
1036     ASSERT(m_objectStoreId != InvalidId);
1037     ASSERT(m_indexId != InvalidId);
1038
1039     if (m_databaseId != other.m_databaseId)
1040         return compareInts(m_databaseId, other.m_databaseId);
1041     if (m_objectStoreId != other.m_objectStoreId)
1042         return compareInts(m_objectStoreId, other.m_objectStoreId);
1043     if (m_indexId != other.m_indexId)
1044         return compareInts(m_indexId, other.m_indexId);
1045     return 0;
1046 }
1047
1048 KeyPrefix::Type KeyPrefix::type() const
1049 {
1050     ASSERT(m_databaseId != InvalidId);
1051     ASSERT(m_objectStoreId != InvalidId);
1052     ASSERT(m_indexId != InvalidId);
1053
1054     if (!m_databaseId)
1055         return GlobalMetaData;
1056     if (!m_objectStoreId)
1057         return DatabaseMetaData;
1058     if (m_indexId == ObjectStoreDataIndexId)
1059         return ObjectStoreData;
1060     if (m_indexId == ExistsEntryIndexId)
1061         return ExistsEntry;
1062     if (m_indexId >= MinimumIndexId)
1063         return IndexData;
1064
1065     ASSERT_NOT_REACHED();
1066     return InvalidType;
1067 }
1068
1069 Vector<char> SchemaVersionKey::encode()
1070 {
1071     KeyPrefix prefix(0, 0, 0);
1072     Vector<char> ret = prefix.encode();
1073     ret.append(encodeByte(SchemaVersionTypeByte));
1074     return ret;
1075 }
1076
1077 Vector<char> MaxDatabaseIdKey::encode()
1078 {
1079     KeyPrefix prefix(0, 0, 0);
1080     Vector<char> ret = prefix.encode();
1081     ret.append(encodeByte(MaxDatabaseIdTypeByte));
1082     return ret;
1083 }
1084
1085 Vector<char> DataVersionKey::encode()
1086 {
1087     KeyPrefix prefix(0, 0, 0);
1088     Vector<char> ret = prefix.encode();
1089     ret.append(encodeByte(DataVersionTypeByte));
1090     return ret;
1091 }
1092
1093 DatabaseFreeListKey::DatabaseFreeListKey()
1094     : m_databaseId(-1)
1095 {
1096 }
1097
1098 const char* DatabaseFreeListKey::decode(const char* start, const char* limit, DatabaseFreeListKey* result)
1099 {
1100     KeyPrefix prefix;
1101     const char* p = KeyPrefix::decode(start, limit, &prefix);
1102     if (!p)
1103         return 0;
1104     ASSERT(!prefix.m_databaseId);
1105     ASSERT(!prefix.m_objectStoreId);
1106     ASSERT(!prefix.m_indexId);
1107     if (p == limit)
1108         return 0;
1109     unsigned char typeByte = 0;
1110     p = decodeByte(p, limit, typeByte);
1111     ASSERT_UNUSED(typeByte, typeByte == DatabaseFreeListTypeByte);
1112     if (p == limit)
1113         return 0;
1114     return decodeVarInt(p, limit, result->m_databaseId);
1115 }
1116
1117 Vector<char> DatabaseFreeListKey::encode(int64_t databaseId)
1118 {
1119     KeyPrefix prefix(0, 0, 0);
1120     Vector<char> ret = prefix.encode();
1121     ret.append(encodeByte(DatabaseFreeListTypeByte));
1122     ret.append(encodeVarInt(databaseId));
1123     return ret;
1124 }
1125
1126 Vector<char> DatabaseFreeListKey::encodeMaxKey()
1127 {
1128     return encode(INT64_MAX);
1129 }
1130
1131 int64_t DatabaseFreeListKey::databaseId() const
1132 {
1133     ASSERT(m_databaseId >= 0);
1134     return m_databaseId;
1135 }
1136
1137 int DatabaseFreeListKey::compare(const DatabaseFreeListKey& other) const
1138 {
1139     ASSERT(m_databaseId >= 0);
1140     return compareInts(m_databaseId, other.m_databaseId);
1141 }
1142
1143 const char* DatabaseNameKey::decode(const char* start, const char* limit, DatabaseNameKey* result)
1144 {
1145     KeyPrefix prefix;
1146     const char* p = KeyPrefix::decode(start, limit, &prefix);
1147     if (!p)
1148         return p;
1149     ASSERT(!prefix.m_databaseId);
1150     ASSERT(!prefix.m_objectStoreId);
1151     ASSERT(!prefix.m_indexId);
1152     if (p == limit)
1153         return 0;
1154     unsigned char typeByte = 0;
1155     p = decodeByte(p, limit, typeByte);
1156     ASSERT_UNUSED(typeByte, typeByte == DatabaseNameTypeByte);
1157     if (p == limit)
1158         return 0;
1159     p = decodeStringWithLength(p, limit, result->m_origin);
1160     if (!p)
1161         return 0;
1162     return decodeStringWithLength(p, limit, result->m_databaseName);
1163 }
1164
1165 Vector<char> DatabaseNameKey::encode(const String& origin, const String& databaseName)
1166 {
1167     KeyPrefix prefix(0, 0, 0);
1168     Vector<char> ret = prefix.encode();
1169     ret.append(encodeByte(DatabaseNameTypeByte));
1170     ret.append(encodeStringWithLength(origin));
1171     ret.append(encodeStringWithLength(databaseName));
1172     return ret;
1173 }
1174
1175 Vector<char> DatabaseNameKey::encodeMinKeyForOrigin(const String& origin)
1176 {
1177     return encode(origin, "");
1178 }
1179
1180 Vector<char> DatabaseNameKey::encodeStopKeyForOrigin(const String& origin)
1181 {
1182     // just after origin in collation order
1183     return encodeMinKeyForOrigin(origin + "\x01");
1184 }
1185
1186 int DatabaseNameKey::compare(const DatabaseNameKey& other)
1187 {
1188     if (int x = codePointCompare(m_origin, other.m_origin))
1189         return x;
1190     return codePointCompare(m_databaseName, other.m_databaseName);
1191 }
1192
1193 Vector<char> DatabaseMetaDataKey::encode(int64_t databaseId, MetaDataType metaDataType)
1194 {
1195     KeyPrefix prefix(databaseId, 0, 0);
1196     Vector<char> ret = prefix.encode();
1197     ret.append(encodeByte(metaDataType));
1198     return ret;
1199 }
1200
1201 ObjectStoreMetaDataKey::ObjectStoreMetaDataKey()
1202     : m_objectStoreId(-1)
1203     , m_metaDataType(-1)
1204 {
1205 }
1206
1207 const char* ObjectStoreMetaDataKey::decode(const char* start, const char* limit, ObjectStoreMetaDataKey* result)
1208 {
1209     KeyPrefix prefix;
1210     const char* p = KeyPrefix::decode(start, limit, &prefix);
1211     if (!p)
1212         return 0;
1213     ASSERT(prefix.m_databaseId);
1214     ASSERT(!prefix.m_objectStoreId);
1215     ASSERT(!prefix.m_indexId);
1216     if (p == limit)
1217         return 0;
1218     unsigned char typeByte = 0;
1219     p = decodeByte(p, limit, typeByte);
1220     ASSERT_UNUSED(typeByte, typeByte == ObjectStoreMetaDataTypeByte);
1221     if (p == limit)
1222         return 0;
1223     p = decodeVarInt(p, limit, result->m_objectStoreId);
1224     if (!p)
1225         return 0;
1226     ASSERT(result->m_objectStoreId);
1227     if (p == limit)
1228         return 0;
1229     return decodeByte(p, limit, result->m_metaDataType);
1230 }
1231
1232 Vector<char> ObjectStoreMetaDataKey::encode(int64_t databaseId, int64_t objectStoreId, unsigned char metaDataType)
1233 {
1234     KeyPrefix prefix(databaseId, 0, 0);
1235     Vector<char> ret = prefix.encode();
1236     ret.append(encodeByte(ObjectStoreMetaDataTypeByte));
1237     ret.append(encodeVarInt(objectStoreId));
1238     ret.append(encodeByte(metaDataType));
1239     return ret;
1240 }
1241
1242 Vector<char> ObjectStoreMetaDataKey::encodeMaxKey(int64_t databaseId)
1243 {
1244     return encode(databaseId, INT64_MAX, ObjectMetaDataTypeMaximum);
1245 }
1246
1247 Vector<char> ObjectStoreMetaDataKey::encodeMaxKey(int64_t databaseId, int64_t objectStoreId)
1248 {
1249     return encode(databaseId, objectStoreId, ObjectMetaDataTypeMaximum);
1250 }
1251
1252 int64_t ObjectStoreMetaDataKey::objectStoreId() const
1253 {
1254     ASSERT(m_objectStoreId >= 0);
1255     return m_objectStoreId;
1256 }
1257 unsigned char ObjectStoreMetaDataKey::metaDataType() const
1258 {
1259     return m_metaDataType;
1260 }
1261
1262 int ObjectStoreMetaDataKey::compare(const ObjectStoreMetaDataKey& other)
1263 {
1264     ASSERT(m_objectStoreId >= 0);
1265     if (int x = compareInts(m_objectStoreId, other.m_objectStoreId))
1266         return x;
1267     int64_t result = m_metaDataType - other.m_metaDataType;
1268     if (result < 0)
1269         return -1;
1270     return (result > 0) ? 1 : result;
1271 }
1272
1273 IndexMetaDataKey::IndexMetaDataKey()
1274     : m_objectStoreId(-1)
1275     , m_indexId(-1)
1276     , m_metaDataType(0)
1277 {
1278 }
1279
1280 const char* IndexMetaDataKey::decode(const char* start, const char* limit, IndexMetaDataKey* result)
1281 {
1282     KeyPrefix prefix;
1283     const char* p = KeyPrefix::decode(start, limit, &prefix);
1284     if (!p)
1285         return 0;
1286     ASSERT(prefix.m_databaseId);
1287     ASSERT(!prefix.m_objectStoreId);
1288     ASSERT(!prefix.m_indexId);
1289     if (p == limit)
1290         return 0;
1291     unsigned char typeByte = 0;
1292     p = decodeByte(p, limit, typeByte);
1293     ASSERT_UNUSED(typeByte, typeByte == IndexMetaDataTypeByte);
1294     if (p == limit)
1295         return 0;
1296     p = decodeVarInt(p, limit, result->m_objectStoreId);
1297     if (!p)
1298         return 0;
1299     p = decodeVarInt(p, limit, result->m_indexId);
1300     if (!p)
1301         return 0;
1302     if (p == limit)
1303         return 0;
1304     return decodeByte(p, limit, result->m_metaDataType);
1305 }
1306
1307 Vector<char> IndexMetaDataKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId, unsigned char metaDataType)
1308 {
1309     KeyPrefix prefix(databaseId, 0, 0);
1310     Vector<char> ret = prefix.encode();
1311     ret.append(encodeByte(IndexMetaDataTypeByte));
1312     ret.append(encodeVarInt(objectStoreId));
1313     ret.append(encodeVarInt(indexId));
1314     ret.append(encodeByte(metaDataType));
1315     return ret;
1316 }
1317
1318 Vector<char> IndexMetaDataKey::encodeMaxKey(int64_t databaseId, int64_t objectStoreId)
1319 {
1320     return encode(databaseId, objectStoreId, INT64_MAX, IndexMetaDataTypeMaximum);
1321 }
1322
1323 Vector<char> IndexMetaDataKey::encodeMaxKey(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
1324 {
1325     return encode(databaseId, objectStoreId, indexId, IndexMetaDataTypeMaximum);
1326 }
1327
1328 int IndexMetaDataKey::compare(const IndexMetaDataKey& other)
1329 {
1330     ASSERT(m_objectStoreId >= 0);
1331     ASSERT(m_indexId >= 0);
1332
1333     if (int x = compareInts(m_objectStoreId, other.m_objectStoreId))
1334         return x;
1335     if (int x = compareInts(m_indexId, other.m_indexId))
1336         return x;
1337     return m_metaDataType - other.m_metaDataType;
1338 }
1339
1340 int64_t IndexMetaDataKey::indexId() const
1341 {
1342     ASSERT(m_indexId >= 0);
1343     return m_indexId;
1344 }
1345
1346 ObjectStoreFreeListKey::ObjectStoreFreeListKey()
1347     : m_objectStoreId(-1)
1348 {
1349 }
1350
1351 const char* ObjectStoreFreeListKey::decode(const char* start, const char* limit, ObjectStoreFreeListKey* result)
1352 {
1353     KeyPrefix prefix;
1354     const char* p = KeyPrefix::decode(start, limit, &prefix);
1355     if (!p)
1356         return 0;
1357     ASSERT(prefix.m_databaseId);
1358     ASSERT(!prefix.m_objectStoreId);
1359     ASSERT(!prefix.m_indexId);
1360     if (p == limit)
1361         return 0;
1362     unsigned char typeByte = 0;
1363     p = decodeByte(p, limit, typeByte);
1364     ASSERT_UNUSED(typeByte, typeByte == ObjectStoreFreeListTypeByte);
1365     if (p == limit)
1366         return 0;
1367     return decodeVarInt(p, limit, result->m_objectStoreId);
1368 }
1369
1370 Vector<char> ObjectStoreFreeListKey::encode(int64_t databaseId, int64_t objectStoreId)
1371 {
1372     KeyPrefix prefix(databaseId, 0, 0);
1373     Vector<char> ret = prefix.encode();
1374     ret.append(encodeByte(ObjectStoreFreeListTypeByte));
1375     ret.append(encodeVarInt(objectStoreId));
1376     return ret;
1377 }
1378
1379 Vector<char> ObjectStoreFreeListKey::encodeMaxKey(int64_t databaseId)
1380 {
1381     return encode(databaseId, INT64_MAX);
1382 }
1383
1384 int64_t ObjectStoreFreeListKey::objectStoreId() const
1385 {
1386     ASSERT(m_objectStoreId >= 0);
1387     return m_objectStoreId;
1388 }
1389
1390 int ObjectStoreFreeListKey::compare(const ObjectStoreFreeListKey& other)
1391 {
1392     // FIXME: It may seem strange that we're not comparing database id's,
1393     // but that comparison will have been made earlier.
1394     // We should probably make this more clear, though...
1395     ASSERT(m_objectStoreId >= 0);
1396     return compareInts(m_objectStoreId, other.m_objectStoreId);
1397 }
1398
1399 IndexFreeListKey::IndexFreeListKey()
1400     : m_objectStoreId(-1)
1401     , m_indexId(-1)
1402 {
1403 }
1404
1405 const char* IndexFreeListKey::decode(const char* start, const char* limit, IndexFreeListKey* result)
1406 {
1407     KeyPrefix prefix;
1408     const char* p = KeyPrefix::decode(start, limit, &prefix);
1409     if (!p)
1410         return 0;
1411     ASSERT(prefix.m_databaseId);
1412     ASSERT(!prefix.m_objectStoreId);
1413     ASSERT(!prefix.m_indexId);
1414     if (p == limit)
1415         return 0;
1416     unsigned char typeByte = 0;
1417     p = decodeByte(p, limit, typeByte);
1418     ASSERT_UNUSED(typeByte, typeByte == IndexFreeListTypeByte);
1419     if (p == limit)
1420         return 0;
1421     p = decodeVarInt(p, limit, result->m_objectStoreId);
1422     if (!p)
1423         return 0;
1424     return decodeVarInt(p, limit, result->m_indexId);
1425 }
1426
1427 Vector<char> IndexFreeListKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
1428 {
1429     KeyPrefix prefix(databaseId, 0, 0);
1430     Vector<char> ret = prefix.encode();
1431     ret.append(encodeByte(IndexFreeListTypeByte));
1432     ret.append(encodeVarInt(objectStoreId));
1433     ret.append(encodeVarInt(indexId));
1434     return ret;
1435 }
1436
1437 Vector<char> IndexFreeListKey::encodeMaxKey(int64_t databaseId, int64_t objectStoreId)
1438 {
1439     return encode(databaseId, objectStoreId, INT64_MAX);
1440 }
1441
1442 int IndexFreeListKey::compare(const IndexFreeListKey& other)
1443 {
1444     ASSERT(m_objectStoreId >= 0);
1445     ASSERT(m_indexId >= 0);
1446     if (int x = compareInts(m_objectStoreId, other.m_objectStoreId))
1447         return x;
1448     return compareInts(m_indexId, other.m_indexId);
1449 }
1450
1451 int64_t IndexFreeListKey::objectStoreId() const
1452 {
1453     ASSERT(m_objectStoreId >= 0);
1454     return m_objectStoreId;
1455 }
1456
1457 int64_t IndexFreeListKey::indexId() const
1458 {
1459     ASSERT(m_indexId >= 0);
1460     return m_indexId;
1461 }
1462
1463 // FIXME: We never use this to look up object store ids, because a mapping
1464 // is kept in the IDBDatabaseBackendImpl. Can the mapping become unreliable?
1465 // Can we remove this?
1466 const char* ObjectStoreNamesKey::decode(const char* start, const char* limit, ObjectStoreNamesKey* result)
1467 {
1468     KeyPrefix prefix;
1469     const char* p = KeyPrefix::decode(start, limit, &prefix);
1470     if (!p)
1471         return 0;
1472     ASSERT(prefix.m_databaseId);
1473     ASSERT(!prefix.m_objectStoreId);
1474     ASSERT(!prefix.m_indexId);
1475     if (p == limit)
1476         return 0;
1477     unsigned char typeByte = 0;
1478     p = decodeByte(p, limit, typeByte);
1479     ASSERT_UNUSED(typeByte, typeByte == ObjectStoreNamesTypeByte);
1480     return decodeStringWithLength(p, limit, result->m_objectStoreName);
1481 }
1482
1483 Vector<char> ObjectStoreNamesKey::encode(int64_t databaseId, const String& objectStoreName)
1484 {
1485     KeyPrefix prefix(databaseId, 0, 0);
1486     Vector<char> ret = prefix.encode();
1487     ret.append(encodeByte(ObjectStoreNamesTypeByte));
1488     ret.append(encodeStringWithLength(objectStoreName));
1489     return ret;
1490 }
1491
1492 int ObjectStoreNamesKey::compare(const ObjectStoreNamesKey& other)
1493 {
1494     return codePointCompare(m_objectStoreName, other.m_objectStoreName);
1495 }
1496
1497 IndexNamesKey::IndexNamesKey()
1498     : m_objectStoreId(-1)
1499 {
1500 }
1501
1502 // FIXME: We never use this to look up index ids, because a mapping
1503 // is kept at a higher level.
1504 const char* IndexNamesKey::decode(const char* start, const char* limit, IndexNamesKey* result)
1505 {
1506     KeyPrefix prefix;
1507     const char* p = KeyPrefix::decode(start, limit, &prefix);
1508     if (!p)
1509         return 0;
1510     ASSERT(prefix.m_databaseId);
1511     ASSERT(!prefix.m_objectStoreId);
1512     ASSERT(!prefix.m_indexId);
1513     if (p == limit)
1514         return 0;
1515     unsigned char typeByte = 0;
1516     p = decodeByte(p, limit, typeByte);
1517     ASSERT_UNUSED(typeByte, typeByte == IndexNamesKeyTypeByte);
1518     if (p == limit)
1519         return 0;
1520     p = decodeVarInt(p, limit, result->m_objectStoreId);
1521     if (!p)
1522         return 0;
1523     return decodeStringWithLength(p, limit, result->m_indexName);
1524 }
1525
1526 Vector<char> IndexNamesKey::encode(int64_t databaseId, int64_t objectStoreId, const String& indexName)
1527 {
1528     KeyPrefix prefix(databaseId, 0, 0);
1529     Vector<char> ret = prefix.encode();
1530     ret.append(encodeByte(IndexNamesKeyTypeByte));
1531     ret.append(encodeVarInt(objectStoreId));
1532     ret.append(encodeStringWithLength(indexName));
1533     return ret;
1534 }
1535
1536 int IndexNamesKey::compare(const IndexNamesKey& other)
1537 {
1538     ASSERT(m_objectStoreId >= 0);
1539     if (int x = compareInts(m_objectStoreId, other.m_objectStoreId))
1540         return x;
1541     return codePointCompare(m_indexName, other.m_indexName);
1542 }
1543
1544 const char* ObjectStoreDataKey::decode(const char* start, const char* end, ObjectStoreDataKey* result)
1545 {
1546     KeyPrefix prefix;
1547     const char* p = KeyPrefix::decode(start, end, &prefix);
1548     if (!p)
1549         return 0;
1550     ASSERT(prefix.m_databaseId);
1551     ASSERT(prefix.m_objectStoreId);
1552     ASSERT(prefix.m_indexId == SpecialIndexNumber);
1553     if (p == end)
1554         return 0;
1555     return extractEncodedIDBKey(p, end, &result->m_encodedUserKey);
1556 }
1557
1558 Vector<char> ObjectStoreDataKey::encode(int64_t databaseId, int64_t objectStoreId, const Vector<char> encodedUserKey)
1559 {
1560     KeyPrefix prefix(databaseId, objectStoreId, SpecialIndexNumber);
1561     Vector<char> ret = prefix.encode();
1562     ret.append(encodedUserKey);
1563
1564     return ret;
1565 }
1566
1567 Vector<char> ObjectStoreDataKey::encode(int64_t databaseId, int64_t objectStoreId, const IDBKey& userKey)
1568 {
1569     return encode(databaseId, objectStoreId, encodeIDBKey(userKey));
1570 }
1571
1572 int ObjectStoreDataKey::compare(const ObjectStoreDataKey& other, bool& ok)
1573 {
1574     return compareEncodedIDBKeys(m_encodedUserKey, other.m_encodedUserKey, ok);
1575 }
1576
1577 PassRefPtr<IDBKey> ObjectStoreDataKey::userKey() const
1578 {
1579     RefPtr<IDBKey> key;
1580     decodeIDBKey(m_encodedUserKey.begin(), m_encodedUserKey.end(), key);
1581     return key;
1582 }
1583
1584 const int64_t ObjectStoreDataKey::SpecialIndexNumber = ObjectStoreDataIndexId;
1585
1586 const char* ExistsEntryKey::decode(const char* start, const char* end, ExistsEntryKey* result)
1587 {
1588     KeyPrefix prefix;
1589     const char* p = KeyPrefix::decode(start, end, &prefix);
1590     if (!p)
1591         return 0;
1592     ASSERT(prefix.m_databaseId);
1593     ASSERT(prefix.m_objectStoreId);
1594     ASSERT(prefix.m_indexId == SpecialIndexNumber);
1595     if (p == end)
1596         return 0;
1597     return extractEncodedIDBKey(p, end, &result->m_encodedUserKey);
1598 }
1599
1600 Vector<char> ExistsEntryKey::encode(int64_t databaseId, int64_t objectStoreId, const Vector<char>& encodedKey)
1601 {
1602     KeyPrefix prefix(databaseId, objectStoreId, SpecialIndexNumber);
1603     Vector<char> ret = prefix.encode();
1604     ret.append(encodedKey);
1605     return ret;
1606 }
1607
1608 Vector<char> ExistsEntryKey::encode(int64_t databaseId, int64_t objectStoreId, const IDBKey& userKey)
1609 {
1610     return encode(databaseId, objectStoreId, encodeIDBKey(userKey));
1611 }
1612
1613 int ExistsEntryKey::compare(const ExistsEntryKey& other, bool& ok)
1614 {
1615     return compareEncodedIDBKeys(m_encodedUserKey, other.m_encodedUserKey, ok);
1616 }
1617
1618 PassRefPtr<IDBKey> ExistsEntryKey::userKey() const
1619 {
1620     RefPtr<IDBKey> key;
1621     decodeIDBKey(m_encodedUserKey.begin(), m_encodedUserKey.end(), key);
1622     return key;
1623 }
1624
1625 const int64_t ExistsEntryKey::SpecialIndexNumber = ExistsEntryIndexId;
1626
1627 IndexDataKey::IndexDataKey()
1628     : m_databaseId(-1)
1629     , m_objectStoreId(-1)
1630     , m_indexId(-1)
1631     , m_sequenceNumber(-1)
1632 {
1633 }
1634
1635 const char* IndexDataKey::decode(const char* start, const char* limit, IndexDataKey* result)
1636 {
1637     KeyPrefix prefix;
1638     const char* p = KeyPrefix::decode(start, limit, &prefix);
1639     if (!p)
1640         return 0;
1641     ASSERT(prefix.m_databaseId);
1642     ASSERT(prefix.m_objectStoreId);
1643     ASSERT(prefix.m_indexId >= MinimumIndexId);
1644     result->m_databaseId = prefix.m_databaseId;
1645     result->m_objectStoreId = prefix.m_objectStoreId;
1646     result->m_indexId = prefix.m_indexId;
1647     result->m_sequenceNumber = -1;
1648     result->m_encodedPrimaryKey = minIDBKey();
1649
1650     p = extractEncodedIDBKey(p, limit, &result->m_encodedUserKey);
1651     if (!p)
1652         return 0;
1653
1654     // [optional] sequence number
1655     if (p == limit)
1656         return p;
1657     p =  decodeVarInt(p, limit, result->m_sequenceNumber);
1658     if (!p)
1659         return 0;
1660
1661     // [optional] primary key
1662     if (p == limit)
1663         return p;
1664     p = extractEncodedIDBKey(p, limit, &result->m_encodedPrimaryKey);
1665     if (!p)
1666         return 0;
1667
1668     return p;
1669 }
1670
1671 Vector<char> IndexDataKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const Vector<char>& encodedUserKey, const Vector<char>& encodedPrimaryKey, int64_t sequenceNumber)
1672 {
1673     KeyPrefix prefix(databaseId, objectStoreId, indexId);
1674     Vector<char> ret = prefix.encode();
1675     ret.append(encodedUserKey);
1676     ret.append(encodeVarInt(sequenceNumber));
1677     ret.append(encodedPrimaryKey);
1678     return ret;
1679 }
1680
1681 Vector<char> IndexDataKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& userKey)
1682 {
1683     return encode(databaseId, objectStoreId, indexId, encodeIDBKey(userKey), minIDBKey());
1684 }
1685
1686 Vector<char> IndexDataKey::encodeMinKey(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
1687 {
1688     return encode(databaseId, objectStoreId, indexId, minIDBKey(), minIDBKey());
1689 }
1690
1691 Vector<char> IndexDataKey::encodeMaxKey(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
1692 {
1693     return encode(databaseId, objectStoreId, indexId, maxIDBKey(), maxIDBKey(), INT64_MAX);
1694 }
1695
1696 int IndexDataKey::compare(const IndexDataKey& other, bool ignoreDuplicates, bool& ok)
1697 {
1698     ASSERT(m_databaseId >= 0);
1699     ASSERT(m_objectStoreId >= 0);
1700     ASSERT(m_indexId >= 0);
1701     int result = compareEncodedIDBKeys(m_encodedUserKey, other.m_encodedUserKey, ok);
1702     if (!ok || result)
1703         return result;
1704     if (ignoreDuplicates)
1705         return 0;
1706     result = compareEncodedIDBKeys(m_encodedPrimaryKey, other.m_encodedPrimaryKey, ok);
1707     if (!ok || result)
1708         return result;
1709     return compareInts(m_sequenceNumber, other.m_sequenceNumber);
1710 }
1711
1712 int64_t IndexDataKey::databaseId() const
1713 {
1714     ASSERT(m_databaseId >= 0);
1715     return m_databaseId;
1716 }
1717
1718 int64_t IndexDataKey::objectStoreId() const
1719 {
1720     ASSERT(m_objectStoreId >= 0);
1721     return m_objectStoreId;
1722 }
1723
1724 int64_t IndexDataKey::indexId() const
1725 {
1726     ASSERT(m_indexId >= 0);
1727     return m_indexId;
1728 }
1729
1730 PassRefPtr<IDBKey> IndexDataKey::userKey() const
1731 {
1732     RefPtr<IDBKey> key;
1733     decodeIDBKey(m_encodedUserKey.begin(), m_encodedUserKey.end(), key);
1734     return key;
1735 }
1736
1737 PassRefPtr<IDBKey> IndexDataKey::primaryKey() const
1738 {
1739     RefPtr<IDBKey> key;
1740     decodeIDBKey(m_encodedPrimaryKey.begin(), m_encodedPrimaryKey.end(), key);
1741     return key;
1742 }
1743
1744 } // namespace IDBLevelDBCoding
1745 } // namespace WebCore
1746
1747 #endif // USE(LEVELDB)
1748 #endif // ENABLE(INDEXED_DATABASE)