list.c

来自「傅立叶变换和小波变换是图像压缩的重要工具。该代大戏是利用小波变换进行图像压缩。」· C语言 代码 · 共 1,356 行 · 第 1/2 页

	assert(pRadixLink->Links);

	memcpy(pRadixLink->Links, OldLinks, (sizeof(Link)*OldNumLinks));
	//memset(pRadixLink->Links + OldNumLinks,0,(sizeof(Link)*(pRadixLink->NumLinks - OldNumLinks)));

	MemFree(OldLinks);
}

void RadixLink_Destroy(RadixLink * pRadixLink)
{
int r;
	assert(pRadixLink);
	for(r=0;r<(pRadixLink->NumLinks);r++)
	{
		if ( pRadixLink->Links[r].Next )
			Link_Destroy(pRadixLink->Links[r].Next);
	}
	MemFree(pRadixLink->Links);
	MemFree(pRadixLink);
}

void RadixLink_Add(RadixLink *pRadixLink,void * Data,int Key)
{
	assert(pRadixLink);
	assert( Key >= 0 );

	if ( Key >= pRadixLink->NumLinks )
		RadixLink_Grow(pRadixLink, Key + (Key>>2) );

	Link_Push(&(pRadixLink->Links[Key]),Data);

	if ( Key < pRadixLink->Min ) pRadixLink->Min = Key;
	if ( Key > pRadixLink->Max ) pRadixLink->Max = Key;
}

void * RadixLink_CutMax(RadixLink *pRadixLink,int *pKey)
{
Link * pLink;
	pLink = (pRadixLink->Links) + (pRadixLink->Max);
	while ( pRadixLink->Max >= 0 )
	{
		if ( pLink->Next )
		{
			if ( pKey ) *pKey = pRadixLink->Max;
			return Link_Pop(pLink);
		}
		pRadixLink->Max --;
		pLink --;
	}
return NULL;
}

void * RadixLink_CutMin(RadixLink *pRadixLink,int *pKey)
{
Link * pLink;
	pLink = (pRadixLink->Links) + (pRadixLink->Min);
	while ( pRadixLink->Min < pRadixLink->NumLinks )
	{
		if ( pLink->Next )
		{
			if ( pKey ) *pKey = pRadixLink->Min;
			return Link_Pop(pLink);
		}
		pRadixLink->Min ++;
		pLink ++;
	}
return NULL;
}

void * RadixLink_CutKey(RadixLink *pRadixLink,int Key)
{
	assert(pRadixLink);
return Link_Pop(&(pRadixLink->Links[Key]));
}


/***** debug only : **********************/

void List_TimerReport(void)
{
#ifdef DO_TIMER
	TIMER_REPORT(List_Ram);
	TIMER_REPORT(List_RadixWalk);
	TIMER_REPORT(List_RadixInit);
#endif
}

/*************************************************/

/**************************************************

Hash has separate Keys & Data

We use a single Circular list of all the nodes.  We have
cappers of Hash = 0 and HASH_SIZE at the head and tail.
So a general hash looks like : (with HASH_SIZE == 7)


(Head)-->A--x->C--x->E--x-->(Tail)
[0]		[1][2][3][4][5][6]

the brackets are hash buckets; little x's mean that hash bucket
has seen no nodes of its own hash, so it points to the next
larger hash's list.

to do a Get :
	simply look at your current pointer and walk while hash == my hash
	example : Get(Hash == 3)
		we get node C : ok, test it
		next is node E : not my hash, so I'm done

to do a delete :
	simply cut your node, and point yourself to the next node.
	example : Delete( Node C )

(Head)-->A--x--x--x->E--x-->(Tail)
[0]		[1][2][3][4][5][6]

		now hash bucket 3 points to node E

to do an add :

	first you must take your current pointer and walk backwards until
	the preceding node has a lower hash than you (see example later).

	then simply add the new node before the current one and make yourself
	point to the new one.

	Example 1: Add an A:
		bucket 1 already is in the right place
		add before the old node :

       +-A1
       | |
(Head)-+ A2-x--x--x->E--x-->(Tail)
[0]		[1][2][3][4][5][6]

		now make the hash point to the new add:

         A2-+
         |  |
(Head)---A1 x--x--x->E--x-->(Tail)
[0]		[1][2][3][4][5][6]

	Example 2 : we need the extra seek in each _Add()
		add a node C at hash 3


         A--+--+
         |     |
(Head)---A (E) C--x->E--x-->(Tail)
[0]		[1][2][3][4][5][6]

		the funny notation is to indicate that bucket 2 still
		points to node E.

		now add a node B at hash 2
		we currently point to node (E)
		the previous node is (C), which is greater than B, so
		we step back; now the current is (C) and the previous is (A) :

         A--+
         |  |   
(Head)---A  +->C--x->E--x-->(Tail)
[0]		[1][2][3][4][5][6]

		which is a good list, so we do the normal add:

         A--+
         |  |   
(Head)---A  B->C--x->E--x-->(Tail)
[0]		[1][2][3][4][5][6]

**************

the whole goal of this system is that the WalkNext() function is
blazing fast.  The only thing that hurts in the _Add function, but
the cost of adding N nodes to hash of size M is only O(N + M*M)
(because the first M adds are O(M) and the later adds are O(1))

*****************************/

