#include <ctype.h>		// isalnum, isspace
#include <stdlib.h>		// strtoul
#include <string.h>		// strchr, strlen, memmove, memcmp, memcpy

#include "substi.h"



/*============================================================================*\
					MISTNI ZALEZITOSTI - SPRAVA PAMETI
\*============================================================================*/


/*----------------------------------------------------------------------------*\
			JEDEN CLANEK RETEZU NAALOKOVANYCH PAMETOVYCH OBLASTI
\*----------------------------------------------------------------------------*/


// Struktura
//
struct mempools
{
	struct mempools	*linkp;		// vazba na dalsi
	int				numby;		// pocet volnych byte
	char			*memp;		// zacatek volne pametove oblasti
};



/*
 * NOVY CLANEK RETEZU
 */

static struct mempools *mempool_alloc(substiallocfncp_t allocfncp,
									  unsigned          numby)
{
#define  MEMORY_SIZE	8192

	struct mempools		*thisp;

	numby = ((numby + sizeof(*thisp) - 1) / MEMORY_SIZE + 1) * MEMORY_SIZE;
	if((thisp = (*allocfncp)(numby)) != NULL)
	{
		thisp->linkp = NULL;
		thisp->numby = numby - sizeof(*thisp);
		thisp->memp  = (char *)thisp + sizeof(*thisp);
	}
	return(thisp);

#undef  MEMORY_SIZE
}



/*
 * NOVY CLANEK RETEZU S PRIPOJENIM NA KONEC
 */

static struct mempools *mempool_create(struct mempools  *thisp,
									   substiallocfncp_t allocfncp,
									   unsigned          numby)
{
	while(thisp->linkp != NULL)
		thisp = thisp->linkp;
	thisp->linkp = mempool_alloc(allocfncp, numby);
	return(thisp->linkp);
}



/*
 * VYRAZENI CASTI PAMETI Z TOHOTO CLANKU
 */

static void *mempool_done(struct mempools *thisp,
						  int             numby)
{
	void	*memp;

	memp = thisp->memp;
	thisp->numby -= numby;
	thisp->memp  += numby;
	return(memp);
}



/*
 * POZADAVEK NA KUS PAMETI
 */

static void *mempool_request(struct mempools   *thisp,
							 substiallocfncp_t allocfncp,
							 int               numby)
{
	struct mempools	*closestp;

// Nalezeni clanku neblize odpovidajicimu zadani
	closestp = NULL;
	while(1)
	{
		if(thisp->numby >= numby)
			do
			{
				if(closestp != NULL)
					if(closestp->numby > thisp->numby)
						break;
				closestp = thisp;
			} while(0);
		if(thisp->linkp == NULL)
			break;
		thisp = thisp->linkp;
	}
// Pokud se nenasel...
	if(closestp == NULL)
	{
// ...je alokovana nova pametova oblast
		if((closestp = mempool_alloc(allocfncp, numby)) == NULL)
			return(NULL);
		thisp->linkp = closestp;
	}
// Z pametove oblasti je "odebrano" prislusne mnozstvi bytu
	return(mempool_done(closestp, numby));
}



/*
 * VYHLEDANI CLANKU RETEZU S NEJVETSIM VOLNYM MISTEM
 */

static struct mempools *mempool_biggest(struct mempools *thisp)
{
	struct mempools	*biggestp;

	biggestp = thisp;
	while((thisp = thisp->linkp) != NULL)
		if(biggestp->numby < thisp->numby)
			biggestp = thisp;
	return(biggestp);
}



/*----------------------------------------------------------------------------*\
				JEDEN CLANEK RETEZU DVOJIC "SYMBOL+HODNOTA"
\*----------------------------------------------------------------------------*/


