← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/include/llvm/ADT/DeltaAlgorithm.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/include/llvm/ADT/DeltaAlgorithm.h
 
1
//===--- DeltaAlgorithm.h - A Set Minimization Algorithm -------*- 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
#ifndef LLVM_ADT_DELTAALGORITHM_H
 
10
#define LLVM_ADT_DELTAALGORITHM_H
 
11
 
 
12
#include <vector>
 
13
#include <set>
 
14
 
 
15
namespace llvm {
 
16
 
 
17
/// DeltaAlgorithm - Implements the delta debugging algorithm (A. Zeller '99)
 
18
/// for minimizing arbitrary sets using a predicate function.
 
19
///
 
20
/// The result of the algorithm is a subset of the input change set which is
 
21
/// guaranteed to satisfy the predicate, assuming that the input set did. For
 
22
/// well formed predicates, the result set is guaranteed to be such that
 
23
/// removing any single element would falsify the predicate.
 
24
///
 
25
/// For best results the predicate function *should* (but need not) satisfy
 
26
/// certain properties, in particular:
 
27
///  (1) The predicate should return false on an empty set and true on the full
 
28
///  set.
 
29
///  (2) If the predicate returns true for a set of changes, it should return
 
30
///  true for all supersets of that set.
 
31
///
 
32
/// It is not an error to provide a predicate that does not satisfy these
 
33
/// requirements, and the algorithm will generally produce reasonable
 
34
/// results. However, it may run substantially more tests than with a good
 
35
/// predicate.
 
36
class DeltaAlgorithm {
 
37
public:
 
38
  typedef unsigned change_ty;
 
39
  // FIXME: Use a decent data structure.
 
40
  typedef std::set<change_ty> changeset_ty;
 
41
  typedef std::vector<changeset_ty> changesetlist_ty;
 
42
 
 
43
private:
 
44
  /// Cache of failed test results. Successful test results are never cached
 
45
  /// since we always reduce following a success.
 
46
  std::set<changeset_ty> FailedTestsCache;
 
47
 
 
48
  /// GetTestResult - Get the test result for the \arg Changes from the
 
49
  /// cache, executing the test if necessary.
 
50
  ///
 
51
  /// \param Changes - The change set to test.
 
52
  /// \return - The test result.
 
53
  bool GetTestResult(const changeset_ty &Changes);
 
54
 
 
55
  /// Split - Partition a set of changes \arg S into one or two subsets.
 
56
  void Split(const changeset_ty &S, changesetlist_ty &Res);
 
57
 
 
58
  /// Delta - Minimize a set of \arg Changes which has been partioned into
 
59
  /// smaller sets, by attempting to remove individual subsets.
 
60
  changeset_ty Delta(const changeset_ty &Changes,
 
61
                     const changesetlist_ty &Sets);
 
62
 
 
63
  /// Search - Search for a subset (or subsets) in \arg Sets which can be
 
64
  /// removed from \arg Changes while still satisfying the predicate.
 
65
  ///
 
66
  /// \param Res - On success, a subset of Changes which satisfies the
 
67
  /// predicate.
 
68
  /// \return - True on success.
 
69
  bool Search(const changeset_ty &Changes, const changesetlist_ty &Sets,
 
70
              changeset_ty &Res);
 
71
              
 
72
protected:
 
73
  /// UpdatedSearchState - Callback used when the search state changes.
 
74
  virtual void UpdatedSearchState(const changeset_ty &Changes,
 
75
                                  const changesetlist_ty &Sets) {}
 
76
 
 
77
  /// ExecuteOneTest - Execute a single test predicate on the change set \arg S.
 
78
  virtual bool ExecuteOneTest(const changeset_ty &S) = 0;
 
79
 
 
80
public:
 
81
  virtual ~DeltaAlgorithm();
 
82
 
 
83
  /// Run - Minimize the set \arg Changes by executing \see ExecuteOneTest() on
 
84
  /// subsets of changes and returning the smallest set which still satisfies
 
85
  /// the test predicate.
 
86
  changeset_ty Run(const changeset_ty &Changes);
 
87
};
 
88
 
 
89
} // end namespace llvm
 
90
 
 
91
#endif