1 | /* |
2 | * Copyright (c) 2015-2016, 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 | #include "ng_holder.h" |
30 | |
31 | #include "ng_util.h" |
32 | #include "ue2common.h" |
33 | |
34 | using namespace std; |
35 | |
36 | namespace ue2 { |
37 | |
38 | // internal use only |
39 | static NFAVertex addSpecialVertex(NGHolder &g, SpecialNodes id) { |
40 | NFAVertex v(add_vertex(g)); |
41 | g[v].index = id; |
42 | return v; |
43 | } |
44 | |
45 | NGHolder::NGHolder(nfa_kind k) |
46 | : kind (k), |
47 | // add initial special nodes |
48 | start(addSpecialVertex(*this, NODE_START)), |
49 | startDs(addSpecialVertex(*this, NODE_START_DOTSTAR)), |
50 | accept(addSpecialVertex(*this, NODE_ACCEPT)), |
51 | acceptEod(addSpecialVertex(*this, NODE_ACCEPT_EOD)) { |
52 | |
53 | // wire up some fake edges for the stylized bits of the NFA |
54 | add_edge(start, startDs, *this); |
55 | add_edge(startDs, startDs, *this); |
56 | add_edge(accept, acceptEod, *this); |
57 | |
58 | (*this)[start].char_reach.setall(); |
59 | (*this)[startDs].char_reach.setall(); |
60 | } |
61 | |
62 | NGHolder::~NGHolder(void) { |
63 | DEBUG_PRINTF("destroying holder @ %p\n" , this); |
64 | } |
65 | |
66 | void clear_graph(NGHolder &h) { |
67 | NGHolder::vertex_iterator vi, ve; |
68 | for (tie(vi, ve) = vertices(h); vi != ve;) { |
69 | NFAVertex v = *vi; |
70 | ++vi; |
71 | |
72 | clear_vertex(v, h); |
73 | if (!is_special(v, h)) { |
74 | remove_vertex(v, h); |
75 | } |
76 | } |
77 | |
78 | assert(num_vertices(h) == N_SPECIALS); |
79 | renumber_vertices(h); /* ensure that we reset our next allocated index */ |
80 | renumber_edges(h); |
81 | |
82 | // Recreate special stylised edges. |
83 | add_edge(h.start, h.startDs, h); |
84 | add_edge(h.startDs, h.startDs, h); |
85 | add_edge(h.accept, h.acceptEod, h); |
86 | } |
87 | |
88 | NFAVertex NGHolder::getSpecialVertex(u32 id) const { |
89 | switch (id) { |
90 | case NODE_START: return start; |
91 | case NODE_START_DOTSTAR: return startDs; |
92 | case NODE_ACCEPT: return accept; |
93 | case NODE_ACCEPT_EOD: return acceptEod; |
94 | default: return null_vertex(); |
95 | } |
96 | } |
97 | |
98 | } |
99 | |