source: mainline/uspace/lib/cpp/include/impl/string.hpp@ b08a62c

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since b08a62c was b08a62c, checked in by Dzejrou <dzejrou@…>, 7 years ago

cpp: added implementation of the most basic string functions
  • Property mode set to 100644
File size: 20.7 KB
Line 
1/*
2 * Copyright (c) 2017 Jaroslav Jindrak
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#ifndef LIBCPP_STRING
30#define LIBCPP_STRING
31
32#include <initializer_list>
33#include <iosfwd>
34#include <cstdio>
35#include <cstdlib>
36#include <cstring>
37
38namespace std
39{
40
41 /**
42 * 21.2, char_traits:
43 */
44
45 template<class Char>
46 struct char_traits;
47
48 /**
49 * 21.2.3, char_traits specializations:
50 */
51
52 template<>
53 struct char_traits<char>
54 {
55 using char_type = char;
56 using int_type = int;
57 using off_type = streamoff;
58 using pos_type = streampos;
59 /* using state_type = mbstate_t; */
60
61 static void assign(char_type& c1, char_type& c2) noexcept
62 {
63 c1 = c2;
64 }
65
66 static constexpr bool eq(char_type c1, char_type c2) noexcept
67 {
68 return c1 == c2;
69 }
70
71 static constexpr bool lt(char_type c1, char_type c2) noexcept
72 {
73 return c1 < c2;
74 }
75
76 static int compare(const char_type* s1, const char_type* s2, size_t n)
77 {
78 return std::str_lcmp(s1, s2, n);
79 }
80
81 static size_t length(const char_type* s)
82 {
83 return std::str_size(s);
84 }
85
86 static const char_type* find(const char_type* s, size_t n, const char_type& c)
87 {
88 size_t i{};
89 while (i++ < n)
90 {
91 if (s[i] == c)
92 return s + i;
93 }
94
95 return nullptr;
96 }
97
98 static char_type* move(char_type* s1, const char_type* s2, size_t n)
99 {
100 return static_cast<char_type*>(memmove(s1, s2, n));
101 }
102
103 static char_type* copy(char_type* s1, const char_type* s2, size_t n)
104 {
105 return static_cast<char_type*>(memcpy(s1, s2, n));
106 }
107
108 static char_type* assign(char_type* s, size_t n, char_type c)
109 {
110 /**
111 * Note: Even though memset accepts int as its second argument,
112 * the actual implementation assigns that int to a dereferenced
113 * char pointer.
114 */
115 return static_cast<char_type*>(memset(s, static_cast<int>(c), n));
116 }
117
118 static constexpr int_type not_eof(int_type c) noexcept
119 {
120 if (!eq_int_type(c, eof()))
121 return c;
122 else
123 return to_int_type('a'); // We just need something that is not eof.
124 }
125
126 static constexpr char_type to_char_type(int_type c) noexcept
127 {
128 return static_cast<char_type>(c);
129 }
130
131 static constexpr int_type to_int_type(char_type c) noexcept
132 {
133 return static_cast<int_type>(c);
134 }
135
136 static constexpr bool eq_int_type(int_type c1, int_type c2) noexcept
137 {
138 return c1 == c2;
139 }
140
141 static constexpr int_type eof() noexcept
142 {
143 return static_cast<int_type>(EOF);
144 }
145 };
146
147 template<>
148 struct char_traits<char16_t>
149 { /* TODO: implement */ };
150
151 template<>
152 struct char_traits<char32_t>
153 { /* TODO: implement */ };
154
155 template<>
156 struct char_traits<wchar_t>
157 {
158 using char_type = wchar_t;
159 using int_type = wint_t;
160 using off_type = streamoff;
161 using pos_type = wstreampos;
162 /* using state_type = mbstate_t; */
163
164 static void assign(char_type& c1, char_type& c2) noexcept
165 {
166 c1 = c2;
167 }
168
169 static constexpr bool eq(char_type c1, char_type c2) noexcept
170 {
171 return c1 == c2;
172 }
173
174 static constexpr bool lt(char_type c1, char_type c2) noexcept
175 {
176 return c1 < c2;
177 }
178
179 static int compare(const char_type* s1, const char_type* s2, size_t n)
180 {
181 return std::wstr_lcmp(s1, s2, n);
182 }
183
184 static size_t length(const char_type* s)
185 {
186 return std::wstr_size(s);
187 }
188
189 static const char_type* find(const char_type* s, size_t n, const char_type& c)
190 {
191 size_t i{};
192 while (i++ < n)
193 {
194 if (s[i] == c)
195 return s + i;
196 }
197
198 return nullptr;
199 }
200
201 static char_type* move(char_type* s1, const char_type* s2, size_t n)
202 {
203 return static_cast<char_type*>(memmove(s1, s2, n * sizeof(wchar_t)));
204 }
205
206 static char_type* copy(char_type* s1, const char_type* s2, size_t n)
207 {
208 return static_cast<char_type*>(memcpy(s1, s2, n * sizeof(wchar_t)));
209 }
210
211 static char_type* assign(char_type* s, size_t n, char_type c)
212 {
213 return static_cast<char_type*>(memset(s, static_cast<int>(c), n * sizeof(wchar_t)));
214 }
215
216 static constexpr int_type not_eof(int_type c) noexcept
217 {
218 if (!eq_int_type(c, eof()))
219 return c;
220 else
221 return to_int_type(L'a'); // We just need something that is not eof.
222 }
223
224 static constexpr char_type to_char_type(int_type c) noexcept
225 {
226 return static_cast<char_type>(c);
227 }
228
229 static constexpr int_type to_int_type(char_type c) noexcept
230 {
231 return static_cast<int_type>(c);
232 }
233
234 static constexpr bool eq_int_type(int_type c1, int_type c2) noexcept
235 {
236 return c1 == c2;
237 }
238
239 static constexpr int_type eof() noexcept
240 {
241 return static_cast<int_type>(EOF);
242 }
243 };
244
245 /**
246 * 21.4, class template basic_string:
247 */
248
249 template<class Char, class Traits = char_traits<Char>,
250 class Allocator = allocator<Char>>
251 class basic_string
252 {
253 public:
254 using traits_type = Traits;
255 using value_type = typename traits_type::char_type;
256 using allocator_type = Allocator;
257 using size_type = typename allocator_traits<allocator_type>::size_type;
258 using difference_type = typename allocator_traits<allocator_type>::difference_type;
259
260 using reference = value_type&;
261 using const_reference = const value_type&;
262 using pointer = allocator_traits<allocator_type>::pointer;
263 using const_pointer = allocator_traits<allocator_type>::const_pointer;
264
265 using iterator = pointer;
266 using const_iterator = const_pointer;
267 using reverse_iterator = std::reverse_iterator<iterator>;
268 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
269
270 static constexpr size_type npos = -1;
271
272 /**
273 * 21.4.2, construct/copy/destroy:
274 */
275 basic_string() noexcept
276 : basic_string(allocator_type{})
277 { /* DUMMY BODY */ }
278
279 explicit basic_string(const allocator_type& alloc);
280
281 basic_string(const basic_string& other);
282
283 basic_string(basic_string&& other);
284
285 basic_string(const basic_string& other, size_type pos, size_type n = npos,
286 const allocator_type& alloc = allocator_type{});
287
288 basic_string(const value_type*, size_type n, const allocator_type& alloc = allocator{});
289
290 basic_string(const value_type*, const allocator_type& alloc = allocator{});
291
292 basic_string(size_type n, value_type c, const allocator_type& alloc = allocator{});
293
294 template<class InputIterator>
295 basic_string(InputIterator first, InputIterator last,
296 const allocator_type& alloc = allocator{});
297
298 basic_string(initializer_list<value_type> init, const allocator_type& alloc = allocator{});
299
300 basic_string(const basic_string& other, const allocator_type& alloc);
301
302 basic_string(basic_string&& other, const allocator_type& alloc);
303
304 ~basic_string();
305
306 basic_string& operator=(const basic_string& other);
307
308 basic_string& operator=(basic_string&& other)
309 noexcept(allocator_traits<allocator_type>::propagate_on_container_move_assignment::value ||
310 allocator_traits<allocator_type>::is_always_equal::value);
311
312 basic_string& operator=(const value_type* other);
313
314 basic_string& operator=(value_type c);
315
316 basic_string& operator=(initializer_list<value_type>);
317
318 /**
319 * 21.4.3, iterators:
320 */
321
322 iterator begin() noexcept
323 {
324 return &data_[0];
325 }
326
327 const_iterator begin() const noexcept
328 {
329 return &data_[0];
330 }
331
332 iterator end() noexcept
333 {
334 return begin() + size_;
335 }
336
337 const_iterator end() const noexcept
338 {
339 return begin() + size_;
340 }
341
342 reverse_iterator rbegin() noexcept
343 {
344 return make_reverse_iterator(end());
345 }
346
347 const_reverse_iterator rbegin() const noexcept
348 {
349 return make_reverse_iterator(cend());
350 }
351
352 reverse_iterator rend() noexcept
353 {
354 return make_reverse_iterator(begin());
355 }
356
357 const_reverse_iterator rend() const noexcept
358 {
359 return make_reverse_iterator(cbegin());
360 }
361
362 const_iterator cbegin() const noexcept
363 {
364 return &data_[0];
365 }
366
367 const_iterator cend() const noexcept
368 {
369 return cbegin() + size_;
370 }
371
372 const_reverse_iterator crbegin() const noexcept
373 {
374 return rbegin();
375 }
376
377 const_reverse_iterator crend() const noexcept
378 {
379 return rend();
380 }
381
382 /**
383 * 21.4.4, capacity:
384 */
385
386 size_type size() const noexcept
387 {
388 return size_;
389 }
390
391 size_type length() const noexcept
392 {
393 return size_;
394 }
395
396 size_type max_size() const noexcept
397 {
398 return allocator_traits<allocator_type>::max_size(allocator_);
399 }
400
401 void resize(size_type n, value_type c);
402
403 void resize(size_type n);
404
405 size_type capacity() const noexcept
406 {
407 return capacity_;
408 }
409
410 void reserve(size_type res_arg = 0);
411
412 void shrink_to_fit();
413
414 void clear() noexcept;
415
416 bool empty() const noexcept
417 {
418 return size_ == 0;
419 }
420
421 /**
422 * 21.4.5, element access:
423 */
424
425 const_reference operator[](size_type idx) const
426 {
427 return data_[idx];
428 }
429
430 reference operator[](size_type idx)
431 {
432 return data_[idx];
433 }
434
435 const_reference at(size_type idx) const
436 {
437 // TODO: bounds checking
438 return data_[idx];
439 }
440
441 reference at(size_type idx)
442 {
443 // TODO: bounds checking
444 return data_[idx];
445 }
446
447 const_reference front() const
448 {
449 return at(0);
450 }
451
452 reference front()
453 {
454 return at(0);
455 }
456
457 const_reference back() const
458 {
459 return at(size_ - 1);
460 }
461
462 reference back()
463 {
464 return at(size_ - 1);
465 }
466
467 /**
468 * 21.4.6, modifiers:
469 */
470
471 basic_string& operator+=(const basic_string& str);
472
473 basic_string& operator+=(const value_type* str);
474
475 basic_string& operator+=(value_type c);
476
477 basic_string& operator+=(initializer_list<value_type> init);
478
479 basic_string& append(const basic_string& str);
480
481 basic_string& append(const basic_string& str, size_type pos
482 size_type n = npos);
483
484 basic_string& append(const value_type* str, size_type n);
485
486 basic_string& append(const value_type* str);
487
488 basic_string& append(size_type n, value_type c);
489
490 template<class InputIterator>
491 basic_string& append(InputIterator first, InputIterator last);
492
493 basic_string& append(initializer_list<value_type> init);
494
495 void push_back(value_type c);
496
497 basic_string& assign(const basic_string& str);
498
499 basic_string& assign(basic_string&& str);
500
501 basic_string& assign(const basic_string& str, size_type pos,
502 size_type n = npos);
503
504 basic_string& assign(const value_type* str, size_type n);
505
506 basic_string& assign(const value_type* str);
507
508 basic_string& assign(size_type n, value_type c);
509
510 template<class InputIterator>
511 basic_string& assign(InputIterator first, InputIterator last);
512
513 basic_string& assign(initializer_list<value_type> init);
514
515 basic_string& insert(size_type pos, const basic_string& str);
516
517 basic_string& insert(size_type pos1, const basic_string& str,
518 size_type pos2, size_type n = npos);
519
520 basic_string& insert(size_type pos, const value_type* str, size_type n);
521
522 basic_string& insert(size_type pos, const value_type* str);
523
524 basic_string& insert(size_type pos, size_type n, value_type c);
525
526 iterator insert(const_iterator pos, value_type c);
527
528 iterator insert(const_iterator pos, size_type n, value_type c);
529
530 template<class InputIterator>
531 iterator insert(const_iterator pos, InputIterator first,
532 InputIterator last);
533
534 iterator insert(const_iterator pos, initializer_list<value_type>);
535
536 basic_string& erase(size_type pos = 0; size_type n = npos);
537
538 iterator erase(const_iterator pos);
539
540 iterator erase(const_iterator pos, const_iterator last);
541
542 void pop_back();
543
544 basic_string& replace(size_type pos, size_type n, const basic_string& str);
545
546 basic_string& replace(size_type pos1, size_type n1, const basic_string& str
547 size_type pos2, size_type n2);
548
549 basic_string& replace(size_type pos, size_type n1, const value_type* str,
550 size_type n2);
551
552 basic_string& replace(size_type pos, size_type n, const value_type* str);
553
554 basic_string& replace(size_type pos, size_type n1, size_type n2,
555 value_type c);
556
557 basic_string& replace(const_iterator i1, const_iterator i2,
558 const basic_string& str);
559
560 basic_string& replace(const_iterator i1, const_iterator i2,
561 const value_type* str, size_type n);
562
563 basic_string& replace(const_iterator i1, const_iterator i2,
564 const value_type* str);
565
566 basic_string& replace(const_iterator i1, const_iterator i2,
567 value_type c);
568
569 template<class InputIterator>
570 basic_string& replace(const_iterator i1, const_iterator i2,
571 InputIterator j1, InputIterator j2);
572
573 basic_string& replace(const_iterator i1, const_iterator i2,
574 initializer_list<value_type> init);
575
576 size_type copy(value_type* str, size_type n, size_type pos = 0) const;
577
578 void swap(basic_string& other)
579 noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
580 allocator_traits<allocator_type>::is_always_equal)
581 {
582 std::swap(data_, other.data_);
583 std::swap(size_, other.size_);
584 std::swap(capacity_, other.capacity_);
585 }
586
587 /**
588 * 21.4.7, string operations:
589 */
590
591 const value_type* c_str() const noexcept
592 {
593 return data_;
594 }
595
596 const value_type* data() const noexcept
597 {
598 return data_;
599 }
600
601 allocator_type get_allocator() const noexcept
602 {
603 return allocator_type{allocator_};
604 }
605
606 size_type find(const basic_string& str, size_type pos = 0) const noexcept;
607
608 size_type find(const value_type* str, size_type pos, size_type n) const;
609
610 size_type find(const value_type* str, size_type pos = 0) const;
611
612 size_type find(value_type c, size_type pos = 0) const;
613
614 size_type rfind(const basic_string& str, size_type pos = npos) const noexcept;
615
616 size_type rfind(const value_type* str, size_type pos, size_type n) const;
617
618 size_type rfind(const value_type* str, size_type pos = npos) const;
619
620 size_type rfind(value_type c, size_type pos = npos) const;
621
622 size_type find_first_of(const basic_string& str, size_type pos = 0) const noexcept;
623
624 size_type find_first_of(const value_type* str, size_type pos, size_type n) const;
625
626 size_type find_first_of(const value_type* str, size_type pos = 0) const;
627
628 size_type find_first_of(value_type c, size_type pos = 0) const;
629
630 size_type find_last_of(const basic_string& str, size_type pos = npos) const noexcept;
631
632 size_type find_last_of(const value_type* str, size_type pos, size_type n) const;
633
634 size_type find_last_of(const value_type* str, size_type pos = npos) const;
635
636 size_type find_last_of(value_type c, size_type pos = npos) const;
637
638 size_type find_first_not_of(const basic_string& str, size_type pos = 0) const noexcept;
639
640 size_type find_first_not_of(const value_type* str, size_type pos, size_type n) const;
641
642 size_type find_first_not_of(const value_type* str, size_type pos = 0) const;
643
644 size_type find_first_not_of(value_type c, size_type pos = 0) const;
645
646 size_type find_last_not_of(const basic_string& str, size_type pos = npos) const noexcept;
647
648 size_type find_last_not_of(const value_type* str, size_type pos, size_type n) const;
649
650 size_type find_last_not_of(const value_type* str, size_type pos = npos) const;
651
652 size_type find_last_not_of(value_type c, size_type pos = npos) const;
653
654 basic_string substr(size_type pos = 0, size_type n = npos) const;
655
656 int compare(const basic_string& other) const noexcept;
657
658 int compare(size_type pos, size_type n, const basic_string& other) const;
659
660 int compare(size_type pos1, size_type n1, const basic_string& other,
661 size_type pos2, size_type n2 = npos) const;
662
663 int compare(const value_type* other) const;
664
665 int compare(size_type pos, size_type n, const value_type* other) const;
666
667 int compare(size_type pos1, size_type n1,
668 const value_type* other, size_type n2) const;
669
670 private:
671 value_type* data_;
672 size_type size_;
673 size_type capacity_;
674 allocator_type allocator_;
675 };
676}
677
678#endif
Note: See TracBrowser for help on using the repository browser.