Don't use ID generation logic always. Only reassign IDs...

chrome/browser/bookmarks/bookmark_codec.cc

 // Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/bookmarks/bookmark_codec.h"
 
+#include <algorithm>
+
 #include "app/l10n_util.h"
 #include "base/string_util.h"
 #include "base/values.h"
 #include "chrome/browser/bookmarks/bookmark_model.h"
 #include "googleurl/src/gurl.h"
 #include "grit/generated_resources.h"
 
 using base::Time;
 
-UniqueIDGenerator::UniqueIDGenerator() {
-  Reset();
-}
-
-int64 UniqueIDGenerator::GetUniqueID(int64 id) {
-  // If the given ID is already assigned, generate new ID.
-  if (IsIdAssigned(id))
-    id = current_max_ + 1;
-
-  // Record the new ID as assigned.
-  RecordId(id);
-
-  if (id > current_max_)
-    current_max_ = id;
-
-  return id;
-}
-
-bool UniqueIDGenerator::IsIdAssigned(int64 id) const {
-  // If the set is already instantiated, then use the set to determine if the
-  // given ID is assigned. Otherwise use the current maximum to determine if the
-  // given ID is assigned.
-  if (assigned_ids_.get())
-    return assigned_ids_->find(id) != assigned_ids_->end();
-  else
-    return id <= current_max_;
-}
-
-void UniqueIDGenerator::RecordId(int64 id) {
-  // If the set is instantiated, then use the set.
-  if (assigned_ids_.get()) {
-    assigned_ids_->insert(id);
-    return;
-  }
-
-  // The set is not yet instantiated. If the ID is current_max_ + 1, then just
-  // update the current_max_. Otherwise, instantiate the set and add all IDs
-  // from 0 to current_max_ to it.
-  if (id == current_max_ + 1) {
-    ++current_max_;
-    return;
-  }
-  assigned_ids_.reset(new std::set<int64>);
-  for (int64 i = 0; i <= current_max_; ++i)
-    assigned_ids_->insert(i);
-  assigned_ids_->insert(id);
-}
-
-void UniqueIDGenerator::Reset() {
-  current_max_ = 0;
-  assigned_ids_.reset(NULL);
-}
-
 const wchar_t* BookmarkCodec::kRootsKey = L"roots";
 const wchar_t* BookmarkCodec::kRootFolderNameKey = L"bookmark_bar";
 const wchar_t* BookmarkCodec::kOtherBookmarkFolderNameKey = L"other";
 const wchar_t* BookmarkCodec::kVersionKey = L"version";
 const wchar_t* BookmarkCodec::kChecksumKey = L"checksum";
 const wchar_t* BookmarkCodec::kIdKey = L"id";
 const wchar_t* BookmarkCodec::kTypeKey = L"type";
 const wchar_t* BookmarkCodec::kNameKey = L"name";
 const wchar_t* BookmarkCodec::kDateAddedKey = L"date_added";
 const wchar_t* BookmarkCodec::kURLKey = L"url";
 const wchar_t* BookmarkCodec::kDateModifiedKey = L"date_modified";
 const wchar_t* BookmarkCodec::kChildrenKey = L"children";
 const wchar_t* BookmarkCodec::kTypeURL = L"url";
 const wchar_t* BookmarkCodec::kTypeFolder = L"folder";
 
 // Current version of the file.
 static const int kCurrentVersion = 1;
 
 BookmarkCodec::BookmarkCodec()
