contexttrie.c

PPMz2压缩方式的源码

//-{--------------------------------------------------------------------

#include "ContextTrie.h"
#include "config.h"

struct ContextTrie
{
	Context * order0;
	Context ** order1;
	uint numNodes;
	uint orders;
	uint * alphabets;

	LinkNode LRU;
	uint NumLRUContexts,MaxLRUContexts;
};

//-}{--------------------------------------------------------------------
// ContextTrie functions

ContextTrie * ContextTrie_Create(uint * alphabets,uint orders,uint ContextMegabytes)
{
ContextTrie * t;
uint i;

	t = new(ContextTrie);
	assert(t);

	t->orders = orders;
	t->alphabets = malloc(orders*sizeof(uint));
	memcpy(t->alphabets,alphabets,orders*sizeof(uint));

	t->order0 = Context_Create(NULL,0);

	t->order1 = calloc(1,sizeofpointer*alphabets[0]);
	for(i=0;i<alphabets[0];i++)
	{
		t->order1[i] = Context_Create(t->order0,i);
	}

	LN_Null(&(t->LRU));

	t->NumLRUContexts = 0;
	t->MaxLRUContexts = (ContextMegabytes<<20)/sizeof(Context);

return t;
}

void ContextTrie_Destroy(ContextTrie * t)
{
	free(t->alphabets);
	destroy(t);
}

void ContextTrie_DeleteContext(ContextTrie * t,Context *c)
{
	assert( ! c->parent || c->parent->order == (c->order - 1) );
	assert( c->order == PPMZ2_Order || ! c->child  || c->child->order  == (c->order + 1) );
	assert( ((Context *)LN_Next(c))->order == c->order );

	if ( c->child )
	{
		if ( c->order == PPMZ2_Order )
		{
			// c->child is a PPMDet !
			//PPMDet_DeleteNodes(
			c->child = NULL; // just let the det LRU clean it up later
		}
		else
		{
			do
			{
				assert(c->child->order == (c->order + 1) );
				assert(c->child->parent == c);
				ContextTrie_DeleteContext(t,c->child);
			} while(c->child);
		}
	}

	if ( c->parent )
	{
		assert(c->parent->order == (c->order - 1) );
		if ( c->parent->child == c )
		{
			// parent points to me; try to get a sibling
			c->parent->child = LN_Next(c);
			if ( c->parent->child == c ) // no siblings, so nullify :
				c->parent->child = NULL;
		}
	}

	assert( ! c->parent || c->parent->order == (c->order - 1) );
	assert( ! c->child );
	assert( ((Context *)LN_Next(c))->order == c->order );

	Context_Destroy(c); // does LN_Cut(c) & LN_Cuts the LRU for us
	t->NumLRUContexts --;
}

void ContextTrie_LRUNewContext(ContextTrie *t,Context *c)
{
	LN_AddHead( &(t->LRU), &(c->LRU) );

	t->NumLRUContexts ++;

	if ( t->NumLRUContexts >= t->MaxLRUContexts )
	{
	LinkNode * pLast;
	
		// delete one at tail

		pLast = LN_CutTail(&(t->LRU));
		assert(pLast);
		c = (Context *)( (ulong)pLast - (ulong)(&(((Context *)0)->LRU)) );

		assert( ! c->parent || c->parent->order == (c->order - 1) );
		assert( c->order == PPMZ2_Order || ! c->child  || c->child->order  == (c->order + 1) );
		assert( ((Context *)LN_Next(c))->order == c->order );
		assert( c->child != c->parent );

		ContextTrie_DeleteContext(t,c);
	}
}

void ContextTrie_LRUOldContext(ContextTrie *t,Context *c)
{
	LN_Cut( &(c->LRU) );
	LN_AddHead( &(t->LRU), &(c->LRU) );
}

Context * ContextTrie_FindOrCreate(ContextTrie * t,Context *c,ulong index)
{
Context * next;
	next = Context_Find(c,index);
	if ( next )
	{
		c = next;
		ContextTrie_LRUOldContext(t,c);
	}
	else
	{
		c = Context_Create(c,index);
		ContextTrie_LRUNewContext(t,c);
	}
return c;
}

void ContextTrie_GetNodes(ContextTrie * t,ulong * pindex,Context ** pinto)
{
Context * c;
uint i;

	*pinto++ = c = t->order0;
	*pinto++ = c = t->order1[*pindex++];
	for(i=2;i<=t->orders;i++)
	{
		c = ContextTrie_FindOrCreate(t,c,*pindex++);

		assert( ! c->parent || c->parent->order == (c->order - 1) );
		assert( c->order == PPMZ2_Order || ! c->child  || c->child->order  == (c->order + 1) );
		assert( ((Context *)LN_Next(c))->order == c->order );

		*pinto++ = c;
	}
}

//-}--------------------------------------------------------------------