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