list.c

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

//#define _CRAPPY_HASH_DEBUG

/*****

List_Ram can still be as high as 30% of the time!

*******/

// #define DO_TIMER

#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
#include "mempool.h"
#include "crc32.h"

#ifdef DO_TIMER
#include "timer.h"

TIMER_VARS(List_Ram);
TIMER_VARS(List_RadixWalk);
TIMER_VARS(List_RadixInit);

#else

#define TIMER_P(x)
#define TIMER_Q(X)

#endif // DO_TIMER

#ifndef NDEBUG
#define Debug(func)	func;
#define DebugAlert()	do { __asm { int 03h } } while(0)
#else
#define Debug(func)
#define DebugAlert()
#endif

#define MemAlloc(size)	calloc(1,size)
#define MemFree(mem)	free(mem)

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

static MemPool *ListPool_g = NULL, *LinkPool_g = NULL, *HashNodePool_g = NULL;
static int UsageCount = 0;

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

int LN_ListLen(LinkNode *pList)
{
LinkNode *pNode;
int Len=0;
	if ( ! pList )
		return 0;
	LN_Walk(pNode,pList) {
		Len++;
	}
return Len;
}

LinkNode *	REGCALL LN_CutHead(LinkNode *pList)
{
LinkNode * LN;
	assert(pList);
	LN = pList->Next;
	if ( LN == pList ) return NULL;
	LN_Cut(LN);
return LN;
}

LinkNode *	REGCALL LN_CutTail(LinkNode *pList)
{
LinkNode * LN;
	assert(pList);
	LN = pList->Prev;
	if ( LN == pList ) return NULL;
	LN_Cut(LN);
return LN;
}

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

struct List
{
	List *Next,*Prev;
	void * Data;
};

void	REGCALL List_Destroy(List * pList)
{
List * pNode;
	assert(pList);
	pNode = pList->Next;
	while( pNode != pList )
	{
	List *Next;
		Next = pNode->Next;
		MemPool_FreeHunk(ListPool_g,pNode);
		pNode = Next;
	}
	MemPool_FreeHunk(ListPool_g,pList);
}

List *	REGCALL List_Create(void)
{
List * pNew;

	pNew = MemPool_GetHunk(ListPool_g);
	assert(pNew);
	pNew->Data = NULL;
	pNew->Next = pNew->Prev = pNew;
return pNew;
}

List *	REGCALL List_AddTail(List *pList,void * Data)
{
List * pNew;

	pNew = MemPool_GetHunk(ListPool_g);
	assert(pNew);

	pNew->Next = pList;
	pNew->Prev = pList->Prev;
	pNew->Next->Prev = pNew;
	pNew->Prev->Next = pNew;
	
	pNew->Data= Data;
return pNew;
}

List *	REGCALL List_AddHead(List *pList,void * Data)
{
List * pNew;

	pNew = MemPool_GetHunk(ListPool_g);
	assert(pNew);
	pNew->Data= Data;

	pNew->Prev = pList;
	pNew->Next = pList->Next;
	pNew->Next->Prev = pNew;
	pNew->Prev->Next = pNew;
return pNew;
}

void *	REGCALL List_CutHead(List *pList)
{
List * pNode;
void * pData;
	pNode = pList->Next;
	if ( pNode == pList ) return NULL;
	pData = pNode->Data;

	pList->Next = pNode->Next;
	pList->Next->Prev = pList;

	MemPool_FreeHunk(ListPool_g,pNode);

return pData;
}

void *	REGCALL List_CutTail(List *pList)
{
List * pNode;
void * pData;
	pNode = pList->Prev;
	if ( pNode == pList ) return NULL;
	pData = pNode->Data;

	pList->Prev = pNode->Prev;
	pList->Prev->Next = pList;

	MemPool_FreeHunk(ListPool_g,pNode);

return pData;
}


void *	REGCALL List_PeekHead(List *pList)
{
List * pNode;
	pNode = pList->Next;
	if ( pNode == pList ) return NULL;
return pNode->Data;
}

void *	REGCALL List_PeekTail(List *pList)
{
List * pNode;
	pNode = pList->Prev;
	if ( pNode == pList ) return NULL;
return pNode->Data;
}

void	REGCALL List_CutNode(List *pNode)
{
	pNode->Prev->Next = pNode->Next;
	pNode->Next->Prev = pNode->Prev;

	pNode->Next = pNode->Prev = pNode;
}

