/* This file is part of vmod_dict.
   Copyright (C) 2017-2020 Sergey Poznyakoff
   
   Vmod_dict 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 3, or (at your option)
   any later version.
   
   Vmod_dict 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 vmod_dict.  If not, see <http://www.gnu.org/licenses/>.
*/
#include <config.h>
#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <limits.h>
#include <ctype.h>
#include <syslog.h>
#include <cache/cache.h>
#include <vcl.h>
#include <vcc_if.h>

#ifdef VPFX
# define VEVENT(a) VPFX(a)
#else
/* For compatibility with varnish prior to 6.2 */
# define VEVENT(a) a
#endif

#include <vas.h>

struct entry
{
	char *key;
	char *val;
	size_t hash;
	struct entry *next, *prev;
};

static struct entry *ent_head, *ent_tail;
static size_t ent_count;

static void
entry_append(struct entry *ent)
{
	ent->next = NULL;
	ent->prev = ent_tail;
	if (ent_tail)
		ent_tail->next = ent;
	else
		ent_head = ent;
	ent_tail = ent;
	ent_count++;
}

static void
entry_remove(struct entry *ent)
{
	struct entry *p;

	if ((p = ent->prev) != NULL)
		p->next = ent->next;
	else
		ent_head = ent->next;
	if ((p = ent->next) != NULL)
		p->prev = ent->prev;
	else
		ent_tail = ent->prev;
	ent_count--;
	free(ent);
}


static size_t hash_size;
static struct entry **hash_table;
static size_t max_hash_size = 8192;
static ssize_t max_coll = -1; /* Max. number of collisions allowed */
static pthread_rwlock_t rwlock;

static int cs_coll[] = {
	0,   1,   2,   3,   4,   5,   6,   7,
	8,   9,  10,  11,  12,  13,  14,  15,
	16,  17,  18,  19,  20,  21,  22,  23,
	24,  25,  26,  27,  28,  29,  30,  31,
	32,  33,  34,  35,  36,  37,  38,  39,
	40,  41,  42,  43,  44,  45,  46,  47,
	48,  49,  50,  51,  52,  53,  54,  55,
	56,  57,  58,  59,  60,  61,  62,  63,
	64,  65,  66,  67,  68,  69,  70,  71,
	72,  73,  74,  75,  76,  77,  78,  79,
	80,  81,  82,  83,  84,  85,  86,  87,
	88,  89,  90,  91,  92,  93,  94,  95,
	96,  97,  98,  99, 100, 101, 102, 103,
	104, 105, 106, 107, 108, 109, 110, 111,
	112, 113, 114, 115, 116, 117, 118, 119,
	120, 121, 122, 123, 124, 125, 126, 127,
	128, 129, 130, 131, 132, 133, 134, 135,
	136, 137, 138, 139, 140, 141, 142, 143,
	144, 145, 146, 147, 148, 149, 150, 151,
	152, 153, 154, 155, 156, 157, 158, 159,
	160, 161, 162, 163, 164, 165, 166, 167,
	168, 169, 170, 171, 172, 173, 174, 175,
	176, 177, 178, 179, 180, 181, 182, 183,
	184, 185, 186, 187, 188, 189, 190, 191,
	192, 193, 194, 195, 196, 197, 198, 199,
	200, 201, 202, 203, 204, 205, 206, 207,
	208, 209, 210, 211, 212, 213, 214, 215,
	216, 217, 218, 219, 220, 221, 222, 223,
	224, 225, 226, 227, 228, 229, 230, 231,
	232, 233, 234, 235, 236, 237, 238, 239,
	240, 241, 242, 243, 244, 245, 246, 247,
	248, 249, 250, 251, 252, 253, 254, 255
};
static int ci_coll[] = {
	0,   1,   2,   3,   4,   5,   6,   7,
	8,   9,  10,  11,  12,  13,  14,  15,
	16,  17,  18,  19,  20,  21,  22,  23,
	24,  25,  26,  27,  28,  29,  30,  31,
	32,  33,  34,  35,  36,  37,  38,  39,
	40,  41,  42,  43,  44,  45,  46,  47,
	48,  49,  50,  51,  52,  53,  54,  55,
	56,  57,  58,  59,  60,  61,  62,  63,
	64,  97,  98,  99, 100, 101, 102, 103,
	104, 105, 106, 107, 108, 109, 110, 111,
	112, 113, 114, 115, 116, 117, 118, 119,
	120, 121, 122,  91,  92,  93,  94,  95,
	96,  97,  98,  99, 100, 101, 102, 103,
	104, 105, 106, 107, 108, 109, 110, 111,
	112, 113, 114, 115, 116, 117, 118, 119,
	120, 121, 122, 123, 124, 125, 126, 127,
	128, 129, 130, 131, 132, 133, 134, 135,
	136, 137, 138, 139, 140, 141, 142, 143,
	144, 145, 146, 147, 148, 149, 150, 151,
	152, 153, 154, 155, 156, 157, 158, 159,
	160, 161, 162, 163, 164, 165, 166, 167,
	168, 169, 170, 171, 172, 173, 174, 175,
	176, 177, 178, 179, 180, 181, 182, 183,
	184, 185, 186, 187, 188, 189, 190, 191,
	192, 193, 194, 195, 196, 197, 198, 199,
	200, 201, 202, 203, 204, 205, 206, 207,
	208, 209, 210, 211, 212, 213, 214, 215,
	216, 217, 218, 219, 220, 221, 222, 223,
	224, 225, 226, 227, 228, 229, 230, 231,
	232, 233, 234, 235, 236, 237, 238, 239,
	240, 241, 242, 243, 244, 245, 246, 247,
	248, 249, 250, 251, 252, 253, 254, 255
};

