blob: e9d02990311a812f76b467caa398ded96cce6a55 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
// 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_
|
