Program Listing for File component_cache.h

↰ Return to documentation for file (src/component_cache.h)

#ifndef COMPONENT_CACHE_H_
#define COMPONENT_CACHE_H_

#include <gmpxx.h>

#include <vector>
#include <sstream>

#include "component_types/cacheable_component.h"
#include "statistics.h"
#include "component_types/component.h"
#include "stack.h"
#include "solver_config.h"
#include "cached_assignment.h"

class ComponentCache {
 public:
  ComponentCache(DataAndStatistics &statistics, SolverConfiguration &config);

  ~ComponentCache() {
    // debug_dump_data();
    for (auto &pentry : entry_base_) {
//      if (pentry != nullptr)
//        delete pentry;
      delete pentry;  // Do NOT need the check as deleting nullptr has no effect
    }
  }

  void init(Component &super_comp, bool quiet = false);

  // compute the size in bytes of the component cache from scratch
  // the value is stored in bytes_memory_usage_
  uint64_t compute_byte_size_infrastructure();
  const CacheableComponent &entry_const(const CacheEntryID id) const {
    assert(entry_base_.size() > id);  // Verify the ID is value for the size.
    assert(entry_base_[id] != nullptr);
    return *entry_base_[id];
  }
  CacheableComponent &entry(const CacheEntryID id) {
    return const_cast<CacheableComponent&>(entry_const(id));
  }
//  /**
//   * Uses a cached component's CacheEntryID to extract the components
//   * cached information.
//   *
//   * @param comp Component to be extracted from the cache.
//   * @return Cache entry for the specified component.
//   */
//  CacheableComponent &entry(const Component& comp) {
//    return entry(comp.id());
//  }
  bool hasEntry(CacheEntryID id) const {
    assert(entry_base_.size() > id);
    return static_cast<bool>(entry_base_[id]);
  }
  inline void removeFromHashTable(CacheEntryID id);

  // we delete the Component with ID id
  // and all its descendants from the cache
  inline void cleanPollutionsInvolving(CacheEntryID id);

  // creates a CCacheEntry in the entry base
  // which contains a packed copy of comp
  // returns the id of the entry created
  // stores in the entry the position of
  // comp which is a part of the component stack
  inline CacheEntryID storeAsEntry(CacheableComponent &ccomp,
                                   CacheEntryID super_comp_id);
  bool manageNewComponent(StackLevel &top, CacheableComponent &packed_comp,
                          Component * unpacked_comp, CachedAssignment &cached_assn,
                          CacheEntryID &cache_entry_id) {
    statistics_.num_cache_look_ups_++;
    unsigned table_ofs =  packed_comp.hashkey() & table_size_mask_;

    CacheEntryID act_id = table_[table_ofs];
    while (act_id) {
      if (entry(act_id).equals(packed_comp)) {
        if (config_.verbose) {
          std::stringstream ss;
          ss << "\tCache hit for component #" << top.super_component() << " with model count "
             << entry(act_id).model_count() << " for cache ID #" << act_id;
          PrintInColor(ss, COLOR_YELLOW);
        }
//        if (config_.perform_random_sampling_ && config_.perform_sample_caching()) {
        if (config_.perform_sample_caching()) {
          // ToDo Add support for multiple samples in cache.
          assert(config_.num_samples_to_cache_ == 1);
          VariableIndex num_vars = unpacked_comp->num_variables();
          VariableIndex bit_shift = CACHED_VARIABLE_LEN * num_vars;
          mpz_class actual_model_count = entry(act_id).model_count() >> bit_shift;
          top.includeSolution(actual_model_count);
          cached_assn.ProcessComponent(unpacked_comp, entry(act_id).model_count());
        } else {
          top.includeSolution(entry(act_id).model_count());
        }
        cache_entry_id = act_id;  // Store the cache ID
        statistics_.incorporate_cache_hit(packed_comp);
        return true;
      }
      act_id = entry(act_id).next_bucket_element();
    }
    return false;
  }


  // unchecked erase of an entry from entry_base_
  void eraseEntry(CacheEntryID id) {
    statistics_.incorporate_cache_erase(*entry_base_[id]);
    delete entry_base_[id];
    entry_base_[id] = nullptr;
    free_entry_base_slots_.push_back(id);
  }

  // store the number in model_count as the model count of CacheEntryID id
  inline void storeValueOf(CacheEntryID id, const mpz_class &model_count);
  bool deleteEntries();

  // delete entries, keeping the descendants tree consistent
  inline void removeFromDescendantsTree(CacheEntryID id);

  // test function to ensure consistency of the descendant tree
  inline void test_descendantstree_consistency();

  void debug_dump_data();

 private:
  void considerCacheResize() {
    if (entry_base_.size() > table_.size()) {
      reHashTable(2*table_.size());
    }
  }

  void reHashTable(unsigned long size) {
    table_.clear();
    table_.resize(size, 0);
    // we assert that table size is a power of 2
    // otherwise the table_size_mask_ doesn't work
    assert((table_.size() & (table_.size() - 1)) == 0);
    table_size_mask_ = table_.size() - 1;
    std::cout << "ZH - Rehash the table.\n";
    std::cout << "ts " << table_.size() << " " << table_size_mask_ << std::endl;
    unsigned collisions = 0;
    for (unsigned id = 2; id < entry_base_.size(); id++) {
      if (entry_base_[id] != nullptr) {
        entry_base_[id]->set_next_bucket_element(0);
        if (entry_base_[id]->modelCountFound()) {
          unsigned table_ofs = tableEntry(id);
          collisions += (table_[table_ofs] > 0 ? 1 : 0);
          entry_base_[id]->set_next_bucket_element(table_[table_ofs]);
          table_[table_ofs] = id;
        }
      }
    }
    std::cout << "ZH - Number of collisions.\n" << "coll " << collisions << std::endl;
  }

  unsigned tableEntry(CacheEntryID id) {
    return entry(id).hashkey() & table_size_mask_;
  }

  void add_descendant(CacheEntryID compid, CacheEntryID descendantid) {
    assert(descendantid != entry_const(compid).first_descendant());
    entry(descendantid).set_next_sibling(entry_const(compid).first_descendant());
    entry(compid).set_first_descendant(descendantid);
  }

  void remove_firstdescendantOf(CacheEntryID compid) {
    CacheEntryID desc = entry(compid).first_descendant();
    if (desc != 0)
      entry(compid).set_first_descendant(entry(desc).next_sibling());
  }

  std::vector<CacheableComponent *> entry_base_;
  std::vector<CacheEntryID> free_entry_base_slots_;

  // the actual hash table
  // by means of which the cache is accessed
  std::vector<CacheEntryID> table_;

  unsigned table_size_mask_ = INT_MAX;

  DataAndStatistics &statistics_;

  unsigned long my_time_ = 0;

  SolverConfiguration &config_;
};


#include "component_cache.inc"


#endif /* COMPONENT_CACHE_H_ */