Line data    Source code

       1             : #ifndef OPENDDS_RTPSRELAYLIB_PARTITION_INDEX_H
       2             : #define OPENDDS_RTPSRELAYLIB_PARTITION_INDEX_H
       3             : 
       4             : #include "Name.h"
       5             : #include "Utility.h"
       6             : 
       7             : #include <unordered_map>
       8             : 
       9             : namespace RtpsRelay {
      10             : 
      11             : struct GuidToParticipantGuid {
      12          21 :   OpenDDS::DCPS::GUID_t operator()(const OpenDDS::DCPS::GUID_t& x) const
      13             :   {
      14          21 :     return OpenDDS::DCPS::make_part_guid(x);
      15             :   }
      16             : };
      17             : 
      18             : struct Identity {
      19           1 :   std::string operator()(const std::string& x) const
      20             :   {
      21           1 :     return x;
      22             :   }
      23             : };
      24             : 
      25             : 
      26             : template<typename T, typename Transformer>
      27             : class TrieNode {
      28             : public:
      29             :   typedef std::shared_ptr<TrieNode> NodePtr;
      30             : 
      31           8 :   static void insert(NodePtr node, const Name& name, const typename T::value_type& guid)
      32             :   {
      33          47 :     for (const auto& atom : name) {
      34          39 :       const auto iter = node->children_.find(atom);
      35          39 :       if (iter == node->children_.end()) {
      36          38 :         NodePtr child(new TrieNode());
      37          38 :         node->children_[atom] = child;
      38          38 :         node = child;
      39          38 :       } else {
      40           1 :         node = iter->second;
      41             :       }
      42             :     }
      43             : 
      44           8 :     node->guids_.insert(guid);
      45           8 :   }
      46             : 
      47           3 :   static void remove(NodePtr node, const Name& name, const typename T::value_type& guid)
      48             :   {
      49           3 :     remove(node, name.begin(), name.end(), guid);
      50           3 :   }
      51             : 
      52          11 :   bool empty() const
      53             :   {
      54          11 :     return guids_.empty() && children_.empty();
      55             :   }
      56             : 
      57          22 :   static void lookup(NodePtr node, const Name& name, T& guids)
      58             :   {
      59          22 :     if (name.is_literal()) {
      60          13 :       lookup_literal(node, name.begin(), name.end(), false, guids);
      61             :     } else {
      62           9 :       lookup_pattern(node, name.begin(), name.end(), guids);
      63             :     }
      64          22 :   }
      65             : 
      66             : private:
      67             :   typedef std::unordered_map<Atom, NodePtr, AtomHash> ChildrenType;
      68             :   ChildrenType children_;
      69             :   T guids_;
      70             : 
      71          51 :   static void insert_guids(NodePtr node,
      72             :                            T& guids)
      73             :   {
      74          51 :     std::transform(node->guids_.begin(), node->guids_.end(), std::inserter(guids, guids.begin()), Transformer());
      75          51 :   }
      76             : 
      77         182 :   static void lookup_literal(NodePtr node,
      78             :                              Name::const_iterator begin,
      79             :                              Name::const_iterator end,
      80             :                              bool glob_only,
      81             :                              T& guids)
      82             :   {
      83         182 :     if (begin == end) {
      84          24 :       insert_guids(node, guids);
      85          24 :       lookup_globs(node, guids);
      86          24 :       return;
      87             :     }
      88             : 
      89         158 :     const auto& atom = *begin;
      90             : 
      91         368 :     for (const auto& pos : node->children_) {
      92         210 :       switch (pos.first.kind()) {
      93         119 :       case Atom::CHARACTER:
      94         119 :         if (!glob_only && pos.first == atom) {
      95          36 :           lookup_literal(pos.second, std::next(begin), end, false, guids);
      96             :         }
      97         119 :         break;
      98           6 :       case Atom::CHARACTER_CLASS:
      99           6 :         if (!glob_only && pos.first.characters().count(atom.character()) != 0) {
     100           5 :           lookup_literal(pos.second, std::next(begin), end, false, guids);
     101             :         }
     102           6 :         break;
     103           5 :       case Atom::NEGATED_CHARACTER_CLASS:
     104           5 :         if (!glob_only && pos.first.characters().count(atom.character()) == 0) {
     105           4 :           lookup_literal(pos.second, std::next(begin), end, false, guids);
     106             :         }
     107           5 :         break;
     108          21 :       case Atom::WILDCARD:
     109          21 :         if (!glob_only) {
     110           6 :           lookup_literal(pos.second, std::next(begin), end, false, guids);
     111             :         }
     112          21 :         break;
     113          59 :       case Atom::GLOB:
     114             :         // Glob consumes character and remains.
     115          59 :         lookup_literal(node, std::next(begin), end, true, guids);
     116             :         // Glob matches no characters.
     117          59 :         lookup_literal(pos.second, begin, end, false, guids);
     118          59 :         break;
     119             :       }
     120             :     }
     121             :   }
     122             : 
     123          41 :   static void lookup_globs(NodePtr node,
     124             :                            T& guids)
     125             :   {
     126          79 :     for (const auto& pos : node->children_) {
     127          38 :       if (pos.first.kind() == Atom::GLOB) {
     128          17 :         insert_guids(pos.second, guids);
     129          17 :         lookup_globs(pos.second, guids);
     130             :       }
     131             :     }
     132          41 :   }
     133             : 
     134         155 :   static void lookup_pattern(NodePtr node,
     135             :                              Name::const_iterator begin,
     136             :                              Name::const_iterator end,
     137             :                              T& guids)
     138             :   {
     139         155 :     if (begin == end) {
     140          10 :       insert_guids(node, guids);
     141          10 :       return;
     142             :     }
     143             : 
     144         145 :     const auto& atom = *begin;
     145             : 
     146         145 :     switch (atom.kind()) {
     147          74 :     case Atom::CHARACTER:
     148             :       {
     149          74 :         const auto pos = node->children_.find(atom);
     150          74 :         if (pos != node->children_.end()) {
     151          25 :           lookup_pattern(pos->second, std::next(begin), end, guids);
     152             :         }
     153             :       }
     154          74 :       break;
     155           2 :     case Atom::CHARACTER_CLASS:
     156           4 :       for (const auto& p : node->children_) {
     157           2 :         if (p.first.kind() == Atom::CHARACTER && atom.characters().count(p.first.character()) != 0) {
     158           2 :           lookup_pattern(p.second, std::next(begin), end, guids);
     159             :         }
     160             :       }
     161           2 :       break;
     162           2 :     case Atom::NEGATED_CHARACTER_CLASS:
     163           4 :       for (const auto& p : node->children_) {
     164           2 :         if (p.first.kind() == Atom::CHARACTER && atom.characters().count(p.first.character()) == 0) {
     165           2 :           lookup_pattern(p.second, std::next(begin), end, guids);
     166             :         }
     167             :       }
     168           2 :       break;
     169           2 :     case Atom::WILDCARD:
     170           7 :       for (const auto& p : node->children_) {
     171           5 :         if (p.first.kind() == Atom::CHARACTER) {
     172           3 :           lookup_pattern(p.second, std::next(begin), end, guids);
     173             :         }
     174             :       }
     175           2 :       break;
     176          65 :     case Atom::GLOB:
     177             :       // Glob consumes character and remains.
     178         116 :       for (const auto& p : node->children_) {
     179          51 :         if (p.first.kind() == Atom::CHARACTER) {
     180          49 :           lookup_pattern(p.second, begin, end, guids);
     181             :         }
     182             :       }
     183             :       // Glob matches no characters.
     184          65 :       lookup_pattern(node, std::next(begin), end, guids);
     185          65 :       break;
     186             :     }
     187             :   }
     188             : 
     189          14 :   static void remove(NodePtr node,
     190             :                      Name::const_iterator begin,
     191             :                      Name::const_iterator end,
     192             :                      const typename T::value_type& guid)
     193             :   {
     194          14 :     if (begin == end) {
     195           3 :       node->guids_.erase(guid);
     196           3 :       return;
     197             :     }
     198             : 
     199          11 :     const auto& atom = *begin;
     200          11 :     const auto pos = node->children_.find(atom);
     201          11 :     if (pos != node->children_.end()) {
     202          11 :       remove(pos->second, std::next(begin), end, guid);
     203          11 :       if (pos->second->empty()) {
     204          11 :         node->children_.erase(pos);
     205             :       }
     206             :     }
     207             :   }
     208             : };
     209             : 
     210             : template <typename T, typename Transformer>
     211             : class PartitionIndex {
     212             : public:
     213             :   typedef TrieNode<T, Transformer> TrieNodeT;
     214             : 
     215           4 :   PartitionIndex()
     216           4 :     : root_(new TrieNodeT())
     217           4 :   {}
     218             : 
     219           8 :   void insert(const std::string& name, const typename T::value_type& guid)
     220             :   {
     221           8 :     TrieNodeT::insert(root_, Name(name), guid);
     222           8 :     cache_.clear();
     223           8 :   }
     224             : 
     225           3 :   void remove(const std::string& name, const typename T::value_type& guid)
     226             :   {
     227           3 :     TrieNodeT::remove(root_, Name(name), guid);
     228           3 :     cache_.clear();
     229           3 :   }
     230             : 
     231             :   /// If 'allowed' is not nullptr, entries inserted into 'guids' must be in 'allowed'
     232          24 :   void lookup(const std::string& name, T& guids, const T* allowed = nullptr) const
     233             :   {
     234          24 :     LimitedInserter inserter(guids, allowed);
     235          24 :     const auto pos = cache_.find(name);
     236          24 :     if (pos != cache_.end()) {
     237           2 :       inserter.insert(pos->second.begin(), pos->second.end());
     238           2 :       return;
     239             :     }
     240          22 :     T& cache_temp = cache_[name];
     241          22 :     TrieNodeT::lookup(root_, Name(name), cache_temp);
     242          22 :     inserter.insert(cache_temp.begin(), cache_temp.end());
     243             :   }
     244             : 
     245             :   class LimitedInserter {
     246             :   public:
     247          24 :     LimitedInserter(T& output, const T* limits)
     248          24 :       : output_(output)
     249          24 :       , limits_(limits)
     250          24 :     {}
     251             : 
     252          24 :     void insert(const typename T::const_iterator& begin, const typename T::const_iterator& end)
     253             :     {
     254          24 :       if (limits_) {
     255           4 :         for (auto iter = begin; iter != end; ++iter) {
     256           3 :           if (limits_->count(*iter)) {
     257           2 :             output_.insert(*iter);
     258             :           }
     259             :         }
     260             :       } else {
     261          23 :         output_.insert(begin, end);
     262             :       }
     263          24 :     }
     264             : 
     265             :   private:
     266             :     T& output_;
     267             :     const T* limits_;
     268             :   };
     269             : 
     270             : private:
     271             :   typename TrieNodeT::NodePtr root_;
     272             :   typedef std::unordered_map<std::string, T> Cache;
     273             :   mutable Cache cache_;
     274             : };
     275             : 
     276             : }
     277             : 
     278             : #endif // RTPSRELAY_PARTITION_INDEX_H_