hybrid_storage_manager.hxx

Go to the documentation of this file.

#include <float.h>

template<class T>
Hybrid_Storage_Manager<T>::
Hybrid_Storage_Manager(Hazy_Database *_db_conn, ondisk_storage_spec *spec, Ondisk_Storage_Manager<T> *disk, int nBuffer, bool epsused) :  _disk(disk),  _epsused(epsused)  {
  unique_id_for_ps = spec->unique_id;
  _conn = _db_conn;
  _buffer_size = nBuffer;
  int half_buf = _buffer_size / 2;
  eps_high = 0; eps_low = 0;
  
  _force_monotone = true; // TOOD: Add a parameter to set this to a non default value.
  assert(spec->strategy == hazy_model::EAGER_HAZY || spec->strategy == hazy_model::LAZY_HAZY);
  _lazy = spec->strategy == hazy_model::LAZY_HAZY;
  std::ostringstream ostr;
  ostr << "PREPARE buffer_query" << unique_id_for_ps << " AS (SELECT id,feature_vector,eps FROM " << spec->intermediate_table_name  << " WHERE eps > 0 ORDER BY eps LIMIT " << half_buf << " ) " << std::endl;
  ostr << " UNION ALL " << std::endl;
  ostr << " (SELECT id, feature_vector,eps FROM " << spec->intermediate_table_name  << " WHERE eps <= 0 ORDER BY eps DESC LIMIT " << half_buf << ")" << std::endl;
  ostr << " ORDER BY eps; " << std::endl;
  
  query_buffer_fill << "EXECUTE buffer_query" << unique_id_for_ps << ";";
  ostr << "PREPARE eps_map_query" << unique_id_for_ps << " AS SELECT id,eps FROM " << spec->intermediate_table_name  << ";";
  query_eps_exec << "EXECUTE eps_map_query" << unique_id_for_ps << ";";
  // Hybrid search queries on disk
  // This is how the hybrid memory looks, it's organized from low eps to high eps.
  // regions (I) and (III) are on disk. We are writing search queries for these regions.
  //             |--- (II) ---|                (in memory)
  // |--- (I) ---|            (--- (III) ---|  (on disk)
  // Region (I) Query
  // NB: you need to cache the model ahead of time
  // and you probably want to retrieve the waste
  // here, we switch with closed intervals [low,high]
  ostr << "PREPARE search_disk_region_one_lazy" << unique_id_for_ps << "(float8, float8) AS SELECT COUNT(*) FROM " << spec->intermediate_table_name << " WHERE eps BETWEEN $1 AND $2 AND dotprdct_cached_waste(feature_vector) > 0;" << std::endl;
  ostr << "PREPARE search_disk_region_one_eager" << unique_id_for_ps << "(float8, float8) AS SELECT COUNT(*) FROM " << spec->external_table_name << " WHERE eps BETWEEN $1 AND $2 AND class = 1;" << std::endl;
  // In region 3, to prevent duplicates, we search with half-open intervals.
  // (low,high]
  ostr << "PREPARE search_disk_region_three_lazy" << unique_id_for_ps << "(float8,float8) AS SELECT (SELECT COUNT(*) FROM " << spec->intermediate_table_name << " WHERE $1 < eps AND eps <= $2 AND dotprdct_cached_waste(feature_vector) > 0) + " << std::endl;
  ostr << "                                                               (SELECT COUNT(*) FROM " << spec->intermediate_table_name << " WHERE eps > $2);" << std::endl;
  ostr << "PREPARE search_disk_region_three_eager" << unique_id_for_ps << "(float8,float8) AS SELECT (SELECT COUNT(*) FROM " << spec->external_table_name << " WHERE $1 < eps AND eps <= $2 AND class = 1) + " << std::endl;
  ostr << "                                                                (SELECT COUNT(*) FROM " << spec->external_table_name << " WHERE eps > $2)" << std::endl;
  
  // NB: we assume that the ondisk manager has created model_caching for us.
  // This is not a great assumption, but its life.
  // a better would be to have a function inside the on disk manager that we could call.
  DEBUG_ONLY(std::cout << "[HYBRID PREPARED QUERIES] " << std::endl << ostr.str() << std::endl << "[END HYBRID PREPARED QUERIES]" << std::endl; );
  int retVal = _conn->execute_statement_msg(ostr.str().c_str(), "[Hybrid_Storage_Manager::model_prepared_statements:__FILE__: __LINE__");
  checkQueryReturnValue(retVal, ostr.str());
  
  // Logging setup
  LOGGING_ONLY(log_se_eps_hit    = 0; log_se_eps_miss    = 0;);
  LOGGING_ONLY(log_se_buffer_hit = 0; log_se_buffer_miss = 0;);
  LOGGING_ONLY(log_iu_buffer_hit = 0; log_iu_buffer_miss = 0;);
}

