← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/CodeGen/PBQP/Graph.h

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2010-03-12 11:30:04 UTC
  • mfrom: (0.41.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100312113004-b0fop4bkycszdd0z
Tags: 0.96~rc1+dfsg-0ubuntu1
https://launchpad.net/bugs/537636
* New upstream RC - FFE (LP: #537636):
  - Add OfficialDatabaseOnly option to clamav-base.postinst.in
  - Add LocalSocketGroup option to clamav-base.postinst.in
  - Add LocalSocketMode option to clamav-base.postinst.in
  - Add CrossFilesystems option to clamav-base.postinst.in
  - Add ClamukoScannerCount option to clamav-base.postinst.in
  - Add BytecodeSecurity opiton to clamav-base.postinst.in
  - Add DetectionStatsHostID option to clamav-freshclam.postinst.in
  - Add Bytecode option to clamav-freshclam.postinst.in
  - Add MilterSocketGroup option to clamav-milter.postinst.in
  - Add MilterSocketMode option to clamav-milter.postinst.in
  - Add ReportHostname option to clamav-milter.postinst.in
  - Bump libclamav SO version to 6.1.0 in libclamav6.install
  - Drop clamdmon from clamav.examples (no longer shipped by upstream)
  - Drop libclamav.a from libclamav-dev.install (not built by upstream)
  - Update SO version for lintian override for libclamav6
  - Add new Bytecode Testing Tool, usr/bin/clambc, to clamav.install
  - Add build-depends on python and python-setuptools for new test suite
  - Update debian/copyright for the embedded copy of llvm (using the system
    llvm is not currently feasible)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/CodeGen/PBQP/Graph.h
 
1
//===-------------------- Graph.h - PBQP Graph ------------------*- C++ -*-===//
 
2
//
 
3
//                     The LLVM Compiler Infrastructure
 
4
//
 
5
// This file is distributed under the University of Illinois Open Source
 
6
// License. See LICENSE.TXT for details.
 
7
//
 
8
//===----------------------------------------------------------------------===//
 
9
//
 
10
// PBQP Graph class.
 
11
//
 
12
//===----------------------------------------------------------------------===//
 
13
 
 
14
 
 
15
#ifndef LLVM_CODEGEN_PBQP_GRAPH_H
 
16
#define LLVM_CODEGEN_PBQP_GRAPH_H
 
17
 
 
18
#include "Math.h"
 
19
 
 
20
#include <list>
 
21
#include <vector>
 
22
#include <map>
 
23
 
 
24
namespace PBQP {
 
25
 
 
26
  /// PBQP Graph class.
 
27
  /// Instances of this class describe PBQP problems.
 
28
  class Graph {
 
29
  private:
 
30
 
 
31
    // ----- TYPEDEFS -----
 
32
    class NodeEntry;
 
33
    class EdgeEntry;
 
34
 
 
35
    typedef std::list<NodeEntry> NodeList;
 
36
    typedef std::list<EdgeEntry> EdgeList;
 
37
 
 
38
  public:
 
39
 
 
40
    typedef NodeList::iterator NodeItr;
 
41
    typedef NodeList::const_iterator ConstNodeItr;
 
42
 
 
43
    typedef EdgeList::iterator EdgeItr;
 
44
    typedef EdgeList::const_iterator ConstEdgeItr;
 
45
 
 
46
  private:
 
47
 
 
48
    typedef std::list<EdgeItr> AdjEdgeList;
 
49
  
 
50
  public:
 
51
 
 
52
    typedef AdjEdgeList::iterator AdjEdgeItr;
 
53
 
 
54
  private:
 
55
 
 
56
    class NodeEntry {
 
57
    private:
 
58
      Vector costs;      
 
59
      AdjEdgeList adjEdges;
 
60
      unsigned degree;
 
61
      void *data;
 
62
    public:
 
63
      NodeEntry(const Vector &costs) : costs(costs), degree(0) {}
 
64
      Vector& getCosts() { return costs; }
 
65
      const Vector& getCosts() const { return costs; }
 
66
      unsigned getDegree() const { return degree; }
 
67
      AdjEdgeItr edgesBegin() { return adjEdges.begin(); }
 
68
      AdjEdgeItr edgesEnd() { return adjEdges.end(); }
 
69
      AdjEdgeItr addEdge(EdgeItr e) {
 
70
        ++degree;
 
71
        return adjEdges.insert(adjEdges.end(), e);
 
72
      }
 
73
      void removeEdge(AdjEdgeItr ae) {
 
74
        --degree;
 
75
        adjEdges.erase(ae);
 
76
      }
 
77
      void setData(void *data) { this->data = data; }
 
78
      void* getData() { return data; }
 
79
    };
 
80
 
 
81
    class EdgeEntry {
 
82
    private:
 
83
      NodeItr node1, node2;
 
84
      Matrix costs;
 
85
      AdjEdgeItr node1AEItr, node2AEItr;
 
86
      void *data;
 
87
    public:
 
88
      EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs)
 
89
        : node1(node1), node2(node2), costs(costs) {}
 
90
      NodeItr getNode1() const { return node1; }
 
91
      NodeItr getNode2() const { return node2; }
 
92
      Matrix& getCosts() { return costs; }
 
93
      const Matrix& getCosts() const { return costs; }
 
94
      void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; }
 
95
      AdjEdgeItr getNode1AEItr() { return node1AEItr; }
 
96
      void setNode2AEItr(AdjEdgeItr ae) { node2AEItr = ae; }
 
97
      AdjEdgeItr getNode2AEItr() { return node2AEItr; }
 
98
      void setData(void *data) { this->data = data; }
 
99
      void *getData() { return data; }
 
100
    };
 
101
 
 
102
    // ----- MEMBERS -----
 
103
 
 
104
    NodeList nodes;
 
105
    unsigned numNodes;
 
106
 
 
107
    EdgeList edges;
 
108
    unsigned numEdges;
 
109
 
 
110
    // ----- INTERNAL METHODS -----
 
111
 
 
112
    NodeEntry& getNode(NodeItr nItr) { return *nItr; }
 
113
    const NodeEntry& getNode(ConstNodeItr nItr) const { return *nItr; }
 
114
 
 
115
    EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; }
 
116
    const EdgeEntry& getEdge(ConstEdgeItr eItr) const { return *eItr; }
 
117
 
 
118
    NodeItr addConstructedNode(const NodeEntry &n) {
 
119
      ++numNodes;
 
120
      return nodes.insert(nodes.end(), n);
 
121
    }
 
122
 
 
123
    EdgeItr addConstructedEdge(const EdgeEntry &e) {
 
124
      assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() &&
 
125
             "Attempt to add duplicate edge.");
 
126
      ++numEdges;
 
127
      EdgeItr edgeItr = edges.insert(edges.end(), e);
 
128
      EdgeEntry &ne = getEdge(edgeItr);
 
129
      NodeEntry &n1 = getNode(ne.getNode1());
 
130
      NodeEntry &n2 = getNode(ne.getNode2());
 
131
      // Sanity check on matrix dimensions:
 
132
      assert((n1.getCosts().getLength() == ne.getCosts().getRows()) &&
 
133
             (n2.getCosts().getLength() == ne.getCosts().getCols()) &&
 
134
             "Edge cost dimensions do not match node costs dimensions.");
 
135
      ne.setNode1AEItr(n1.addEdge(edgeItr));
 
136
      ne.setNode2AEItr(n2.addEdge(edgeItr));
 
137
      return edgeItr;
 
138
    }
 
