1 /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /*
3  *     Copyright 2016 Couchbase, Inc.
4  *
5  *   Licensed under the Apache License, Version 2.0 (the "License");
6  *   you may not use this file except in compliance with the License.
7  *   You may obtain a copy of the License at
8  *
9  *       http://www.apache.org/licenses/LICENSE-2.0
10  *
11  *   Unless required by applicable law or agreed to in writing, software
12  *   distributed under the License is distributed on an "AS IS" BASIS,
13  *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  *   See the License for the specific language governing permissions and
15  *   limitations under the License.
16  */
17 #pragma once
18 
19 #include <platform/platform.h>
20 
21 #include <algorithm>
22 #include <cstddef>
23 #include <cstdint>
24 #include <cstring>
25 #include <iterator>
26 #include <stdexcept>
27 #include <string>
28 #include <type_traits>
29 #include <typeinfo>
30 #include <vector>
31 
32 namespace cb {
33 
34 /**
35  * Struct representing a buffer of some known size. This is used to
36  * refer to some existing region of memory which is owned elsewhere - i.e.
37  * this object does not have ownership semantics.
38  * A user should not free() the buf member themselves!
39  *
40  * @todo more member functions can be made constexpr in C++14
41  *       without implicit const / with generalised constexpr
42  */
43 template <typename T>
44 struct sized_buffer {
45     using value_type = T;
46     using base_type = typename std::remove_const<T>::type;
47 
48     // Type of instantiation
49     using buffer_type = sized_buffer<value_type>;
50 
51     // Const variant of instantiation (may be same as buffer_type)
52     using cbuffer_type = sized_buffer<const base_type>;
53 
54     // Non-const variant of instantiation (may be same as buffer_type)
55     using ncbuffer_type = sized_buffer<base_type>;
56 
57     using pointer = value_type*;
58     using const_pointer = const base_type*;
59     using reference = value_type&;
60     using const_reference = const base_type&;
61 
62     using iterator = pointer;
63     using const_iterator = const_pointer;
64 
65     using size_type = std::size_t;
66     using difference_type = std::ptrdiff_t;
67 
68     static const size_type npos = size_type(-1);
69 
sized_buffercb::sized_buffer70     constexpr sized_buffer() : sized_buffer(nullptr, 0) {
71     }
72 
sized_buffercb::sized_buffer73     constexpr sized_buffer(pointer buf_, size_type len_) : buf(buf_), len(len_) {
74     }
75 
76     /**
77      * Constructor from const reference to a string
78      * (cannot be instantiated for non-const T)
79      */
sized_buffercb::sized_buffer80     sized_buffer(const std::basic_string<base_type>& str)
81         : sized_buffer(str.data(), str.size()) {
82     }
83 
84     /**
85      * Constructor from non-const reference to a string
86      */
sized_buffercb::sized_buffer87     sized_buffer(std::basic_string<base_type>& str)
88         : sized_buffer(&str[0], str.size()) {
89     }
90 
91     /**
92      * Constructor from const reference to a vector
93      * (cannot be instantiated for non-const T)
94      */
sized_buffercb::sized_buffer95     sized_buffer(const std::vector<base_type>& vec)
96         : sized_buffer(vec.data(), vec.size()) {
97     }
98 
99     /**
100      * Constructor from non-const reference to a vector
101      */
sized_buffercb::sized_buffer102     sized_buffer(std::vector<base_type>& vec)
103         : sized_buffer(vec.data(), vec.size()) {
104     }
105 
106     /**
107      * Implicit constructor from non-const variant of instantiation
108      *
109      * This will allow automatic conversions to occur from non-const to const
110      * in the same way that a raw pointer would:
111      *
112      *     cb::sized_buffer<char> buf{vec.data(), vec.size()};
113      *     cb::sized_buffer<const char> cbuf = buf;
114      *
115      * @param other Buffer to copy from
116      */
sized_buffercb::sized_buffer117     constexpr sized_buffer(const ncbuffer_type& other) : buf(other.buf), len(other.len) {
118     }
119 
120     // Iterators
121 
begincb::sized_buffer122     iterator begin() {
123         return buf;
124     }
125 
begincb::sized_buffer126     constexpr const_iterator begin() const {
127         return buf;
128     }
129 
cbegincb::sized_buffer130     constexpr const_iterator cbegin() const {
131         return buf;
132     }
133 
endcb::sized_buffer134     iterator end() {
135         return buf + size();
136     }
137 
endcb::sized_buffer138     constexpr const_iterator end() const {
139         return buf + size();
140     }
141 
cendcb::sized_buffer142     constexpr const_iterator cend() const {
143         return buf + size();
144     }
145 
146     // Element access
147 
operator []cb::sized_buffer148     reference operator[](size_type pos) {
149         return buf[pos];
150     }
151 
operator []cb::sized_buffer152     constexpr const_reference operator[](size_type pos) const {
153         return buf[pos];
154     }
155 
atcb::sized_buffer156     reference at(size_type pos) {
157         if (pos >= size()) {
158             throw std::out_of_range(
159                     std::string("cb::sized_buffer<") + typeid(T).name() +
160                     ">::at: 'pos' out of range (" + std::to_string(pos) +
161                     " > " + std::to_string(size()) + ")");
162         }
163         return buf[pos];
164     }
165 
atcb::sized_buffer166     const_reference at(size_type pos) const {
167         if (pos >= size()) {
168             throw std::out_of_range(
169                     std::string("cb::sized_buffer<") + typeid(T).name() +
170                     ">::at: 'pos' out of range (" + std::to_string(pos) +
171                     " > " + std::to_string(size()) + ")");
172         }
173         return buf[pos];
174     }
175 
frontcb::sized_buffer176     reference front() {
177         return buf[0];
178     }
179 
frontcb::sized_buffer180     constexpr const_reference front() const {
181         return buf[0];
182     }
183 
backcb::sized_buffer184     reference back() {
185         return buf[size() - 1];
186     }
187 
backcb::sized_buffer188     constexpr const_reference back() const {
189         return buf[size() - 1];
190     }
191 
datacb::sized_buffer192     pointer data() {
193         return buf;
194     }
195 
datacb::sized_buffer196     constexpr const_pointer data() const {
197         return buf;
198     }
199 
200     // Capacity
201 
sizecb::sized_buffer202     constexpr size_type size() const {
203         return len;
204     }
205 
emptycb::sized_buffer206     constexpr bool empty() const {
207         return size() == 0;
208     }
209 
210     // Operations
211 
212     /**
213      * Returns a buffer of the substring [pos, pos + rcount),
214      * where rcount is the smaller of count and size() - pos.
215      */
substrcb::sized_buffer216     sized_buffer<value_type> substr(size_type pos = 0, size_type count = npos) {
217         if (pos > size()) {
218             throw std::out_of_range(
219                     std::string("cb::sized_buffer<") + typeid(T).name() +
220                     ">::substr: 'pos' out of range (" + std::to_string(pos) +
221                     " > " + std::to_string(size()) + ")");
222         }
223 
224         const size_type rcount = std::min(count, size() - pos);
225         return buffer_type(data() + pos, rcount);
226     }
227 
228     /**
229      * Compares two character sequences.
230      *
231      * The length rlen of the sequences to compare is the smaller of size() and
232      * v.size(). The function compares the two views by calling
233      * traits::compare(data(), v.data(), rlen). If the result is nonzero then
234      * it is returned. Otherwise, returns a value as indicated:
235      *
236      *  - size() < v.size(): -1
237      *  - size() == v.size(): 0
238      *  - size() > v.size(): 1
239      */
comparecb::sized_buffer240     int compare(buffer_type v) const {
241         const size_type rlen = std::min(size(), v.size());
242         const int cmp =
243                 std::char_traits<base_type>::compare(data(), v.data(), rlen);
244 
245         if (cmp != 0) {
246             return cmp;
247         } else if (size() < v.size()) {
248             return -1;
249         } else if (size() > v.size()) {
250             return 1;
251         } else {
252             return 0;
253         }
254     }
255 
256     /**
257      * Finds the first occurrence of v in this buffer, starting at position pos.
258      *
259      * @return Position of the first character of the found substring,
260      *         or npos if no such substring is found.
261      */
findcb::sized_buffer262     size_type find(cbuffer_type v, size_type pos = 0) const {
263         if (pos > size()) {
264             return npos;
265         }
266 
267         auto ptr = std::search(begin() + pos, end(), v.begin(), v.end());
268         if (ptr == end()) {
269             return npos;
270         } else {
271             return ptr - begin();
272         }
273     }
274 
275     /**
276      * Finds the first occurrence of any of the characters of v in this buffer,
277      * starting at position pos.
278      *
279      * @return Position of the first occurrence of any character of the
280      *         substring, or npos if no such character is found.
281      */
find_first_ofcb::sized_buffer282     size_type find_first_of(cbuffer_type v, size_type pos = 0) const {
283         if (pos > size()) {
284             return npos;
285         }
286 
287         auto ptr = std::find_first_of(begin() + pos, end(), v.begin(), v.end());
288         if (ptr == end()) {
289             return npos;
290         } else {
291             return ptr - begin();
292         }
293     }
294 
295     // Ideally these would be private but they're already in use
296     pointer buf;
297     size_type len;
298 };
299 
300 template <class T>
301 const size_t sized_buffer<T>::npos;
302 
303 template <class CharT>
operator ==(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs)304 bool operator==(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs) {
305     return lhs.compare(rhs) == 0;
306 }
307 
308 template <class CharT>
operator !=(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs)309 bool operator!=(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs) {
310     return lhs.compare(rhs) != 0;
311 }
312 
313 template <class CharT>
operator <(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs)314 bool operator<(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs) {
315     return lhs.compare(rhs) < 0;
316 }
317 
318 template <class CharT>
operator >(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs)319 bool operator>(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs) {
320     return lhs.compare(rhs) > 0;
321 }
322 
323 template <class CharT>
operator <=(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs)324 bool operator<=(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs) {
325     return lhs.compare(rhs) <= 0;
326 }
327 
328 template <class CharT>
operator >=(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs)329 bool operator>=(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs) {
330     return lhs.compare(rhs) >= 0;
331 }
332 
333 namespace {
334 template <typename CharT>
buffer_hash(sized_buffer<CharT> base)335 size_t buffer_hash(sized_buffer<CharT> base) {
336     // Probably only needs trivially copyable
337     static_assert(std::is_pod<CharT>::value,
338                   "cb::buffer_hash: Template param CharT must be a POD");
339 
340     // Perform the hash over the raw bytes of the CharT array
341     const size_t size = base.size() * sizeof(CharT);
342     const auto* bytes = reinterpret_cast<const uint8_t*>(base.data());
343 
344     size_t rv = 5381;
345     for (size_t ii = 0; ii < size; ii++) {
346         rv = ((rv << 5) + rv) ^ size_t(bytes[ii]);
347     }
348     return rv;
349 }
350 }
351 
352 /**
353  * The char_buffer is intended for strings you might want to modify
354  */
355 using char_buffer = sized_buffer<char>;
356 
357 /**
358  * The byte_buffer is intended to use for a blob of bytes you might want
359  * to modify
360  */
361 using byte_buffer = sized_buffer<uint8_t>;
362 
363 /**
364  * The const_byte_buffer is intended for a blob of bytes you _don't_
365  * want to modify.
366  */
367 using const_byte_buffer = sized_buffer<const uint8_t>;
368 
369 /**
370  * The const_char_buffer is intended for strings you're not going
371  * to modify.
372  */
373 class const_char_buffer : public sized_buffer<const char> {
374 public:
const_char_buffer()375     const_char_buffer() : sized_buffer() {
376     }
377 
378     using sized_buffer::sized_buffer;
379 
const_char_buffer(const char* cStr)380     const_char_buffer(const char* cStr)
381         : sized_buffer(cStr, std::strlen(cStr)) {
382     }
383 };
384 
385 PLATFORM_PUBLIC_API
386 std::string to_string(const_char_buffer cb);
387 
operator ==(const_char_buffer lhs, const char* rhs)388 inline bool operator==(const_char_buffer lhs, const char* rhs) {
389     return lhs.compare(const_char_buffer(rhs)) == 0;
390 }
391 
392 } // namespace cb
393 
394 constexpr inline cb::const_char_buffer operator"" _ccb(const char* str,
395                                                        size_t len) noexcept {
396     return cb::const_char_buffer(str, len);
397 }
398 
399 namespace std {
400 template <typename CharT>
401 struct hash<cb::sized_buffer<CharT>> {
operator ()std::hash402     size_t operator()(cb::sized_buffer<CharT> s) const {
403         return cb::buffer_hash(s);
404     }
405 };
406 }
407 
408 namespace std {
409 template <>
410 struct hash<cb::const_char_buffer> {
operator ()std::hash411     size_t operator()(cb::const_char_buffer s) const {
412         return cb::buffer_hash(s);
413     }
414 };
415 }
416