-    : ids_reassigned_(false) {
+    : ids_reassigned_(false),
+      ids_missing_(false),
+      maximum_id_(0) {
 }
 
 Value* BookmarkCodec::Encode(BookmarkModel* model) {
   return Encode(model->GetBookmarkBarNode(), model->other_node());
 }
 
 Value* BookmarkCodec::Encode(const BookmarkNode* bookmark_bar_node,
                              const BookmarkNode* other_folder_node) {
   ids_reassigned_ = false;
   InitializeChecksum();
   DictionaryValue* roots = new DictionaryValue();
   roots->Set(kRootFolderNameKey, EncodeNode(bookmark_bar_node));
   roots->Set(kOtherBookmarkFolderNameKey, EncodeNode(other_folder_node));
 
   DictionaryValue* main = new DictionaryValue();
   main->SetInteger(kVersionKey, kCurrentVersion);
   FinalizeChecksum();
   // We are going to store the computed checksum. So set stored checksum to be
   // the same as computed checksum.
   stored_checksum_ = computed_checksum_;
   main->Set(kChecksumKey, Value::CreateStringValue(computed_checksum_));
   main->Set(kRootsKey, roots);
   return main;
 }
 
 bool BookmarkCodec::Decode(BookmarkNode* bb_node,
                            BookmarkNode* other_folder_node,
                            int64* max_id,
                            const Value& value) {
-  // TODO(munjal): Instead of paying the price of ID generator in al lcases, we
-  // should only pay the price if we detect the file has changed and do a second
-  // pass to reassign IDs. See issue 16357.
-  id_generator_.Reset();
   ids_reassigned_ = false;
+  ids_missing_ = false;
+  maximum_id_ = 0;
   stored_checksum_.clear();
   InitializeChecksum();
   bool success = DecodeHelper(bb_node, other_folder_node, value);
   FinalizeChecksum();
-  *max_id = id_generator_.current_max() + 1;
+  // If either the checksums differ or some IDs were missing, reassign IDs.
+  if (ids_missing_ || computed_checksum() != stored_checksum())
+    ReassignIDs(bb_node, other_folder_node);
+  *max_id = maximum_id_ + 1;
   return success;
 }
 
 Value* BookmarkCodec::EncodeNode(const BookmarkNode* node) {
   DictionaryValue* value = new DictionaryValue();
   std::string id;
   id = Int64ToString(node->id());
   value->SetString(kIdKey, id);
   const std::wstring& title = node->GetTitle();
   value->SetString(kNameKey, title);
@@ skipping 85 matching lines @@
     DecodeNode(*static_cast<DictionaryValue*>(child_value), parent, NULL);
   }
   return true;
 }
 
 bool BookmarkCodec::DecodeNode(const DictionaryValue& value,
                                BookmarkNode* parent,
                                BookmarkNode* node) {
   std::string id_string;
   int64 id = 0;
-  if (value.GetString(kIdKey, &id_string))
-    if (!StringToInt64(id_string, &id))
-      return false;
-  int64 new_id = id_generator_.GetUniqueID(id);
-  if (new_id != id)
-    ids_reassigned_ = true;
-  id = new_id;
+  if (!value.GetString(kIdKey, &id_string) || !StringToInt64(id_string, &id))
+    ids_missing_ = true;
+
+  maximum_id_ = std::max(maximum_id_, id);
 
   std::wstring title;
-  if (!value.GetString(kNameKey, &title))
-    title = std::wstring();
+  value.GetString(kNameKey, &title);
 
   std::wstring date_added_string;
   if (!value.GetString(kDateAddedKey, &date_added_string))
     date_added_string = Int64ToWString(Time::Now().ToInternalValue());
 
   std::wstring type_string;
   if (!value.GetString(kTypeKey, &type_string))
     return false;
 
   if (type_string != kTypeURL && type_string != kTypeFolder)
@@ skipping 22 matching lines @@
     if (!value.Get(kChildrenKey, &child_values))
       return false;
 
     if (child_values->GetType() != Value::TYPE_LIST)
       return false;
 
     if (!node) {
       node = new BookmarkNode(id, GURL());
     } else {
       // If a new node is not created, explicitly assign ID to the existing one.
-      DCHECK(id != 0);
       node->set_id(id);
     }
 
     node->SetType(BookmarkNode::FOLDER);
     node->set_date_group_modified(Time::FromInternalValue(
         StringToInt64(WideToUTF16Hack(last_modified_date))));
 
     if (parent)
       parent->Add(parent->GetChildCount(), node);
 
     UpdateChecksumWithFolderNode(id_string, title);
 
     if (!DecodeChildren(*static_cast<ListValue*>(child_values), node))
       return false;
   }
 
   node->SetTitle(title);
   node->set_date_added(Time::FromInternalValue(
       StringToInt64(WideToUTF16Hack(date_added_string))));
   return true;
 }
 
+void BookmarkCodec::ReassignIDs(BookmarkNode* bb_node,
+                                BookmarkNode* other_node) {
+  maximum_id_ = 0;
+  ReassignIDsHelper(bb_node);

[Erik does not do reviews, 2009/07/15 19:44:52]

Are there (or should there be) any assumptions about the ids of bb_node and
other_node?  At initial creation time, these will have an id of 1 and 2
respectively, but in this new code that isn't true.  Scott, do you think this is
an issue?

+  ReassignIDsHelper(other_node);
+  ids_reassigned_ = true;
+}
+
+void BookmarkCodec::ReassignIDsHelper(BookmarkNode* node) {
+  DCHECK(node);
+  node->set_id(++maximum_id_);
+  for (int i = 0; i < node->GetChildCount(); ++i)
+    ReassignIDsHelper(node->GetChild(i));
+}
+
 void BookmarkCodec::UpdateChecksum(const std::string& str) {
   MD5Update(&md5_context_, str.data(), str.length() * sizeof(char));
 }
 
 void BookmarkCodec::UpdateChecksum(const std::wstring& str) {
   MD5Update(&md5_context_, str.data(), str.length() * sizeof(wchar_t));
 }
 
 void BookmarkCodec::UpdateChecksumWithUrlNode(const std::string& id,
                                               const std::wstring& title,
@@ skipping 13 matching lines @@
 
 void BookmarkCodec::InitializeChecksum() {
   MD5Init(&md5_context_);
 }
 
 void BookmarkCodec::FinalizeChecksum() {
   MD5Digest digest;
   MD5Final(&digest, &md5_context_);
   computed_checksum_ = MD5DigestToBase16(digest);
 }