← 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/StringMap.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/StringMap.h
 
1
//===--- StringMap.h - String Hash table map interface ----------*- 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 StringMap class.
 
11
//
 
12
//===----------------------------------------------------------------------===//
 
13
 
 
14
#ifndef LLVM_ADT_STRINGMAP_H
 
15
#define LLVM_ADT_STRINGMAP_H
 
16
 
 
17
#include "llvm/ADT/StringRef.h"
 
18
#include "llvm/Support/Allocator.h"
 
19
#include <cstring>
 
20
#include <string>
 
21
 
 
22
namespace llvm {
 
23
  template<typename ValueT>
 
24
  class StringMapConstIterator;
 
25
  template<typename ValueT>
 
26
  class StringMapIterator;
 
27
  template<typename ValueTy>
 
28
  class StringMapEntry;
 
29
 
 
30
/// StringMapEntryInitializer - This datatype can be partially specialized for
 
31
/// various datatypes in a stringmap to allow them to be initialized when an
 
32
/// entry is default constructed for the map.
 
33
template<typename ValueTy>
 
34
class StringMapEntryInitializer {
 
35
public:
 
36
  template <typename InitTy>
 
37
  static void Initialize(StringMapEntry<ValueTy> &T, InitTy InitVal) {
 
38
    T.second = InitVal;
 
39
  }
 
40
};
 
41
 
 
42
 
 
43
/// StringMapEntryBase - Shared base class of StringMapEntry instances.
 
44
class StringMapEntryBase {
 
45
  unsigned StrLen;
 
46
public:
 
47
  explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {}
 
48
 
 
49
  unsigned getKeyLength() const { return StrLen; }
 
50
};
 
51
 
 
52
/// StringMapImpl - This is the base class of StringMap that is shared among
 
53
/// all of its instantiations.
 
54
class StringMapImpl {
 
55
public:
 
56
  /// ItemBucket - The hash table consists of an array of these.  If Item is
 
57
  /// non-null, this is an extant entry, otherwise, it is a hole.
 
58
  struct ItemBucket {
 
59
    /// FullHashValue - This remembers the full hash value of the key for
 
60
    /// easy scanning.
 
61
    unsigned FullHashValue;
 
62
 
 
63
    /// Item - This is a pointer to the actual item object.
 
64
    StringMapEntryBase *Item;
 
65
  };
 
66
 
 
67
protected:
 
68
  ItemBucket *TheTable;
 
69
  unsigned NumBuckets;
 
70
  unsigned NumItems;
 
71
  unsigned NumTombstones;
 
72
  unsigned ItemSize;
 
73
protected:
 
74
  explicit StringMapImpl(unsigned itemSize) : ItemSize(itemSize) {
 
75
    // Initialize the map with zero buckets to allocation.
 
76
    TheTable = 0;
 
77
    NumBuckets = 0;
 
78
    NumItems = 0;
 
79
    NumTombstones = 0;
 
80
  }
 
81
  StringMapImpl(unsigned InitSize, unsigned ItemSize);
 
82
  void RehashTable();
 
83
 
 
84
  /// ShouldRehash - Return true if the table should be rehashed after a new
 
85
  /// element was recently inserted.
 
86
  bool ShouldRehash() const {
 
87
    // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
 
88
    // the buckets are empty (meaning that many are filled with tombstones),
 
89
    // grow the table.
 
90
    return NumItems*4 > NumBuckets*3 ||
 
91
           NumBuckets-(NumItems+NumTombstones) < NumBuckets/8;
 
92
  }
 
93
 
 
94
  /// LookupBucketFor - Look up the bucket that the specified string should end
 
95
  /// up in.  If it already exists as a key in the map, the Item pointer for the
 
96
  /// specified bucket will be non-null.  Otherwise, it will be null.  In either
 
97
  /// case, the FullHashValue field of the bucket will be set to the hash value
 
98
  /// of the string.
 
99
  unsigned LookupBucketFor(StringRef Key);
 
100
 
 
101
  /// FindKey - Look up the bucket that contains the specified key. If it exists
 
102
  /// in the map, return the bucket number of the key.  Otherwise return -1.
 
103
  /// This does not modify the map.
 
104
  int FindKey(StringRef Key) const;
 
105
 
 
106
  /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
 
107
  /// delete it.  This aborts if the value isn't in the table.
 
108
  void RemoveKey(StringMapEntryBase *V);
 
109
 
 
110
  /// RemoveKey - Remove the StringMapEntry for the specified key from the
 
111
  /// table, returning it.  If the key is not in the table, this returns null.
 
112
  StringMapEntryBase *RemoveKey(StringRef Key);
 
113
private:
 
114
  void init(unsigned Size);
 
115
public:
 
116
  static StringMapEntryBase *getTombstoneVal() {
 
117
    return (StringMapEntryBase*)-1;
 
118
  }
 
119
 
 
120
  unsigned getNumBuckets() const { return NumBuckets; }
 
121
  unsigned getNumItems() const { return NumItems; }
 
122
 
 
123
  bool empty() const { return NumItems == 0; }
 
124
  unsigned size() const { return NumItems; }
 
125
};
 
126
 
 
127
/// StringMapEntry - This is used to represent one value that is inserted into
 
128
/// a StringMap.  It contains the Value itself and the key: the string length
 
129
/// and data.
 
130
template<typename ValueTy>
 
131
class StringMapEntry : public StringMapEntryBase {
 
132
public:
 
133
  ValueTy second;
 
134
 
 
135
  explicit StringMapEntry(unsigned strLen)
 
136
    : StringMapEntryBase(strLen), second() {}
 
137
  StringMapEntry(unsigned strLen, const ValueTy &V)
 
138
    : StringMapEntryBase(strLen), second(V) {}
 
139
 
 
140
  StringRef getKey() const { 
 
141
    return StringRef(getKeyData(), getKeyLength()); 
 
142
  }
 
143
 
 
144
  const ValueTy &getValue() const { return second; }
 
145
  ValueTy &getValue() { return second; }
 
146
 
 
147
  void setValue(const ValueTy &V) { second = V; }
 
148
 
 
149
  /// getKeyData - Return the start of the string data that is the key for this
 
150
  /// value.  The string data is always stored immediately after the
 
151
  /// StringMapEntry object.
 
152
  const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
 
153
 
 
154
  const char *first() const { return getKeyData(); }
 
155
 
 
156
  /// Create - Create a StringMapEntry for the specified key and default
 
157
  /// construct the value.
 
158
  template<typename AllocatorTy, typename InitType>
 
159
  static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd,
 
160
                                AllocatorTy &Allocator,
 
161
                                InitType InitVal) {
 
162
    unsigned KeyLength = static_cast<unsigned>(KeyEnd-KeyStart);
 
163
 
 
164
    // Okay, the item doesn't already exist, and 'Bucket' is the bucket to fill
 
165
    // in.  Allocate a new item with space for the string at the end and a null
 
166
    // terminator.
 
167
 
 
168
    unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+
 
169
      KeyLength+1;
 
170
    unsigned Alignment = alignof<StringMapEntry>();
 
171
 
 
172
    StringMapEntry *NewItem =
 
173
      static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
 
174
 
 
175
    // Default construct the value.
 
176
    new (NewItem) StringMapEntry(KeyLength);
 
177
 
 
178
    // Copy the string information.
 
179
    char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
 
180
    memcpy(StrBuffer, KeyStart, KeyLength);
 
181
    StrBuffer[KeyLength] = 0;  // Null terminate for convenience of clients.
 
182
 
 
183
    // Initialize the value if the client wants to.
 
184
    StringMapEntryInitializer<ValueTy>::Initialize(*NewItem, InitVal);
 
185
    return NewItem;
 
186
  }
 
187
 
 
188
  template<typename AllocatorTy>
 
189
  static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd,
 
190
                                AllocatorTy &Allocator) {
 
191
    return Create(KeyStart, KeyEnd, Allocator, 0);
 
192
  }
 