#ifdef _CRAPPY_HASH_DEBUG //{

#pragma message("using crappy debug hash implementation")

struct Hash
{
	HashNode ** NodeArray;
	int			NodeArrayLen;
	int			NodeCount;
};


struct HashNode
{
	ulong	Key;
	ulong	Data;
};

Hash *	Hash_Create(void)
{
Hash * H;
	H = new(Hash);
	assert(H);
	//memset(H,0,sizeof(*H));
return H;
}

void Hash_Destroy(Hash *H)
{
	assert(H);
	if ( H->NodeArray )
	{
	int n;
		for(n=0;n<H->NodeCount;n++)
		{
			MemPool_FreeHunk(HashNodePool_g,H->NodeArray[n]);
		}
		destroy(H->NodeArray);
	}

	destroy(H);
}	

HashNode *	REGCALL Hash_Add(Hash *H,ulong Key,ulong Data)
{
HashNode * hn;
	hn = MemPool_GetHunk(HashNodePool_g);
	assert(hn);
	hn->Key = Key;
	hn->Data = Data;

	if ( H->NodeCount == H->NodeArrayLen )
	{
		H->NodeArrayLen = H->NodeCount + 100;
		if ( H->NodeArray )
		{
			H->NodeArray = geRam_Realloc(H->NodeArray,H->NodeArrayLen*sizeof(HashNode *));
		}
		else
		{
			H->NodeArray = geRam_Allocate(H->NodeArrayLen*sizeof(HashNode *));
		}
		assert(H->NodeArray);
	}

	H->NodeArray[H->NodeCount] = hn;
	H->NodeCount ++;

return hn;
}

void		REGCALL Hash_DeleteNode(Hash *pHash,HashNode *pNode)
{
int n;

	n = 0;
	while( pHash->NodeArray[n] != pNode )
	{
		n++;
		assert( n < pHash->NodeCount );
	}

	pHash->NodeArray[n] = pHash->NodeArray[ pHash->NodeCount - 1];
	assert(pHash->NodeArray[n]);
	pHash->NodeArray[ pHash->NodeCount - 1] = NULL;
	pHash->NodeCount --;

	MemPool_FreeHunk(HashNodePool_g,pNode);
}

HashNode *	REGCALL Hash_Get(Hash *pHash,ulong Key,ulong *pData)
{
int n;
	for(n=0;n<pHash->NodeCount;n++)
	{
		if ( pHash->NodeArray[n]->Key == Key )
		{
			if ( pData )
				*pData = pHash->NodeArray[n]->Data;
			return pHash->NodeArray[n];
		}
	}
	return NULL;
}

HashNode *	REGCALL Hash_WalkNext(Hash *pHash,HashNode *pCur)
{
int n;

	if ( pCur )
	{
		n = 0;
		while( pHash->NodeArray[n] != pCur )
		{
			n++;
			assert( n < pHash->NodeCount );
		}
		n ++;
	}
	else
	{
		n = 0;
	}
	if ( n == pHash->NodeCount )
		return NULL;
	else
		return pHash->NodeArray[n];
}

ulong		REGCALL Hash_NumMembers(Hash *pHash)
{
	return pHash->NodeCount;
}


#else //}{ the real thing

#define HASH_MOD	(1009) // or 1013  , a nice prime
#define HASH_SIZE	(HASH_MOD + 1) 
#define HASH(Key)	((( ((Key)>>15) ^ (Key) )%HASH_MOD)+1)

struct Hash
{

	Debug(Hash * MySelf1)

	HashNode *	HashTable[HASH_SIZE];
	HashNode *	NodeList;

	Debug(int	Members)
	Debug(Hash * MySelf2)
};

struct HashNode
{
	LinkNode LN;
	ulong	Key;
	ulong	Data;
	ulong	Hash;
};

