Imported Upstream version 20150501upstream/20150501

Change-Id: If4a5c98fe2f75b34bb268fb8276f6f1d88fab3a2
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>

19 files changed, 229 insertions, 568 deletions

diff --git a/util/arena.cc b/util/arena.cc
deleted file mode 100644
index 25753c5..0000000
--- a/util/arena.cc
+++ /dev/null
@@ -1,168 +0,0 @@
-// Copyright 2000 The RE2 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 "util/util.h"
-
-namespace re2 {
-
-// ----------------------------------------------------------------------
-// UnsafeArena::UnsafeArena()
-// UnsafeArena::~UnsafeArena()
-//    Destroying the arena automatically calls Reset()
-// ----------------------------------------------------------------------
-
-
-UnsafeArena::UnsafeArena(const size_t block_size)
-  : block_size_(block_size),
-    freestart_(NULL),                   // set for real in Reset()
-    last_alloc_(NULL),
-    remaining_(0),
-    blocks_alloced_(1),
-    overflow_blocks_(NULL) {
-  assert(block_size > kDefaultAlignment);
-
-  first_blocks_[0].mem = reinterpret_cast<char*>(malloc(block_size_));
-  first_blocks_[0].size = block_size_;
-
-  Reset();
-}
-
-UnsafeArena::~UnsafeArena() {
-  FreeBlocks();
-  assert(overflow_blocks_ == NULL);    // FreeBlocks() should do that
-  // The first X blocks stay allocated always by default.  Delete them now.
-  for (int i = 0; i < blocks_alloced_; i++)
-    free(first_blocks_[i].mem);
-}
-
-// ----------------------------------------------------------------------
-// UnsafeArena::Reset()
-//    Clears all the memory an arena is using.
-// ----------------------------------------------------------------------
-
-void UnsafeArena::Reset() {
-  FreeBlocks();
-  freestart_ = first_blocks_[0].mem;
-  remaining_ = first_blocks_[0].size;
-  last_alloc_ = NULL;
-
-  // We do not know for sure whether or not the first block is aligned,
-  // so we fix that right now.
-  const int overage = reinterpret_cast<uintptr_t>(freestart_) &
-                      (kDefaultAlignment-1);
-  if (overage > 0) {
-    const int waste = kDefaultAlignment - overage;
-    freestart_ += waste;
-    remaining_ -= waste;
-  }
-  freestart_when_empty_ = freestart_;
-  assert(!(reinterpret_cast<uintptr_t>(freestart_)&(kDefaultAlignment-1)));
-}
-
-// -------------------------------------------------------------
-// UnsafeArena::AllocNewBlock()
-//    Adds and returns an AllocatedBlock.
-//    The returned AllocatedBlock* is valid until the next call
-//    to AllocNewBlock or Reset.  (i.e. anything that might
-//    affect overflow_blocks_).
-// -------------------------------------------------------------
-
-UnsafeArena::AllocatedBlock* UnsafeArena::AllocNewBlock(const size_t block_size) {
-  AllocatedBlock *block;
-  // Find the next block.
-  if ( blocks_alloced_ < arraysize(first_blocks_) ) {
-    // Use one of the pre-allocated blocks
-    block = &first_blocks_[blocks_alloced_++];
-  } else {                   // oops, out of space, move to the vector
-    if (overflow_blocks_ == NULL) overflow_blocks_ = new vector<AllocatedBlock>;
-    // Adds another block to the vector.
-    overflow_blocks_->resize(overflow_blocks_->size()+1);
-    // block points to the last block of the vector.
-    block = &overflow_blocks_->back();
-  }
-
-  block->mem = reinterpret_cast<char*>(malloc(block_size));
-  block->size = block_size;
-
-  return block;
-}
-
-// ----------------------------------------------------------------------
-// UnsafeArena::GetMemoryFallback()
-//    We take memory out of our pool, aligned on the byte boundary
-//    requested.  If we don't have space in our current pool, we
-//    allocate a new block (wasting the remaining space in the
-//    current block) and give you that.  If your memory needs are
-//    too big for a single block, we make a special your-memory-only
-//    allocation -- this is equivalent to not using the arena at all.
-// ----------------------------------------------------------------------
-
-void* UnsafeArena::GetMemoryFallback(const size_t size, const int align) {
-  if (size == 0)
-    return NULL;             // stl/stl_alloc.h says this is okay
-
-  assert(align > 0 && 0 == (align & (align - 1)));  // must be power of 2
-
-  // If the object is more than a quarter of the block size, allocate
-  // it separately to avoid wasting too much space in leftover bytes
-  if (block_size_ == 0 || size > block_size_/4) {
-    // then it gets its own block in the arena
-    assert(align <= kDefaultAlignment);   // because that's what new gives us
-    // This block stays separate from the rest of the world; in particular
-    // we don't update last_alloc_ so you can't reclaim space on this block.
-    return AllocNewBlock(size)->mem;
-  }
-
-  const int overage =
-    (reinterpret_cast<uintptr_t>(freestart_) & (align-1));
-  if (overage) {
-    const int waste = align - overage;
-    freestart_ += waste;
-    if (waste < remaining_) {
-      remaining_ -= waste;
-    } else {
-      remaining_ = 0;
-    }
-  }
-  if (size > remaining_) {
-    AllocatedBlock *block = AllocNewBlock(block_size_);
-    freestart_ = block->mem;
-    remaining_ = block->size;
-  }
-  remaining_ -= size;
-  last_alloc_ = freestart_;
-  freestart_ += size;
-  assert((reinterpret_cast<uintptr_t>(last_alloc_) & (align-1)) == 0);
-  return reinterpret_cast<void*>(last_alloc_);
-}
-
-// ----------------------------------------------------------------------
-// UnsafeArena::FreeBlocks()
-//    Unlike GetMemory(), which does actual work, ReturnMemory() is a
-//    no-op: we don't "free" memory until Reset() is called.  We do
-//    update some stats, though.  Note we do no checking that the
-//    pointer you pass in was actually allocated by us, or that it
-//    was allocated for the size you say, so be careful here!
-//       FreeBlocks() does the work for Reset(), actually freeing all
-//    memory allocated in one fell swoop.
-// ----------------------------------------------------------------------
-
-void UnsafeArena::FreeBlocks() {
-  for ( int i = 1; i < blocks_alloced_; ++i ) {  // keep first block alloced
-    free(first_blocks_[i].mem);
-    first_blocks_[i].mem = NULL;
-    first_blocks_[i].size = 0;
-  }
-  blocks_alloced_ = 1;
-  if (overflow_blocks_ != NULL) {
-    vector<AllocatedBlock>::iterator it;
-    for (it = overflow_blocks_->begin(); it != overflow_blocks_->end(); ++it) {
-      free(it->mem);
-    }
-    delete overflow_blocks_;             // These should be used very rarely
-    overflow_blocks_ = NULL;
-  }
-}
-
-}  // namespace re2
diff --git a/util/arena.h b/util/arena.h
deleted file mode 100644
index 7eb385b..0000000
--- a/util/arena.h
+++ /dev/null
@@ -1,103 +0,0 @@
-// Copyright 2000 The RE2 Authors.  All Rights Reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// Sometimes it is necessary to allocate a large number of small
-// objects.  Doing this the usual way (malloc, new) is slow,
-// especially for multithreaded programs.  An UnsafeArena provides a
-// mark/release method of memory management: it asks for a large chunk
-// from the operating system and doles it out bit by bit as required.
-// Then you free all the memory at once by calling UnsafeArena::Reset().
-// The "Unsafe" refers to the fact that UnsafeArena is not safe to
-// call from multiple threads.
-//
-// The global operator new that can be used as follows:
-//
-//   #include "lib/arena-inl.h"
-//
-//   UnsafeArena arena(1000);
-//   Foo* foo = new (AllocateInArena, &arena) Foo;
-//
-
-#ifndef RE2_UTIL_ARENA_H_
-#define RE2_UTIL_ARENA_H_
-
-namespace re2 {
-
-// This class is thread-compatible.
-class UnsafeArena {
- public:
-  UnsafeArena(const size_t block_size);
-  virtual ~UnsafeArena();
-
-  void Reset();
-
-  // This should be the worst-case alignment for any type.  This is
-  // good for IA-32, SPARC version 7 (the last one I know), and
-  // supposedly Alpha.  i386 would be more time-efficient with a
-  // default alignment of 8, but ::operator new() uses alignment of 4,
-  // and an assertion will fail below after the call to MakeNewBlock()
-  // if you try to use a larger alignment.
-#ifdef __i386__
-  static const int kDefaultAlignment = 4;
-#else
-  static const int kDefaultAlignment = 8;
-#endif
-
- private:
-  void* GetMemoryFallback(const size_t size, const int align);
-
- public:
-  void* GetMemory(const size_t size, const int align) {
-    if ( size > 0 && size < remaining_ && align == 1 ) {       // common case
-      last_alloc_ = freestart_;
-      freestart_ += size;
-      remaining_ -= size;
-      return reinterpret_cast<void*>(last_alloc_);
-    }
-    return GetMemoryFallback(size, align);
-  }
-
- private:
-  struct AllocatedBlock {
-    char *mem;
-    size_t size;
-  };
-
-  // The returned AllocatedBlock* is valid until the next call to AllocNewBlock
-  // or Reset (i.e. anything that might affect overflow_blocks_).
-  AllocatedBlock *AllocNewBlock(const size_t block_size);
-
-  const AllocatedBlock *IndexToBlock(int index) const;
-
-  const size_t block_size_;
-  char* freestart_;         // beginning of the free space in most recent block
-  char* freestart_when_empty_;  // beginning of the free space when we're empty
-  char* last_alloc_;         // used to make sure ReturnBytes() is safe
-  size_t remaining_;
-  // STL vector isn't as efficient as it could be, so we use an array at first
-  int blocks_alloced_;       // how many of the first_blocks_ have been alloced
-  AllocatedBlock first_blocks_[16];   // the length of this array is arbitrary
-  // if the first_blocks_ aren't enough, expand into overflow_blocks_.
-  vector<AllocatedBlock>* overflow_blocks_;
-
-  void FreeBlocks();         // Frees all except first block
-
-  DISALLOW_EVIL_CONSTRUCTORS(UnsafeArena);
-};
-
-// Operators for allocation on the arena
-// Syntax: new (AllocateInArena, arena) MyClass;
-// STL containers, etc.
-enum AllocateInArenaType { AllocateInArena };
-
-}  // namespace re2
-
-inline void* operator new(size_t size,
-                          re2::AllocateInArenaType /* unused */,
-                          re2::UnsafeArena *arena) {
-  return reinterpret_cast<char*>(arena->GetMemory(size, 1));
-}
-
-#endif  // RE2_UTIL_ARENA_H_
-
diff --git a/util/atomicops.h b/util/atomicops.h
index 11c1196..d69b075 100644
--- a/util/atomicops.h
+++ b/util/atomicops.h
@@ -5,6 +5,35 @@
 #ifndef RE2_UTIL_ATOMICOPS_H__
 #define RE2_UTIL_ATOMICOPS_H__
 