template<class T>
void
Hybrid_Storage_Manager<T>::
resort(struct hazy_model &m) {
  _disk->resort(m);
  LOGGING_ONLY(std::cout << "[RESORT]" << std::endl;);
  // clear the map and then fill it back up.
  _entity_map.clear(); _buffer.clear();
  typedef typename Hybrid_Storage_Manager<T>::_full_entity_entry t_fee;
  _conn->postgresTupleParser<t_fee>(query_buffer_fill.str().c_str(), t_fee::parse_tuple, _buffer);
  // sort the buffer and rebuild
  // THIS SORT SHOULD NOT BE NECESSARY since query is ordered
  // TODO: Check that it parses in the correct order in the vector, add this regression test, then remove this sort.
  // std::sort( _buffer.begin(), _buffer.end(), Hybrid_Storage_Manager<T>::_full_entity_entry::_full_entity_compare);
  
  // reconstruct _entitymap
  // determine eps_high and eps_low
  eps_high = 0.0; eps_low = 0.0;
  int n = _buffer.size();
  LOGGING_ONLY(std::cout << "[RESORT] buffer size: " << n << std::endl;);
  eps_high  = (n > 0) ? _buffer[0].eps : 0.0;
  eps_low   = (n > 1) ? _buffer[n-1].eps : eps_high;
  // Rebuild the entity map.
  VERBOSE_ONLY(std::cout << "[RESORT] entities" << std::endl;);
  for(int i = 0; i < n; i++) {
    const struct _full_entity_entry &e = _buffer[i];
    _entity_map[e.k] = i;
    VERBOSE_ONLY(std::cout << " " << e.k << "@" << i << "  eps=" << e.eps << std::endl;);
  }
  VERBOSE_ONLY(std::cout << std::endl;);
  // reset the iterators
  _full_entity_entry l;
  l.eps = 0;
  // find the upper and the lower bound
  // this could be done much more efficiently...
  low_water_it  = std::lower_bound( _buffer.begin(), _buffer.end(), l, 
                                    Hybrid_Storage_Manager<T>::_full_entity_entry::_full_entity_compare);
  high_water_it = std::upper_bound( _buffer.begin(), _buffer.end(), l,
                                    Hybrid_Storage_Manager<T>::_full_entity_entry::_full_entity_compare);
  
  // Rebuild the _epsmap
  if(_epsused) {
    _conn->postgresMapParser<key, double>(query_eps_exec.str().c_str(), Hybrid_Storage_Manager::parse_eps_map, _epsmap);
  }
  LOGGING_ONLY(double space_used_in_hybrid = 0; calculateSpaceUsed(space_used_in_hybrid););
  LOGGING_ONLY(std::cout << "[Hybrid::resort] storage used: " << space_used_in_hybrid << std::endl;);
  LOGGING_ONLY(double entity_map_used = 0; calculateSpaceUsedByEntityMap(entity_map_used););
  LOGGING_ONLY(double eps_map_used = 0; calculateSpaceUsedByEpsMap(eps_map_used););
  LOGGING_ONLY(double buffer_used = 0; calculateSpaceUsedByBuffer(buffer_used););
  LOGGING_ONLY(std::cout << "[Hybrid::resort] entity_map_used: " << entity_map_used << std::endl;);
  LOGGING_ONLY(std::cout << "[Hybrid::resort] eps_map_used: " << eps_map_used << std::endl;);
  LOGGING_ONLY(std::cout << "[Hybrid::resort] buffer_map_used: " << buffer_used << std::endl;);
}

