void
Pool::runAllActions(const boost::container::vector<Callback> &actions) {
	boost::container::vector<Callback>::const_iterator it, end = actions.end();
	for (it = actions.begin(); it != end; it++) {
		(*it)();
	}
}

cpu_times copy_destroy_time(boost::container::vector<typename C::value_type> &unique_range)
{
   cpu_timer copy_timer, assign_timer, destroy_timer;

   cpu_timer total_time;

   for(std::size_t i = 0; i != NIter; ++i){
      {
         C c(unique_range.begin(), unique_range.end());
         total_time.resume();
         copy_timer.resume();
         C caux(c);
         copy_timer.stop();
         assign_timer.resume();
         c = caux;
         assign_timer.stop();
         destroy_timer.resume();
      }
      destroy_timer.stop();
      total_time.stop();
   }
   total_time.stop();

   std::cout << " Copy sorted range             " << boost::timer::format(copy_timer.elapsed(), boost::timer::default_places, "%ws\n");
   std::cout << " Assign sorted range           " << boost::timer::format(assign_timer.elapsed(), boost::timer::default_places, "%ws\n");
   std::cout << " Destroy                       " << boost::timer::format(destroy_timer.elapsed(), boost::timer::default_places, "%ws\n");
   std::cout << " Total time =                  " << boost::timer::format(total_time.elapsed(), boost::timer::default_places, "%ws\n") << std::endl;
   return total_time.elapsed();
}

cpu_times insert_time( boost::container::vector<typename C::value_type> &unique_range
                     , boost::container::vector<typename C::value_type> &range
                     , const char *RangeType)
{
   cpu_timer ur_timer,r_timer;
   ur_timer.stop();r_timer.stop();

   cpu_timer total_time;
   total_time.resume();

   for(std::size_t i = 0; i != NIter; ++i){
      {
         total_time.resume();
         ur_timer.resume();
         C c;
         c.insert(unique_range.begin(), unique_range.end());
         ur_timer.stop();
         total_time.stop();
      }
      {
         total_time.resume();
         r_timer.resume();
         C c;
         c.insert(range.begin(), range.end());
         r_timer.stop();
         total_time.stop();
      }
   }

   std::cout << " Insert " << RangeType << " unique_range " << boost::timer::format(ur_timer.elapsed(), boost::timer::default_places, "%ws\n");
   std::cout << " Insert " << RangeType << " range        " << boost::timer::format(r_timer.elapsed(), boost::timer::default_places, "%ws\n");
   std::cout << " Total time =              " << boost::timer::format(total_time.elapsed(), boost::timer::default_places, "%ws\n") << std::endl;
   return total_time.elapsed();
}

bool
Group::pushGetWaiter(const Options &newOptions, const GetCallback &callback,
	boost::container::vector<Callback> &postLockActions)
{
	if (OXT_LIKELY(!testOverflowRequestQueue()
		&& (newOptions.maxRequestQueueSize == 0
		    || getWaitlist.size() < newOptions.maxRequestQueueSize)))
	{
		getWaitlist.push_back(GetWaiter(
			newOptions.copyAndPersist().detachFromUnionStationTransaction(),
			callback));
		return true;
	} else {
		postLockActions.push_back(boost::bind(GetCallback::call,
			callback, SessionPtr(), boost::make_shared<RequestQueueFullException>(newOptions.maxRequestQueueSize)));

		HookScriptOptions hsOptions;
		if (prepareHookScriptOptions(hsOptions, "queue_full_error")) {
			// TODO <Feb 17, 2015] DK> should probably rate limit this, since we are already at heavy load
			postLockActions.push_back(boost::bind(runHookScripts, hsOptions));
		}

		return false;
	}
}

/**
 * Process all waiters on the getWaitlist. Call when capacity has become free.
 * This function assigns sessions to them by calling get() on the corresponding
 * Groups, or by creating more Groups, in so far the new capacity allows.
 */
