/* ARISA - Nick Hashing
 * Copyright (C) 2003, 2004 Carl Ritson
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * 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 "arisa.h"
#include <ctype.h>

#define INIT_SIZE 	4
#define SHRINK_RATIO 	4
#define CHAIN_LIMIT	48
#define SIZE_CAP	8192


int mode_from_char(char c) {
	switch (c) {
		case '@': case 'o': return MODE_OP;
		case '+': case 'v': return MODE_VOICE;
		case '%': case 'h': return MODE_HOP;
		case '&': case 'a': return MODE_ANTIKICK;
		case '~': case 'q': return MODE_OWNER;
		case ' ': return MODE_REG;
		default:
			  return MODE_UNKNOWN;
	}
}

int mode_from_str(const char *str) {
	int mode = 0;
	if(str == NULL)
		return MODE_UNKNOWN;
	while(*str != '\0')
		mode |= mode_from_char(*(str++));
	return mode;
}

char *str_from_mode(char *buffer, size_t bufsize, int mode) {
	int i = 0;

	if(buffer == NULL || bufsize == 0)
		return NULL;
	
	if((mode & MODE_OWNER) && i < (bufsize - 1))
		buffer[i++] = 'q';
	if((mode & MODE_ANTIKICK) && i < (bufsize - 1))
		buffer[i++] = 'a';
	if((mode & MODE_OP) && i < (bufsize - 1))
		buffer[i++] = 'o';
	if((mode & MODE_VOICE) && i < (bufsize - 1))
		buffer[i++] = 'v';
	if((mode & MODE_HOP) && i < (bufsize - 1))
		buffer[i++] = 'h';

	buffer[i] = '\0';

	return buffer;
}	

static unsigned long nickhash_hash(const char *nick) {
	unsigned long hash = 0;
	int i;
	
	assert(nick != NULL);
	
	for(i = 0; nick[i] != '\0'; ++i) {
		hash = hash * 37UL + (unsigned long) irc_tolower(nick[i]);
	}
	
	return hash;
}

nickhash_t *nickhash_init(void) {
	nickhash_t *ht = xalloc(sizeof(nickhash_t));
	unsigned int i;
	
	LOCK_INIT(&(ht->lock));
	
	ht->table 	= xalloc(sizeof(nh_bucket_t *) * INIT_SIZE);
	ht->size 	= INIT_SIZE;
	ht->no_buckets 	= 0;
	for(i = 0; i < ht->size; ++i) {
		ht->table[i] = NULL;
	}

	return ht;
}

static nh_bucket_t *init_bucket(unsigned long hash, const char *nick) {
	nh_bucket_t *b = xalloc(sizeof(nh_bucket_t));
	b->hash 	= hash;
	b->nick 	= xstrdup(nick);
	b->cms 		= NULL;
	b->no_cms	= 0;
	b->next		= NULL;
	return b;
}

static void free_bucket(nh_bucket_t *b) {
	xfree(b->nick);
	if(b->cms != NULL)
		xfree(b->cms);
	xfree(b);
}

//static void bucket_log(nh_bucket_t *b);

static void bucket_channel_add(nh_bucket_t *b, channel_t *chan, int mode) {
	int i;
	
	//bucket_log(b);
	
	if(chan == NULL)
		return;
	
	for(i = 0; i < b->no_cms; ++i) {
		if(b->cms[i].channel == chan) {
			b->cms[i].mode = mode;
			return;
		}
	}
	
	b->no_cms++;
	b->cms = xreloc(b->cms,sizeof(chanmode_t)*b->no_cms);
	b->cms[b->no_cms-1].channel	= chan;
	b->cms[b->no_cms-1].mode	= mode;

	//bucket_log(b);
}

static void bucket_channel_del(nh_bucket_t *b, channel_t *chan) {
	int i;
	
	//bucket_log(b);
	
	for(i = 0; i < b->no_cms; ++i) {
		if(b->cms[i].channel == chan)
			break;
	}

	if(i < b->no_cms) {
		for(i++; i < b->no_cms; ++i) {
			b->cms[i-1].channel = b->cms[i].channel;
			b->cms[i-1].mode = b->cms[i].mode;
		}
		b->no_cms--;
		b->cms = xreloc(b->cms,sizeof(chanmode_t)*(b->no_cms+1));
	}
	
	//bucket_log(b);
}

static void bucket_log(nh_bucket_t *b) {
	int i;
	
	if(b == NULL)
		return;

	D("(%p) hash: %lu, nick: %s, no_cms: %d",b,b->hash,b->nick,b->no_cms);
	for(i = 0; i < b->no_cms; ++i) {
		// FIXME: bad evil evil evil, debug stuff! bad lock, dame yo!
		LOCK(b->cms[i].channel);
		D("cms[%d] = name:%s, mode:%d",
				i,b->cms[i].channel->name,b->cms[i].mode);
		UNLOCK(b->cms[i].channel);
	}
}

void nickhash_flush(nickhash_t *ht) {
	nh_bucket_t *b = NULL, *p = NULL;
	unsigned int i;

	LOCK(ht);
	for(i = 0; i < ht->size; ++i) {
		for(p = ht->table[i]; p != NULL; p = b) {
			b = p->next;
			free_bucket(p);
		}
		ht->table[i] = NULL;
	}
	ht->no_buckets = 0;
	UNLOCK(ht);
}

void nickhash_free(nickhash_t *ht) {
	nickhash_flush(ht);
	LOCK_FREE(&(ht->lock));
	xfree(ht->table);
	xfree(ht);
}

/* lock assumed */
static int nickhash_place(nickhash_t *ht, nh_bucket_t *b, 
		nh_bucket_t **hint, nh_bucket_t **dup) {
	nh_bucket_t *p = ht->table[b->hash % ht->size];
	int depth = 0;
	
	b->next = NULL;
	
	if(hint != NULL) {
		if(*hint == NULL)
			ht->table[b->hash % ht->size] = b;
		else
			(*hint)->next = b;
		return 0;
	}
	
	if(p == NULL) {
		ht->table[b->hash % ht->size] = b;
	} else {
		for(;;) {
			depth++;
			if(irc_strcasecmp(p->nick,b->nick) == 0) {
				if(dup != NULL)
					*dup = p;
				return -1;
			}
			if(p->next != NULL)
				p = p->next;
			else
				break;
		}
		p->next = b;
	}
	
	//D("%p, depth:%d",b,depth);
	return depth;
}

