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: PagedArray()30 PagedArray() : pages_(NULL), page_count_(0) {} 31 ~PagedArray()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. Allocate(size_t size)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. clear()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