static int *collation = cs_coll;

static inline int
collate(char i)
{
	return collation[(unsigned char)i];
}

#define SIZE_T_MAX ((size_t)-1)

static inline size_t
rotl(size_t x, int n)
{
	return ((x << n) | (x >> ((CHAR_BIT * sizeof x) - n))) & SIZE_T_MAX;
}

static size_t
string_hash(const char *str)
{
	size_t value = 0;
	unsigned char ch;

	while ((ch = *str++))
		value = collate(ch) + rotl(value, 7);
	return value;
}

static inline int
chareq(int a, int b)
{
	return collate(a) == collate(b);
}

static int
streq(const char *a, const char *b)
{
	while (*a) {
		if (!(*b && chareq(*a, *b)))
			return 0;
		a++;
		b++;
	}
	return *b ? 0 : 1;
}

static ssize_t
my_getline(FILE *fp, char **pstr, size_t *psize)
{
	char *str;
	size_t size;
	size_t n;
	int c;
        
	if (!pstr || !psize) {
		errno = EINVAL;
		return -1;
	}

	str = *pstr;
	size = *psize;

	if (!str || size == 0) {
		/* Initial allocation */
		size = 16;
		str = malloc(size);
		if (!str)
			return -1;
		*pstr = str;
		*psize = size;
	}
	
	n = 0;
	while ((c = getc(fp)) != EOF) {
		if (n == size) {
			char *p;
			size_t sz;
			
			if (size >= (size_t) -1 / 3 * 2) {
				errno = ENOMEM;
				return -1;
			}
			sz = size + (size + 1) / 2;
			p = realloc(str, sz);
			if (!p)
				return -1;
			*pstr = str = p;
			*psize = size = sz;
		}
		str[n++] = c;
		if (c == '\n')
			break;
	}

	if (n == size) {
		char *p = realloc(str, size + 1);
		if (!p)
			return -1;
		*pstr = str = p;
		*psize = ++size;
	}
	str[n] = 0;
	return n;
}

static inline int
isws(int c)
{
	return c == ' ' || c == '\t' || c == '\r' || c == '\n';
}

static void
load_entries(char const *file)
{
	FILE *fp;
	ssize_t n;
	char *buf = NULL;
	size_t size = 0;
	unsigned line;
	char *p, *val;
	size_t l;
	struct entry *ent;

	fp = fopen(file, "r");
	if (!fp) {
		syslog(LOG_DAEMON|LOG_ERR,
		       "dict.init: can't load \"%s\": %s",
		       file, strerror(errno));
		abort();
	}
	line = 0;
	while ((n = my_getline(fp, &buf, &size)) > 0) {
		line++;
		
		while (n > 0 && isws(buf[n-1]))
			n--;
		buf[n] = 0;

		for (p = buf; isws(*p); p++, n--)
			;
		if (n == 0 || *p == '#')
			continue;

		l = strcspn(p, " \t");
		p[l] = 0;

		if (l == n) {
			syslog(LOG_DAEMON|LOG_ERR,
			       "%s:%u: malformed line", file, line);
			continue;
		}

		val = p + l + 1;
		while (*val == ' ' || *val == '\t')
			val++;

		ent = malloc(sizeof *ent + l + strlen(val) + 2);
		AN(ent);
		ent->key = (char*)(ent + 1);
		ent->val = ent->key + l + 1;
		strcpy(ent->key, p);
		strcpy(ent->val, val);
		ent->hash = string_hash(ent->key);
		entry_append(ent);
	}
	free(buf);
	assert(n != -1);
	fclose(fp);
}