/* lock assumed */
static nh_bucket_t *nickhash_find(nickhash_t *ht, const char *nick,
						nh_bucket_t **prev) {
	nh_bucket_t *b = NULL;
	unsigned long hash;
	
	if(nick == NULL)
		return NULL;
	
	hash = nickhash_hash(nick);
	b = ht->table[hash % ht->size];
	if(prev != NULL)
		*prev = NULL;
	while(b != NULL) {
		if(irc_strcasecmp(b->nick,nick) == 0)
			break;
		if(prev != NULL)
			*prev = b;
		b = b->next;
	}
	
	//D("return %p",b);
	return b;
}

/* lock assumed */
static void nickhash_resize(nickhash_t *ht, unsigned int new_size) {
	nh_bucket_t **old_table	= ht->table;
	unsigned int old_size	= ht->size;
	unsigned int i;
	int bkt_seen = 0, bkt_known = ht->no_buckets;
	nh_bucket_t *b = NULL, *p = NULL;
	
	if(new_size > SIZE_CAP || new_size < INIT_SIZE || new_size == old_size)
		return;

	//D("%d -> %d",ht->size,new_size);
	
	ht->size  = new_size;
	ht->table = xalloc(sizeof(nh_bucket_t *)*ht->size);
	for(i = 0; i < ht->size; ++i)
		ht->table[i] = NULL;

	for(i = 0; i < old_size; ++i) {
		if(old_table[i] == NULL)
			continue;
		for(p = old_table[i]; p != NULL; p = b) {
			b = p->next;
			if(nickhash_place(ht,p,NULL,NULL) == -1) {
				free_bucket(p);
				ht->no_buckets--;
			}
			bkt_seen++;
		}
	}
	//D("resize saw %d of %d buckets, lost %d buckets",
	//		bkt_seen,bkt_known,bkt_known - ht->no_buckets);
	
	xfree(old_table);
}