139
 
 
140
    inline void copyFrom(const Graph &other);
 
141
  public:
 
142
 
 
143
    /// \brief Construct an empty PBQP graph.
 
144
    Graph() : numNodes(0), numEdges(0) {}
 
145
 
 
146
    /// \brief Copy construct this graph from "other". Note: Does not copy node
 
147
    ///        and edge data, only graph structure and costs.
 
148
    /// @param other Source graph to copy from.
 
149
    Graph(const Graph &other) : numNodes(0), numEdges(0) {
 
150
      copyFrom(other);
 
151
    }
 
152
 
 
153
    /// \brief Make this graph a copy of "other". Note: Does not copy node and
 
154
    ///        edge data, only graph structure and costs.
 
155
    /// @param other The graph to copy from.
 
156
    /// @return A reference to this graph.
 
157
    ///
 
158
    /// This will clear the current graph, erasing any nodes and edges added,
 
159
    /// before copying from other.
 
160
    Graph& operator=(const Graph &other) {
 
161
      clear();      
 
162
      copyFrom(other);
 
163
      return *this;
 
164
    }
 
165
 
 
166
    /// \brief Add a node with the given costs.
 
167
    /// @param costs Cost vector for the new node.
 
168
    /// @return Node iterator for the added node.
 
169
    NodeItr addNode(const Vector &costs) {
 
170
      return addConstructedNode(NodeEntry(costs));
 
171
    }
 
