1// Copyright 2013 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "net/tools/balsa/balsa_headers.h"
6
7#include <stdio.h>
8#include <algorithm>
9#include <string>
10#include <utility>
11#include <vector>
12
13#include "base/containers/hash_tables.h"
14#include "base/logging.h"
15#include "base/port.h"
16#include "base/strings/string_piece.h"
17#include "base/strings/stringprintf.h"
18#include "net/tools/balsa/balsa_enums.h"
19#include "net/tools/balsa/buffer_interface.h"
20#include "net/tools/balsa/simple_buffer.h"
21#include "third_party/tcmalloc/chromium/src/base/googleinit.h"
22
23#if defined(COMPILER_MSVC)
24#include <string.h>
25#define snprintf _snprintf
26#define strncasecmp _strnicmp
27#else
28#include <strings.h>
29#endif
30
31namespace {
32
33const char kContentLength[] = "Content-Length";
34const char kTransferEncoding[] = "Transfer-Encoding";
35const char kSpaceChar = ' ';
36
37#if defined(COMPILER_MSVC)
38base::hash_set<base::StringPiece,
39               net::StringPieceCaseCompare> g_multivalued_headers;
40#else
41base::hash_set<base::StringPiece,
42               net::StringPieceCaseHash,
43               net::StringPieceCaseEqual> g_multivalued_headers;
44#endif
45
46void InitMultivaluedHeaders() {
47  g_multivalued_headers.insert("accept");
48  g_multivalued_headers.insert("accept-charset");
49  g_multivalued_headers.insert("accept-encoding");
50  g_multivalued_headers.insert("accept-language");
51  g_multivalued_headers.insert("accept-ranges");
52  g_multivalued_headers.insert("allow");
53  g_multivalued_headers.insert("cache-control");
54  g_multivalued_headers.insert("connection");
55  g_multivalued_headers.insert("content-encoding");
56  g_multivalued_headers.insert("content-language");
57  g_multivalued_headers.insert("expect");
58  g_multivalued_headers.insert("if-match");
59  g_multivalued_headers.insert("if-none-match");
60  g_multivalued_headers.insert("pragma");
61  g_multivalued_headers.insert("proxy-authenticate");
62  g_multivalued_headers.insert("te");
63  g_multivalued_headers.insert("trailer");
64  g_multivalued_headers.insert("transfer-encoding");
65  g_multivalued_headers.insert("upgrade");
66  g_multivalued_headers.insert("vary");
67  g_multivalued_headers.insert("via");
68  g_multivalued_headers.insert("warning");
69  g_multivalued_headers.insert("www-authenticate");
70  // Not mentioned in RFC 2616, but it can have multiple values.
71  g_multivalued_headers.insert("set-cookie");
72}
73
74REGISTER_MODULE_INITIALIZER(multivalued_headers, InitMultivaluedHeaders());
75
76const int kFastToBufferSize = 32;  // I think 22 is adequate, but anyway..
77
78}  // namespace
79
80namespace net {
81
82BalsaHeaders::iterator_base::iterator_base() : headers_(NULL), idx_(0) { }
83
84BalsaHeaders::iterator_base::iterator_base(const iterator_base& it)
85    : headers_(it.headers_),
86      idx_(it.idx_) {
87}
88
89std::ostream& BalsaHeaders::iterator_base::operator<<(std::ostream& os) const {
90  os << "[" << this->headers_ << ", " << this->idx_ << "]";
91  return os;
92}
93
94BalsaHeaders::iterator_base::iterator_base(const BalsaHeaders* headers,
95                                           HeaderLines::size_type index)
96    : headers_(headers),
97      idx_(index) {
98}
99
100BalsaBuffer::~BalsaBuffer() {
101  CleanupBlocksStartingFrom(0);
102}
103
104// Returns the total amount of memory used by the buffer blocks.
105size_t BalsaBuffer::GetTotalBufferBlockSize() const {
106  size_t buffer_size = 0;
107  for (Blocks::const_iterator iter = blocks_.begin();
108       iter != blocks_.end();
109       ++iter) {
110    buffer_size += iter->buffer_size;
111  }
112  return buffer_size;
113}
114
115void BalsaBuffer::WriteToContiguousBuffer(const base::StringPiece& sp) {
116  if (sp.empty()) {
117    return;
118  }
119  CHECK(can_write_to_contiguous_buffer_);
120  DCHECK_GE(blocks_.size(), 1u);
121  if (blocks_[0].buffer == NULL && sp.size() <= blocksize_) {
122    blocks_[0] = AllocBlock();
123    memcpy(blocks_[0].start_of_unused_bytes(), sp.data(), sp.size());
124  } else if (blocks_[0].bytes_free < sp.size()) {
125    // the first block isn't big enough, resize it.
126    const size_t old_storage_size_used = blocks_[0].bytes_used();
127    const size_t new_storage_size = old_storage_size_used + sp.size();
128    char* new_storage = new char[new_storage_size];
129    char* old_storage = blocks_[0].buffer;
130    if (old_storage_size_used) {
131      memcpy(new_storage, old_storage, old_storage_size_used);
132    }
133    memcpy(new_storage + old_storage_size_used, sp.data(), sp.size());
134    blocks_[0].buffer = new_storage;
135    blocks_[0].bytes_free = sp.size();
136    blocks_[0].buffer_size = new_storage_size;
137    delete[] old_storage;
138  } else {
139    memcpy(blocks_[0].start_of_unused_bytes(), sp.data(), sp.size());
140  }
141  blocks_[0].bytes_free -= sp.size();
142}
143
144base::StringPiece BalsaBuffer::Write(const base::StringPiece& sp,
145                                     Blocks::size_type* block_buffer_idx) {
146  if (sp.empty()) {
147    return sp;
148  }
149  char* storage = Reserve(sp.size(), block_buffer_idx);
150  memcpy(storage, sp.data(), sp.size());
151  return base::StringPiece(storage, sp.size());
152}
153
154char* BalsaBuffer::Reserve(size_t size,
155                           Blocks::size_type* block_buffer_idx) {
156  // There should always be a 'first_block', even if it
157  // contains nothing.
158  DCHECK_GE(blocks_.size(), 1u);
159  BufferBlock* block = NULL;
160  Blocks::size_type block_idx = can_write_to_contiguous_buffer_ ? 1 : 0;
161  for (; block_idx < blocks_.size(); ++block_idx) {
162    if (blocks_[block_idx].bytes_free >= size) {
163      block = &blocks_[block_idx];
164      break;
165    }
166  }
167  if (block == NULL) {
168    if (blocksize_ < size) {
169      blocks_.push_back(AllocCustomBlock(size));
170    } else {
171      blocks_.push_back(AllocBlock());
172    }
173    block = &blocks_.back();
174  }
175
176  char* storage = block->start_of_unused_bytes();
177  block->bytes_free -= size;
178  if (block_buffer_idx) {
179    *block_buffer_idx = block_idx;
180  }
181  return storage;
182}
183
184void BalsaBuffer::Clear() {
185  CHECK(!blocks_.empty());
186  if (blocksize_ == blocks_[0].buffer_size) {
187    CleanupBlocksStartingFrom(1);
188    blocks_[0].bytes_free = blocks_[0].buffer_size;
189  } else {
190    CleanupBlocksStartingFrom(0);
191    blocks_.push_back(AllocBlock());
192  }
193  DCHECK_GE(blocks_.size(), 1u);
194  can_write_to_contiguous_buffer_ = true;
195}
196
197void BalsaBuffer::Swap(BalsaBuffer* b) {
198  blocks_.swap(b->blocks_);
199  std::swap(can_write_to_contiguous_buffer_,
200            b->can_write_to_contiguous_buffer_);
201  std::swap(blocksize_, b->blocksize_);
202}
203
204void BalsaBuffer::CopyFrom(const BalsaBuffer& b) {
205  CleanupBlocksStartingFrom(0);
206  blocks_.resize(b.blocks_.size());
207  for (Blocks::size_type i = 0; i < blocks_.size(); ++i) {
208    blocks_[i] = CopyBlock(b.blocks_[i]);
209  }
210  blocksize_ = b.blocksize_;
211  can_write_to_contiguous_buffer_ = b.can_write_to_contiguous_buffer_;
212}
213
214BalsaBuffer::BalsaBuffer()
215    : blocksize_(kDefaultBlocksize), can_write_to_contiguous_buffer_(true) {
216  blocks_.push_back(AllocBlock());
217}
218
219BalsaBuffer::BalsaBuffer(size_t blocksize) :
220    blocksize_(blocksize), can_write_to_contiguous_buffer_(true) {
221  blocks_.push_back(AllocBlock());
222}
223
224BalsaBuffer::BufferBlock BalsaBuffer::AllocBlock() {
225  return AllocCustomBlock(blocksize_);
226}
227
228BalsaBuffer::BufferBlock BalsaBuffer::AllocCustomBlock(size_t blocksize) {
229  return BufferBlock(new char[blocksize], blocksize, blocksize);
230}
231
232BalsaBuffer::BufferBlock BalsaBuffer::CopyBlock(const BufferBlock& b) {
233  BufferBlock block = b;
234  if (b.buffer == NULL) {
235    return block;
236  }
237
238  block.buffer = new char[b.buffer_size];
239  memcpy(block.buffer, b.buffer, b.bytes_used());
240  return block;
241}
242
243void BalsaBuffer::CleanupBlocksStartingFrom(Blocks::size_type start_idx) {
244  for (Blocks::size_type i = start_idx; i < blocks_.size(); ++i) {
245    delete[] blocks_[i].buffer;
246  }
247  blocks_.resize(start_idx);
248}
249
250BalsaHeaders::const_header_lines_key_iterator::const_header_lines_key_iterator(
251    const const_header_lines_key_iterator& other)
252    : iterator_base(other),
253      key_(other.key_) {
254}
255
256BalsaHeaders::const_header_lines_key_iterator::const_header_lines_key_iterator(
257    const BalsaHeaders* headers,
258    HeaderLines::size_type index,
259    const base::StringPiece& key)
260    : iterator_base(headers, index),
261      key_(key) {
262}
263
264BalsaHeaders::const_header_lines_key_iterator::const_header_lines_key_iterator(
265    const BalsaHeaders* headers,
266    HeaderLines::size_type index)
267    : iterator_base(headers, index) {
268}
269
270BalsaHeaders::BalsaHeaders()
271    : balsa_buffer_(4096),
272      content_length_(0),
273      content_length_status_(BalsaHeadersEnums::NO_CONTENT_LENGTH),
274      parsed_response_code_(0),
275      firstline_buffer_base_idx_(0),
276      whitespace_1_idx_(0),
277      non_whitespace_1_idx_(0),
278      whitespace_2_idx_(0),
279      non_whitespace_2_idx_(0),
280      whitespace_3_idx_(0),
281      non_whitespace_3_idx_(0),
282      whitespace_4_idx_(0),
283      end_of_firstline_idx_(0),
284      transfer_encoding_is_chunked_(false) {
285}
286
287BalsaHeaders::~BalsaHeaders() {}
288
289void BalsaHeaders::Clear() {
290  balsa_buffer_.Clear();
291  transfer_encoding_is_chunked_ = false;
292  content_length_ = 0;
293  content_length_status_ = BalsaHeadersEnums::NO_CONTENT_LENGTH;
294  parsed_response_code_ = 0;
295  firstline_buffer_base_idx_ = 0;
296  whitespace_1_idx_ = 0;
297  non_whitespace_1_idx_ = 0;
298  whitespace_2_idx_ = 0;
299  non_whitespace_2_idx_ = 0;
300  whitespace_3_idx_ = 0;
301  non_whitespace_3_idx_ = 0;
302  whitespace_4_idx_ = 0;
303  end_of_firstline_idx_ = 0;
304  header_lines_.clear();
305}
306
307void BalsaHeaders::Swap(BalsaHeaders* other) {
308  // Protect against swapping with self.
309  if (this == other) return;
310
311  balsa_buffer_.Swap(&other->balsa_buffer_);
312
313  bool tmp_bool = transfer_encoding_is_chunked_;
314  transfer_encoding_is_chunked_ = other->transfer_encoding_is_chunked_;
315  other->transfer_encoding_is_chunked_ = tmp_bool;
316
317  size_t tmp_size_t = content_length_;
318  content_length_ = other->content_length_;
319  other->content_length_ = tmp_size_t;
320
321  BalsaHeadersEnums::ContentLengthStatus tmp_status =
322      content_length_status_;
323  content_length_status_ = other->content_length_status_;
324  other->content_length_status_ = tmp_status;
325
326  tmp_size_t = parsed_response_code_;
327  parsed_response_code_ = other->parsed_response_code_;
328  other->parsed_response_code_ = tmp_size_t;
329
330  BalsaBuffer::Blocks::size_type tmp_blk_idx = firstline_buffer_base_idx_;
331  firstline_buffer_base_idx_ = other->firstline_buffer_base_idx_;
332  other->firstline_buffer_base_idx_ = tmp_blk_idx;
333
334  tmp_size_t = whitespace_1_idx_;
335  whitespace_1_idx_ = other->whitespace_1_idx_;
336  other->whitespace_1_idx_ = tmp_size_t;
337
338  tmp_size_t = non_whitespace_1_idx_;
339  non_whitespace_1_idx_ = other->non_whitespace_1_idx_;
340  other->non_whitespace_1_idx_ = tmp_size_t;
341
342  tmp_size_t = whitespace_2_idx_;
343  whitespace_2_idx_ = other->whitespace_2_idx_;
344  other->whitespace_2_idx_ = tmp_size_t;
345
346  tmp_size_t = non_whitespace_2_idx_;
347  non_whitespace_2_idx_ = other->non_whitespace_2_idx_;
348  other->non_whitespace_2_idx_ = tmp_size_t;
349
350  tmp_size_t = whitespace_3_idx_;
351  whitespace_3_idx_ = other->whitespace_3_idx_;
352  other->whitespace_3_idx_ = tmp_size_t;
353
354  tmp_size_t = non_whitespace_3_idx_;
355  non_whitespace_3_idx_ = other->non_whitespace_3_idx_;
356  other->non_whitespace_3_idx_ = tmp_size_t;
357
358  tmp_size_t = whitespace_4_idx_;
359  whitespace_4_idx_ = other->whitespace_4_idx_;
360  other->whitespace_4_idx_ = tmp_size_t;
361
362  tmp_size_t = end_of_firstline_idx_;
363  end_of_firstline_idx_ = other->end_of_firstline_idx_;
364  other->end_of_firstline_idx_ = tmp_size_t;
365
366  swap(header_lines_, other->header_lines_);
367}
368
369void BalsaHeaders::CopyFrom(const BalsaHeaders& other) {
370  // Protect against copying with self.
371  if (this == &other) return;
372
373  balsa_buffer_.CopyFrom(other.balsa_buffer_);
374  transfer_encoding_is_chunked_ = other.transfer_encoding_is_chunked_;
375  content_length_ = other.content_length_;
376  content_length_status_ = other.content_length_status_;
377  parsed_response_code_ = other.parsed_response_code_;
378  firstline_buffer_base_idx_ = other.firstline_buffer_base_idx_;
379  whitespace_1_idx_ = other.whitespace_1_idx_;
380  non_whitespace_1_idx_ = other.non_whitespace_1_idx_;
381  whitespace_2_idx_ = other.whitespace_2_idx_;
382  non_whitespace_2_idx_ = other.non_whitespace_2_idx_;
383  whitespace_3_idx_ = other.whitespace_3_idx_;
384  non_whitespace_3_idx_ = other.non_whitespace_3_idx_;
385  whitespace_4_idx_ = other.whitespace_4_idx_;
386  end_of_firstline_idx_ = other.end_of_firstline_idx_;
387  header_lines_ = other.header_lines_;
388}
389
390void BalsaHeaders::AddAndMakeDescription(const base::StringPiece& key,
391                                         const base::StringPiece& value,
392                                         HeaderLineDescription* d) {
393  CHECK(d != NULL);
394  // + 2 to size for ": "
395  size_t line_size = key.size() + 2 + value.size();
396  BalsaBuffer::Blocks::size_type block_buffer_idx = 0;
397  char* storage = balsa_buffer_.Reserve(line_size, &block_buffer_idx);
398  size_t base_idx = storage - GetPtr(block_buffer_idx);
399
400  char* cur_loc = storage;
401  memcpy(cur_loc, key.data(), key.size());
402  cur_loc += key.size();
403  *cur_loc = ':';
404  ++cur_loc;
405  *cur_loc = ' ';
406  ++cur_loc;
407  memcpy(cur_loc, value.data(), value.size());
408  *d = HeaderLineDescription(base_idx,
409                             base_idx + key.size(),
410                             base_idx + key.size() + 2,
411                             base_idx + key.size() + 2 + value.size(),
412                             block_buffer_idx);
413}
414
415void BalsaHeaders::AppendOrPrependAndMakeDescription(
416    const base::StringPiece& key,
417    const base::StringPiece& value,
418    bool append,
419    HeaderLineDescription* d) {
420  // Figure out how much space we need to reserve for the new header size.
421  size_t old_value_size = d->last_char_idx - d->value_begin_idx;
422  if (old_value_size == 0) {
423    AddAndMakeDescription(key, value, d);
424    return;
425  }
426  base::StringPiece old_value(GetPtr(d->buffer_base_idx) + d->value_begin_idx,
427                        old_value_size);
428
429  BalsaBuffer::Blocks::size_type block_buffer_idx = 0;
430  // + 3 because we potentially need to add ": ", and "," to the line.
431  size_t new_size = key.size() + 3 + old_value_size + value.size();
432  char* storage = balsa_buffer_.Reserve(new_size, &block_buffer_idx);
433  size_t base_idx = storage - GetPtr(block_buffer_idx);
434
435  base::StringPiece first_value = old_value;
436  base::StringPiece second_value = value;
437  if (!append) {  // !append == prepend
438    first_value = value;
439    second_value = old_value;
440  }
441  char* cur_loc = storage;
442  memcpy(cur_loc, key.data(), key.size());
443  cur_loc += key.size();
444  *cur_loc = ':';
445  ++cur_loc;
446  *cur_loc = ' ';
447  ++cur_loc;
448  memcpy(cur_loc, first_value.data(), first_value.size());
449  cur_loc += first_value.size();
450  *cur_loc = ',';
451  ++cur_loc;
452  memcpy(cur_loc, second_value.data(), second_value.size());
453
454  *d = HeaderLineDescription(base_idx,
455                             base_idx + key.size(),
456                             base_idx + key.size() + 2,
457                             base_idx + new_size,
458                             block_buffer_idx);
459}
460
461// Removes all keys value pairs with key 'key' starting at 'start'.
462void BalsaHeaders::RemoveAllOfHeaderStartingAt(const base::StringPiece& key,
463                                               HeaderLines::iterator start) {
464  while (start != header_lines_.end()) {
465    start->skip = true;
466    ++start;
467    start = GetHeaderLinesIterator(key, start);
468  }
469}
470
471void BalsaHeaders::HackHeader(const base::StringPiece& key,
472                              const base::StringPiece& value) {
473  // See TODO in balsa_headers.h
474  const HeaderLines::iterator end = header_lines_.end();
475  const HeaderLines::iterator begin = header_lines_.begin();
476  HeaderLines::iterator i = GetHeaderLinesIteratorNoSkip(key, begin);
477  if (i != end) {
478    // First, remove all of the header lines including this one.  We want to
479    // remove before replacing, in case our replacement ends up being appended
480    // at the end (and thus would be removed by this call)
481    RemoveAllOfHeaderStartingAt(key, i);
482    // Now add the replacement, at this location.
483    AddAndMakeDescription(key, value, &(*i));
484    return;
485  }
486  AppendHeader(key, value);
487}
488
489void BalsaHeaders::HackAppendToHeader(const base::StringPiece& key,
490                                      const base::StringPiece& append_value) {
491  // See TODO in balsa_headers.h
492  const HeaderLines::iterator end = header_lines_.end();
493  const HeaderLines::iterator begin = header_lines_.begin();
494
495  HeaderLines::iterator i = GetHeaderLinesIterator(key, begin);
496  if (i == end) {
497    HackHeader(key, append_value);
498    return;
499  }
500
501  AppendOrPrependAndMakeDescription(key, append_value, true, &(*i));
502}
503
504void BalsaHeaders::ReplaceOrAppendHeader(const base::StringPiece& key,
505                                         const base::StringPiece& value) {
506  const HeaderLines::iterator end = header_lines_.end();
507  const HeaderLines::iterator begin = header_lines_.begin();
508  HeaderLines::iterator i = GetHeaderLinesIterator(key, begin);
509  if (i != end) {
510    // First, remove all of the header lines including this one.  We want to
511    // remove before replacing, in case our replacement ends up being appended
512    // at the end (and thus would be removed by this call)
513    RemoveAllOfHeaderStartingAt(key, i);
514    // Now, take the first instance and replace it.  This will remove the
515    // 'skipped' tag if the replacement is done in-place.
516    AddAndMakeDescription(key, value, &(*i));
517    return;
518  }
519  AppendHeader(key, value);
520}
521
522void BalsaHeaders::AppendHeader(const base::StringPiece& key,
523                                const base::StringPiece& value) {
524  HeaderLineDescription hld;
525  AddAndMakeDescription(key, value, &hld);
526  header_lines_.push_back(hld);
527}
528
529void BalsaHeaders::AppendToHeader(const base::StringPiece& key,
530                                  const base::StringPiece& value) {
531  AppendOrPrependToHeader(key, value, true);
532}
533
534void BalsaHeaders::PrependToHeader(const base::StringPiece& key,
535                                   const base::StringPiece& value) {
536  AppendOrPrependToHeader(key, value, false);
537}
538
539base::StringPiece BalsaHeaders::GetValueFromHeaderLineDescription(
540    const HeaderLineDescription& line) const {
541  DCHECK_GE(line.last_char_idx, line.value_begin_idx);
542  return base::StringPiece(GetPtr(line.buffer_base_idx) + line.value_begin_idx,
543                     line.last_char_idx - line.value_begin_idx);
544}
545
546const base::StringPiece BalsaHeaders::GetHeader(
547    const base::StringPiece& key) const {
548  DCHECK(!IsMultivaluedHeader(key))
549      << "Header '" << key << "' may consist of multiple lines. Do not "
550      << "use BalsaHeaders::GetHeader() or you may be missing some of its "
551      << "values.";
552  const HeaderLines::const_iterator end = header_lines_.end();
553  const HeaderLines::const_iterator begin = header_lines_.begin();
554  HeaderLines::const_iterator i = GetConstHeaderLinesIterator(key, begin);
555  if (i == end) {
556    return base::StringPiece();
557  }
558  return GetValueFromHeaderLineDescription(*i);
559}
560
561BalsaHeaders::const_header_lines_iterator BalsaHeaders::GetHeaderPosition(
562    const base::StringPiece& key) const {
563  const HeaderLines::const_iterator end = header_lines_.end();
564  const HeaderLines::const_iterator begin = header_lines_.begin();
565  HeaderLines::const_iterator i = GetConstHeaderLinesIterator(key, begin);
566  if (i == end) {
567    return header_lines_end();
568  }
569
570  return const_header_lines_iterator(this, (i - begin));
571}
572
573BalsaHeaders::const_header_lines_key_iterator BalsaHeaders::GetIteratorForKey(
574    const base::StringPiece& key) const {
575  HeaderLines::const_iterator i =
576      GetConstHeaderLinesIterator(key, header_lines_.begin());
577  if (i == header_lines_.end()) {
578    return header_lines_key_end();
579  }
580
581  const HeaderLines::const_iterator begin = header_lines_.begin();
582  return const_header_lines_key_iterator(this, (i - begin), key);
583}
584
585void BalsaHeaders::AppendOrPrependToHeader(const base::StringPiece& key,
586                                           const base::StringPiece& value,
587                                           bool append) {
588  HeaderLines::iterator i = GetHeaderLinesIterator(key, header_lines_.begin());
589  if (i == header_lines_.end()) {
590    // The header did not exist already.  Instead of appending to an existing
591    // header simply append the key/value pair to the headers.
592    AppendHeader(key, value);
593    return;
594  }
595  HeaderLineDescription hld = *i;
596
597  AppendOrPrependAndMakeDescription(key, value, append, &hld);
598
599  // Invalidate the old header line and add the new one.
600  i->skip = true;
601  header_lines_.push_back(hld);
602}
603
604BalsaHeaders::HeaderLines::const_iterator
605BalsaHeaders::GetConstHeaderLinesIterator(
606    const base::StringPiece& key,
607    BalsaHeaders::HeaderLines::const_iterator start) const {
608  const HeaderLines::const_iterator end = header_lines_.end();
609  for (HeaderLines::const_iterator i = start; i != end; ++i) {
610    const HeaderLineDescription& line = *i;
611    if (line.skip) {
612      continue;
613    }
614    const size_t key_len = line.key_end_idx - line.first_char_idx;
615
616    if (key_len != key.size()) {
617      continue;
618    }
619    if (strncasecmp(GetPtr(line.buffer_base_idx) + line.first_char_idx,
620                    key.data(), key_len) == 0) {
621      DCHECK_GE(line.last_char_idx, line.value_begin_idx);
622      return i;
623    }
624  }
625  return end;
626}
627
628BalsaHeaders::HeaderLines::iterator BalsaHeaders::GetHeaderLinesIteratorNoSkip(
629    const base::StringPiece& key,
630    BalsaHeaders::HeaderLines::iterator start) {
631  const HeaderLines::iterator end = header_lines_.end();
632  for (HeaderLines::iterator i = start; i != end; ++i) {
633    const HeaderLineDescription& line = *i;
634    const size_t key_len = line.key_end_idx - line.first_char_idx;
635
636    if (key_len != key.size()) {
637      continue;
638    }
639    if (strncasecmp(GetPtr(line.buffer_base_idx) + line.first_char_idx,
640                    key.data(), key_len) == 0) {
641      DCHECK_GE(line.last_char_idx, line.value_begin_idx);
642      return i;
643    }
644  }
645  return end;
646}
647
648BalsaHeaders::HeaderLines::iterator BalsaHeaders::GetHeaderLinesIterator(
649    const base::StringPiece& key,
650    BalsaHeaders::HeaderLines::iterator start) {
651  const HeaderLines::iterator end = header_lines_.end();
652  for (HeaderLines::iterator i = start; i != end; ++i) {
653    const HeaderLineDescription& line = *i;
654    if (line.skip) {
655      continue;
656    }
657    const size_t key_len = line.key_end_idx - line.first_char_idx;
658
659    if (key_len != key.size()) {
660      continue;
661    }
662    if (strncasecmp(GetPtr(line.buffer_base_idx) + line.first_char_idx,
663                    key.data(), key_len) == 0) {
664      DCHECK_GE(line.last_char_idx, line.value_begin_idx);
665      return i;
666    }
667  }
668  return end;
669}
670
671void BalsaHeaders::GetAllOfHeader(
672    const base::StringPiece& key, std::vector<base::StringPiece>* out) const {
673  for (const_header_lines_key_iterator it = GetIteratorForKey(key);
674       it != header_lines_end(); ++it) {
675    out->push_back(it->second);
676  }
677}
678
679bool BalsaHeaders::HasNonEmptyHeader(const base::StringPiece& key) const {
680  for (const_header_lines_key_iterator it = GetIteratorForKey(key);
681       it != header_lines_key_end(); ++it) {
682    if (!it->second.empty())
683      return true;
684  }
685  return false;
686}
687
688void BalsaHeaders::GetAllOfHeaderAsString(const base::StringPiece& key,
689                                          std::string* out) const {
690  const_header_lines_iterator it = header_lines_begin();
691  const_header_lines_iterator end = header_lines_end();
692
693  for (; it != end; ++it) {
694    if (key == it->first) {
695      if (!out->empty()) {
696        out->append(",");
697      }
698      out->append(std::string(it->second.data(), it->second.size()));
699    }
700  }
701}
702
703// static
704bool BalsaHeaders::IsMultivaluedHeader(const base::StringPiece& header) {
705  return g_multivalued_headers.find(header) != g_multivalued_headers.end();
706}
707
708void BalsaHeaders::RemoveAllOfHeader(const base::StringPiece& key) {
709  HeaderLines::iterator it = GetHeaderLinesIterator(key, header_lines_.begin());
710  RemoveAllOfHeaderStartingAt(key, it);
711}
712
713void BalsaHeaders::RemoveAllHeadersWithPrefix(const base::StringPiece& key) {
714  for (HeaderLines::size_type i = 0; i < header_lines_.size(); ++i) {
715    if (header_lines_[i].skip) {
716      continue;
717    }
718    HeaderLineDescription& line = header_lines_[i];
719    const size_t key_len = line.key_end_idx - line.first_char_idx;
720    if (key_len < key.size()) {
721      // If the key given to us is longer than this header, don't consider it.
722      continue;
723    }
724    if (!strncasecmp(GetPtr(line.buffer_base_idx) + line.first_char_idx,
725                     key.data(), key.size())) {
726      line.skip = true;
727    }
728  }
729}
730
731size_t BalsaHeaders::GetMemoryUsedLowerBound() const {
732  return (sizeof(*this) +
733          balsa_buffer_.GetTotalBufferBlockSize() +
734          header_lines_.capacity() * sizeof(HeaderLineDescription));
735}
736
737size_t BalsaHeaders::GetSizeForWriteBuffer() const {
738  // First add the space required for the first line + CRLF
739  size_t write_buf_size = whitespace_4_idx_ - non_whitespace_1_idx_ + 2;
740  // Then add the space needed for each header line to write out + CRLF.
741  const HeaderLines::size_type end = header_lines_.size();
742  for (HeaderLines::size_type i = 0; i < end; ++i) {
743    const HeaderLineDescription& line = header_lines_[i];
744    if (!line.skip) {
745      // Add the key size and ": ".
746      write_buf_size += line.key_end_idx - line.first_char_idx + 2;
747      // Add the value size and the CRLF
748      write_buf_size += line.last_char_idx - line.value_begin_idx + 2;
749    }
750  }
751  // Finally tag on the terminal CRLF.
752  return write_buf_size + 2;
753}
754
755void BalsaHeaders::DumpToString(std::string* str) const {
756  const base::StringPiece firstline = first_line();
757  const int buffer_length =
758      OriginalHeaderStreamEnd() - OriginalHeaderStreamBegin();
759  // First check whether the header object is empty.
760  if (firstline.empty() && buffer_length == 0) {
761    str->append("\n<empty header>\n");
762    return;
763  }
764
765  // Then check whether the header is in a partially parsed state. If so, just
766  // dump the raw data.
767  if (balsa_buffer_.can_write_to_contiguous_buffer()) {
768    base::StringAppendF(str, "\n<incomplete header len: %d>\n%.*s\n",
769                        buffer_length, buffer_length,
770                        OriginalHeaderStreamBegin());
771    return;
772  }
773
774  // If the header is complete, then just dump them with the logical key value
775  // pair.
776  str->reserve(str->size() + GetSizeForWriteBuffer());
777  base::StringAppendF(str, "\n %.*s\n",
778                      static_cast<int>(firstline.size()),
779                      firstline.data());
780  BalsaHeaders::const_header_lines_iterator i = header_lines_begin();
781  for (; i != header_lines_end(); ++i) {
782    base::StringAppendF(str, " %.*s: %.*s\n",
783                        static_cast<int>(i->first.size()), i->first.data(),
784                        static_cast<int>(i->second.size()), i->second.data());
785  }
786}
787
788void BalsaHeaders::SetFirstLine(const base::StringPiece& line) {
789  base::StringPiece new_line = balsa_buffer_.Write(line,
790                                                   &firstline_buffer_base_idx_);
791  whitespace_1_idx_ = new_line.data() - GetPtr(firstline_buffer_base_idx_);
792  non_whitespace_1_idx_ = whitespace_1_idx_;
793  whitespace_4_idx_ = whitespace_1_idx_ + line.size();
794  whitespace_2_idx_ = whitespace_4_idx_;
795  non_whitespace_2_idx_ = whitespace_4_idx_;
796  whitespace_3_idx_ = whitespace_4_idx_;
797  non_whitespace_3_idx_ = whitespace_4_idx_;
798  end_of_firstline_idx_ = whitespace_4_idx_;
799}
800
801void BalsaHeaders::SetContentLength(size_t length) {
802  // If the content-length is already the one we want, don't do anything.
803  if (content_length_status_ == BalsaHeadersEnums::VALID_CONTENT_LENGTH &&
804      content_length_ == length) {
805    return;
806  }
807  const base::StringPiece content_length(kContentLength,
808                                         sizeof(kContentLength) - 1);
809  // If header state indicates that there is either a content length or
810  // transfer encoding header, remove them before adding the new content
811  // length. There is always the possibility that client can manually add
812  // either header directly and cause content_length_status_ or
813  // transfer_encoding_is_chunked_ to be inconsistent with the actual header.
814  // In the interest of efficiency, however, we will assume that clients will
815  // use the header object correctly and thus we will not scan the all headers
816  // each time this function is called.
817  if (content_length_status_ != BalsaHeadersEnums::NO_CONTENT_LENGTH) {
818    RemoveAllOfHeader(content_length);
819  } else if (transfer_encoding_is_chunked_) {
820    const base::StringPiece transfer_encoding(kTransferEncoding,
821                                        sizeof(kTransferEncoding) - 1);
822    RemoveAllOfHeader(transfer_encoding);
823    transfer_encoding_is_chunked_ = false;
824  }
825  content_length_status_ = BalsaHeadersEnums::VALID_CONTENT_LENGTH;
826  content_length_ = length;
827  // FastUInt64ToBuffer is supposed to use a maximum of kFastToBufferSize bytes.
828  char buffer[kFastToBufferSize];
829  int len_converted = snprintf(buffer, sizeof(buffer), "%zd", length);
830  CHECK_GT(len_converted, 0);
831  const base::StringPiece length_str(buffer, len_converted);
832  AppendHeader(content_length, length_str);
833}
834
835void BalsaHeaders::SetChunkEncoding(bool chunk_encode) {
836  if (transfer_encoding_is_chunked_ == chunk_encode) {
837    return;
838  }
839  if (content_length_status_ != BalsaHeadersEnums::NO_CONTENT_LENGTH &&
840      chunk_encode) {
841    // Want to change to chunk encoding, but have content length. Arguably we
842    // can leave this step out, since transfer-encoding overrides
843    // content-length.
844    const base::StringPiece content_length(kContentLength,
845                                     sizeof(kContentLength) - 1);
846    RemoveAllOfHeader(content_length);
847    content_length_status_ = BalsaHeadersEnums::NO_CONTENT_LENGTH;
848    content_length_ = 0;
849  }
850  const base::StringPiece transfer_encoding(kTransferEncoding,
851                                      sizeof(kTransferEncoding) - 1);
852  if (chunk_encode) {
853    const char kChunked[] = "chunked";
854    const base::StringPiece chunked(kChunked, sizeof(kChunked) - 1);
855    AppendHeader(transfer_encoding, chunked);
856  } else {
857    RemoveAllOfHeader(transfer_encoding);
858  }
859  transfer_encoding_is_chunked_ = chunk_encode;
860}
861
862// See the comment about this function in the header file for a
863// warning about its usage.
864void BalsaHeaders::SetFirstlineFromStringPieces(
865    const base::StringPiece& firstline_a,
866    const base::StringPiece& firstline_b,
867    const base::StringPiece& firstline_c) {
868  size_t line_size = (firstline_a.size() +
869                      firstline_b.size() +
870                      firstline_c.size() +
871                      2);
872  char* storage = balsa_buffer_.Reserve(line_size, &firstline_buffer_base_idx_);
873  char* cur_loc = storage;
874
875  memcpy(cur_loc, firstline_a.data(), firstline_a.size());
876  cur_loc += firstline_a.size();
877
878  *cur_loc = ' ';
879  ++cur_loc;
880
881  memcpy(cur_loc, firstline_b.data(), firstline_b.size());
882  cur_loc += firstline_b.size();
883
884  *cur_loc = ' ';
885  ++cur_loc;
886
887  memcpy(cur_loc, firstline_c.data(), firstline_c.size());
888
889  whitespace_1_idx_ = storage - GetPtr(firstline_buffer_base_idx_);
890  non_whitespace_1_idx_ = whitespace_1_idx_;
891  whitespace_2_idx_ = non_whitespace_1_idx_ + firstline_a.size();
892  non_whitespace_2_idx_ = whitespace_2_idx_ + 1;
893  whitespace_3_idx_ = non_whitespace_2_idx_ + firstline_b.size();
894  non_whitespace_3_idx_ = whitespace_3_idx_ + 1;
895  whitespace_4_idx_ = non_whitespace_3_idx_ + firstline_c.size();
896  end_of_firstline_idx_ = whitespace_4_idx_;
897}
898
899void BalsaHeaders::SetRequestMethod(const base::StringPiece& method) {
900  // This is the first of the three parts of the firstline.
901  if (method.size() <= (whitespace_2_idx_ - non_whitespace_1_idx_)) {
902    non_whitespace_1_idx_ = whitespace_2_idx_ - method.size();
903    char* stream_begin = GetPtr(firstline_buffer_base_idx_);
904    memcpy(stream_begin + non_whitespace_1_idx_,
905           method.data(),
906           method.size());
907  } else {
908    // The new method is too large to fit in the space available for the old
909    // one, so we have to reformat the firstline.
910    SetFirstlineFromStringPieces(method, request_uri(), request_version());
911  }
912}
913
914void BalsaHeaders::SetResponseVersion(const base::StringPiece& version) {
915  // Note: There is no difference between request_method() and
916  // response_Version(). Thus, a function to set one is equivalent to a
917  // function to set the other. We maintain two functions for this as it is
918  // much more descriptive, and makes code more understandable.
919  SetRequestMethod(version);
920}
921
922void BalsaHeaders::SetRequestUri(const base::StringPiece& uri) {
923  SetFirstlineFromStringPieces(request_method(), uri, request_version());
924}
925
926void BalsaHeaders::SetResponseCode(const base::StringPiece& code) {
927  // Note: There is no difference between request_uri() and response_code().
928  // Thus, a function to set one is equivalent to a function to set the other.
929  // We maintain two functions for this as it is much more descriptive, and
930  // makes code more understandable.
931  SetRequestUri(code);
932}
933
934void BalsaHeaders::SetParsedResponseCodeAndUpdateFirstline(
935    size_t parsed_response_code) {
936  char buffer[kFastToBufferSize];
937  int len_converted = snprintf(buffer, sizeof(buffer),
938                               "%zd", parsed_response_code);
939  CHECK_GT(len_converted, 0);
940  SetResponseCode(base::StringPiece(buffer, len_converted));
941}
942
943void BalsaHeaders::SetRequestVersion(const base::StringPiece& version) {
944  // This is the last of the three parts of the firstline.
945  // Since whitespace_3_idx and non_whitespace_3_idx may point to the same
946  // place, we ensure below that any available space includes space for a
947  // litteral space (' ') character between the second component and the third
948  // component. If the space between whitespace_3_idx_ and
949  // end_of_firstline_idx_ is >= to version.size() + 1 (for the space), then we
950  // can update the firstline in-place.
951  char* stream_begin = GetPtr(firstline_buffer_base_idx_);
952  if (version.size() + 1 <= end_of_firstline_idx_ - whitespace_3_idx_) {
953    *(stream_begin + whitespace_3_idx_) = kSpaceChar;
954    non_whitespace_3_idx_ = whitespace_3_idx_ + 1;
955    whitespace_4_idx_ = non_whitespace_3_idx_ + version.size();
956    memcpy(stream_begin + non_whitespace_3_idx_,
957           version.data(),
958           version.size());
959  } else {
960    // The new version is to large to fit in the space available for the old
961    // one, so we have to reformat the firstline.
962    SetFirstlineFromStringPieces(request_method(), request_uri(), version);
963  }
964}
965
966void BalsaHeaders::SetResponseReasonPhrase(const base::StringPiece& reason) {
967  // Note: There is no difference between request_version() and
968  // response_reason_phrase(). Thus, a function to set one is equivalent to a
969  // function to set the other. We maintain two functions for this as it is
970  // much more descriptive, and makes code more understandable.
971  SetRequestVersion(reason);
972}
973
974}  // namespace net
975