Home | History | Annotate | Download | only in third_party 
      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_
     82