void
Pool::assignSessionsToGetWaiters(boost::container::vector<Callback> &postLockActions) {
	bool done = false;
	vector<GetWaiter>::iterator it, end = getWaitlist.end();
	vector<GetWaiter> newWaitlist;

	for (it = getWaitlist.begin(); it != end && !done; it++) {
		GetWaiter &waiter = *it;

		Group *group = findMatchingGroup(waiter.options);
		if (group != NULL) {
			SessionPtr session = group->get(waiter.options, waiter.callback,
				postLockActions);
			if (session != NULL) {
				postLockActions.push_back(boost::bind(GetCallback::call,
					waiter.callback, session, ExceptionPtr()));
			}
			/* else: the callback has now been put in
			 *       the group's get wait list.
			 */
		} else if (!atFullCapacityUnlocked()) {
			createGroupAndAsyncGetFromIt(waiter.options, waiter.callback,
				postLockActions);
		} else {
			/* Still cannot satisfy this get request. Keep it on the get
			 * wait list and try again later.
			 */
			newWaitlist.push_back(waiter);
		}
	}

	std::swap(getWaitlist, newWaitlist);
}

/** One of the post lock actions can potentially perform a long-running
 * operation, so running them in a thread is advised.
 */
void
Group::finishShutdown(boost::container::vector<Callback> &postLockActions) {
	TRACE_POINT();
	#ifndef NDEBUG
		LifeStatus lifeStatus = (LifeStatus) this->lifeStatus.load(boost::memory_order_relaxed);
		P_ASSERT_EQ(lifeStatus, SHUTTING_DOWN);
	#endif
	P_DEBUG("Finishing shutdown of group " << info.name);
	if (shutdownCallback) {
		postLockActions.push_back(shutdownCallback);
		shutdownCallback = Callback();
	}
	postLockActions.push_back(boost::bind(interruptAndJoinAllThreads,
		shared_from_this()));
	this->lifeStatus.store(SHUT_DOWN, boost::memory_order_seq_cst);
	selfPointer.reset();
}

bool check_all_not_empty(boost::container::vector< std::pair<Iterator, Iterator > > &iterator_pairs)
{
   for(std::size_t i = 0, max = iterator_pairs.size(); i != max; ++i){
      if(iterator_pairs[i].first == iterator_pairs[i].second)
         return false;
   }
   return true;
}

bool check_not_end(boost::container::vector<Iterator> &iterators, Iterator itend, std::size_t number_of_ends = 0)
{
   std::size_t end_count = 0;
   for(std::size_t i = 0, max = iterators.size(); i != max; ++i){
      if(iterators[i] == itend && (++end_count > number_of_ends) )
         return false;
   }
   return true;
}

void
Pool::assignExceptionToGetWaiters(Queue &getWaitlist,
	const ExceptionPtr &exception,
	boost::container::vector<Callback> &postLockActions)
{
	while (!getWaitlist.empty()) {
		postLockActions.push_back(boost::bind(GetCallback::call,
			getWaitlist.front().callback, SessionPtr(),
			exception));
		getWaitlist.pop_front();
	}
}

void extensions_time(boost::container::vector<typename C::value_type> &sorted_unique_range)
{
   cpu_timer sur_timer,sur_opt_timer;
   sur_timer.stop();sur_opt_timer.stop();

   for(std::size_t i = 0; i != NIter; ++i){
      {
         sur_timer.resume();
         C c(sorted_unique_range.begin(), sorted_unique_range.end());
         sur_timer.stop();
      }
      {
         sur_opt_timer.resume();
         C c(boost::container::ordered_unique_range, sorted_unique_range.begin(), sorted_unique_range.end());
         sur_opt_timer.stop();
      }

   }
   std::cout << " Construct sorted_unique_range             " << boost::timer::format(sur_timer.elapsed(), boost::timer::default_places, "%ws\n");
   std::cout << " Construct sorted_unique_range (extension) " << boost::timer::format(sur_opt_timer.elapsed(), boost::timer::default_places, "%ws\n");
   std::cout << "Extension/Standard: ";
   compare_times(sur_opt_timer.elapsed(), sur_timer.elapsed());
}

