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/visibility.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 #include <iosfwd>
32 
33 namespace cb {
34 
35 /**
36  * Struct representing a buffer of some known size. This is used to
37  * refer to some existing region of memory which is owned elsewhere - i.e.
38  * this object does not have ownership semantics.
39  * A user should not free() the buf member themselves!
40  *
41  * @todo more member functions can be made constexpr in C++14
42  *       without implicit const / with generalised constexpr
43  */
44 template <typename T>
45 struct sized_buffer {
46     using value_type = T;
47     using base_type = typename std::remove_const<T>::type;
48 
49     // Type of instantiation
50     using buffer_type = sized_buffer<value_type>;
51 
52     // Const variant of instantiation (may be same as buffer_type)
53     using cbuffer_type = sized_buffer<const base_type>;
54 
55     // Non-const variant of instantiation (may be same as buffer_type)
56     using ncbuffer_type = sized_buffer<base_type>;
57 
58     using pointer = value_type*;
59     using const_pointer = const base_type*;
60     using reference = value_type&;
61     using const_reference = const base_type&;
62 
63     using iterator = pointer;
64     using const_iterator = const_pointer;
65 
66     using size_type = std::size_t;
67     using difference_type = std::ptrdiff_t;
68 
69     static const size_type npos = size_type(-1);
70 
sized_buffercb::sized_buffer71     constexpr sized_buffer() : sized_buffer(nullptr, 0) {
72     }
73 
sized_buffercb::sized_buffer74     constexpr sized_buffer(pointer buf_, size_type len_) : buf(buf_), len(len_) {
75     }
76 
77     /**
78      * Constructor from const reference to a string
79      * (cannot be instantiated for non-const T)
80      */
sized_buffercb::sized_buffer81     sized_buffer(const std::basic_string<base_type>& str)
82         : sized_buffer(str.data(), str.size()) {
83     }
84 
85     /**
86      * Constructor from non-const reference to a string
87      */
sized_buffercb::sized_buffer88     sized_buffer(std::basic_string<base_type>& str)
89         : sized_buffer(&str[0], str.size()) {
90     }
91 
92     /**
93      * Constructor from const reference to a vector
94      * (cannot be instantiated for non-const T)
95      */
sized_buffercb::sized_buffer96     sized_buffer(const std::vector<base_type>& vec)
97         : sized_buffer(vec.data(), vec.size()) {
98     }
99 
100     /**
101      * Constructor from non-const reference to a vector
102      */
sized_buffercb::sized_buffer103     sized_buffer(std::vector<base_type>& vec)
104         : sized_buffer(vec.data(), vec.size()) {
105     }
106 
107     /**
108      * Implicit constructor from non-const variant of instantiation
109      *
110      * This will allow automatic conversions to occur from non-const to const
111      * in the same way that a raw pointer would:
112      *
113      *     cb::sized_buffer<char> buf{vec.data(), vec.size()};
114      *     cb::sized_buffer<const char> cbuf = buf;
115      *
116      * @param other Buffer to copy from
117      */
sized_buffercb::sized_buffer118     constexpr sized_buffer(const ncbuffer_type& other) : buf(other.buf), len(other.len) {
119     }
120 
121     // Iterators
122 
begincb::sized_buffer123     iterator begin() {
124         return buf;
125     }
126 
begincb::sized_buffer127     constexpr const_iterator begin() const {
128         return buf;
129     }
130 
cbegincb::sized_buffer131     constexpr const_iterator cbegin() const {
132         return buf;
133     }
134 
endcb::sized_buffer135     iterator end() {
136         return buf + size();
137     }
138 
endcb::sized_buffer139     constexpr const_iterator end() const {
140         return buf + size();
141     }
142 
cendcb::sized_buffer143     constexpr const_iterator cend() const {
144         return buf + size();
145     }
146 
147     // Element access
148 
operator []cb::sized_buffer149     reference operator[](size_type pos) {
150         return buf[pos];
151     }
152 
operator []cb::sized_buffer153     constexpr const_reference operator[](size_type pos) const {
154         return buf[pos];
155     }
156 
atcb::sized_buffer157     reference at(size_type pos) {
158         if (pos >= size()) {
159             throw std::out_of_range(
160                     std::string("cb::sized_buffer<") + typeid(T).name() +
161                     ">::at: 'pos' out of range (" + std::to_string(pos) +
162                     " > " + std::to_string(size()) + ")");
163         }
164         return buf[pos];
165     }
166 
atcb::sized_buffer167     const_reference at(size_type pos) const {
168         if (pos >= size()) {
169             throw std::out_of_range(
170                     std::string("cb::sized_buffer<") + typeid(T).name() +
171                     ">::at: 'pos' out of range (" + std::to_string(pos) +
172                     " > " + std::to_string(size()) + ")");
173         }
174         return buf[pos];
175     }
176 
frontcb::sized_buffer177     reference front() {
178         return buf[0];
179     }
180 
frontcb::sized_buffer181     constexpr const_reference front() const {
182         return buf[0];
183     }
184 
backcb::sized_buffer185     reference back() {
186         return buf[size() - 1];
187     }
188 
backcb::sized_buffer189     constexpr const_reference back() const {
190         return buf[size() - 1];
191     }
192 
datacb::sized_buffer193     pointer data() {
194         return buf;
195     }
196 
datacb::sized_buffer197     constexpr const_pointer data() const {
198         return buf;
199     }
200 
201     // Capacity
202 
sizecb::sized_buffer203     constexpr size_type size() const {
204         return len;
205     }
206 
emptycb::sized_buffer207     constexpr bool empty() const {
208         return size() == 0;
209     }
210 
211     // Operations
212 
213     /**
214      * Returns a buffer of the substring [pos, pos + rcount),
215      * where rcount is the smaller of count and size() - pos.
216      */
substrcb::sized_buffer217     sized_buffer<value_type> substr(size_type pos = 0, size_type count = npos) {
218         if (pos > size()) {
219             throw std::out_of_range(
220                     std::string("cb::sized_buffer<") + typeid(T).name() +
221                     ">::substr: 'pos' out of range (" + std::to_string(pos) +
222                     " > " + std::to_string(size()) + ")");
223         }
224 
225         const size_type rcount = std::min(count, size() - pos);
226         return buffer_type(data() + pos, rcount);
227     }
228 
229     /**
230      * Compares two character sequences.
231      *
232      * The length rlen of the sequences to compare is the smaller of size() and
233      * v.size(). The function compares the two views by calling
234      * traits::compare(data(), v.data(), rlen). If the result is nonzero then
235      * it is returned. Otherwise, returns a value as indicated:
236      *
237      *  - size() < v.size(): -1
238      *  - size() == v.size(): 0
239      *  - size() > v.size(): 1
240      */
comparecb::sized_buffer241     int compare(buffer_type v) const {
242         const size_type rlen = std::min(size(), v.size());
243         const int cmp =
244                 std::char_traits<base_type>::compare(data(), v.data(), rlen);
245 
246         if (cmp != 0) {
247             return cmp;
248         } else if (size() < v.size()) {
249             return -1;
250         } else if (size() > v.size()) {
251             return 1;
252         } else {
253             return 0;
254         }
255     }
256 
257     /**
258      * Finds the first occurrence of v in this buffer, starting at position pos.
259      *
260      * @return Position of the first character of the found substring,
261      *         or npos if no such substring is found.
262      */
findcb::sized_buffer263     size_type find(cbuffer_type v, size_type pos = 0) const {
264         if (pos > size()) {
265             return npos;
266         }
267 
268         auto ptr = std::search(begin() + pos, end(), v.begin(), v.end());
269         if (ptr == end()) {
270             return npos;
271         } else {
272             return ptr - begin();
273         }
274     }
275 
276     /**
277      * Finds the first occurrence of any of the characters of v in this buffer,
278      * starting at position pos.
279      *
280      * @return Position of the first occurrence of any character of the
281      *         substring, or npos if no such character is found.
282      */
find_first_ofcb::sized_buffer283     size_type find_first_of(cbuffer_type v, size_type pos = 0) const {
284         if (pos > size()) {
285             return npos;
286         }
287 
288         auto ptr = std::find_first_of(begin() + pos, end(), v.begin(), v.end());
289         if (ptr == end()) {
290             return npos;
291         } else {
292             return ptr - begin();
293         }
294     }
295 
296     // Ideally these would be private but they're already in use
297     pointer buf;
298     size_type len;
299 };
300 
301 template <class T>
302 const size_t sized_buffer<T>::npos;
303 
304 template <class CharT>
operator ==(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs)305 bool operator==(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs) {
306     return lhs.compare(rhs) == 0;
307 }
308 
309 template <class CharT>
operator !=(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs)310 bool operator!=(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs) {
311     return lhs.compare(rhs) != 0;
312 }
313 
314 template <class CharT>
operator <(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs)315 bool operator<(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs) {
316     return lhs.compare(rhs) < 0;
317 }
318 
319 template <class CharT>
operator >(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs)320 bool operator>(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs) {
321     return lhs.compare(rhs) > 0;
322 }
323 
324 template <class CharT>
operator <=(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs)325 bool operator<=(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs) {
326     return lhs.compare(rhs) <= 0;
327 }
328 
329 template <class CharT>
operator >=(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs)330 bool operator>=(sized_buffer<CharT> lhs, sized_buffer<CharT> rhs) {
331     return lhs.compare(rhs) >= 0;
332 }
333 
334 namespace {
335 template <typename CharT>
buffer_hash(sized_buffer<CharT> base)336 size_t buffer_hash(sized_buffer<CharT> base) {
337     // Probably only needs trivially copyable
338     static_assert(std::is_pod<CharT>::value,
339                   "cb::buffer_hash: Template param CharT must be a POD");
340 
341     // Perform the hash over the raw bytes of the CharT array
342     const size_t size = base.size() * sizeof(CharT);
343     const auto* bytes = reinterpret_cast<const uint8_t*>(base.data());
344 
345     size_t rv = 5381;
346     for (size_t ii = 0; ii < size; ii++) {
347         rv = ((rv << 5) + rv) ^ size_t(bytes[ii]);
348     }
349     return rv;
350 }
351 }
352 
353 /**
354  * The char_buffer is intended for strings you might want to modify
355  */
356 using char_buffer = sized_buffer<char>;
357 
358 /**
359  * The byte_buffer is intended to use for a blob of bytes you might want
360  * to modify
361  */
362 using byte_buffer = sized_buffer<uint8_t>;
363 
364 /**
365  * The const_byte_buffer is intended for a blob of bytes you _don't_
366  * want to modify.
367  */
368 using const_byte_buffer = sized_buffer<const uint8_t>;
369 
370 /**
371  * The const_char_buffer is intended for strings you're not going
372  * to modify.
373  */
374 class const_char_buffer : public sized_buffer<const char> {
375 public:
const_char_buffer()376     const_char_buffer() : sized_buffer() {
377     }
378 
379     using sized_buffer::sized_buffer;
380 
const_char_buffer(const char* cStr)381     const_char_buffer(const char* cStr)
382         : sized_buffer(cStr, std::strlen(cStr)) {
383     }
384 };
385 
386 PLATFORM_PUBLIC_API
387 std::string to_string(const_char_buffer cb);
388 
operator ==(const_char_buffer lhs, const char* rhs)389 inline bool operator==(const_char_buffer lhs, const char* rhs) {
390     return lhs.compare(const_char_buffer(rhs)) == 0;
391 }
392 
393 PLATFORM_PUBLIC_API
394 std::ostream& operator<<(std::ostream& os,
395                          const cb::const_char_buffer& cb);
396 
397 } // namespace cb
398 
399 constexpr inline cb::const_char_buffer operator"" _ccb(const char* str,
400                                                        size_t len) noexcept {
401     return cb::const_char_buffer(str, len);
402 }
403 
404 namespace std {
405 template <typename CharT>
406 struct hash<cb::sized_buffer<CharT>> {
operator ()std::hash407     size_t operator()(cb::sized_buffer<CharT> s) const {
408         return cb::buffer_hash(s);
409     }
410 };
411 }
412 
413 namespace std {
414 template <>
415 struct hash<cb::const_char_buffer> {
operator ()std::hash416     size_t operator()(cb::const_char_buffer s) const {
417         return cb::buffer_hash(s);
418     }
419 };
420 }
421