fastfilter::Automaton Struct Reference

#include <fast_filter.h>

Public Member Functions
	Automaton ()
void	add (const std::string &pat)
void	build ()
bool	search_any (const std::string &s) const

Static Public Member Functions
static char	norm (char c)

Public Attributes
std::vector< ACNode >	g
size_t	patterns = 0

Detailed Description

Definition at line 116 of file fast_filter.h.

Constructor & Destructor Documentation

Automaton()

fastfilter::Automaton::Automaton ( )

inline

Definition at line 118 of file fast_filter.h.

{ g.reserve(1024); g.push_back(ACNode()); }

References g.

Member Function Documentation

add()

void fastfilter::Automaton::add ( const std::string & pat )

inline

Definition at line 120 of file fast_filter.h.

                                {
    int v = 0; for(char cc : pat){ char c = norm(cc); if(!g[v].next.count(c)){ g[v].next[c] = (int)g.size(); g.push_back(ACNode()); } v = g[v].next[c]; }
    g[v].out = true; patterns++; }

References g, norm(), and patterns.

Referenced by fastfilter::Engine::load_patterns_file(), and fastfilter::Engine::load_patterns_sqlite().

build()

void fastfilter::Automaton::build ( )

inline

Definition at line 123 of file fast_filter.h.

              {
    std::deque<int> q; // BFS
    for(auto &kv : g[0].next){ q.push_back(kv.second); g[kv.second].fail = 0; }
    while(!q.empty()){
      int v = q.front(); q.pop_front();
      for(auto &kv : g[v].next){ char c = kv.first; int u = kv.second; q.push_back(u);
        int f = g[v].fail; while(f && !g[f].next.count(c)) f = g[f].fail; if(g[f].next.count(c) && g[f].next[c]!=u) g[u].fail = g[f].next[c]; else g[u].fail = 0; g[u].out = g[u].out || g[g[u].fail].out; }
    }
  }

References g.

Referenced by fastfilter::Engine::load_patterns_file(), and fastfilter::Engine::load_patterns_sqlite().

norm()

char fastfilter::Automaton::norm ( char c )

inlinestatic

Definition at line 119 of file fast_filter.h.

{ return (char)std::tolower((unsigned char)c); }

Referenced by add(), and search_any().

search_any()

bool fastfilter::Automaton::search_any ( const std::string & s ) const

inline

Definition at line 132 of file fast_filter.h.

                                            {
    int v = 0; for(char cc: s){ char c = norm(cc); while(v && !g[v].next.count(c)) v = g[v].fail; if(g[v].next.count(c)) v = g[v].next.at(c); if(g[v].out) return true; }
    return false; }

References g, and norm().

Referenced by fastfilter::Engine::check_url().

Member Data Documentation

g

std::vector<ACNode> fastfilter::Automaton::g

Definition at line 117 of file fast_filter.h.

Referenced by add(), Automaton(), build(), and search_any().

patterns

size_t fastfilter::Automaton::patterns = 0

Definition at line 117 of file fast_filter.h.

Referenced by add().

---

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

• BastionGuard/src/filters/fast_filter.h