int nickhash_present_mode(nickhash_t *ht, channel_t *chan,
			const char *nick, int *mode) {
	nh_bucket_t *b = NULL;
	int i,ret = 0;
	
	//D("ht:%p, chan:%p, nick:\"%s\"",ht,chan,nick);
	
	assert(ht != NULL);
	if(nick == NULL)
		return 0;
	
	LOCK(ht);
	b = nickhash_find(ht,nick,NULL);
	if(b != NULL) {
		//D("found %s",nick);
		if(chan == NULL) {
			ret = 1;
		} else {
			for(i = 0; i < b->no_cms && ret == 0; ++i) {
				if(b->cms[i].channel == chan) {
					if(mode != NULL)
						*mode = b->cms[i].mode;
					ret = 1;
				}
			}
		}
		//if(ret == 0)
		//	bucket_log(b);
	}
	UNLOCK(ht);

	//D("ret: %d",ret);
	return ret;
}

int nickhash_present(nickhash_t *ht, channel_t *chan, const char *nick) {
	return nickhash_present_mode(ht,chan,nick,NULL);
}

void nickhash_add_mode(nickhash_t *ht, channel_t *chan, 
				const char *nick, int mode) {
	nh_bucket_t *p = NULL, *hint;
	int depth = 0;
	
	//D("ht:%p(%d), chan:%p, nick:\"%s\", mode:%d",
	//		ht,ht->no_buckets,chan,nick,mode);
	
	assert(ht != NULL);
	if(nick == NULL)
		return;

	LOCK(ht);
	if((p = nickhash_find(ht,nick,&hint)) == NULL) {
		p = init_bucket(nickhash_hash(nick),nick);
		depth = nickhash_place(ht,p,&hint,NULL);
		assert(depth != -1); // we ran a find, there should be no dup
		ht->no_buckets++;
	}
		
	if(chan != NULL)
		bucket_channel_add(p,chan,mode);
	
	if(depth > CHAIN_LIMIT || (ht->size * SHRINK_RATIO) < ht->no_buckets)
		nickhash_resize(ht,ht->size * 2);
	UNLOCK(ht);
}

void nickhash_add(nickhash_t *ht, channel_t *chan, const char *nick) {
	nickhash_add_mode(ht,chan,nick,MODE_UNKNOWN);
}

static void nickhash_cull(nickhash_t *ht, nh_bucket_t *b, nh_bucket_t *prev) {
	if(prev != NULL)
		prev->next = b->next;
	else
		ht->table[b->hash % ht->size] = b->next;
	
	//D("cull %p",b);
	//bucket_log(b);
	
	ht->no_buckets--;
	free_bucket(b);
}

void nickhash_del(nickhash_t *ht, channel_t *chan, const char *nick) {
	nh_bucket_t *b = NULL, *p = NULL;

	//D("ht:%p, chan:%p, nick:\"%s\"",ht,chan,nick);
	
	assert(ht != NULL);
	if(nick == NULL)
		return;

	LOCK(ht);
	b = nickhash_find(ht,nick,&p);
	if(b != NULL) {
		if(chan != NULL)
			bucket_channel_del(b,chan);
		if(chan == NULL || b->no_cms == 0)
			nickhash_cull(ht,b,p);
	} else
		//D("not found");

	if(ht->size > (ht->no_buckets * SHRINK_RATIO))
		nickhash_resize(ht,ht->size / 2);
	UNLOCK(ht);
}

void nickhash_flush_channel(nickhash_t *ht, channel_t *chan) {
	nh_bucket_t *b,*p,*n;
	unsigned int i;
	
	//D("ht:%p, chan:%p",ht,chan);
	
	assert(ht != NULL);
	if(chan == NULL)
		return;

	LOCK(ht);
	for(i = 0; i < ht->size; ++i) {
		if(ht->table[i] != NULL) {
			p = NULL; n = NULL;
			for(b = ht->table[i]; b != NULL; p = b, b = n) {
				n = b->next;
				bucket_channel_del(b,chan);
				if(b->no_cms == 0) {
					nickhash_cull(ht,b,p);
					b = p;
				}
			}
		}
	}

	if(ht->size > (ht->no_buckets * SHRINK_RATIO))
		nickhash_resize(ht,ht->size / 2);
	UNLOCK(ht);
}

void nickhash_rename(nickhash_t *ht, const char *onick, const char *nnick) {
	nh_bucket_t *b = NULL,*p = NULL;
	unsigned long nhash;
	int add = 0;
	
	//D("ht:%p, onick:\"%s\", nnick:\"%s\"",ht,onick,nnick);
	
	assert(ht != NULL);
	if(onick == NULL || nnick == NULL)
		return;

	nhash = nickhash_hash(nnick);

	LOCK(ht);
	b = nickhash_find(ht,onick,&p);
	if(b != NULL) {
		if(p != NULL)
			p->next = b->next;
		else
			ht->table[b->hash % ht->size] = b->next;
		xfree(b->nick);
		b->nick = xstrdup(nnick);
		b->hash = nhash;
		if(nickhash_place(ht,b,NULL,NULL) == -1) { // failure
			free_bucket(b);
			ht->no_buckets--;
		} 
	} else
		add = 1;
	UNLOCK(ht);
	
	if(add)
		nickhash_add(ht,NULL,nnick);
}

