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 Utility functions for working with Report ID sets.
31 */
32 #include "ng_reports.h"
33
34 #include "ng_holder.h"
35 #include "util/container.h"
36 #include "util/compile_context.h"
37 #include "util/graph_range.h"
38 #include "util/report_manager.h"
39
40 using namespace std;
41
42 namespace ue2 {
43
44 /** Returns the set of all reports in the graph. */
all_reports(const NGHolder & g)45 set<ReportID> all_reports(const NGHolder &g) {
46 set<ReportID> rv;
47 for (auto v : inv_adjacent_vertices_range(g.accept, g)) {
48 insert(&rv, g[v].reports);
49 }
50 for (auto v : inv_adjacent_vertices_range(g.acceptEod, g)) {
51 insert(&rv, g[v].reports);
52 }
53
54 return rv;
55 }
56
57 /** True if *all* reports in the graph are exhaustible. */
can_exhaust(const NGHolder & g,const ReportManager & rm)58 bool can_exhaust(const NGHolder &g, const ReportManager &rm) {
59 for (ReportID report_id : all_reports(g)) {
60 if (rm.getReport(report_id).ekey == INVALID_EKEY) {
61 return false;
62 }
63 }
64
65 return true;
66 }
67
set_report(NGHolder & g,ReportID internal_report)68 void set_report(NGHolder &g, ReportID internal_report) {
69 // First, wipe the report IDs on all vertices.
70 for (auto v : vertices_range(g)) {
71 g[v].reports.clear();
72 }
73
74 // Any predecessors of accept get our id.
75 for (auto v : inv_adjacent_vertices_range(g.accept, g)) {
76 g[v].reports.insert(internal_report);
77 }
78
79 // Same for preds of acceptEod, except accept itself.
80 for (auto v : inv_adjacent_vertices_range(g.acceptEod, g)) {
81 if (v == g.accept) {
82 continue;
83 }
84 g[v].reports.insert(internal_report);
85 }
86 }
87
88 /** Derive a maximum offset for the graph from the max_offset values of its
89 * reports. Returns MAX_OFFSET for inf. */
findMaxOffset(const NGHolder & g,const ReportManager & rm)90 u64a findMaxOffset(const NGHolder &g, const ReportManager &rm) {
91 u64a maxOffset = 0;
92 set<ReportID> reports = all_reports(g);
93 assert(!reports.empty());
94
95 for (ReportID report_id : all_reports(g)) {
96 const Report &ir = rm.getReport(report_id);
97 if (ir.hasBounds()) {
98 maxOffset = max(maxOffset, ir.maxOffset);
99 } else {
100 return MAX_OFFSET;
101 }
102 }
103 return maxOffset;
104 }
105
106 } // namespace ue2
107