courgette/third_party/paged_array.h

   1 // Copyright (c) 2010 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 // PagedArray implements an array stored using many fixed-size pages.
   6 //
   7 // PagedArray is a work-around to allow large arrays to be allocated when there
   8 // is too much address space fragmentation for allocating the large arrays as
   9 // contigous arrays.
  10 #ifndef COURGETTE_BSDIFF_PAGED_ARRAY_H_
  11 #define COURGETTE_BSDIFF_PAGED_ARRAY_H_
  12
  13 // For std::nothrow:
  14 #include <new>
  15
  16 #include "base/basictypes.h"
  17
  18 namespace courgette {
  19
  20 // PagedArray implements an array stored using many fixed-size pages.
  21 template<typename T>
  22 class PagedArray {
  23   enum {
  24     // Page size in elements.  Page size of 2^18 * sizeof(T) is 1MB for T = int.
  25     kLogPageSize = 18,
  26     kPageSize = 1 << kLogPageSize
  27   };
  28
  29  public:
  30   PagedArray() : pages_(NULL), page_count_(0) {}
  31
  32   ~PagedArray() { clear(); }
  33
  34   T& operator[](size_t i) {
  35     size_t page = i >> kLogPageSize;
  36     size_t offset = i & (kPageSize - 1);
  37     // It is tempting to add a DCHECK(page < page_count_), but that makes
  38     // bsdiff_create run 2x slower (even when compiled optimized.)
  39     return pages_[page][offset];
  40   }
  41
  42   // Allocates storage for |size| elements. Returns true on success and false if
  43   // allocation fails.
  44   bool Allocate(size_t size) {
  45     clear();
  46     size_t pages_needed = (size + kPageSize - 1) >> kLogPageSize;
  47     pages_ = new(std::nothrow) T*[pages_needed];
  48     if (pages_ == NULL)
  49       return false;
  50
  51     for (page_count_ = 0; page_count_ < pages_needed; ++page_count_) {
  52       T* block = new(std::nothrow) T[kPageSize];
  53       if (block == NULL) {
  54         clear();
  55         return false;
  56       }
  57       pages_[page_count_] = block;
  58     }
  59     return true;
  60   }
  61
  62   // Releases all storage.  May be called more than once.
  63   void clear() {
  64     if (pages_ != NULL) {
  65       while (page_count_ != 0) {
  66         --page_count_;
  67         delete[] pages_[page_count_];
  68       }
  69       delete[] pages_;
  70       pages_ = NULL;
  71     }
  72   }
  73
  74  private:
  75   T** pages_;
  76   size_t page_count_;
  77
  78   DISALLOW_COPY_AND_ASSIGN(PagedArray);
  79 };
  80 }  // namespace
  81 #endif  // COURGETTE_BSDIFF_PAGED_ARRAY_H_