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

courgette/memory_allocator.h

 // Copyright (c) 2011 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.
 
 #ifndef COURGETTE_MEMORY_ALLOCATOR_H_
 #define COURGETTE_MEMORY_ALLOCATOR_H_
 
 #include <memory>
 
 #include "base/basictypes.h"
@@ skipping 48 matching lines @@
 
 // Manages a temporary file.  The file is created in the %TEMP% folder and
 // is deleted when the file handle is closed.
 // NOTE: Since the file will be used as backing for a memory allocation,
 // it will never be so big that size_t cannot represent its size.
 class TempFile {
  public:
   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;
 
   // Returns the handle of the temporary file or INVALID_HANDLE_VALUE if
   // 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.
 class FileMapping {
  public:
   FileMapping();
   ~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.
   bool valid() const;
 
   // Returns a writable pointer to the beginning of the memory mapped file.
   // If Create has not been called successfully, return value is NULL.
   void* view() const;
 
  protected:
-  __declspec(noinline) void InitializeView(size_t size);
+  bool InitializeView(size_t size);
 
   HANDLE mapping_;
   void* view_;
 };
 
 // Manages a temporary file and a memory mapping of the temporary file.
 // The memory that this class manages holds a pointer back to the TempMapping
 // object itself, so that given a memory pointer allocated by this class,
 // you can get a pointer to the TempMapping instance that owns that memory.
 class TempMapping {
  public:
   TempMapping();
   ~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.
   static TempMapping* GetMappingFromPtr(void* mem);
 
  protected:
   TempFile file_;
   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
 // already committed to other processes.  Provided there is enough disk, the
 // temporary file acts like a pagefile that other processes can't access.
 template<class T>
 class MemoryAllocator {
  public:
   typedef T value_type;
   typedef value_type* pointer;
@@ skipping 12 matching lines @@
 
   // 5MB is the maximum heap allocation size that we'll attempt.
   // When applying a patch for Chrome 10.X we found that at this
   // threshold there were 17 allocations higher than this threshold
   // (largest at 136MB) 10 allocations just below the threshold and 6362
   // smaller allocations.
   static const size_t kMaxHeapAllocationSize = 1024 * 1024 * 5;
 
   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;
   };
 
   MemoryAllocator() _THROW0() {
   }
 
   // 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() {
   }
 
   void deallocate(pointer ptr, size_type size) {
     uint8* mem = reinterpret_cast<uint8*>(ptr);
     mem -= sizeof(T);
     if (mem[0] == HEAP_ALLOCATION) {
       delete [] mem;
     } else {
       DCHECK_EQ(static_cast<uint8>(FILE_ALLOCATION), mem[0]);
       TempMapping* mapping = TempMapping::GetMappingFromPtr(mem);
       delete mapping;
     }
   }
 
   pointer allocate(size_type count) {
     // We use the first byte of each allocation to mark the allocation type.
     // However, so that the allocation is properly aligned, we allocate an
     // extra element and then use the first byte of the first element
     // to mark the allocation type.
     count++;
 
     if (count > max_size())
-      throw std::length_error("overflow");
+      return NULL;
 
     size_type bytes = count * sizeof(T);
     uint8* mem = NULL;
 
     // First see if we can do this allocation on the heap.
     if (count < kMaxHeapAllocationSize)
       mem = new(std::nothrow) uint8[bytes];
     if (mem != NULL) {
       mem[0] = static_cast<uint8>(HEAP_ALLOCATION);
     } 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) {
     return allocate(count);
   }
 
   void construct(pointer ptr, const T& value) {
     ::new(ptr) T(value);
   }
 
   void destroy(pointer ptr) {
     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);
   }
 };
 
 #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_