hash_filter.h

Go to the documentation of this file.

#ifndef CVMFS_GARBAGE_COLLECTION_HASH_FILTER_H_
#define CVMFS_GARBAGE_COLLECTION_HASH_FILTER_H_

#include <set>

#include "crypto/hash.h"
#include "smallhash.h"

class AbstractHashFilter {
 public:
  virtual ~AbstractHashFilter() {}

  virtual void Fill(const shash::Any &hash) = 0;

  virtual bool Contains(const shash::Any &hash) const = 0;

  virtual void Freeze() {}

  virtual size_t Count() const = 0;
};


//------------------------------------------------------------------------------


class SimpleHashFilter : public AbstractHashFilter {
 public:
  SimpleHashFilter() : frozen_(false) {}

  void Fill(const shash::Any &hash) {
    assert(!frozen_);
    hashes_.insert(hash);
  }

  bool Contains(const shash::Any &hash) const {
    return hashes_.find(hash) != hashes_.end();
  }

  void Freeze() { frozen_ = true; }
  size_t Count() const { return hashes_.size(); }

 private:
  std::set<shash::Any>  hashes_;
  bool                  frozen_;
};


//------------------------------------------------------------------------------


class SmallhashFilter : public AbstractHashFilter {
 protected:
  static uint32_t hasher(const shash::Any &key) {
    // Don't start with the first bytes, because == is using them as well
    return (uint32_t) *(reinterpret_cast<const uint32_t *>(key.digest) + 1);
  }

 public:
  SmallhashFilter() : frozen_(false) {
    // zero_element is MD5("unobtanium")
    shash::Any zero_element(shash::kMd5,
                            shash::HexPtr("d61f853acc5a39e01f3906f73e31d256"));
    hashmap_.Init(1048576, zero_element, &SmallhashFilter::hasher);
  }

  void Fill(const shash::Any &hash) {
    assert(!frozen_);
    hashmap_.Insert(hash, true);
  }

  bool Contains(const shash::Any &hash) const {
    return hashmap_.Contains(hash);
  }

  void   Freeze()      { frozen_ = true;         }
  size_t Count() const { return hashmap_.size(); }

 private:
  SmallHashDynamic<shash::Any, bool>  hashmap_;
  bool                                frozen_;
};

#endif  // CVMFS_GARBAGE_COLLECTION_HASH_FILTER_H_