193
 
 
194
 
 
195
  /// Create - Create a StringMapEntry with normal malloc/free.
 
196
  template<typename InitType>
 
197
  static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd,
 
198
                                InitType InitVal) {
 
199
    MallocAllocator A;
 
200
    return Create(KeyStart, KeyEnd, A, InitVal);
 
201
  }
 
202
 
 
203
  static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) {
 
204
    return Create(KeyStart, KeyEnd, ValueTy());
 
205
  }
 
206
 
 
207
  /// GetStringMapEntryFromValue - Given a value that is known to be embedded
 
208
  /// into a StringMapEntry, return the StringMapEntry itself.
 
209
  static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) {
 
210
    StringMapEntry *EPtr = 0;
 
211
    char *Ptr = reinterpret_cast<char*>(&V) -
 
212
                  (reinterpret_cast<char*>(&EPtr->second) -
 
213
                   reinterpret_cast<char*>(EPtr));
 
214
    return *reinterpret_cast<StringMapEntry*>(Ptr);
 
215
  }
 
216
  static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) {
 
217
    return GetStringMapEntryFromValue(const_cast<ValueTy&>(V));
 
218
  }
 
219
 
 
220
  /// Destroy - Destroy this StringMapEntry, releasing memory back to the
 
221
  /// specified allocator.
 
