| // Copyright 2016 Google Inc. All Rights Reserved. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| #include "cobalt/base/token.h" |
| |
| #include <set> |
| #include <vector> |
| |
| #include "base/logging.h" |
| #include "base/memory/singleton.h" |
| #include "base/synchronization/lock.h" |
| |
| namespace base { |
| |
| namespace { |
| |
| // TODO: Replace more potential strings with Token, like event names and |
| // attribute names. |
| // TODO: Turn kTagName of HTMLElements into Token. |
| // TODO: Implement Token friendly containers. |
| // TODO: Improve the internal storage of Token. Possibly remove the use of |
| // std::string and manage the buffer by ourselves. |
| class TokenStorage { |
| public: |
| static TokenStorage* GetInstance() { return Singleton<TokenStorage>::get(); } |
| |
| const char* GetStorage(const char* str); |
| |
| private: |
| friend struct DefaultSingletonTraits<TokenStorage>; |
| |
| TokenStorage() |
| : hash_table_(Token::kHashSlotCount * Token::kStringsPerSlot) {} |
| |
| std::vector<std::string> hash_table_; |
| // The collision table contains Tokens whose hash values collide with one of |
| // the existing Token. This should happen very rare. |
| std::set<std::string> collision_table_; |
| const std::string empty_; |
| base::Lock lock_; |
| }; |
| |
| #if defined(BASE_HASH_USE_HASH_STRUCT) |
| |
| uint32 hash(const char* str) { |
| return BASE_HASH_NAMESPACE::hash<const char*>()(str); |
| } |
| |
| #else |
| |
| uint32 hash(const char* str) { return BASE_HASH_NAMESPACE::hash_value(str); } |
| |
| #endif // COMPILER |
| |
| } // namespace |
| |
| Token::Token() : str_(TokenStorage::GetInstance()->GetStorage("")) {} |
| |
| Token::Token(const char* str) |
| : str_(TokenStorage::GetInstance()->GetStorage(str)) {} |
| |
| Token::Token(const std::string& str) |
| : str_(TokenStorage::GetInstance()->GetStorage(str.c_str())) {} |
| |
| const char* TokenStorage::GetStorage(const char* str) { |
| DCHECK(str); |
| |
| if (!str || str[0] == 0) { |
| return empty_.c_str(); |
| } |
| |
| uint32 slot = hash(str) % Token::kHashSlotCount; |
| // First check if we already have this token. |
| for (uint32 i = 0; i < Token::kStringsPerSlot; ++i) { |
| uint32 index = slot * Token::kStringsPerSlot + i; |
| if (hash_table_[index].empty()) { |
| break; |
| } |
| if (hash_table_[index] == str) { |
| return hash_table_[index].c_str(); |
| } |
| } |
| |
| base::AutoLock auto_lock(lock_); |
| // Now try to create this token in the table. |
| for (uint32 i = 0; i < Token::kStringsPerSlot; ++i) { |
| uint32 index = slot * Token::kStringsPerSlot + i; |
| if (hash_table_[index].empty()) { |
| hash_table_[index] = str; |
| return hash_table_[index].c_str(); |
| } |
| } |
| |
| // This should never happen in production as we use a quite large bin size |
| // compares to the tokens in the system. But it is does, we want to ensure |
| // that the code can still work without crashing. |
| if (collision_table_.empty()) { |
| LOG(ERROR) << "Got collisions in Token."; |
| } |
| |
| std::set<std::string>::iterator iter = collision_table_.find(str); |
| if (iter != collision_table_.end()) { |
| return iter->c_str(); |
| } |
| return collision_table_.insert(str).first->c_str(); |
| } |
| |
| } // namespace base |