172
 
 
173
    /// \brief Add an edge between the given nodes with the given costs.
 
174
    /// @param n1Itr First node.
 
175
    /// @param n2Itr Second node.
 
176
    /// @return Edge iterator for the added edge.
 
177
    EdgeItr addEdge(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr,
 
178
                    const Matrix &costs) {
 
179
      assert(getNodeCosts(n1Itr).getLength() == costs.getRows() &&
 
180
             getNodeCosts(n2Itr).getLength() == costs.getCols() &&
 
181
             "Matrix dimensions mismatch.");
 
182
      return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs)); 
 
183
    }
 
184
 
 
185
    /// \brief Get the number of nodes in the graph.
 
186
    /// @return Number of nodes in the graph.
 
187
    unsigned getNumNodes() const { return numNodes; }
 
188
 
 
189
    /// \brief Get the number of edges in the graph.
 
190
    /// @return Number of edges in the graph.
 
191
    unsigned getNumEdges() const { return numEdges; }
 
192
 
 
193
    /// \brief Get a node's cost vector.
 
194
    /// @param nItr Node iterator.
 
195
    /// @return Node cost vector.
 
196
    Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); }
 
197
 
 
198
    /// \brief Get a node's cost vector (const version).
 
199
    /// @param nItr Node iterator.
 
200
    /// @return Node cost vector.
 
201
    const Vector& getNodeCosts(ConstNodeItr nItr) const {
 
202
      return getNode(nItr).getCosts();
 
203
    }
 
204
 
 
205
    /// \brief Set a node's data pointer.
 
206
    /// @param nItr Node iterator.
 
207
    /// @param data Pointer to node data.
 
208
    ///
 
209
    /// Typically used by a PBQP solver to attach data to aid in solution.
 
210
    void setNodeData(NodeItr nItr, void *data) { getNode(nItr).setData(data); }
 
211
 
 
212
    /// \brief Get the node's data pointer.
 
213
    /// @param nItr Node iterator.
 
214
    /// @return Pointer to node data.
 
215
    void* getNodeData(NodeItr nItr) { return getNode(nItr).getData(); }
 
216
    
 
217
    /// \brief Get an edge's cost matrix.
 
218
    /// @param eItr Edge iterator.
 
219
    /// @return Edge cost matrix.
 
220
    Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); }
 
221
 
 
222
    /// \brief Get an edge's cost matrix (const version).
 
223
    /// @param eItr Edge iterator.
 
224
    /// @return Edge cost matrix.
 
225
    const Matrix& getEdgeCosts(ConstEdgeItr eItr) const {
 
226
      return getEdge(eItr).getCosts();
 
227
    }
 
228
 
 
229
    /// \brief Set an edge's data pointer.
 
230
    /// @param eItr Edge iterator.
 
231
    /// @param data Pointer to edge data.
 
232
    ///
 
233
    /// Typically used by a PBQP solver to attach data to aid in solution.
 
234
    void setEdgeData(EdgeItr eItr, void *data) { getEdge(eItr).setData(data); }
 
235
 
 
236
    /// \brief Get an edge's data pointer.
 
237
    /// @param eItr Edge iterator.
 
238
    /// @return Pointer to edge data. 
 
