/*
 * Copyright (c) 2013, Coraid, Inc.
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of Coraid nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL CORAID BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <u.h>
#include <libc.h>
#include <thread.h>
#include <fcall.h>
#include <9p.h>
#include "dat.h"

static uvlong np2q, nq2m;
static int maxp2q, maxq2m;
static int p2qcoll, q2mcoll;

/* FNV hash */
static ulong
pathhash(char *path)
{
	uchar *p;
	ulong h;

	h = 2166136261UL;
	for(p = (uchar *)path; *p; ++p)
		h = (h ^ *p) * 16777619;
	return h % super.nht;
}

static ulong
qidhash(uvlong qpath)
{
	return qpath % super.nht;
}

static uvlong
qoffset(ulong bucket)
{
	return BlkSize * (super.nhashblk + 1) + bucket * sizeof(uvlong);
}

static PQMap *
nextpq(PQMap *pq)
{
	uchar *p;

	p = (uchar *)pq;
	p += pq->plen + offsetof(PQMap, pname[0]);
	return (PQMap *)p;
}

uvlong
p2q(int fd, char *path, int create)
{
	PQMap *pq, *pend;
	uchar *p;
	uvlong *uvp;
	uvlong hlist, next, qpath;
	ulong bucket;
	int plen, nsearch, n;

	++np2q;
	plen = strlen(path);
	bucket = pathhash(path);
	if(fd == -1)
		n = cread(&hlist, sizeof(uvlong), BlkSize + bucket * sizeof(uvlong));
	else
		n = spread(fd, &hlist, sizeof(uvlong), BlkSize + bucket * sizeof(uvlong));
	if(n < 0)
		sysfatal("cread failure: %r");
	if(hlist == 0) {
		if(create) {
			hlist = allocblock();
			if(hlist == 0)
				return 0;
			p = cbclean(hlist);
			pq = (PQMap *)p;
			qpath = super.qgen++ | ((uvlong)TFile << 60);
			pq->qpath = qpath;
			pq->plen = plen;
			memmove(pq->pname, path, plen);
			cbwrite(hlist);
			brelease(hlist);
			uvp = cbread(bucket / NPerBlk + 1);
			uvp[bucket % NPerBlk] = hlist;
			cbwrite(bucket / NPerBlk + 1);
			brelease(bucket / NPerBlk + 1);
			return qpath;
		}
		return 0;
	}
	nsearch = 1;
	p = nil;	/* make the compiler happy */
	if(fd != -1)
		p = θmalloc(BlkSize);
	while(hlist) {
		if(fd == -1) {
			p = cbread(hlist);
			if(p == nil) {
				fprint(2, "cbread failed on block %ulld\n", hlist);
				return 0;
			}
		}
		else
			spread(fd, p, BlkSize, hlist * BlkSize);
		pend = (PQMap *)(p + BlkSize);
		--pend;
		for(pq = (PQMap *)p; pq < pend && pq->qpath != 0; pq = nextpq(pq)) {
			if(plen == pq->plen && memcmp(path, pq->pname, plen) == 0)
				goto found;
			++nsearch;
		}
		next = *((uvlong *)(p + BlkSize - sizeof(uvlong)));
		if(next == 0 && create)
			goto addone;
		if(fd == -1)
			brelease(hlist);
		hlist = next;
	}
	if(fd != -1)
		free(p);
	return 0;
found:
	if(nsearch > maxp2q)
		maxp2q = nsearch;
	next = pq->qpath;
	if(fd == -1)
		brelease(hlist);
	else
		free(p);
	if(create)
		return 0;
	return next;
addone:
	for(pq = (PQMap *)p; pq < pend && pq->qpath != 0; pq = nextpq(pq)) ;
	if(pq != (PQMap *)p)
		++p2qcoll;
	if(pq >= pend) {
fprint(2, "HUH?");
		next = allocblock();
		if(next == 0)
			return 0;
		*((uvlong *)(p + BlkSize - sizeof(uvlong))) = next;
		cbwrite(hlist);
		brelease(hlist);
		hlist = next;
		p = cbclean(hlist);
		pq = (PQMap *)p;
	}
	qpath = super.qgen++ | ((uvlong)TFile << 60);
	pq->qpath = qpath;
	pq->plen = plen;
	memmove(pq->pname, path, plen);
	if(hlist != 0) {		/* shouldn't be possible, but just to be safe */
		cbwrite(hlist);
		brelease(hlist);
	}
	return qpath;
}

void
setqhash(uvlong qpath, uvlong midx)
{
	ulong bucket;

	bucket = qidhash(qpath);
	cwrite(&midx, sizeof(uvlong), qoffset(bucket));
}

