← Back to branch summary

~ubuntu-branches/ubuntu/saucy/clamav/saucy

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/Support/DeltaAlgorithm.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Leonel Nunez
  • Date: 2008-02-11 22:52:13 UTC
  • mfrom: (1.1.6 upstream)
  • mto: This revision was merged to the branch mainline in revision 38.
  • Revision ID: james.westby@ubuntu.com-20080211225213-p2uwj4czso1w2f8h
Tags: upstream-0.92~dfsg
Import upstream version 0.92~dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/Support/DeltaAlgorithm.cpp
1
 
//===--- DeltaAlgorithm.cpp - 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
 
#include "llvm/ADT/DeltaAlgorithm.h"
10
 
#include <algorithm>
11
 
#include <iterator>
12
 
using namespace llvm;
13
 
 
14
 
DeltaAlgorithm::~DeltaAlgorithm() {
15
 
}
16
 
 
17
 
bool DeltaAlgorithm::GetTestResult(const changeset_ty &Changes) {
18
 
  if (FailedTestsCache.count(Changes))
19
 
    return false;
20
 
 
21
 
  bool Result = ExecuteOneTest(Changes);
22
 
  if (!Result)
23
 
    FailedTestsCache.insert(Changes);
24
 
 
25
 
  return Result;
26
 
}
27
 
 
28
 
void DeltaAlgorithm::Split(const changeset_ty &S, changesetlist_ty &Res) {
29
 
  // FIXME: Allow clients to provide heuristics for improved splitting.
30
 
 
31
 
  // FIXME: This is really slow.
32
 
  changeset_ty LHS, RHS;
33
 
  unsigned idx = 0, N = S.size() / 2;
34
 
  for (changeset_ty::const_iterator it = S.begin(),
35
 
         ie = S.end(); it != ie; ++it, ++idx)
36
 
    ((idx < N) ? LHS : RHS).insert(*it);
37
 
  if (!LHS.empty())
38
 
    Res.push_back(LHS);
39
 
  if (!RHS.empty())
40
 
    Res.push_back(RHS);
41
 
}
42
 
 
43
 
DeltaAlgorithm::changeset_ty
44
 
DeltaAlgorithm::Delta(const changeset_ty &Changes,
45
 
                      const changesetlist_ty &Sets) {
46
 
  // Invariant: union(Res) == Changes
47
 
  UpdatedSearchState(Changes, Sets);
48
 
 
49
 
  // If there is nothing left we can remove, we are done.
50
 
  if (Sets.size() <= 1)
51
 
    return Changes;
52
 
 
53
 
  // Look for a passing subset.
54
 
  changeset_ty Res;
55
 
  if (Search(Changes, Sets, Res))
56
 
    return Res;
57
 
 
58
 
  // Otherwise, partition the sets if possible; if not we are done.
59
 
  changesetlist_ty SplitSets;
60
 
  for (changesetlist_ty::const_iterator it = Sets.begin(),
61
 
         ie = Sets.end(); it != ie; ++it)
62
 
    Split(*it, SplitSets);
63
 
  if (SplitSets.size() == Sets.size())
64
 
    return Changes;
65
 
 
66
 
  return Delta(Changes, SplitSets);
67
 
}
68
 
 
69
 
bool DeltaAlgorithm::Search(const changeset_ty &Changes,
70
 
                            const changesetlist_ty &Sets,
71
 
                            changeset_ty &Res) {
72
 
  // FIXME: Parallelize.
73
 
  for (changesetlist_ty::const_iterator it = Sets.begin(),
74
 
         ie = Sets.end(); it != ie; ++it) {
75
 
    // If the test passes on this subset alone, recurse.
76
 
    if (GetTestResult(*it)) {
77
 
      changesetlist_ty Sets;
78
 
      Split(*it, Sets);
79
 
      Res = Delta(*it, Sets);
80
 
      return true;
81
 
    }
82
 
 
83
 
    // Otherwise, if we have more than two sets, see if test passes on the
84
 
    // complement.
85
 
    if (Sets.size() > 2) {
86
 
      // FIXME: This is really slow.
87
 
      changeset_ty Complement;
88
 
      std::set_difference(
89
 
        Changes.begin(), Changes.end(), it->begin(), it->end(),
90
 
        std::insert_iterator<changeset_ty>(Complement, Complement.begin()));
91
 
      if (GetTestResult(Complement)) {
92
 
        changesetlist_ty ComplementSets;
93
 
        ComplementSets.insert(ComplementSets.end(), Sets.begin(), it);
94
 
        ComplementSets.insert(ComplementSets.end(), it + 1, Sets.end());
95
 
        Res = Delta(Complement, ComplementSets);
96
 
        return true;
97
 
      }
98
 
    }
99
 
  }
100
 
 
101
 
  return false;
102
 
}
103
 
 
104
 
DeltaAlgorithm::changeset_ty DeltaAlgorithm::Run(const changeset_ty &Changes) {
105
 
  // Check empty set first to quickly find poor test functions.
106
 
  if (GetTestResult(changeset_ty()))
107
 
    return changeset_ty();
108
 
 
109
 
  // Otherwise run the real delta algorithm.
110
 
  changesetlist_ty Sets;
111
 
  Split(Changes, Sets);
112
 
 
113
 
  return Delta(Changes, Sets);
114
 
}