Changeset 127a8e

Timestamp:

Jul 8, 2010, 4:04:11 PM (14 years ago)

Author:

Tillmann Crueger <crueger@…>

Branches:

Action_Thermostats, Add_AtomRandomPerturbation, Add_FitFragmentPartialChargesAction, Add_RotateAroundBondAction, Add_SelectAtomByNameAction, Added_ParseSaveFragmentResults, AddingActions_SaveParseParticleParameters, Adding_Graph_to_ChangeBondActions, Adding_MD_integration_tests, Adding_ParticleName_to_Atom, Adding_StructOpt_integration_tests, AtomFragments, Automaking_mpqc_open, AutomationFragmentation_failures, Candidate_v1.5.4, Candidate_v1.6.0, Candidate_v1.6.1, ChangeBugEmailaddress, ChangingTestPorts, ChemicalSpaceEvaluator, CombiningParticlePotentialParsing, Combining_Subpackages, Debian_Package_split, Debian_package_split_molecuildergui_only, Disabling_MemDebug, Docu_Python_wait, EmpiricalPotential_contain_HomologyGraph, EmpiricalPotential_contain_HomologyGraph_documentation, Enable_parallel_make_install, Enhance_userguide, Enhanced_StructuralOptimization, Enhanced_StructuralOptimization_continued, Example_ManyWaysToTranslateAtom, Exclude_Hydrogens_annealWithBondGraph, FitPartialCharges_GlobalError, Fix_BoundInBox_CenterInBox_MoleculeActions, Fix_ChargeSampling_PBC, Fix_ChronosMutex, Fix_FitPartialCharges, Fix_FitPotential_needs_atomicnumbers, Fix_ForceAnnealing, Fix_IndependentFragmentGrids, Fix_ParseParticles, Fix_ParseParticles_split_forward_backward_Actions, Fix_PopActions, Fix_QtFragmentList_sorted_selection, Fix_Restrictedkeyset_FragmentMolecule, Fix_StatusMsg, Fix_StepWorldTime_single_argument, Fix_Verbose_Codepatterns, Fix_fitting_potentials, Fixes, ForceAnnealing_goodresults, ForceAnnealing_oldresults, ForceAnnealing_tocheck, ForceAnnealing_with_BondGraph, ForceAnnealing_with_BondGraph_continued, ForceAnnealing_with_BondGraph_continued_betteresults, ForceAnnealing_with_BondGraph_contraction-expansion, FragmentAction_writes_AtomFragments, FragmentMolecule_checks_bonddegrees, GeometryObjects, Gui_Fixes, Gui_displays_atomic_force_velocity, ImplicitCharges, IndependentFragmentGrids, IndependentFragmentGrids_IndividualZeroInstances, IndependentFragmentGrids_IntegrationTest, IndependentFragmentGrids_Sole_NN_Calculation, JobMarket_RobustOnKillsSegFaults, JobMarket_StableWorkerPool, JobMarket_unresolvable_hostname_fix, MoreRobust_FragmentAutomation, ODR_violation_mpqc_open, PartialCharges_OrthogonalSummation, PdbParser_setsAtomName, PythonUI_with_named_parameters, QtGui_reactivate_TimeChanged_changes, Recreated_GuiChecks, Rewrite_FitPartialCharges, RotateToPrincipalAxisSystem_UndoRedo, SaturateAtoms_findBestMatching, SaturateAtoms_singleDegree, StoppableMakroAction, Subpackage_CodePatterns, Subpackage_JobMarket, Subpackage_LinearAlgebra, Subpackage_levmar, Subpackage_mpqc_open, Subpackage_vmg, Switchable_LogView, ThirdParty_MPQC_rebuilt_buildsystem, TrajectoryDependenant_MaxOrder, TremoloParser_IncreasedPrecision, TremoloParser_MultipleTimesteps, TremoloParser_setsAtomName, Ubuntu_1604_changes, stable

Children:

4d7462

Parents:

40f928

Message:

Improved managing of Ids in the World