// Struktura
//
struct sympairs
{
	struct sympairs	*linkp;		// vazba na dalsi
	int				size;		// velikost pameti zabrana timto clankem
	int				vallen;		// delka "hodnoty"
	char			*valp;		// "hodnota"
	int				symlen;		// delka "symbolu"
	char			symt[0];	// "symbol"
};
//
#define  SYMPAIR_FREE(p)		((p)->symlen =  0)
#define  SYMPAIR_IS_FREE(p)		((p)->symlen == 0)
#define  SYMPAIR_BASE(p, e)		((p)->valp =  NULL,  (p)->vallen = (e))
#define  SYMPAIR_IS_BASE(p)		((p)->valp == NULL)
#define  SYMPAIR_EVAL_GET(p)	(p)->vallen
#define  SYMPAIR_EVAL_NEXT(p)	((p)->vallen++)


// Test: Je symbol uzavren v zavorkach?
//
#define  SYMPAIR_IS_BKT(s, l, e)											\
	if(s[0] == SUBSTI_CHRS_LBKT)											\
	{																		\
		if(s[l - 1] != SUBSTI_CHRS_RBKT)									\
			return(e);														\
		++s;																\
		if((l -= 2) <= 0)													\
			return(e);														\
	}



/*
 * VYHLEDANI CLANKU RETEZU PODLE ZADANEHO "SYMBOLU"
 */

static struct sympairs *sympair_find_symbol(struct sympairs *thisp,
											char const      *symp,
											int             symlen)
{
SYMPAIR_IS_BKT(symp, symlen, NULL)
	while(thisp != NULL)
	{
		if(thisp->symlen == symlen)
			if(!memcmp(thisp->symt, symp, thisp->symlen))
				return(thisp);
		thisp = thisp->linkp;
	}
	return(NULL);
}



/*
 * VYHLEDANI VOLNEHO CLANKU RETEZU PODLE IDEALNI VELIKOSTI ALOKOVANE PAMETI
 */

static struct sympairs *sympair_find_closest(struct sympairs *thisp,
											 int             size)
{
	struct sympairs	*closestp;

	closestp = NULL;
	while(thisp != NULL)
	{
		if(SYMPAIR_IS_FREE(thisp))
			if(thisp->size >= size)
				do
				{
					if(closestp != NULL)
						if(closestp->size > thisp->size)
							break;
					closestp = thisp;
				} while(0);
		thisp = thisp->linkp;
	}
	return(closestp);
}



/*============================================================================*\
					MISTNI ZALEZITOSTI - POMOCNE FUNKCE
\*============================================================================*/


/*----------------------------------------------------------------------------*\
						PREVOD: HODNOTA --> TEXT
\*----------------------------------------------------------------------------*/


// Maximalni pocet znaku 32bitoveho dec.cisla
//
#define  UTOA10_MAX_DIGITS		11



/*
 * FUNKCE PREVODU
 */

static int utoa10(unsigned value,
				  char     buffer[])
{
#define  RADIX		10

	char	*xfbp,
			xfert[UTOA10_MAX_DIGITS];

	xfbp = xfert;
	do
		*xfbp++ = value % RADIX + '0';
	while(value /= RADIX);
	value = xfbp - xfert;
	do
		*buffer++ = *--xfbp;
	while(xfbp >= xfert);
	return(value);

#undef  RADIX
}



/*----------------------------------------------------------------------------*\
							NALEZENI KONCE RETEZCE
\*----------------------------------------------------------------------------*/


/*
 * "SYMBOL"
 */

static char const *findend_symbol(char const *endp,
								  int        commentc)
{
	int		digit, basec,
			lbkt0f;

	basec = '\0';
	lbkt0f = *endp ^ SUBSTI_CHRS_LBKT;
	if(lbkt0f)
		--endp;
	while((digit = *++endp) != '\0')
	{
		if(digit == '_')
			continue;
		if(digit == SUBSTI_CHRS_BASE)
		{
			if(basec != '\0')
				break;
			basec = digit;
			continue;
		}
		if(digit == SUBSTI_CHRS_RBKT)
		{
			if(!lbkt0f)
				++endp;
			break;
		}
		if(digit == commentc)
			break;
		if(!isalnum(digit))
			break;
	}
	return(endp);
}



