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.
5 // PagedArray implements an array stored using many fixed-size pages.
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
10 #ifndef COURGETTE_BSDIFF_PAGED_ARRAY_H_
11 #define COURGETTE_BSDIFF_PAGED_ARRAY_H_
16 #include "base/basictypes.h"
20 // PagedArray implements an array stored using many fixed-size pages.
24 // Page size in elements. Page size of 2^18 * sizeof(T) is 1MB for T = int.
26 kPageSize = 1 << kLogPageSize
30 PagedArray() : pages_(NULL), page_count_(0) {}
32 ~PagedArray() { clear(); }
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];
42 // Allocates storage for |size| elements. Returns true on success and false if
44 bool Allocate(size_t size) {
46 size_t pages_needed = (size + kPageSize - 1) >> kLogPageSize;
47 pages_ = new(std::nothrow) T*[pages_needed];
51 for (page_count_ = 0; page_count_ < pages_needed; ++page_count_) {
52 T* block = new(std::nothrow) T[kPageSize];
57 pages_[page_count_] = block;
62 // Releases all storage. May be called more than once.
65 while (page_count_ != 0) {
67 delete[] pages_[page_count_];
78 DISALLOW_COPY_AND_ASSIGN(PagedArray);
81 #endif // COURGETTE_BSDIFF_PAGED_ARRAY_H_