void	REGCALL List_DeleteNode(List *pNode)
{
	List_CutNode(pNode);
	List_FreeNode(pNode);
}

void	REGCALL List_FreeNode(List *pNode)
{
	assert(pNode);
	MemPool_FreeHunk(ListPool_g,pNode);
}

void *	REGCALL List_NodeData(List *pNode)
{
	assert(pNode);
	return pNode->Data;
}

List *	REGCALL List_Next(List *pNode)
{
	return pNode->Next;
}
List *	REGCALL List_Prev(List *pNode)
{
	return pNode->Prev;
}

List *	List_Find(List *pList,void *Data)
{
List *pNode;
	assert(pList);
	for(pNode = pList->Next; pNode != pList; pNode = pNode->Next )
	{
		if ( pNode->Data == Data )
			return pNode;
	}
	return NULL;
}

/***********************************************************/
// Stack by linked list

struct Link
{
	Link * Next;
	void * Data;
};

void	REGCALL Link_Destroy(Link * pLink)
{
	while( pLink )
	{
	Link *Next;
		Next = pLink->Next;
		MemPool_FreeHunk(LinkPool_g,pLink);
		pLink = Next;
	}
}

Link *	REGCALL Link_Create(void)
{
Link * pLink;
	pLink = MemPool_GetHunk(LinkPool_g);
	assert(pLink);
	pLink->Next = NULL;
	pLink->Data = NULL;
return pLink;
}

void	REGCALL Link_Push(Link *pLink,void * Data)
{
Link * pNode;
	assert(pLink);
	pNode = MemPool_GetHunk(LinkPool_g);
	assert(pNode);
//	DebugWarn(geRam_IsValidPtr(pLink));
//	DebugWarn(geRam_IsValidPtr(pNode));
	pNode->Data = Data;

	pNode->Next = pLink->Next;
	pLink->Next = pNode;
}

void *	REGCALL Link_Pop(Link *pLink)
{
void *pData;
Link * pNode;
	if ( ! pLink ) return NULL;
//	DebugWarn(geRam_IsValidPtr(pLink));
	pNode = pLink->Next;
	if ( ! pNode ) return NULL;
//	DebugWarn(geRam_IsValidPtr(pNode));
	pData = pNode->Data;
	pLink->Next = pNode->Next;
	MemPool_FreeHunk(LinkPool_g,pNode);
return pData;
}

void *	REGCALL Link_Peek(Link *pLink)
{
void *pData;
Link * pNode;
	if ( ! pLink ) return NULL;
//	DebugWarn(geRam_IsValidPtr(pLink));
	pNode = pLink->Next;
	if ( ! pNode ) return NULL;
//	DebugWarn(geRam_IsValidPtr(pNode));
	pData = pNode->Data;
return pData;
}

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

#ifdef _DEBUG	// else it's in list.h
struct Stack
{
	void ** Buffer, **End;
	void ** Head;
	int members;
};
#endif

void	REGCALL Stack_Destroy(Stack * pStack)
{
	if ( pStack )
	{
		destroy(pStack->Buffer);
		destroy(pStack);
	}
}

Stack *	REGCALL Stack_Create(void)
{
Stack * pStack;
	pStack = new(Stack);
	assert(pStack);
	pStack->members = 4096;
	pStack->Buffer = MemAlloc(sizeof(void *)*(pStack->members));
	assert(pStack->Buffer);
	pStack->End = pStack->Buffer + (pStack->members);
	pStack->Head = pStack->Buffer;
return pStack;
}

int	REGCALL Stack_Extend(Stack *pStack)
{
void ** NewBuffer;
int newmembers;
	// realloc
	newmembers = pStack->members + 4096;
	NewBuffer = MemAlloc(sizeof(void *)*newmembers);
	assert(NewBuffer);
	memcpy(NewBuffer,pStack->Buffer, sizeof(void *)*(pStack->members));
	pStack->Head = NewBuffer + pStack->members;
	pStack->members = newmembers;
	MemFree(pStack->Buffer);
	pStack->Buffer = NewBuffer;

	pStack->End = pStack->Buffer + (pStack->members);
return newmembers;
}

void	REGCALL Stack_Push_Func(Stack *pStack,void * Data)
{
	assert(pStack);
	*(pStack->Head)++ = Data;
	if ( pStack->Head == pStack->End )
		Stack_Extend(pStack);
}

