Switch out use of std::string and std::vector for large allocations for a buffer class that doesn...

courgette/memory_allocator.h

Index: courgette/memory_allocator.h
===================================================================
--- courgette/memory_allocator.h	(revision 80344)
+++ courgette/memory_allocator.h	(working copy)
@@ -66,9 +66,9 @@
   TempFile();
   ~TempFile();
 
-  __declspec(noinline) void Create();
+  bool Create();
   void Close();
-  __declspec(noinline) void SetSize(size_t size);
+  bool SetSize(size_t size);
 
   // Returns true iff the temp file is currently open.
   bool valid() const;
@@ -77,15 +77,8 @@
   // a temp file has not been created.
   base::PlatformFile handle() const;
 
-  // Returns the size of the temp file.  If the temp file doesn't exist,
-  // the return value is 0.
-  size_t size() const;
-
  protected:
-  __declspec(noinline) FilePath PrepareTempFile();
-
   base::PlatformFile file_;
-  size_t size_;
 };
 
 // Manages a read/write virtual mapping of a physical file.
@@ -95,7 +88,7 @@
   ~FileMapping();
 
   // Map a file from beginning to |size|.
-  __declspec(noinline) void Create(HANDLE file, size_t size);
+  bool Create(HANDLE file, size_t size);
   void Close();
 
   // Returns true iff a mapping has been created.
@@ -106,7 +99,7 @@
   void* view() const;
 
  protected:
-  __declspec(noinline) void InitializeView(size_t size);
+  bool InitializeView(size_t size);
 
   HANDLE mapping_;
   void* view_;
@@ -122,12 +115,15 @@
   ~TempMapping();
 
   // Creates a temporary file of size |size| and maps it into the current
-  // process' address space.
-  __declspec(noinline) void Initialize(size_t size);
+  // process's address space.
+  bool Initialize(size_t size);
 
   // Returns a writable pointer to the reserved memory.
   void* memory() const;
 
+  // Returns true if the mapping is valid and memory is available.
+  bool valid() const;
+
   // Returns a pointer to the TempMapping instance that allocated the |mem|
   // block of memory.  It's the callers responsibility to make sure that
   // the memory block was allocated by the TempMapping class.
@@ -138,10 +134,11 @@
   FileMapping mapping_;
 };
 
-// An STL compatible memory allocator class that allocates memory either
-// from the heap or via a temporary file.  A file allocation will be made
-// if either the requested memory size exceeds |kMaxHeapAllocationSize|
-// or if a heap allocation fails.
+// A memory allocator class that allocates memory either from the heap or via a
+// temporary file.  The interface is STL inspired but the class does not throw
+// STL exceptions on allocation failure.  Instead it returns NULL.
+// A file allocation will be made if either the requested memory size exceeds
+// |kMaxHeapAllocationSize| or if a heap allocation fails.
 // Allocating the memory as a mapping of a temporary file solves the problem
 // that there might not be enough physical memory and pagefile to support the
 // allocation.  This can happen because these resources are too small, or
@@ -174,7 +171,7 @@
 
   template<class OtherT>
   struct rebind {
-    // convert an MemoryAllocator<T> to a MemoryAllocator<OtherT>
+    // convert a MemoryAllocator<T> to a MemoryAllocator<OtherT>
     typedef MemoryAllocator<OtherT> other;
   };
 
@@ -183,11 +180,11 @@
 
   // We can't use an explicit constructor here, as dictated by our style guide.
   // The implementation of basic_string in Visual Studio 2010 prevents this.
