ops limiter

limiter.h

//
// working concept of ops limiter
//
// http://blog.malcom.pl/2013/04/20/limitowanie-ops/
//
// MIT license
//

#ifndef LOPS_LIMITER_H
#define LOPS_LIMITER_H

#include <algorithm>
#include <cstdint>

#ifdef WIN32

	#ifndef WIN32_LEAN_AND_MEAN
		#define WIN32_LEAN_AND_MEAN
	#endif

	#include <windows.h>

	// undef some macros to avoid conflict with stl algorithm
	#ifdef min
		#undef min
	#endif

#else
	#include <time.h>		// nanosleep
	#include <sys/time.h>	// gettimeofday
#endif

namespace lops {

//
// Token traits specify interpretation of the result of the operation executed
// by user's function in order to detect processing termination (is_eof) and
// error occurrence (is_error).
// is_error may be ignored (always returns false) if the user's function throw
// exceptions to inform about error occurrence
//
template<typename T>
struct TokenTraits {

	static inline bool is_eof(T token) {
		return token == 0;
	}

	static inline bool is_error(T token) {
		return token < 0;
	}

};


//
// Time policy provides implementation of the mechanisms connected with time,
// function which stops executing current thread/context for defined time (sleep)
// and function returning current time marker (time).
// time maker doesn't have to concern real time; it should be possible to
// calculate passage of time using the formula dt=t1-t0
//
template<typename T>
struct NativeTimePolicy {

	static void sleep(T usec) {
	#ifdef WIN32
		Sleep(static_cast<DWORD>(usec / 1000));
	#else
		struct timespec req;
		req.tv_sec = 0;
		req.tv_nsec = usec * 1000;
		nanosleep(&req, NULL);
	#endif
	}

	static T time() {
	#ifdef WIN32
		FILETIME ft;
		GetSystemTimeAsFileTime(&ft);

		ULARGE_INTEGER t;
		t.HighPart = ft.dwHighDateTime;
		t.LowPart = ft.dwLowDateTime;

		return t.QuadPart / 10;
	#else
		struct timeval tv;
		gettimeofday(&tv, NULL);

		return (tv.tv_sec * 1000000) + tv.tv_usec;
	#endif
	}

};


//
// Specifying the method of request processing
// - one call user's function with given value of tokens which may be executed
//   in current window
// - sequentially calls user's function in order to process all operations
//   represented by the value of tokens given by user
//
enum ProcessType {
	ProcessOne,
	ProcessAll
};


// maybe int_ form #include <boost/mpl/int.hpp> ?
template<int N>
struct Int2Type {
	enum { value = N };
};


//
// Main class for limiting operations.
// It delivers get/set-teru to rate value, specifying limitations of the operation
// falling on one second and execution operator which replaces limited function execution.
// This operator takes the object meeting callable concept (function, functor, lambda)
// with defined prototype:
//
//   Token func(Token token);
//
// This function takes the value of tokens which it may use, it returns the
// value of used tokens.
//
template<
	typename Token,									// token type
	typename Time,									// time type
	ProcessType Process = ProcessAll,				// process algorithm
	typename TokenTraits = TokenTraits<Token>,		// token traits - is_eof/is_error
	typename TimePolicy = NativeTimePolicy<Time>	// time policy - time/sleep
>
class Limiter {
public:

	Limiter(uint32_t rate = 0)
		: m_start( TimePolicy::time() ),
		  m_used(0)
	{
		setRate(rate);
	}

	uint32_t getRate() const {
		return m_rate;
	}

	void setRate(uint32_t rate, uint16_t wins = 10) {
		m_rate = rate;
		m_interval = 1000000 / wins;
		m_value = m_rate / wins;
	}

	template<typename T>
	Token operator()(T func, Token token) {

		if (m_rate == 0)
			return func(token);

		return process(func, token, Int2Type<Process>());
	}

protected:

	template<typename T>
	Token process(T func, Token token, Int2Type<ProcessOne>) {
		return do_process(func, token);
	}

	template<typename T>
	Token process(T func, Token token, Int2Type<ProcessAll>) {

		Token rest = token;

		while (rest != 0) {

			Token ret = do_process(func, rest);
			if ( TokenTraits::is_eof(ret) )
				break;
			if ( TokenTraits::is_error(ret) )
				return ret;

			rest -= ret;
		}

		return token - rest;
	}


	template<typename T>
	Token do_process(T func, Token token) {

		// process window stuff
		Time now = TimePolicy::time();
		Time inv = now - m_start;

		if (inv >= m_interval) {
			// in new window
			m_start = now - (inv % m_interval);
			m_used = 0;

		} else if (m_used >= m_value) {
			// sleep rest of window time
			TimePolicy::sleep(m_interval - inv);
			m_start = TimePolicy::time();
			m_used = 0;
		}

		// calculate token chunk for current window
		Token chunk = m_value - m_used;
		chunk = std::min(chunk, token);

		// call user function
		Token ret = func(chunk);
		if ( !TokenTraits::is_error(ret) )
			m_used += ret;

		return ret;
	}


	// rate in ops
	uint32_t m_rate;

	// window interval time and token value
	Time m_interval;
	Token m_value;

	// current windows
	Time m_start;
	Token m_used;

};

} // namespace lops

#endif // LOPS_LIMITER_H