222
  template<typename AllocatorTy>
 
223
  void Destroy(AllocatorTy &Allocator) {
 
224
    // Free memory referenced by the item.
 
225
    this->~StringMapEntry();
 
226
    Allocator.Deallocate(this);
 
227
  }
 
228
 
 
229
  /// Destroy this object, releasing memory back to the malloc allocator.
 
230
  void Destroy() {
 
231
    MallocAllocator A;
 
232
    Destroy(A);
 
233
  }
 
234
};
 
235
 
 
236
 
 
237
/// StringMap - This is an unconventional map that is specialized for handling
 
238
/// keys that are "strings", which are basically ranges of bytes. This does some
 
239
/// funky memory allocation and hashing things to make it extremely efficient,
 
240
/// storing the string data *after* the value in the map.
 
241
template<typename ValueTy, typename AllocatorTy = MallocAllocator>
 
242
class StringMap : public StringMapImpl {
 
243
  AllocatorTy Allocator;
 
244
  typedef StringMapEntry<ValueTy> MapEntryTy;
 
245
public:
 
246
  StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
 
247
  explicit StringMap(unsigned InitialSize)
 
248
    : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
 
249
  explicit StringMap(const StringMap &RHS)
 
250
    : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {
 
251
    assert(RHS.empty() &&
 
252
           "Copy ctor from non-empty stringmap not implemented yet!");
 
253
  }
 
254
  void operator=(const StringMap &RHS) {
 
255
    assert(RHS.empty() &&
 
256
           "assignment from non-empty stringmap not implemented yet!");
 
257
    clear();
 
258
  }
 
259
 
 
260
 
 
261
  AllocatorTy &getAllocator() { return Allocator; }
 
262
  const AllocatorTy &getAllocator() const { return Allocator; }
 
263
 
 
264
  typedef const char* key_type;
 
265
  typedef ValueTy mapped_type;
 
266
  typedef StringMapEntry<ValueTy> value_type;
 
267
  typedef size_t size_type;
 
268
 
 
269
  typedef StringMapConstIterator<ValueTy> const_iterator;
 
270
  typedef StringMapIterator<ValueTy> iterator;
 
271
 
 
272
  iterator begin() {
 
273
    return iterator(TheTable, NumBuckets == 0);
 
274
  }
 
275
  iterator end() {
 
276
    return iterator(TheTable+NumBuckets, true);
 
277
  }
 
278
  const_iterator begin() const {
 
279
    return const_iterator(TheTable, NumBuckets == 0);
 
280
  }
 
281
  const_iterator end() const {
 
282
    return const_iterator(TheTable+NumBuckets, true);
 
283
  }
 
284
 
 
285
  iterator find(StringRef Key) {
 
286
    int Bucket = FindKey(Key);
 
287
    if (Bucket == -1) return end();
 
288
    return iterator(TheTable+Bucket);
 
289
  }
 
290
 
 
291
  const_iterator find(StringRef Key) const {
 
292
    int Bucket = FindKey(Key);
 
293
    if (Bucket == -1) return end();
 
294
    return const_iterator(TheTable+Bucket);
 
295
  }
 
296
 
 
297
   /// lookup - Return the entry for the specified key, or a default
 
298
  /// constructed value if no such entry exists.
 
299
  ValueTy lookup(StringRef Key) const {
 
300
    const_iterator it = find(Key);
 
301
    if (it != end())
 
302
      return it->second;
 
303
    return ValueTy();
 
304
  }
 
305
 
 
306
  ValueTy& operator[](StringRef Key) {
 
307
    return GetOrCreateValue(Key).getValue();
 
308
  }
 
309
 
 
310
  size_type count(StringRef Key) const {
 
311
    return find(Key) == end() ? 0 : 1;
 
312
  }
 
313
 
 
314
  /// insert - Insert the specified key/value pair into the map.  If the key
 
315
  /// already exists in the map, return false and ignore the request, otherwise
 
316
  /// insert it and return true.
 
317
  bool insert(MapEntryTy *KeyValue) {
 
318
    unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
 
319
    ItemBucket &Bucket = TheTable[BucketNo];
 
320
    if (Bucket.Item && Bucket.Item != getTombstoneVal())
 
321
      return false;  // Already exists in map.
 
322
 
 
323
    if (Bucket.Item == getTombstoneVal())
 
324
      --NumTombstones;
 
325
    Bucket.Item = KeyValue;
 
326
    ++NumItems;
 
327
 
 
328
    if (ShouldRehash())
 
329
      RehashTable();
 
330
    return true;
 
331
  }
 
332
 
 
333
  // clear - Empties out the StringMap
 
334
  void clear() {
 
335
    if (empty()) return;
 
336
 
 
337
    // Zap all values, resetting the keys back to non-present (not tombstone),
 
338
    // which is safe because we're removing all elements.
 
339
    for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) {
 
340
      if (I->Item && I->Item != getTombstoneVal()) {
 
341
        static_cast<MapEntryTy*>(I->Item)->Destroy(Allocator);
 
342
        I->Item = 0;
 
343
      }
 
344
    }
 
345
 
 
346
    NumItems = 0;
 
347
  }
 