-  MemoryAllocator(const MemoryAllocator<T>& other) _THROW0() {
+  MemoryAllocator(const MemoryAllocator<T>& other) _THROW0() {  // NOLINT
   }
 
   template<class OtherT>
-  explicit MemoryAllocator(const MemoryAllocator<OtherT>& other) _THROW0() {
+  MemoryAllocator(const MemoryAllocator<OtherT>& other) _THROW0() {  // NOLINT
   }
 
   ~MemoryAllocator() {
@@ -213,7 +210,7 @@
     count++;
 
     if (count > max_size())
-      throw std::length_error("overflow");
+      return NULL;
 
     size_type bytes = count * sizeof(T);
     uint8* mem = NULL;
@@ -226,12 +223,13 @@
     } else {
       // If either the heap allocation failed or the request exceeds the
       // max heap allocation threshold, we back the allocation with a temp file.
-      TempMapping* mapping = new TempMapping();
-      mapping->Initialize(bytes);
-      mem = reinterpret_cast<uint8*>(mapping->memory());
-      mem[0] = static_cast<uint8>(FILE_ALLOCATION);
+      TempMapping* mapping = new(std::nothrow) TempMapping();
+      if (mapping && mapping->Initialize(bytes)) {
+        mem = reinterpret_cast<uint8*>(mapping->memory());
+        mem[0] = static_cast<uint8>(FILE_ALLOCATION);
+      }
     }
-    return reinterpret_cast<pointer>(mem + sizeof(T));
+    return mem ? reinterpret_cast<pointer>(mem + sizeof(T)) : NULL;
   }
 
   pointer allocate(size_type count, const void* hint) {
@@ -246,7 +244,7 @@
     ptr->~T();
   }
 
-  size_t max_size() const _THROW0() {
+  size_type max_size() const _THROW0() {
     size_type count = static_cast<size_type>(-1) / sizeof(T);
     return (0 < count ? count : 1);
   }
@@ -254,14 +252,239 @@
 
 #else  // OS_WIN
 
-// On Mac, Linux, we just use the default STL allocator.
+// On Mac, Linux, we use a bare bones implementation that only does
+// heap allocations.
 template<class T>
-class MemoryAllocator : public std::allocator<T> {
+class MemoryAllocator {
  public:
+  typedef T value_type;
+  typedef value_type* pointer;
+  typedef value_type& reference;
+  typedef const value_type* const_pointer;
+  typedef const value_type& const_reference;
+  typedef size_t size_type;
+  typedef ptrdiff_t difference_type;
+
+  template<class OtherT>
+  struct rebind {
+    // convert a MemoryAllocator<T> to a MemoryAllocator<OtherT>
+    typedef MemoryAllocator<OtherT> other;
+  };
+
+  MemoryAllocator() {
+  }
+
+  explicit MemoryAllocator(const MemoryAllocator<T>& other) {
+  }
+
+  template<class OtherT>
+  explicit MemoryAllocator(const MemoryAllocator<OtherT>& other) {
+  }
+
+  ~MemoryAllocator() {
+  }
+
+  void deallocate(pointer ptr, size_type size) {
+    delete [] ptr;
+  }
+
+  pointer allocate(size_type count) {
+    if (count > max_size())
+      return NULL;
+    return reinterpret_cast<pointer>(
+        new(std::nothrow) uint8[count * sizeof(T)]);
+  }
+
+  pointer allocate(size_type count, const void* hint) {
+    return allocate(count);
+  }
+
+  void construct(pointer ptr, const T& value) {
+    ::new(ptr) T(value);
+  }
+
+  void destroy(pointer ptr) {
+    ptr->~T();
+  }
+
+  size_type max_size() const {
+    size_type count = static_cast<size_type>(-1) / sizeof(T);
+    return (0 < count ? count : 1);
+  }
 };
 
 #endif  // OS_WIN
 
+// Manages a growable buffer.  The buffer allocation is done by the
+// MemoryAllocator class.  This class will not throw exceptions so call sites
+// must be prepared to handle memory allocation failures.
+// The interface is STL inspired to avoid having to make too many changes
+// to code that previously was using STL.
+template<typename T, class Allocator = MemoryAllocator<T> >
+class NoThrowBuffer {
+ public:
+  typedef T value_type;
+  static const size_t kAllocationFailure = 0xffffffff;
+  static const size_t kStartSize = sizeof(T) > 0x100 ? 1 : 0x100 / sizeof(T);
+
+  NoThrowBuffer() : buffer_(NULL), size_(0), alloc_size_(0) {
+  }
+
+  ~NoThrowBuffer() {
+    clear();
+  }
+
+  void clear() {
+    if (buffer_) {
+      alloc_.deallocate(buffer_, alloc_size_);
+      buffer_ = NULL;
+      size_ = 0;
+      alloc_size_ = 0;
+    }
+  }
+
+  bool empty() const {
+    return size_ == 0;
+  }
+
+  CheckBool reserve(size_t size) WARN_UNUSED_RESULT {
+    if (failed())
+      return false;
+
+    if (size <= alloc_size_)
+      return true;
+
+    if (size < kStartSize)
+      size = kStartSize;
+
+    T* new_buffer = alloc_.allocate(size);
+    if (!new_buffer) {
+      clear();
+      alloc_size_ = kAllocationFailure;
+    } else {
+      if (buffer_) {
+        memcpy(new_buffer, buffer_, size_ * sizeof(T));
+        alloc_.deallocate(buffer_, alloc_size_);
+      }
+      buffer_ = new_buffer;
+      alloc_size_ = size;
+    }
+
+    return !failed();
+  }
+
+  CheckBool append(const T* data, size_t size) WARN_UNUSED_RESULT {
+    if (failed())
+      return false;
+
+    if (size > alloc_.max_size() - size_)
+      return false;
+
+    if (!size)
+      return true;
+
+    if ((alloc_size_ - size_) < size) {
+      const size_t max_size = alloc_.max_size();
+      size_t new_size = alloc_size_ ? alloc_size_ : kStartSize;
+      while (new_size < size_ + size) {
+        if (new_size < max_size - new_size) {
+          new_size *= 2;
+        } else {
+          new_size = max_size;
+        }
+      }
+      if (!reserve(new_size))
+        return false;
+    }
+
+    memcpy(buffer_ + size_, data, size * sizeof(T));
+    size_ += size;
+
+    return true;
+  }
+
+  CheckBool resize(size_t size, const T& init_value) WARN_UNUSED_RESULT {
+    if (size > size_) {
+      if (!reserve(size))
+        return false;
+      for (size_t i = size_; i < size; ++i)
+        buffer_[i] = init_value;
+    } else if (size < size_) {
+      // TODO(tommi): Should we allocate a new, smaller buffer?
+      // It might be faster for us to simply change the size.
+    }
+
+    size_ = size;
+
+    return true;
+  }
+
+  CheckBool push_back(const T& item) WARN_UNUSED_RESULT {
+    return append(&item, 1);
+  }
+
+  const T& back() const {
+    return buffer_[size_ - 1];
+  }
+
+  T& back() {
+    return buffer_[size_ - 1];
+  }
+
+  const T* begin() const {
+    if (!size_)
+      return NULL;
+    return &buffer_[0];
+  }
+
+  T* begin() {
+    if (!size_)
+      return NULL;
+    return &buffer_[0];
+  }
+
+  const T* end() const {
+    if (!size_)
+      return NULL;
+    return &buffer_[size_ - 1];
+  }
+
+  T* end() {
+    if (!size_)
+      return NULL;
+    return &buffer_[size_ - 1];
+  }
+
+  const T& operator[](size_t index) const {
+    DCHECK(index < size_);
+    return buffer_[index];
+  }
+
+  T& operator[](size_t index) {
+    DCHECK(index < size_);
+    return buffer_[index];
+  }
+
+  size_t size() const {
+    return size_;
+  }
+
+  T* data() const {
+    return buffer_;
+  }
+
+  // Returns true if an allocation failure has ever occurred for this object.
+  bool failed() const {
+    return alloc_size_ == kAllocationFailure;
+  }
+
+ protected:
+  T* buffer_;
+  size_t size_;  // how much of the buffer we're using.
+  size_t alloc_size_;  // how much space we have allocated.
+  Allocator alloc_;
+};
+
 }  // namespace courgette
 
 #endif  // COURGETTE_MEMORY_ALLOCATOR_H_