Squashed 'third_party/ctemplate/' content from commit 6742f62
Change-Id: I828e4e4c906f13ba19944d78a8a78652b62949af
git-subtree-dir: third_party/ctemplate
git-subtree-split: 6742f6233db12f545e90baa8f34f5c29c4eb396a
diff --git a/src/template_string.cc b/src/template_string.cc
new file mode 100644
index 0000000..a77d37f
--- /dev/null
+++ b/src/template_string.cc
@@ -0,0 +1,256 @@
+// Copyright (c) 2008, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+// * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// ---
+// Authors: jcrim@google.com (Jay Crim)
+// csilvers@google.com (Craig Silverstein)
+
+#include <config.h>
+#include "base/mutex.h" // This has to come first to get _XOPEN_SOURCE
+#include <ctemplate/find_ptr.h>
+#include <ctemplate/template_string.h>
+#include HASH_SET_H
+#include "base/arena.h"
+#include "base/thread_annotations.h"
+#include <assert.h>
+#include "base/macros.h" // for uint32, uint64, UNALIGNED_LOAD32
+#include "base/util.h"
+
+#ifdef HAVE_UNORDERED_MAP
+using HASH_NAMESPACE::unordered_set;
+// This is totally cheap, but minimizes the need for #ifdef's below...
+#define hash_set unordered_set
+#else
+using HASH_NAMESPACE::hash_set;
+#endif
+
+namespace ctemplate {
+
+// Based on public domain MurmurHashUnaligned2, by Austin Appleby.
+// http://murmurhash.googlepages.com/
+// This variation:
+// - interleaves odd/even 32-bit words to improve performance and
+// to generate more random bits,
+// - has a more complex final mix to combine the 32-bit hashes into
+// 64-bits,
+// - uses a fixed seed.
+// This is not static because template_string_test accesses it directly.
+uint64 MurmurHash64(const char* ptr, size_t len) {
+ const uint32 kMultiplyVal = 0x5bd1e995;
+ const int kShiftVal = 24;
+ const uint32 kHashSeed1 = 0xc86b14f7;
+ const uint32 kHashSeed2 = 0x650f5c4d;
+
+ uint32 h1 = kHashSeed1 ^ len, h2 = kHashSeed2;
+ while (len >= 8) {
+ uint32 k1 = UNALIGNED_LOAD32(ptr);
+ k1 *= kMultiplyVal;
+ k1 ^= k1 >> kShiftVal;
+ k1 *= kMultiplyVal;
+
+ h1 *= kMultiplyVal;
+ h1 ^= k1;
+ ptr += 4;
+
+ uint32 k2 = UNALIGNED_LOAD32(ptr);
+ k2 *= kMultiplyVal;
+ k2 ^= k2 >> kShiftVal;
+ k2 *= kMultiplyVal;
+
+ h2 *= kMultiplyVal;
+ h2 ^= k2;
+ ptr += 4;
+
+ len -= 8;
+ }
+
+ if (len >= 4) {
+ uint32 k1 = UNALIGNED_LOAD32(ptr);
+ k1 *= kMultiplyVal;
+ k1 ^= k1 >> kShiftVal;
+ k1 *= kMultiplyVal;
+
+ h1 *= kShiftVal;
+ h1 ^= k1;
+
+ ptr += 4;
+ len -= 4;
+ }
+
+ switch(len) {
+ case 3:
+ h2 ^= ptr[2] << 16; // fall through.
+ case 2:
+ h2 ^= ptr[1] << 8; // fall through.
+ case 1:
+ h2 ^= ptr[0]; // fall through.
+ default:
+ h2 *= kMultiplyVal;
+ }
+
+ h1 ^= h2 >> 18;
+ h1 *= kMultiplyVal;
+ h2 ^= h1 >> 22;
+ h2 *= kMultiplyVal;
+ h1 ^= h2 >> 17;
+ h1 *= kMultiplyVal;
+
+ uint64 h = h1;
+ h = (h << 32) | h2;
+ return h;
+}
+
+// Unlike StaticTemplateString, it is not a good idea to have a
+// default TemplateString::Hasher because TemplateString does not
+// provide any lifetime guarantees. The global template_string_set is
+// an obvious exception.
+struct TemplateStringHasher {
+ size_t operator()(const TemplateString& ts) const {
+ TemplateId id = ts.GetGlobalId();
+ DCHECK(IsTemplateIdInitialized(id));
+ return hasher(id);
+ }
+ // Less operator for MSVC's hash containers.
+ bool operator()(const TemplateString& a, const TemplateString& b) const {
+ const TemplateId id_a = a.GetGlobalId();
+ const TemplateId id_b = b.GetGlobalId();
+ assert(IsTemplateIdInitialized(id_a));
+ assert(IsTemplateIdInitialized(id_b));
+ return hasher(id_a, id_b);
+ }
+ TemplateIdHasher hasher;
+ // These two public members are required by msvc. 4 and 8 are defaults.
+ static const size_t bucket_size = 4;
+ static const size_t min_buckets = 8;
+};
+
+namespace {
+Mutex mutex(base::LINKER_INITIALIZED);
+
+typedef hash_set<TemplateString, TemplateStringHasher> TemplateStringSet;
+
+TemplateStringSet* template_string_set
+GUARDED_BY(mutex) PT_GUARDED_BY(mutex) = NULL;
+
+UnsafeArena* arena
+GUARDED_BY(mutex) PT_GUARDED_BY(mutex) = NULL;
+} // unnamed namespace
+
+
+size_t StringHash::Hash(const char* s, size_t slen) const {
+ return static_cast<size_t>(MurmurHash64(s, slen));
+}
+
+void TemplateString::AddToGlobalIdToNameMap() LOCKS_EXCLUDED(mutex) {
+ // shouldn't be calling this if we don't have an id.
+ CHECK(IsTemplateIdInitialized(id_));
+ {
+ // Check to see if it's already here.
+ ReaderMutexLock reader_lock(&mutex);
+ if (template_string_set) {
+ const TemplateString* iter =
+ find_ptr0(*template_string_set, *this);
+ if (iter) {
+ DCHECK_EQ(TemplateString(ptr_, length_),
+ TemplateString(iter->ptr_, iter->length_))
+ << "TemplateId collision!";
+ return;
+ }
+ }
+ }
+ WriterMutexLock writer_lock(&mutex);
+ // First initialize our data structures if we need to.
+ if (!template_string_set) {
+ template_string_set = new TemplateStringSet;
+ }
+
+ if (!arena) {
+ arena = new UnsafeArena(1024); // 1024 was picked out of a hat.
+ }
+
+ if (template_string_set->count(*this)) {
+ return;
+ }
+ // If we are immutable, we can store ourselves directly in the map.
+ // Otherwise, we need to make an immutable copy.
+ if (is_immutable()) {
+ template_string_set->insert(*this);
+ } else {
+ const char* immutable_copy = arena->Memdup(ptr_, length_);
+ template_string_set->insert(
+ TemplateString(immutable_copy, length_, true, id_));
+ }
+}
+
+TemplateId TemplateString::GetGlobalId() const {
+ if (IsTemplateIdInitialized(id_)) {
+ return id_;
+ }
+ // Initialize the id and sets the "initialized" flag.
+ return static_cast<TemplateId>(MurmurHash64(ptr_, length_) |
+ kTemplateStringInitializedFlag);
+}
+
+// static
+TemplateString TemplateString::IdToString(TemplateId id) LOCKS_EXCLUDED(mutex) {
+ ReaderMutexLock reader_lock(&mutex);
+ if (!template_string_set)
+ return TemplateString(kStsEmpty);
+ // To search the set by TemplateId, we must first construct a dummy
+ // TemplateString. This may seem weird, but it lets us use a
+ // hash_set instead of a hash_map.
+ TemplateString id_as_template_string(NULL, 0, false, id);
+ const TemplateString* iter = find_ptr0(*template_string_set, id_as_template_string);
+ return iter ? *iter : TemplateString(kStsEmpty);
+}
+
+StaticTemplateStringInitializer::StaticTemplateStringInitializer(
+ const StaticTemplateString* sts) {
+ // Compute the sts's id if it wasn't specified at static-init
+ // time. If it was specified at static-init time, verify it's
+ // correct. This is necessary because static-init id's are, by
+ // nature, pre-computed, and the id-generating algorithm may have
+ // changed between the time they were computed and now.
+ if (sts->do_not_use_directly_.id_ == 0) {
+ sts->do_not_use_directly_.id_ = TemplateString(*sts).GetGlobalId();
+ } else {
+ // Don't use the TemplateString(const StaticTemplateString& sts)
+ // constructor below, since if we do, GetGlobalId will just return
+ // sts->do_not_use_directly_.id_ and the check will be pointless.
+ DCHECK_EQ(TemplateString(sts->do_not_use_directly_.ptr_,
+ sts->do_not_use_directly_.length_).GetGlobalId(),
+ sts->do_not_use_directly_.id_);
+ }
+
+ // Now add this id/name pair to the backwards map from id to name.
+ TemplateString ts_copy_of_sts(*sts);
+ ts_copy_of_sts.AddToGlobalIdToNameMap();
+}
+
+}