348
 
 
349
  /// GetOrCreateValue - Look up the specified key in the table.  If a value
 
350
  /// exists, return it.  Otherwise, default construct a value, insert it, and
 
351
  /// return.
 
352
  template <typename InitTy>
 
353
  StringMapEntry<ValueTy> &GetOrCreateValue(StringRef Key,
 
354
                                            InitTy Val) {
 
355
    unsigned BucketNo = LookupBucketFor(Key);
 
356
    ItemBucket &Bucket = TheTable[BucketNo];
 
357
    if (Bucket.Item && Bucket.Item != getTombstoneVal())
 
358
      return *static_cast<MapEntryTy*>(Bucket.Item);
 
359
 
 
360
    MapEntryTy *NewItem =
 
361
      MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val);
 
362
 
 
363
    if (Bucket.Item == getTombstoneVal())
 
364
      --NumTombstones;
 
365
    ++NumItems;
 
366
 
 
367
    // Fill in the bucket for the hash table.  The FullHashValue was already
 
368
    // filled in by LookupBucketFor.
 
369
    Bucket.Item = NewItem;
 
370
 
 
371
    if (ShouldRehash())
 
372
      RehashTable();
 
373
    return *NewItem;
 
374
  }
 
375
 
 
376
  StringMapEntry<ValueTy> &GetOrCreateValue(StringRef Key) {
 
377
    return GetOrCreateValue(Key, ValueTy());
 
378
  }
 