/*
 * "HODNOTA"
 */

static char const *findend_value(char const *valp,
								 int        commentc)
{
	int			digit;
	char const	*endp;

	endp = valp;
	while((digit = *valp) != '\0')
	{
		if(digit == commentc)
			break;
		++valp;
		if(!isspace(digit))
			endp = valp;
	}
	return(endp);
}



/*============================================================================*\
					MISTNI ZALEZITOSTI - ZPRACOVANI TEXTU
\*============================================================================*/


//  "Handle" - promenne teto vrstvy
//
struct substis
{
// Zacatky retezu pametovych oblasti
	struct mempools		*poolp;		// ...naalokovanych
	struct sympairs		*pairp;		// ...dvojic "symbol+hodnota"
// Funkce spravy pameti
	substiallocfncp_t	allocfncp;
	substifreefncp_t	freefncp;
// Specialni znaky pouzite v textu
	int					symbolc,
						commentc;
};



/*----------------------------------------------------------------------------*\
							DEFINICE "SYMBOLU"
\*----------------------------------------------------------------------------*/


/*
 * NOVA DVOJICE
 */

static struct sympairs *operate_pair(substihndp_t hndp,
									 int          size)
{
	struct sympairs	*pairp;

	if((pairp = sympair_find_closest(hndp->pairp, size)) == NULL)
		pairp = mempool_request(hndp->poolp,
								hndp->allocfncp,
								sizeof(*pairp) + size);
	return(pairp);
}



/*
 * NOVY "SYMBOL"
 */

static char const *operate_define(substihndp_t hndp,
								  char const   *linep,
								  char const   *symp)
{
	char const 		*endp;
	int				symlen;
	char const		*valp;
	int				vallen;
	struct sympairs	*pairp;
	unsigned		eval;

	endp = findend_symbol(symp, hndp->commentc);
	if((symlen = endp - symp) <= 0)
		return(linep);
	valp = endp + 1;
	while(isspace(*valp))
		++valp;
	eval = endp[-1];
	endp = findend_value(valp, hndp->commentc);
	if((vallen = endp - valp) <= 0)	// bez zadani "hodnoty"
	{
		pairp = sympair_find_symbol(hndp->pairp, symp, symlen);
		if(pairp == NULL)			// "symbol" v retezu neni
			return(linep);
		SYMPAIR_FREE(pairp);		// je, vyradit
		return("");
	}
	if(eval == SUBSTI_CHRS_BASE)
		do
		{
			char	*vendp;

			eval = strtoul(valp, &vendp, 0);
			if(vendp != endp)
				return(linep);
			valp   = NULL;			// znacka: je to bazova hodnota
			vallen = 0;
		} while(0);
	do
	{
		int		size;

		size = symlen + vallen;
		pairp = sympair_find_symbol(hndp->pairp, symp, symlen);
		if(pairp != NULL)			// "symbol" v retezu uz je
		{
			if(pairp->size >= size)	// vyhovuje velikost?
				break;				// ano, opakovane pouzit
			SYMPAIR_FREE(pairp);	// ne, zneplatnit pro vyhledani
		}
		if((pairp = operate_pair(hndp, size)) == NULL)
			return(NULL);
		pairp->linkp = hndp->pairp;
		pairp->size  = size;
		hndp->pairp  = pairp;
	} while(0);
// Zarazeni noveho clanku retezu dvojic "symbol+hodnota"
	pairp->symlen = symlen;
	memcpy(pairp->symt, symp, symlen);
	if(valp != NULL)				// regulerni dvojice symbol+hodnota
	{
		pairp->valp   = pairp->symt + symlen;
		pairp->vallen = vallen;
		memcpy(pairp->valp, valp, vallen);
	}
	else							// bazova hodnota
		SYMPAIR_BASE(pairp, eval);
	return("");
}



/*----------------------------------------------------------------------------*\
						NAHRADA "SYMBOLU" ZA "HODNOTU"
\*----------------------------------------------------------------------------*/


