// 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_ |