net/tools/balsa/balsa_headers.cc

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