// NB: This is not returning waste time
template<class T>
void
Hybrid_Storage_Manager<T>::
incrementalUpdate(struct hazy_model &m, double &waste_time) {
  m.invalidate_db_model();
  
  // if its lazy, then return.
  if(isLazy()) { 
    LOGGING_ONLY(std::cout << "[Hybrid::IU] LazyUpdate" << std::endl;);
    return; 
  }
  LOGGING_ONLY(std::cout << "[Hybrid::IU] Buffer size: " << _buffer.size() << " model=" << m.low_water << "," << m.high_water << std::endl;);
  //******************************
  // HERE THE STRATEGY IS EAGER
  //******************************
  Timer waste_timer(true);
  int nTotalTuples = 0, nWasteTuples = 0;
  // buffer looks like this right now:
  //             low_water -- old low_water -- old high_water -- high_water
  // in code:     new_low  -- low_water_it  -- high_water_it  -- new_high   : these are the end of iteration.
  // regions:             (1)              (2)                (3)
  // first search region (1)
  
  _tbuffer_it new_low, new_high;
  for(new_low = low_water_it;
      new_low != _buffer.begin() && new_low->eps >= m.low_water; new_low--) {
    double val = IncrementalSGD<T>::classifyExample(m._model, new_low->x);
    VERBOSE_ONLY(std::cout << "\t update: " << new_low->k << " eps=" << new_low->eps << " to " << val << std::endl;);
    new_low->label = val > 0;
    nTotalTuples++; nWasteTuples += val > 0 ? 0 : 1;
  }
  // TODO: How do we do this properly? The problem is that begin points at a valid element.
  // yet we will get kicked out of the loop; in contrast, end points to the first valid element
  // using reverse iterators is painful, because we need to conver low_water_it to a reverse iterator...
  if(new_low == _buffer.begin() && new_low != _buffer.end() && new_low->eps >= m.low_water) {
    double val = IncrementalSGD<T>::classifyExample(m._model, new_low->x);
    VERBOSE_ONLY(std::cout << "\t update: " << new_low->k << " eps=" << new_low->eps << " to " << val << "  *" <<std::endl;);
    new_low->label = val > 0;
    nTotalTuples++; nWasteTuples += val > 0 ? 0 : 1;
  }
  
  // now search region (2) and (3)
  for(new_high = low_water_it; 
      new_high != _buffer.end() && new_high->eps <= m.high_water; new_high++) {
    double val = IncrementalSGD<T>::classifyExample(m._model, new_high->x);
    VERBOSE_ONLY(std::cout << "\t update: " << new_high->k << " eps=" << new_high->eps << " to " << val  <<std::endl;);
    new_high->label = val > 0;
    nTotalTuples++; nWasteTuples += val > 0 ? 0 : 1;
  }
  
  // High_water may be actually lower than old_high_water
  if(_force_monotone && new_high != _buffer.end()) {       
    LOGGING_ONLY(int nMonotoneWaste = 0;);
    while(new_high != high_water_it && new_high->eps <= high_water_it->eps) { nTotalTuples++; new_high->label = true; new_high++; LOGGING_ONLY(nMonotoneWaste++;); }
    LOGGING_ONLY(std::cout << "[Hybrid] monotone fixes " << nMonotoneWaste << std::endl;);
  }
  // We stop the waste timer here, before we go to disk. This should only reflect the scan cost.
  double total_time = waste_timer.stop();
  
  //  if(new_low != _buffer.begin() && new_high != _buffer.end()) {
  if( (new_low == _buffer.begin() || new_high == _buffer.end()) || (_buffer.size() == 0)) {
    // it hit one of the walls, we need to go to disk.
    // this misses the buffer.
    LOGGING_ONLY(log_iu_buffer_miss++;);
    LOGGING_ONLY(std::cout << "[Hybrid::IU] miss: " << log_iu_buffer_miss << std::endl;);
    
    // call the incremental update routine on disk for two regions
    // (1) [low_water, buffer_low] and (2) [buffer_high, high_water]
    // We do not optimzie for the middle region, but it doesn't seem to work that well..
    _disk->incrementalUpdate(m,waste_time);
    LOGGING_ONLY(std::cout << "[Hybrid::IU] \t waste=" << waste_time << std::endl;);
    
  } else {
    // then it is completely contained in the buffer
    LOGGING_ONLY(log_iu_buffer_hit++;);
    // TODO: Should this be verbose?
    LOGGING_ONLY(std::cout << "[Hybrid::IU] hit: " << log_iu_buffer_hit << std::endl;);
    LOGGING_ONLY(std::cout << "\t [lw,hw]=[" << m.low_water << "," << m.high_water << "] iterators=[" << new_low->eps << "," << new_high->eps << "]" << std::endl;);
  } 
  
  // Add because disk could have set time
  waste_time += ((nTotalTuples == 0) ? 0 : total_time * (double) nWasteTuples / (double) nTotalTuples);
  low_water_it = new_low; high_water_it = new_high;
}

