Line data Source code
1 : //
2 : // Copyright (c) 2021 Vinnie Falco (vinnie dot falco at gmail dot com)
3 : //
4 : // Distributed under the Boost Software License, Version 1.0. (See accompanying
5 : // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 : //
7 : // Official repository: https://github.com/CPPAlliance/http_proto
8 : //
9 :
10 : #ifndef BOOST_HTTP_PROTO_IMPL_FIELDS_BASE_IPP
11 : #define BOOST_HTTP_PROTO_IMPL_FIELDS_BASE_IPP
12 :
13 : #include <boost/http_proto/fields.hpp>
14 : #include <boost/http_proto/field.hpp>
15 : #include <boost/http_proto/detail/copied_strings.hpp>
16 : #include <boost/http_proto/detail/except.hpp>
17 : #include <boost/http_proto/detail/number_string.hpp>
18 : #include <boost/http_proto/detail/move_chars.hpp>
19 : #include <boost/assert.hpp>
20 : #include <boost/assert/source_location.hpp>
21 : #include <string>
22 :
23 : namespace boost {
24 : namespace http_proto {
25 :
26 : class fields_base::
27 : op_t
28 : {
29 : fields_base& self_;
30 : string_view* s0_;
31 : string_view* s1_;
32 : char* buf_ = nullptr;
33 : char const* cbuf_ = nullptr;
34 : std::size_t cap_ = 0;
35 :
36 : public:
37 : explicit
38 861 : op_t(
39 : fields_base& self,
40 : string_view* s0 = nullptr,
41 : string_view* s1 = nullptr) noexcept
42 861 : : self_(self)
43 : , s0_(s0)
44 861 : , s1_(s1)
45 : {
46 861 : }
47 :
48 861 : ~op_t()
49 861 : {
50 861 : if(buf_)
51 651 : delete[] buf_;
52 861 : }
53 :
54 : char const*
55 6 : buf() const noexcept
56 : {
57 6 : return buf_;
58 : }
59 :
60 : char const*
61 1420 : cbuf() const noexcept
62 : {
63 1420 : return cbuf_;
64 : }
65 :
66 : char*
67 9 : end() const noexcept
68 : {
69 9 : return buf_ + cap_;
70 : }
71 :
72 : table
73 3 : tab() const noexcept
74 : {
75 3 : return table(end());
76 : }
77 :
78 : static
79 : std::size_t
80 : growth(
81 : std::size_t n0,
82 : std::size_t m) noexcept;
83 :
84 : bool
85 : reserve(std::size_t bytes);
86 :
87 : bool
88 : grow(
89 : std::size_t extra_char,
90 : std::size_t extra_field);
91 :
92 : void
93 : copy_prefix(
94 : std::size_t n,
95 : std::size_t i) noexcept;
96 :
97 : void
98 : move_chars(
99 : char* dest,
100 : char const* src,
101 : std::size_t n) const noexcept;
102 : };
103 :
104 : /* Growth functions for containers
105 :
106 : N1 = g( N0, M );
107 :
108 : g = growth function
109 : M = minimum capacity
110 : N0 = old size
111 : N1 = new size
112 : */
113 : std::size_t
114 1649 : fields_base::
115 : op_t::
116 : growth(
117 : std::size_t n0,
118 : std::size_t m) noexcept
119 : {
120 1649 : auto const E = alignof(entry);
121 1649 : auto const m1 =
122 1649 : E * ((m + E - 1) / E);
123 1649 : BOOST_ASSERT(m1 >= m);
124 1649 : if(n0 == 0)
125 : {
126 : // exact
127 284 : return m1;
128 : }
129 1365 : if(m1 > n0)
130 1295 : return m1;
131 70 : return n0;
132 : }
133 :
134 : bool
135 845 : fields_base::
136 : op_t::
137 : reserve(
138 : std::size_t bytes)
139 : {
140 845 : if(bytes > max_capacity_in_bytes())
141 : {
142 : // max capacity exceeded
143 1 : detail::throw_length_error();
144 : }
145 844 : auto n = growth(
146 844 : self_.h_.cap, bytes);
147 844 : if(n <= self_.h_.cap)
148 48 : return false;
149 796 : auto buf = new char[n];
150 796 : buf_ = self_.h_.buf;
151 796 : cbuf_ = self_.h_.cbuf;
152 796 : cap_ = self_.h_.cap;
153 796 : self_.h_.buf = buf;
154 796 : self_.h_.cbuf = buf;
155 796 : self_.h_.cap = n;
156 796 : return true;
157 : }
158 :
159 : bool
160 807 : fields_base::
161 : op_t::
162 : grow(
163 : std::size_t extra_char,
164 : std::size_t extra_field)
165 : {
166 : // extra_field is naturally limited
167 : // by max_off_t, since each field
168 : // is at least 4 bytes
169 807 : BOOST_ASSERT(
170 : extra_field <= max_off_t &&
171 : extra_field <= static_cast<
172 : std::size_t>(
173 : max_off_t - self_.h_.count));
174 807 : if( extra_char > max_off_t ||
175 805 : extra_char > static_cast<std::size_t>(
176 805 : max_off_t - self_.h_.size))
177 2 : detail::throw_length_error();
178 1610 : auto n1 = growth(
179 805 : self_.h_.cap,
180 : detail::header::bytes_needed(
181 805 : self_.h_.size + extra_char,
182 805 : self_.h_.count + extra_field));
183 805 : return reserve(n1);
184 : }
185 :
186 : void
187 0 : fields_base::
188 : op_t::
189 : copy_prefix(
190 : std::size_t n,
191 : std::size_t i) noexcept
192 : {
193 : // copy first n chars
194 0 : std::memcpy(
195 0 : self_.h_.buf,
196 0 : cbuf_,
197 : n);
198 : // copy first i entries
199 0 : if(i > 0)
200 0 : std::memcpy(
201 0 : self_.h_.tab_() - i,
202 : reinterpret_cast<entry*>(
203 0 : buf_ + cap_) - i,
204 : i * sizeof(entry));
205 0 : }
206 :
207 : void
208 37 : fields_base::
209 : op_t::
210 : move_chars(
211 : char* dest,
212 : char const* src,
213 : std::size_t n) const noexcept
214 : {
215 37 : detail::move_chars(
216 37 : dest, src, n, s0_, s1_);
217 37 : }
218 :
219 : //------------------------------------------------
220 :
221 439 : fields_base::
222 : fields_base(
223 0 : detail::kind k) noexcept
224 0 : : fields_view_base(&h_)
225 439 : , h_(k)
226 : {
227 439 : }
228 :
229 : // construct a complete copy of h
230 18 : fields_base::
231 : fields_base(
232 12 : detail::header const& h)
233 12 : : fields_view_base(&h_)
234 18 : , h_(h.kind)
235 : {
236 18 : if(h.is_default())
237 : {
238 6 : BOOST_ASSERT(h.cap == 0);
239 6 : BOOST_ASSERT(h.buf == nullptr);
240 6 : h_ = h;
241 6 : return;
242 : }
243 :
244 : // allocate and copy the buffer
245 24 : op_t op(*this);
246 12 : op.grow(h.size, h.count);
247 12 : h.assign_to(h_);
248 12 : std::memcpy(
249 12 : h_.buf, h.cbuf, h.size);
250 12 : h.copy_table(h_.buf + h_.cap);
251 : }
252 :
253 : //------------------------------------------------
254 :
255 457 : fields_base::
256 469 : ~fields_base()
257 : {
258 457 : if(h_.buf)
259 395 : delete[] h_.buf;
260 457 : }
261 :
262 : //------------------------------------------------
263 : //
264 : // Capacity
265 : //
266 : //------------------------------------------------
267 :
268 : void
269 8 : fields_base::
270 : clear() noexcept
271 : {
272 8 : if(! h_.buf)
273 4 : return;
274 : using H =
275 : detail::header;
276 : auto const& h =
277 4 : *H::get_default(
278 4 : h_.kind);
279 4 : h.assign_to(h_);
280 4 : std::memcpy(
281 4 : h_.buf,
282 4 : h.cbuf,
283 4 : h_.size);
284 : }
285 :
286 : void
287 40 : fields_base::
288 : reserve_bytes(
289 : std::size_t n)
290 : {
291 41 : op_t op(*this);
292 40 : if(! op.reserve(n))
293 25 : return;
294 28 : std::memcpy(
295 14 : h_.buf, op.cbuf(), h_.size);
296 14 : auto const nt =
297 14 : sizeof(entry) * h_.count;
298 14 : if(nt > 0)
299 6 : std::memcpy(
300 6 : h_.buf + h_.cap - nt,
301 6 : op.end() - nt,
302 : nt);
303 : }
304 :
305 : void
306 7 : fields_base::
307 : shrink_to_fit() noexcept
308 : {
309 14 : if(detail::header::bytes_needed(
310 7 : h_.size, h_.count) >=
311 7 : h_.cap)
312 3 : return;
313 8 : fields_base tmp(h_);
314 4 : tmp.h_.swap(h_);
315 : }
316 :
317 : //------------------------------------------------
318 : //
319 : // Modifiers
320 : //
321 : //------------------------------------------------
322 :
323 : std::size_t
324 24 : fields_base::
325 : erase(
326 : field id) noexcept
327 : {
328 24 : BOOST_ASSERT(
329 : id != field::unknown);
330 : #if 1
331 24 : auto const end_ = end();
332 24 : auto it = find_last(end_, id);
333 24 : if(it == end_)
334 3 : return 0;
335 21 : std::size_t n = 1;
336 21 : auto const begin_ = begin();
337 21 : raw_erase(it.i_);
338 57 : while(it != begin_)
339 : {
340 36 : --it;
341 36 : if(it->id == id)
342 : {
343 25 : raw_erase(it.i_);
344 25 : ++n;
345 : }
346 : }
347 21 : h_.on_erase_all(id);
348 21 : return n;
349 : #else
350 : std::size_t n = 0;
351 : auto it0 = find(id);
352 : auto const end_ = end();
353 : if(it0 != end_)
354 : {
355 : auto it1 = it0;
356 : std::size_t total = 0;
357 : std::size_t size = 0;
358 : // [it0, it1) run of id
359 : for(;;)
360 : {
361 : size += length(it1.i_);
362 : ++it1;
363 : if(it1 == end_)
364 : goto finish;
365 : if(it1->id != id)
366 : break;
367 : }
368 : std::memmove(
369 : h_.buf + offset(it0.i_),
370 : h_.buf + offset(it1.i_),
371 : h_.size - offset(it2.i_));
372 :
373 : finish:
374 : h_.size -= size;
375 : h_.count -= n;
376 : }
377 : return n;
378 : #endif
379 : }
380 :
381 : std::size_t
382 18 : fields_base::
383 : erase(
384 : string_view name) noexcept
385 : {
386 18 : auto it0 = find(name);
387 18 : auto const end_ = end();
388 18 : if(it0 == end_)
389 3 : return 0;
390 15 : auto it = end_;
391 15 : std::size_t n = 1;
392 15 : auto const id = it0->id;
393 15 : if(id == field::unknown)
394 : {
395 : // fix self-intersection
396 6 : name = it0->name;
397 :
398 : for(;;)
399 : {
400 24 : --it;
401 24 : if(it == it0)
402 6 : break;
403 18 : if(grammar::ci_is_equal(
404 36 : it->name, name))
405 : {
406 9 : raw_erase(it.i_);
407 9 : ++n;
408 : }
409 : }
410 6 : raw_erase(it.i_);
411 : }
412 : else
413 : {
414 : for(;;)
415 : {
416 21 : --it;
417 21 : if(it == it0)
418 9 : break;
419 12 : if(it->id == id)
420 : {
421 6 : raw_erase(it.i_);
422 6 : ++n;
423 : }
424 : }
425 9 : raw_erase(it.i_);
426 9 : h_.on_erase_all(id);
427 : }
428 15 : return n;
429 : }
430 :
431 : //------------------------------------------------
432 :
433 : void
434 17 : fields_base::
435 : set(
436 : iterator it,
437 : string_view value)
438 : {
439 17 : auto const i = it.i_;
440 17 : auto const& e0 = h_.tab()[i];
441 17 : auto const pos0 = offset(i);
442 17 : auto const pos1 = offset(i + 1 );
443 : std::ptrdiff_t dn =
444 17 : value.size() -
445 17 : it->value.size();
446 17 : if( value.empty() &&
447 17 : ! it->value.empty())
448 0 : --dn; // remove SP
449 17 : else if(
450 17 : it->value.empty() &&
451 0 : ! value.empty())
452 0 : ++dn; // add SP
453 :
454 34 : op_t op(*this, &value);
455 20 : if( dn > 0 &&
456 6 : op.grow(value.size() -
457 20 : it->value.size(), 0))
458 : {
459 : // reallocated
460 3 : auto dest = h_.buf +
461 3 : pos0 + e0.nn + 1;
462 6 : std::memcpy(
463 3 : h_.buf,
464 3 : op.buf(),
465 3 : dest - h_.buf);
466 3 : if(! value.empty())
467 : {
468 3 : *dest++ = ' ';
469 3 : value.copy(
470 : dest,
471 : value.size());
472 3 : dest += value.size();
473 : }
474 3 : *dest++ = '\r';
475 3 : *dest++ = '\n';
476 6 : std::memcpy(
477 3 : h_.buf + pos1 + dn,
478 6 : op.buf() + pos1,
479 3 : h_.size - pos1);
480 6 : std::memcpy(
481 3 : h_.buf + h_.cap -
482 3 : sizeof(entry) * h_.count,
483 3 : &op.tab()[h_.count - 1],
484 3 : sizeof(entry) * h_.count);
485 : }
486 : else
487 : {
488 : // copy the value first
489 28 : auto dest = h_.buf + pos0 +
490 14 : it->name.size() + 1;
491 14 : if(! value.empty())
492 : {
493 14 : *dest++ = ' ';
494 14 : value.copy(
495 : dest,
496 : value.size());
497 14 : dest += value.size();
498 : }
499 14 : op.move_chars(
500 14 : h_.buf + pos1 + dn,
501 14 : h_.buf + pos1,
502 14 : h_.size - pos1);
503 14 : *dest++ = '\r';
504 14 : *dest++ = '\n';
505 : }
506 : {
507 : // update tab
508 17 : auto ft = h_.tab();
509 22 : for(std::size_t j = h_.count - 1;
510 22 : j > i; --j)
511 5 : ft[j] = ft[j] + dn;
512 17 : auto& e = ft[i];
513 34 : e.vp = e.np + e.nn +
514 17 : 1 + ! value.empty();
515 17 : e.vn = static_cast<
516 17 : off_t>(value.size());
517 17 : h_.size = static_cast<
518 17 : off_t>(h_.size + dn);
519 : }
520 17 : auto const id = it->id;
521 17 : if(h_.is_special(id))
522 : {
523 : // replace first char of name
524 : // with null to hide metadata
525 7 : char saved = h_.buf[pos0];
526 7 : auto& e = h_.tab()[i];
527 7 : e.id = field::unknown;
528 7 : h_.buf[pos0] = '\0';
529 7 : h_.on_erase(id);
530 7 : h_.buf[pos0] = saved;
531 7 : e.id = id;
532 7 : h_.on_insert(id, it->value);
533 : }
534 17 : }
535 :
536 : // erase existing fields with id
537 : // and then add the field with value
538 : void
539 18 : fields_base::
540 : set(
541 : field id,
542 : string_view value)
543 : {
544 18 : BOOST_ASSERT(
545 : id != field::unknown);
546 18 : auto const i0 = h_.find(id);
547 18 : if(i0 != h_.count)
548 : {
549 : // field exists
550 12 : auto const ft = h_.tab();
551 : {
552 : // provide strong guarantee
553 : auto const n0 =
554 12 : h_.size - length(i0);
555 : auto const n =
556 12 : ft[i0].nn + 2 +
557 12 : value.size() + 2;
558 : // VFALCO missing overflow check
559 12 : reserve_bytes(n0 + n);
560 : }
561 12 : erase_all_impl(i0, id);
562 : }
563 18 : insert_impl(id, to_string(id),
564 18 : value, h_.count);
565 18 : }
566 :
567 : // erase existing fields with name
568 : // and then add the field with value
569 : void
570 13 : fields_base::
571 : set(
572 : string_view name,
573 : string_view value)
574 : {
575 13 : auto const i0 = h_.find(name);
576 13 : if(i0 != h_.count)
577 : {
578 : // field exists
579 9 : auto const ft = h_.tab();
580 9 : auto const id = ft[i0].id;
581 : {
582 : // provide strong guarantee
583 : auto const n0 =
584 9 : h_.size - length(i0);
585 : auto const n =
586 9 : ft[i0].nn + 2 +
587 9 : value.size() + 2;
588 : // VFALCO missing overflow check
589 9 : reserve_bytes(n0 + n);
590 : }
591 : // VFALCO simple algorithm but
592 : // costs one extra memmove
593 9 : erase_all_impl(i0, id);
594 : }
595 13 : insert_impl(
596 : string_to_field(name),
597 13 : name, value, h_.count);
598 12 : }
599 :
600 : //------------------------------------------------
601 : //
602 : // (implementation)
603 : //
604 : //------------------------------------------------
605 :
606 : // copy start line and fields
607 : void
608 9 : fields_base::
609 : copy_impl(
610 : detail::header const& h)
611 : {
612 9 : BOOST_ASSERT(
613 : h.kind == ph_->kind);
614 9 : if(! h.is_default())
615 : {
616 : auto const n =
617 6 : detail::header::bytes_needed(
618 6 : h.size, h.count);
619 6 : if(n <= h_.cap)
620 : {
621 : // no realloc
622 1 : h.assign_to(h_);
623 1 : h.copy_table(
624 1 : h_.buf + h_.cap);
625 1 : std::memcpy(
626 1 : h_.buf,
627 1 : h.cbuf,
628 1 : h.size);
629 1 : return;
630 : }
631 : }
632 16 : fields_base tmp(h);
633 8 : tmp.h_.swap(h_);
634 : }
635 :
636 : void
637 792 : fields_base::
638 : insert_impl(
639 : field id,
640 : string_view name,
641 : string_view value,
642 : std::size_t before)
643 : {
644 792 : auto const tab0 = h_.tab_();
645 792 : auto const pos = offset(before);
646 : auto const n =
647 792 : name.size() + // name
648 792 : 1 + // ':'
649 792 : ! value.empty() + // [SP]
650 792 : value.size() + // value
651 792 : 2; // CRLF
652 :
653 1584 : op_t op(*this, &name, &value);
654 792 : if(op.grow(n, 1))
655 : {
656 : // reallocated
657 767 : if(pos > 0)
658 639 : std::memcpy(
659 639 : h_.buf,
660 639 : op.cbuf(),
661 : pos);
662 767 : if(before > 0)
663 814 : std::memcpy(
664 407 : h_.tab_() - before,
665 407 : tab0 - before,
666 : before * sizeof(entry));
667 1534 : std::memcpy(
668 767 : h_.buf + pos + n,
669 767 : op.cbuf() + pos,
670 767 : h_.size - pos);
671 : }
672 : else
673 : {
674 23 : op.move_chars(
675 23 : h_.buf + pos + n,
676 23 : h_.buf + pos,
677 23 : h_.size - pos);
678 : }
679 :
680 : // serialize
681 : {
682 790 : auto dest = h_.buf + pos;
683 790 : name.copy(dest, name.size());
684 790 : dest += name.size();
685 790 : *dest++ = ':';
686 790 : if(! value.empty())
687 : {
688 723 : *dest++ = ' ';
689 723 : value.copy(
690 : dest, value.size());
691 723 : dest += value.size();
692 : }
693 790 : *dest++ = '\r';
694 790 : *dest = '\n';
695 : }
696 :
697 : // update table
698 790 : auto const tab = h_.tab_();
699 : {
700 790 : auto i = h_.count - before;
701 790 : if(i > 0)
702 : {
703 18 : auto p0 = tab0 - h_.count;
704 18 : auto p = tab - h_.count - 1;
705 18 : do
706 : {
707 36 : *p++ = *p0++ + n;
708 : }
709 36 : while(--i);
710 : }
711 : }
712 790 : auto& e = tab[0 - before - 1];
713 790 : e.np = static_cast<off_t>(
714 790 : pos - h_.prefix);
715 790 : e.nn = static_cast<
716 790 : off_t>(name.size());
717 790 : e.vp = static_cast<off_t>(
718 1580 : pos - h_.prefix +
719 790 : name.size() + 1 +
720 790 : ! value.empty());
721 790 : e.vn = static_cast<
722 790 : off_t>(value.size());
723 790 : e.id = id;
724 :
725 : // update container
726 790 : h_.count++;
727 790 : h_.size = static_cast<
728 790 : off_t>(h_.size + n);
729 790 : if( id != field::unknown)
730 614 : h_.on_insert(id, value);
731 790 : }
732 :
733 : // erase i and update metadata
734 : void
735 31 : fields_base::
736 : erase_impl(
737 : std::size_t i,
738 : field id) noexcept
739 : {
740 31 : raw_erase(i);
741 31 : if(id != field::unknown)
742 31 : h_.on_erase(id);
743 31 : }
744 :
745 : //------------------------------------------------
746 :
747 : void
748 141 : fields_base::
749 : raw_erase(
750 : std::size_t i) noexcept
751 : {
752 141 : BOOST_ASSERT(i < h_.count);
753 141 : BOOST_ASSERT(h_.buf != nullptr);
754 141 : auto const p0 = offset(i);
755 141 : auto const p1 = offset(i + 1);
756 141 : std::memmove(
757 141 : h_.buf + p0,
758 141 : h_.buf + p1,
759 141 : h_.size - p1);
760 141 : auto const n = p1 - p0;
761 141 : --h_.count;
762 141 : auto ft = h_.tab();
763 216 : for(;i < h_.count; ++i)
764 75 : ft[i] = ft[i + 1] - n;
765 141 : h_.size = static_cast<
766 141 : off_t>(h_.size - n);
767 141 : }
768 :
769 : //------------------------------------------------
770 :
771 : // erase all fields with id
772 : // and update metadata
773 : std::size_t
774 21 : fields_base::
775 : erase_all_impl(
776 : std::size_t i0,
777 : field id) noexcept
778 : {
779 21 : BOOST_ASSERT(
780 : id != field::unknown);
781 21 : std::size_t n = 1;
782 21 : std::size_t i = h_.count - 1;
783 21 : auto const ft = h_.tab();
784 46 : while(i > i0)
785 : {
786 25 : if(ft[i].id == id)
787 : {
788 13 : raw_erase(i);
789 13 : ++n;
790 : }
791 : // go backwards to
792 : // reduce memmoves
793 25 : --i;
794 : }
795 21 : raw_erase(i0);
796 21 : h_.on_erase_all(id);
797 21 : return n;
798 : }
799 :
800 : // return i-th field absolute offset
801 : std::size_t
802 1150 : fields_base::
803 : offset(
804 : std::size_t i) const noexcept
805 : {
806 1150 : if(i == 0)
807 464 : return h_.prefix;
808 686 : if(i < h_.count)
809 348 : return h_.prefix +
810 174 : h_.tab_()[0-(i + 1)].np;
811 : // make final CRLF the last "field"
812 : //BOOST_ASSERT(i == h_.count);
813 512 : return h_.size - 2;
814 : }
815 :
816 : // return i-th field absolute length
817 : std::size_t
818 21 : fields_base::
819 : length(
820 : std::size_t i) const noexcept
821 : {
822 : return
823 21 : offset(i + 1) -
824 21 : offset(i);
825 : }
826 :
827 : //------------------------------------------------
828 :
829 : // erase n fields matching id
830 : // without updating metadata
831 : void
832 0 : fields_base::
833 : raw_erase_n(
834 : field id,
835 : std::size_t n) noexcept
836 : {
837 : // iterate in reverse
838 0 : auto e = &h_.tab()[h_.count];
839 0 : auto const e0 = &h_.tab()[0];
840 0 : while(n > 0)
841 : {
842 0 : BOOST_ASSERT(e != e0);
843 0 : ++e; // decrement
844 0 : if(e->id == id)
845 : {
846 0 : raw_erase(e0 - e);
847 0 : --n;
848 : }
849 : }
850 0 : }
851 :
852 : } // http_proto
853 : } // boost
854 :
855 : #endif
|
