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