/**
 * Must be called before destroying a Group. You can optionally provide a
 * callback so that you are notified when shutdown has finished.
 *
 * The caller is responsible for migrating waiters on the getWaitlist.
 *
 * One of the post lock actions can potentially perform a long-running
 * operation, so running them in a thread is advised.
 */
void
Group::shutdown(const Callback &callback,
	boost::container::vector<Callback> &postLockActions)
{
	assert(isAlive());
	assert(getWaitlist.empty());

	P_DEBUG("Begin shutting down group " << info.name);
	shutdownCallback = callback;
	detachAll(postLockActions);
	startCheckingDetachedProcesses(true);
	interruptableThreads.interrupt_all();
	postLockActions.push_back(boost::bind(doCleanupSpawner, spawner));
	spawner.reset();
	selfPointer = shared_from_this();
	assert(disableWaitlist.empty());
	lifeStatus.store(SHUTTING_DOWN, boost::memory_order_seq_cst);
}

void
Group::assignSessionsToGetWaiters(boost::container::vector<Callback> &postLockActions) {
	unsigned int i = 0;
	bool done = false;

	while (!done && i < getWaitlist.size()) {
		const GetWaiter &waiter = getWaitlist[i];
		RouteResult result = route(waiter.options);
		if (result.process != NULL) {
			postLockActions.push_back(boost::bind(
				GetCallback::call,
				waiter.callback,
				newSession(result.process),
				ExceptionPtr()));
			getWaitlist.erase(getWaitlist.begin() + i);
		} else {
			done = result.finished;
			if (!result.finished) {
				i++;
			}
		}
	}
}

std::size_t generate_elements(boost::container::vector<T> &elements, std::size_t L, std::size_t NK, Compare comp)
{
   elements.resize(L);
   boost::movelib::unique_ptr<std::size_t[]> key_reps(new std::size_t[NK ? NK : L]);

   std::srand(0);
   for (std::size_t i = 0; i < (NK ? NK : L); ++i) {
      key_reps[i] = 0;
   }
   for (std::size_t i = 0; i < L; ++i) {
      std::size_t  key = NK ? (i % NK) : i;
      elements[i].key = key;
   }
   ::random_shuffle(elements.data(), elements.data() + L);
   ::random_shuffle(elements.data(), elements.data() + L);

   for (std::size_t i = 0; i < L; ++i) {
      elements[i].val = key_reps[elements[i].key]++;
   }
   std::size_t split_count = L / 2;
   std::stable_sort(elements.data(), elements.data() + split_count, comp);
   std::stable_sort(elements.data() + split_count, elements.data() + L, comp);
   return split_count;
}

