/* -*- Mode:C++; c-basic-offset:8; tab-width:8; -*- */
/*
 * Copyright (c) 1997 David Wetherall
 * Copyright (c) 2005 David Wei
 * Copyright (c) 2009 INRIA
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation;
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#include "ns2-calendar-scheduler.h"
#include "event-impl.h"
#include "ns3/assert.h"
#include "ns3/log.h"
#include <cassert>
#include <math.h>
#include <string.h>

namespace ns3 {

NS_LOG_COMPONENT_DEFINE ("Ns2CalendarScheduler");

NS_OBJECT_ENSURE_REGISTERED (Ns2CalendarScheduler);

#define CALENDAR_HASH(key) ((key.m_ts / width_) % nbuckets_)

TypeId 
Ns2CalendarScheduler::GetTypeId (void)
{
	static TypeId tid = TypeId ("ns3::Ns2CalendarScheduler")
		.SetParent<Scheduler> ()
		.AddConstructor<Ns2CalendarScheduler> ()
		;
	return tid;
}

Ns2CalendarScheduler::Ns2CalendarScheduler ()
{
	NS_LOG_FUNCTION (this);

	adjust_new_width_interval_ = 10;
	min_bin_width_ = 1;
	avg_gap_ = -2;
	last_time_ = 0;
	gap_num_ = 0;
	head_search_ = 0;
	insert_search_ = 0; 
	round_num_ = 0; 
	time_to_newwidth_ = adjust_new_width_interval_;
	cal_clock_ = Scheduler::EventKey ();
	reinit(4, 1, cal_clock_);
}
Ns2CalendarScheduler::~Ns2CalendarScheduler ()
{
	NS_LOG_FUNCTION (this);
	
	for (int i = 0; i < nbuckets_; i++) {
		Bucket *bucket = &buckets_[i];
		if (bucket->list_ == 0) {
			continue;
		}
		if (bucket->list_->next_ == bucket->list_) {
			delete bucket->list_;
			continue;
		}
		BucketItem *next;
		BucketItem *cur;
		for (cur = bucket->list_; 
		     cur->next_ != bucket->list_; 
		     cur = next) {
			next = cur->next_;
			delete cur;
		}
		delete cur;
	}
	delete [] buckets_;
	qsize_ = 0;
	stat_qsize_ = 0;
}
void
Ns2CalendarScheduler::Insert (const Event &event)
{
	NS_LOG_FUNCTION (this);

	Scheduler::EventKey newtime = event.key;
	int i = CALENDAR_HASH(newtime);

	Bucket* current=(&buckets_[i]);
	BucketItem *head = current->list_;
	BucketItem *after=0;
	BucketItem *e = new BucketItem ();
	e->event = event;

	if (!head) {
		current->list_ = e;
		e->next_ = e->prev_ = e;
		++stat_qsize_; 
		++(current->count_);
	} else {
		insert_search_++;
		if (newtime < head->event.key) {
			//  e-> head -> ...
			e->next_ = head;
			e->prev_ = head->prev_;
			e->prev_->next_ = e;
			head->prev_ = e;
			current->list_ = e;
			++stat_qsize_;
			++(current->count_);
		} else {
			for (after = head->prev_; newtime < after->event.key; after = after->prev_) 
				{ insert_search_++; };
			//...-> after -> e -> ...
			e->next_ = after->next_;
			e->prev_ = after;
			e->next_->prev_ = e;
			after->next_ = e;
			if (after->event.key < newtime) {
				//unique timing
				++stat_qsize_; 
				++(current->count_);
			}
		}
	}
	++qsize_;
	//assert(e == buckets_[i].list_ ||  e->prev_->time_ <= e->time_);
	//assert(e == buckets_[i].list_->prev_ || e->next_->time_ >= e->time_);

	if (stat_qsize_ > top_threshold_) {
		resize(nbuckets_ << 1, cal_clock_);
		return;
	}
}
bool 
Ns2CalendarScheduler::IsEmpty (void) const
{
	return qsize_ == 0;
}
Scheduler::Event
Ns2CalendarScheduler::PeekNext (void) const
{
	NS_LOG_FUNCTION (this);
	NS_ASSERT (!IsEmpty ());

	BucketItem *e = const_cast<Ns2CalendarScheduler *> (this)->head ();
	NS_ASSERT (e != 0);
	
	return e->event;
}


Scheduler::Event
Ns2CalendarScheduler::RemoveNext (void)
{
	NS_LOG_FUNCTION (this);
	NS_ASSERT (!IsEmpty ());

	BucketItem *e = head ();
	NS_ASSERT (e != 0);

	if (last_time_ == 0) last_time_ = e->event.key.m_ts;
	else 
	{
		gap_num_ ++;
		if (gap_num_ >= qsize_ ) {
			uint64_t tt_gap_ = e->event.key.m_ts - last_time_;
			avg_gap_ = tt_gap_ / gap_num_;
			gap_num_ = 0;
			last_time_ = e->event.key.m_ts;
			round_num_ ++;
			if ((round_num_ > 20) &&
			    (( head_search_> (insert_search_<<1))
			     ||( insert_search_> (head_search_<<1)) )) 
				{
					resize(nbuckets_, cal_clock_);
					round_num_ = 0;
				} else {
				if (round_num_ > 100) {
					round_num_ = 0;
					head_search_ = 0;
					insert_search_ = 0;
				}
			}
		}
	}

	int l = lastbucket_;

	// update stats and unlink
	if (e->next_ == e || e->next_->event.key != e->event.key) {
		--stat_qsize_;
		//assert(stat_qsize_ >= 0);
		--buckets_[l].count_;
		//assert(buckets_[l].count_ >= 0);
	}
	--qsize_;

	if (e->next_ == e)
		buckets_[l].list_ = 0;
	else {
		e->next_->prev_ = e->prev_;
		e->prev_->next_ = e->next_;
		buckets_[l].list_ = e->next_;
	}

	e->next_ = e->prev_ = NULL;


	//if (buckets_[l].count_ == 0)
	//	assert(buckets_[l].list_ == 0);
  
	if (stat_qsize_ < bot_threshold_) {
		resize(nbuckets_ >> 1, cal_clock_);
	}

	Scheduler::Event event = e->event;
	delete e;
	return event;
}

void
Ns2CalendarScheduler::Remove (const Event &ev)
{
	NS_ASSERT (!IsEmpty ());


	int i = CALENDAR_HASH(ev.key);

	Bucket* current=(&buckets_[i]);
	BucketItem *head = current->list_;
	BucketItem *e=0;

	if (!head) {
		NS_LOG_DEBUG ("event not in scheduler");
		return;
	}
	for (e = head->prev_; ev.key != e->event.key; e = e->prev_) {}
	--stat_qsize_;
	--buckets_[i].count_;
	if (e->next_ == e) {
		assert(buckets_[i].list_ == e);
		buckets_[i].list_ = 0;
	} else {
		e->next_->prev_ = e->prev_;
		e->prev_->next_ = e->next_;
		if (buckets_[i].list_ == e)
			buckets_[i].list_ = e->next_;
	}

	if (buckets_[i].count_ == 0)
		assert(buckets_[i].list_ == 0);

	e->next_ = e->prev_ = NULL;

	delete e;

	--qsize_;

	return;
}

Ns2CalendarScheduler::BucketItem *
Ns2CalendarScheduler::head (void)
{
	NS_ASSERT (!IsEmpty ());
	
	int l = -1, i = lastbucket_;
	int lastbucket_dec = (lastbucket_) ? lastbucket_ - 1 : nbuckets_ - 1;
	uint64_t diff;
	BucketItem *e, *min_e = NULL;
#define CAL_DEQUEUE(x) 						\
do {							\
	head_search_++;						\
	if ((e = buckets_[i].list_) != NULL) {			\
		diff = e->event.key.m_ts - cal_clock_.m_ts;	\
		if (diff < diff##x##_)	{			\
			l = i;					\
			goto found_l;				\
		}						\
		if (min_e == NULL || min_e->event.key > e->event.key) {	\
			min_e = e;					\
			l = i;						\
		}							\
	}								\
	if (++i == nbuckets_) i = 0;					\
} while (0)
  
	// CAL_DEQUEUE applied successively will find the event to
	// dequeue (within one year) and keep track of the
	// minimum-priority event seen so far; the argument controls
	// the criteria used to decide whether the event should be
	// considered `within one year'.  Importantly, the number of
	// buckets should not be less than 4.
	CAL_DEQUEUE(0); 
	CAL_DEQUEUE(1); 
	for (; i != lastbucket_dec; ) {
		CAL_DEQUEUE(2);
	}
	// one last bucket is left unchecked - take the minimum
	// [could have done CAL_DEQUEUE(3) with diff3_ = bwidth*(nbuck*3/2-1)]
	e = buckets_[i].list_;
	if (min_e != NULL && 
	    (e == NULL || min_e->event.key < e->event.key))
		e = min_e;
	else {
		//assert(e);
		l = i;
	}
 found_l:
	//assert(buckets_[l].count_ >= 0);
	//assert(buckets_[l].list_ == e);
  
	/* l is the index of the bucket to dequeue, e is the event */
	/* 
	 * still want to advance lastbucket_ and cal_clock_ to save
	 * time when deque() follows. 
	 */
	assert (l != -1);
	lastbucket_ = l;
	cal_clock_  = e->event.key;

	return e;
}