• Improved algorithm for managing ids to use less time and space
• Made the moleculeIds managed

Location:

src

Files:

• World.cpp (modified) (6 diffs)
• World.hpp (modified) (2 diffs)
• defs.hpp (modified) (1 diff)

src/World.cpp

@@ -25 +25 @@
 #include "Box.hpp"
 #include "Matrix.hpp"
+#include "defs.hpp"
 
 #include "Patterns/Singleton_impl.hpp"
@@ -121 +122 @@
   molecule *mol = NULL;
   mol = NewMolecule();
-  ASSERT(!molecules.count(currMoleculeId),"currMoleculeId did not specify an unused ID");
-  mol->setId(currMoleculeId++);
+  moleculeId_t id = getNextMoleculeId();
+  ASSERT(!molecules.count(id),"proposed id did not specify an unused ID");
+  mol->setId(id);
   // store the molecule by ID
   molecules[mol->getId()] = mol;
@@ -140 +142 @@
   DeleteMolecule(mol);
   molecules.erase(id);
+  releaseMoleculeId(id);
 }
 
@@ -145 +148 @@
   OBSERVE;
   atomId_t id = getNextAtomId();
+  ASSERT(!atoms.count(id),"proposed id did not specify an unused ID");
   atom *res = NewAtom(id);
   res->setWorld(this);