+// The memory ordering constraints resemble the ones in C11.
+// RELAXED - no memory ordering, just an atomic operation.
+// CONSUME - data-dependent ordering.
+// ACQUIRE - prevents memory accesses from hoisting above the operation.
+// RELEASE - prevents memory accesses from sinking below the operation.
+
+#ifndef __has_builtin
+#define __has_builtin(x) 0
+#endif
+
+#if !defined(OS_NACL) && (__has_builtin(__atomic_load_n) || (__GNUC__*10000 + __GNUC_MINOR__*100 + __GNUC_PATCHLEVEL__ >= 40801))
+
+#define ATOMIC_LOAD_RELAXED(x, p) do { (x) = __atomic_load_n((p), __ATOMIC_RELAXED); } while (0)
+#define ATOMIC_LOAD_CONSUME(x, p) do { (x) = __atomic_load_n((p), __ATOMIC_CONSUME); } while (0)
+#define ATOMIC_LOAD_ACQUIRE(x, p) do { (x) = __atomic_load_n((p), __ATOMIC_ACQUIRE); } while (0)
+#define ATOMIC_STORE_RELAXED(p, v) __atomic_store_n((p), (v), __ATOMIC_RELAXED)
+#define ATOMIC_STORE_RELEASE(p, v) __atomic_store_n((p), (v), __ATOMIC_RELEASE)
+
+#else  // old compiler
+
+#define ATOMIC_LOAD_RELAXED(x, p) do { (x) = *(p); } while (0)
+#define ATOMIC_LOAD_CONSUME(x, p) do { (x) = *(p); MaybeReadMemoryBarrier(); } while (0)
+#define ATOMIC_LOAD_ACQUIRE(x, p) do { (x) = *(p); ReadMemoryBarrier(); } while (0)
+#define ATOMIC_STORE_RELAXED(p, v) do { *(p) = (v); } while (0)
+#define ATOMIC_STORE_RELEASE(p, v) do { WriteMemoryBarrier(); *(p) = (v); } while (0)
+
+// WriteMemoryBarrier(), ReadMemoryBarrier() and MaybeReadMemoryBarrier()
+// are an implementation detail and must not be used in the rest of the code.
+
 #if defined(__i386__)
 
 static inline void WriteMemoryBarrier() {
@@ -21,7 +50,7 @@ static inline void WriteMemoryBarrier() {
   __asm__ __volatile__("sfence" : : : "memory");
 }
 
-#elif defined(__ppc__)
+#elif defined(__ppc__) || defined(__powerpc64__)
 
 static inline void WriteMemoryBarrier() {
   __asm__ __volatile__("eieio" : : : "memory");
@@ -33,6 +62,40 @@ static inline void WriteMemoryBarrier() {
   __asm__ __volatile__("wmb" : : : "memory");
 }
 
+#elif defined(__aarch64__)
+
+static inline void WriteMemoryBarrier() {
+  __asm__ __volatile__("dmb st" : : : "memory");
+}
+
+#elif defined(__arm__) && defined(__linux__)
+
+// Linux on ARM puts a suitable memory barrier at a magic address for us to call.
+static inline void WriteMemoryBarrier() {
+  ((void(*)(void))0xffff0fa0)();
+}
+
+#elif defined(__windows__)
+
+// Windows
+inline void WriteMemoryBarrier() {
+  LONG x;
+  ::InterlockedExchange(&x, 0);
+}
+
+#elif defined(OS_NACL)
+
+// Native Client
+inline void WriteMemoryBarrier() {
+  __sync_synchronize();
+}
+
+#elif defined(__mips__)
+
+inline void WriteMemoryBarrier() {
+  __asm__ __volatile__("sync" : : : "memory");
+}
+
 #else
 
 #include "util/mutex.h"
@@ -50,19 +113,9 @@ static inline void WriteMemoryBarrier() {
   re2::MutexLock l(&mu);
 }
 
-/*
-#error Need WriteMemoryBarrier for architecture.
-
-// Windows
-inline void WriteMemoryBarrier() {
-  LONG x;
-  ::InterlockedExchange(&x, 0);
-}
-*/
-
 #endif
 
-// Alpha has very weak memory ordering. If relying on WriteBarriers, must one
+// Alpha has very weak memory ordering. If relying on WriteBarriers, one must
 // use read barriers for the readers too.
 #if defined(__alpha__)
 
@@ -74,6 +127,38 @@ static inline void MaybeReadMemoryBarrier() {
 
 static inline void MaybeReadMemoryBarrier() {}
 
-#endif // __alpha__
+#endif  // __alpha__
+
+// Read barrier for various targets.
+
+#if defined(__aarch64__)
+
+static inline void ReadMemoryBarrier() {
+  __asm__ __volatile__("dmb ld" : : : "memory");
+}
+
+#elif defined(__alpha__)
+
+static inline void ReadMemoryBarrier() {
+  __asm__ __volatile__("mb" : : : "memory");
+}
+
+#elif defined(__mips__)
+
+inline void ReadMemoryBarrier() {
+  __asm__ __volatile__("sync" : : : "memory");
+}
+
+#else
+
+static inline void ReadMemoryBarrier() {}
+
+#endif
+
+#endif  // old compiler
+
+#ifndef NO_THREAD_SAFETY_ANALYSIS
+#define NO_THREAD_SAFETY_ANALYSIS
+#endif
 
 #endif  // RE2_UTIL_ATOMICOPS_H__
diff --git a/util/flags.h b/util/flags.h
index 77a06a2..98d5c06 100644
--- a/util/flags.h
+++ b/util/flags.h
@@ -5,7 +5,7 @@
 // Simplified version of Google's command line flags.
 // Does not support parsing the command line.
 // If you want to do that, see
-// http://code.google.com/p/google-gflags
+// https://gflags.github.io/gflags/
 
 #ifndef RE2_UTIL_FLAGS_H__
 #define RE2_UTIL_FLAGS_H__
diff --git a/util/logging.h b/util/logging.h
index 4443f7c..b318f27 100644
--- a/util/logging.h
+++ b/util/logging.h
@@ -68,7 +68,7 @@ class LogMessage {
  private:
   bool flushed_;
   std::ostringstream str_;
-  DISALLOW_EVIL_CONSTRUCTORS(LogMessage);
+  DISALLOW_COPY_AND_ASSIGN(LogMessage);
 };
 
 class LogMessageFatal : public LogMessage {
@@ -80,7 +80,7 @@ class LogMessageFatal : public LogMessage {
     abort();
   }
  private:
-  DISALLOW_EVIL_CONSTRUCTORS(LogMessageFatal);
+  DISALLOW_COPY_AND_ASSIGN(LogMessageFatal);
 };
 
 #endif  // RE2_UTIL_LOGGING_H__
diff --git a/util/mutex.h b/util/mutex.h
index 9787bfb..4a8de4c 100644
--- a/util/mutex.h
+++ b/util/mutex.h
@@ -10,6 +10,8 @@
 #ifndef RE2_UTIL_MUTEX_H_
 #define RE2_UTIL_MUTEX_H_
 
+#include <stdlib.h>
+
 namespace re2 {
 
 #define HAVE_PTHREAD 1
@@ -102,7 +104,6 @@ void Mutex::ReaderUnlock() { assert(mutex_-- > 0); }
 
 #elif defined(HAVE_PTHREAD) && defined(HAVE_RWLOCK)
 
-#include <stdlib.h>      // for abort()
 #define SAFE_PTHREAD(fncall)  do { if ((fncall) != 0) abort(); } while (0)
 
 Mutex::Mutex()             { SAFE_PTHREAD(pthread_rwlock_init(&mutex_, NULL)); }
@@ -117,7 +118,6 @@ void Mutex::ReaderUnlock() { SAFE_PTHREAD(pthread_rwlock_unlock(&mutex_)); }
 
 #elif defined(HAVE_PTHREAD)
 
-#include <stdlib.h>      // for abort()
 #define SAFE_PTHREAD(fncall)  do { if ((fncall) != 0) abort(); } while (0)
 
 Mutex::Mutex()             { SAFE_PTHREAD(pthread_mutex_init(&mutex_, NULL)); }
diff --git a/util/pcre.cc b/util/pcre.cc
index 5e67e1f..db3282f 100644
--- a/util/pcre.cc
+++ b/util/pcre.cc
@@ -347,7 +347,7 @@ int PCRE::GlobalReplace(string *str,
   int count = 0;
   int vec[kVecSize];
   string out;
-  int start = 0;
+  size_t start = 0;
   bool last_match_was_empty_string = false;
 
   for (; start <= str->length();) {
@@ -377,7 +377,7 @@ int PCRE::GlobalReplace(string *str,
       if (matches <= 0)
         break;
     }
-    int matchstart = vec[0], matchend = vec[1];
+    size_t matchstart = vec[0], matchend = vec[1];
     assert(matchstart >= start);
     assert(matchend >= matchstart);
 
diff --git a/util/pcre.h b/util/pcre.h
index 4dda95d..f8b4a1e 100644
--- a/util/pcre.h
+++ b/util/pcre.h
@@ -510,7 +510,7 @@ class PCRE {
   int               match_limit_;    // Limit on execution resources
   int               stack_limit_;    // Limit on stack resources (bytes)
   mutable int32_t  hit_limit_;  // Hit limit during execution (bool)?
-  DISALLOW_EVIL_CONSTRUCTORS(PCRE);
+  DISALLOW_COPY_AND_ASSIGN(PCRE);
 };
 
 // PCRE_Options allow you to set the PCRE::Options, plus any pcre
diff --git a/util/sparse_array.h b/util/sparse_array.h
index 3e33f89..8bc243b 100644
--- a/util/sparse_array.h
+++ b/util/sparse_array.h
@@ -226,7 +226,7 @@ class SparseArray {
   vector<IndexValue> dense_;
   bool valgrind_;
 
-  DISALLOW_EVIL_CONSTRUCTORS(SparseArray);
+  DISALLOW_COPY_AND_ASSIGN(SparseArray);
 };
 
 template<typename Value>
@@ -294,7 +294,7 @@ template<typename Value>
 bool SparseArray<Value>::has_index(int i) const {
   DCHECK_GE(i, 0);
   DCHECK_LT(i, max_size_);
-  if (static_cast<uint>(i) >= max_size_) {
+  if (static_cast<uint>(i) >= static_cast<uint>(max_size_)) {
     return false;
   }
   // Unsigned comparison avoids checking sparse_to_dense_[i] < 0.
@@ -306,7 +306,7 @@ bool SparseArray<Value>::has_index(int i) const {
 template<typename Value>
 typename SparseArray<Value>::iterator SparseArray<Value>::set(int i, Value v) {
   DebugCheckInvariants();
-  if (static_cast<uint>(i) >= max_size_) {
+  if (static_cast<uint>(i) >= static_cast<uint>(max_size_)) {
     // Semantically, end() would be better here, but we already know
     // the user did something stupid, so begin() insulates them from
     // dereferencing an invalid pointer.
@@ -368,7 +368,7 @@ template<typename Value>
 typename SparseArray<Value>::iterator
 SparseArray<Value>::set_new(int i, Value v) {
   DebugCheckInvariants();
-  if (static_cast<uint>(i) >= max_size_) {
+  if (static_cast<uint>(i) >= static_cast<uint>(max_size_)) {
     // Semantically, end() would be better here, but we already know
     // the user did something stupid, so begin() insulates them from
     // dereferencing an invalid pointer.
diff --git a/util/sparse_array_test.cc b/util/sparse_array_test.cc
deleted file mode 100644
index bc7a19f..0000000
--- a/util/sparse_array_test.cc
+++ /dev/null
@@ -1,150 +0,0 @@
-// Copyright 2006 The RE2 Authors.  All Rights Reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// Simple tests that SparseArray behaves.
-
-#include "util/util.h"
-#include "utest/utest.h"
-
-namespace re2 {
-
-static const string kNotFound = "NOT FOUND";
-
-TEST(SparseArray, BasicOperations) {
-  static const int n = 50;
-  SparseArray<int> set(n);
-
-  int order[n];
-  int value[n];
-  for (int i = 0; i < n; i++)
-    order[i] = i;
-  for (int i = 0; i < n; i++)
-    value[i] = rand()%1000 + 1;
-  for (int i = 1; i < n; i++) {
-    int j = rand()%i;
-    int t = order[i];
-    order[i] = order[j];
-    order[j] = t;
-  }
-
-  for (int i = 0;; i++) {
-    for (int j = 0; j < i; j++) {
-      ASSERT_TRUE(set.has_index(order[j]));
-      ASSERT_EQ(value[order[j]], set.get(order[j], -1));
-    }
-    if (i >= n)
-      break;
-    for (int j = i; j < n; j++)
-      ASSERT_FALSE(set.has_index(order[j]));
-    set.set(order[i], value[order[i]]);
-  }
-
-  int nn = 0;
-  for (SparseArray<int>::iterator i = set.begin(); i != set.end(); ++i) {
-    ASSERT_EQ(order[nn++], i->index());
-    ASSERT_EQ(value[i->index()], i->value());
-  }
-  ASSERT_EQ(nn, n);
-
-  set.clear();
-  for (int i = 0; i < n; i++)
-    ASSERT_FALSE(set.has_index(i));
-
-  ASSERT_EQ(0, set.size());
-  ASSERT_EQ(0, distance(set.begin(), set.end()));
-}
-
-class SparseArrayStringTest : public testing::Test {
- protected:
-  SparseArrayStringTest()
-      : str_map_(10) {
-    InsertOrUpdate(&str_map_, 1, "a");
-    InsertOrUpdate(&str_map_, 5, "b");
-    InsertOrUpdate(&str_map_, 2, "c");
-    InsertOrUpdate(&str_map_, 7, "d");
-  }
-
-  SparseArray<string> str_map_;
-  typedef SparseArray<string>::iterator iterator;
-};
-
-TEST_F(SparseArrayStringTest, FindGetsPresentElement) {
-  iterator it = str_map_.find(2);
-  ASSERT_TRUE(str_map_.end() != it);
-  EXPECT_EQ("c", it->second);
-}
-
-TEST_F(SparseArrayStringTest, FindDoesNotFindAbsentElement) {
-  iterator it = str_map_.find(3);
-  ASSERT_TRUE(str_map_.end() == it);
-}
-
-TEST_F(SparseArrayStringTest, ContainsKey) {
-  EXPECT_TRUE(ContainsKey(str_map_, 1));
-  EXPECT_TRUE(ContainsKey(str_map_, 2));
-  EXPECT_FALSE(ContainsKey(str_map_, 3));
-}
-
-TEST_F(SparseArrayStringTest, InsertIfNotPresent) {
-  EXPECT_FALSE(ContainsKey(str_map_, 3));
-  EXPECT_TRUE(InsertIfNotPresent(&str_map_, 3, "r"));
-  EXPECT_EQ("r", FindWithDefault(str_map_, 3, kNotFound));
-  EXPECT_FALSE(InsertIfNotPresent(&str_map_, 3, "other value"));
-  EXPECT_EQ("r", FindWithDefault(str_map_, 3, kNotFound));
-}
-
-TEST(SparseArrayTest, Erase) {
-  SparseArray<string> str_map(5);
-  str_map.set(1, "a");
-  str_map.set(2, "b");
-  EXPECT_EQ("a", FindWithDefault(str_map, 1, kNotFound));
-  EXPECT_EQ("b", FindWithDefault(str_map, 2, kNotFound));
-  str_map.erase(1);
-  EXPECT_EQ("NOT FOUND", FindWithDefault(str_map, 1, kNotFound));
-  EXPECT_EQ("b", FindWithDefault(str_map, 2, kNotFound));
-}
-
-typedef SparseArrayStringTest SparseArrayStringSurvivesInvalidIndexTest;
-// TODO(jyasskin): Cover invalid arguments to every method.
-
-TEST_F(SparseArrayStringSurvivesInvalidIndexTest, SetNegative) {
-  EXPECT_DEBUG_DEATH(str_map_.set(-123456789, "hi"),
-                     "\\(jyasskin\\) Illegal index -123456789 passed to"
-                     " SparseArray\\(10\\).set\\(\\).");
-  EXPECT_EQ(4, str_map_.size());
-}
-
-TEST_F(SparseArrayStringSurvivesInvalidIndexTest, SetTooBig) {
-  EXPECT_DEBUG_DEATH(str_map_.set(12345678, "hi"),
-                     "\\(jyasskin\\) Illegal index 12345678 passed to"
-                     " SparseArray\\(10\\).set\\(\\).");
-  EXPECT_EQ(4, str_map_.size());
-}
-
-TEST_F(SparseArrayStringSurvivesInvalidIndexTest, SetNew_Negative) {
-  EXPECT_DEBUG_DEATH(str_map_.set_new(-123456789, "hi"),
-                     "\\(jyasskin\\) Illegal index -123456789 passed to"
-                     " SparseArray\\(10\\).set_new\\(\\).");
-  EXPECT_EQ(4, str_map_.size());
-}
-
-TEST_F(SparseArrayStringSurvivesInvalidIndexTest, SetNew_Existing) {
-  EXPECT_DEBUG_DEATH({
-    str_map_.set_new(2, "hi");
-    EXPECT_EQ("hi", FindWithDefault(str_map_, 2, kNotFound));
-
-    // The old value for 2 is still present, but can never be removed.
-    // This risks crashing later, if the map fills up.
-    EXPECT_EQ(5, str_map_.size());
-  }, "Check failed: !has_index\\(i\\)");
-}
-
-TEST_F(SparseArrayStringSurvivesInvalidIndexTest, SetNew_TooBig) {
-  EXPECT_DEBUG_DEATH(str_map_.set_new(12345678, "hi"),
-                     "\\(jyasskin\\) Illegal index 12345678 passed to"
-                     " SparseArray\\(10\\).set_new\\(\\).");
-  EXPECT_EQ(4, str_map_.size());
-}
-
-}  // namespace re2
diff --git a/util/sparse_set.h b/util/sparse_set.h
index 165dd09..ff592a8 100644
--- a/util/sparse_set.h
+++ b/util/sparse_set.h
@@ -51,19 +51,28 @@
 
 namespace re2 {
 
+static bool InitMemory() {
+#ifdef MEMORY_SANITIZER
+  return true;
+#else
+  return RunningOnValgrind();
+#endif
+}
+
 class SparseSet {
  public:
   SparseSet()
-    : size_(0), max_size_(0), sparse_to_dense_(NULL), dense_(NULL), valgrind_(RunningOnValgrind()) {}
+    : size_(0), max_size_(0), sparse_to_dense_(NULL), dense_(NULL),
+      init_memory_(InitMemory()) {}
 
   SparseSet(int max_size) {
     max_size_ = max_size;
     sparse_to_dense_ = new int[max_size];
     dense_ = new int[max_size];
-    valgrind_ = RunningOnValgrind();
+    init_memory_ = InitMemory();
     // Don't need to zero the memory, but do so anyway
     // to appease Valgrind.
-    if (valgrind_) {
+    if (init_memory_) {
       for (int i = 0; i < max_size; i++) {
         dense_[i] = 0xababababU;
         sparse_to_dense_[i] = 0xababababU;
@@ -95,7 +104,7 @@ class SparseSet {
       int* a = new int[new_max_size];
       if (sparse_to_dense_) {
         memmove(a, sparse_to_dense_, max_size_*sizeof a[0]);
-        if (valgrind_) {
+        if (init_memory_) {
           for (int i = max_size_; i < new_max_size; i++)
             a[i] = 0xababababU;
         }
@@ -106,7 +115,7 @@ class SparseSet {
       a = new int[new_max_size];
       if (dense_) {
         memmove(a, dense_, size_*sizeof a[0]);
-        if (valgrind_) {
+        if (init_memory_) {
           for (int i = size_; i < new_max_size; i++)
             a[i] = 0xababababU;
         }
@@ -128,7 +137,7 @@ class SparseSet {
   bool contains(int i) const {
     DCHECK_GE(i, 0);
     DCHECK_LT(i, max_size_);
-    if (static_cast<uint>(i) >= max_size_) {
+    if (static_cast<uint>(i) >= static_cast<uint>(max_size_)) {
       return false;
     }
     // Unsigned comparison avoids checking sparse_to_dense_[i] < 0.
@@ -145,7 +154,7 @@ class SparseSet {
   // Set the value at the new index i to v.
   // Fast but unsafe: only use if contains(i) is false.
   void insert_new(int i) {
-    if (static_cast<uint>(i) >= max_size_) {
+    if (static_cast<uint>(i) >= static_cast<uint>(max_size_)) {
       // Semantically, end() would be better here, but we already know
       // the user did something stupid, so begin() insulates them from
       // dereferencing an invalid pointer.
@@ -169,9 +178,9 @@ class SparseSet {
   int max_size_;
   int* sparse_to_dense_;
   int* dense_;
-  bool valgrind_;
+  bool init_memory_;
 
-  DISALLOW_EVIL_CONSTRUCTORS(SparseSet);
+  DISALLOW_COPY_AND_ASSIGN(SparseSet);
 };
 
 }  // namespace re2
diff --git a/util/stringpiece.cc b/util/stringpiece.cc
deleted file mode 100644
index 37895b0..0000000
--- a/util/stringpiece.cc
+++ /dev/null
@@ -1,87 +0,0 @@
-// Copyright 2004 The RE2 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 "re2/stringpiece.h"
-#include "util/util.h"
-
-using re2::StringPiece;
-
-std::ostream& operator<<(std::ostream& o, const StringPiece& piece) {
-  o.write(piece.data(), piece.size());
-  return o;
-}
-
-bool StringPiece::_equal(const StringPiece& x, const StringPiece& y) {
-  int len = x.size();
-  if (len != y.size()) {
-    return false;
-  }
-  const char* p = x.data();
-  const char* p2 = y.data();
-  // Test last byte in case strings share large common prefix
-  if ((len > 0) && (p[len-1] != p2[len-1])) return false;
-  const char* p_limit = p + len;
-  for (; p < p_limit; p++, p2++) {
-    if (*p != *p2)
-      return false;
-  }
-  return true;
-}
-
-void StringPiece::CopyToString(string* target) const {
-  target->assign(ptr_, length_);
-}
-
-int StringPiece::copy(char* buf, size_type n, size_type pos) const {
-  int ret = min(length_ - pos, n);
-  memcpy(buf, ptr_ + pos, ret);
-  return ret;
-}
-
-int StringPiece::find(const StringPiece& s, size_type pos) const {
-  if (length_ < 0 || pos > static_cast<size_type>(length_))
-    return npos;
-
-  const char* result = std::search(ptr_ + pos, ptr_ + length_,
-                                   s.ptr_, s.ptr_ + s.length_);
-  const size_type xpos = result - ptr_;
-  return xpos + s.length_ <= length_ ? xpos : npos;
-}
-
-int StringPiece::find(char c, size_type pos) const {
-  if (length_ <= 0 || pos >= static_cast<size_type>(length_)) {
-    return npos;
-  }
-  const char* result = std::find(ptr_ + pos, ptr_ + length_, c);
-  return result != ptr_ + length_ ? result - ptr_ : npos;
-}
-
-int StringPiece::rfind(const StringPiece& s, size_type pos) const {
-  if (length_ < s.length_) return npos;
-  const size_t ulen = length_;
-  if (s.length_ == 0) return min(ulen, pos);
-
-  const char* last = ptr_ + min(ulen - s.length_, pos) + s.length_;
-  const char* result = std::find_end(ptr_, last, s.ptr_, s.ptr_ + s.length_);
-  return result != last ? result - ptr_ : npos;
-}
-
-int StringPiece::rfind(char c, size_type pos) const {
-  if (length_ <= 0) return npos;
-  for (int i = min(pos, static_cast<size_type>(length_ - 1));
-       i >= 0; --i) {
-    if (ptr_[i] == c) {
-      return i;
-    }
-  }
-  return npos;
-}
-
-StringPiece StringPiece::substr(size_type pos, size_type n) const {
-  if (pos > length_) pos = length_;
-  if (n > length_ - pos) n = length_ - pos;
-  return StringPiece(ptr_ + pos, n);
-}
-
-const StringPiece::size_type StringPiece::npos = size_type(-1);
diff --git a/util/stringprintf.cc b/util/stringprintf.cc
index c908181..79ba7fc 100644
--- a/util/stringprintf.cc
+++ b/util/stringprintf.cc
@@ -18,7 +18,7 @@ static void StringAppendV(string* dst, const char* format, va_list ap) {
   int result = vsnprintf(space, sizeof(space), format, backup_ap);
   va_end(backup_ap);
 
-  if ((result >= 0) && (result < sizeof(space))) {
+  if ((result >= 0) && (static_cast<unsigned long>(result) < sizeof(space))) {
     // It fit
     dst->append(space, result);
     return;
diff --git a/util/strutil.cc b/util/strutil.cc
index 6ab79b3..f6ac644 100644
--- a/util/strutil.cc
+++ b/util/strutil.cc
@@ -20,7 +20,7 @@ int CEscapeString(const char* src, int src_len, char* dest,
   int used = 0;
 
   for (; src < src_end; src++) {
-    if (dest_len - used < 2)   // Need space for two letter escape
+    if (dest_len - used < 2)   // space for two-character escape
       return -1;
 
     unsigned char c = *src;
@@ -36,7 +36,7 @@ int CEscapeString(const char* src, int src_len, char* dest,
         // digit then that digit must be escaped too to prevent it being
         // interpreted as part of the character code by C.
         if (c < ' ' || c > '~') {
-          if (dest_len - used < 4) // need space for 4 letter escape
+          if (dest_len - used < 5)   // space for four-character escape + \0
             return -1;
           sprintf(dest + used, "\\%03o", c);
           used += 4;
@@ -57,7 +57,7 @@ int CEscapeString(const char* src, int src_len, char* dest,
 // ----------------------------------------------------------------------
 // CEscape()
 //    Copies 'src' to result, escaping dangerous characters using
-//    C-style escape sequences.  'src' and 'dest' should not overlap. 
+//    C-style escape sequences.  'src' and 'dest' should not overlap.
 // ----------------------------------------------------------------------
 string CEscape(const StringPiece& src) {
   const int dest_length = src.size() * 4 + 1; // Maximum possible expansion
diff --git a/util/test.cc b/util/test.cc
index 0644829..220bfb0 100644
--- a/util/test.cc
+++ b/util/test.cc
@@ -3,7 +3,9 @@
 // license that can be found in the LICENSE file.
 
 #include <stdio.h>
+#ifndef WIN32
 #include <sys/resource.h>
+#endif
 #include "util/test.h"
 
 DEFINE_string(test_tmpdir, "/var/tmp", "temp directory");
@@ -23,9 +25,13 @@ void RegisterTest(void (*fn)(void), const char *name) {
 
 namespace re2 {
 int64 VirtualProcessSize() {
+#ifdef WIN32
+  return 0;
+#else
   struct rusage ru;
   getrusage(RUSAGE_SELF, &ru);
   return (int64)ru.ru_maxrss*1024;
+#endif
 }
 }  // namespace re2
 
diff --git a/util/test.h b/util/test.h
index 0f93865..d48fef0 100644
--- a/util/test.h
+++ b/util/test.h
@@ -31,8 +31,6 @@ class TestRegisterer {
 #define EXPECT_GE CHECK_GE
 #define EXPECT_FALSE(x) CHECK(!(x))
 
-#define ARRAYSIZE arraysize
-
 #define EXPECT_TRUE_M(x, y) CHECK(x) << (y)
 #define EXPECT_FALSE_M(x, y) CHECK(!(x)) << (y)
 #define ASSERT_TRUE_M(x, y) CHECK(x) << (y)
diff --git a/util/threadwin.cc b/util/threadwin.cc
new file mode 100644
index 0000000..f1e456e
--- /dev/null
+++ b/util/threadwin.cc
@@ -0,0 +1,49 @@
+// Copyright 2009 The RE2 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 <windows.h>
+
+#include "util/util.h"
+#include "util/thread.h"
+
+Thread::Thread() {
+  pid_ = 0;
+  running_ = 0;
+  joinable_ = 0;
+}
+
+Thread::~Thread() {
+}
+
+DWORD WINAPI startThread(void *v) {
+  Thread* t = (Thread*)v;
+  t->Run();
+  return 0;
+}
+
+void Thread::Start() {
+  CHECK(!running_);
+  pid_ = CreateThread(NULL, 0, startThread, this, 0, NULL);
+  running_ = true;
+  if (!joinable_)
+  {
+    CloseHandle(pid_);
+    pid_ = 0;
+  }
+}
+
+void Thread::Join() {
+  CHECK(running_);
+  CHECK(joinable_);
+  if (0 != pid_)
+  {
+      WaitForSingleObject(pid_, INFINITE);
+  }
+  running_ = 0;
+}
+
+void Thread::SetJoinable(bool j) {
+  CHECK(!running_);
+  joinable_ = j;
+}
diff --git a/util/util.h b/util/util.h
index 471c64f..250ee93 100644
--- a/util/util.h
+++ b/util/util.h
@@ -12,11 +12,15 @@
 #include <stddef.h>         // For size_t
 #include <assert.h>
 #include <stdarg.h>
-#include <sys/time.h>
 #include <time.h>
 #include <ctype.h>	// For isdigit, isalpha.
 
+#if !defined(WIN32)
+#include <sys/time.h>  // For gettimeofday
+#endif
+
 // C++
+#include <ctime>
 #include <vector>
 #include <string>
 #include <algorithm>
@@ -41,7 +45,7 @@ using std::sort;
 using std::swap;
 using std::make_pair;
 
-#if defined(__GNUC__) && !defined(USE_CXX0X)
+#if defined(__GNUC__) && !defined(USE_CXX0X) && !defined(_LIBCPP_ABI_VERSION) && !defined(OS_ANDROID)
 
 #include <tr1/unordered_set>
 using std::tr1::unordered_set;
@@ -49,7 +53,27 @@ using std::tr1::unordered_set;
 #else
 
 #include <unordered_set>
+#if defined(WIN32) || defined(OS_ANDROID)
+using std::tr1::unordered_set;
+#else
 using std::unordered_set;
+#endif
+
+#endif
+
+#ifdef WIN32
+
+#define snprintf _snprintf_s
+#define sprintf sprintf_s
+#define stricmp _stricmp
+#define strtof strtod /* not really correct but best we can do */
+#define strtoll _strtoi64
+#define strtoull _strtoui64
+#define vsnprintf vsnprintf_s
+
+#pragma warning(disable: 4018) // signed/unsigned mismatch
+#pragma warning(disable: 4244) // possible data loss in int conversion
+#pragma warning(disable: 4800) // conversion from int to bool
 
 #endif
 
@@ -69,30 +93,21 @@ typedef unsigned int uint;
 typedef unsigned short ushort;
 
 // COMPILE_ASSERT causes a compile error about msg if expr is not true.
+#if __cplusplus >= 201103L
+#define COMPILE_ASSERT(expr, msg) static_assert(expr, #msg)
+#else
 template<bool> struct CompileAssert {};
 #define COMPILE_ASSERT(expr, msg) \
   typedef CompileAssert<(bool(expr))> msg[bool(expr) ? 1 : -1]
+#endif
 
-// DISALLOW_EVIL_CONSTRUCTORS disallows the copy and operator= functions.
+// DISALLOW_COPY_AND_ASSIGN disallows the copy and operator= functions.
 // It goes in the private: declarations in a class.
-#define DISALLOW_EVIL_CONSTRUCTORS(TypeName) \
+#define DISALLOW_COPY_AND_ASSIGN(TypeName) \
   TypeName(const TypeName&);                 \
   void operator=(const TypeName&)
 
-#define arraysize(array) (sizeof(array)/sizeof((array)[0]))
-
-// Fake lock annotations.  For real ones, see
-// http://code.google.com/p/data-race-test/
-#ifndef ANNOTATE_PUBLISH_MEMORY_RANGE
-#define ANNOTATE_PUBLISH_MEMORY_RANGE(a, b)
-#define ANNOTATE_IGNORE_WRITES_BEGIN()
-#define ANNOTATE_IGNORE_WRITES_END()
-#define ANNOTATE_BENIGN_RACE(a, b)
-#define NO_THREAD_SAFETY_ANALYSIS
-#define ANNOTATE_HAPPENS_BEFORE(x)
-#define ANNOTATE_HAPPENS_AFTER(x)
-#define ANNOTATE_UNPROTECTED_READ(x) (x)
-#endif
+#define arraysize(array) (int)(sizeof(array)/sizeof((array)[0]))
 
 class StringPiece;
 
@@ -123,7 +138,6 @@ int RunningOnValgrind();
 
 }  // namespace re2
 
-#include "util/arena.h"
 #include "util/logging.h"
 #include "util/mutex.h"
 #include "util/utf.h"
diff --git a/util/valgrind.cc b/util/valgrind.cc
index 46f804b..ee257d0 100644
--- a/util/valgrind.cc
+++ b/util/valgrind.cc
@@ -3,12 +3,20 @@
 // license that can be found in the LICENSE file.
 
 #include "util/util.h"
+#ifndef WIN32
 #include "util/valgrind.h"
+#endif
 
 namespace re2 {
 
+#ifndef __has_feature
+#define __has_feature(x) 0
+#endif
+
 int RunningOnValgrind() {
-#ifdef RUNNING_ON_VALGRIND
+#if __has_feature(memory_sanitizer)
+	return true;
+#elif defined(RUNNING_ON_VALGRIND)
 	return RUNNING_ON_VALGRIND;
 #else
 	return 0;