1 /*
2  * Copyright (C) 2019 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include "types.h"
18 
19 IOVector& IOVector::operator=(IOVector&& move) noexcept {
20     chain_ = std::move(move.chain_);
21     chain_length_ = move.chain_length_;
22     begin_offset_ = move.begin_offset_;
23     start_index_ = move.start_index_;
24 
25     move.clear();
26     return *this;
27 }
28 
29 IOVector::block_type IOVector::clear() {
30     chain_length_ = 0;
31     begin_offset_ = 0;
32     start_index_ = 0;
33     block_type res;
34     if (!chain_.empty()) {
35         res = std::move(chain_.back());
36     }
37     chain_.clear();
38     return res;
39 }
40 
41 void IOVector::drop_front(IOVector::size_type len) {
42     if (len == 0) {
43         return;
44     }
45     if (len == size()) {
46         clear();
47         return;
48     }
49     CHECK_LT(len, size());
50 
51     auto dropped = 0u;
52     while (dropped < len) {
53         const auto next = chain_[start_index_].size() - begin_offset_;
54         if (dropped + next <= len) {
55             pop_front_block();
56             dropped += next;
57         } else {
58             const auto taken = len - dropped;
59             begin_offset_ += taken;
60             break;
61         }
62     }
63 }
64 
65 IOVector IOVector::take_front(IOVector::size_type len) {
66     if (len == 0) {
67         return {};
68     }
69     if (len == size()) {
70         return std::move(*this);
71     }
72 
73     CHECK_GE(size(), len);
74     IOVector res;
75     // first iterate over the blocks that completely go into the other vector
76     while (chain_[start_index_].size() - begin_offset_ <= len) {
77         chain_length_ -= chain_[start_index_].size();
78         len -= chain_[start_index_].size() - begin_offset_;
79         if (chain_[start_index_].size() > begin_offset_) {
80             res.append(std::move(chain_[start_index_]));
81             if (begin_offset_) {
82                 res.begin_offset_ = std::exchange(begin_offset_, 0);
83             }
84         } else {
85             begin_offset_ = 0;
86         }
87         ++start_index_;
88     }
89 
90     if (len > 0) {
91         // what's left is a single buffer that needs to be split between the |res| and |this|
92         // we know that it has to be split - there was a check for the case when it has to
93         // go away as a whole.
94         if (begin_offset_ != 0 || len < chain_[start_index_].size() / 2) {
95             // let's memcpy the data out
96             block_type block(chain_[start_index_].begin() + begin_offset_,
97                              chain_[start_index_].begin() + begin_offset_ + len);
98             res.append(std::move(block));
99             begin_offset_ += len;
100         } else {
101             CHECK_EQ(begin_offset_, 0u);
102             // move out the internal buffer out and copy only the tail of it back in
103             block_type block(chain_[start_index_].begin() + len, chain_[start_index_].end());
104             chain_length_ -= chain_[start_index_].size();
105             chain_[start_index_].resize(len);
106             res.append(std::move(chain_[start_index_]));
107             chain_length_ += block.size();
108             chain_[start_index_] = std::move(block);
109         }
110     }
111     return res;
112 }
113 
114 void IOVector::trim_front() {
115     if ((begin_offset_ == 0 && start_index_ == 0) || chain_.empty()) {
116         return;
117     }
118     block_type& first_block = chain_[start_index_];
119     if (begin_offset_ == first_block.size()) {
120         ++start_index_;
121     } else {
122         memmove(first_block.data(), first_block.data() + begin_offset_,
123                 first_block.size() - begin_offset_);
124         first_block.resize(first_block.size() - begin_offset_);
125     }
126     chain_length_ -= begin_offset_;
127     begin_offset_ = 0;
128     trim_chain_front();
129 }
130 
131 void IOVector::trim_chain_front() {
132     if (start_index_) {
133         chain_.erase(chain_.begin(), chain_.begin() + start_index_);
134         start_index_ = 0;
135     }
136 }
137 
138 void IOVector::pop_front_block() {
139     chain_length_ -= chain_[start_index_].size();
140     begin_offset_ = 0;
141     chain_[start_index_].clear();
142     ++start_index_;
143     if (start_index_ > std::max<size_t>(4, chain_.size() / 2)) {
144         trim_chain_front();
145     }
146 }
147 
148 IOVector::block_type IOVector::coalesce() && {
149     // Destructive coalesce() may optimize for several cases when it doesn't need to allocate
150     // new buffer, or even return one of the existing blocks as is. The only guarantee is that
151     // after this call the IOVector is in some valid state. Nothing is guaranteed about the
152     // specifics.
153     if (size() == 0) {
154         return {};
155     }
156     if (begin_offset_ == chain_[start_index_].size() && chain_.size() == start_index_ + 2) {
157         chain_length_ -= chain_.back().size();
158         auto res = std::move(chain_.back());
159         chain_.pop_back();
160         return res;
161     }
162     if (chain_.size() == start_index_ + 1) {
163         chain_length_ -= chain_.back().size();
164         auto res = std::move(chain_.back());
165         chain_.pop_back();
166         if (begin_offset_ != 0) {
167             memmove(res.data(), res.data() + begin_offset_, res.size() - begin_offset_);
168             res.resize(res.size() - begin_offset_);
169             begin_offset_ = 0;
170         }
171         return res;
172     }
173     if (auto& firstBuffer = chain_[start_index_]; firstBuffer.capacity() >= size()) {
174         auto res = std::move(chain_[start_index_]);
175         auto size = res.size();
176         chain_length_ -= size;
177         if (begin_offset_ != 0) {
178             memmove(res.data(), res.data() + begin_offset_, res.size() - begin_offset_);
179             size -= begin_offset_;
180             begin_offset_ = 0;
181         }
182         for (auto i = start_index_ + 1; i < chain_.size(); ++i) {
183             memcpy(res.data() + size, chain_[i].data(), chain_[i].size());
184             size += chain_[i].size();
185         }
186         res.resize(size);
187         ++start_index_;
188         return res;
189     }
190     return const_cast<const IOVector*>(this)->coalesce<>();
191 }
192 
193 std::vector<adb_iovec> IOVector::iovecs() const {
194     std::vector<adb_iovec> result;
195     result.reserve(chain_.size() - start_index_);
196     iterate_blocks([&result](const char* data, size_t len) {
197         adb_iovec iov;
198         iov.iov_base = const_cast<char*>(data);
199         iov.iov_len = len;
200         result.emplace_back(iov);
201     });
202 
203     return result;
204 }
205