/* -*-	Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
//
// Copyright (c) 1997 by the University of Southern California
// All rights reserved.
//
// Permission to use, copy, modify, and distribute this software and its
// documentation in source and binary forms for non-commercial purposes
// and without fee is hereby granted, provided that the above copyright
// notice appear in all copies and that both the copyright notice and
// this permission notice appear in supporting documentation. and that
// any documentation, advertising materials, and other materials related
// to such distribution and use acknowledge that the software was
// developed by the University of Southern California, Information
// Sciences Institute.  The name of the University may not be used to
// endorse or promote products derived from this software without
// specific prior written permission.
//
// THE UNIVERSITY OF SOUTHERN CALIFORNIA makes no representations about
// the suitability of this software for any purpose.  THIS SOFTWARE IS
// PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES,
// INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// Other copyrights might apply to parts of this software and are so
// noted when applicable.
//
// Multimedia cache implementation
//
// $Header: /nfs/jade/vint/CVSROOT/ns-2/webcache/mcache.cc,v 1.11 1999/12/20 19:20:40 haoboy Exp $

#include <assert.h>
#include <stdio.h>

#include "rap/media-app.h"
#include "mcache.h"


MediaPage::MediaPage(const char *n, int s, double mt, double et, 
		     double a, int l) :
	ClientPage(n, s, mt, et, a), num_layer_(l), locked_(0), realsize_(0)
{
	for (int i = 0; i < num_layer_; i++) {
		hc_[i] = new HitCount(this, i);
		flags_[i] = 0;
	}
}

MediaPage::~MediaPage()
{
	int i; 
	for (i = 0; i < num_layer_; i++) {
		// Delete hit count list
		// These hit count records should have already been removed
		// from the cache's hit count list. 
		assert((hc_[i]->prev() == NULL) && (hc_[i]->next() == NULL));
		delete hc_[i];
		// Delete media segment list
		layer_[i].destroy();
	}
}

void MediaPage::print_info(char *buf) 
{
	ClientPage::print_info(buf);
	buf += strlen(buf);
	sprintf(buf, " pgtype MEDIA layer %d", num_layer_);
}

// Make the page full with stream data
void MediaPage::create()
{
	assert((num_layer_ >= 0) && (num_layer_ < MAX_LAYER));
	int i, sz = size_ / num_layer_;
	for (i = 0; i < num_layer_; i++) {
		// Delete whatever that was there. 
		layer_[i].destroy();
		add_segment(i, MediaSegment(0, sz));
		set_complete_layer(i);
	}
	realsize_ = size_;
}

void MediaPage::add_segment(int layer, const MediaSegment& s) 
{
	assert((layer >= 0) && (layer < MAX_LAYER));
	layer_[layer].add(s);
	realsize_ += s.datasize();
	if (s.is_last())
		set_complete_layer(layer);
}

int MediaPage::is_complete()
{
	// Consider a page finished when all NON-EMPTY layers are 
	// marked as "completed"
	for (int i = 0; i < num_layer_; i++)
		if (!is_complete_layer(i) && (layer_[i].length() > 0))
			return 0;
	return 1;
}

void MediaPage::set_complete()
{
	for (int i = 0; i < num_layer_; i++)
		set_complete_layer(i);
}

// Used for cache replacement
int MediaPage::evict_tail_segment(int layer, int size)
{
	if (is_locked() || is_tlocked())
		return 0;

	assert((layer >= 0) && (layer < MAX_LAYER));
	//#ifdef MCACHE_DEBUG
#if 0
	char buf[20];
	name(buf);
	fprintf(stderr, "Page %s evicted layer %d: ", buf, layer);
#endif
	int sz = layer_[layer].evict_tail(size);
	realsize_ -= sz;
	//#ifdef MCACHE_DEBUG
#if 0
	fprintf(stderr, "\n");
#endif
	return sz;
}



//----------------------------------------------------------------------
// Classes related to a multimedia client page pool
//
// HitCountList and MClientPagePool
//----------------------------------------------------------------------

void HitCountList::update(HitCount *h)
{
	HitCount *tmp = h->prev();
	if ((tmp != NULL) && (tmp->hc() < h->hc())) {
		// Hit count increased, need to move this one up
		detach(h);
		while ((tmp != NULL) && (tmp->hc() < h->hc())) {
			if ((tmp->page() == h->page()) &&
			    (tmp->layer() < h->layer()))
				// XXX Don't violate layer encoding within the
				// same page!
				break;
			tmp = tmp->prev();
		}
		if (tmp == NULL) 
			// Insert it at the head
			insert(h, head_);
		else 
			append(h, tmp);
	} else if ((h->next() != NULL) && (h->hc() < h->next()->hc())) {
		// Hit count decreased, need to move this one down
		tmp = h->next();
		detach(h);
		while ((tmp != NULL) && (h->hc() < tmp->hc())) {
			if ((h->page() == tmp->page()) && 
			    (h->layer() < tmp->layer()))
				// XXX Don't violate layer encoding within 
				// the same page!
				break;
			tmp = tmp->next();
		}
		if (tmp == NULL)
			// At the tail
			append(h, tail_);
		else
			insert(h, tmp);
	}
	// We may end up with two cases here:
	//
	// (1) tmp->hc()>h->hc() && tmp->layer()<h->layer(). This is
	// the normal case, where both hit count ordering and layer 
	// ordering are preserved;
	//
	// (2) tmp->hc()>h->hc() && tmp->layer()>h->layer(). In this
	// case, we should move h BEFORE tmp so that the layer 
	// ordering is not violated. We basically order the list using 
	// layer number as primary key, and use hit count as secondary
	// key. 
	// Note that the hit count ordering is only violated when more packets 
	// in layer i are dropped than those in layer i+1.
}

// Check the integrity of the resulting hit count list
void HitCountList::check_integrity()
{
	HitCount *p = (HitCount*)head_, *q;
	while (p != NULL) {
		q = p->next();
		while (q != NULL) {
			// Check layer ordering 
			if ((p->page() == q->page()) && 
			    (p->layer() > q->layer())) {
				fprintf(stderr, "Wrong hit count list.\n");
				abort();
			}
			q = q->next();
		}
		p = p->next();
	}
}

void HitCountList::add(HitCount *h)
{
	HitCount *tmp = (HitCount*)head_;

	// XXX First, ensure that the layer ordering within the same page
	// is not violated!!
	while ((tmp != NULL) && (tmp->hc() > h->hc())) {
		if ((tmp->page() == h->page()) && (tmp->layer() > h->layer()))
			break;
		tmp = tmp->next();
	}
	// Then order according to layer number
	while ((tmp != NULL) && (tmp->hc() == h->hc()) && 
	       (tmp->layer() < h->layer()))
		tmp = tmp->next();

	if (tmp == NULL) {
		if (head_ == NULL) 
			head_ = tail_ = h;
		else
			append(h, tail_);
		return;
	} else if ((tmp == head_) && 
		   ((tmp->hc() < h->hc()) || (tmp->layer() > h->layer()))) {
		insert(h, head_);
		return;
	}

	// Now tmp->hc()<=h->hc(), or tmp->hc()>h->hc() but 
	// tmp->layer()>h->layer(), insert h BEFORE tmp
	insert(h, tmp);
}

// Debug only
void HitCountList::print() 
{
	HitCount *p = (HitCount *)head_;
	int i = 0;
	char buf[20];
	while (p != NULL) {
		p->page()->name(buf);
	        fprintf(stderr, "(%s %d %f) ", buf, p->layer(), p->hc());
		if (++i % 4 == 0)
			printf("\n");
		p = p->next();
	}
	if (i % 4 != 0)
		fprintf(stderr, "\n");
}

//------------------------------
// Multimedia client page pool
//------------------------------
static class MClientPagePoolClass : public TclClass {
public:
        MClientPagePoolClass() : TclClass("PagePool/Client/Media") {}
        TclObject* create(int, const char*const*) {
		return (new MClientPagePool());
	}
} class_mclientpagepool_agent;

MClientPagePool::MClientPagePool() : 
	used_size_(0), repl_style_(FINEGRAIN)
{
	bind("max_size_", &max_size_);
	used_size_ = 0;
}

int MClientPagePool::command(int argc, const char*const* argv)
{
	if (argc == 3) 
		if (strcmp(argv[1], "set-repl-style") == 0) {
			// Set replacement style
			// <obj> set-repl-style <style>
			if (strcmp(argv[2], "FINEGRAIN") == 0) 
				repl_style_ = FINEGRAIN;
			else if (strcmp(argv[2], "ATOMIC") == 0)
				repl_style_ = ATOMIC;
			else {
				fprintf(stderr, "Unknown style %s", argv[3]);
				return (TCL_ERROR);
			}
			return (TCL_OK);
		}
	return ClientPagePool::command(argc, argv);
}

void MClientPagePool::hc_update(const char *name, int max_layer)
{
	MediaPage *pg = (MediaPage*)get_page(name);
	assert(pg != NULL);

	int i;
	HitCount *h;
	// First we update the hit count of each layer of the given page
	for (i = 0; i <= max_layer; i++)
		pg->hit_layer(i);
	// Then we update the position of these hit count records
	for (i = 0; i <= max_layer; i++) {
		h = pg->get_hit_count(i);
		hclist_.update(h);
	}
#if 1
	hclist_.check_integrity();
#endif
}

// Add a segment to an object, and adjust hit counts accordingly
// XXX Call cache replacement algorithm if necessary
int MClientPagePool::add_segment(const char* name, int layer, 
				 const MediaSegment& s)
{
	MediaPage* pg = (MediaPage *)get_page(name);
	if (pg == NULL)
		return -1;
	if (layer >= pg->num_layer()) {
		if (s.datasize() == 0)
			return 0;
		else {
			fprintf(stderr, 
				"MClientPagePool: cannot add a new layer.\n");
			abort();
		}
	}

	// Check space availability
	if (used_size_ + s.datasize() > max_size_) {
		// If atomic replacement is used, page size is deducted in
		// remove_page(). If fine-grain is used, evicted size is 
		// deducted in repl_finegrain().
		cache_replace(pg, s.datasize());
		//#ifdef MCACHE_DEBUG
#if 0
		fprintf(stderr, 
			"Replaced for page %s segment (%d %d) layer %d\n",
			name, s.start(), s.end(), layer);
#endif
	} 
	// Add new page. When we are doing atomic replacement, the size that
	// we evicted may be larger than what we add.
	used_size_ += s.datasize();

	// If this layer was not 'in' before, add its hit count block
	if (pg->layer_size(layer) == 0)
		hclist_.add(pg->get_hit_count(layer));

	// Add new segment
	pg->add_segment(layer, s);

	return 0;
}

void MClientPagePool::fill_page(const char* pgname)
{
	MediaPage *pg = (MediaPage*)get_page(pgname);
	used_size_ -= pg->realsize();
	// Lock this page before we do any replacement. 
	pg->lock();
	pg->create();
	// If we cannot hold the nominal size of the page, do replacement
	if (used_size_ + pg->size() > max_size_)
		// Size deduction has already been done in remove_page()
		cache_replace(pg, pg->size());
	used_size_ += pg->size();
	pg->unlock();
}

ClientPage* MClientPagePool::enter_page(int argc, const char*const* argv)
{
	double mt = -1, et, age = -1, noc = 0;
	int size = -1, media_page = 0, layer = -1;
	for (int i = 3; i < argc; i+=2) {
		if (strcmp(argv[i], "modtime") == 0)
			mt = strtod(argv[i+1], NULL);
		else if (strcmp(argv[i], "size") == 0) 
			size = atoi(argv[i+1]);
		else if (strcmp(argv[i], "age") == 0)
			age = strtod(argv[i+1], NULL);
		else if (strcmp(argv[i], "noc") == 0)
			// non-cacheable flag
			noc = 1;
		else if (strcmp(argv[i], "pgtype") == 0) {
			if (strcmp(argv[i+1], "MEDIA") == 0)
				media_page = 1;
		} else if (strcmp(argv[i], "layer") == 0)
			layer = atoi(argv[i+1]);
	}
	// XXX allow mod time < 0 and age < 0!
	if ((size < 0) || (media_page && (layer <= 0))) {
		fprintf(stderr, "%s: wrong page information %s\n",
			name_, argv[2]);
		return NULL;
	}
	et = Scheduler::instance().clock();
	ClientPage *pg;
	if (media_page)
		pg = new MediaPage(argv[2], size, mt, et, age, layer);
	else 
		pg = new ClientPage(argv[2], size, mt, et, age);
	if (add_page(pg) < 0) {
		delete pg;
		return NULL;
	}
	if (noc) 
		pg->set_uncacheable();
	if (media_page) 
		((MediaPage *)pg)->lock();
	return pg;
}

int MClientPagePool::cache_replace(ClientPage *pg, int size)
{
	switch (repl_style_) {
	case FINEGRAIN:
		return repl_finegrain(pg, size);
	case ATOMIC:
#if 0
		char tmp[128];
		pg->name(tmp);
		fprintf(stderr, "Replaced for page %s size %d\n", tmp, size);
		fprintf(stderr, "Used size %d, max size %d\n", used_size_, 
			max_size_);
#endif
		return repl_atomic(pg, size);
	default:
		fprintf(stderr, "Corrupted replacement style.\n");
		abort();
	}
	// To make msvc happy
	return -1;
}

int MClientPagePool::repl_atomic(ClientPage*, int size)
{
	// XXX We use standard LRU to determine the stream to be kicked out.
	// The major problem is that we do not keep discrete hit counts. 
	// We solve the problem by using hit counts of the base layer as 
	// a close approximate. Because whenever a stream is accessed, 
	// it's assumed that the client bw can always afford the base layer,
	// this should be a fairly good approximation. 

	HitCount *h, *p;
	int sz, totalsz = 0;
	// Repeatedly get rid of streams until get enough space
	h = (HitCount*)hclist_.tail();
	while (h != NULL) {
		if (h->layer() != 0) {
			// We only look for the base layer
			h = h->prev();
			continue;
		}
		MediaPage *pg = (MediaPage *)h->page();
		// Don't touch locked pages
		if (pg->is_tlocked() || pg->is_locked()) {
			h = h->prev();
			continue;
		}
		sz = pg->realsize();
		totalsz += sz;
		char tmp[HTTP_MAXURLLEN];
		pg->name(tmp);
		// Before we delete, find the previous hit count record that
		// does not belong to this page. 
		p = h->prev(); 
		while ((p != NULL) && (p->page() == h->page()))
			p = p->prev();
		h = p;
		// XXX Manually remove hit count before deleting it
		for (int i = 0; i < pg->num_layer(); i++) {
			p = pg->get_hit_count(i);
			hclist_.detach(p);
		}
		// Delete the page, together with its media segment list
#if 0
		fprintf(stderr, "At time %g, atomic replacement evicted page %s\n", 
			Scheduler::instance().clock(), tmp); 
		fprintf(stderr, "Hit count list: \n");
		hclist_.print();
		fprintf(stderr,"----------------------------------------\n\n");
#endif		
		remove_page(tmp);
		if (sz >= size)
			return totalsz;
		// Continue to evict to meet the space requirement
		size -= sz;
	}
	fprintf(stderr, "Cache replacement cannot get enough space.\n");
	abort();
	return 0; // Make msvc happy
}

int MClientPagePool::repl_finegrain(ClientPage *, int size)
{
	// Traverse through hit count table, evict segments from the tail
	// of a layer with minimum hit counts
	HitCount *h, *p;
	int sz, totalsz = 0;

	// Repeatedly evict pages/segments until get enough space
	h = (HitCount*)hclist_.tail();
	while (h != NULL) {
		MediaPage *pg = (MediaPage *)h->page();
		// XXX Don't touch locked pages
		if (pg->is_tlocked() || pg->is_locked()) {
			h = h->prev();
			continue;
		}
		// Try to get "size" space by evicting other segments
		sz = pg->evict_tail_segment(h->layer(), size);
		// Decrease the cache used space
		used_size_ -= sz;
		totalsz += sz;
		// If we have not got enough space, we must have got rid of 
		// the entire layer
		assert((sz == size) || 
		       ((sz < size) && (pg->layer_size(h->layer()) == 0)));

		// If we don't have anything of this layer left, get rid of 
		// the hit count record. 
		// XXX Must do this BEFORE removing the page
		p = h;
		h = h->prev();
		if (pg->layer_size(p->layer()) == 0) {
			// XXX Should NEVER delete a hit count record!!
			// A hit count record is ONLY deleted when the page
			// is deleted (evicted from cache: ~MediaPage())
			hclist_.detach(p);
			p->reset();
		}
		// Furthermore, if the page has nothing left, get rid of it
		if (pg->realsize() == 0) {
			// NOTE: we do not manually remove hit counts of 
			// this page because if its realsize is 0, all 
			// hit count records must have already been 
			// detached from the page. 
			char tmp[HTTP_MAXURLLEN];
			pg->name(tmp);
#if 0
			fprintf(stderr, "At time %g, fine-grain evicted page %s\n",
				Scheduler::instance().clock(), tmp);
			fprintf(stderr, "Hit count list: \n");
			hclist_.print();
			fprintf(stderr,
				"---------------------------------------\n\n");
#endif
			// Then the hit count record will be deleted in here
			remove_page(tmp);
		}
		// If we've got enough space, return; otherwise continue
		if (sz >= size)
			return totalsz;
		size -= sz;	// Evict to fill the rest
	}
	fprintf(stderr, "Cache replacement cannot get enough space.\n");
	abort();
	return 0; // Make msvc happy
}

// Clean all hit count record of a page regardless of whether it's in the 
// hit count list. Used when hclist_ is not used at all, e.g., by MediaClient.
int MClientPagePool::force_remove(const char *name)
{
	// XXX Bad hack. Needs to integrate this into ClientPagePool.
	ClientPage *pg = (ClientPage*)get_page(name);
	// We should not remove a non-existent page!!
	assert(pg != NULL);
	if (pg->type() == MEDIA) {
		HitCount *p;
		MediaPage *q = (MediaPage*)pg;
		used_size_ -= q->realsize();
		for (int i = 0; i < q->num_layer(); i++) {
			p = q->get_hit_count(i);
			hclist_.detach(p);
		}
	} else if (pg->type() == HTML)
		used_size_ -= pg->size();
	return ClientPagePool::remove_page(name);
}

int MClientPagePool::remove_page(const char *name)
{
	// XXX Bad hack. Needs to integrate this into ClientPagePool.
	ClientPage *pg = (ClientPage*)get_page(name);
	// We should not remove a non-existent page!!
	assert(pg != NULL);
	if (pg->type() == MEDIA)
		used_size_ -= ((MediaPage *)pg)->realsize();
	else if (pg->type() == HTML)
		used_size_ -= pg->size();
	return ClientPagePool::remove_page(name);
}



//------------------------------------------------------------
// MediaPagePool
// Generate requests and pages for clients and servers 
//------------------------------------------------------------
static class MediaPagePoolClass : public TclClass {
public:
        MediaPagePoolClass() : TclClass("PagePool/Media") {}
        TclObject* create(int, const char*const*) {
		return (new MediaPagePool());
	}
} class_mediapagepool_agent;

MediaPagePool::MediaPagePool() : PagePool()
{
	size_ = NULL;
	duration_ = 0;
	layer_ = 1;
}

// For now, only one page, fixed size, fixed layer
int MediaPagePool::command(int argc, const char*const* argv)
{
	Tcl& tcl = Tcl::instance();

	if (argc == 2) {
		if (strcmp(argv[1], "get-poolsize") == 0) { 
			tcl.resultf("%d", num_pages_);
			return TCL_OK;
		} else if (strcmp(argv[1], "get-start-time") == 0) {
			tcl.resultf("%.17g", start_time_);
			return TCL_OK;
		} else if (strcmp(argv[1], "get-duration") == 0) {
			tcl.resultf("%d", duration_);
			return TCL_OK;
		}
	} else if (argc == 3) {
		if (strcmp(argv[1], "gen-pageid") == 0) {
			// Generating requested page id
			if (rvReq_ == NULL) {
				tcl.add_errorf("no page id ranvar.");
				return TCL_ERROR;
			}
			int p = (int)rvReq_->value();
			assert((p >= 0) && (p < num_pages_));
			tcl.resultf("%d", p);
			return TCL_OK;
		} else if (strcmp(argv[1], "is-media-page") == 0) {
			// XXX Currently all pages are media pages. Should
			// be able to allow both normal pages and media pages
			// in the future
			tcl.result("1");
			return TCL_OK;
		} else if (strcmp(argv[1], "get-layer") == 0) {
			// XXX Currently all pages have the same number of 
			// layers. Should be able to change this in future.
			tcl.resultf("%d", layer_); 
			return TCL_OK;
		} else if (strcmp(argv[1], "set-start-time") == 0) {
			double st = strtod(argv[2], NULL);
			start_time_ = st;
			end_time_ = st + duration_;
			return TCL_OK;
		} else if (strcmp(argv[1], "set-duration") == 0) {
			// XXX Need this info to set page mod time!!
			duration_ = atoi(argv[2]);
			end_time_ = start_time_ + duration_;
			return TCL_OK;
		} else if (strcmp(argv[1], "gen-init-modtime") == 0) {
			// XXX We are not interested in page consistency here,
			// so never change this page.
			tcl.resultf("%d", -1);
			return TCL_OK;
		} else if (strcmp(argv[1], "gen-size") == 0) {
			int pagenum = atoi(argv[2]);
			if (pagenum >= num_pages_) {
				tcl.add_errorf("Invalid page id %d", pagenum);
				return TCL_ERROR;
			}
			tcl.resultf("%d", size_[pagenum]);
			return TCL_OK;
		} else if (strcmp(argv[1], "set-layer") == 0) {
			layer_ = atoi(argv[2]);
			return TCL_OK;
		} else if (strcmp(argv[1], "set-num-pages") == 0) {
			if (size_ != NULL) {
				tcl.add_errorf("can't change number of pages");
				return TCL_ERROR;
			}
			num_pages_ = atoi(argv[2]);
			size_ = new int[num_pages_];
			return TCL_OK;
		} else if (strcmp(argv[1], "ranvar-req") == 0) {
			rvReq_ = (RandomVariable*)TclObject::lookup(argv[2]);
			return TCL_OK;
		}
	} else if (argc == 4) {
		if (strcmp(argv[1], "gen-modtime") == 0) {
			// This should never be called, because we never
			// deals with page modifications!!
			fprintf(stderr, "%s: gen-modtime called!\n", name());
			abort();
		} else if (strcmp(argv[1], "set-pagesize") == 0) {
			// <pagepool> set-pagesize <pagenum> <size>
			int pagenum = atoi(argv[2]);
			if (pagenum >= num_pages_) {
				tcl.add_errorf("Invalid page id %d", pagenum);
				return TCL_ERROR;
			}
			size_[pagenum] = atoi(argv[3]);
			return TCL_OK;
		}
	}
	return PagePool::command(argc, argv);
}



//----------------------------------------------------------------------
// PagePool that generates requests using the SURGE model
//
// Part of the code by Paul Barford (barford@cs.bu.edu).
// Copyright (c) 1997 Trustees of Boston University
//
// Allow two options: (1) setting if all pages are media page or normal
// HTTP pages; (2) average page size
//----------------------------------------------------------------------
//  static class SurgePagePoolClass : public TclClass {
//  public:
//          SurgePagePoolClass() : TclClass("PagePool/Surge") {}
//          TclObject* create(int, const char*const*) {
//  		return (new SurgePagePool());
//  	}
//  } class_surgepagepool_agent;

//  SurgePagePool::SurgePagePool() : PagePool()
//  {
//  }



//----------------------------------------------------------------------
// Multimedia web applications: cache, etc.
//----------------------------------------------------------------------

static class MediaCacheClass : public TclClass {
public:
	MediaCacheClass() : TclClass("Http/Cache/Media") {}
	TclObject* create(int, const char*const*) {
		return (new MediaCache());
	}
} class_mediacache;

// By default we use online prefetching
MediaCache::MediaCache() : pref_style_(ONLINE_PREF)
{
	cmap_ = new Tcl_HashTable;
	Tcl_InitHashTable(cmap_, TCL_ONE_WORD_KEYS);
}

MediaCache::~MediaCache()
{
	Tcl_HashEntry *he;
	Tcl_HashSearch hs;
	if (cmap_) {
		for (he = Tcl_FirstHashEntry(cmap_, &hs);  he != NULL;
		     he = Tcl_NextHashEntry(&hs))
			delete (RegInfo*)Tcl_GetHashValue(he);
		Tcl_DeleteHashTable(cmap_);
		delete cmap_;
	}
}

AppData* MediaCache::get_data(int& size, AppData* req)
{
	assert(req != NULL);
	if (req->type() != MEDIA_REQUEST) {
		return HttpApp::get_data(size, req);
	}

	MediaRequest *r = (MediaRequest *)req;

	// Get statistics block for the requestor
	Tcl_HashEntry *he = 
		Tcl_FindHashEntry(cmap_, (const char *)(r->app()));
	assert(he != NULL);
	RegInfo *ri = (RegInfo *)Tcl_GetHashValue(he);

	// Process request
	if (r->request() == MEDIAREQ_GETSEG) {
		// Get a new data segment
		MediaPage* pg = (MediaPage*)pool_->get_page(r->name());
		assert(pg != NULL);
		MediaSegment s1(r->st(), r->et());
		MediaSegment s2 = pg->next_overlap(r->layer(), s1);
		HttpMediaData *p;
		if (s2.datasize() == 0) {
			// No more data available for this layer, allocate
			// an ADU with data size 0 to signal the end
			// of transmission for this layer
			size = 0;
			p = new HttpMediaData(name(), r->name(),
					      r->layer(), 0, 0);
		} else {
			size = s2.datasize();
			p = new HttpMediaData(name(), r->name(),
					   r->layer(), s2.start(), s2.end());
		}
		// XXX If we are still receiving the stream, don't 
		// ever say that this is the last segment. If the 
		// page is not locked, it's still possible that we
		// return a NULL segment because the requested one
		// is not available. Don't set the 'LAST' flag in this 
		// case.
		if (s2.is_last()) {
			p->set_last();
			if (!pg->is_locked() && (s2.datasize() == 0) && 
			    (r->layer() == 0)) 
				p->set_finish();
		}

		//----------------------------------------
		// Update statistics of this connection
		//----------------------------------------
		// Update the highest layer that this client has requested
		if (ri->hl_ < r->layer())
			ri->hl_ = r->layer();
		if (size > 0) {
			// Update total delivered bytes
			ri->db_[r->layer()] += size;
			// Update prefetched bytes that've been delivered
			ri->eb_[r->layer()] += ri->pref_size(r->layer(), s2);
		}
		return p;
	} else if (r->request() == MEDIAREQ_CHECKSEG) {
		// If we are not doing online prefetching, return nothing
		if (pref_style_ != ONLINE_PREF)
			return NULL;
		// Check the availability of a new data segment
		// And refetch if it is not available
		MediaPage* pg = (MediaPage*)pool_->get_page(r->name());
		assert(pg != NULL);
		if (pg->is_locked()) 
			// If we are during the first retrieval, don't prefetch
			return NULL;
		MediaSegmentList ul = pg->is_available(r->layer(),
				      MediaSegment(r->st(),r->et()));
		if (ul.length() == 0)
			// All segments are available
			return NULL;
		// Otherwise do prefetching on these "holes"
		char *buf = ul.dump2buf();
		Tcl::instance().evalf("%s pref-segment %s %s %d %s", name(), 
				      r->app()->name(), r->name(), 
				      r->layer(), buf);
//  		log("E PREF p %s l %d %s\n", r->name(), r->layer(), buf);
		delete []buf;
		ul.destroy();

		// Update the highest layer that this client has requested
		Tcl_HashEntry *he = 
			Tcl_FindHashEntry(cmap_, (const char *)(r->app()));
		assert(he != NULL);
		RegInfo *ri = (RegInfo *)Tcl_GetHashValue(he);
		if (ri->hl_ < r->layer())
			ri->hl_ = r->layer();
		return NULL;
	}
		
	fprintf(stderr, 
		"MediaCache %s gets an unknown MediaRequest type %d\n",
		name(), r->request());
	abort();
	return NULL; // Make msvc happy
}

// Add received media segment into page pool
void MediaCache::process_data(int size, AppData* data) 
{
	switch (data->type()) {
	case MEDIA_DATA: {
		HttpMediaData* d = (HttpMediaData*)data;
		// Cache this segment, do replacement if necessary
		if (mpool()->add_segment(d->page(), d->layer(), 
					 MediaSegment(*d)) == -1) {
			fprintf(stderr, "MediaCache %s gets a segment for an "
				"unknown page %s\n", name(), d->page());
			abort();
		}
		if (d->is_pref()) {
			// Update total prefetched bytes
			Tcl_HashEntry *he = Tcl_FindHashEntry(cmap_, 
						(const char*)(d->conid()));
			// Client-cache-server disconnection procedure:
			// (1) client disconnects from cache, then
			// (2) cache disconnects from server and shuts down 
			//     prefetching channel. 
			// Therefore, after client disconnects, the cache 
			// may still receive a few prefetched segments. 
			// Ignore those because we no longer keep statistics
			// about the torn-down connection.
			if (he != NULL) {
				RegInfo *ri = (RegInfo *)Tcl_GetHashValue(he);
				ri->add_pref(d->layer(), MediaSegment(*d));
				ri->pb_[d->layer()] += d->datasize();
			}
		}
		// XXX debugging only
#if 1
  		log("E RSEG p %s l %d s %d e %d z %d f %d\n", 
  		    d->page(), d->layer(), d->st(), d->et(), d->datasize(),
  		    d->is_pref());
#endif
		break;
	} 
	default:
		HttpCache::process_data(size, data);
	}
}

int MediaCache::command(int argc, const char*const* argv) 
{
	Tcl& tcl = Tcl::instance();
	if (argc == 2) {
		if (strcmp(argv[1], "get-pref-style") == 0) {
			switch (pref_style_) {
			case NOPREF:
				tcl.result("NOPREF");
				break;
			case ONLINE_PREF:
				tcl.result("ONLINE_PREF");
				break;
			case OFFLINE_PREF:
				tcl.result("OFFLINE_PREF");
				break;
			default:
				fprintf(stderr, 
					"Corrupted prefetching style %d", 
					pref_style_);
				return TCL_ERROR;
			}
			return TCL_OK;
		}
	} else if (argc == 3) {
		if (strcmp(argv[1], "offline-complete") == 0) {
			// Delete whatever segments in the given page, 
			// make it complete. Used by offline prefetching
			ClientPage *pg = mpool()->get_page(argv[2]);
			if (pg == NULL)
				// XXX It's possible that we've already kicked
				// it out of the cache. Do nothing.
				return TCL_OK;
			assert(pg->type() == MEDIA);
			assert(!((MediaPage*)pg)->is_locked());
			mpool()->fill_page(argv[2]);
			return TCL_OK;
		} else if (strcmp(argv[1], "set-pref-style") == 0) {
			// Set prefetching style
			// <obj> set-pref-style <style>
			//
			// style can be: NOPREF, ONLINE_PREF, OFFLINE_PREF
			if (strcmp(argv[2], "NOPREF") == 0) 
				pref_style_ = NOPREF;
			else if (strcmp(argv[2], "ONLINE_PREF") == 0) 
				pref_style_ = ONLINE_PREF;
			else if (strcmp(argv[2], "OFFLINE_PREF") == 0) 
				pref_style_ = OFFLINE_PREF;
			else {
				fprintf(stderr, "Wrong prefetching style %s",
					argv[2]);
				return TCL_ERROR;
			}
			return TCL_OK;
		} else if (strcmp(argv[1], "dump-page") == 0) {
			// Dump segments of a given page
			ClientPage *p=(ClientPage*)mpool()->get_page(argv[2]);
			if (p->type() != MEDIA)
				// Do nothing for non-media pages
				return TCL_OK;
			MediaPage *pg = (MediaPage *)p;
			char *buf;
			for (int i = 0; i < pg->num_layer(); i++) {
				buf = pg->print_layer(i);
				if (strlen(buf) > 0)
					log("E SEGS p %s l %d %s\n", argv[2], 
					    i, buf);
				delete []buf;
			}
			return TCL_OK;
		} else if (strcmp(argv[1], "stream-received") == 0) {
			// We've got the entire page, unlock it
			MediaPage *pg = (MediaPage*)mpool()->get_page(argv[2]);
			assert(pg != NULL);
			pg->unlock();
			// XXX Should we clear all "last" flag of segments??
#ifdef MCACHE_DEBUG
			// Printing out current buffer status of the page
			char *buf;
			for (int i = 0; i < pg->num_layer(); i++) {
				buf = pg->print_layer(i);
				log("E SEGS p %s l %d %s\n", argv[2], i, buf);
				delete []buf;
			}
#endif
			// Show cache free size
			log("E SIZ n %d z %d t %d\n", mpool()->num_pages(),
			    mpool()->usedsize(), mpool()->maxsize());
			return TCL_OK;
		}
	} else if (argc == 5) {
		if (strcmp(argv[1], "register-client") == 0) {
			// <server> register-client <app> <client> <pageid>
			TclObject *a = TclObject::lookup(argv[2]);
			assert(a != NULL);
			int newEntry;
			Tcl_HashEntry *he = Tcl_CreateHashEntry(cmap_, 
					(const char *)a, &newEntry);
			if (he == NULL) {
				tcl.add_errorf("cannot create hash entry");
				return TCL_ERROR;
			}
			if (!newEntry) {
				tcl.add_errorf("duplicate connection");
				return TCL_ERROR;
			}
			RegInfo *p = new RegInfo;
			p->client_ = (HttpApp*)TclObject::lookup(argv[3]);
			assert(p->client_ != NULL);
			strcpy(p->name_, argv[4]);
			Tcl_SetHashValue(he, (ClientData)p);

			// Lock the page while transmitting it to a client
			MediaPage *pg = (MediaPage*)mpool()->get_page(argv[4]);
			assert((pg != NULL) && (pg->type() == MEDIA));
			pg->tlock();

			return TCL_OK;
		} else if (strcmp(argv[1], "unregister-client") == 0) {
			// <server> unregister-client <app> <client> <pageid>
			TclObject *a = TclObject::lookup(argv[2]);
			assert(a != NULL);
			Tcl_HashEntry *he = 
				Tcl_FindHashEntry(cmap_, (const char*)a);
			if (he == NULL) {
				tcl.add_errorf("cannot find hash entry");
				return TCL_ERROR;
			}
			RegInfo *ri = (RegInfo*)Tcl_GetHashValue(he);
			// Update hit count
			mpool()->hc_update(argv[4], ri->hl_);
#ifdef MCACHE_DEBUG
			printf("Cache %d hit counts: \n", id_);
			mpool()->dump_hclist();
#endif
			// Dump per-connection statistics
			for (int i = 0; i <= ri->hl_; i++)
				log("E STAT p %s l %d d %d e %d p %d\n",
				    ri->name_, i, ri->db_[i], ri->eb_[i], 
				    ri->pb_[i]);
			delete ri;
			Tcl_DeleteHashEntry(he);

			// Lock the page while transmitting it to a client
			MediaPage *pg = (MediaPage*)mpool()->get_page(argv[4]);
			assert((pg != NULL) && (pg->type() == MEDIA));
			pg->tunlock();

			return TCL_OK;
		}
	}

	return HttpCache::command(argc, argv);
}



//----------------------------------------------------------------------
// Media web client 
//   Use C++ interface to records quality of received stream.
// NOTE: 
//   It has OTcl inheritance, but no C++ inheritance!
//----------------------------------------------------------------------

static class HttpMediaClientClass : public TclClass {
public:
	HttpMediaClientClass() : TclClass("Http/Client/Media") {}
	TclObject* create(int, const char*const*) {
		return (new MediaClient());
	}
} class_httpmediaclient;

// Records the quality of stream received
void MediaClient::process_data(int size, AppData* data)
{
	assert(data != NULL);

	switch (data->type()) {
	case MEDIA_DATA: {
		HttpMediaData* d = (HttpMediaData*)data;
		// XXX Don't pass any data to page pool!!
   		if (mpool()->add_segment(d->page(), d->layer(), 
   					 MediaSegment(*d)) == -1) {
   			fprintf(stderr, 
  "MediaCache %s gets a segment for an unknown page %s\n", name(), d->page());
//     			abort();
   		}
		// Note: we store the page only to produce some statistics
		// later so that we need not do postprocessing of traces.
#if 1
    		log("C RSEG p %s l %d s %d e %d z %d\n", 
    		    d->page(), d->layer(), d->st(), d->et(), d->datasize());
#endif
		break;
	}
	default:
		HttpClient::process_data(size, data);
	}
}

int MediaClient::command(int argc, const char*const* argv)
{
	if (argc == 3) {
		if (strcmp(argv[1], "stream-received") == 0) {
			// XXX This is the place to do statistics collection
			// about quality of received stream.
			// 
			// Dump delivered quality log
			MediaPage *pg = (MediaPage*)mpool()->get_page(argv[2]);
			assert(pg != NULL);
			// Printing out current buffer status of the page
			char *buf;
			for (int i = 0; i < pg->num_layer(); i++) {
				buf = pg->print_layer(i);
				if (strlen(buf) > 0) 
					log("C SEGS p %s l %d %s\n", 
					    argv[2], i, buf);
				delete []buf;
			}
			// then delete the stream from buffer
			mpool()->force_remove(argv[2]);
			return TCL_OK;
		}
	}
	return HttpClient::command(argc, argv);
}



//----------------------------------------------------------------------
// Multimedia web server
//----------------------------------------------------------------------

static class MediaServerClass : public TclClass {
public:
	MediaServerClass() : TclClass("Http/Server/Media") {}
	TclObject* create(int, const char*const*) {
		return (new MediaServer());
	}
} class_mediaserver;

MediaServer::MediaServer() : HttpServer() 
{
	pref_ = new Tcl_HashTable;
	Tcl_InitHashTable(pref_, 2);
	cmap_ = new Tcl_HashTable;
	Tcl_InitHashTable(cmap_, TCL_ONE_WORD_KEYS);
}

MediaServer::~MediaServer() 
{
	Tcl_HashEntry *he;
	Tcl_HashSearch hs;
	if (pref_ != NULL) {
		for (he = Tcl_FirstHashEntry(pref_, &hs);  he != NULL;
		     he = Tcl_NextHashEntry(&hs)) {
			PrefInfo *pi = (PrefInfo*)Tcl_GetHashValue(he);
			pi->sl_->destroy();
			delete pi->sl_;
		}
		Tcl_DeleteHashTable(pref_);
		delete pref_;
	}
	if (cmap_ != NULL) {
		for (he = Tcl_FirstHashEntry(cmap_, &hs);  he != NULL;
		     he = Tcl_NextHashEntry(&hs))
			delete (RegInfo*)Tcl_GetHashValue(he);
		Tcl_DeleteHashTable(cmap_);
		delete cmap_;
	}
}

// Return the next segment to be sent to a particular application
MediaSegment MediaServer::get_next_segment(MediaRequest *r, Application*& ci)
{
	MediaPage* pg = (MediaPage*)pool_->get_page(r->name());
	assert(pg != NULL);

	// XXX Extremely hacky way to map media app names to 
	// HTTP connections. Should maintain another hash table for this.
	RegInfo *ri = get_reginfo(r->app());
	assert(ri != NULL);
	PrefInfoQ* q = get_piq(r->name(), ri->client_);

	// We are not on the prefetching list, send a normal data segment
	if ((q == NULL) || (q->is_empty())) {
		MediaSegment s1(r->st(), r->et());
		return pg->next_overlap(r->layer(), s1);
	}

	// Cycle through the prefetched segments that we need to send
	int found = 0;
	int searched = 0;
	PrefInfo *pi; 
	while (!found) {
		PrefInfoE *pe = q->dequeue();
		pi = pe->data();
		q->enqueue(pe);
		// If there's a pending segment in any layer, send it
		for (int i = 0; i < pg->num_layer(); i++) 
			if (pi->sl_[i].length() > 0) 
				found = 1;
		// If no pending prefetched segments, return empty
		if (searched++ == q->size()) 
			return MediaSegment(0, 0);
	}

	// Send a segment from the prefetching list. Only use the data size
	// included in the request.
	MediaSegmentList *p = pi->sl_;
	// Set return conid
	ci = pi->conid_;

	// Find one available segment in prefetching list if there is none
	// in the given layer
	int l = r->layer(), i = 0;
	MediaSegment res;
	while ((res.datasize() == 0) && (i < pg->num_layer())) {
		// next() doesn't work. Need a method that returns the 
		// *FIRST* non-empty segment which satisfies the size 
		// constraint.
		res = p[l].get_nextseg(MediaSegment(0, r->datasize()));
		i++;
		l = (l+1) % pg->num_layer();
	}
	// XXX We must do boundary check of the prefetched segments to make
	// sure that the start and end offsets are valid!
	if (res.start() < 0) 
		res.set_start(0);
	if (res.end() > pg->layer_size(l))
		res.set_end(pg->layer_size(l));
	if (res.datasize() > 0) {
		// XXX We may end up getting data from another layer!!
		l = (l-1+pg->num_layer()) % pg->num_layer();
		if (l != r->layer())
			r->set_layer(l);
		// We may not be able to get the specified data size, due 
		// to arbitrary stream lengths
		//assert(res.datasize() == r->datasize());
		p[r->layer()].evict_head(r->datasize());
	}
	// Set the prefetching flag of this segment
	res.set_pref();
	return res;
}

// Similar to MediaCache::get_data(), but ignore segment availability checking
AppData* MediaServer::get_data(int& size, AppData *req)
{
	assert((req != NULL) && (req->type() == MEDIA_REQUEST));
	MediaRequest *r = (MediaRequest *)req;
	Application* conid = NULL;

	if (r->request() == MEDIAREQ_GETSEG) {
		// Get a new data segment
		MediaSegment s2 = get_next_segment(r, conid);
		HttpMediaData *p;
		if (s2.datasize() == 0) {
			// No more data available for this layer, most likely
			// it's because this layer is finished.
			size = 0;
			p = new HttpMediaData(name(), r->name(),
					      r->layer(), 0, 0);
		} else {
			size = s2.datasize();
			p = new HttpMediaData(name(), r->name(),
					   r->layer(), s2.start(), s2.end());
		}
		if (s2.is_last()) {
			p->set_last();
			// Tear down the connection after we've sent the last
			// segment of the base layer and are requested again.
			if ((s2.datasize() == 0) && (r->layer() == 0))
				p->set_finish();
		}
		if (s2.is_pref()) {
			// Add connection id into returned data
			p->set_conid(conid);
			p->set_pref();
		}
		return p;
	} else if (r->request() == MEDIAREQ_CHECKSEG) 
		// We don't need to return anything, so just NULL
		return NULL;
	else {
		fprintf(stderr, 
		       "MediaServer %s gets an unknown MediaRequest type %d\n",
			name(), r->request());
		abort();
	}
	/*NOTREACHED*/
	return NULL; // Make msvc happy
}

