← 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/ImmutableIntervalMap.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/ImmutableIntervalMap.h
 
1
//===--- ImmutableIntervalMap.h - Immutable (functional) map  ---*- 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
// This file defines the ImmutableIntervalMap class.
 
11
//
 
12
//===----------------------------------------------------------------------===//
 
13
#include "llvm/ADT/ImmutableMap.h"
 
14
 
 
15
namespace llvm {
 
16
 
 
17
class Interval {
 
18
private:
 
19
  uint64_t Start;
 
20
  uint64_t End;
 
21
 
 
22
public:
 
23
  Interval(uint64_t S, uint64_t E) : Start(S), End(E) {}
 
24
 
 
25
  uint64_t getStart() const { return Start; }
 
26
  uint64_t getEnd() const { return End; }
 
27
};
 
28
 
 
29
template <typename T>
 
30
struct ImutIntervalInfo {
 
31
  typedef const std::pair<Interval, T> value_type;
 
32
  typedef const value_type &value_type_ref;
 
33
  typedef const Interval key_type;
 
34
  typedef const Interval &key_type_ref;
 
35
  typedef const T data_type;
 
36
  typedef const T &data_type_ref;
 
37
 
 
38
  static key_type_ref KeyOfValue(value_type_ref V) {
 
39
    return V.first;
 
40
  }
 
41
 
 
42
  static data_type_ref DataOfValue(value_type_ref V) {
 
43
    return V.second;
 
44
  }
 
45
 
 
46
  static bool isEqual(key_type_ref L, key_type_ref R) {
 
47
    return L.getStart() == R.getStart() && L.getEnd() == R.getEnd();
 
48
  }
 
49
 
 
50
  static bool isDataEqual(data_type_ref L, data_type_ref R) {
 
51
    return ImutContainerInfo<T>::isEqual(L,R);
 
52
  }
 
53
 
 
54
  static bool isLess(key_type_ref L, key_type_ref R) {
 
55
    // Assume L and R does not overlap.
 
56
    if (L.getStart() < R.getStart()) {
 
57
      assert(L.getEnd() < R.getStart());
 
58
      return true;
 
59
    } else if (L.getStart() == R.getStart()) {
 
60
      assert(L.getEnd() == R.getEnd());
 
61
      return false;
 
62
    } else {
 
63
      assert(L.getStart() > R.getEnd());
 
64
      return false;
 
65
    }
 
66
  }
 
67
 
 
68
  static bool isContainedIn(key_type_ref K, key_type_ref L) {
 
69
    if (K.getStart() >= L.getStart() && K.getEnd() <= L.getEnd())
 
70
      return true;
 
71
    else
 
72
      return false;
 
73
  }
 
74
 
 
75
  static void Profile(FoldingSetNodeID &ID, value_type_ref V) {
 
76
    ID.AddInteger(V.first.getStart());
 
77
    ID.AddInteger(V.first.getEnd());
 
78
    ImutProfileInfo<T>::Profile(ID, V.second);
 
79
  }
 
80
};
 
81
 
 
82
template <typename ImutInfo>
 
83
class ImutIntervalAVLFactory : public ImutAVLFactory<ImutInfo> {
 
84
  typedef ImutAVLTree<ImutInfo> TreeTy;
 
85
  typedef typename ImutInfo::value_type     value_type;
 
86
  typedef typename ImutInfo::value_type_ref value_type_ref;
 
87
  typedef typename ImutInfo::key_type       key_type;
 
88
  typedef typename ImutInfo::key_type_ref   key_type_ref;
 
89
  typedef typename ImutInfo::data_type      data_type;
 
90
  typedef typename ImutInfo::data_type_ref  data_type_ref;
 
91
 
 
92
public:
 
93
  ImutIntervalAVLFactory(BumpPtrAllocator &Alloc) 
 
94
    : ImutAVLFactory<ImutInfo>(Alloc) {}
 
95
 
 
96
  TreeTy *Add(TreeTy *T, value_type_ref V) {
 
97
    T = Add_internal(V,T);
 
98
    this->MarkImmutable(T);
 
99
    return T;
 
100
  }
 
101
 
 
102
  TreeTy *Find(TreeTy *T, key_type_ref K) {
 
103
    if (!T)
 
104
      return NULL;
 
105
 
 
106
    key_type_ref CurrentKey = ImutInfo::KeyOfValue(this->Value(T));
 
107
 
 
108
    if (ImutInfo::isContainedIn(K, CurrentKey))
 
109
      return T;
 
110
    else if (ImutInfo::isLess(K, CurrentKey))
 
111
      return Find(this->Left(T), K);
 
112
    else
 
113
      return Find(this->Right(T), K);
 
114
  }
 
115
 
 
116
private:
 
117
  TreeTy *Add_internal(value_type_ref V, TreeTy *T) {
 
118
    key_type_ref K = ImutInfo::KeyOfValue(V);
 
119
    T = RemoveAllOverlaps(T, K);
 
120
    if (this->isEmpty(T))
 
121
      return this->CreateNode(NULL, V, NULL);
 
122
 
 
123
    assert(!T->isMutable());
 
124
 
 
125
    key_type_ref KCurrent = ImutInfo::KeyOfValue(this->Value(T));
 
126
 
 
127
    if (ImutInfo::isLess(K, KCurrent))
 
128
      return this->Balance(Add_internal(V, this->Left(T)), this->Value(T), this->Right(T));
 
129
    else
 
130
      return this->Balance(this->Left(T), this->Value(T), Add_internal(V, this->Right(T)));
 
131
  }
 
132
 
 
133
  // Remove all overlaps from T.
 
134
  TreeTy *RemoveAllOverlaps(TreeTy *T, key_type_ref K) {
 
135
    bool Changed;
 
136
    do {
 
137
      Changed = false;
 
138
      T = RemoveOverlap(T, K, Changed);
 
139
      this->MarkImmutable(T);
 
140
    } while (Changed);
 
141
 
 
142
    return T;
 
143
  }
 
144
 
 
145
  // Remove one overlap from T.
 
146
  TreeTy *RemoveOverlap(TreeTy *T, key_type_ref K, bool &Changed) {
 
147
    if (!T)
 
148
      return NULL;
 
149
    Interval CurrentK = ImutInfo::KeyOfValue(this->Value(T));
 
150
 
 
151
    // If current key does not overlap the inserted key.
 
152
    if (CurrentK.getStart() > K.getEnd())
 
153
      return this->Balance(RemoveOverlap(this->Left(T), K, Changed), this->Value(T), this->Right(T));
 
154
    else if (CurrentK.getEnd() < K.getStart())
 
155
      return this->Balance(this->Left(T), this->Value(T), RemoveOverlap(this->Right(T), K, Changed));
 
156
 
 
157
    // Current key overlaps with the inserted key.
 
158
    // Remove the current key.
 
159
    Changed = true;
 
160
    data_type_ref OldData = ImutInfo::DataOfValue(this->Value(T));
 
161
    T = this->Remove_internal(CurrentK, T);
 
162
    // Add back the unoverlapped part of the current key.
 
163
    if (CurrentK.getStart() < K.getStart()) {
 
164
      if (CurrentK.getEnd() <= K.getEnd()) {
 
165
        Interval NewK(CurrentK.getStart(), K.getStart()-1);
 
166
        return Add_internal(std::make_pair(NewK, OldData), T);
 
167
      } else {
 
168
        Interval NewK1(CurrentK.getStart(), K.getStart()-1);
 
169
        T = Add_internal(std::make_pair(NewK1, OldData), T); 
 
170
 
 
171
        Interval NewK2(K.getEnd()+1, CurrentK.getEnd());
 
172
        return Add_internal(std::make_pair(NewK2, OldData), T);
 
173
      }
 
174
    } else {
 
175
      if (CurrentK.getEnd() > K.getEnd()) {
 
176
        Interval NewK(K.getEnd()+1, CurrentK.getEnd());
 
177
        return Add_internal(std::make_pair(NewK, OldData), T);
 
178
      } else
 
179
        return T;
 
180
    }
 
181
  }
 
182
};
 
183
 
 
184
/// ImmutableIntervalMap maps an interval [start, end] to a value. The intervals
 
185
/// in the map are guaranteed to be disjoint.
 
186
template <typename ValT>
 
187
class ImmutableIntervalMap 
 
188
  : public ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> > {
 
189
 
 
190
  typedef typename ImutIntervalInfo<ValT>::value_type      value_type;
 
191
  typedef typename ImutIntervalInfo<ValT>::value_type_ref  value_type_ref;
 
192
  typedef typename ImutIntervalInfo<ValT>::key_type        key_type;
 
193
  typedef typename ImutIntervalInfo<ValT>::key_type_ref    key_type_ref;
 
194
  typedef typename ImutIntervalInfo<ValT>::data_type       data_type;
 
195
  typedef typename ImutIntervalInfo<ValT>::data_type_ref   data_type_ref;
 
196
  typedef ImutAVLTree<ImutIntervalInfo<ValT> > TreeTy;
 
197
 
 
198
public:
 
199
  explicit ImmutableIntervalMap(TreeTy *R) 
 
200
    : ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> >(R) {}
 
201
 
 
202
  class Factory {
 
203
    ImutIntervalAVLFactory<ImutIntervalInfo<ValT> > F;
 
204
 
 
205
  public:
 
206
    Factory(BumpPtrAllocator& Alloc) : F(Alloc) {}
 
207
 
 
208
    ImmutableIntervalMap GetEmptyMap() { 
 
209
      return ImmutableIntervalMap(F.GetEmptyTree()); 
 
210
    }
 
211
 
 
212
    ImmutableIntervalMap Add(ImmutableIntervalMap Old, 
 
213
                             key_type_ref K, data_type_ref D) {
 
214
      TreeTy *T = F.Add(Old.Root, std::make_pair<key_type, data_type>(K, D));
 
215
      return ImmutableIntervalMap(F.GetCanonicalTree(T));
 
216
    }
 
217
 
 
218
    ImmutableIntervalMap Remove(ImmutableIntervalMap Old, key_type_ref K) {
 
219
      TreeTy *T = F.Remove(Old.Root, K);
 
220
      return ImmutableIntervalMap(F.GetCanonicalTree(T));
 
221
    }
 
222
 
 
223
    data_type *Lookup(ImmutableIntervalMap M, key_type_ref K) {
 
224
      TreeTy *T = F.Find(M.getRoot(), K);
 
225
      if (T)
 
226
        return &T->getValue().second;
 
227
      else
 
228
        return 0;
 
229
    }
 
230
  };
 
231
 
 
232
private:
 
233
  // For ImmutableIntervalMap, the lookup operation has to be done by the 
 
234
  // factory.
 
235
  data_type* lookup(key_type_ref K) const;
 
236
};
 
237
 
 
238
} // end namespace llvm