• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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