239
    void* getEdgeData(EdgeItr eItr) { return getEdge(eItr).getData(); }
 
240
 
 
241
    /// \brief Get a node's degree.
 
242
    /// @param nItr Node iterator.
 
243
    /// @return The degree of the node.
 
244
    unsigned getNodeDegree(NodeItr nItr) const {
 
245
      return getNode(nItr).getDegree();
 
246
    }
 
247
 
 
248
    /// \brief Begin iterator for node set.
 
249
    NodeItr nodesBegin() { return nodes.begin(); }
 
250
 
 
251
    /// \brief Begin const iterator for node set.
 
252
    ConstNodeItr nodesBegin() const { return nodes.begin(); }
 
253
 
 
254
    /// \brief End iterator for node set.
 
255
    NodeItr nodesEnd() { return nodes.end(); }
 
256
 
 
257
    /// \brief End const iterator for node set.
 
258
    ConstNodeItr nodesEnd() const { return nodes.end(); }
 
259
 
 
260
    /// \brief Begin iterator for edge set.
 
261
    EdgeItr edgesBegin() { return edges.begin(); }
 
262
 
 
263
    /// \brief End iterator for edge set.
 
264
    EdgeItr edgesEnd() { return edges.end(); }
 
265
 
 
266
    /// \brief Get begin iterator for adjacent edge set.
 
267
    /// @param nItr Node iterator.
 
268
    /// @return Begin iterator for the set of edges connected to the given node.
 
269
    AdjEdgeItr adjEdgesBegin(NodeItr nItr) {
 
270
      return getNode(nItr).edgesBegin();
 
271
    }
 
272
 
 
273
    /// \brief Get end iterator for adjacent edge set.
 
274
    /// @param nItr Node iterator.
 
275
    /// @return End iterator for the set of edges connected to the given node.
 
276
    AdjEdgeItr adjEdgesEnd(NodeItr nItr) {
 
277
      return getNode(nItr).edgesEnd();
 
278
    }
 
279
 
 
280
    /// \brief Get the first node connected to this edge.
 
281
    /// @param eItr Edge iterator.
 
282
    /// @return The first node connected to the given edge. 
 
283
    NodeItr getEdgeNode1(EdgeItr eItr) {
 
284
      return getEdge(eItr).getNode1();
 
285
    }
 
286
 
 
287
    /// \brief Get the second node connected to this edge.
 
288
    /// @param eItr Edge iterator.
 
289
    /// @return The second node connected to the given edge. 
 
290
    NodeItr getEdgeNode2(EdgeItr eItr) {
 
291
      return getEdge(eItr).getNode2();
 
292
    } 
 
293
 
 
294
    /// \brief Get the "other" node connected to this edge.
 
295
    /// @param eItr Edge iterator.
 
296
    /// @param nItr Node iterator for the "given" node.
 
297
    /// @return The iterator for the "other" node connected to this edge. 
 
298
    NodeItr getEdgeOtherNode(EdgeItr eItr, NodeItr nItr) {
 
299
      EdgeEntry &e = getEdge(eItr);
 
300
      if (e.getNode1() == nItr) {
 
301
        return e.getNode2();
 
302
      } // else
 
303
      return e.getNode1();
 
304
    }
 
305
 
 
306
    /// \brief Get the edge connecting two nodes.
 
307
    /// @param n1Itr First node iterator.
 
308
    /// @param n2Itr Second node iterator.
 
309
    /// @return An iterator for edge (n1Itr, n2Itr) if such an edge exists,
 
310
    ///         otherwise returns edgesEnd(). 
 
311
    EdgeItr findEdge(NodeItr n1Itr, NodeItr n2Itr) {
 
312
      for (AdjEdgeItr aeItr = adjEdgesBegin(n1Itr), aeEnd = adjEdgesEnd(n1Itr);
 
313
         aeItr != aeEnd; ++aeItr) {
 
314
        if ((getEdgeNode1(*aeItr) == n2Itr) ||
 
315
            (getEdgeNode2(*aeItr) == n2Itr)) {
 
316
          return *aeItr;
 
317
        }
 
318
      }
 
319
      return edges.end();
 
320
    }
 
