VNFs/DPPD-PROX/tools/flow_extract/flowtable.hpp

   1 /*
   2 // Copyright (c) 2010-2017 Intel Corporation
   3 //
   4 // Licensed under the Apache License, Version 2.0 (the "License");
   5 // you may not use this file except in compliance with the License.
   6 // You may obtain a copy of the License at
   7 //
   8 //     http://www.apache.org/licenses/LICENSE-2.0
   9 //
  10 // Unless required by applicable law or agreed to in writing, software
  11 // distributed under the License is distributed on an "AS IS" BASIS,
  12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13 // See the License for the specific language governing permissions and
  14 // limitations under the License.
  15 */
  16
  17 #ifndef _FLOWTABLE_H_
  18 #define _FLOWTABLE_H_
  19
  20 #include <inttypes.h>
  21 #include <sys/time.h>
  22 #include <stdio.h>
  23 #include <cstring>
  24
  25 #include <vector>
  26 #include <list>
  27 #include <cstddef>
  28 #include <utility>
  29
  30 #include "crc.hpp"
  31 #include "timestamp.hpp"
  32
  33 using namespace std;
  34
  35 template <typename K, typename T>
  36 class FlowTable {
  37 public:
  38         struct entry {
  39                 entry(K key, T value, const struct timeval& tv, list<struct entry> *parent) :
  40                         key(key), value(value), tv(tv), parent(parent) {}
  41                 bool expired(const Timestamp &now, const Timestamp &maxDiff) const
  42                 {
  43                         return now - Timestamp(tv) > maxDiff;
  44                 }
  45                 K key;
  46                 T value;
  47                 struct timeval tv; /* List time entry has been hit */
  48                 list<struct entry> *parent;
  49         };
  50         class Iterator {
  51                 friend class FlowTable;
  52         public:
  53                 bool operator!=(const Iterator& other) {
  54                         return m_v != other.m_v ||
  55                                 m_vec_pos != other.m_vec_pos ||
  56                                 m_a != other.m_a;
  57
  58                 }
  59                 Iterator& operator++() {
  60                         m_a++;
  61                         while (m_vec_pos != m_v->size() - 1 && m_a == (*m_v)[m_vec_pos].end()) {
  62                                 m_vec_pos++;
  63                                 m_a = (*m_v)[m_vec_pos].begin();
  64                         }
  65
  66                         return *this;
  67                 }
  68                 struct entry &operator*() {
  69                         return *m_a;
  70                 }
  71         private:
  72                 Iterator(uint32_t vec_pos, vector<list<struct entry> > *v)
  73                         : m_vec_pos(vec_pos), m_v(v)
  74                 {
  75                         m_a = (*m_v)[vec_pos].begin();
  76                         while (m_vec_pos != m_v->size() - 1 && m_a == (*m_v)[m_vec_pos].end()) {
  77                                 m_vec_pos++;
  78                                 m_a = (*m_v)[m_vec_pos].begin();
  79                         }
  80                 }
  81                 Iterator(uint32_t vec_pos, vector<list<struct entry> > *v, const typename list< struct entry>::iterator& a)
  82                         : m_vec_pos(vec_pos), m_v(v), m_a(a)
  83                 { }
  84                 uint32_t m_vec_pos;
  85                 vector<list<struct entry> > *m_v;
  86                 typename list<struct entry>::iterator m_a;
  87         };
  88         uint32_t getEntryCount() const {return m_entryCount;}
  89         FlowTable(uint32_t size);
  90         void expire(const struct timeval& tv);
  91         struct entry* lookup(const K& key);
  92         void  remove(struct FlowTable<K,T>::entry* entry);
  93         struct entry* insert(const K& key, const T& value, const struct timeval& tv);
  94         Iterator begin() {return Iterator(0, &m_elems);}
  95         Iterator end() {return Iterator(m_elems.size() - 1, &m_elems, m_elems.back().end());}
  96         void clear();
  97 private:
  98         void clearBucket(list<struct entry> *l);
  99         vector<list<struct entry> > m_elems;
 100         uint32_t m_entryCount;
 101 };
 102
 103 template <typename K, typename T>
 104 FlowTable<K, T>::FlowTable(uint32_t size)
 105         : m_elems(), m_entryCount(0)
 106
 107 {
 108         m_elems.resize(size);
 109 }
 110
 111 template <typename K, typename T>
 112 struct FlowTable<K, T>::entry* FlowTable<K, T>::lookup(const K& key)
 113 {
 114         uint32_t ret = crc32((uint8_t*)&key, sizeof(K), 0);
 115
 116         list<struct entry> &l = m_elems[ret % m_elems.size()];
 117
 118         if (l.empty())
 119                 return NULL;
 120
 121         for (typename list<struct entry>::iterator it = l.begin(); it != l.end(); ++it) {
 122                 if (memcmp(&((*it).key), &key, sizeof(key)) == 0)
 123                         return &(*it);
 124         }
 125         return NULL;
 126 }
 127
 128 template <typename K, typename T>
 129 struct FlowTable<K, T>::entry *FlowTable<K, T>::insert(const K& key, const T& value, const struct timeval& tv)
 130 {
 131         uint32_t ret = crc32((uint8_t*)&key, sizeof(K), 0);
 132         list<struct entry> &l = m_elems[ret % m_elems.size()];
 133
 134         l.push_back(entry(key, value, tv, &l));
 135
 136         struct entry &n = l.back();
 137         m_entryCount++;
 138         n.key = key;
 139         n.value = value;
 140         return &n;
 141 }
 142
 143 template <typename K, typename T>
 144 void FlowTable<K, T>::remove(struct FlowTable<K,T>::entry* entry)
 145 {
 146         list<struct entry> &l = *entry->parent;
 147
 148         for (typename list<struct entry>::iterator it = l.begin(); it != l.end(); ++it) {
 149                 if (memcmp(&((*it).key), &entry->key, sizeof(entry->key)) == 0) {
 150                         l.erase(it);
 151                         m_entryCount--;
 152                         return ;
 153                 }
 154         }
 155 }
 156
 157 template <typename K, typename T>
 158 void FlowTable<K, T>::clearBucket(list<struct entry> *l)
 159 {
 160         while (!l->empty()) {
 161                 m_entryCount--;
 162                 l->erase(l->begin());
 163         }
 164 }
 165
 166 template <typename K, typename T>
 167 void FlowTable<K, T>::clear()
 168 {
 169         for (size_t i = 0; i < m_elems.size(); ++i) {
 170                 clearBucket(&m_elems[i]);
 171         }
 172 }
 173
 174 #endif /* _FLOWTABLE_H_ */