template<class T>
void
Hybrid_Storage_Manager<T>::
insertEntity(struct hazy_model &m, key e, T f) {
  // TODO: do we need to do the eviction? What does main memory do?
  // For now, simply insert -- wait for a rebuild.
  _disk->insertEntity(m, e, f);
}

template<class T>
void
Hybrid_Storage_Manager<T>::
getEntityClass(key e, sClass &c, struct hazy_model &m) {
  // This is only a fast path. 
  // If we are using the epsilon map, then we get rid of the automatic ins
  // and automatic outs.
  if(_epsused) {
    _tepsmap_iterator it = _epsmap.find(e);
    // check if it is an automatic out
    if(it != _epsmap.end())  {
      double eps = it->second;
      DEBUG_ONLY(std::cout << "[Hybrid::SE] e=" << e << " eps=" << eps << std::endl;);
      if(m.low_water  > eps) { 
        c = 0; 
        LOGGING_ONLY(log_se_eps_hit++;); 
        LOGGING_ONLY(std::cout << "[Hybrid::SE] pos: " << log_se_eps_hit << std::endl;);
        return; }
      // check if it is an automatic in
      if(m.high_water < eps) { 
        c = 1; 
        LOGGING_ONLY(log_se_eps_hit++;); 
        LOGGING_ONLY(std::cout << "[Hybrid::SE] neg: " << log_se_eps_hit << std::endl;);
        return; 
      }     
      
    } else {
      // If eps is turned on, but we don't have anyone loaded this is an error.
      // assert(false);
    }
  } 
  // Log that we missed on the entity.
  LOGGING_ONLY(log_se_eps_miss++;);
  LOGGING_ONLY(std::cout << "[Hybrid::SE] eps miss: " << log_se_eps_miss << std::endl;);
  
  // Search for it in the buffer.
  _tentitymap::iterator i = _entity_map.find(e);
  if(i == _entity_map.end()) {
    LOGGING_ONLY(log_se_buffer_miss++;);
    LOGGING_ONLY(std::cout << "[Hybrid::SE] buffer miss: " << log_se_buffer_miss << std::endl;);    
    
    //  it's on disk.
    _disk->getEntityClass(e, c, m);
    return;
    
  } else {
    // here, we have found e in the buffer.
    LOGGING_ONLY(log_se_buffer_hit++;);  
    _full_entity_entry &fee = _buffer[i->second];
    
    if(isEager()) { 
      // We know that fee is between low and high water of the last update, and so its epsilon is correct.
      // WARNING: it's epsilon may be out of date if it it is not in this region, but we assume that low_water < 0 and high_water > 0 
      //          and so this check correctly classifies the entity.
      DEBUG_ONLY(assert(m.low_water <= 0 && m.high_water >= 0););
      LOGGING_ONLY(std::cout << "[Hybrid::SE] buffer_hit " << log_se_buffer_hit << " for " << i->second << " fee.k " << fee.k << " fee.eps " << fee.eps <<  " label" << fee.label << std::endl;);
      c = fee.label;
    } else {
      // If we are not using the eps map, it is possible that this entity is actually below low water (resp. above high water)
      // and we do not need to perform the classification.
      // (if we had used the epsmap, then above this check would have been performed for us)
      if(! _epsused) {  
        if(fee.eps > m.high_water) { 
          LOGGING_ONLY(log_se_eps_hit++;); // TODO: Should we add in a special counter for this event?
          LOGGING_ONLY(std::cout << "[Hybrid::SE] hit: " << log_se_buffer_hit << std::endl;);
          c = 1; return;
        }
        if(fee.eps < m.low_water) {
          LOGGING_ONLY(log_se_eps_hit++;); // TODO: Should we add in a special counter for this event?
          LOGGING_ONLY(std::cout << "[Hybrid::SE] hit: " << log_se_buffer_hit << std::endl;);     
          c = 0; 
          return;
        }
      } // end _epsused
      c = (IncrementalSGD<T>::classifyExample(m._model, fee.x) > 0); 
      // END LAZY calculations
    }
  }
}


