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