void *	REGCALL Stack_Pop_Func(Stack *pStack)
{
	assert(pStack);
	if ( pStack->Head == pStack->Buffer )
		return NULL;
	pStack->Head --;
return *(pStack->Head);
}

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

struct RadixList
{
	int NumLists;
	int Min,Max;
	List ** Lists;
};

RadixList * RadixList_Create(int RadixListMax)
{
RadixList * pRadixList;
int r;
	pRadixList = new(RadixList);
	assert(pRadixList);
	pRadixList->NumLists = RadixListMax+1;
	pRadixList->Lists = MemAlloc(sizeof(List *)*(pRadixList->NumLists));
	assert(pRadixList->Lists);
	for(r=0;r<(pRadixList->NumLists);r++)
	{
		pRadixList->Lists[r] = List_Create();
		assert(pRadixList->Lists[r]);
	}
	pRadixList->Min = pRadixList->NumLists;
	pRadixList->Max = - 1;
return pRadixList;
}

void RadixList_Destroy(RadixList * pRadixList)
{
int r;
	assert(pRadixList);
	for(r=0;r<(pRadixList->NumLists);r++)
	{
		List_Destroy(pRadixList->Lists[r]);
	}
	MemFree(pRadixList->Lists);
	MemFree(pRadixList);
}

List * RadixList_Add(RadixList *pRadixList,void * Data,int Key)
{
List * l;
	assert(pRadixList);
	assert( Key < pRadixList->NumLists && Key >= 0 );
	l = List_AddTail(pRadixList->Lists[Key],Data);
	if ( Key < pRadixList->Min ) pRadixList->Min = Key;
	if ( Key > pRadixList->Max ) pRadixList->Max = Key;
return l;
}

void * RadixList_CutMax(RadixList *pRadixList,int *pKey)
{
	assert(pRadixList);

	while ( pRadixList->Max >= 0 )
	{
	void * Data;

		if ( Data = List_CutHead(pRadixList->Lists[pRadixList->Max]) )
		{
			if ( pKey ) *pKey = pRadixList->Max;
			return Data;	
		}
		pRadixList->Max --;

	}

return NULL;
}

void * RadixList_CutMin(RadixList *pRadixList,int *pKey)
{
	assert(pRadixList);

	while ( pRadixList->Min < pRadixList->NumLists )
	{
	void * Data;

		if ( Data = List_CutHead(pRadixList->Lists[pRadixList->Min]) )
		{
			if ( pKey ) *pKey = pRadixList->Min;
			return Data;	
		}
		pRadixList->Min ++;

	}

return NULL;
}

void * RadixList_CutKey(RadixList *pRadixList,int Key)
{
	assert(pRadixList);
return List_CutHead(pRadixList->Lists[Key]);
}

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

struct RadixLN
{
	int NumLNs;
	int Min,Max;
	LinkNode * LNs;
};

RadixLN * RadixLN_Create(int RadixLNMax)
{
RadixLN * pRadixLN;
LinkNode * LNs;
int r;
	pRadixLN = new(RadixLN);
	assert(pRadixLN);
	pRadixLN->NumLNs = RadixLNMax+1;
	pRadixLN->LNs = MemAlloc(sizeof(LinkNode)*(pRadixLN->NumLNs));
	assert(pRadixLN->LNs);

TIMER_P(List_RadixInit); // not counting the allocs, tracking in List_Ram

	LNs = pRadixLN->LNs;
	for(r=(pRadixLN->NumLNs);r--;LNs++)
	{
		// LN_InitList( LNs );
		LNs->Next = LNs->Prev = LNs;
	}
	pRadixLN->Min = RadixLNMax;
	pRadixLN->Max = 0;
	
TIMER_Q(List_RadixInit);

return pRadixLN;
}

void RadixLN_Destroy(RadixLN * pRadixLN)
{
	assert(pRadixLN);
	MemFree(pRadixLN->LNs);
	MemFree(pRadixLN);
}

void RadixLN_AddHead(RadixLN *pRadixLN,LinkNode *LN,int Key)
{
	assert(pRadixLN);
	assert( Key < pRadixLN->NumLNs && Key >= 0 );
	LN_AddHead(&(pRadixLN->LNs[Key]),LN);
	if ( Key < pRadixLN->Min ) pRadixLN->Min = Key;
	if ( Key > pRadixLN->Max ) pRadixLN->Max = Key;
}