cpu_times search_time(boost::container::vector<typename C::value_type> &unique_range, const char *RangeType)
{
   cpu_timer find_timer, lower_timer, upper_timer, equal_range_timer, count_timer;

   C c(unique_range.begin(), unique_range.end());

   cpu_timer total_time;
   total_time.resume();

   boost::container::vector<typename C::iterator> v_it(NElements);
   boost::container::vector< std::pair<typename C::iterator, typename C::iterator> > v_itp(NElements);

   for(std::size_t i = 0; i != NIter; ++i){
      //Find
      {
         find_timer.resume();
         for(std::size_t rep = 0; rep != 2; ++rep)
         for(std::size_t i = 0, max = unique_range.size(); i != max; ++i){
            v_it[i] = c.find(unique_range[i]);
         }
         find_timer.stop();
         if(!check_not_end(v_it, c.end())){
            std::cout << "ERROR! find all elements not found" << std::endl;
         }
      }
      //Lower
      {
         lower_timer.resume();
         for(std::size_t rep = 0; rep != 2; ++rep)
         for(std::size_t i = 0, max = unique_range.size(); i != max; ++i){
            v_it[i] = c.lower_bound(unique_range[i]);
         }
         lower_timer.stop();
         if(!check_not_end(v_it, c.end())){
            std::cout << "ERROR! lower_bound all elements not found" << std::endl;
         }
      }
      //Upper
      {
         upper_timer.resume();
         for(std::size_t rep = 0; rep != 2; ++rep)
         for(std::size_t i = 0, max = unique_range.size(); i != max; ++i){
            v_it[i] = c.upper_bound(unique_range[i]);
         }
         upper_timer.stop();
         if(!check_not_end(v_it, c.end(), 1u)){
            std::cout << "ERROR! upper_bound all elements not found" << std::endl;
         }
      }
      //Equal
      {
         equal_range_timer.resume();
         for(std::size_t rep = 0; rep != 2; ++rep)
         for(std::size_t i = 0, max = unique_range.size(); i != max; ++i){
            v_itp[i] = c.equal_range(unique_range[i]);
         }
         equal_range_timer.stop();
         if(!check_all_not_empty(v_itp)){
            std::cout << "ERROR! equal_range all elements not found" << std::endl;
         }
      }
      //Count
      {
         std::size_t count = 0;
         count_timer.resume();
         for(std::size_t rep = 0; rep != 2; ++rep)
         for(std::size_t i = 0, max = unique_range.size(); i != max; ++i){
            count += c.count(unique_range[i]);
         }
         count_timer.stop();
         if(count/2 != c.size()){
            std::cout << "ERROR! count all elements not found" << std::endl;
         }
      }
   }
   total_time.stop();

   std::cout << " Find        " << RangeType << " " << boost::timer::format(find_timer.elapsed(), boost::timer::default_places, "%ws\n");
   std::cout << " Lower Bound " << RangeType << " " << boost::timer::format(lower_timer.elapsed(), boost::timer::default_places, "%ws\n");
   std::cout << " Upper Bound " << RangeType << " " << boost::timer::format(upper_timer.elapsed(), boost::timer::default_places, "%ws\n");
   std::cout << " Equal Range " << RangeType << " " << boost::timer::format(equal_range_timer.elapsed(), boost::timer::default_places, "%ws\n");
   std::cout << " Count       " << RangeType << " " << boost::timer::format(count_timer.elapsed(), boost::timer::default_places, "%ws\n");
   std::cout << " Total time =      " << boost::timer::format(total_time.elapsed(), boost::timer::default_places, "%ws\n") << std::endl;
   return total_time.elapsed();
}

void
Group::cleanupSpawner(boost::container::vector<Callback> &postLockActions) {
	assert(isAlive());
	postLockActions.push_back(boost::bind(doCleanupSpawner, spawner));
}

