TupleString.h

Go to the documentation of this file.

#ifndef TUPLESTRING_H
#define TUPLESTRING_H
  /*
 * Classes to manage the parameters that are built from tuples of strings.
 *
 * To avoid ever calling strcasecmp, we upcase on input.
 * 
 * For performance reasons, we make a hash key of the tuple for faster
 * search times in structures like unordered_map
 * 
 */

#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include "xxh3.h"

// this is the value we inherit from Parameter.h
// it may be overkill, but we're dealing with defacto standards
static const short ParamNameMaxLen=11;

// this gives us a fixed length base
struct MStringStrider {
  char mStride[ParamNameMaxLen];
};


// these make the compiler do our indexing for us
template <short NumStrings>
struct TupleStrider {
  union{
    MStringStrider stride[NumStrings];
    char mString[ParamNameMaxLen*NumStrings];
  };
};

// We build up our MultiString Template here
template <short NumStrings>
class MultiString
{
 public:
  TupleStrider <NumStrings> multiString;
  MultiString(){}

  MultiString(const MultiString<NumStrings> &rhs){
    memcpy(multiString.mString, rhs.getMString(), getMStringLen());
  }
  // we only bother with constructors for 1,2,3,4,8 as those are what we use

  MultiString(const char *t1)
    {
      memset(multiString.mString, 0, getMStringLen());
      strncpy(multiString.mString, t1, getTupleMaxLen());
    }

  MultiString(const char *t1, const char *t2)
    {
      memset(multiString.mString, 0, getMStringLen());
      strncpy(multiString.mString, t1, getTupleMaxLen());
      strncpy(getTuplePtr(1), t2, getTupleMaxLen());
    }

  MultiString(const char *t1, const char *t2, const char *t3)
    {
      memset(multiString.mString, 0, getMStringLen());      
      strncpy(multiString.mString, t1, getTupleMaxLen());
      strncpy(getTuplePtr(1), t2, getTupleMaxLen());
      strncpy(getTuplePtr(2), t3, getTupleMaxLen());
    }
  MultiString(const char *t1, const char *t2, const char *t3, const char *t4)
    {
      memset(multiString.mString, 0, getMStringLen());      
      strncpy(multiString.mString, t1, getTupleMaxLen());
      strncpy(getTuplePtr(1), t2, getTupleMaxLen());
      strncpy(getTuplePtr(2), t3, getTupleMaxLen());
      strncpy(getTuplePtr(3), t4, getTupleMaxLen());
    }

  MultiString(const char *t1, const char *t2, const char *t3, const char *t4,
              const char *t5, const char *t6, const char *t7, const char *t8
              )
    {
      memset(multiString.mString, 0, getMStringLen());      
      strncpy(multiString.mString, t1, getTupleMaxLen());
      strncpy(getTuplePtr(1), t2, getTupleMaxLen());
      strncpy(getTuplePtr(2), t3, getTupleMaxLen());
      strncpy(getTuplePtr(3), t4, getTupleMaxLen());
      strncpy(getTuplePtr(4), t5, getTupleMaxLen());
      strncpy(getTuplePtr(5), t6, getTupleMaxLen());
      strncpy(getTuplePtr(6), t7, getTupleMaxLen());
      strncpy(getTuplePtr(7), t8, getTupleMaxLen());
    }

  inline char *getTuplePtr(short index) {
    return (char *)  &(multiString.stride[index]); }

  inline void upcase()
    {
      for(int i=0; i < mStringLen ;i++)
        {
          multiString.mString[i] = std::toupper(multiString.mString[i]);
        }
    }

  inline short length() const { return mStringLen;}
  
  inline bool operator== (const MultiString& rhs) const
    {
     return memcmp(multiString.mString, rhs.getMString(), mStringCmpLen)==0;
    }
  inline bool operator< (const MultiString& rhs) const
    {
     return memcmp(multiString.mString, rhs.getMString(), mStringCmpLen) < 0 ;
    }
  inline const char *getMString() const {return multiString.mString;}
  inline const short getMStringLen() const {return mStringLen;}
  inline const short getTupleMaxLen() const {return ParamNameMaxLen;}
  
 private:
  static const short mStringLen=NumStrings*ParamNameMaxLen;
  static const short mStringCmpLen=NumStrings*ParamNameMaxLen-1; // last one will always be null
};

// TupleString is just the MultiString with hashkeys built in
template <short NumStrings>
class TupleString
{
 public:
  MultiString <NumStrings> tupleCat;
  TupleString()
    {}
  TupleString(const char* key1)
    {
      tupleCat = MultiString <NumStrings>(key1);
      tupleCat.upcase();
      makeHash();
    }
  
  TupleString(const char* key1, const char* key2)
    {
      tupleCat = MultiString <NumStrings>(key1, key2);
      tupleCat.upcase();
      makeHash();
    }

  TupleString(const char* key1, const char* key2, const char* key3)
    {
      tupleCat = MultiString <NumStrings>(key1, key2, key3);
      tupleCat.upcase();
      makeHash();
    }

  TupleString(const char* key1, const char* key2, const char* key3,
              const char* key4)
    {
      tupleCat = MultiString <NumStrings>(key1, key2, key3, key4);
      tupleCat.upcase();
      makeHash();
    }

