source: src/IdPool_impl.hpp@ 53d894

/*
 * IdPool_impl.hpp
 *
 *  Created on: Dec 23, 2011
 *      Author: heber
 */

#ifndef IDPOOL_IMPL_HPP_
#define IDPOOL_IMPL_HPP_

// include config.h
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include "IdPool.hpp"

#include "CodePatterns/Log.hpp"

template <class T>
IdPool<T>::IdPool(const T _currId, const unsigned int _max_skips, const unsigned int _max_size) :
  currId(_currId),
  MAX_FRAGMENTATION_SKIPS(_max_skips),
  MAX_POOL_FRAGMENTATION(_max_size)
{}

template <class T>
IdPool<T>::~IdPool()
{}

template <class T>
T IdPool<T>::getNextId()
{
  setLastAction(reserve);
  // try to find an Id in the pool;
  if(!pool.empty()) {
    typename IdPool_t::iterator iter=pool.begin();
    T id = iter->first;
    range<T> newRange = makeRange(id+1,iter->last);
    // we wont use this iterator anymore, so we don't care about invalidating
    pool.erase(iter);
    if(newRange.first<newRange.last)
      pool.insert(newRange);
    return id;
  }
  // Nothing in the pool... we are out of luck
  return currId++;
}

template <class T>
void IdPool<T>::releaseId(T id)
{
  setLastAction(release);
  pool.insert(makeRange(id,id+1));
  defragIdPool();
}

template <class T>
bool IdPool<T>::reserveId(T id)
{
  setLastAction(reserve);
  if(id>=currId ) {
    range<T> newRange = makeRange(currId,id);
    if(newRange.first<newRange.last)
      pool.insert(newRange);
    currId=id+1;
    defragIdPool();
    return true;
  }
  // look for a range that matches the request
  for(typename IdPool_t::iterator iter=pool.begin();iter!=pool.end();++iter){
    if(iter->isBefore(id)){
      // we have covered 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->isBeyond(id)){
      // we found a matching range... get the id from this range

      // split up this range at the point of id
      range<T> bottomRange = makeRange(iter->first,id);
      range<T> topRange = makeRange(id+1,iter->last);
      // remove this range
      pool.erase(iter);
      if(bottomRange.first<bottomRange.last){
        pool.insert(bottomRange);
      }
      if(topRange.first<topRange.last){
        pool.insert(topRange);
      }
      defragIdPool();
      return true;
    }
  }
  // this ID could not be reserved
  return false;
}

template <class T>
void IdPool<T>::defragIdPool()
{
  // check if the situation is bad enough to make defragging neccessary
  if((numDefragSkips<MAX_FRAGMENTATION_SKIPS) &&
     (pool.size()<lastPoolSize+MAX_POOL_FRAGMENTATION)) {
    return;
  }
  LOG(1, "STATUS: Defragmenting id pool.");
  for(typename IdPool_t::iterator iter = pool.begin();iter!=pool.end();) {
    // see if this range is adjacent to the next one
    typename IdPool_t::iterator next = iter;
    next++;
    if(next!=pool.end() && (next->first==iter->last)) {
      // merge the two ranges
      range<T> newRange = makeRange(iter->first,next->last);
      pool.erase(iter);
      pool.erase(next);
      pair<typename IdPool_t::iterator,bool> res = pool.insert(newRange);
      ASSERT(res.second,"Id-Pool was confused");
      iter=res.first;
      continue;
    }
    ++iter;
  }
  if(!pool.empty()) {
    // check if the last range is at the border
    typename IdPool_t::iterator iter = pool.end();
    iter--;
    if(iter->last==currId){
      currId=iter->first;
      pool.erase(iter);
    }
  }
  lastPoolSize=pool.size();
  numDefragSkips=0;
}

/**
 * This define allows simple instantiation of the necessary singleton functions
 * at a chosen place.
 */
#define CONSTRUCT_IDPOOL(name) \
    template name IdPool< name >::getNextId(); \
    template bool IdPool< name >::reserveId( name ); \
    template void IdPool< name >::releaseId( name ); \
    template void IdPool< name >::setLastAction(const enum Actions _action); \
    template void IdPool< name >::defragIdPool() ;

#endif /* IDPOOL_IMPL_HPP_ */