proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive > Class Template Reference

#include <PerfectIndexMap.h>

Public Member Functions
	PerfectIndexMap ()
virtual	~PerfectIndexMap ()=default
folly::Optional< std::string >	getSingleOrNone (const std::string &keyStr) const
folly::Optional< std::string >	getSingleOrNone (Key key) const
void	add (const std::string &keyStr, const std::string &value)
void	add (Key key, const std::string &value)
void	set (const std::string &keyStr, const std::string &value)
void	set (Key key, const std::string &value)
bool	remove (const std::string &keyStr)
bool	remove (Key key)
size_t	size ()

Private Member Functions
const std::string *	getSingleKey (Key key) const
const std::string *	getSingleOtherKey (const std::string &keyStr) const
void	setKey (Key key, const std::string &value)
void	setOtherKey (const std::string &keyStr, const std::string &value)
bool	removeKey (Key key)
bool	removeOtherKey (const std::string &keyStr)
std::ptrdiff_t	searchForKey (Key key, const Key *&data) const
std::ptrdiff_t	searchForOtherKey (const std::string &keyStr, size_t &startIndex) const
void	addKeyToIndex (Key key, const std::string &value)
void	addOtherKeyToIndex (const std::string &keyStr, const std::string &value)
void	replaceKeyAtIndex (std::ptrdiff_t index, Key key, const std::string &value)
void	replaceOtherKeyAtIndex (size_t namesIndex, const std::string &keyStr, const std::string &value)
void	removeAtIndex (std::ptrdiff_t index)

Private Attributes
size_t	otherKeyCount_ {0}
size_t	noneKeyCount_ {0}
folly::fbvector< Key >	keys_
folly::fbvector< size_t >	otherKeyNamesKeysIndex_
folly::fbvector< std::string >	otherKeyNames_
folly::fbvector< std::string >	values_

Detailed Description

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>
class proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >

Definition at line 48 of file PerfectIndexMap.h.

Constructor & Destructor Documentation

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::PerfectIndexMap ( )

inline

Definition at line 51 of file PerfectIndexMap.h.

{}

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

virtual proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::~PerfectIndexMap ( )

virtualdefault

Member Function Documentation

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

void proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::add ( const std::string &  keyStr, const std::string &  value  )

inline