Hash * Hash_Create(void)
{
Hash * pHash;
HashNode *pHead,*pTail;

	pHash = new(Hash);
	if ( ! pHash ) 
		return NULL;
	
	//memset(pHash,0,sizeof(Hash));

	Debug( pHash->MySelf1 = pHash )
	Debug( pHash->MySelf2 = pHash )

	pTail = MemPool_GetHunk(HashNodePool_g);
	assert(pTail);
	LN_Null(pTail);
	pTail->Key = pTail->Data = 0;
	pTail->Hash = HASH_SIZE;

	pHead = MemPool_GetHunk(HashNodePool_g);
	assert(pHead);
	LN_Null(pHead);
	pHead->Key = pHead->Data = 0;
	pHead->Hash = 0;

	LN_AddBefore(pHead,pTail);

	pHash->NodeList = pHead;

	Debug(pHash->Members = 0)

return pHash;
}

void Hash_Destroy(Hash *pHash)
{
	if ( pHash )
	{
	HashNode *pList,*pNode,*pNext;
	
		assert( pHash->MySelf1 == pHash && pHash->MySelf2 == pHash );

		Debug(pHash->Members += 2) // count Head & Tail

		pList = pHash->NodeList;
		LN_Walk_Editting(pNode,pList,pNext) {
			MemPool_FreeHunk(HashNodePool_g,pNode);
			assert(pHash->Members > 1);
			Debug(pHash->Members --)
		}
		assert(pHash->Members == 1);
		MemPool_FreeHunk(HashNodePool_g,pList);
		destroy(pHash);
	}
}

#ifndef NDEBUG
int Hash_ListLen(Hash *pHash,ulong H)
{
HashNode *hn;
int Len = 0;
	hn = pHash->HashTable[H];
	if ( ! hn )
		return 0;
	while( hn->Hash == H )
	{
		Len ++;
		assert(pHash->Members >= Len);
		hn = LN_Next(hn);
	}
return Len;
}
#endif

HashNode * REGCALL Hash_Add(Hash *pHash,ulong Key,ulong Data)
{
ulong H;
HashNode *hn,**pTable,*Node,*Prev;
Debug( int ListLen1; int ListLen2; int HashLen1; int HashLen2; int WalkLen)

	assert(pHash);
	assert( pHash->MySelf1 == pHash && pHash->MySelf2 == pHash );

	hn = MemPool_GetHunk(HashNodePool_g);
	assert(hn);
	Debug( LN_Null(hn) )

	hn->Key = Key;
	hn->Data = Data;
	hn->Hash = H = HASH(Key);

	pTable = &(pHash->HashTable[H]);
	Node = *pTable;

	assert( H > 0 );
	assert( pHash->NodeList->Hash == 0 );
	assert( ((HashNode *)LN_Prev(pHash->NodeList))->Hash == HASH_SIZE );

	Debug(HashLen1 = Hash_NumMembers(pHash))
	Debug(ListLen1 = Hash_ListLen(pHash,H))

	if ( ! Node )
	{
		Prev = pHash->NodeList;
		Node = LN_Next(Prev);

		Debug(WalkLen = 0)

		assert(Prev->Hash < H);
		while( Node->Hash < H )
		{
			Prev = Node;
			Node = LN_Next(Prev);
		
			assert(WalkLen < pHash->Members );
			Debug( WalkLen ++)
			
			assert(Prev->Hash <= Node->Hash);
			assert(Prev->Hash < HASH_SIZE );
		}

		assert(Prev->Hash < H);
		assert(Node->Hash >= H);
	}

	LN_AddBefore(hn,Node);
	*pTable = hn;

	Debug(pHash->Members ++)

	Debug(ListLen2 = Hash_ListLen(pHash,H))
	assert( ListLen2 == (ListLen1 + 1) );
	Debug(HashLen2 = Hash_NumMembers(pHash))
	assert( HashLen2 == (HashLen1 + 1) );

return hn;
}

void REGCALL Hash_DeleteNode(Hash *pHash,HashNode *pNode)
{
HashNode ** pHead;
ulong H;
Debug( int ListLen1; int ListLen2;int HashLen1; int HashLen2)

	assert(pNode );
	assert( pHash );
	assert( pHash->MySelf1 == pHash && pHash->MySelf2 == pHash );

	assert( pNode->Hash > 0 && pNode->Hash < HASH_SIZE );

	H = pNode->Hash;
	pHead = & ( pHash->HashTable[H] );

	Debug( HashLen1 = Hash_NumMembers(pHash) )
	Debug( ListLen1 = Hash_ListLen(pHash,H) )
	assert(pHash->Members > 0);
	Debug(pHash->Members --)

	if ( *pHead == pNode )
	{
		*pHead = LN_Next(pNode);
		if ( (*pHead)->Hash != H )
		{
			// pNode was the head of the list
			assert( ((HashNode *)LN_Prev(pNode))->Hash < H );
			*pHead = NULL;
		}
	}
	assert( *pHead == NULL || (*pHead)->Hash == H );

	LN_Cut(pNode);

	MemPool_FreeHunk(HashNodePool_g,pNode);
	
	Debug( HashLen2 = Hash_NumMembers(pHash) )
	Debug( ListLen2 = Hash_ListLen(pHash,H) )
	assert( HashLen2 == (HashLen1 - 1) );

}

