Use an array of pages for the large arrays....

courgette/third_party/paged_array.h

Index: courgette/third_party/paged_array.h
===================================================================
--- courgette/third_party/paged_array.h	(revision 0)
+++ courgette/third_party/paged_array.h	(revision 0)
@@ -0,0 +1,81 @@
+// Copyright (c) 2010 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.
+
+// PagedArray implements an array stored using many fixed-size pages.
+//
+// PagedArray is a work-around to allow large arrays to be allocated when there
+// is too much address space fragmentation for allocating the large arrays as
+// contigous arrays.
+#ifndef COURGETTE_BSDIFF_PAGED_ARRAY_H_
+#define COURGETTE_BSDIFF_PAGED_ARRAY_H_
+
+// For std::nothrow:
+#include <new>
+
+#include "base/basictypes.h"
+
+namespace courgette {
+
+// PagedArray implements an array stored using many fixed-size pages.
+template<typename T>
+class PagedArray {
+  enum {
+    // Page size in elements.  Page size of 2^18 * sizeof(T) is 1MB for T = int.
+    kLogPageSize = 18,
+    kPageSize = 1 << kLogPageSize
+  };
+
+ public:
+  PagedArray() : pages_(NULL), page_count_(0) {}
+
+  ~PagedArray() { clear(); }
+
+  T& operator[](size_t i) {
+    size_t page = i >> kLogPageSize;
+    size_t offset = i & (kPageSize - 1);
+    // It is tempting to add a DCHECK(page < page_count_), but that makes
+    // bsdiff_create run 2x slower (even when compiled optimized.)
+    return pages_[page][offset];
+  }
+
+  // Allocates storage for |size| elements. Returns true on success and false if
+  // allocation fails.
+  bool Allocate(size_t size) {
+    clear();
+    size_t pages_needed = (size + kPageSize - 1) >> kLogPageSize;
+    pages_ = new(std::nothrow) T*[pages_needed];
+    if (pages_ == NULL)
+      return false;
+
+    for (page_count_ = 0; page_count_ < pages_needed; ++page_count_) {
+      T* block = new(std::nothrow) T[kPageSize];
+      if (block == NULL) {
+        clear();
+        return false;
+      }
+      pages_[page_count_] = block;
+    }
+    return true;
+  }
+
+  // Releases all storage.  May be called more than once.
+  void clear() {
+    if (pages_ != NULL) {
+      while (page_count_ != 0) {
+        --page_count_;
+        delete[] pages_[page_count_];
+      }
+      delete[] pages_;
+      pages_ = NULL;
+    }
+  }
+
+ private:
+  T** pages_;
+  size_t page_count_;
+
+  DISALLOW_COPY_AND_ASSIGN(PagedArray);
+};
+}  // namespace
+#endif  // COURGETTE_BSDIFF_PAGED_ARRAY_H_