uvlong
q2m(int fd, uvlong qpath, int create)
{
	uvlong val;
	uvlong first, meta;
	ulong bucket;
	int nsearch, n;

	if(qpath == 0)
		return 0;
	++nq2m;
	bucket = qidhash(qpath);
	if(fd == -1)
		n = cread(&first, sizeof(uvlong), qoffset(bucket));
	else
		n= spread(fd, &first, sizeof(uvlong), qoffset(bucket));
	if(n < 0)
		sysfatal("cread failure: %r");
	if(first == 0) {
		if(create) {
			meta = setmetaint(0, "qhnext", nil, 0);
			//setqhash(qpath, meta);
			return meta;
		}
		return 0;
	}
	nsearch = 1;
	for(meta = first; meta; ) {
		if(getmetaint(fd, meta, "qpath", &val) != MTnone && val == qpath)
			break;
		if(getmetaint(fd, meta, "qhnext", &meta) == MTnone)
			meta = 0;
		++nsearch;
	}
	if(meta == 0) {
		if(create) {
			meta = setmetaint(0, "qhnext", nil, first);
			//setqhash(qpath, meta);
		}
	}
	else
		if(nsearch > maxq2m)
			maxq2m = nsearch;
	return meta;
}

void
rehashone(uvlong qpath, char *from, char *to)
{
	PQMap *pq, *rend;
	uchar *p;
	uvlong *uvp;
	uvlong hlist, next;
	ulong bucket;
	int plen;

	rmp(from);
	plen = strlen(to);
	bucket = pathhash(to);
	if(cread(&hlist, sizeof(uvlong), BlkSize + bucket * sizeof(uvlong)) < 0)
		sysfatal("cread failure: %r");
	if(hlist == 0) {
		hlist = allocblock();
		if(hlist == 0)
			return;
		p = cbclean(hlist);
		pq = (PQMap *)p;
		pq->qpath = qpath;
		pq->plen = plen;
		memmove(pq->pname, to, plen);
		cbwrite(hlist);
		brelease(hlist);
		uvp = cbread(bucket / NPerBlk + 1);
		uvp[bucket % NPerBlk] = hlist;
		cbwrite(bucket / NPerBlk + 1);
		brelease(bucket / NPerBlk + 1);
		return;
	}
	while(hlist) {
		p = cbread(hlist);
		rend = (PQMap *)(p + BlkSize);
		--rend;
		for(pq = (PQMap *)p; pq < rend; pq = nextpq(pq))
			if(plen == pq->plen && memcmp(to, pq->pname, plen) == 0)
				goto found;
		next = *((uvlong *)(p + BlkSize - sizeof(uvlong)));
		if(next == 0)
			goto addone;
		brelease(hlist);
		hlist = next;
	}
	return;
found:
	fprint(2, "Impossible! Repath destination exists\n");
	brelease(hlist);
	return;
addone:
	for(pq = (PQMap *)p; pq < rend && pq->qpath != 0; pq = nextpq(pq)) ;
	if(pq >= rend) {
		next = allocblock();
		*((uvlong *)(p + BlkSize - sizeof(uvlong))) = next;
		cbwrite(hlist);
		brelease(hlist);
		if(next == 0)
			return;
		hlist = next;
		p = cbclean(hlist);
		pq = (PQMap *)p;
	}
	pq->qpath = qpath;
	pq->plen = plen;
	memmove(pq->pname, to, plen);
	cbwrite(hlist);
	brelease(hlist);
}

void
rehashpath(uvlong qpath, char *from, char *to)
{
	char *f, *t, *name;
	uvlong cqid, meta;

	meta = q2m(-1, qpath, 0);
	if(meta != 0 && getmetaint(-1, meta, "child", &cqid) != MTnone) {
		while(cqid != 0) {
			meta = q2m(-1, cqid, 0);
			if(meta == 0)
				break;
			name = getmetastr(-1, meta, "name");
			f = smprint("%s/%s", from, name);
			t = smprint("%s/%s", to, name);
			free(name);
			rehashpath(cqid, f, t);
			free(f);
			free(t);
			if(getmetaint(-1, meta, "sib", &cqid) == MTnone)
				break;
		}
	}
	rehashone(qpath, from, to);
}

static PQMap *
rmpath(PQMap *full, PQMap *victim)
{
	PQMap *next, *last;
	PQMap *rend;
	int plen;

	rend = (PQMap *)((char *)full + BlkSize - sizeof(uvlong));
	for(last = victim; last < rend - 1 && last->plen > 0; last = nextpq(last)) ;
	/*
	 * last now points to the start of the first empty path/qid map slot
	 */
	plen = victim->plen + offsetof(PQMap, pname[0]);
	next = nextpq(victim);
	memmove(victim, next, (char *)rend - (char *)next);
	/*
	 * now last has moved up by plen bytes
	 */
	last = (PQMap *)((char *)last - plen);
	memset(last, 0, (char *)rend - (char *)last);
	return last;
}