HashNode * REGCALL Hash_Get(Hash *pHash,ulong Key,ulong *pData)
{
ulong H;
HashNode *pNode;

	assert(pHash );
	assert( pHash->MySelf1 == pHash && pHash->MySelf2 == pHash );

	H = HASH(Key);
	assert( H > 0 && H < HASH_SIZE );

	pNode = pHash->HashTable[H];
	if ( ! pNode )
		return NULL;

	assert( pNode->Hash == H );

	while( pNode->Hash == H )
	{
		if ( pNode->Key == Key )
		{
			if ( pData )
				*pData = pNode->Data;
			return pNode;
		}
		pNode = LN_Next(pNode);
	}

return NULL;
}

HashNode * REGCALL Hash_WalkNext(Hash *pHash,HashNode *pNode)
{
HashNode *pNext;

	assert(pHash);
	assert( pHash->MySelf1 == pHash && pHash->MySelf2 == pHash );

	if ( ! pNode )
	{
		pNode = pHash->NodeList;
		assert( pNode->Hash == 0 );
	}

	pNext = LN_Next(pNode);
	assert( pNext->Hash > 0 );
	assert( pNext->Hash >= pNode->Hash );

	assert( pNext != pNode );
	assert( LN_Prev(pNext) == pNode );

	if ( pNext->Hash == HASH_SIZE )
	{
		assert( ((HashNode *)LN_Next(pNext)) == pHash->NodeList );
		return NULL;
	}

	assert(pNext->Hash < HASH_SIZE);

return pNext;
}

ulong		REGCALL Hash_NumMembers(Hash *pHash)
{
ulong N;
HashNode *pNode;

	assert(pHash);
	assert( pHash->MySelf1 == pHash && pHash->MySelf2 == pHash );

	pNode = pHash->NodeList;
	assert( pNode->Hash == 0 );
	pNode = LN_Next(pNode);
	assert( pNode->Hash > 0 );

	N = 0;
	while( pNode->Hash < HASH_SIZE )
	{
		assert( N < (ulong)pHash->Members );
		pNode = LN_Next(pNode);
		N ++;
	}

	assert( N == (ulong)pHash->Members );

return N;
}

#endif //}{ hashes

ulong	Hash_StringToKey(const char * String)
{
return crcbuf(String,strlen(String));
}

void	HashNode_SetData(HashNode *pNode,ulong Data)
{
	assert(pNode);
	pNode->Data = Data;
}

void	HashNode_GetData(HashNode *pNode,ulong *pKey,ulong *pData)
{
	assert(pNode);
	*pKey	= pNode->Key;
	*pData	= pNode->Data;
}

ulong	HashNode_Data(HashNode *pNode)
{
	assert(pNode);
return pNode->Data;
}

ulong	HashNode_Key(HashNode *pNode)
{
	assert(pNode);
return pNode->Key;
}

/***************************/

bool List_Start(void)
{
	assert(UsageCount >= 0 );
	if ( UsageCount == 0 )
	{
		assert(ListPool_g == NULL && LinkPool_g == NULL);
		if ( ! (ListPool_g = MemPool_Create(sizeof(List),1024,1024) ) )
			return false;
		if ( ! (LinkPool_g = MemPool_Create(sizeof(Link),128,128) ) )
			return false;
		if ( ! (HashNodePool_g = MemPool_Create(sizeof(HashNode),128,128) ) )
			return false;
		// could latch ListFuncs_Stop() on atexit() , but no need, really..
	}
	UsageCount ++;
	return true;
}

bool List_Stop(void)
{
	assert(UsageCount > 0 );
	UsageCount --;
	if ( UsageCount == 0 )
	{
		assert(ListPool_g && LinkPool_g );
		MemPool_Destroy(ListPool_g); ListPool_g = NULL;
		MemPool_Destroy(LinkPool_g); LinkPool_g = NULL;
		MemPool_Destroy(HashNodePool_g); HashNodePool_g = NULL;
	}
	return true;
}