1 /* 2 * Copyright (c) 2015-2017, Intel Corporation 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are met: 6 * 7 * * Redistributions of source code must retain the above copyright notice, 8 * this list of conditions and the following disclaimer. 9 * * Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * * Neither the name of Intel Corporation nor the names of its contributors 13 * may be used to endorse or promote products derived from this software 14 * without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 26 * POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29 /** \file 30 * \brief Functions for splitting NFAGraphs into LHS and RHS. 31 */ 32 33 #ifndef NG_SPLIT_H 34 #define NG_SPLIT_H 35 36 #include "ng_holder.h" 37 38 #include <unordered_map> 39 #include <vector> 40 41 namespace ue2 { 42 43 class NGHolder; 44 45 /** Note: pivot should be a vertex that dominates acceptEod. Treating 'in' 46 * allocated to rhs if they are reachable from the pivot. Conversely, a vertex 47 * is in the lhs if it is reachable from start without going through the 48 * pivot. The pivot ends up in the LHS and any adjacent vertices in the RHS. 49 * 50 * Note: The RHS is setup to be triggered by TOP 0 51 * 52 * When multiple split vertices are provided: 53 * - RHS contains all vertices reachable from every pivot 54 * - LHS contains all vertices which are reachable from start ignoring any 55 * vertices which have an edge to every pivot 56 */ 57 void splitGraph(const NGHolder &base, NFAVertex pivot, NGHolder *lhs, 58 std::unordered_map<NFAVertex, NFAVertex> *lhs_map, 59 NGHolder *rhs, 60 std::unordered_map<NFAVertex, NFAVertex> *rhs_map); 61 62 void splitGraph(const NGHolder &base, const std::vector<NFAVertex> &pivots, 63 NGHolder *lhs, 64 std::unordered_map<NFAVertex, NFAVertex> *lhs_map, 65 NGHolder *rhs, 66 std::unordered_map<NFAVertex, NFAVertex> *rhs_map); 67 68 void splitLHS(const NGHolder &base, NFAVertex pivot, NGHolder *lhs, 69 std::unordered_map<NFAVertex, NFAVertex> *lhs_map); 70 71 void splitRHS(const NGHolder &base, const std::vector<NFAVertex> &pivots, 72 NGHolder *rhs, std::unordered_map<NFAVertex, NFAVertex> *rhs_map); 73 74 } // namespace ue2 75 76 #endif // NG_SPLIT_H 77