  TupleString(const char* key1, const char* key2, const char* key3,
              const char* key4, const char* key5, const char* key6,
              const char* key7, const char* key8)
    {
      tupleCat = MultiString <NumStrings>(key1, key2, key3, key4,
                                          key5, key6, key7, key8);
      tupleCat.upcase();
      makeHash();
    }
  
  inline void makeHash()
  {
    hashKey = XXH3_64bits(tupleCat.getMString(), tupleCat.length());
  }

  // if the hashkeys are equal, check the string
  inline bool operator== (const TupleString& rhs) const
    {
     if(hashKey == rhs.getHashKey())
       {
        return tupleCat == rhs.tupleCat;
       }
     return false;
    }

  // if the hashkeys are equal, check the string
  inline bool operator<(const TupleString& rhs) const
    {
     if(hashKey == rhs.getHashKey())
       return(tupleCat < rhs.tupleCat);
     return hashKey < rhs.getHashKey();
    }

  inline const uint64_t getHashKey() const {return hashKey;}
  inline const char* getCatKey() const {return tupleCat.getMString();}

  inline char *getTuplePtr(short index) { return tupleCat.getTuplePtr(index); }
 private:
  uint64_t hashKey;
};


template <short NumStrings>
struct TupleStringHash
{
  size_t operator() (const TupleString <NumStrings>& k) const
    {
      return k.getHashKey();
    }
  static_assert((NumStrings==1) || (NumStrings==2) || (NumStrings==3)
                || (NumStrings==4) || (NumStrings==8),
                "invalid NumStrings must be: [1,2,3,4,8]");
};


/* convenience typedefs */
typedef TupleString<1> TupleString1;
typedef TupleString<2> TupleString2;
typedef TupleString<3> TupleString3;
typedef TupleString<4> TupleString4;
typedef TupleString<8> TupleString8;


/* 
   combine a map with key(tuple) and value(index) with a vector of
   record types for the map to index into. We enforce uniqueness on the
   map and only append a new value for a unique key.
*/


//templating a template is tricky with only c++11
//this looks a little weird, but avoids code replication

template <short NumStrings, class ParamValue>
class TwoLevelParam
{
 public:
  std::vector<ParamValue> paramVector;
  std::unordered_map<TupleString<NumStrings>, size_t, TupleStringHash<NumStrings>> tupleMap;
  inline TwoLevelParam()
    {
    }
  inline ParamValue* get_param(const size_t &index)
  {
    return &(paramVector[index]);
  }

  inline ParamValue* get_param_by_key(const TupleString<NumStrings> &findKey)
  {
    auto ret = tupleMap.find(findKey);
    if(ret!=tupleMap.end())
      {
        return &paramVector[ret->second];
      }
    else
      {
        return NULL;
      }
  }

  inline bool insert(const TupleString<NumStrings> &tKey,
                     const ParamValue &mValue)
  {
    size_t newPlace = paramVector.size();
    const auto ret = tupleMap.emplace(std::make_pair(tKey,newPlace));
    if(ret.second)
      {

        paramVector.push_back(mValue);
      }
    return ret.second;
  }

  // return whether it was newly inserted and the pointer to the value
  inline std::pair<bool, ParamValue*> insert_check(const TupleString<NumStrings> &tKey,
                                                   const ParamValue &mValue)
  {
    size_t newPlace = paramVector.size();
    auto ret = tupleMap.emplace(std::make_pair(tKey,newPlace));
    if(ret.second)
      {
        paramVector.push_back(mValue);
      }
    return std::make_pair(ret.second, &paramVector[ret.first->second]);
  }
   
  // underscore naming inherited from original Parameter.[hC]
  inline std::pair<bool, size_t> const index_param(const TupleString<NumStrings> &findKey) const
  {
    const auto ret = tupleMap.find(findKey);
    if(ret!=tupleMap.end())
      {
        return std::make_pair(true, ret->second);
      }
    else
      {
        return std::make_pair(false, paramVector.size());
      }
  }

  // possibly faster
  inline int64_t const index(const TupleString<NumStrings> &findKey) const
  {
    const auto ret = tupleMap.find(findKey);
    if(ret!=tupleMap.end())
      {
        return ret->second;
      }
    return -1;
  }

  void clear()
  {
    tupleMap.clear();
    paramVector.clear();
  }

  // mem_opt relies on strict ordering by name for indices to match up.
  // Sort the key strings alphanumerically and reset the indices
  // to have an in order param vector.
  // This is not within an #ifdef MEM_OPT_VERSION so it can be used
  // during genCompressedPsf
  void sort()
  {
    typedef std::pair<TupleString<NumStrings>, size_t> TSKeypair;
    std::vector <TSKeypair> sortVector;
    std::vector <ParamValue> sortValues;
    for(auto apair : tupleMap)
      {
        sortVector.push_back(apair);
      }
    std::sort(sortVector.begin(), sortVector.end(),
              [] (TSKeypair a, TSKeypair b)
              {
                return a.first.tupleCat<b.first.tupleCat;
              });
    for(int newIndex=0; newIndex < sortVector.size(); ++newIndex)
      {
        sortValues.push_back(paramVector[sortVector[newIndex].second]);
        tupleMap[sortVector[newIndex].first]=newIndex;
      }
    paramVector=sortValues;
  }

};

#endif