// Promenne pro vystup textu po substituci
//
struct repouts
{
	char	*memp;				// kam to davat
	int		numby,				// kolik zbyva volne pameti
			chars;				// kolik bylo ulozeno do ".memp"
};
//
#define  OUTPUT_SETUP(r, p)	   ((r)->memp  = (p)->memp,						\
								(r)->numby = (p)->numby)
#define  OUTPUT_STORE(r, t, n) (memcpy((r)->memp, (t), (n)),				\
								(r)->memp  += (n),							\
								(r)->numby -= (n),							\
								(r)->chars += (n))



/*
 * INICIALIZACE HODNOT VYSTUPU
 */

static void operate_replace_init(substihndp_t   hndp,
								 struct repouts *rop)
{
	struct mempools	*poolp;

	poolp = mempool_biggest(hndp->poolp);
	OUTPUT_SETUP(rop, poolp);
	rop->chars = 0;
}



/*
 * NALEZENI "SYMBOLU" A JEHO NAHRADA - "SUBSTITUCE"
 */

static char const *operate_replace_symbol(substihndp_t   hndp,
										  char const     *linep,
										  char const     *symp,
										  struct repouts *rop)
{
#define  SYMLEN		numby

	int				numby;
	char const 		*endp;
	struct sympairs	*pairp;

	do
	{
		++symp;		// [
		endp = findend_symbol(symp, hndp->commentc);
		if((SYMLEN = endp - symp) <= 0)
			break;
		if((pairp = sympair_find_symbol(hndp->pairp, symp, SYMLEN)) == NULL)
		{
			if((numby = endp - linep) > 0)
				OUTPUT_STORE(rop, linep, numby);
			break;
		}
		--symp;		// ]
		if(SYMPAIR_IS_BASE(pairp))
		{
			numby = SYMPAIR_EVAL_GET(pairp);
			if((pairp = alloca(sizeof(*pairp) + UTOA10_MAX_DIGITS)) == NULL)
				return(NULL);
			pairp->valp   = (char *)pairp + sizeof(*pairp);
			pairp->vallen = utoa10(numby, pairp->valp);
		}
		numby = symp - linep + pairp->vallen;
		if(numby >= rop->numby)
		{
			struct mempools	*poolp;

			if((poolp = mempool_create(hndp->poolp,
										hndp->allocfncp,
										rop->chars + numby)) == NULL)
				return(NULL);
			if(rop->chars > 0)
				memcpy(poolp->memp, rop->memp - rop->chars, rop->chars);
			OUTPUT_SETUP(rop, poolp);
		}
		if((numby -= pairp->vallen) > 0)
			OUTPUT_STORE(rop, linep,   numby);
		OUTPUT_STORE(rop, pairp->valp, pairp->vallen);
	} while(0);
	return(endp);

#undef  SYMLEN
}



/*
 * DOPLNENI KONCE VSTUPNIHO RADKU DO VYSTUPU
 */

static char const *operate_replace_rest(substihndp_t   hndp,
										char const     *endp,
										char const     *comp,
										struct repouts *rop)
{
	int				numby;
	struct mempools	*poolp;

	if((numby = comp - endp) > 0)
	{
		if(rop->chars + numby >= rop->numby)
		{
			if((poolp = mempool_create(hndp->poolp,
										hndp->allocfncp,
										rop->chars + numby)) == NULL)
				return(NULL);
			memcpy(poolp->memp, rop->memp - rop->chars, rop->chars);
			rop->memp = poolp->memp + rop->chars;
		}
		OUTPUT_STORE(rop, endp, numby);
	}
	rop->memp[0] = '\0';
	return(rop->memp - rop->chars);
}



/*
 * VSTUPNI BOD
 */