// The 'self' parameter is for keeping the current Group object alive while this thread is running.
void
Group::finalizeRestart(GroupPtr self,
	Options oldOptions,
	Options newOptions, RestartMethod method,
	SpawningKit::FactoryPtr spawningKitFactory,
	unsigned int restartsInitiated,
	boost::container::vector<Callback> postLockActions)
{
	TRACE_POINT();

	Pool::runAllActions(postLockActions);
	postLockActions.clear();

	this_thread::disable_interruption di;
	this_thread::disable_syscall_interruption dsi;

	// Create a new spawner.
	Options spawnerOptions = oldOptions;
	resetOptions(newOptions, &spawnerOptions);
	SpawningKit::SpawnerPtr newSpawner = spawningKitFactory->create(spawnerOptions);
	SpawningKit::SpawnerPtr oldSpawner;

	UPDATE_TRACE_POINT();
	Pool *pool = getPool();

	Pool::DebugSupportPtr debug = pool->debugSupport;
	if (debug != NULL && debug->restarting) {
		this_thread::restore_interruption ri(di);
		this_thread::restore_syscall_interruption rsi(dsi);
		this_thread::interruption_point();
		debug->debugger->send("About to end restarting");
		debug->messages->recv("Finish restarting");
	}

	ScopedLock l(pool->syncher);
	if (!isAlive()) {
		P_DEBUG("Group " << getName() << " is shutting down, so aborting restart");
		return;
	}
	if (restartsInitiated != this->restartsInitiated) {
		// Before this restart could be finalized, another restart command was given.
		// The spawner we just created might be out of date now so we abort.
		P_DEBUG("Restart of group " << getName() << " aborted because a new restart was initiated concurrently");
		if (debug != NULL && debug->restarting) {
			debug->debugger->send("Restarting aborted");
		}
		return;
	}

	// Run some sanity checks.
	pool->fullVerifyInvariants();
	assert(m_restarting);
	UPDATE_TRACE_POINT();

	// Atomically swap the new spawner with the old one.
	resetOptions(newOptions);
	oldSpawner = spawner;
	spawner    = newSpawner;

	m_restarting = false;
	if (shouldSpawn()) {
		spawn();
	} else if (isWaitingForCapacity()) {
		P_INFO("Group " << getName() << " is waiting for capacity to become available. "
			"Trying to shutdown another idle process to free capacity...");
		if (pool->forceFreeCapacity(this, postLockActions) != NULL) {
			spawn();
		} else {
			P_INFO("There are no processes right now that are eligible "
				"for shutdown. Will try again later.");
		}
	}
	verifyInvariants();

	l.unlock();
	oldSpawner.reset();
	Pool::runAllActions(postLockActions);
	P_DEBUG("Restart of group " << getName() << " done");
	if (debug != NULL && debug->restarting) {
		debug->debugger->send("Restarting done");
	}
}

static void reset_alloc_stats(bc::vector<T, Allocator> &v)
   { v.reset_alloc_stats(); }

void fill_range_strings()
{
   boost::container::string model_s;
   model_s.append(sizeof(boost::container::string), '*');

   //sorted_unique_range_int
   sorted_unique_range_string.resize(NElements);
   std::stringstream sstr;

   for(std::size_t i = 0, max = sorted_unique_range_string.size(); i != max; ++i){
      sstr.str(std::string());
      sstr << std::setfill('0') << std::setw(10) << i;
      sorted_unique_range_string[i] = model_s;
      const std::string &s = sstr.str();
      sorted_unique_range_string[i].append(s.begin(), s.end());
   }
   //sorted_range_string
   sorted_range_string = sorted_unique_range_string;
   sorted_range_string.insert(sorted_range_string.end(), sorted_unique_range_string.begin(), sorted_unique_range_string.end());
   std::sort(sorted_range_string.begin(), sorted_range_string.end());

   //random_range_string
   std::srand(0);
   random_range_string.assign(sorted_range_string.begin(), sorted_range_string.end());
   std::random_shuffle(random_range_string.begin(), random_range_string.end());
   //random_unique_range_string
   std::srand(0);
   random_unique_range_string.assign(sorted_unique_range_string.begin(), sorted_unique_range_string.end());
   std::random_shuffle(random_unique_range_string.begin(), random_unique_range_string.end());
}

void fill_range_ints()
{
   //sorted_unique_range_int
   sorted_unique_range_int.resize(NElements);
   for(std::size_t i = 0, max = sorted_unique_range_int.size(); i != max; ++i){
      sorted_unique_range_int[i] = static_cast<int>(i);
   }
   //sorted_range_int
   sorted_range_int = sorted_unique_range_int;
   sorted_range_int.insert(sorted_range_int.end(), sorted_unique_range_int.begin(), sorted_unique_range_int.end());
   std::sort(sorted_range_int.begin(), sorted_range_int.end());

   //random_range_int
   std::srand(0);
   random_range_int.assign(sorted_range_int.begin(), sorted_range_int.end());
   std::random_shuffle(random_range_int.begin(), random_range_int.end());
   //random_unique_range_int
   std::srand(0);
   random_unique_range_int.assign(sorted_unique_range_int.begin(), sorted_unique_range_int.end());
   std::random_shuffle(random_unique_range_int.begin(), random_unique_range_int.end());
}

 ~Data()
 {
     assert(iterators.empty());
 }