/*
Implementation Notes

We represent time using 32 bit values and use 1 us resolution.
This allows for 4000 seconds of time, so more than an hour.
We assume that each link will send at least one packet every
30 minutes, a safe assumption if link speeds are at least 1 Kb/s,
AND if neighbors' links are constrained so they can't send us
packets faster than the max rate at which we can forward them.
This allows us to use circular time values that wrap around.
If a, b are distinct time values, we interpret a to be greater
than b if (a-b) < 2^31.

We maintain two heaps defined on the links. The active heap
contains links for which packets are currently queued. The
vactive heap contains links that are "virtually active", meaning
that they recently sent their last packet, but they are not
yet allowed to send their next, given the limit on their bit
rate and packet rate. If a packet arrives for a virtually active
link, it is moved to the active heap with a deadline inherited
from the vactive heap.

It's important that links be moved off the vactive heap when
they become eligible to send new packets. This is done in the
nextReady routine, which is expected to be called frequently
(e.g. once on each iteration of the router's main loop).
*/

#include "qMgr.h"

qMgr::qMgr(int nL1, int nP1, int qL1, pktStore *ps1, lnkTbl *lt1) 
: nL(nL1), nP(nP1), qL(qL1), ps(ps1), lt(lt1) {
// Constructor for qMgr, allocates space and initializes everything.
	int i;

	queues = new listset(nP,nL);
	active = new mheap(nL,4,true);  // active is also a min-heap
	vactive = new mheap(nL,4,true);  // vactive is a min-heap 
	npq = new int[nL+1]; nbq = new int[nL+1];

	for (i = 1; i <= nL; i++) { npq[i] = 0; nbq[i] = 0; }
}
		
qMgr::~qMgr() { delete queues; delete active; delete [] npq; delete [] nbq; }

bool qMgr::enq(int p, int lnk, uint32_t now) {
// Enqueue packet on given queue on link. Return true if
// packet was successfully queued, else false. Note, it
// is up to the caller to discard packets that are not queued.
	if (npq[lnk] >= qL) return false;
	queues->enq(p,lnk);
	if (!active->member(lnk)) {
		uint32_t d = now;;
		if (vactive->member(lnk)) {
			d = vactive->key(lnk);
			if ((now - d) <= (1 << 31))  // that is, if now >= d
				d = now;
			vactive->remove(lnk);
		}
		active->insert(lnk,d);
	}
	npq[lnk]++; nbq[lnk] += ps->leng(p);
	return true;
}

int qMgr::deq(int lnk) {
// Remove first packet from the queue for lnk and update heaps.
// Return the index of the deleted packet.
	int p = queues->deq(lnk);
	if (p == Null) return Null;
	npq[lnk]--; nbq[lnk] -= ps->leng(p);

	uint32_t d = (ps->leng(p)*8000)/lt->bitRate(lnk); 
	d = max(d,lt->minDelta(lnk));
	d += active->key(lnk);

	if (queues->empty(lnk)) {
		vactive->insert(lnk,d);
		active->remove(lnk);
	} else {
		active->changekey(lnk,d);
	}
	return p;
}


int qMgr::nextReady(uint32_t now) {
// Return the index of the next link that is ready to send, or Null if
// none is ready to send. This routine also checks to see if any of
// the links in the vactive heap can be removed.
	// remove vactive links whose times are now past
	int lnk = vactive->findmin(); uint32_t d = vactive->key(lnk);
	while (lnk != Null && (now - d) <= (1 << 31)) {
		vactive->remove(lnk);
		lnk = vactive->findmin(); d = vactive->key(lnk);
	}
	// determine next active queue that is ready to go
	if (active->empty()) return Null;
	lnk = active->findmin(); d = active->key(lnk);
	if ((now - d) <= (1 << 31)) return lnk;
	return Null;
}