void 
Ns2CalendarScheduler::reinit(int nbuck, uint64_t bwidth, Scheduler::EventKey start)
{
	buckets_ = new Bucket[nbuck];

	memset(buckets_, 0, sizeof(Bucket)*nbuck); //faster than ctor
  
	width_ = bwidth;
	nbuckets_ = nbuck;
	qsize_ = 0;
	stat_qsize_ = 0;
        
	lastbucket_ =  CALENDAR_HASH(start);

	diff0_ = bwidth*nbuck/2;
	diff1_ = diff0_ + bwidth;
	diff2_ = bwidth*nbuck;
	//diff3_ = bwidth*(nbuck*3/2-1);
  
	bot_threshold_ = (nbuck >> 1) - 2;
	top_threshold_ = (nbuck << 1);
}

void 
Ns2CalendarScheduler::resize(int newsize, Scheduler::EventKey start)
{
	uint64_t bwidth;
	if (newsize == nbuckets_) {
		/* we resize for bwidth*/
		if (head_search_) bwidth = head_search_; else bwidth = 1;
		if (insert_search_) bwidth = bwidth / insert_search_;
		bwidth = static_cast<uint64_t> (sqrt (bwidth) * width_);
		if (bwidth < min_bin_width_) {
			if (time_to_newwidth_>0) {
				time_to_newwidth_ --;
				head_search_ = 0;
				insert_search_ = 0;
				round_num_ = 0;
				return; //failed to adjust bwidth
			} else {
				// We have many (adjust_new_width_interval_) times failure in adjusting bwidth.
				// should do a reshuffle with newwidth 
				bwidth = newwidth(newsize);
			}
		}
		//snoopy queue calculation
	} else {
		/* we resize for size */
		bwidth = newwidth(newsize);
		if (newsize < 4)
			newsize = 4;
	}

	Bucket *oldb = buckets_;
	int oldn = nbuckets_;

	reinit(newsize, bwidth, start);

	// copy events to new buckets
	int i;

	for (i = 0; i < oldn; ++i) {
		// we can do inserts faster, if we use insert2, but to
		// preserve FIFO, we have to start from the end of
		// each bucket and use insert2
		if  (oldb[i].list_) {
			BucketItem *tail = oldb[i].list_->prev_;
			BucketItem *e = tail; 
			do {
				BucketItem* ep = e->prev_;
				e->next_ = e->prev_ = 0;
				insert2(e);
				e = ep;
			} while (e != tail);
		}
	}
	head_search_ = 0;
	insert_search_ = 0;
	round_num_ = 0;
	delete [] oldb;
}