static char const *operate_replace(substihndp_t hndp,
								   char const   *linep,
								   char const   *symp,
								   char const   *comp)
{
	char const 		*endp;
	struct repouts	rov;

	operate_replace_init(hndp, &rov);
	endp = linep;
	while(1)
	{
		while(symp[1] == hndp->symbolc)
			++symp;
		if(symp >= comp)
			break;
		if((endp = operate_replace_symbol(hndp, linep, symp, &rov)) == NULL)
			return(NULL);
		if(endp < comp)
			if((symp = strchr(endp, hndp->symbolc)) != NULL)
				if(symp < comp)
				{
					if(rov.chars > 0)
						linep = endp;
					continue;
				}
		break;
	}
	if(rov.chars <= 0)
		return(linep);
	return(operate_replace_rest(hndp, endp, comp, &rov));
}



/*----------------------------------------------------------------------------*\
				ZARAZENI NOVE DVOJICE PODLE "BAZOVEHO SYMBOLU"
\*----------------------------------------------------------------------------*/


/*
 * NOVY CLANEK RETEZU DVOJIC "SYMBOL+HODNOTA"
 */

static int operate_base_symbol(substihndp_t hndp,
							   char const   *symp,
							   int          symlen,
							   unsigned     eval)
{
	int				size;
	struct sympairs	*pairp;
	char			buffer[UTOA10_MAX_DIGITS];

SYMPAIR_IS_BKT(symp, symlen, -1)
	size = symlen + utoa10(eval, buffer);
	if((pairp = operate_pair(hndp, size)) == NULL)
		return(-1);
	pairp->linkp  = hndp->pairp;
	pairp->size   = size;
	pairp->vallen = size - symlen;
	pairp->valp   = pairp->symt + symlen;
	memcpy(pairp->valp, buffer, pairp->vallen);
	pairp->symlen = symlen;
	memcpy(pairp->symt, symp, symlen);
	hndp->pairp = pairp;
	return(0);
}



/*
 * NALEZENI "BAZOVANYCH SYMBOLU" S EVENT. ZARAZENIM
 */

static int operate_base(substihndp_t hndp,
						char const   *symp,
						char const   *comp)
{
	int				baselen, symlen;
	char const		*basep, *endp;
	struct sympairs	*pairp;

	do
	{
		while(symp[0] == hndp->symbolc)
			++symp;
		endp = findend_symbol(symp, hndp->commentc);
		if((symlen = endp - symp) <= 0)
			break;
		if((basep = strchr(symp, SUBSTI_CHRS_BASE)) == NULL)
			break;
		if((baselen = basep - symp + 1) < symlen)
			if(sympair_find_symbol(hndp->pairp, symp, symlen) == NULL)
				if((pairp = sympair_find_symbol(hndp->pairp,
												 symp,
												 baselen)) != NULL)
					if(baselen = operate_base_symbol(hndp,
													 symp,
													 symlen,
													 SYMPAIR_EVAL_NEXT(pairp)))
						return(baselen);
		if((symp = strchr(endp + 1, hndp->symbolc)) == NULL)
			break;
	} while(symp < comp);
	return(0);
}



/*----------------------------------------------------------------------------*\
							ZANEDBANI "BILYCH" ZNAKU
\*----------------------------------------------------------------------------*/


/*
 * UVODNICH
 */

static char const *operate_trim_beg(substihndp_t hndp,
									char const   *linep)
{
	char const	*comp;

	if((comp = strchr(linep, hndp->commentc)) == NULL)
		comp = linep + strlen(linep);
	while(1)
		if(comp == linep)
			return(NULL);
		else
			if(isspace(comp[-1]))
				--comp;
			else
				return(comp);
}



/*
 * KONCOVE
 */

static char const *operate_trim_end(substihndp_t hndp,
									char const   *linep,
									char const   *comp)
{
	int				numby;
	struct mempools	*poolp;

	numby = comp - linep;
	poolp = mempool_biggest(hndp->poolp);
	if(poolp->numby <= numby)
		if((poolp = mempool_create(hndp->poolp,
									hndp->allocfncp,
									numby + 1)) == NULL)
			return(NULL);
	memcpy(poolp->memp, linep, numby);
	poolp->memp[numby] = '\0';
	return(poolp->memp);
}