321
 
 
322
    /// \brief Remove a node from the graph.
 
323
    /// @param nItr Node iterator.
 
324
    void removeNode(NodeItr nItr) {
 
325
      NodeEntry &n = getNode(nItr);
 
326
      for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end;) {
 
327
        EdgeItr eItr = *itr;
 
328
        ++itr;
 
329
        removeEdge(eItr); 
 
330
      }
 
331
      nodes.erase(nItr);
 
332
      --numNodes;
 
333
    }
 
334
 
 
335
    /// \brief Remove an edge from the graph.
 
336
    /// @param eItr Edge iterator.
 
337
    void removeEdge(EdgeItr eItr) {
 
338
      EdgeEntry &e = getEdge(eItr);
 
339
      NodeEntry &n1 = getNode(e.getNode1());
 
340
      NodeEntry &n2 = getNode(e.getNode2());
 
341
      n1.removeEdge(e.getNode1AEItr());
 
342
      n2.removeEdge(e.getNode2AEItr());
 
343
      edges.erase(eItr);
 
344
      --numEdges;
 
345
    }
 
346
 
 
347
    /// \brief Remove all nodes and edges from the graph.
 
348
    void clear() {
 
349
      nodes.clear();
 
350
      edges.clear();
 
351
      numNodes = numEdges = 0;
 
352
    }
 
353
 
 
354
    /// \brief Print a representation of this graph in DOT format.
 
355
    /// @param os Output stream to print on.
 
356
    template <typename OStream>
 
357
    void printDot(OStream &os) {
 
358
    
 
359
      os << "graph {\n";
 
360
 
 
361
      for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
 
362
           nodeItr != nodeEnd; ++nodeItr) {
 
363
 
 
364
        os << "  node" << nodeItr << " [ label=\""
 
365
           << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n";
 
366
      }
 
367
 
 
368
      os << "  edge [ len=" << getNumNodes() << " ]\n";
 
369
 
 
370
      for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
 
371
           edgeItr != edgeEnd; ++edgeItr) {
 
372
 
 
373
        os << "  node" << getEdgeNode1(edgeItr)
 
374
           << " -- node" << getEdgeNode2(edgeItr)
 
375
           << " [ label=\"";
 
376
 
 
377
        const Matrix &edgeCosts = getEdgeCosts(edgeItr);
 
378
 
 
379
        for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
 
380
          os << edgeCosts.getRowAsVector(i) << "\\n";
 
381
        }
 
382
        os << "\" ]\n";
 
383
      }
 
384
      os << "}\n";
 
385
    }
 
386
 
 
387
  };
 
388
 
 
389
  class NodeItrComparator {
 
390
  public:
 
391
    bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const {
 
392
      return &*n1 < &*n2;
 
393
    }
 
394
 
 
395
    bool operator()(Graph::ConstNodeItr n1, Graph::ConstNodeItr n2) const {
 
396
      return &*n1 < &*n2;
 
397
    }
 
398
  };
 
399
 
 
400
  class EdgeItrCompartor {
 
401
  public:
 
402
    bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const {
 
403
      return &*e1 < &*e2;
 
404
    }
 
405
 
 
406
    bool operator()(Graph::ConstEdgeItr e1, Graph::ConstEdgeItr e2) const {
 
407
      return &*e1 < &*e2;
 
408
    }
 
409
  };
 
410
 
 
411
  void Graph::copyFrom(const Graph &other) {
 
412
    std::map<Graph::ConstNodeItr, Graph::NodeItr,
 
413
             NodeItrComparator> nodeMap;
 
414
 
 
415
     for (Graph::ConstNodeItr nItr = other.nodesBegin(),
 
416
                             nEnd = other.nodesEnd();
 
417
         nItr != nEnd; ++nItr) {
 
418
      nodeMap[nItr] = addNode(other.getNodeCosts(nItr));
 
419
    }
 
420
      
 
421
  }
 
422
 
 
423
}
 
424
 
 
425
#endif // LLVM_CODEGEN_PBQP_GRAPH_HPP