string_multi_map.h

Go to the documentation of this file.

// Copyright 2010 Google Inc.

#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 {

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();
  }

  int num_names() const { return set_.size(); }

  int num_values() const { return vector_.size(); }

  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;
  }

  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();
  }

  bool RemoveAll(const StringPiece& key) {
    return RemoveAllFromSortedArray(&key, 1);
  }

  bool RemoveAllFromSortedArray(const StringPiece* names, int names_size) {
#ifndef NDEBUG
    for (int i = 1; i < names_size; ++i) {
      StringCompare compare;
      DCHECK(!compare(names[i], names[i - 1]))
          << "\"" << names[i - 1] << "\" vs \"" << names[i];
    }
#endif

    SetEntry lookup_entry;

    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_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; }

  const GoogleString* value(int index) const { return vector_[index].second; }

  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;

    SetEntry& entry = const_cast<SetEntry&>(*iter);
    if (iter_inserted.second) {
      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));
  }

  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), StringPiece());
      }
    }
  }

 private:
  class SetEntry {
   public:
    SetEntry() { }
    SetEntry(StringPiece key) : key_(key) { }
    SetEntry(const SetEntry& src)
        : key_(src.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);
    }

    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;
  };

  typedef std::pair<StringPiece, GoogleString*> StringPair; 
  typedef std::set<SetEntry, EntryCompare> Set;
  typedef std::vector<StringPair> StringPairVector;

  Set set_;
  StringPairVector vector_;

  
};

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

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

}  

#endif