/*============================================================================*\
								VECI VEREJNE
\*============================================================================*/


/*
 * INICIALIZACE - PRVOTNI ALOKACE PAMETI
 */

substihndp_t substi_initial0(substiallocfncp_t allocfncp,
							 substifreefncp_t  freefncp,
							 int               symbolc,
							 int               commentc)
{
	struct mempools	*poolp;
	substihndp_t	hndp;

	if((poolp = mempool_alloc(allocfncp, sizeof(struct substis))) == NULL)
		return(NULL);
	hndp = mempool_done(poolp, sizeof(struct substis));
	hndp->poolp		= poolp;
	hndp->pairp		= NULL;
	hndp->allocfncp	= allocfncp;
	hndp->freefncp	= freefncp;
	hndp->symbolc	= symbolc;
	hndp->commentc	= commentc;
	return(hndp);
}



/*
 * ZPRACOVANI JEDNOHO RADKU TEXTU
 */

char const *substi_operate(substihndp_t  hndp,
						   char const    *linep)
{
#define  RTNP	symp

	char const	*comp, *symp;

	if((comp = operate_trim_beg(hndp, linep)) == NULL)
		return("");
	do
	{
		if((symp = strchr(linep, hndp->symbolc)) == NULL)
		{
			RTNP = linep;
			break;
		}
		if(symp >= comp)
		{
			RTNP = linep;
			break;
		}
		if(symp[1] == hndp->symbolc)
		{
			RTNP = operate_define(hndp, linep, symp + 2);
			break;
		}
		if(operate_base(hndp, symp + 1, comp))
			return(NULL);
		RTNP = operate_replace(hndp, linep, symp, comp);
	} while(0);
	if(RTNP != linep)
		return(RTNP);
	if(*comp == '\0')
		return(linep);
	return(operate_trim_end(hndp, linep, comp));

#undef  RTNP
}



/*
 * UVOLNENI NAALOKOVANE PAMETI
 */

void substi_leave(substihndp_t hndp)
{
	struct mempools		*poolp, *linkp;
	substifreefncp_t	freefncp;

	if(hndp == NULL)
		return;
	freefncp = hndp->freefncp;
	poolp    = hndp->poolp;
	while(poolp != NULL)
	{
		linkp = poolp->linkp;
		(*freefncp)(poolp);
		poolp = linkp;
	}
}



/*
 * PRO LADENI: SEZNAM DVOJIC "SYMBOL+HODNOTA"
 */

static int list_one(struct sympairs *pairp,
					substilistfncp_t fncp,
					void             *userdata)
{
#define  VALLEN(p)	(SYMPAIR_IS_BASE(p) ? UTOA10_MAX_DIGITS : (p)->vallen)

	char	*symp, *valp;

	if((symp = alloca(pairp->symlen + 1 + VALLEN(pairp) + 1)) == NULL)
		return(SUBSTI_LIST_ERROR);
	memcpy(symp, pairp->symt, pairp->symlen);
	symp[pairp->symlen] = '\0';
	valp = symp + pairp->symlen + 1;
	if(SYMPAIR_IS_BASE(pairp))
	{
		int		vallen;

		vallen = utoa10(SYMPAIR_EVAL_GET(pairp), valp);
		valp[vallen] = '\0';
	}
	else
	{
		memcpy(valp, pairp->valp, pairp->vallen);
		valp[pairp->vallen] = '\0';
	}
	return((*fncp)(symp, valp, userdata));

#undef  VALLEN
}

int substi_list(substihndp_t     hndp,
				substilistfncp_t fncp,
				void             *userdata)
{
	struct sympairs	*pairp;

	if(hndp == NULL)
		return(0);
	pairp = hndp->pairp;
	while(pairp != NULL)
	{
		int		test;

		if((test = list_one(pairp, fncp, userdata)) != SUBSTI_LIST_CONTINUE)
			return(test);
		pairp = pairp->linkp;
	}
	return(0);
}