static void
rehash(void)
{
	struct entry *ent;
	for (ent = ent_head; ent; ent = ent->next)
		ent->hash = string_hash(ent->key);
}

static void
fill_table(void)
{
	struct entry *ent;
	size_t next_size;
	
	next_size = ent_count * 2 + 1;
	if (next_size > max_hash_size)
		max_hash_size = next_size;
	
	do {
		size_t cn = 0;
		size_t hs;

		hash_size = next_size;
		hs = sizeof(hash_table[0]) * hash_size;
		hash_table = realloc(hash_table, hs);
		AN(hash_table);
		memset(hash_table, 0, hs);
		for (ent = ent_head; ent; ent = ent->next) {
			size_t h = ent->hash % hash_size;
			size_t i = h;
			size_t n = 0;
			
			while (hash_table[i]) {
				if (streq(hash_table[i]->key, ent->key)) {
					entry_remove(hash_table[i]);
					break;
				}
				i = (i + 1) % hash_size;
				assert(i != h);
				n++;
			}

			if (n > cn) cn = n;
			hash_table[i] = ent;
		}

		if (max_coll <= 0 || cn < max_coll)
			break;

		next_size = next_size * 2 + 1;
	} while (next_size < max_hash_size);
}	

int
VEVENT(dict_event)(VRT_CTX, struct vmod_priv *priv, enum vcl_event_e e)
{
	switch (e) {
	case VCL_EVENT_LOAD:
		pthread_rwlock_init(&rwlock, NULL);
		break;

	case VCL_EVENT_DISCARD:
		pthread_rwlock_wrlock(&rwlock);
		while (ent_head)
			entry_remove(ent_head);
		free(hash_table);
		hash_table = NULL;
		hash_size = 0;
		pthread_rwlock_unlock(&rwlock);
		break;
		
	case VCL_EVENT_WARM:
	case VCL_EVENT_COLD:
		break;
	}
	return 0;
}

VCL_VOID
vmod_ci(VRT_CTX, VCL_BOOL ci)
{
	int *cp;
	pthread_rwlock_wrlock(&rwlock);
        cp = ci ? ci_coll : cs_coll;
	if (cp != collation) {
		collation = cp;
		rehash();
		fill_table();
	}
	pthread_rwlock_unlock(&rwlock);
}

VCL_VOID
vmod_collisions(VRT_CTX, VCL_INT coll)
{
	max_coll = coll;
}

VCL_VOID
vmod_load(VRT_CTX, VCL_STRING file)
{
	pthread_rwlock_wrlock(&rwlock);
	load_entries(file);
	fill_table();
	pthread_rwlock_unlock(&rwlock);
}

VCL_VOID
vmod_clear(VRT_CTX)
{
	size_t i;
	
	pthread_rwlock_wrlock(&rwlock);
	for (i = 0; i < hash_size; i++)
		hash_table[i] = NULL;
	while (ent_head)
		entry_remove(ent_head);
	pthread_rwlock_unlock(&rwlock);
}	

static char const *
lookup_unlocked(char const *key)
{
	size_t i, h;
	char const *s = NULL;

	if (hash_size == 0)
		return NULL;
	
	h = string_hash(key) % hash_size;
	i = h;
	while (hash_table[i]) {
		if (streq(hash_table[i]->key, key)) {
			s = hash_table[i]->val;
			break;
		}
		i = (i + 1) % hash_size;
		if (i == h)
			break;
	}
	return s;
}
	
VCL_STRING
vmod_lookup(VRT_CTX, VCL_STRING key)
{
	char *s = NULL;
	if (key) {
		pthread_rwlock_rdlock(&rwlock);
		char const *p = lookup_unlocked(key);
		if (p) {
			s = WS_Copy(ctx->ws, p, -1);
			AN(s);
		}
		pthread_rwlock_unlock(&rwlock);
	}
	return s;
}