/* -*- linux-c -*- --------------------------------------------------------- *
 *
 * linux/fs/autofs/inodehash.c
 *
 *  Copyright 1997 Transmeta Corporation -- All Rights Reserved
 *
 * This file is part of the Linux kernel and is made available under
 * the terms of the GNU General Public License, version 2, or at your
 * option, any later version, incorporated herein by reference.
 *
 * ------------------------------------------------------------------------- */

#include "autofs_i.h"

void vfree(const void * addr);
void * vmalloc(unsigned long size);


struct inode_hash {
	ino_t ino;
	struct dentry *dent;
};

struct inode_hash_tbl {
	int entries;
	int maxent;		/* Highest entry number = max entries - 1 */
	int shiftcnt;
	struct inode_hash *hash;
	void (*free)(const void *);
};

#define AUTOFS_MIN_INO_HASH_SIZE  6  /*  2^6 entries minimum */
#define AUTOFS_MAX_INO_HASH_SIZE 20  /* 2^20 entries maximum */ 

static int autofs_rehash(struct inode_hash_tbl *tbl, int nshift)
{
	void (*nfree)(const void *);
	struct inode_hash *nhash;
	int nmax = 1 << nshift;
	int i, ep, step;
	ino_t ino;
	
	if ( tbl->entries > nmax )
		return -1;	/* Can't fit all entries in that size table */

	nhash = kmalloc(GFP_KERNEL, nmax*sizeof(struct inode_hash));
	if ( nhash ) {
		nfree = kfree;
	} else {
		if ( nmax > PAGE_SIZE/sizeof(struct inode_hash) ) {
			nhash = vmalloc(nmax*sizeof(struct inode_hash));
			if ( !nhash )
				return -1;
			nfree = vfree;
		} else
			return -1;
	}

	memset(nhash, 0, nmax*sizeof(struct inode_hash));
	nmax--;			/* Make maximum value (= mask), not count */

	for ( i = 0 ; i <= tbl->maxent ; i++ ) {
		if ( (ino = tbl->hash[i].ino) ) {
			ep = ino & nmax;
			step = (ino ^ (ino >> (nshift-1))) | 1;
			while ( nhash[ep].ino )
				ep = (ep+step) & nmax;
			nhash[ep].ino = ino;
			nhash[ep].dent = tbl->hash[i].dent;
		}
	}

	tbl->free(tbl->hash);

	tbl->maxent = nmax;
	tbl->shiftcnt = nshift;
	tbl->hash = nhash;
	tbl->free = nfree;

	return 0;
}

static inline int autofs_grow_hash(struct inode_hash_tbl *tbl)
{
	return autofs_rehash(tbl,tbl->shiftcnt+1);
}

static inline int autofs_shrink_hash(struct inode_hash_tbl *tbl)
{
	return autofs_rehash(tbl,tbl->shiftcnt-1);
}

int autofs_ino_hash_insert(struct inode_hash_tbl *tbl,
			   struct dentry *dent, ino_t ino)
{
	int ep, step;

	if ( tbl->entries > tbl->maxent )
		if ( tbl->shiftcnt >= AUTOFS_MAX_INO_HASH_SIZE ||
		     autofs_grow_hash(tbl) )
			return -1;
	
	ep = ino & tbl->maxent;
	step = (ino ^ (ino >> (tbl->shiftcnt-1))) | 1; /* Always odd */

	/* step is always odd and the size of the table is 2^n, so we will
	   always seek the whole list */
	while ( tbl->hash[ep].ino )
		ep = (ep+step) & tbl->maxent;

	tbl->hash[ep].ino  = ino;
	tbl->hash[ep].dent = dent;
	tbl->entries++;

	return 0;
}

int autofs_ino_hash_remove(struct inode_hash_tbl *tbl, ino_t ino)
{
	int ep, ep1, ep0, step;

	ep = ep0 = ino & tbl->maxent;
	step = (ino ^ (ino >> (tbl->shiftcnt-1))) | 1;

	while ( tbl->hash[ep].ino != ino ) {
		ep = (ep+step) & tbl->maxent;
		if ( ep == ep0 )
			return -1;
	}
	
	ep1 = (ep+step) & tbl->maxent;

	/* Compact the hash chain */
	while ( tbl->hash[ep1].ino && ep1 != ep0 ) {
		if ( (tbl->hash[ep1].ino & tbl->maxent) == ep0 ) {
			tbl->hash[ep] = tbl->hash[ep1];
			ep = ep1;
		}
		ep1 = (ep1+step) & tbl->maxent;
	}

	tbl->hash[ep].ino  = 0;
	tbl->hash[ep].dent = NULL;
	tbl->entries--;

	if ( tbl->shiftcnt > AUTOFS_MIN_INO_HASH_SIZE &&
	     tbl->entries <= (tbl->maxent >> 2) )
		autofs_shrink_hash(tbl);

	return 0;
}

struct dentry *autofs_ino_hash_lookup(struct inode_hash_tbl *tbl, ino_t ino)
{
	int ep, ep0, step;

	ep = ep0 = ino & tbl->maxent;
	step = (ino ^ (ino >> (tbl->shiftcnt-1))) | 1;

	while ( tbl->hash[ep].ino && tbl->hash[ep].ino != ino ) {
		ep = (ep+step) & tbl->maxent;
		if ( ep == ep0 )
			return NULL; /* Not found */
	}
	return tbl->hash[ep].dent;
}