template<class T>
void
Hybrid_Storage_Manager<T>::
getNumInClass(sClass c, int &nClass, struct hazy_model &m, double &waste_time) {
  LOGGING_ONLY(double space_used_in_hybrid = 0; calculateSpaceUsed(space_used_in_hybrid););
  LOGGING_ONLY(std::cout << "[Hybrid::GetNum] storage used: " << space_used_in_hybrid << std::endl;);
  LOGGING_ONLY(double entity_map_used = 0; calculateSpaceUsedByEntityMap(entity_map_used););
  LOGGING_ONLY(double eps_map_used = 0; calculateSpaceUsedByEpsMap(eps_map_used););
  LOGGING_ONLY(double buffer_used = 0; calculateSpaceUsedByBuffer(buffer_used););
  LOGGING_ONLY(std::cout << "[Hybrid::GetNum] entity_map_used: " << entity_map_used << std::endl;);
  LOGGING_ONLY(std::cout << "[Hybrid::GetNum] eps_map_used: " << eps_map_used << std::endl;);
  LOGGING_ONLY(std::cout << "[Hybrid::GetNum] buffer_map_used: " << buffer_used << std::endl;);
  // This is how the hybrid memory looks, it's organized from low eps to high eps.
  // regions (I) and (III) are on disk. We are writing search queries for these regions.
  //             |--- (II) ---|                (in memory)
  // |--- (I) ---|            |--- (III) ---|  (on disk)
  // Region (I) Query
  // NB: you need to cache the model ahead of time
  // and you probably want to retrieve the waste
  int region_one_count = 0, region_three_count =0;
  double region_one_waste = 0.0, region_three_waste = 0.0;
  // first search region (II)  
  Timer _lazy_waste(true);
  _tbuffer_it it = low_water_it;
  bool model_is_cached = false;
  LOGGING_ONLY(std::cout << "[Hybrid::GetNum]" << std::endl);
  
  // Becuase of duplicates in the buffer and on disk, we do the following:
  if(low_water_it == _buffer.begin() ) {      
    VERBOSE_ONLY(std::cout << "[Hybrid::GetNum] Searching Region (I)" << std::endl;);
    _full_entity_entry l; l.eps = m.low_water;
    it = upper_bound( low_water_it, _buffer.end(), l, Hybrid_Storage_Manager<T>::_full_entity_entry::_full_entity_compare);
    std::ostringstream ostr;
    ostr.precision(16);
    // now we search region (I)
    double top_of_region_one = (low_water_it == _buffer.end()) ? 0.0 : low_water_it->eps;
    if (top_of_region_one < 0.0) { top_of_region_one -= FLT_EPSILON;}  // THIS IS AWFUL. TODO: FIGURE OUT A BETTER WAY TO DO THIS.
    if(isEager()) {
      ostr << "EXECUTE search_disk_region_one_eager" << unique_id_for_ps << "(" << m.low_water << ", " << top_of_region_one << ");";
    } else {       
      std::string model_string, bias_string;
      ostr << "EXECUTE model_initialization" << unique_id_for_ps << ";";
      if(!m.test_and_set_model_in_db()) {       
        model_to_dbstring(m._model, model_string, bias_string);
        ostr << "EXECUTE model_caching" << unique_id_for_ps << "(" << model_string << ", " << bias_string << ");"; 
      }
      ostr << "EXECUTE search_disk_region_one_lazy" << unique_id_for_ps << "(" << m.low_water << ", " << top_of_region_one << ");";
      model_is_cached = true;
    }
    VERBOSE_ONLY(std::cout << "[Hybrid::GetNum] Region (I): " << ostr.str() << std::endl;);
    int retVal = _conn->execute_query_msg_int(ostr.str().c_str(), "[Hybrid::GetRegion]", region_one_count);
    checkQueryReturnValue(retVal, ostr.str());
    LOGGING_ONLY(std::cout << "[Hybrid::GetNum] region_one_count=" << region_one_count << std::endl);   
    if(isLazy()) {
      // Calculate the waste
      std::ostringstream waste_str;
      waste_str << "EXECUTE retrieve_ratio" << unique_id_for_ps << ";";
      int retVal = _conn->execute_query_msg_double(waste_str.str().c_str(), "[Hybrid::GetWaste]", region_one_waste);
      checkQueryReturnValue(retVal, waste_str.str());
    }
  } else {
    LOGGING_ONLY(std::cout << "[Hybrid::GetNum] Avoiding Region (I)" << std::endl;);
  }
  // ***************
  // We always need to search
  // Region III
  // *****
  _full_entity_entry h; h.eps = m.high_water;
  // Find the second highest max value in the buffer.
  // This is to avoid duplicates.
  int n = _buffer.size();
  int max_count_index = n-1;
  while(max_count_index >= 0 && _buffer[max_count_index].eps == _buffer[n-1].eps) { max_count_index--; }
  double bottom_of_region_three = (max_count_index >= 0) ? _buffer[max_count_index].eps : 0.0; 
  if (bottom_of_region_three > 0.0) { bottom_of_region_three += FLT_EPSILON; } 
  
  std::ostringstream ostr;
  ostr.precision(16); // TODO: Levent fix this to something reasonable
  double top_of_region_three = std::max(m.high_water, bottom_of_region_three);
  if(isEager()) {
    ostr << "EXECUTE search_disk_region_three_eager" << unique_id_for_ps << "(" << bottom_of_region_three << ", " << top_of_region_three << ");";      
  } else {
    if(!model_is_cached) {
      std::string model_string, bias_string;
      ostr << "EXECUTE model_initialization" << unique_id_for_ps << ";";
      if(!m.test_and_set_model_in_db()) { 
        model_to_dbstring(m._model, model_string, bias_string);
        ostr << "EXECUTE model_caching" << unique_id_for_ps << "(" << model_string << ", " << bias_string << ");"; 
      }
    }
    ostr << "EXECUTE search_disk_region_three_lazy" << unique_id_for_ps << "(" << bottom_of_region_three << "," << top_of_region_three << ");";      
  }
  VERBOSE_ONLY(std::cout << "Region III query: " << ostr.str() << std::endl;);
  int retVal = _conn->execute_query_msg_int(ostr.str().c_str(), "[Hybrid::GetRegion]", region_three_count);
  checkQueryReturnValue(retVal, ostr.str());
  LOGGING_ONLY(std::cout << "[Hybrid::GetNum] region_three_count=" << region_three_count << std::endl);   
  // Get the values.
  
  if(isLazy()) {
    // Calculate the waste
    std::ostringstream waste_str;
    waste_str << "EXECUTE retrieve_ratio" << unique_id_for_ps << ";";
    int retVal = _conn->execute_query_msg_double(waste_str.str().c_str(), "[Hybrid::GetWaste]", region_three_waste);
    checkQueryReturnValue(retVal, waste_str.str());
  }
  
  LOGGING_ONLY(std::cout << "[Hybrid::GetNum] Search Region (II)" << std::endl;);
  // Calculate the number in class and waste from the two regions.
  nClass = region_one_count + region_three_count;
  waste_time  = region_one_waste + region_three_waste;
  
  // Now search region (II)
  if(isEager()) {
    for(; it != _buffer.end() && it->eps <= bottom_of_region_three; it++) {
      nClass += it->label ? 1 : 0;
    }
    waste_time = 0.0;
  } else {
    int nTotalTuples = _buffer.size();
    int region_two_count = 0;
    for(; it != _buffer.end() && it->eps <= bottom_of_region_three; it++) {
      region_two_count += (IncrementalSGD<T>::classifyExample(m._model, it->x) > 0) ? 1 : 0; 
    }
    nClass += region_two_count;
    waste_time  += ((nTotalTuples == 0) ? 0 : _lazy_waste.stop() * (double) (nTotalTuples - region_two_count) / (double) nTotalTuples);
  }
  
}

