1 | /* |
2 | * Copyright (C) 2016-2018 Apple Inc. All rights reserved. |
3 | * |
4 | * Redistribution and use in source and binary forms, with or without |
5 | * modification, are permitted provided that the following conditions |
6 | * are met: |
7 | * 1. Redistributions of source code must retain the above copyright |
8 | * notice, this list of conditions and the following disclaimer. |
9 | * 2. Redistributions in binary form must reproduce the above copyright |
10 | * notice, this list of conditions and the following disclaimer in the |
11 | * documentation and/or other materials provided with the distribution. |
12 | * |
13 | * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY |
14 | * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
15 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
16 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR |
17 | * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
18 | * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
19 | * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
20 | * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
21 | * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
22 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
23 | * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
24 | */ |
25 | |
26 | #include "LargeMap.h" |
27 | #include <utility> |
28 | |
29 | namespace bmalloc { |
30 | |
31 | LargeRange LargeMap::remove(size_t alignment, size_t size) |
32 | { |
33 | size_t alignmentMask = alignment - 1; |
34 | |
35 | LargeRange* candidate = m_free.end(); |
36 | for (LargeRange* it = m_free.begin(); it != m_free.end(); ++it) { |
37 | if (!it->isEligibile()) |
38 | continue; |
39 | |
40 | if (it->size() < size) |
41 | continue; |
42 | |
43 | if (candidate != m_free.end() && candidate->begin() < it->begin()) |
44 | continue; |
45 | |
46 | if (test(it->begin(), alignmentMask)) { |
47 | char* aligned = roundUpToMultipleOf(alignment, it->begin()); |
48 | if (aligned < it->begin()) // Check for overflow. |
49 | continue; |
50 | |
51 | char* alignedEnd = aligned + size; |
52 | if (alignedEnd < aligned) // Check for overflow. |
53 | continue; |
54 | |
55 | if (alignedEnd > it->end()) |
56 | continue; |
57 | } |
58 | |
59 | candidate = it; |
60 | } |
61 | |
62 | if (candidate == m_free.end()) |
63 | return LargeRange(); |
64 | |
65 | return m_free.pop(candidate); |
66 | } |
67 | |
68 | void LargeMap::add(const LargeRange& range) |
69 | { |
70 | LargeRange merged = range; |
71 | |
72 | for (size_t i = 0; i < m_free.size(); ++i) { |
73 | if (!canMerge(merged, m_free[i])) |
74 | continue; |
75 | |
76 | merged = merge(merged, m_free.pop(i--)); |
77 | } |
78 | |
79 | merged.setUsedSinceLastScavenge(); |
80 | m_free.push(merged); |
81 | } |
82 | |
83 | void LargeMap::markAllAsEligibile() |
84 | { |
85 | for (LargeRange& range : m_free) |
86 | range.setEligible(true); |
87 | } |
88 | |
89 | } // namespace bmalloc |
90 | |