void nickhash_change_mode(nickhash_t *ht, channel_t *chan, 
			const char *nick, int op, int mask) {
	nh_bucket_t *b = NULL;
	int pmask,add = 0;

	assert(ht != NULL);
	if(nick == NULL || chan == NULL)
		return;
	
	if(op == MODE_ADD) {
		pmask = (unsigned int)-1;
	} else if(op == MODE_DEL) {
		pmask = ~mask;
		mask = 0x0;
	} else if(op == MODE_SET) {
		pmask = 0x0;
	} else {
		pmask = (unsigned int)-1;
		mask = 0x0;
	}

	LOCK(ht);
	b = nickhash_find(ht,nick,NULL);
	if(b != NULL) {
		int i,found;
		for(i = 0, found = 0; i < b->no_cms && !found; ++i) {
			if(b->cms[i].channel == chan) {
				b->cms[i].mode =
					(b->cms[i].mode & pmask) | mask;
				found = 1;
			}
		}
		if(!found)
			bucket_channel_add(b,chan,
					(MODE_UNKNOWN & pmask) | mask);
	} else
		add = 1;
	UNLOCK(ht);

	if(add)
		nickhash_add_mode(ht,chan,nick,(MODE_UNKNOWN & pmask) | mask);
}

int nickhash_highest_mode(nickhash_t *ht, const char *nick) {
	nh_bucket_t *b;
	int i,mode = 0;
	
	LOCK(ht);
	b = nickhash_find(ht,nick,NULL);
	if(b != NULL) {
		for(i = 0; i < b->no_cms; ++i) {
			if(b->cms[i].mode > mode)
				mode = b->cms[i].mode;
		}
	}
	UNLOCK(ht);

	return mode;
}

int nickhash_query_nick(nickhash_t *ht, const char *nick, chanmode_t **cms) {
	nh_bucket_t *b;
	int ret = -1;

	*cms = NULL;
	
	LOCK(ht);
	b = nickhash_find(ht,nick,NULL);
	if(b != NULL) {
		ret = b->no_cms;
		if(b->no_cms > 0) {
			*cms = xalloc(sizeof(chanmode_t) * b->no_cms);
			memcpy(*cms,b->cms,sizeof(chanmode_t) * b->no_cms);
		}
	}
	UNLOCK(ht);

	return ret;
}

int nickhash_query_channel(nickhash_t *ht, channel_t *chan, nickmode_t **nms) {
	nh_bucket_t *b;
	pqueue_t bkts;
	size_t bytes = 0;
	char *heap = NULL;
	int i,j,found,ret,tmp;

	pqueue_init(&bkts,0);
	
	LOCK(ht);
	for(i = 0; i < ht->size; ++i) {
		b = ht->table[i];
		while(b != NULL) {
			for(j = 0, found = 0; j < b->no_cms && !found; ++j) {
				if(b->cms[j].channel == chan) {
					pqueue_push_back(&bkts,b);
					bytes += strlen(b->nick) + 
						sizeof(nickmode_t) + 1;
					found = 1;
				}
			}
			b = b->next;
		}
	}
	
	i	= 0;
	ret	= pqueue_length(&bkts);
	if(ret > 0) {
		*nms	= xalloc(bytes);
		heap	= ((char *)(*nms)) + (sizeof(nickmode_t) * ret);
	} else {
		*nms	= NULL;
	}
	while((b = pqueue_pop_front(&bkts)) != NULL) {
		for(j = 0, found = -1; j < b->no_cms && found == -1; ++j) {
			if(b->cms[j].channel == chan)
				found = j;
		}
		assert(found >= 0);
		
		tmp = strlen(b->nick);
		(*nms)[i].nick = heap;
		(*nms)[i].mode = b->cms[found].mode;
		
		xstrncpy((*nms)[i].nick,b->nick,tmp+1);
		heap += tmp + 1;
		
		i++;
	}
	UNLOCK(ht);

	return ret;
}