template <class T>
void
Hybrid_Storage_Manager<T>::calculateSpaceUsedByEpsMap(double &spaceUsed) {
  spaceUsed = _epsmap.size() * (sizeof(key) + sizeof(double));
}

template <class T>
void
Hybrid_Storage_Manager<T>::calculateSpaceUsedByEntityMap(double &spaceUsed) {
  spaceUsed = _entity_map.size() * (sizeof(key) + sizeof(int));
}

template <class T>
void
Hybrid_Storage_Manager<T>::calculateSpaceUsedByBuffer(double &spaceUsed) {
  spaceUsed = 0;
  for(unsigned int i = 0; i < _buffer.size(); i ++) {
    double record_at_i_size = sizeof(key) + sizeof(double) + sizeof(bool);
    record_at_i_size += _buffer[i].x.getSpaceUsed();
    spaceUsed += record_at_i_size;
  }
}


template <class T>
void
Hybrid_Storage_Manager<T>::calculateSpaceUsed(double &spaceUsed) {
  spaceUsed = 0;
  double spaceUsedByStructure = 0;
  calculateSpaceUsedByEpsMap(spaceUsedByStructure);
  spaceUsed += spaceUsedByStructure;
  calculateSpaceUsedByEntityMap(spaceUsedByStructure);
  spaceUsed += spaceUsedByStructure;
  calculateSpaceUsedByBuffer(spaceUsedByStructure);
  spaceUsed += spaceUsedByStructure;
}

---