1// Copyright (c) 2013 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "content/browser/indexed_db/indexed_db_leveldb_coding.h"
6
7#include <iterator>
8#include <limits>
9
10#include "base/logging.h"
11#include "base/strings/string16.h"
12#include "base/strings/utf_string_conversions.h"
13#include "base/sys_byteorder.h"
14#include "content/common/indexed_db/indexed_db_key.h"
15#include "content/common/indexed_db/indexed_db_key_path.h"
16
17// LevelDB Coding Scheme
18// =====================
19//
20// LevelDB stores key/value pairs. Keys and values are strings of bytes,
21// normally of type std::string.
22//
23// The keys in the backing store are variable-length tuples with different
24// types of fields. Each key in the backing store starts with a ternary
25// prefix: (database id, object store id, index id). For each, 0 is reserved
26// for metadata. See KeyPrefix::Decode() for details of the prefix coding.
27//
28// The prefix makes sure that data for a specific database, object store, and
29// index are grouped together. The locality is important for performance:
30// common operations should only need a minimal number of seek operations. For
31// example, all the metadata for a database is grouped together so that
32// reading that metadata only requires one seek.
33//
34// Each key type has a class (in square brackets below) which knows how to
35// encode, decode, and compare that key type.
36//
37// Strings (origins, names, etc) are encoded as UTF-16BE.
38//
39//
40// Global metadata
41// ---------------
42// The prefix is <0, 0, 0>, followed by a metadata type byte:
43//
44// <0, 0, 0, 0> => backing store schema version [SchemaVersionKey]
45// <0, 0, 0, 1> => maximum allocated database [MaxDatabaseIdKey]
46// <0, 0, 0, 2> => SerializedScriptValue version [DataVersionKey]
47// <0, 0, 0, 3>
48//   => Blob journal
49//     The format of the journal is:
50//         {database_id (var int), blobKey (var int)}*.
51//     If the blobKey is kAllBlobsKey, the whole database should be deleted.
52//     [BlobJournalKey]
53// <0, 0, 0, 4> => Live blob journal; same format. [LiveBlobJournalKey]
54// <0, 0, 0, 100, database id>
55//   => Existence implies the database id is in the free list
56//      [DatabaseFreeListKey]
57// <0, 0, 0, 201, origin, database name> => Database id (int) [DatabaseNameKey]
58//
59//
60// Database metadata: [DatabaseMetaDataKey]
61// ----------------------------------------
62// The prefix is <database id, 0, 0> followed by a metadata type byte:
63//
64// <database id, 0, 0, 0> => origin name
65// <database id, 0, 0, 1> => database name
66// <database id, 0, 0, 2> => IDB string version data (obsolete)
67// <database id, 0, 0, 3> => maximum allocated object store id
68// <database id, 0, 0, 4> => IDB integer version (var int)
69// <database id, 0, 0, 5> => blob key generator current number
70//
71//
72// Object store metadata: [ObjectStoreMetaDataKey]
73// -----------------------------------------------
74// The prefix is <database id, 0, 0>, followed by a type byte (50), then the
75// object store id (var int), then a metadata type byte.
76//
77// <database id, 0, 0, 50, object store id, 0> => object store name
78// <database id, 0, 0, 50, object store id, 1> => key path
79// <database id, 0, 0, 50, object store id, 2> => auto increment flag
80// <database id, 0, 0, 50, object store id, 3> => is evictable
81// <database id, 0, 0, 50, object store id, 4> => last "version" number
82// <database id, 0, 0, 50, object store id, 5> => maximum allocated index id
83// <database id, 0, 0, 50, object store id, 6> => has key path flag (obsolete)
84// <database id, 0, 0, 50, object store id, 7> => key generator current number
85//
86// The key path was originally just a string (#1) or null (identified by flag,
87// #6). To support null, string, or array the coding is now identified by the
88// leading bytes in #1 - see EncodeIDBKeyPath.
89//
90// The "version" field is used to weed out stale index data. Whenever new
91// object store data is inserted, it gets a new "version" number, and new
92// index data is written with this number. When the index is used for
93// look-ups, entries are validated against the "exists" entries, and records
94// with old "version" numbers are deleted when they are encountered in
95// GetPrimaryKeyViaIndex, IndexCursorImpl::LoadCurrentRow and
96// IndexKeyCursorImpl::LoadCurrentRow.
97//
98//
99// Index metadata: [IndexMetaDataKey]
100// ----------------------------------
101// The prefix is <database id, 0, 0>, followed by a type byte (100), then the
102// object store id (var int), then the index id (var int), then a metadata
103// type byte.
104//
105// <database id, 0, 0, 100, object store id, index id, 0> => index name
106// <database id, 0, 0, 100, object store id, index id, 1> => unique flag
107// <database id, 0, 0, 100, object store id, index id, 2> => key path
108// <database id, 0, 0, 100, object store id, index id, 3> => multi-entry flag
109//
110//
111// Other object store and index metadata
112// -------------------------------------
113// The prefix is <database id, 0, 0> followed by a type byte. The object
114// store and index id are variable length integers, the names are variable
115// length strings.
116//
117// <database id, 0, 0, 150, object store id>
118//   => existence implies the object store id is in the free list
119//      [ObjectStoreFreeListKey]
120// <database id, 0, 0, 151, object store id, index id>
121//   => existence implies the index id is in the free list [IndexFreeListKey]
122// <database id, 0, 0, 200, object store name>
123//   => object store id [ObjectStoreNamesKey]
124// <database id, 0, 0, 201, object store id, index name>
125//   => index id [IndexNamesKey]
126//
127//
128// Object store data: [ObjectStoreDataKey]
129// ---------------------------------------
130// The prefix is followed by a type byte and the encoded IDB primary key. The
131// data has a "version" prefix followed by the serialized script value.
132//
133// <database id, object store id, 1, user key>
134//   => "version", serialized script value
135//
136//
137// "Exists" entry: [ExistsEntryKey]
138// --------------------------------
139// The prefix is followed by a type byte and the encoded IDB primary key.
140//
141// <database id, object store id, 2, user key> => "version"
142//
143//
144// Blob entry table: [BlobEntryKey]
145// --------------------------------
146//
147// The prefix is followed by a type byte and the encoded IDB primary key.
148//
149// <database id, object store id, 3, user key> => array of IndexedDBBlobInfo
150//
151//
152// Index data
153// ----------
154// The prefix is followed by a type byte, the encoded IDB index key, a
155// "sequence" number (obsolete; var int), and the encoded IDB primary key.
156//
157// <database id, object store id, index id, index key, sequence number,
158//   primary key> => "version", primary key [IndexDataKey]
159//
160// The sequence number is obsolete; it was used to allow two entries with the
161// same user (index) key in non-unique indexes prior to the inclusion of the
162// primary key in the data.
163//
164// Note: In order to be compatible with LevelDB's Bloom filter each bit of the
165// encoded key needs to used and "not ignored" by the comparator.
166
167using base::StringPiece;
168using blink::WebIDBKeyType;
169using blink::WebIDBKeyTypeArray;
170using blink::WebIDBKeyTypeBinary;
171using blink::WebIDBKeyTypeDate;
172using blink::WebIDBKeyTypeInvalid;
173using blink::WebIDBKeyTypeMin;
174using blink::WebIDBKeyTypeNull;
175using blink::WebIDBKeyTypeNumber;
176using blink::WebIDBKeyTypeString;
177using blink::WebIDBKeyPathType;
178using blink::WebIDBKeyPathTypeArray;
179using blink::WebIDBKeyPathTypeNull;
180using blink::WebIDBKeyPathTypeString;
181
182namespace content {
183
184// As most of the IndexedDBKeys and encoded values are short, we
185// initialize some std::vectors with a default inline buffer size to reduce
186// the memory re-allocations when the std::vectors are appended.
187static const size_t kDefaultInlineBufferSize = 32;
188
189static const unsigned char kIndexedDBKeyNullTypeByte = 0;
190static const unsigned char kIndexedDBKeyStringTypeByte = 1;
191static const unsigned char kIndexedDBKeyDateTypeByte = 2;
192static const unsigned char kIndexedDBKeyNumberTypeByte = 3;
193static const unsigned char kIndexedDBKeyArrayTypeByte = 4;
194static const unsigned char kIndexedDBKeyMinKeyTypeByte = 5;
195static const unsigned char kIndexedDBKeyBinaryTypeByte = 6;
196
197static const unsigned char kIndexedDBKeyPathTypeCodedByte1 = 0;
198static const unsigned char kIndexedDBKeyPathTypeCodedByte2 = 0;
199
200static const unsigned char kObjectStoreDataIndexId = 1;
201static const unsigned char kExistsEntryIndexId = 2;
202static const unsigned char kBlobEntryIndexId = 3;
203
204static const unsigned char kSchemaVersionTypeByte = 0;
205static const unsigned char kMaxDatabaseIdTypeByte = 1;
206static const unsigned char kDataVersionTypeByte = 2;
207static const unsigned char kBlobJournalTypeByte = 3;
208static const unsigned char kLiveBlobJournalTypeByte = 4;
209static const unsigned char kMaxSimpleGlobalMetaDataTypeByte =
210    5;  // Insert before this and increment.
211static const unsigned char kDatabaseFreeListTypeByte = 100;
212static const unsigned char kDatabaseNameTypeByte = 201;
213
214static const unsigned char kObjectStoreMetaDataTypeByte = 50;
215static const unsigned char kIndexMetaDataTypeByte = 100;
216static const unsigned char kObjectStoreFreeListTypeByte = 150;
217static const unsigned char kIndexFreeListTypeByte = 151;
218static const unsigned char kObjectStoreNamesTypeByte = 200;
219static const unsigned char kIndexNamesKeyTypeByte = 201;
220
221static const unsigned char kObjectMetaDataTypeMaximum = 255;
222static const unsigned char kIndexMetaDataTypeMaximum = 255;
223
224const unsigned char kMinimumIndexId = 30;
225
226inline void EncodeIntSafely(int64 nParam, int64 max, std::string* into) {
227  DCHECK_LE(nParam, max);
228  return EncodeInt(nParam, into);
229}
230
231std::string MaxIDBKey() {
232  std::string ret;
233  EncodeByte(kIndexedDBKeyNullTypeByte, &ret);
234  return ret;
235}
236
237std::string MinIDBKey() {
238  std::string ret;
239  EncodeByte(kIndexedDBKeyMinKeyTypeByte, &ret);
240  return ret;
241}
242
243void EncodeByte(unsigned char value, std::string* into) {
244  into->push_back(value);
245}
246
247void EncodeBool(bool value, std::string* into) {
248  into->push_back(value ? 1 : 0);
249}
250
251void EncodeInt(int64 value, std::string* into) {
252#ifndef NDEBUG
253  // Exercised by unit tests in debug only.
254  DCHECK_GE(value, 0);
255#endif
256  uint64 n = static_cast<uint64>(value);
257
258  do {
259    unsigned char c = n;
260    into->push_back(c);
261    n >>= 8;
262  } while (n);
263}
264
265void EncodeVarInt(int64 value, std::string* into) {
266#ifndef NDEBUG
267  // Exercised by unit tests in debug only.
268  DCHECK_GE(value, 0);
269#endif
270  uint64 n = static_cast<uint64>(value);
271
272  do {
273    unsigned char c = n & 0x7f;
274    n >>= 7;
275    if (n)
276      c |= 0x80;
277    into->push_back(c);
278  } while (n);
279}
280
281void EncodeString(const base::string16& value, std::string* into) {
282  if (value.empty())
283    return;
284  // Backing store is UTF-16BE, convert from host endianness.
285  size_t length = value.length();
286  size_t current = into->size();
287  into->resize(into->size() + length * sizeof(base::char16));
288
289  const base::char16* src = value.c_str();
290  base::char16* dst =
291      reinterpret_cast<base::char16*>(&*into->begin() + current);
292  for (unsigned i = 0; i < length; ++i)
293    *dst++ = htons(*src++);
294}
295
296void EncodeBinary(const std::string& value, std::string* into) {
297  EncodeVarInt(value.length(), into);
298  into->append(value.begin(), value.end());
299  DCHECK(into->size() >= value.size());
300}
301
302void EncodeStringWithLength(const base::string16& value, std::string* into) {
303  EncodeVarInt(value.length(), into);
304  EncodeString(value, into);
305}
306
307void EncodeDouble(double value, std::string* into) {
308  // This always has host endianness.
309  const char* p = reinterpret_cast<char*>(&value);
310  into->insert(into->end(), p, p + sizeof(value));
311}
312
313void EncodeIDBKey(const IndexedDBKey& value, std::string* into) {
314  size_t previous_size = into->size();
315  DCHECK(value.IsValid());
316  switch (value.type()) {
317    case WebIDBKeyTypeArray: {
318      EncodeByte(kIndexedDBKeyArrayTypeByte, into);
319      size_t length = value.array().size();
320      EncodeVarInt(length, into);
321      for (size_t i = 0; i < length; ++i)
322        EncodeIDBKey(value.array()[i], into);
323      DCHECK_GT(into->size(), previous_size);
324      return;
325    }
326    case WebIDBKeyTypeBinary:
327      EncodeByte(kIndexedDBKeyBinaryTypeByte, into);
328      EncodeBinary(value.binary(), into);
329      DCHECK_GT(into->size(), previous_size);
330      return;
331    case WebIDBKeyTypeString:
332      EncodeByte(kIndexedDBKeyStringTypeByte, into);
333      EncodeStringWithLength(value.string(), into);
334      DCHECK_GT(into->size(), previous_size);
335      return;
336    case WebIDBKeyTypeDate:
337      EncodeByte(kIndexedDBKeyDateTypeByte, into);
338      EncodeDouble(value.date(), into);
339      DCHECK_EQ(9u, static_cast<size_t>(into->size() - previous_size));
340      return;
341    case WebIDBKeyTypeNumber:
342      EncodeByte(kIndexedDBKeyNumberTypeByte, into);
343      EncodeDouble(value.number(), into);
344      DCHECK_EQ(9u, static_cast<size_t>(into->size() - previous_size));
345      return;
346    case WebIDBKeyTypeNull:
347    case WebIDBKeyTypeInvalid:
348    case WebIDBKeyTypeMin:
349    default:
350      NOTREACHED();
351      EncodeByte(kIndexedDBKeyNullTypeByte, into);
352      return;
353  }
354}
355
356void EncodeIDBKeyPath(const IndexedDBKeyPath& value, std::string* into) {
357  // May be typed, or may be a raw string. An invalid leading
358  // byte is used to identify typed coding. New records are
359  // always written as typed.
360  EncodeByte(kIndexedDBKeyPathTypeCodedByte1, into);
361  EncodeByte(kIndexedDBKeyPathTypeCodedByte2, into);
362  EncodeByte(static_cast<char>(value.type()), into);
363  switch (value.type()) {
364    case WebIDBKeyPathTypeNull:
365      break;
366    case WebIDBKeyPathTypeString: {
367      EncodeStringWithLength(value.string(), into);
368      break;
369    }
370    case WebIDBKeyPathTypeArray: {
371      const std::vector<base::string16>& array = value.array();
372      size_t count = array.size();
373      EncodeVarInt(count, into);
374      for (size_t i = 0; i < count; ++i) {
375        EncodeStringWithLength(array[i], into);
376      }
377      break;
378    }
379  }
380}
381
382void EncodeBlobJournal(const BlobJournalType& journal, std::string* into) {
383  BlobJournalType::const_iterator iter;
384  for (iter = journal.begin(); iter != journal.end(); ++iter) {
385    EncodeVarInt(iter->first, into);
386    EncodeVarInt(iter->second, into);
387  }
388}
389
390bool DecodeByte(StringPiece* slice, unsigned char* value) {
391  if (slice->empty())
392    return false;
393
394  *value = (*slice)[0];
395  slice->remove_prefix(1);
396  return true;
397}
398
399bool DecodeBool(StringPiece* slice, bool* value) {
400  if (slice->empty())
401    return false;
402
403  *value = !!(*slice)[0];
404  slice->remove_prefix(1);
405  return true;
406}
407
408bool DecodeInt(StringPiece* slice, int64* value) {
409  if (slice->empty())
410    return false;
411
412  StringPiece::const_iterator it = slice->begin();
413  int shift = 0;
414  int64 ret = 0;
415  while (it != slice->end()) {
416    unsigned char c = *it++;
417    ret |= static_cast<int64>(c) << shift;
418    shift += 8;
419  }
420  *value = ret;
421  slice->remove_prefix(it - slice->begin());
422  return true;
423}
424
425bool DecodeVarInt(StringPiece* slice, int64* value) {
426  if (slice->empty())
427    return false;
428
429  StringPiece::const_iterator it = slice->begin();
430  int shift = 0;
431  int64 ret = 0;
432  do {
433    if (it == slice->end())
434      return false;
435
436    unsigned char c = *it;
437    ret |= static_cast<int64>(c & 0x7f) << shift;
438    shift += 7;
439  } while (*it++ & 0x80);
440  *value = ret;
441  slice->remove_prefix(it - slice->begin());
442  return true;
443}
444
445bool DecodeString(StringPiece* slice, base::string16* value) {
446  if (slice->empty()) {
447    value->clear();
448    return true;
449  }
450
451  // Backing store is UTF-16BE, convert to host endianness.
452  DCHECK(!(slice->size() % sizeof(base::char16)));
453  size_t length = slice->size() / sizeof(base::char16);
454  base::string16 decoded;
455  decoded.reserve(length);
456  const base::char16* encoded =
457      reinterpret_cast<const base::char16*>(slice->begin());
458  for (unsigned i = 0; i < length; ++i)
459    decoded.push_back(ntohs(*encoded++));
460
461  *value = decoded;
462  slice->remove_prefix(length * sizeof(base::char16));
463  return true;
464}
465
466bool DecodeStringWithLength(StringPiece* slice, base::string16* value) {
467  if (slice->empty())
468    return false;
469
470  int64 length = 0;
471  if (!DecodeVarInt(slice, &length) || length < 0)
472    return false;
473  size_t bytes = length * sizeof(base::char16);
474  if (slice->size() < bytes)
475    return false;
476
477  StringPiece subpiece(slice->begin(), bytes);
478  slice->remove_prefix(bytes);
479  if (!DecodeString(&subpiece, value))
480    return false;
481
482  return true;
483}
484
485bool DecodeBinary(StringPiece* slice, std::string* value) {
486  if (slice->empty())
487    return false;
488
489  int64 length = 0;
490  if (!DecodeVarInt(slice, &length) || length < 0)
491    return false;
492  size_t size = length;
493  if (slice->size() < size)
494    return false;
495
496  value->assign(slice->begin(), size);
497  slice->remove_prefix(size);
498  return true;
499}
500
501bool DecodeIDBKey(StringPiece* slice, scoped_ptr<IndexedDBKey>* value) {
502  if (slice->empty())
503    return false;
504
505  unsigned char type = (*slice)[0];
506  slice->remove_prefix(1);
507
508  switch (type) {
509    case kIndexedDBKeyNullTypeByte:
510      *value = make_scoped_ptr(new IndexedDBKey());
511      return true;
512
513    case kIndexedDBKeyArrayTypeByte: {
514      int64 length = 0;
515      if (!DecodeVarInt(slice, &length) || length < 0)
516        return false;
517      IndexedDBKey::KeyArray array;
518      while (length--) {
519        scoped_ptr<IndexedDBKey> key;
520        if (!DecodeIDBKey(slice, &key))
521          return false;
522        array.push_back(*key);
523      }
524      *value = make_scoped_ptr(new IndexedDBKey(array));
525      return true;
526    }
527    case kIndexedDBKeyBinaryTypeByte: {
528      std::string binary;
529      if (!DecodeBinary(slice, &binary))
530        return false;
531      *value = make_scoped_ptr(new IndexedDBKey(binary));
532      return true;
533    }
534    case kIndexedDBKeyStringTypeByte: {
535      base::string16 s;
536      if (!DecodeStringWithLength(slice, &s))
537        return false;
538      *value = make_scoped_ptr(new IndexedDBKey(s));
539      return true;
540    }
541    case kIndexedDBKeyDateTypeByte: {
542      double d;
543      if (!DecodeDouble(slice, &d))
544        return false;
545      *value = make_scoped_ptr(new IndexedDBKey(d, WebIDBKeyTypeDate));
546      return true;
547    }
548    case kIndexedDBKeyNumberTypeByte: {
549      double d;
550      if (!DecodeDouble(slice, &d))
551        return false;
552      *value = make_scoped_ptr(new IndexedDBKey(d, WebIDBKeyTypeNumber));
553      return true;
554    }
555  }
556
557  NOTREACHED();
558  return false;
559}
560
561bool DecodeDouble(StringPiece* slice, double* value) {
562  if (slice->size() < sizeof(*value))
563    return false;
564
565  memcpy(value, slice->begin(), sizeof(*value));
566  slice->remove_prefix(sizeof(*value));
567  return true;
568}
569
570bool DecodeIDBKeyPath(StringPiece* slice, IndexedDBKeyPath* value) {
571  // May be typed, or may be a raw string. An invalid leading
572  // byte sequence is used to identify typed coding. New records are
573  // always written as typed.
574  if (slice->size() < 3 || (*slice)[0] != kIndexedDBKeyPathTypeCodedByte1 ||
575      (*slice)[1] != kIndexedDBKeyPathTypeCodedByte2) {
576    base::string16 s;
577    if (!DecodeString(slice, &s))
578      return false;
579    *value = IndexedDBKeyPath(s);
580    return true;
581  }
582
583  slice->remove_prefix(2);
584  DCHECK(!slice->empty());
585  WebIDBKeyPathType type = static_cast<WebIDBKeyPathType>((*slice)[0]);
586  slice->remove_prefix(1);
587
588  switch (type) {
589    case WebIDBKeyPathTypeNull:
590      DCHECK(slice->empty());
591      *value = IndexedDBKeyPath();
592      return true;
593    case WebIDBKeyPathTypeString: {
594      base::string16 string;
595      if (!DecodeStringWithLength(slice, &string))
596        return false;
597      DCHECK(slice->empty());
598      *value = IndexedDBKeyPath(string);
599      return true;
600    }
601    case WebIDBKeyPathTypeArray: {
602      std::vector<base::string16> array;
603      int64 count;
604      if (!DecodeVarInt(slice, &count))
605        return false;
606      DCHECK_GE(count, 0);
607      while (count--) {
608        base::string16 string;
609        if (!DecodeStringWithLength(slice, &string))
610          return false;
611        array.push_back(string);
612      }
613      DCHECK(slice->empty());
614      *value = IndexedDBKeyPath(array);
615      return true;
616    }
617  }
618  NOTREACHED();
619  return false;
620}
621
622bool DecodeBlobJournal(StringPiece* slice, BlobJournalType* journal) {
623  BlobJournalType output;
624  while (!slice->empty()) {
625    int64 database_id = -1;
626    int64 blob_key = -1;
627    if (!DecodeVarInt(slice, &database_id))
628      return false;
629    if (!KeyPrefix::IsValidDatabaseId(database_id))
630      return false;
631    if (!DecodeVarInt(slice, &blob_key))
632      return false;
633    if (!DatabaseMetaDataKey::IsValidBlobKey(blob_key) &&
634        (blob_key != DatabaseMetaDataKey::kAllBlobsKey)) {
635      return false;
636    }
637    output.push_back(std::make_pair(database_id, blob_key));
638  }
639  journal->swap(output);
640  return true;
641}
642
643bool ConsumeEncodedIDBKey(StringPiece* slice) {
644  unsigned char type = (*slice)[0];
645  slice->remove_prefix(1);
646
647  switch (type) {
648    case kIndexedDBKeyNullTypeByte:
649    case kIndexedDBKeyMinKeyTypeByte:
650      return true;
651    case kIndexedDBKeyArrayTypeByte: {
652      int64 length;
653      if (!DecodeVarInt(slice, &length))
654        return false;
655      while (length--) {
656        if (!ConsumeEncodedIDBKey(slice))
657          return false;
658      }
659      return true;
660    }
661    case kIndexedDBKeyBinaryTypeByte: {
662      int64 length = 0;
663      if (!DecodeVarInt(slice, &length) || length < 0)
664        return false;
665      if (slice->size() < static_cast<size_t>(length))
666        return false;
667      slice->remove_prefix(length);
668      return true;
669    }
670    case kIndexedDBKeyStringTypeByte: {
671      int64 length = 0;
672      if (!DecodeVarInt(slice, &length) || length < 0)
673        return false;
674      if (slice->size() < static_cast<size_t>(length) * sizeof(base::char16))
675        return false;
676      slice->remove_prefix(length * sizeof(base::char16));
677      return true;
678    }
679    case kIndexedDBKeyDateTypeByte:
680    case kIndexedDBKeyNumberTypeByte:
681      if (slice->size() < sizeof(double))
682        return false;
683      slice->remove_prefix(sizeof(double));
684      return true;
685  }
686  NOTREACHED();
687  return false;
688}
689
690bool ExtractEncodedIDBKey(StringPiece* slice, std::string* result) {
691  const char* start = slice->begin();
692  if (!ConsumeEncodedIDBKey(slice))
693    return false;
694
695  if (result)
696    result->assign(start, slice->begin());
697  return true;
698}
699
700static WebIDBKeyType KeyTypeByteToKeyType(unsigned char type) {
701  switch (type) {
702    case kIndexedDBKeyNullTypeByte:
703      return WebIDBKeyTypeInvalid;
704    case kIndexedDBKeyArrayTypeByte:
705      return WebIDBKeyTypeArray;
706    case kIndexedDBKeyBinaryTypeByte:
707      return WebIDBKeyTypeBinary;
708    case kIndexedDBKeyStringTypeByte:
709      return WebIDBKeyTypeString;
710    case kIndexedDBKeyDateTypeByte:
711      return WebIDBKeyTypeDate;
712    case kIndexedDBKeyNumberTypeByte:
713      return WebIDBKeyTypeNumber;
714    case kIndexedDBKeyMinKeyTypeByte:
715      return WebIDBKeyTypeMin;
716  }
717
718  NOTREACHED();
719  return WebIDBKeyTypeInvalid;
720}
721
722int CompareEncodedStringsWithLength(StringPiece* slice1,
723                                    StringPiece* slice2,
724                                    bool* ok) {
725  int64 len1, len2;
726  if (!DecodeVarInt(slice1, &len1) || !DecodeVarInt(slice2, &len2)) {
727    *ok = false;
728    return 0;
729  }
730  DCHECK_GE(len1, 0);
731  DCHECK_GE(len2, 0);
732  if (len1 < 0 || len2 < 0) {
733    *ok = false;
734    return 0;
735  }
736  DCHECK_GE(slice1->size(), len1 * sizeof(base::char16));
737  DCHECK_GE(slice2->size(), len2 * sizeof(base::char16));
738  if (slice1->size() < len1 * sizeof(base::char16) ||
739      slice2->size() < len2 * sizeof(base::char16)) {
740    *ok = false;
741    return 0;
742  }
743
744  // Extract the string data, and advance the passed slices.
745  StringPiece string1(slice1->begin(), len1 * sizeof(base::char16));
746  StringPiece string2(slice2->begin(), len2 * sizeof(base::char16));
747  slice1->remove_prefix(len1 * sizeof(base::char16));
748  slice2->remove_prefix(len2 * sizeof(base::char16));
749
750  *ok = true;
751  // Strings are UTF-16BE encoded, so a simple memcmp is sufficient.
752  return string1.compare(string2);
753}
754
755int CompareEncodedBinary(StringPiece* slice1,
756                         StringPiece* slice2,
757                         bool* ok) {
758  int64 len1, len2;
759  if (!DecodeVarInt(slice1, &len1) || !DecodeVarInt(slice2, &len2)) {
760    *ok = false;
761    return 0;
762  }
763  DCHECK_GE(len1, 0);
764  DCHECK_GE(len2, 0);
765  if (len1 < 0 || len2 < 0) {
766    *ok = false;
767    return 0;
768  }
769  size_t size1 = len1;
770  size_t size2 = len2;
771
772  DCHECK_GE(slice1->size(), size1);
773  DCHECK_GE(slice2->size(), size2);
774  if (slice1->size() < size1 || slice2->size() < size2) {
775    *ok = false;
776    return 0;
777  }
778
779  // Extract the binary data, and advance the passed slices.
780  StringPiece binary1(slice1->begin(), size1);
781  StringPiece binary2(slice2->begin(), size2);
782  slice1->remove_prefix(size1);
783  slice2->remove_prefix(size2);
784
785  *ok = true;
786  // This is the same as a memcmp()
787  return binary1.compare(binary2);
788}
789
790static int CompareInts(int64 a, int64 b) {
791#ifndef NDEBUG
792  // Exercised by unit tests in debug only.
793  DCHECK_GE(a, 0);
794  DCHECK_GE(b, 0);
795#endif
796  int64 diff = a - b;
797  if (diff < 0)
798    return -1;
799  if (diff > 0)
800    return 1;
801  return 0;
802}
803
804static inline int CompareSizes(size_t a, size_t b) {
805  if (a > b)
806    return 1;
807  if (b > a)
808    return -1;
809  return 0;
810}
811
812static int CompareTypes(WebIDBKeyType a, WebIDBKeyType b) { return b - a; }
813
814int CompareEncodedIDBKeys(StringPiece* slice_a,
815                          StringPiece* slice_b,
816                          bool* ok) {
817  DCHECK(!slice_a->empty());
818  DCHECK(!slice_b->empty());
819  *ok = true;
820  unsigned char type_a = (*slice_a)[0];
821  unsigned char type_b = (*slice_b)[0];
822  slice_a->remove_prefix(1);
823  slice_b->remove_prefix(1);
824
825  if (int x = CompareTypes(KeyTypeByteToKeyType(type_a),
826                           KeyTypeByteToKeyType(type_b)))
827    return x;
828
829  switch (type_a) {
830    case kIndexedDBKeyNullTypeByte:
831    case kIndexedDBKeyMinKeyTypeByte:
832      // Null type or max type; no payload to compare.
833      return 0;
834    case kIndexedDBKeyArrayTypeByte: {
835      int64 length_a, length_b;
836      if (!DecodeVarInt(slice_a, &length_a) ||
837          !DecodeVarInt(slice_b, &length_b)) {
838        *ok = false;
839        return 0;
840      }
841      for (int64 i = 0; i < length_a && i < length_b; ++i) {
842        int result = CompareEncodedIDBKeys(slice_a, slice_b, ok);
843        if (!*ok || result)
844          return result;
845      }
846      return length_a - length_b;
847    }
848    case kIndexedDBKeyBinaryTypeByte:
849      return CompareEncodedBinary(slice_a, slice_b, ok);
850    case kIndexedDBKeyStringTypeByte:
851      return CompareEncodedStringsWithLength(slice_a, slice_b, ok);
852    case kIndexedDBKeyDateTypeByte:
853    case kIndexedDBKeyNumberTypeByte: {
854      double d, e;
855      if (!DecodeDouble(slice_a, &d) || !DecodeDouble(slice_b, &e)) {
856        *ok = false;
857        return 0;
858      }
859      if (d < e)
860        return -1;
861      if (d > e)
862        return 1;
863      return 0;
864    }
865  }
866
867  NOTREACHED();
868  return 0;
869}
870
871namespace {
872
873template <typename KeyType>
874int Compare(const StringPiece& a,
875            const StringPiece& b,
876            bool only_compare_index_keys,
877            bool* ok) {
878  KeyType key_a;
879  KeyType key_b;
880
881  StringPiece slice_a(a);
882  if (!KeyType::Decode(&slice_a, &key_a)) {
883    *ok = false;
884    return 0;
885  }
886  StringPiece slice_b(b);
887  if (!KeyType::Decode(&slice_b, &key_b)) {
888    *ok = false;
889    return 0;
890  }
891
892  *ok = true;
893  return key_a.Compare(key_b);
894}
895
896template <typename KeyType>
897int CompareSuffix(StringPiece* a,
898                  StringPiece* b,
899                  bool only_compare_index_keys,
900                  bool* ok) {
901  NOTREACHED();
902  return 0;
903}
904
905template <>
906int CompareSuffix<ExistsEntryKey>(StringPiece* slice_a,
907                                  StringPiece* slice_b,
908                                  bool only_compare_index_keys,
909                                  bool* ok) {
910  DCHECK(!slice_a->empty());
911  DCHECK(!slice_b->empty());
912  return CompareEncodedIDBKeys(slice_a, slice_b, ok);
913}
914
915template <>
916int CompareSuffix<ObjectStoreDataKey>(StringPiece* slice_a,
917                                      StringPiece* slice_b,
918                                      bool only_compare_index_keys,
919                                      bool* ok) {
920  return CompareEncodedIDBKeys(slice_a, slice_b, ok);
921}
922
923template <>
924int CompareSuffix<BlobEntryKey>(StringPiece* slice_a,
925                                StringPiece* slice_b,
926                                bool only_compare_index_keys,
927                                bool* ok) {
928  return CompareEncodedIDBKeys(slice_a, slice_b, ok);
929}
930
931template <>
932int CompareSuffix<IndexDataKey>(StringPiece* slice_a,
933                                StringPiece* slice_b,
934                                bool only_compare_index_keys,
935                                bool* ok) {
936  // index key
937  int result = CompareEncodedIDBKeys(slice_a, slice_b, ok);
938  if (!*ok || result)
939    return result;
940  if (only_compare_index_keys)
941    return 0;
942
943  // sequence number [optional]
944  int64 sequence_number_a = -1;
945  int64 sequence_number_b = -1;
946  if (!slice_a->empty() && !DecodeVarInt(slice_a, &sequence_number_a))
947      return 0;
948  if (!slice_b->empty() && !DecodeVarInt(slice_b, &sequence_number_b))
949      return 0;
950
951  if (slice_a->empty() || slice_b->empty())
952    return CompareSizes(slice_a->size(), slice_b->size());
953
954  // primary key [optional]
955  result = CompareEncodedIDBKeys(slice_a, slice_b, ok);
956  if (!*ok || result)
957    return result;
958
959  return CompareInts(sequence_number_a, sequence_number_b);
960}
961
962int Compare(const StringPiece& a,
963            const StringPiece& b,
964            bool only_compare_index_keys,
965            bool* ok) {
966  StringPiece slice_a(a);
967  StringPiece slice_b(b);
968  KeyPrefix prefix_a;
969  KeyPrefix prefix_b;
970  bool ok_a = KeyPrefix::Decode(&slice_a, &prefix_a);
971  bool ok_b = KeyPrefix::Decode(&slice_b, &prefix_b);
972  DCHECK(ok_a);
973  DCHECK(ok_b);
974  if (!ok_a || !ok_b) {
975    *ok = false;
976    return 0;
977  }
978
979  *ok = true;
980  if (int x = prefix_a.Compare(prefix_b))
981    return x;
982
983  switch (prefix_a.type()) {
984    case KeyPrefix::GLOBAL_METADATA: {
985      DCHECK(!slice_a.empty());
986      DCHECK(!slice_b.empty());
987
988      unsigned char type_byte_a;
989      if (!DecodeByte(&slice_a, &type_byte_a)) {
990        *ok = false;
991        return 0;
992      }
993
994      unsigned char type_byte_b;
995      if (!DecodeByte(&slice_b, &type_byte_b)) {
996        *ok = false;
997        return 0;
998      }
999
1000      if (int x = type_byte_a - type_byte_b)
1001        return x;
1002      if (type_byte_a < kMaxSimpleGlobalMetaDataTypeByte)
1003        return 0;
1004
1005      // Compare<> is used (which re-decodes the prefix) rather than an
1006      // specialized CompareSuffix<> because metadata is relatively uncommon
1007      // in the database.
1008
1009      if (type_byte_a == kDatabaseFreeListTypeByte) {
1010        // TODO(jsbell): No need to pass only_compare_index_keys through here.
1011        return Compare<DatabaseFreeListKey>(a, b, only_compare_index_keys, ok);
1012      }
1013      if (type_byte_a == kDatabaseNameTypeByte) {
1014        return Compare<DatabaseNameKey>(
1015            a, b, /*only_compare_index_keys*/ false, ok);
1016      }
1017      break;
1018    }
1019
1020    case KeyPrefix::DATABASE_METADATA: {
1021      DCHECK(!slice_a.empty());
1022      DCHECK(!slice_b.empty());
1023
1024      unsigned char type_byte_a;
1025      if (!DecodeByte(&slice_a, &type_byte_a)) {
1026        *ok = false;
1027        return 0;
1028      }
1029
1030      unsigned char type_byte_b;
1031      if (!DecodeByte(&slice_b, &type_byte_b)) {
1032        *ok = false;
1033        return 0;
1034      }
1035
1036      if (int x = type_byte_a - type_byte_b)
1037        return x;
1038      if (type_byte_a < DatabaseMetaDataKey::MAX_SIMPLE_METADATA_TYPE)
1039        return 0;
1040
1041      // Compare<> is used (which re-decodes the prefix) rather than an
1042      // specialized CompareSuffix<> because metadata is relatively uncommon
1043      // in the database.
1044
1045      if (type_byte_a == kObjectStoreMetaDataTypeByte) {
1046        // TODO(jsbell): No need to pass only_compare_index_keys through here.
1047        return Compare<ObjectStoreMetaDataKey>(
1048            a, b, only_compare_index_keys, ok);
1049      }
1050      if (type_byte_a == kIndexMetaDataTypeByte) {
1051        return Compare<IndexMetaDataKey>(
1052            a, b, /*only_compare_index_keys*/ false, ok);
1053      }
1054      if (type_byte_a == kObjectStoreFreeListTypeByte) {
1055        return Compare<ObjectStoreFreeListKey>(
1056            a, b, only_compare_index_keys, ok);
1057      }
1058      if (type_byte_a == kIndexFreeListTypeByte) {
1059        return Compare<IndexFreeListKey>(
1060            a, b, /*only_compare_index_keys*/ false, ok);
1061      }
1062      if (type_byte_a == kObjectStoreNamesTypeByte) {
1063        // TODO(jsbell): No need to pass only_compare_index_keys through here.
1064        return Compare<ObjectStoreNamesKey>(
1065            a, b, only_compare_index_keys, ok);
1066      }
1067      if (type_byte_a == kIndexNamesKeyTypeByte) {
1068        return Compare<IndexNamesKey>(
1069            a, b, /*only_compare_index_keys*/ false, ok);
1070      }
1071      break;
1072    }
1073
1074    case KeyPrefix::OBJECT_STORE_DATA: {
1075      // Provide a stable ordering for invalid data.
1076      if (slice_a.empty() || slice_b.empty())
1077        return CompareSizes(slice_a.size(), slice_b.size());
1078
1079      return CompareSuffix<ObjectStoreDataKey>(
1080          &slice_a, &slice_b, /*only_compare_index_keys*/ false, ok);
1081    }
1082
1083    case KeyPrefix::EXISTS_ENTRY: {
1084      // Provide a stable ordering for invalid data.
1085      if (slice_a.empty() || slice_b.empty())
1086        return CompareSizes(slice_a.size(), slice_b.size());
1087
1088      return CompareSuffix<ExistsEntryKey>(
1089          &slice_a, &slice_b, /*only_compare_index_keys*/ false, ok);
1090    }
1091
1092    case KeyPrefix::BLOB_ENTRY: {
1093      // Provide a stable ordering for invalid data.
1094      if (slice_a.empty() || slice_b.empty())
1095        return CompareSizes(slice_a.size(), slice_b.size());
1096
1097      return CompareSuffix<BlobEntryKey>(
1098          &slice_a, &slice_b, /*only_compare_index_keys*/ false, ok);
1099    }
1100
1101    case KeyPrefix::INDEX_DATA: {
1102      // Provide a stable ordering for invalid data.
1103      if (slice_a.empty() || slice_b.empty())
1104        return CompareSizes(slice_a.size(), slice_b.size());
1105
1106      return CompareSuffix<IndexDataKey>(
1107          &slice_a, &slice_b, only_compare_index_keys, ok);
1108    }
1109
1110    case KeyPrefix::INVALID_TYPE:
1111      break;
1112  }
1113
1114  NOTREACHED();
1115  *ok = false;
1116  return 0;
1117}
1118
1119}  // namespace
1120
1121int Compare(const StringPiece& a,
1122            const StringPiece& b,
1123            bool only_compare_index_keys) {
1124  bool ok;
1125  int result = Compare(a, b, only_compare_index_keys, &ok);
1126  DCHECK(ok);
1127  if (!ok)
1128    return 0;
1129  return result;
1130}
1131
1132KeyPrefix::KeyPrefix()
1133    : database_id_(INVALID_TYPE),
1134      object_store_id_(INVALID_TYPE),
1135      index_id_(INVALID_TYPE) {}
1136
1137KeyPrefix::KeyPrefix(int64 database_id)
1138    : database_id_(database_id), object_store_id_(0), index_id_(0) {
1139  DCHECK(KeyPrefix::IsValidDatabaseId(database_id));
1140}
1141
1142KeyPrefix::KeyPrefix(int64 database_id, int64 object_store_id)
1143    : database_id_(database_id),
1144      object_store_id_(object_store_id),
1145      index_id_(0) {
1146  DCHECK(KeyPrefix::IsValidDatabaseId(database_id));
1147  DCHECK(KeyPrefix::IsValidObjectStoreId(object_store_id));
1148}
1149
1150KeyPrefix::KeyPrefix(int64 database_id, int64 object_store_id, int64 index_id)
1151    : database_id_(database_id),
1152      object_store_id_(object_store_id),
1153      index_id_(index_id) {
1154  DCHECK(KeyPrefix::IsValidDatabaseId(database_id));
1155  DCHECK(KeyPrefix::IsValidObjectStoreId(object_store_id));
1156  DCHECK(KeyPrefix::IsValidIndexId(index_id));
1157}
1158
1159KeyPrefix::KeyPrefix(enum Type type,
1160                     int64 database_id,
1161                     int64 object_store_id,
1162                     int64 index_id)
1163    : database_id_(database_id),
1164      object_store_id_(object_store_id),
1165      index_id_(index_id) {
1166  DCHECK_EQ(type, INVALID_TYPE);
1167  DCHECK(KeyPrefix::IsValidDatabaseId(database_id));
1168  DCHECK(KeyPrefix::IsValidObjectStoreId(object_store_id));
1169}
1170
1171KeyPrefix KeyPrefix::CreateWithSpecialIndex(int64 database_id,
1172                                            int64 object_store_id,
1173                                            int64 index_id) {
1174  DCHECK(KeyPrefix::IsValidDatabaseId(database_id));
1175  DCHECK(KeyPrefix::IsValidObjectStoreId(object_store_id));
1176  DCHECK(index_id);
1177  return KeyPrefix(INVALID_TYPE, database_id, object_store_id, index_id);
1178}
1179
1180bool KeyPrefix::IsValidDatabaseId(int64 database_id) {
1181  return (database_id > 0) && (database_id < KeyPrefix::kMaxDatabaseId);
1182}
1183
1184bool KeyPrefix::IsValidObjectStoreId(int64 object_store_id) {
1185  return (object_store_id > 0) &&
1186         (object_store_id < KeyPrefix::kMaxObjectStoreId);
1187}
1188
1189bool KeyPrefix::IsValidIndexId(int64 index_id) {
1190  return (index_id >= kMinimumIndexId) && (index_id < KeyPrefix::kMaxIndexId);
1191}
1192
1193bool KeyPrefix::Decode(StringPiece* slice, KeyPrefix* result) {
1194  unsigned char first_byte;
1195  if (!DecodeByte(slice, &first_byte))
1196    return false;
1197
1198  size_t database_id_bytes = ((first_byte >> 5) & 0x7) + 1;
1199  size_t object_store_id_bytes = ((first_byte >> 2) & 0x7) + 1;
1200  size_t index_id_bytes = (first_byte & 0x3) + 1;
1201
1202  if (database_id_bytes + object_store_id_bytes + index_id_bytes >
1203      slice->size())
1204    return false;
1205
1206  {
1207    StringPiece tmp(slice->begin(), database_id_bytes);
1208    if (!DecodeInt(&tmp, &result->database_id_))
1209      return false;
1210  }
1211  slice->remove_prefix(database_id_bytes);
1212  {
1213    StringPiece tmp(slice->begin(), object_store_id_bytes);
1214    if (!DecodeInt(&tmp, &result->object_store_id_))
1215      return false;
1216  }
1217  slice->remove_prefix(object_store_id_bytes);
1218  {
1219    StringPiece tmp(slice->begin(), index_id_bytes);
1220    if (!DecodeInt(&tmp, &result->index_id_))
1221      return false;
1222  }
1223  slice->remove_prefix(index_id_bytes);
1224  return true;
1225}
1226
1227std::string KeyPrefix::EncodeEmpty() {
1228  const std::string result(4, 0);
1229  DCHECK(EncodeInternal(0, 0, 0) == std::string(4, 0));
1230  return result;
1231}
1232
1233std::string KeyPrefix::Encode() const {
1234  DCHECK(database_id_ != kInvalidId);
1235  DCHECK(object_store_id_ != kInvalidId);
1236  DCHECK(index_id_ != kInvalidId);
1237  return EncodeInternal(database_id_, object_store_id_, index_id_);
1238}
1239
1240std::string KeyPrefix::EncodeInternal(int64 database_id,
1241                                      int64 object_store_id,
1242                                      int64 index_id) {
1243  std::string database_id_string;
1244  std::string object_store_id_string;
1245  std::string index_id_string;
1246
1247  EncodeIntSafely(database_id, kMaxDatabaseId, &database_id_string);
1248  EncodeIntSafely(object_store_id, kMaxObjectStoreId, &object_store_id_string);
1249  EncodeIntSafely(index_id, kMaxIndexId, &index_id_string);
1250
1251  DCHECK(database_id_string.size() <= kMaxDatabaseIdSizeBytes);
1252  DCHECK(object_store_id_string.size() <= kMaxObjectStoreIdSizeBytes);
1253  DCHECK(index_id_string.size() <= kMaxIndexIdSizeBytes);
1254
1255  unsigned char first_byte =
1256      (database_id_string.size() - 1) << (kMaxObjectStoreIdSizeBits +
1257                                          kMaxIndexIdSizeBits) |
1258      (object_store_id_string.size() - 1) << kMaxIndexIdSizeBits |
1259      (index_id_string.size() - 1);
1260  COMPILE_ASSERT(kMaxDatabaseIdSizeBits + kMaxObjectStoreIdSizeBits +
1261                         kMaxIndexIdSizeBits ==
1262                     sizeof(first_byte) * 8,
1263                 CANT_ENCODE_IDS);
1264  std::string ret;
1265  ret.reserve(kDefaultInlineBufferSize);
1266  ret.push_back(first_byte);
1267  ret.append(database_id_string);
1268  ret.append(object_store_id_string);
1269  ret.append(index_id_string);
1270
1271  DCHECK_LE(ret.size(), kDefaultInlineBufferSize);
1272  return ret;
1273}
1274
1275int KeyPrefix::Compare(const KeyPrefix& other) const {
1276  DCHECK(database_id_ != kInvalidId);
1277  DCHECK(object_store_id_ != kInvalidId);
1278  DCHECK(index_id_ != kInvalidId);
1279
1280  if (database_id_ != other.database_id_)
1281    return CompareInts(database_id_, other.database_id_);
1282  if (object_store_id_ != other.object_store_id_)
1283    return CompareInts(object_store_id_, other.object_store_id_);
1284  if (index_id_ != other.index_id_)
1285    return CompareInts(index_id_, other.index_id_);
1286  return 0;
1287}
1288
1289KeyPrefix::Type KeyPrefix::type() const {
1290  DCHECK(database_id_ != kInvalidId);
1291  DCHECK(object_store_id_ != kInvalidId);
1292  DCHECK(index_id_ != kInvalidId);
1293
1294  if (!database_id_)
1295    return GLOBAL_METADATA;
1296  if (!object_store_id_)
1297    return DATABASE_METADATA;
1298  if (index_id_ == kObjectStoreDataIndexId)
1299    return OBJECT_STORE_DATA;
1300  if (index_id_ == kExistsEntryIndexId)
1301    return EXISTS_ENTRY;
1302  if (index_id_ == kBlobEntryIndexId)
1303    return BLOB_ENTRY;
1304  if (index_id_ >= kMinimumIndexId)
1305    return INDEX_DATA;
1306
1307  NOTREACHED();
1308  return INVALID_TYPE;
1309}
1310
1311std::string SchemaVersionKey::Encode() {
1312  std::string ret = KeyPrefix::EncodeEmpty();
1313  ret.push_back(kSchemaVersionTypeByte);
1314  return ret;
1315}
1316
1317std::string MaxDatabaseIdKey::Encode() {
1318  std::string ret = KeyPrefix::EncodeEmpty();
1319  ret.push_back(kMaxDatabaseIdTypeByte);
1320  return ret;
1321}
1322
1323std::string DataVersionKey::Encode() {
1324  std::string ret = KeyPrefix::EncodeEmpty();
1325  ret.push_back(kDataVersionTypeByte);
1326  return ret;
1327}
1328
1329std::string BlobJournalKey::Encode() {
1330  std::string ret = KeyPrefix::EncodeEmpty();
1331  ret.push_back(kBlobJournalTypeByte);
1332  return ret;
1333}
1334
1335std::string LiveBlobJournalKey::Encode() {
1336  std::string ret = KeyPrefix::EncodeEmpty();
1337  ret.push_back(kLiveBlobJournalTypeByte);
1338  return ret;
1339}
1340
1341DatabaseFreeListKey::DatabaseFreeListKey() : database_id_(-1) {}
1342
1343bool DatabaseFreeListKey::Decode(StringPiece* slice,
1344                                 DatabaseFreeListKey* result) {
1345  KeyPrefix prefix;
1346  if (!KeyPrefix::Decode(slice, &prefix))
1347    return false;
1348  DCHECK(!prefix.database_id_);
1349  DCHECK(!prefix.object_store_id_);
1350  DCHECK(!prefix.index_id_);
1351  unsigned char type_byte = 0;
1352  if (!DecodeByte(slice, &type_byte))
1353    return false;
1354  DCHECK_EQ(type_byte, kDatabaseFreeListTypeByte);
1355  if (!DecodeVarInt(slice, &result->database_id_))
1356    return false;
1357  return true;
1358}
1359
1360std::string DatabaseFreeListKey::Encode(int64 database_id) {
1361  std::string ret = KeyPrefix::EncodeEmpty();
1362  ret.push_back(kDatabaseFreeListTypeByte);
1363  EncodeVarInt(database_id, &ret);
1364  return ret;
1365}
1366
1367std::string DatabaseFreeListKey::EncodeMaxKey() {
1368  return Encode(std::numeric_limits<int64>::max());
1369}
1370
1371int64 DatabaseFreeListKey::DatabaseId() const {
1372  DCHECK_GE(database_id_, 0);
1373  return database_id_;
1374}
1375
1376int DatabaseFreeListKey::Compare(const DatabaseFreeListKey& other) const {
1377  DCHECK_GE(database_id_, 0);
1378  return CompareInts(database_id_, other.database_id_);
1379}
1380
1381bool DatabaseNameKey::Decode(StringPiece* slice, DatabaseNameKey* result) {
1382  KeyPrefix prefix;
1383  if (!KeyPrefix::Decode(slice, &prefix))
1384    return false;
1385  DCHECK(!prefix.database_id_);
1386  DCHECK(!prefix.object_store_id_);
1387  DCHECK(!prefix.index_id_);
1388  unsigned char type_byte = 0;
1389  if (!DecodeByte(slice, &type_byte))
1390    return false;
1391  DCHECK_EQ(type_byte, kDatabaseNameTypeByte);
1392  if (!DecodeStringWithLength(slice, &result->origin_))
1393    return false;
1394  if (!DecodeStringWithLength(slice, &result->database_name_))
1395    return false;
1396  return true;
1397}
1398
1399std::string DatabaseNameKey::Encode(const std::string& origin_identifier,
1400                                    const base::string16& database_name) {
1401  std::string ret = KeyPrefix::EncodeEmpty();
1402  ret.push_back(kDatabaseNameTypeByte);
1403  EncodeStringWithLength(base::ASCIIToUTF16(origin_identifier), &ret);
1404  EncodeStringWithLength(database_name, &ret);
1405  return ret;
1406}
1407
1408std::string DatabaseNameKey::EncodeMinKeyForOrigin(
1409    const std::string& origin_identifier) {
1410  return Encode(origin_identifier, base::string16());
1411}
1412
1413std::string DatabaseNameKey::EncodeStopKeyForOrigin(
1414    const std::string& origin_identifier) {
1415  // just after origin in collation order
1416  return EncodeMinKeyForOrigin(origin_identifier + '\x01');
1417}
1418
1419int DatabaseNameKey::Compare(const DatabaseNameKey& other) {
1420  if (int x = origin_.compare(other.origin_))
1421    return x;
1422  return database_name_.compare(other.database_name_);
1423}
1424
1425bool DatabaseMetaDataKey::IsValidBlobKey(int64 blob_key) {
1426  return blob_key >= kBlobKeyGeneratorInitialNumber;
1427}
1428
1429const int64 DatabaseMetaDataKey::kAllBlobsKey = 1;
1430const int64 DatabaseMetaDataKey::kBlobKeyGeneratorInitialNumber = 2;
1431const int64 DatabaseMetaDataKey::kInvalidBlobKey = -1;
1432
1433std::string DatabaseMetaDataKey::Encode(int64 database_id,
1434                                        MetaDataType meta_data_type) {
1435  KeyPrefix prefix(database_id);
1436  std::string ret = prefix.Encode();
1437  ret.push_back(meta_data_type);
1438  return ret;
1439}
1440
1441ObjectStoreMetaDataKey::ObjectStoreMetaDataKey()
1442    : object_store_id_(-1), meta_data_type_(0xFF) {}
1443
1444bool ObjectStoreMetaDataKey::Decode(StringPiece* slice,
1445                                    ObjectStoreMetaDataKey* result) {
1446  KeyPrefix prefix;
1447  if (!KeyPrefix::Decode(slice, &prefix))
1448    return false;
1449  DCHECK(prefix.database_id_);
1450  DCHECK(!prefix.object_store_id_);
1451  DCHECK(!prefix.index_id_);
1452  unsigned char type_byte = 0;
1453  if (!DecodeByte(slice, &type_byte))
1454    return false;
1455  DCHECK_EQ(type_byte, kObjectStoreMetaDataTypeByte);
1456  if (!DecodeVarInt(slice, &result->object_store_id_))
1457    return false;
1458  DCHECK(result->object_store_id_);
1459  if (!DecodeByte(slice, &result->meta_data_type_))
1460    return false;
1461  return true;
1462}
1463
1464std::string ObjectStoreMetaDataKey::Encode(int64 database_id,
1465                                           int64 object_store_id,
1466                                           unsigned char meta_data_type) {
1467  KeyPrefix prefix(database_id);
1468  std::string ret = prefix.Encode();
1469  ret.push_back(kObjectStoreMetaDataTypeByte);
1470  EncodeVarInt(object_store_id, &ret);
1471  ret.push_back(meta_data_type);
1472  return ret;
1473}
1474
1475std::string ObjectStoreMetaDataKey::EncodeMaxKey(int64 database_id) {
1476  return Encode(database_id,
1477                std::numeric_limits<int64>::max(),
1478                kObjectMetaDataTypeMaximum);
1479}
1480
1481std::string ObjectStoreMetaDataKey::EncodeMaxKey(int64 database_id,
1482                                                 int64 object_store_id) {
1483  return Encode(database_id, object_store_id, kObjectMetaDataTypeMaximum);
1484}
1485
1486int64 ObjectStoreMetaDataKey::ObjectStoreId() const {
1487  DCHECK_GE(object_store_id_, 0);
1488  return object_store_id_;
1489}
1490unsigned char ObjectStoreMetaDataKey::MetaDataType() const {
1491  return meta_data_type_;
1492}
1493
1494int ObjectStoreMetaDataKey::Compare(const ObjectStoreMetaDataKey& other) {
1495  DCHECK_GE(object_store_id_, 0);
1496  if (int x = CompareInts(object_store_id_, other.object_store_id_))
1497    return x;
1498  return meta_data_type_ - other.meta_data_type_;
1499}
1500
1501IndexMetaDataKey::IndexMetaDataKey()
1502    : object_store_id_(-1), index_id_(-1), meta_data_type_(0) {}
1503
1504bool IndexMetaDataKey::Decode(StringPiece* slice, IndexMetaDataKey* result) {
1505  KeyPrefix prefix;
1506  if (!KeyPrefix::Decode(slice, &prefix))
1507    return false;
1508  DCHECK(prefix.database_id_);
1509  DCHECK(!prefix.object_store_id_);
1510  DCHECK(!prefix.index_id_);
1511  unsigned char type_byte = 0;
1512  if (!DecodeByte(slice, &type_byte))
1513    return false;
1514  DCHECK_EQ(type_byte, kIndexMetaDataTypeByte);
1515  if (!DecodeVarInt(slice, &result->object_store_id_))
1516    return false;
1517  if (!DecodeVarInt(slice, &result->index_id_))
1518    return false;
1519  if (!DecodeByte(slice, &result->meta_data_type_))
1520    return false;
1521  return true;
1522}
1523
1524std::string IndexMetaDataKey::Encode(int64 database_id,
1525                                     int64 object_store_id,
1526                                     int64 index_id,
1527                                     unsigned char meta_data_type) {
1528  KeyPrefix prefix(database_id);
1529  std::string ret = prefix.Encode();
1530  ret.push_back(kIndexMetaDataTypeByte);
1531  EncodeVarInt(object_store_id, &ret);
1532  EncodeVarInt(index_id, &ret);
1533  EncodeByte(meta_data_type, &ret);
1534  return ret;
1535}
1536
1537std::string IndexMetaDataKey::EncodeMaxKey(int64 database_id,
1538                                           int64 object_store_id) {
1539  return Encode(database_id,
1540                object_store_id,
1541                std::numeric_limits<int64>::max(),
1542                kIndexMetaDataTypeMaximum);
1543}
1544
1545std::string IndexMetaDataKey::EncodeMaxKey(int64 database_id,
1546                                           int64 object_store_id,
1547                                           int64 index_id) {
1548  return Encode(
1549      database_id, object_store_id, index_id, kIndexMetaDataTypeMaximum);
1550}
1551
1552int IndexMetaDataKey::Compare(const IndexMetaDataKey& other) {
1553  DCHECK_GE(object_store_id_, 0);
1554  DCHECK_GE(index_id_, 0);
1555
1556  if (int x = CompareInts(object_store_id_, other.object_store_id_))
1557    return x;
1558  if (int x = CompareInts(index_id_, other.index_id_))
1559    return x;
1560  return meta_data_type_ - other.meta_data_type_;
1561}
1562
1563int64 IndexMetaDataKey::IndexId() const {
1564  DCHECK_GE(index_id_, 0);
1565  return index_id_;
1566}
1567
1568ObjectStoreFreeListKey::ObjectStoreFreeListKey() : object_store_id_(-1) {}
1569
1570bool ObjectStoreFreeListKey::Decode(StringPiece* slice,
1571                                    ObjectStoreFreeListKey* result) {
1572  KeyPrefix prefix;
1573  if (!KeyPrefix::Decode(slice, &prefix))
1574    return false;
1575  DCHECK(prefix.database_id_);
1576  DCHECK(!prefix.object_store_id_);
1577  DCHECK(!prefix.index_id_);
1578  unsigned char type_byte = 0;
1579  if (!DecodeByte(slice, &type_byte))
1580    return false;
1581  DCHECK_EQ(type_byte, kObjectStoreFreeListTypeByte);
1582  if (!DecodeVarInt(slice, &result->object_store_id_))
1583    return false;
1584  return true;
1585}
1586
1587std::string ObjectStoreFreeListKey::Encode(int64 database_id,
1588                                           int64 object_store_id) {
1589  KeyPrefix prefix(database_id);
1590  std::string ret = prefix.Encode();
1591  ret.push_back(kObjectStoreFreeListTypeByte);
1592  EncodeVarInt(object_store_id, &ret);
1593  return ret;
1594}
1595
1596std::string ObjectStoreFreeListKey::EncodeMaxKey(int64 database_id) {
1597  return Encode(database_id, std::numeric_limits<int64>::max());
1598}
1599
1600int64 ObjectStoreFreeListKey::ObjectStoreId() const {
1601  DCHECK_GE(object_store_id_, 0);
1602  return object_store_id_;
1603}
1604
1605int ObjectStoreFreeListKey::Compare(const ObjectStoreFreeListKey& other) {
1606  // TODO(jsbell): It may seem strange that we're not comparing database id's,
1607  // but that comparison will have been made earlier.
1608  // We should probably make this more clear, though...
1609  DCHECK_GE(object_store_id_, 0);
1610  return CompareInts(object_store_id_, other.object_store_id_);
1611}
1612
1613IndexFreeListKey::IndexFreeListKey() : object_store_id_(-1), index_id_(-1) {}
1614
1615bool IndexFreeListKey::Decode(StringPiece* slice, IndexFreeListKey* result) {
1616  KeyPrefix prefix;
1617  if (!KeyPrefix::Decode(slice, &prefix))
1618    return false;
1619  DCHECK(prefix.database_id_);
1620  DCHECK(!prefix.object_store_id_);
1621  DCHECK(!prefix.index_id_);
1622  unsigned char type_byte = 0;
1623  if (!DecodeByte(slice, &type_byte))
1624    return false;
1625  DCHECK_EQ(type_byte, kIndexFreeListTypeByte);
1626  if (!DecodeVarInt(slice, &result->object_store_id_))
1627    return false;
1628  if (!DecodeVarInt(slice, &result->index_id_))
1629    return false;
1630  return true;
1631}
1632
1633std::string IndexFreeListKey::Encode(int64 database_id,
1634                                     int64 object_store_id,
1635                                     int64 index_id) {
1636  KeyPrefix prefix(database_id);
1637  std::string ret = prefix.Encode();
1638  ret.push_back(kIndexFreeListTypeByte);
1639  EncodeVarInt(object_store_id, &ret);
1640  EncodeVarInt(index_id, &ret);
1641  return ret;
1642}
1643
1644std::string IndexFreeListKey::EncodeMaxKey(int64 database_id,
1645                                           int64 object_store_id) {
1646  return Encode(
1647      database_id, object_store_id, std::numeric_limits<int64>::max());
1648}
1649
1650int IndexFreeListKey::Compare(const IndexFreeListKey& other) {
1651  DCHECK_GE(object_store_id_, 0);
1652  DCHECK_GE(index_id_, 0);
1653  if (int x = CompareInts(object_store_id_, other.object_store_id_))
1654    return x;
1655  return CompareInts(index_id_, other.index_id_);
1656}
1657
1658int64 IndexFreeListKey::ObjectStoreId() const {
1659  DCHECK_GE(object_store_id_, 0);
1660  return object_store_id_;
1661}
1662
1663int64 IndexFreeListKey::IndexId() const {
1664  DCHECK_GE(index_id_, 0);
1665  return index_id_;
1666}
1667
1668// TODO(jsbell): We never use this to look up object store ids,
1669// because a mapping is kept in the IndexedDBDatabase. Can the
1670// mapping become unreliable?  Can we remove this?
1671bool ObjectStoreNamesKey::Decode(StringPiece* slice,
1672                                 ObjectStoreNamesKey* result) {
1673  KeyPrefix prefix;
1674  if (!KeyPrefix::Decode(slice, &prefix))
1675    return false;
1676  DCHECK(prefix.database_id_);
1677  DCHECK(!prefix.object_store_id_);
1678  DCHECK(!prefix.index_id_);
1679  unsigned char type_byte = 0;
1680  if (!DecodeByte(slice, &type_byte))
1681    return false;
1682  DCHECK_EQ(type_byte, kObjectStoreNamesTypeByte);
1683  if (!DecodeStringWithLength(slice, &result->object_store_name_))
1684    return false;
1685  return true;
1686}
1687
1688std::string ObjectStoreNamesKey::Encode(
1689    int64 database_id,
1690    const base::string16& object_store_name) {
1691  KeyPrefix prefix(database_id);
1692  std::string ret = prefix.Encode();
1693  ret.push_back(kObjectStoreNamesTypeByte);
1694  EncodeStringWithLength(object_store_name, &ret);
1695  return ret;
1696}
1697
1698int ObjectStoreNamesKey::Compare(const ObjectStoreNamesKey& other) {
1699  return object_store_name_.compare(other.object_store_name_);
1700}
1701
1702IndexNamesKey::IndexNamesKey() : object_store_id_(-1) {}
1703
1704// TODO(jsbell): We never use this to look up index ids, because a mapping
1705// is kept at a higher level.
1706bool IndexNamesKey::Decode(StringPiece* slice, IndexNamesKey* result) {
1707  KeyPrefix prefix;
1708  if (!KeyPrefix::Decode(slice, &prefix))
1709    return false;
1710  DCHECK(prefix.database_id_);
1711  DCHECK(!prefix.object_store_id_);
1712  DCHECK(!prefix.index_id_);
1713  unsigned char type_byte = 0;
1714  if (!DecodeByte(slice, &type_byte))
1715    return false;
1716  DCHECK_EQ(type_byte, kIndexNamesKeyTypeByte);
1717  if (!DecodeVarInt(slice, &result->object_store_id_))
1718    return false;
1719  if (!DecodeStringWithLength(slice, &result->index_name_))
1720    return false;
1721  return true;
1722}
1723
1724std::string IndexNamesKey::Encode(int64 database_id,
1725                                  int64 object_store_id,
1726                                  const base::string16& index_name) {
1727  KeyPrefix prefix(database_id);
1728  std::string ret = prefix.Encode();
1729  ret.push_back(kIndexNamesKeyTypeByte);
1730  EncodeVarInt(object_store_id, &ret);
1731  EncodeStringWithLength(index_name, &ret);
1732  return ret;
1733}
1734
1735int IndexNamesKey::Compare(const IndexNamesKey& other) {
1736  DCHECK_GE(object_store_id_, 0);
1737  if (int x = CompareInts(object_store_id_, other.object_store_id_))
1738    return x;
1739  return index_name_.compare(other.index_name_);
1740}
1741
1742ObjectStoreDataKey::ObjectStoreDataKey() {}
1743ObjectStoreDataKey::~ObjectStoreDataKey() {}
1744
1745bool ObjectStoreDataKey::Decode(StringPiece* slice,
1746                                ObjectStoreDataKey* result) {
1747  KeyPrefix prefix;
1748  if (!KeyPrefix::Decode(slice, &prefix))
1749    return false;
1750  DCHECK(prefix.database_id_);
1751  DCHECK(prefix.object_store_id_);
1752  DCHECK_EQ(prefix.index_id_, kSpecialIndexNumber);
1753  if (!ExtractEncodedIDBKey(slice, &result->encoded_user_key_))
1754    return false;
1755  return true;
1756}
1757
1758std::string ObjectStoreDataKey::Encode(int64 database_id,
1759                                       int64 object_store_id,
1760                                       const std::string encoded_user_key) {
1761  KeyPrefix prefix(KeyPrefix::CreateWithSpecialIndex(
1762      database_id, object_store_id, kSpecialIndexNumber));
1763  std::string ret = prefix.Encode();
1764  ret.append(encoded_user_key);
1765
1766  return ret;
1767}
1768
1769std::string ObjectStoreDataKey::Encode(int64 database_id,
1770                                       int64 object_store_id,
1771                                       const IndexedDBKey& user_key) {
1772  std::string encoded_key;
1773  EncodeIDBKey(user_key, &encoded_key);
1774  return Encode(database_id, object_store_id, encoded_key);
1775}
1776
1777scoped_ptr<IndexedDBKey> ObjectStoreDataKey::user_key() const {
1778  scoped_ptr<IndexedDBKey> key;
1779  StringPiece slice(encoded_user_key_);
1780  if (!DecodeIDBKey(&slice, &key)) {
1781    // TODO(jsbell): Return error.
1782  }
1783  return key.Pass();
1784}
1785
1786const int64 ObjectStoreDataKey::kSpecialIndexNumber = kObjectStoreDataIndexId;
1787
1788ExistsEntryKey::ExistsEntryKey() {}
1789ExistsEntryKey::~ExistsEntryKey() {}
1790
1791bool ExistsEntryKey::Decode(StringPiece* slice, ExistsEntryKey* result) {
1792  KeyPrefix prefix;
1793  if (!KeyPrefix::Decode(slice, &prefix))
1794    return false;
1795  DCHECK(prefix.database_id_);
1796  DCHECK(prefix.object_store_id_);
1797  DCHECK_EQ(prefix.index_id_, kSpecialIndexNumber);
1798  if (!ExtractEncodedIDBKey(slice, &result->encoded_user_key_))
1799    return false;
1800  return true;
1801}
1802
1803std::string ExistsEntryKey::Encode(int64 database_id,
1804                                   int64 object_store_id,
1805                                   const std::string& encoded_key) {
1806  KeyPrefix prefix(KeyPrefix::CreateWithSpecialIndex(
1807      database_id, object_store_id, kSpecialIndexNumber));
1808  std::string ret = prefix.Encode();
1809  ret.append(encoded_key);
1810  return ret;
1811}
1812
1813std::string ExistsEntryKey::Encode(int64 database_id,
1814                                   int64 object_store_id,
1815                                   const IndexedDBKey& user_key) {
1816  std::string encoded_key;
1817  EncodeIDBKey(user_key, &encoded_key);
1818  return Encode(database_id, object_store_id, encoded_key);
1819}
1820
1821scoped_ptr<IndexedDBKey> ExistsEntryKey::user_key() const {
1822  scoped_ptr<IndexedDBKey> key;
1823  StringPiece slice(encoded_user_key_);
1824  if (!DecodeIDBKey(&slice, &key)) {
1825    // TODO(jsbell): Return error.
1826  }
1827  return key.Pass();
1828}
1829
1830const int64 ExistsEntryKey::kSpecialIndexNumber = kExistsEntryIndexId;
1831
1832bool BlobEntryKey::Decode(StringPiece* slice, BlobEntryKey* result) {
1833  KeyPrefix prefix;
1834  if (!KeyPrefix::Decode(slice, &prefix))
1835    return false;
1836  DCHECK(prefix.database_id_);
1837  DCHECK(prefix.object_store_id_);
1838  DCHECK_EQ(prefix.index_id_, kSpecialIndexNumber);
1839
1840  if (!ExtractEncodedIDBKey(slice, &result->encoded_user_key_))
1841    return false;
1842  result->database_id_ = prefix.database_id_;
1843  result->object_store_id_ = prefix.object_store_id_;
1844
1845  return true;
1846}
1847
1848bool BlobEntryKey::FromObjectStoreDataKey(StringPiece* slice,
1849                                          BlobEntryKey* result) {
1850  KeyPrefix prefix;
1851  if (!KeyPrefix::Decode(slice, &prefix))
1852    return false;
1853  DCHECK(prefix.database_id_);
1854  DCHECK(prefix.object_store_id_);
1855  DCHECK_EQ(prefix.index_id_, ObjectStoreDataKey::kSpecialIndexNumber);
1856
1857  if (!ExtractEncodedIDBKey(slice, &result->encoded_user_key_))
1858    return false;
1859  result->database_id_ = prefix.database_id_;
1860  result->object_store_id_ = prefix.object_store_id_;
1861  return true;
1862}
1863
1864std::string BlobEntryKey::ReencodeToObjectStoreDataKey(StringPiece* slice) {
1865  // TODO(ericu): We could be more efficient here, since the suffix is the same.
1866  BlobEntryKey key;
1867  if (!Decode(slice, &key))
1868    return std::string();
1869
1870  return ObjectStoreDataKey::Encode(
1871      key.database_id_, key.object_store_id_, key.encoded_user_key_);
1872}
1873
1874std::string BlobEntryKey::EncodeMinKeyForObjectStore(int64 database_id,
1875                                                     int64 object_store_id) {
1876  // Our implied encoded_user_key_ here is empty, the lowest possible key.
1877  return Encode(database_id, object_store_id, std::string());
1878}
1879
1880std::string BlobEntryKey::EncodeStopKeyForObjectStore(int64 database_id,
1881                                                      int64 object_store_id) {
1882  DCHECK(KeyPrefix::ValidIds(database_id, object_store_id));
1883  KeyPrefix prefix(KeyPrefix::CreateWithSpecialIndex(
1884      database_id, object_store_id, kSpecialIndexNumber + 1));
1885  return prefix.Encode();
1886}
1887
1888std::string BlobEntryKey::Encode() const {
1889  DCHECK(!encoded_user_key_.empty());
1890  return Encode(database_id_, object_store_id_, encoded_user_key_);
1891}
1892
1893std::string BlobEntryKey::Encode(int64 database_id,
1894                                 int64 object_store_id,
1895                                 const IndexedDBKey& user_key) {
1896  std::string encoded_key;
1897  EncodeIDBKey(user_key, &encoded_key);
1898  return Encode(database_id, object_store_id, encoded_key);
1899}
1900
1901std::string BlobEntryKey::Encode(int64 database_id,
1902                                 int64 object_store_id,
1903                                 const std::string& encoded_user_key) {
1904  DCHECK(KeyPrefix::ValidIds(database_id, object_store_id));
1905  KeyPrefix prefix(KeyPrefix::CreateWithSpecialIndex(
1906      database_id, object_store_id, kSpecialIndexNumber));
1907  return prefix.Encode() + encoded_user_key;
1908}
1909
1910const int64 BlobEntryKey::kSpecialIndexNumber = kBlobEntryIndexId;
1911
1912IndexDataKey::IndexDataKey()
1913    : database_id_(-1),
1914      object_store_id_(-1),
1915      index_id_(-1),
1916      sequence_number_(-1) {}
1917
1918IndexDataKey::~IndexDataKey() {}
1919
1920bool IndexDataKey::Decode(StringPiece* slice, IndexDataKey* result) {
1921  KeyPrefix prefix;
1922  if (!KeyPrefix::Decode(slice, &prefix))
1923    return false;
1924  DCHECK(prefix.database_id_);
1925  DCHECK(prefix.object_store_id_);
1926  DCHECK_GE(prefix.index_id_, kMinimumIndexId);
1927  result->database_id_ = prefix.database_id_;
1928  result->object_store_id_ = prefix.object_store_id_;
1929  result->index_id_ = prefix.index_id_;
1930  result->sequence_number_ = -1;
1931  result->encoded_primary_key_ = MinIDBKey();
1932
1933  if (!ExtractEncodedIDBKey(slice, &result->encoded_user_key_))
1934    return false;
1935
1936  // [optional] sequence number
1937  if (slice->empty())
1938    return true;
1939  if (!DecodeVarInt(slice, &result->sequence_number_))
1940    return false;
1941
1942  // [optional] primary key
1943  if (slice->empty())
1944    return true;
1945  if (!ExtractEncodedIDBKey(slice, &result->encoded_primary_key_))
1946    return false;
1947  return true;
1948}
1949
1950std::string IndexDataKey::Encode(int64 database_id,
1951                                 int64 object_store_id,
1952                                 int64 index_id,
1953                                 const std::string& encoded_user_key,
1954                                 const std::string& encoded_primary_key,
1955                                 int64 sequence_number) {
1956  KeyPrefix prefix(database_id, object_store_id, index_id);
1957  std::string ret = prefix.Encode();
1958  ret.append(encoded_user_key);
1959  EncodeVarInt(sequence_number, &ret);
1960  ret.append(encoded_primary_key);
1961  return ret;
1962}
1963
1964std::string IndexDataKey::Encode(int64 database_id,
1965                                 int64 object_store_id,
1966                                 int64 index_id,
1967                                 const IndexedDBKey& user_key) {
1968  std::string encoded_key;
1969  EncodeIDBKey(user_key, &encoded_key);
1970  return Encode(
1971      database_id, object_store_id, index_id, encoded_key, MinIDBKey(), 0);
1972}
1973
1974std::string IndexDataKey::Encode(int64 database_id,
1975                                 int64 object_store_id,
1976                                 int64 index_id,
1977                                 const IndexedDBKey& user_key,
1978                                 const IndexedDBKey& user_primary_key) {
1979  std::string encoded_key;
1980  EncodeIDBKey(user_key, &encoded_key);
1981  std::string encoded_primary_key;
1982  EncodeIDBKey(user_primary_key, &encoded_primary_key);
1983  return Encode(database_id,
1984                object_store_id,
1985                index_id,
1986                encoded_key,
1987                encoded_primary_key,
1988                0);
1989}
1990
1991std::string IndexDataKey::EncodeMinKey(int64 database_id,
1992                                       int64 object_store_id,
1993                                       int64 index_id) {
1994  return Encode(
1995      database_id, object_store_id, index_id, MinIDBKey(), MinIDBKey(), 0);
1996}
1997
1998std::string IndexDataKey::EncodeMaxKey(int64 database_id,
1999                                       int64 object_store_id,
2000                                       int64 index_id) {
2001  return Encode(database_id,
2002                object_store_id,
2003                index_id,
2004                MaxIDBKey(),
2005                MaxIDBKey(),
2006                std::numeric_limits<int64>::max());
2007}
2008
2009int64 IndexDataKey::DatabaseId() const {
2010  DCHECK_GE(database_id_, 0);
2011  return database_id_;
2012}
2013
2014int64 IndexDataKey::ObjectStoreId() const {
2015  DCHECK_GE(object_store_id_, 0);
2016  return object_store_id_;
2017}
2018
2019int64 IndexDataKey::IndexId() const {
2020  DCHECK_GE(index_id_, 0);
2021  return index_id_;
2022}
2023
2024scoped_ptr<IndexedDBKey> IndexDataKey::user_key() const {
2025  scoped_ptr<IndexedDBKey> key;
2026  StringPiece slice(encoded_user_key_);
2027  if (!DecodeIDBKey(&slice, &key)) {
2028    // TODO(jsbell): Return error.
2029  }
2030  return key.Pass();
2031}
2032
2033scoped_ptr<IndexedDBKey> IndexDataKey::primary_key() const {
2034  scoped_ptr<IndexedDBKey> key;
2035  StringPiece slice(encoded_primary_key_);
2036  if (!DecodeIDBKey(&slice, &key)) {
2037    // TODO(jsbell): Return error.
2038  }
2039  return key.Pass();
2040}
2041
2042}  // namespace content
2043