void 
Ns2CalendarScheduler::insert2(Ns2CalendarScheduler::BucketItem* e)
{
	// Same as insert, but for inserts e *before* any same-time-events, if
	//   there should be any.  Since it is used only by CalendarScheduler::newwidth(),
	//   some important checks present in insert() need not be performed.

	int i = CALENDAR_HASH(e->event.key);
	BucketItem *head = buckets_[i].list_;
	BucketItem *before=0;
	if (!head) {
		buckets_[i].list_ = e;
		e->next_ = e->prev_ = e;
		++stat_qsize_; 
		++buckets_[i].count_;
	} else {
		bool newhead;
		if (e->event.key > head->prev_->event.key) { //strict LIFO, so > and not >=
			// insert at the tail
			before = head;
			newhead = false;
		} else {
			// insert event in time sorted order, LIFO for sim-time events
			for (before = head; e->event.key > before->event.key; before = before->next_)
				;
			newhead = (before == head);
		}

		e->next_ = before;
		e->prev_ = before->prev_;
		before->prev_ = e;
		e->prev_->next_ = e;
		if (newhead) {
			buckets_[i].list_ = e;
			//assert(e->time_ <= e->next_->time_);
		}

		if (e != e->next_ && e->next_->event.key != e->event.key) {
			// unique timing
			++stat_qsize_; 
			++buckets_[i].count_;
		}
	}
	//assert(e == buckets_[i].list_ ||  e->prev_->time_ <= e->time_);
	//assert(e == buckets_[i].list_->prev_ || e->next_->time_ >= e->time_);

	++qsize_;
	// no need to check resizing
}

uint64_t
Ns2CalendarScheduler::newwidth(int newsize)
{
	if (adjust_new_width_interval_) {
		time_to_newwidth_ = adjust_new_width_interval_;
		if (avg_gap_ > 0) return avg_gap_*4;
	}
	int i;
	int max_bucket = 0; // index of the fullest bucket
	for (i = 1; i < nbuckets_; ++i) {
		if (buckets_[i].count_ > buckets_[max_bucket].count_)
			max_bucket = i;
	}
	int nsamples = buckets_[max_bucket].count_;

	if (nsamples <= 4) return width_;
	
	uint64_t nw = (buckets_[max_bucket].list_->prev_->event.key.m_ts 
		       - buckets_[max_bucket].list_->event.key.m_ts) * 4;
	
	nw /= ((newsize < nsamples) ? newsize : nsamples); // min (newsize, nsamples)

	nw = std::max (nw, min_bin_width_);
	
	return nw;
}

  
} // namespace ns3