void RadixLN_AddTail(RadixLN *pRadixLN,LinkNode *LN,int Key)
{
	assert(pRadixLN);
	assert( Key < pRadixLN->NumLNs && Key >= 0 );
	LN_AddTail(&(pRadixLN->LNs[Key]),LN);
	if ( Key < pRadixLN->Min ) pRadixLN->Min = Key;
	if ( Key > pRadixLN->Max ) pRadixLN->Max = Key;
}

LinkNode * RadixLN_CutMax(RadixLN *pRadixLN,int *pKey)
{
	assert(pRadixLN);

TIMER_P(List_RadixWalk);
	while ( pRadixLN->Max >= 0 )
	{
	LinkNode * LN;

		if ( LN = LN_CutHead(&(pRadixLN->LNs[pRadixLN->Max])) )
		{
			if ( pKey ) *pKey = pRadixLN->Max;
TIMER_Q(List_RadixWalk);
			return LN;
		}
		pRadixLN->Max --;
	}
TIMER_Q(List_RadixWalk);

return NULL;
}

LinkNode * RadixLN_CutMin(RadixLN *pRadixLN,int *pKey)
{
	assert(pRadixLN);

TIMER_P(List_RadixWalk);
	while ( pRadixLN->Min < pRadixLN->NumLNs )
	{
	LinkNode * LN;

		if ( LN = LN_CutHead(&(pRadixLN->LNs[pRadixLN->Min])) )
		{
			if ( pKey ) *pKey = pRadixLN->Max;
TIMER_Q(List_RadixWalk);
			return LN;
		}
		pRadixLN->Min ++;
	}
TIMER_Q(List_RadixWalk);

return NULL;
}

LinkNode * RadixLN_CutKey(RadixLN *pRadixLN,int Key)
{
	assert(pRadixLN);
return LN_CutHead(&(pRadixLN->LNs[Key]));
}


LinkNode * RadixLN_PeekMax(RadixLN *pRadixLN,int *pKey)
{
LinkNode * LNs;
	assert(pRadixLN);

TIMER_P(List_RadixWalk);
	LNs = & pRadixLN->LNs[pRadixLN->Max];
	while ( pRadixLN->Max >= 0 )
	{
	LinkNode * LN;

		LN = LNs->Next;
		if ( LN != LNs )
		{
			if ( pKey ) *pKey = pRadixLN->Max;
TIMER_Q(List_RadixWalk);
			return LN;
		}
		pRadixLN->Max --;
		LNs --;
	}
TIMER_Q(List_RadixWalk);

return NULL;
}

LinkNode * RadixLN_PeekMin(RadixLN *pRadixLN,int *pKey)
{
LinkNode * LNlist;
	assert(pRadixLN);

TIMER_P(List_RadixWalk);
	LNlist = & pRadixLN->LNs[pRadixLN->Min];
	while ( pRadixLN->Min < pRadixLN->NumLNs )
	{
	LinkNode * LN;

		LN = LNlist->Next;
		if ( LN != LNlist )
		{
			if ( pKey ) *pKey = pRadixLN->Min;
TIMER_Q(List_RadixWalk);
			return LN;
		}
		pRadixLN->Min ++;
		LNlist ++;
	}
TIMER_Q(List_RadixWalk);

return NULL;
}

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

struct RadixLink
{
	int NumLinks;
	int Min,Max;
	Link * Links;
};

RadixLink * RadixLink_Create(int RadixLinkMax)
{
RadixLink * pRadixLink;
	pRadixLink = new(RadixLink);
	assert(pRadixLink);
	pRadixLink->NumLinks = RadixLinkMax+1;
	pRadixLink->Links = MemAlloc(sizeof(Link)*(pRadixLink->NumLinks));
	assert(pRadixLink->Links);
	//memset(pRadixLink->Links,0,(sizeof(Link)*(pRadixLink->NumLinks)));
	pRadixLink->Min = pRadixLink->NumLinks;
	pRadixLink->Max = - 1;
return pRadixLink;
}

void RadixLink_Grow(RadixLink *pRadixLink,int NewMax)
{
Link * OldLinks;
int OldNumLinks;

	OldNumLinks = pRadixLink->NumLinks;
	OldLinks = pRadixLink->Links;

	pRadixLink->NumLinks = NewMax + 1;
	pRadixLink->Links = MemAlloc(sizeof(Link)*(pRadixLink->NumLinks));