12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Copyright (c) 2010 The Chromium Authors. All rights reserved. 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// found in the LICENSE file. 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// PagedArray implements an array stored using many fixed-size pages. 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// PagedArray is a work-around to allow large arrays to be allocated when there 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// is too much address space fragmentation for allocating the large arrays as 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// contigous arrays. 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef COURGETTE_BSDIFF_PAGED_ARRAY_H_ 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define COURGETTE_BSDIFF_PAGED_ARRAY_H_ 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// For std::nothrow: 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <new> 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/basictypes.h" 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace courgette { 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// PagedArray implements an array stored using many fixed-size pages. 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template<typename T> 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class PagedArray { 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) enum { 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Page size in elements. Page size of 2^18 * sizeof(T) is 1MB for T = int. 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kLogPageSize = 18, 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) kPageSize = 1 << kLogPageSize 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) }; 282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public: 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) PagedArray() : pages_(NULL), page_count_(0) {} 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ~PagedArray() { clear(); } 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) T& operator[](size_t i) { 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) size_t page = i >> kLogPageSize; 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) size_t offset = i & (kPageSize - 1); 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // It is tempting to add a DCHECK(page < page_count_), but that makes 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // bsdiff_create run 2x slower (even when compiled optimized.) 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return pages_[page][offset]; 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Allocates storage for |size| elements. Returns true on success and false if 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // allocation fails. 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool Allocate(size_t size) { 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) clear(); 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) size_t pages_needed = (size + kPageSize - 1) >> kLogPageSize; 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) pages_ = new(std::nothrow) T*[pages_needed]; 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (pages_ == NULL) 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return false; 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (page_count_ = 0; page_count_ < pages_needed; ++page_count_) { 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) T* block = new(std::nothrow) T[kPageSize]; 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (block == NULL) { 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) clear(); 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return false; 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) pages_[page_count_] = block; 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return true; 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Releases all storage. May be called more than once. 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void clear() { 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (pages_ != NULL) { 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (page_count_ != 0) { 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) --page_count_; 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) delete[] pages_[page_count_]; 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) delete[] pages_; 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) pages_ = NULL; 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) private: 752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) T** pages_; 762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) size_t page_count_; 772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(PagedArray); 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} // namespace 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#endif // COURGETTE_BSDIFF_PAGED_ARRAY_H_ 82