void
rmp(char *path)
{
	PQMap *pq, *rend, *last;
	uchar *p;
	uvlong hlist, next;
	ulong bucket;
	int plen;

	plen = strlen(path);
	if(plen == 0)
		return;
	bucket = pathhash(path);
	if(cread(&hlist, sizeof(uvlong), BlkSize + bucket * sizeof(uvlong)) < 0)
		sysfatal("cread failure: %r");
	while(hlist) {
		p = cbread(hlist);
		rend = (PQMap *)(p + BlkSize);
		--rend;
		for(pq = (PQMap *)p; pq < rend; pq = nextpq(pq))
			if(plen == pq->plen && memcmp(path, pq->pname, plen) == 0)
				goto found;
		next = *((uvlong *)(p + BlkSize - sizeof(uvlong)));
		brelease(hlist);
		hlist = next;
	}
	return;
found:
	while(hlist) {
		last = rmpath((PQMap *)p, pq);
		next = *((uvlong *)(p + BlkSize - sizeof(uvlong)));
		if(next != 0) {
			p = cbread(next);
			pq = (PQMap *)p;
			if(pq->plen == 0 || pq->plen > (char *)rend - (char *)last) {
				brelease(next);
				next = 0;
			}
			else
				memmove(last, pq, pq->plen + offsetof(PQMap, pname[0]));
		}
		cbwrite(hlist);
		brelease(hlist);
		hlist = next;
	}
}

void
rmq(uvlong qpath, uvlong victim)
{
	uvlong prev, meta, next;
	ulong bucket;

	if(qpath == 0)
		return;
	bucket = qidhash(qpath);
	if(cread(&meta, sizeof(uvlong), qoffset(bucket)) < 0)
		sysfatal("cread failure: %r");
	if(meta == victim) {
		if(getmetaint(-1, meta, "qhnext", &next) == MTnone)
			next = 0;
		if(cwrite(&next, sizeof(uvlong), qoffset(bucket)) < 0)
			sysfatal("cwrite failure: %r");
		return;
	}
	for(prev = meta; prev; ) {
		if(getmetaint(-1, prev, "qhnext", &meta) == MTnone)
			meta = 0;
		if(meta == victim) {
			if(getmetaint(-1, victim, "qhnext", &next) == MTnone)
				next = 0;
			setmetaint(prev, "qhnext", nil, next);
			return;
		}
		prev = meta;		
	}
}

static char hstatbuf[1024];

char *
prhstat(void)
{
	char *p, *e;

	p = hstatbuf;
	e = p + nelem(hstatbuf);
	p = seprint(p, e, "Hash stats:\n");
	p = seprint(p, e, "np2q: %ulld\n", np2q);
	p = seprint(p, e, "p2qcoll: %ud\n", p2qcoll);
	p = seprint(p, e, "maxp2q: %ud\n", maxp2q);
	p = seprint(p, e, "nq2m: %ulld\n", nq2m);
	p = seprint(p, e, "q2mcoll: %ud\n", q2mcoll);
	seprint(p, e, "maxq2m: %ud\n", maxq2m);
	return hstatbuf;
}

void
showphash(int fd, char *path)
{
	uvlong hlist;
	ulong bucket;

	bucket = pathhash(path);
	cread(&hlist, sizeof(uvlong), BlkSize + bucket * sizeof(uvlong));
	fprint(fd, "%s: bucket:%uld hlist:%ulld\n", path, bucket, hlist);
}

void
fixpaths(int fd)
{
	PQMap *pq, *pend;
	uvlong *hb;
	uchar *p;
	char *path;
	uvlong hlist, next;
	ulong bucket;
	int i, j;

	fprint(fd, "Checking for dangling path names\n");
	for(bucket = 0, i = 0; i < super.nhashblk; ++i) {
		hb = cbread(i + 1);
		for(j = 0; j < BlkSize / sizeof(uvlong) && bucket < super.nht; ++j, ++bucket) {
			if(bucket % 100000 == 0)
				fprint(fd, ".");
restart:
			hlist = hb[j];
			while(hlist) {
				p = cbread(hlist);
				if(p == nil) {
					fprint(fd, "hlist block read failure in fixpaths\n");
					return;
				}
				pend = (PQMap *)(p + BlkSize);
				--pend;
				for(pq = (PQMap *)p; pq < pend && pq->qpath != 0; pq = nextpq(pq)) {
					if(q2m(-1, pq->qpath, 0) == 0) {
						path = θmalloc(pq->plen + 1);
						memmove(path, pq->pname, pq->plen);
						fprint(fd, "removing dangling path %s\n", path);
						rmp(path);
						free(path);
						brelease(hlist);
						goto restart;
					}
				}
				next = *((uvlong *)(p + BlkSize - sizeof(uvlong)));
				brelease(hlist);
				hlist = next;
			}
		}
		brelease(i + 1);
	}
}