src/pagespeed/kernel/base/string_multi_map.h - incubator-pagespeed-debian - Git at Google

 // Copyright 2010 Google Inc.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //      http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.
 //
 // Author: jmarantz@google.com (Joshua Marantz)

 #ifndef PAGESPEED_KERNEL_BASE_STRING_MULTI_MAP_H_
 #define PAGESPEED_KERNEL_BASE_STRING_MULTI_MAP_H_

 #include <algorithm>
 #include <set>
 #include <utility>
 #include <vector>

 #include "base/logging.h"
 #include "pagespeed/kernel/base/basictypes.h"
 #include "pagespeed/kernel/base/string.h"
 #include "pagespeed/kernel/base/string_util.h"

 namespace net_instaweb {

 // Implements an ordered string map, providing case-sensitive and case
 // insensitive versions.  The order of insertion is retained and
 // names/value pairs can be accessed by index or looked up by name.
 //
 // The keys and values in the map may contain embedded NUL characters.
 // The values can also be the NULL pointer, which the API retains
 // distinctly from empty strings.
 template<class StringCompare> class StringMultiMap {
  public:
   StringMultiMap() { }
   ~StringMultiMap() {
     Clear();
   }

   bool empty() const {
     return vector_.empty();
   }

   void Clear() {
     for (int i = 0, n = vector_.size(); i < n; ++i) {
       delete vector_[i].second;
     }
     set_.clear();
     vector_.clear();
   }

   // Returns the number of distinct names
   int num_names() const { return set_.size(); }

   // Returns the number of distinct values, which can be larger than num_names
   // if Add is called twice with the same name.
   int num_values() const { return vector_.size(); }

   // Find the value(s) associated with a variable.  Note that you may
   // specify a variable multiple times by calling Add multiple times
   // with the same variable, and each of these values will be returned
   // in the vector.
   bool Lookup(const StringPiece& name, ConstStringStarVector* values) const {
     SetEntry lookup_entry(name);
     typename Set::const_iterator p = set_.find(lookup_entry);
     bool ret = false;
     if (p != set_.end()) {
       ret = true;
       const SetEntry& stored_entry = *p;
       *values = stored_entry.values();
     }
     return ret;
   }

   // Looks up a single value.  Returns NULL if the name is not found or more
   // than one value is found.
   const GoogleString* Lookup1(const StringPiece& name) const {
     ConstStringStarVector v;
     if (Lookup(name, &v) && v.size() == 1) {
       return v[0];
     }
     return NULL;
   }

   bool Has(const StringPiece& name) const {
     SetEntry lookup_entry(name);
     return set_.find(lookup_entry) != set_.end();
   }

   // Remove all variables by name.  Returns true if anything was removed.
   bool RemoveAll(const StringPiece& key) {
     return RemoveAllFromSortedArray(&key, 1);
   }

   // Remove all variables by name.  Returns true if anything was removed.
   //
   // The 'names' vector must be sorted based on StringCompare.
   bool RemoveAllFromSortedArray(const StringPiece* names, int names_size) {
 #ifndef NDEBUG
     for (int i = 1; i < names_size; ++i) {
       StringCompare compare;
       // compare implements <, and we want <= to allow for for
       // duplicate entries, such as the two Set-Cookie entries that
       // occur in ResponseHeadersTest.TestUpdateFrom.  We could also
       // require call-sites to de-dup but this seems easier.  We can
       // implement a<=b via !compare(b, a).
       DCHECK(!compare(names[i], names[i - 1]))
           << "\"" << names[i - 1] << "\" vs \"" << names[i];
     }
 #endif

     // Keep around dummy entry for stuffing in keys and doing lookups.
     // The values field for this instance is unused.
     SetEntry lookup_entry;

     // First, see if any of the names are in the map.  This way we'll avoid
     // making any allocations if there is no work to be done.  We cannot
     // actually remove the map entries, though, until we rebuild the vector,
     // since the map owns the StringPiece key storage used by the vector.
     const int kNotFound = -1;
     int index_of_first_match = kNotFound;
     typename Set::iterator set_entry_of_first_match;
     for (int i = 0; i < names_size; ++i) {
       lookup_entry.set_key(names[i]);
       set_entry_of_first_match = set_.find(lookup_entry);
       if (set_entry_of_first_match != set_.end()) {
         index_of_first_match = i;
         break;
       }
     }

     if (index_of_first_match == kNotFound) {
       return false;
     } else {
       StringPairVector temp_vector;  // Temp variable for new vector.
       temp_vector.reserve(vector_.size() - 1);
       StringCompare compare;
       for (int i = 0; i < num_values(); ++i) {
         if (std::binary_search(names, names + names_size, name(i), compare)) {
           delete vector_[i].second;
         } else {
           temp_vector.push_back(vector_[i]);
         }
       }

       vector_.swap(temp_vector);

       set_.erase(set_entry_of_first_match);
       for (int i = index_of_first_match + 1; i < names_size; ++i) {
         lookup_entry.set_key(names[i]);
         set_.erase(lookup_entry);
       }
     }
     return true;
   }

   StringPiece name(int index) const { return vector_[index].first; }

   // Note that the value can be NULL.
   const GoogleString* value(int index) const { return vector_[index].second; }

   // Add a new variable.  The value can be null.
   void Add(const StringPiece& key, const StringPiece& value) {
     SetEntry lookup_entry(key);
     std::pair<typename Set::iterator, bool> iter_inserted =
         set_.insert(lookup_entry);
     typename Set::iterator iter = iter_inserted.first;

     // To avoid letting you corrupt the comparison sanity of an STL set,
     // the 'insert' method returns an iterator that returns you only a
     // const reference to the stored entry.  However, the mutation we are
     // going to do here is to change the key to point to storage we'll
     // own in the entry, which we want to allocate only the first time
     // it is added.
     //
     // We also need to be able to mutate the entry to allow adding new
     // value entries.
     SetEntry& entry = const_cast<SetEntry&>(*iter);
     if (iter_inserted.second) {
       // The first time we insert, make a copy of the key in storage we own.
       entry.SaveKey();
     }
     GoogleString* value_copy = NULL;
     if (value.data() != NULL) {
       value_copy = new GoogleString(value.as_string());
     }
     entry.AddValue(value_copy);
     vector_.push_back(StringPair(iter->key(), value_copy));
   }

   // Parse and add from a string of name-value pairs.
   // For example,
   //   "name1=value1,name2=value2,name3="
   // where separators is "," and value_separator is '='.
   // If omit_if_no_value is true, a name-value pair with an empty value will
   // not be added.
   void AddFromNameValuePairs(const StringPiece& name_value_list,
                              const StringPiece& separators,
                              char value_separator,
                              bool omit_if_no_value) {
     StringPieceVector pairs;
     SplitStringPieceToVector(name_value_list, separators, &pairs, true);
     for (int i = 0, n = pairs.size(); i < n; ++i) {
       StringPiece& pair = pairs[i];
       StringPiece::size_type pos = pair.find(value_separator);
       if (pos != StringPiece::npos) {
         Add(pair.substr(0, pos), pair.substr(pos + 1));
       } else if (!omit_if_no_value) {
         Add(pair, StringPiece(NULL, 0));
       }
     }
   }

   void CopyFrom(const StringMultiMap& string_multi_map) {
     Clear();
     for (int i = 0; i < string_multi_map.num_values(); ++i) {
       const GoogleString* value = string_multi_map.value(i);
       if (value != NULL) {
         Add(string_multi_map.name(i), *value);
       } else {
         Add(string_multi_map.name(i), NULL);
       }
     }
   }

  private:
   // We are creating a map-like object using a std::set to make it clearer
   // how we are managing key storage within the entry.
   class SetEntry {
    public:
     SetEntry() { }
     SetEntry(StringPiece key) : key_(key) { }
     SetEntry(const SetEntry& src)
         : key_(src.key_) {
       // Note that a copy-construction does occur in Add, but only of
       // the lookup_entry, which will not have a saved key.
       DCHECK(src.values_.empty());
     }

     SetEntry& operator=(const SetEntry& src) {
       if (&src != this) {
         DCHECK(src.values_.empty());
         key_ = src.key_;
       }
       return *this;
     }

     void set_key(StringPiece key) {
       key_ = key;
     }

     void AddValue(const GoogleString* value) {
       values_.push_back(value);
     }

     // During lookups, key will point to the passed-in StringPiece.
     // However, the persistent entry we put in the map must duplicate
     // the key into key_storage and change key to point to that.
     void SaveKey() {
       key_.CopyToString(&key_storage_);
       key_ = key_storage_;
     }

     StringPiece key() const { return key_; }
     const ConstStringStarVector& values() const { return values_; }

    private:
     GoogleString key_storage_;
     StringPiece key_;
     ConstStringStarVector values_;
   };

   struct EntryCompare {
     bool operator()(const SetEntry& a, const SetEntry& b) const {
       return compare(a.key(), b.key());
     }

     StringCompare compare;
   };

   // We are keeping two structures, conceptually map<String,vector<String>> and
   // vector<pair<String,String>>, so we can do associative lookups and
   // also order-preserving iteration and easy indexed access.
   //
   // To avoid duplicating the strings and superfluous string-allocations on
   // lookups, we implement this via a set, whose entries own the keys.  A
   // separate string-pair-vector owns the values as new'd GoogleString*.  We
   // use a pointer here to avoid the cost of string-copies as the vector is
   // resized.
   typedef std::pair<StringPiece, GoogleString*> StringPair;  // owns the value
   typedef std::set<SetEntry, EntryCompare> Set;
   typedef std::vector<StringPair> StringPairVector;

   Set set_;
   StringPairVector vector_;

   DISALLOW_COPY_AND_ASSIGN(StringMultiMap);
 };

 class StringMultiMapInsensitive
     : public StringMultiMap<StringCompareInsensitive> {
  public:
   StringMultiMapInsensitive() { }
  private:
   DISALLOW_COPY_AND_ASSIGN(StringMultiMapInsensitive);
 };

 class StringMultiMapSensitive : public StringMultiMap<StringCompareSensitive> {
  public:
   StringMultiMapSensitive() { }
  private:
   DISALLOW_COPY_AND_ASSIGN(StringMultiMapSensitive);
 };

 }  // namespace net_instaweb

 #endif  // PAGESPEED_KERNEL_BASE_STRING_MULTI_MAP_H_
	// Copyright 2010 Google Inc.
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.
	//
	// Author: jmarantz@google.com (Joshua Marantz)

	#ifndef PAGESPEED_KERNEL_BASE_STRING_MULTI_MAP_H_
	#define PAGESPEED_KERNEL_BASE_STRING_MULTI_MAP_H_

	#include <algorithm>
	#include <set>
	#include <utility>
	#include <vector>

	#include "base/logging.h"
	#include "pagespeed/kernel/base/basictypes.h"
	#include "pagespeed/kernel/base/string.h"
	#include "pagespeed/kernel/base/string_util.h"

	namespace net_instaweb {

	// Implements an ordered string map, providing case-sensitive and case
	// insensitive versions. The order of insertion is retained and
	// names/value pairs can be accessed by index or looked up by name.
	//
	// The keys and values in the map may contain embedded NUL characters.
	// The values can also be the NULL pointer, which the API retains
	// distinctly from empty strings.
	template<class StringCompare> class StringMultiMap {
	public:
	StringMultiMap() { }
	~StringMultiMap() {
	Clear();
	}

	bool empty() const {
	return vector_.empty();
	}

	void Clear() {
	for (int i = 0, n = vector_.size(); i < n; ++i) {
	delete vector_[i].second;
	}
	set_.clear();
	vector_.clear();
	}

	// Returns the number of distinct names
	int num_names() const { return set_.size(); }

	// Returns the number of distinct values, which can be larger than num_names
	// if Add is called twice with the same name.
	int num_values() const { return vector_.size(); }

	// Find the value(s) associated with a variable. Note that you may
	// specify a variable multiple times by calling Add multiple times
	// with the same variable, and each of these values will be returned
	// in the vector.
	bool Lookup(const StringPiece& name, ConstStringStarVector* values) const {
	SetEntry lookup_entry(name);
	typename Set::const_iterator p = set_.find(lookup_entry);
	bool ret = false;
	if (p != set_.end()) {
	ret = true;
	const SetEntry& stored_entry = *p;
	*values = stored_entry.values();
	}
	return ret;
	}

	// Looks up a single value. Returns NULL if the name is not found or more
	// than one value is found.
	const GoogleString* Lookup1(const StringPiece& name) const {
	ConstStringStarVector v;
	if (Lookup(name, &v) && v.size() == 1) {
	return v[0];
	}
	return NULL;
	}

	bool Has(const StringPiece& name) const {
	SetEntry lookup_entry(name);
	return set_.find(lookup_entry) != set_.end();
	}

	// Remove all variables by name. Returns true if anything was removed.
	bool RemoveAll(const StringPiece& key) {
	return RemoveAllFromSortedArray(&key, 1);
	}

	// Remove all variables by name. Returns true if anything was removed.
	//
	// The 'names' vector must be sorted based on StringCompare.
	bool RemoveAllFromSortedArray(const StringPiece* names, int names_size) {
	#ifndef NDEBUG
	for (int i = 1; i < names_size; ++i) {
	StringCompare compare;
	// compare implements <, and we want <= to allow for for
	// duplicate entries, such as the two Set-Cookie entries that
	// occur in ResponseHeadersTest.TestUpdateFrom. We could also
	// require call-sites to de-dup but this seems easier. We can
	// implement a<=b via !compare(b, a).
	DCHECK(!compare(names[i], names[i - 1]))
	<< "\"" << names[i - 1] << "\" vs \"" << names[i];
	}
	#endif

	// Keep around dummy entry for stuffing in keys and doing lookups.
	// The values field for this instance is unused.
	SetEntry lookup_entry;

	// First, see if any of the names are in the map. This way we'll avoid
	// making any allocations if there is no work to be done. We cannot
	// actually remove the map entries, though, until we rebuild the vector,
	// since the map owns the StringPiece key storage used by the vector.
	const int kNotFound = -1;
	int index_of_first_match = kNotFound;
	typename Set::iterator set_entry_of_first_match;
	for (int i = 0; i < names_size; ++i) {
	lookup_entry.set_key(names[i]);
	set_entry_of_first_match = set_.find(lookup_entry);
	if (set_entry_of_first_match != set_.end()) {
	index_of_first_match = i;
	break;
	}
	}

	if (index_of_first_match == kNotFound) {
	return false;
	} else {
	StringPairVector temp_vector; // Temp variable for new vector.
	temp_vector.reserve(vector_.size() - 1);
	StringCompare compare;
	for (int i = 0; i < num_values(); ++i) {
	if (std::binary_search(names, names + names_size, name(i), compare)) {
	delete vector_[i].second;
	} else {
	temp_vector.push_back(vector_[i]);
	}
	}

	vector_.swap(temp_vector);

	set_.erase(set_entry_of_first_match);
	for (int i = index_of_first_match + 1; i < names_size; ++i) {
	lookup_entry.set_key(names[i]);
	set_.erase(lookup_entry);
	}
	}
	return true;
	}

	StringPiece name(int index) const { return vector_[index].first; }

	// Note that the value can be NULL.
	const GoogleString* value(int index) const { return vector_[index].second; }

	// Add a new variable. The value can be null.
	void Add(const StringPiece& key, const StringPiece& value) {
	SetEntry lookup_entry(key);
	std::pair<typename Set::iterator, bool> iter_inserted =
	set_.insert(lookup_entry);
	typename Set::iterator iter = iter_inserted.first;

	// To avoid letting you corrupt the comparison sanity of an STL set,
	// the 'insert' method returns an iterator that returns you only a
	// const reference to the stored entry. However, the mutation we are
	// going to do here is to change the key to point to storage we'll
	// own in the entry, which we want to allocate only the first time
	// it is added.
	//
	// We also need to be able to mutate the entry to allow adding new
	// value entries.
	SetEntry& entry = const_cast<SetEntry&>(*iter);
	if (iter_inserted.second) {
	// The first time we insert, make a copy of the key in storage we own.
	entry.SaveKey();
	}
	GoogleString* value_copy = NULL;
	if (value.data() != NULL) {
	value_copy = new GoogleString(value.as_string());
	}
	entry.AddValue(value_copy);
	vector_.push_back(StringPair(iter->key(), value_copy));
	}

	// Parse and add from a string of name-value pairs.
	// For example,
	// "name1=value1,name2=value2,name3="
	// where separators is "," and value_separator is '='.
	// If omit_if_no_value is true, a name-value pair with an empty value will
	// not be added.
	void AddFromNameValuePairs(const StringPiece& name_value_list,
	const StringPiece& separators,
	char value_separator,
	bool omit_if_no_value) {
	StringPieceVector pairs;
	SplitStringPieceToVector(name_value_list, separators, &pairs, true);
	for (int i = 0, n = pairs.size(); i < n; ++i) {
	StringPiece& pair = pairs[i];
	StringPiece::size_type pos = pair.find(value_separator);
	if (pos != StringPiece::npos) {
	Add(pair.substr(0, pos), pair.substr(pos + 1));
	} else if (!omit_if_no_value) {
	Add(pair, StringPiece(NULL, 0));
	}
	}
	}

	void CopyFrom(const StringMultiMap& string_multi_map) {
	Clear();
	for (int i = 0; i < string_multi_map.num_values(); ++i) {
	const GoogleString* value = string_multi_map.value(i);
	if (value != NULL) {
	Add(string_multi_map.name(i), *value);
	} else {
	Add(string_multi_map.name(i), NULL);
	}
	}
	}

	private:
	// We are creating a map-like object using a std::set to make it clearer
	// how we are managing key storage within the entry.
	class SetEntry {
	public:
	SetEntry() { }
	SetEntry(StringPiece key) : key_(key) { }
	SetEntry(const SetEntry& src)
	: key_(src.key_) {
	// Note that a copy-construction does occur in Add, but only of
	// the lookup_entry, which will not have a saved key.
	DCHECK(src.values_.empty());
	}

	SetEntry& operator=(const SetEntry& src) {
	if (&src != this) {
	DCHECK(src.values_.empty());
	key_ = src.key_;
	}
	return *this;
	}

	void set_key(StringPiece key) {
	key_ = key;
	}

	void AddValue(const GoogleString* value) {
	values_.push_back(value);
	}

	// During lookups, key will point to the passed-in StringPiece.
	// However, the persistent entry we put in the map must duplicate
	// the key into key_storage and change key to point to that.
	void SaveKey() {
	key_.CopyToString(&key_storage_);
	key_ = key_storage_;
	}

	StringPiece key() const { return key_; }
	const ConstStringStarVector& values() const { return values_; }

	private:
	GoogleString key_storage_;
	StringPiece key_;
	ConstStringStarVector values_;
	};

	struct EntryCompare {
	bool operator()(const SetEntry& a, const SetEntry& b) const {
	return compare(a.key(), b.key());
	}

	StringCompare compare;
	};

	// We are keeping two structures, conceptually map<String,vector<String>> and
	// vector<pair<String,String>>, so we can do associative lookups and
	// also order-preserving iteration and easy indexed access.
	//
	// To avoid duplicating the strings and superfluous string-allocations on
	// lookups, we implement this via a set, whose entries own the keys. A
	// separate string-pair-vector owns the values as new'd GoogleString*. We
	// use a pointer here to avoid the cost of string-copies as the vector is
	// resized.
	typedef std::pair<StringPiece, GoogleString*> StringPair; // owns the value
	typedef std::set<SetEntry, EntryCompare> Set;
	typedef std::vector<StringPair> StringPairVector;

	Set set_;
	StringPairVector vector_;

	DISALLOW_COPY_AND_ASSIGN(StringMultiMap);
	};

	class StringMultiMapInsensitive
	: public StringMultiMap<StringCompareInsensitive> {
	public:
	StringMultiMapInsensitive() { }
	private:
	DISALLOW_COPY_AND_ASSIGN(StringMultiMapInsensitive);
	};

	class StringMultiMapSensitive : public StringMultiMap<StringCompareSensitive> {
	public:
	StringMultiMapSensitive() { }
	private:
	DISALLOW_COPY_AND_ASSIGN(StringMultiMapSensitive);
	};

	} // namespace net_instaweb

	#endif // PAGESPEED_KERNEL_BASE_STRING_MULTI_MAP_H_