Definition at line 78 of file PerfectIndexMap.h.

                                                            {
    CHECK(AllowDuplicates);
    auto key = PerfectHashStrToKey(keyStr);
    if (key == OtherKey) {
      addOtherKeyToIndex(keyStr, value);
    } else {
      add(key, value);
    }
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

void proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::add ( Key  key, const std::string &  value  )

inline

Definition at line 88 of file PerfectIndexMap.h.

                                            {
    CHECK(AllowDuplicates && key != OtherKey && key != NoneKey);
    addKeyToIndex(key, value);
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

void proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::addKeyToIndex ( Key  key, const std::string &  value  )

inlineprivate

Definition at line 279 of file PerfectIndexMap.h.

                                                      {
    keys_.push_back(key);
    values_.emplace_back(value);
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

void proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::addOtherKeyToIndex ( const std::string &  keyStr, const std::string &  value  )

inlineprivate

Definition at line 283 of file PerfectIndexMap.h.

                                                                           {
    keys_.push_back(OtherKey);
    otherKeyNames_.emplace_back(keyStr);
    otherKeyNamesKeysIndex_.push_back(keys_.size() - 1);
    values_.emplace_back(value);
    ++otherKeyCount_;
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

const std::string* proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::getSingleKey ( Key  key ) const

inlineprivate

Definition at line 140 of file PerfectIndexMap.h.

                                                {
    const Key* data = keys_.data();
    if (data) {
      auto offset = searchForKey(key, data);
      if (data) {
        if (AllowDuplicates && searchForKey(key, ++data) != -1) {
            return nullptr;
        }
        return &values_[offset];
      }
    }
    return nullptr;
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

folly::Optional<std::string> proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::getSingleOrNone ( const std::string &  keyStr ) const

inline

Definition at line 56 of file PerfectIndexMap.h.

                                     {
    auto key = PerfectHashStrToKey(keyStr);
    if (key == OtherKey) {
      const std::string *result = getSingleOtherKey(keyStr);
      return (
        result == nullptr ? folly::none : folly::Optional<std::string>(*result)
      );
    } else {
      return getSingleOrNone(key);
    }
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

folly::Optional<std::string> proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::getSingleOrNone ( Key  key ) const

inline

Definition at line 68 of file PerfectIndexMap.h.

                                                          {
    CHECK(key != OtherKey && key != NoneKey);
    const std::string *result = getSingleKey(key);
    return (
      result == nullptr ? folly::none : folly::Optional<std::string>(*result)
    );
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

const std::string* proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::getSingleOtherKey ( const std::string &  keyStr ) const

inlineprivate

Definition at line 153 of file PerfectIndexMap.h.

                                                                    {
    size_t searchIndex = 0;
    auto index = searchForOtherKey(keyStr, searchIndex);
    if (index != -1) {
      if (AllowDuplicates && searchForOtherKey(keyStr, ++searchIndex) != -1) {
        return nullptr;
      }
      return &values_[index];
    }
    return nullptr;
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

bool proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::remove ( const std::string &  keyStr )

inline

Definition at line 115 of file PerfectIndexMap.h.

                                       {
    auto key = PerfectHashStrToKey(keyStr);
    if (key == OtherKey) {
      return removeOtherKey(keyStr);
    } else {
      return remove(key);
    }
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

bool proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::remove ( Key  key )

inline

Definition at line 123 of file PerfectIndexMap.h.

                       {
    CHECK(key != OtherKey && key != NoneKey);
    return removeKey(key);
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

void proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::removeAtIndex ( std::ptrdiff_t  index )

inlineprivate

Definition at line 302 of file PerfectIndexMap.h.

                                         {
    CHECK(keys_[index] != NoneKey);
    if (keys_[index] == OtherKey) {
      --otherKeyCount_;
    }
    keys_[index] = NoneKey;
    ++noneKeyCount_;
    // We purposefully omit actually clearing some other data structures
    // as it is often useful for debugging purposes to leave this data around.
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

bool proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::removeKey ( Key  key )

inlineprivate

Definition at line 210 of file PerfectIndexMap.h.

                          {
    const Key* data = keys_.data();
    bool anyRemoved = false;
    std::ptrdiff_t offset;
    while (data) {
      offset = searchForKey(key, data);
      if (data) {
        removeAtIndex(offset);
        anyRemoved = true;
        if (!AllowDuplicates) {
          break;
        }
        ++data;
      }
    }
    return anyRemoved;
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

bool proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::removeOtherKey ( const std::string &  keyStr )

inlineprivate

Definition at line 227 of file PerfectIndexMap.h.

                                               {
    bool anyRemoved = false;
    size_t searchIndex = 0;
    while (searchForOtherKey(keyStr, searchIndex) != -1) {
      removeAtIndex(otherKeyNamesKeysIndex_[searchIndex]);
      anyRemoved = true;
      if (!AllowDuplicates) {
        break;
      }
      ++searchIndex;
    }
    return anyRemoved;
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

void proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::replaceKeyAtIndex ( std::ptrdiff_t  index, Key  key, const std::string &  value  )

inlineprivate

Definition at line 290 of file PerfectIndexMap.h.

                                                           {
    keys_[index] = key;
    values_[index] = value;
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

void proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::replaceOtherKeyAtIndex ( size_t  namesIndex, const std::string &  keyStr, const std::string &  value  )

inlineprivate

Definition at line 295 of file PerfectIndexMap.h.

                                                                          {
    otherKeyNames_[namesIndex] = keyStr;
    values_[otherKeyNamesKeysIndex_[namesIndex]] = value;
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

std::ptrdiff_t proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::searchForKey ( Key  key, const Key *&  data  ) const

inlineprivate

Definition at line 245 of file PerfectIndexMap.h.

                                                             {
    if (data) {
      data = (Key*)memchr(
        (void*)data, key, keys_.size() - (data - keys_.data()));
      if (data) {
        return data - keys_.data();
      }
    }
    return -1;
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

std::ptrdiff_t proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::searchForOtherKey ( const std::string &  keyStr, size_t &  startIndex  ) const

inlineprivate

Definition at line 255 of file PerfectIndexMap.h.

                                                         {
    while (startIndex < otherKeyNamesKeysIndex_.size()) {
      // The key can only be OtherKey or NoneKey
      if (keys_[otherKeyNamesKeysIndex_[startIndex]] == OtherKey) {
        if (CaseInsensitive) {
          // One might be tempted to merge this statement with that above
          // but that would be wrong.  If CaseInsensitive is true, we do not
          // want any other check evaluating.
          if (caseInsensitiveEqual(otherKeyNames_[startIndex], keyStr)) {
            return otherKeyNamesKeysIndex_[startIndex];
          }
        } else {
          if (otherKeyNames_[startIndex] == keyStr) {
            return otherKeyNamesKeysIndex_[startIndex];
          }
        }
      }
      ++startIndex;
    }
    return -1;
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

void proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::set ( const std::string &  keyStr, const std::string &  value  )

inline

Definition at line 97 of file PerfectIndexMap.h.

                                                            {
    auto key = PerfectHashStrToKey(keyStr);
    if (key == OtherKey) {
      setOtherKey(keyStr, value);
    } else {
      set(key, value);
    }
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

void proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::set ( Key  key, const std::string &  value  )

inline

Definition at line 106 of file PerfectIndexMap.h.

                                            {
    CHECK(key != OtherKey && key != NoneKey);
    setKey(key, value);
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

void proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::setKey ( Key  key, const std::string &  value  )

inlineprivate

Definition at line 165 of file PerfectIndexMap.h.

                                               {
    const Key* data = keys_.data();
    bool set = false;
    std::ptrdiff_t offset;
    while (data) {
      offset = searchForKey(key, data);
      if (data) {
        if (!set) {
          replaceKeyAtIndex(offset, key, value);
          if (AllowDuplicates) {
            set = true;
          } else {
            return;
          }
        } else {
          removeAtIndex(offset);
        }
        ++data;
      }
    }
    if (!set) {
      addKeyToIndex(key, value);
    }
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

void proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::setOtherKey ( const std::string &  keyStr, const std::string &  value  )

inlineprivate

Definition at line 189 of file PerfectIndexMap.h.

                                                                    {
    bool set = false;
    size_t searchIndex = 0;
    while (searchForOtherKey(keyStr, searchIndex) != -1) {
      if (!set) {
        replaceOtherKeyAtIndex(searchIndex, keyStr, value);
        if (AllowDuplicates) {
          set = true;
        } else {
          return;
        }
      } else {
        removeAtIndex(otherKeyNamesKeysIndex_[searchIndex]);
      }
      ++searchIndex;
    }
    if (!set) {
      addOtherKeyToIndex(keyStr, value);
    }
  }

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

size_t proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::size ( )

inline

Definition at line 128 of file PerfectIndexMap.h.

                {
    return keys_.size() - noneKeyCount_;
  }

Member Data Documentation

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

folly::fbvector<Key> proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::keys_

private

Definition at line 350 of file PerfectIndexMap.h.

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

size_t proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::noneKeyCount_ {0}

private

Definition at line 341 of file PerfectIndexMap.h.

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

size_t proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::otherKeyCount_ {0}

private

Definition at line 340 of file PerfectIndexMap.h.

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

folly::fbvector<std::string> proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::otherKeyNames_

private

Definition at line 366 of file PerfectIndexMap.h.

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

folly::fbvector<size_t> proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::otherKeyNamesKeysIndex_

private

Definition at line 358 of file PerfectIndexMap.h.

template<typename Key, Key OtherKey, Key NoneKey, Key(*)(const std::string &) PerfectHashStrToKey, bool AllowDuplicates, bool CaseInsensitive>

folly::fbvector<std::string> proxygen::PerfectIndexMap< Key, OtherKey, NoneKey, PerfectHashStrToKey, AllowDuplicates, CaseInsensitive >::values_

private

Definition at line 370 of file PerfectIndexMap.h.

---

The documentation for this class was generated from the following file:

• proxygen/lib/utils/PerfectIndexMap.h