@@ -221 +225 @@
 
 atomId_t World::getNextAtomId(){
-  // see if we can reuse some Id
-  if(atomIdPool.empty()){
-    return currAtomId++;
-  }
-  else{
-    // we give out the first ID from the pool
-    atomId_t id = *(atomIdPool.begin());
-    atomIdPool.erase(id);
+  // try to find an Id in the pool;
+  if(!atomIdPool.empty()){
+    atomIdPool_t::iterator iter=atomIdPool.begin();
+    atomId_t id = iter->first;
+    pair<atomId_t,atomId_t> newRange = make_pair(id+1,iter->second);
+    // we wont use this iterator anymore, so we don't care about invalidating
+    atomIdPool.erase(iter);
+    if(newRange.first<newRange.second){
+      atomIdPool.insert(newRange);
+    }
     return id;
   }
+  // Nothing in the pool... we are out of luck
+  return currAtomId++;
 }
 
 void World::releaseAtomId(atomId_t id){
-  atomIdPool.insert(id);
-  // defragmentation of the pool
-  set<atomId_t>::reverse_iterator iter;
-  // go through all Ids in the pool that lie immediately below the border
-  while(!atomIdPool.empty() && *(atomIdPool.rbegin())==(currAtomId-1)){
-    atomIdPool.erase(--currAtomId);
-  }
+  atomIdPool.insert(make_pair(id,id+1));
+  defragAtomIdPool();
 }
 
 bool World::reserveAtomId(atomId_t id){
   if(id>=currAtomId ){
-    // add all ids between the new one and current border as available
-    for(atomId_t pos=currAtomId; pos<id; ++pos){
-      atomIdPool.insert(pos);
+    pair<atomId_t,atomId_t> newRange = make_pair(currAtomId,id);
+    if(newRange.first<newRange.second){
+      atomIdPool.insert(newRange);
     }
     currAtomId=id+1;
+    defragAtomIdPool();
     return true;
   }
-  else if(atomIdPool.count(id)){
-    atomIdPool.erase(id);
+  // look for a range that matches the request
+  for(atomIdPool_t::iterator iter=atomIdPool.begin();iter!=atomIdPool.end();++iter){
+    if(iter->first>id){
+      // we have coverd all available ranges... nothing to be found here
+      break;
+    }
+    // no need to check first, since it has to be <=id, since otherwise we would have broken out
+    if(iter->second > id){
+      // we found a matching range... get the id from this range
+
+      // split up this range at the point of id
+      pair<atomId_t,atomId_t> bottomRange = make_pair(iter->first,id);
+      pair<atomId_t,atomId_t> topRange = make_pair(id+1,iter->second);
+      // remove this range
+      atomIdPool.erase(iter);
+      if(bottomRange.first<bottomRange.second){
+        atomIdPool.insert(bottomRange);
+      }
+      if(topRange.first<topRange.second){
+        atomIdPool.insert(topRange);
+      }
+      defragAtomIdPool();
+      return true;
+    }
+  }
+  // this ID could not be reserved
+  return false;
+}
+
+void World::defragAtomIdPool(){
+  // check if the situation is bad enough to make defragging neccessary
+  if((numAtomDefragSkips<MAX_FRAGMENTATION_SKIPS) &&
+     (atomIdPool.size()<lastAtomPoolSize+MAX_POOL_FRAGMENTATION)){
+    ++numAtomDefragSkips;
+    return;
+  }
+  for(atomIdPool_t::iterator iter = atomIdPool.begin();iter!=atomIdPool.end();){
+    // see if this range is adjacent to the next one
+    atomIdPool_t::iterator next = iter;
+    next++;
+    if(next!=atomIdPool.end() && (next->first==iter->second)){
+      // merge the two ranges
+      pair<atomId_t,atomId_t> newRange = make_pair(iter->first,next->second);
+      atomIdPool.erase(iter);
+      atomIdPool.erase(next);
+      pair<atomIdPool_t::iterator,bool> res = atomIdPool.insert(newRange);
+      ASSERT(res.second,"Id-Pool was confused");
+      iter=res.first;
+      continue;
+    }
+    ++iter;
+  }
+  if(!atomIdPool.empty()){
+    // check if the last range is at the border
+    atomIdPool_t::iterator iter = atomIdPool.end();
+    iter--;
+    if(iter->second==currAtomId){
+      currAtomId=iter->first;
+      atomIdPool.erase(iter);
+    }
+  }
+  lastAtomPoolSize=atomIdPool.size();
+  numAtomDefragSkips=0;
+}
+
+// Molecules
+
+moleculeId_t World::getNextMoleculeId(){
+  // try to find an Id in the pool;
+  if(!moleculeIdPool.empty()){
+    moleculeIdPool_t::iterator iter=moleculeIdPool.begin();
+    moleculeId_t id = iter->first;
+    pair<moleculeId_t,moleculeId_t> newRange = make_pair(id+1,iter->second);
+    // we wont use this iterator anymore, so we don't care about invalidating
+    moleculeIdPool.erase(iter);
+    if(newRange.first<newRange.second){
+      moleculeIdPool.insert(newRange);
+    }
+    return id;
+  }
+  // Nothing in the pool... we are out of luck
+  return currMoleculeId++;
+}
+
+void World::releaseMoleculeId(moleculeId_t id){
+  moleculeIdPool.insert(make_pair(id,id+1));
+  defragMoleculeIdPool();
+}
+
+bool World::reserveMoleculeId(moleculeId_t id){
+  if(id>=currMoleculeId ){
+    pair<moleculeId_t,moleculeId_t> newRange = make_pair(currMoleculeId,id);
+    if(newRange.first<newRange.second){
+      moleculeIdPool.insert(newRange);
+    }
+    currMoleculeId=id+1;
+    defragMoleculeIdPool();
     return true;
   }
-  else{
-    // this ID could not be reserved
-    return false;
-  }
-}
-
-// Molecules
+  // look for a range that matches the request
+  for(moleculeIdPool_t::iterator iter=moleculeIdPool.begin();iter!=moleculeIdPool.end();++iter){
+    if(iter->first>id){
+      // we have coverd all available ranges... nothing to be found here
+      break;
+    }
+    // no need to check first, since it has to be <=id, since otherwise we would have broken out
+    if(iter->second > id){
+      // we found a matching range... get the id from this range
+
+      // split up this range at the point of id
+      pair<moleculeId_t,moleculeId_t> bottomRange = make_pair(iter->first,id);
+      pair<moleculeId_t,moleculeId_t> topRange = make_pair(id+1,iter->second);
+      // remove this range
+      moleculeIdPool.erase(iter);
+      if(bottomRange.first<bottomRange.second){
+        moleculeIdPool.insert(bottomRange);
+      }
+      if(topRange.first<topRange.second){
+        moleculeIdPool.insert(topRange);
+      }
+      defragMoleculeIdPool();
+      return true;
+    }
+  }
+  // this ID could not be reserved
+  return false;
+}
+
+void World::defragMoleculeIdPool(){
+  // check if the situation is bad enough to make defragging neccessary
+  if((numMoleculeDefragSkips<MAX_FRAGMENTATION_SKIPS) &&
+     (moleculeIdPool.size()<lastMoleculePoolSize+MAX_POOL_FRAGMENTATION)){
+    ++numMoleculeDefragSkips;
+    return;
+  }
+  for(moleculeIdPool_t::iterator iter = moleculeIdPool.begin();iter!=moleculeIdPool.end();){
+    // see if this range is adjacent to the next one
+    moleculeIdPool_t::iterator next = iter;
+    next++;
+    if(next!=moleculeIdPool.end() && (next->first==iter->second)){
+      // merge the two ranges
+      pair<moleculeId_t,moleculeId_t> newRange = make_pair(iter->first,next->second);
+      moleculeIdPool.erase(iter);
+      moleculeIdPool.erase(next);
+      pair<moleculeIdPool_t::iterator,bool> res = moleculeIdPool.insert(newRange);
+      ASSERT(res.second,"Id-Pool was confused");
+      iter=res.first;
+      continue;
+    }
+    ++iter;
+  }
+  if(!moleculeIdPool.empty()){
+    // check if the last range is at the border
+    moleculeIdPool_t::iterator iter = moleculeIdPool.end();
+    iter--;
+    if(iter->second==currMoleculeId){
+      currMoleculeId=iter->first;
+      moleculeIdPool.erase(iter);
+    }
+  }
+  lastMoleculePoolSize=moleculeIdPool.size();
+  numMoleculeDefragSkips=0;
+}
 
 /******************************* Iterators ********************************/
@@ -322 +478 @@
     atoms(this),
     currAtomId(0),
+    lastAtomPoolSize(0),
+    numAtomDefragSkips(0),
     molecules(),
     currMoleculeId(0),

src/World.hpp

@@ -288 +288 @@
   void releaseAtomId(atomId_t);
   bool reserveAtomId(atomId_t);
+  void defragAtomIdPool();
+
+  moleculeId_t getNextMoleculeId();
+  void releaseMoleculeId(moleculeId_t);
+  bool reserveMoleculeId(moleculeId_t);
+  void defragMoleculeIdPool();
 
   periodentafel *periode;
@@ -298 +304 @@
   AtomSet atoms;
 private:
-  std::set<atomId_t> atomIdPool; //<!stores the pool for all available AtomIds below currAtomId
+  typedef std::set<std::pair<atomId_t, atomId_t> > atomIdPool_t;
+
+  /**
+   * stores the pool for all available AtomIds below currAtomId
+   *
+   * The pool contains ranges of free ids in the form [bottom,top).
+   */
+  atomIdPool_t atomIdPool;
   atomId_t currAtomId; //!< stores the next available Id for atoms
+  size_t lastAtomPoolSize; //!< size of the pool after last defrag, to skip some defrags
+  unsigned int numAtomDefragSkips;
+
   MoleculeSet molecules;
+  typedef std::set<std::pair<moleculeId_t, moleculeId_t> > moleculeIdPool_t;
+  moleculeIdPool_t moleculeIdPool;
   moleculeId_t currMoleculeId;
+  size_t lastMoleculePoolSize; //!< size of the pool after last defrag, to skip some defrags
+  unsigned int numMoleculeDefragSkips;
 private:
   /**

src/defs.hpp

@@ -84 +84 @@
 #define MOLECUILDER_NAME "Molecuilder"
 
+const unsigned int MAX_POOL_FRAGMENTATION=20;
+const unsigned int MAX_FRAGMENTATION_SKIPS=100;
+
 #endif /*DEFS_HPP_*/