379
 
 
380
  template <typename InitTy>
 
381
  StringMapEntry<ValueTy> &GetOrCreateValue(const char *KeyStart,
 
382
                                            const char *KeyEnd,
 
383
                                            InitTy Val) {
 
384
    return GetOrCreateValue(StringRef(KeyStart, KeyEnd - KeyStart), Val);
 
385
  }
 
386
 
 
387
  StringMapEntry<ValueTy> &GetOrCreateValue(const char *KeyStart,
 
388
                                            const char *KeyEnd) {
 
389
    return GetOrCreateValue(StringRef(KeyStart, KeyEnd - KeyStart));
 
390
  }
 
391
 
 
392
  /// remove - Remove the specified key/value pair from the map, but do not
 
393
  /// erase it.  This aborts if the key is not in the map.
 
394
  void remove(MapEntryTy *KeyValue) {
 
395
    RemoveKey(KeyValue);
 
396
  }
 
397
 
 
398
  void erase(iterator I) {
 
399
    MapEntryTy &V = *I;
 
400
    remove(&V);
 
401
    V.Destroy(Allocator);
 
402
  }
 
403
 
 
404
  bool erase(StringRef Key) {
 
405
    iterator I = find(Key);
 
406
    if (I == end()) return false;
 
407
    erase(I);
 
408
    return true;
 
409
  }
 
410
 
 
411
  ~StringMap() {
 
412
    clear();
 
413
    free(TheTable);
 
414
  }
 
415
};
 
416
 
 
417
 
 
418
template<typename ValueTy>
 
419
class StringMapConstIterator {
 
420
protected:
 
421
  StringMapImpl::ItemBucket *Ptr;
 
422
public:
 
423
  typedef StringMapEntry<ValueTy> value_type;
 
424
 
 
425
  explicit StringMapConstIterator(StringMapImpl::ItemBucket *Bucket,
 
426
                                  bool NoAdvance = false)
 
427
  : Ptr(Bucket) {
 
428
    if (!NoAdvance) AdvancePastEmptyBuckets();
 
429
  }
 
430
 
 
431
  const value_type &operator*() const {
 
432
    return *static_cast<StringMapEntry<ValueTy>*>(Ptr->Item);
 
433
  }
 
434
  const value_type *operator->() const {
 
435
    return static_cast<StringMapEntry<ValueTy>*>(Ptr->Item);
 
436
  }
 
437
 
 
438
  bool operator==(const StringMapConstIterator &RHS) const {
 
439
    return Ptr == RHS.Ptr;
 
440
  }
 
441
  bool operator!=(const StringMapConstIterator &RHS) const {
 
442
    return Ptr != RHS.Ptr;
 
443
  }
 
444
 
 
445
  inline StringMapConstIterator& operator++() {          // Preincrement
 
446
    ++Ptr;
 
447
    AdvancePastEmptyBuckets();
 
448
    return *this;
 
449
  }
 
450
  StringMapConstIterator operator++(int) {        // Postincrement
 
451
    StringMapConstIterator tmp = *this; ++*this; return tmp;
 
452
  }
 
453
 
 
454
private:
 
455
  void AdvancePastEmptyBuckets() {
 
456
    while (Ptr->Item == 0 || Ptr->Item == StringMapImpl::getTombstoneVal())
 
457
      ++Ptr;
 
458
  }
 
459
};
 
460
 
 
461
template<typename ValueTy>
 
462
class StringMapIterator : public StringMapConstIterator<ValueTy> {
 
463
public:
 
464
  explicit StringMapIterator(StringMapImpl::ItemBucket *Bucket,
 
465
                             bool NoAdvance = false)
 
466
    : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) {
 
467
  }
 
468
  StringMapEntry<ValueTy> &operator*() const {
 
469
    return *static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item);
 
470
  }
 
471
  StringMapEntry<ValueTy> *operator->() const {
 
472
    return static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item);
 
473
  }
 
474
};
 
475
 
 
476
}
 
477
 
 
478
#endif