int MediaServer::command(int argc, const char*const* argv)
{
	Tcl& tcl = Tcl::instance();
	if (argc == 3) {
		if (strcmp(argv[1], "is-media-page") == 0) {
			ClientPage *pg = pool_->get_page(argv[2]);
			if (pg && (pg->type() == MEDIA))
				tcl.result("1");
			else 
				tcl.result("0");
			return TCL_OK;
		}
	} else if (argc == 5) { 
		if (strcmp(argv[1], "stop-prefetching") == 0) {
			/*
			 * <server> stop-prefetching <Client> <conid> <pagenum>
			 */
			TclObject *a = TclObject::lookup(argv[2]);
			assert(a != NULL);
			int tmp[2];
			tmp[0] = (int)a;
			tmp[1] = atoi(argv[4]);
			Tcl_HashEntry *he = 
				Tcl_FindHashEntry(pref_, (const char*)tmp);
			if (he == NULL) {
				tcl.add_errorf(
				  "Server %d cannot stop prefetching!\n", id_);
				return TCL_ERROR;
			}
			a = TclObject::lookup(argv[3]);
			assert(a != NULL);
			PrefInfoQ *q = (PrefInfoQ*)Tcl_GetHashValue(he);
			PrefInfoE *pe = find_prefinfo(q, (Application*)a);
			assert(pe != NULL);
			PrefInfo *pi = pe->data();
			MediaSegmentList *p = pi->sl_;
			assert(p != NULL);
			for (int i = 0; i < MAX_LAYER; i++)
				p[i].destroy();
			delete []p;
			delete pi;
			q->detach(pe);
			delete pe;
			// If no more prefetching streams left for this client,
			// delete all the information.
			// Return 0 means that we still have prefetching 
			// clients left, don't tear down the channel yet. 
			// Otherwise return 1. 
			int res = 0;
			if (q->is_empty()) {
				delete q;
				Tcl_DeleteHashEntry(he);
				res = 1;
			}
			tcl.resultf("%d", res);
			return (TCL_OK);
		} else if (strcmp(argv[1], "register-client") == 0) {
			// <cache> register-client <app> <client> <pageid>
			TclObject *a = TclObject::lookup(argv[2]);
			assert(a != NULL);
			int newEntry;
			Tcl_HashEntry *he = Tcl_CreateHashEntry(cmap_, 
					(const char *)a, &newEntry);
			if (he == NULL) {
				tcl.add_errorf("cannot create hash entry");
				return TCL_ERROR;
			}
			if (!newEntry) {
				tcl.add_errorf("duplicate connection");
				return TCL_ERROR;
			}
			RegInfo *p = new RegInfo;
			p->client_ = (HttpApp*)TclObject::lookup(argv[3]);
			assert(p->client_ != NULL);
			strcpy(p->name_, argv[4]);
			Tcl_SetHashValue(he, (ClientData)p);
			return TCL_OK;
		} else if (strcmp(argv[1], "unregister-client") == 0) {
			// <cache> unregister-client <app> <client> <pageid>
			TclObject *a = TclObject::lookup(argv[2]);
			assert(a != NULL);
			Tcl_HashEntry *he = 
				Tcl_FindHashEntry(cmap_, (const char*)a);
			if (he == NULL) {
				tcl.add_errorf("cannot find hash entry");
				return TCL_ERROR;
			}
			RegInfo *p = (RegInfo*)Tcl_GetHashValue(he);
			delete p;
			Tcl_DeleteHashEntry(he);
			return TCL_OK;
		}
	} else {
		if (strcmp(argv[1], "enter-page") == 0) {
			ClientPage *pg = pool_->enter_page(argc, argv);
			if (pg == NULL)
				return TCL_ERROR;
			if (pg->type() == MEDIA) 
				((MediaPage*)pg)->create();
			// Unlock the page after creation
			((MediaPage*)pg)->unlock(); 
			return TCL_OK;
		} else if (strcmp(argv[1], "register-prefetch") == 0) {
			/*
			 * <server> register-prefetch <client> <pagenum> 
			 * 	<conid> <layer> {<segments>}
			 * Registers a list of segments to be prefetched by 
			 * <client>, where each <segment> is a pair of 
			 * (start, end). <pagenum> should be pageid without 
			 * preceding [server:] prefix.
			 * 
			 * <conid> is the OTcl name of the original client 
			 * who requested the page. This is used for the cache
			 * to get statistics about a particular connection.
			 * 
			 * <client> is the requestor of the stream.
			 */
			TclObject *a = TclObject::lookup(argv[2]);
			assert(a != NULL);
			int newEntry = 1;
			int tmp[2];
			tmp[0] = (int)a;
			tmp[1] = atoi(argv[3]);
			// Map <cache_ptr><conid> to a pref entry
			Tcl_HashEntry *he = Tcl_CreateHashEntry(pref_, 
					(const char*)tmp, &newEntry);
			if (he == NULL) {
				fprintf(stderr, "Cannot create entry.\n");
				return TCL_ERROR;
			}
			PrefInfo *pi;
			PrefInfoE *pe;
			PrefInfoQ *q; 
			MediaSegmentList *p;
			a = TclObject::lookup(argv[4]);
			if (newEntry) {
				q = new PrefInfoQ;
				Tcl_SetHashValue(he, (ClientData)q);
				pe = NULL;
			} else {
				q = (PrefInfoQ *)Tcl_GetHashValue(he);
				pe = find_prefinfo(q, (Application*)a);
			}
			if (pe == NULL) {
				pi = new PrefInfo;
				pi->conid_ = (Application*)a;
				p = pi->sl_ = new MediaSegmentList[MAX_LAYER];
				q->enqueue(new PrefInfoE(pi));
			} else {
				pi = pe->data();
				p = pi->sl_;
			}
			assert((pi != NULL) && (p != NULL));
			// Preempt all old requests because they 
			// cannot reach the cache "in time"
			int layer = atoi(argv[5]);
			p[layer].destroy();
			// Add segments into prefetching list
			assert(argc % 2 == 0);
			for (int i = 6; i < argc; i+=2)
				p[layer].add(MediaSegment(atoi(argv[i]), 
							  atoi(argv[i+1])));
			return TCL_OK;
		}
	}
			
	return HttpServer::command(argc, argv);
}
