색인 기반 범용 대기 열 구축 및 구현 (C 언어 구현)

8323 단어 ProgramTheory
실제 삽입 식 응용 프로 그래 밍 에서 우 리 는 대기 열 이라는 데이터 구 조 를 자주 사용 합 니 다. 대기 열의 상용 동작 은 대기 열의 초기 화 (Init), 대기 열의 요소 추가 (Add), 대기 열의 요소 삭제 (Del), 대기 열의 요소 분배 (Malloc), 대기 열의 요소 소각 (Free), 대기 열의 반복 순환 (Poll) 이 있 습 니 다. 그 중에서 대기 열의 요소 분배 (Malloc) 와 소각 (Free),일반적인 원 리 는 우리 가 먼저 하나의 요소 유형 배열 (NodeHeapArray [NODE HEAP ARRAY MAX]) 을 기본적으로 정의 하 는 것 이다. 이 요소 유형 배열 은 바로 기본 적 인 우리 응용 시스템 의 고유 자원 이다. 이런 자원 은 신청 되 고 회수 할 수 있다.대기 열의 조작 은 기본적으로 매우 통용 되 기 때문에 가장 자주 사용 하 는 조작 시작 은 구체 적 인 유형의 요소 대상 을 대상 으로 요소 대상 의 속성 과 내용 에 대해 조작 하 는 것 이다. 이런 조작 인 터 페 이 스 는 다 형 성 을 가지 고 응용 층 인 터 페 이 스 를 고려 해 야 하 며 통용 되 는 대기 열 조작 인 터 페 이 스 는 통일 되 고 명확 하 다.따라서 우 리 는 일반적인 이러한 대기 열 유형 을 추상 화한 다음 에 이러한 유형의 대기 열의 유 니 버 설 조작 인터페이스 (Init, Add, Del, Malloc, Free) 를 구체 적 으로 실현 하여 코드 의 불필요 한 작성 량 을 줄 이 고 버그 가 발생 할 확률 을 확보 할 수 있 습 니 다.
    현재 우 리 는 색인 을 기반 으로 옮 겨 다 니 고 연결 하 는 배열 의 범 형 대기 열 (BASE LIST) 을 만 들 수 있 습 니 다. 이러한 범 형 대기 열 은 여러 가지 유형의 노드 요 소 를 호 환 할 수 있 습 니 다. 구체 적 인 노드 유형 요소 의 조작 인 터 페 이 스 는 사용자 가 단독으로 맞 춤 형 으로 실현 할 수 있 기 때문에 BASE 에 영향 을 주지 않 습 니 다.LIST；
    구체 적 인 실현 코드 는 다음 과 같다.
My_Typedef. h 파일
// ----------------------------------- My_Typedef.h --------------------------------------------------



#ifndef  _MY_TYPEDF_H_

#include 

#include 

#include 

#include 

typedef unsigned char 				u8;
typedef unsigned short 				u16;
typedef unsigned int 				u32; 

#endif

Base_List. h 파일
// ----------------------------------- Base_List.h --------------------------------------------------

#ifndef _BASE_LIST_H_
#define _BASE_LIST_H_

#include "My_Typedef.h"

#define NODE_HEAD_INDEX 								    0x00000000
#define NODE_TAIL_INDEX 								    0xFFFFFFFF
#define NODE_FLAG_USED								    0x00000001

typedef struct _BASE_NODE_T{
	u32 PrevIndex;
	u32 NextIndex;
	u32 NodeFlag;
}BASE_NODE_T;

typedef struct _BASE_NODEHEAP_T{
	u32 NodeAmount;
	u32 CurIndex;
	//   NodeHeap[]  
}BASE_NODEHEAP_T;

typedef struct _BASE_LIST_T{
	u32 ListSize;
	u32 HeadIndex;
	u32 TailIndex;
	u32 NodeSize;
	u32 HeapMax;
	//    LIST Heap    
}BASE_LIST_T;

int 	BaseList_Init(BASE_LIST_T* pList, u32 NodeSize, u32 HeapMax);                        //                
int 	BaseList_Add(BASE_LIST_T* pList, u32* pIndex);                                                 //                 

void 	BaseList_Del(BASE_LIST_T* pList, u32 Index);                                                      //                 

#endif

Base_List. c 파일
// ----------------------------------- Base_List.c --------------------------------------------------

#include "Base_List.h"


int BaseNode_Malloc(BASE_NODEHEAP_T* pHeap, u32* pIndex, u32 NodeSize, u32 HeapMax)
{
	// Heap         Index = 0x00000000 Index = 0xFFFFFFFF    
	void* pHeapArray = NULL;
	BASE_NODE_T* pBaseNode = NULL;
	u32 index = 0;


	if(pHeap->NodeAmount >= (HeapMax-2))
	{
		return -1;									//             
	}
	
	if(pHeap->NodeAmount == 0)
	{
		// Heap          
		pHeap->NodeAmount = 1;
		pHeap->CurIndex = 1;						//      
		pHeapArray = pHeap + sizeof(u32)*2;			//   NodeHeap  
		pBaseNode = (BASE_NODE_T*)pHeapArray;
		memset((void*)pBaseNode, 0, NodeSize);		//          
		pBaseNode->NodeFlag = NODE_FLAG_USED;		//              
		*pIndex = pHeap->CurIndex;
		return 0;									//        0
	}
	else
	{
		index = pHeap->CurIndex;
		if(index == 0 || index >= HeapMax)
		{
			index = 1;
		}
		
		pHeapArray = pHeap + sizeof(u32)*2 + index*NodeSize;		//   NodeHeap  
		pBaseNode = (BASE_NODE_T*)pHeapArray;
		while(pBaseNode->NodeFlag&NODE_FLAG_USED)
		{
			index++;
			if(index==0 || index >= HeapMax)
			{
				index = 0;
			}
			pHeapArray = pHeap + sizeof(u32)*2 + index*NodeSize;		//   NodeHeap  
			pBaseNode = (BASE_NODE_T*)pHeapArray;
		}


		pHeap->NodeAmount++;
		pHeap->CurIndex = index;
		memset((void*)pBaseNode, 0, NodeSize);		//          
		pBaseNode->NodeFlag = NODE_FLAG_USED;		//              
		*pIndex = pHeap->CurIndex;
		return 0;									//        0
	}
}


void BaseNode_Free(BASE_NODEHEAP_T* pHeap, u32 Index, u32 NodeSize, u32 HeapMax)
{
	void* pHeapArray = NULL;
	BASE_NODE_T* pBaseNode = NULL;
	u32 index = 0;
	
	if(pHeap->NodeAmount == 0)
	{
		return;
	}


	if((Index == 0) && (Index >= HeapMax))
	{
		return;
	}


	pHeapArray = pHeap + sizeof(u32)*2 + Index*NodeSize;		//   NodeHeap  
	pBaseNode = (BASE_NODE_T*)pHeapArray;
	if(pBaseNode->NodeFlag&NODE_FLAG_USED)
	{
		//         Free 
		memset((void*)pBaseNode, 0, NodeSize);
		pHeap->NodeAmount--;
	}
	return;
}


int BaseList_Init(BASE_LIST_T* pList, u32 NodeSize, u32 HeapMax)
{
	BASE_NODEHEAP_T* pHeap = NULL;
	void* pVoid = (void*)pList;
	void* pHeapArray = NULL;
	u32 i = 0;
	pList->ListSize = 0;
	pList->NodeSize = NodeSize;
	pList->HeapMax = HeapMax;
	pList->HeadIndex = 0;
	pList->TailIndex = 0;
	pHeap = (BASE_NODEHEAP_T*)(pVoid+sizeof(u32)*5);
	pHeapArray = pHeap + sizeof(u32)*2;
	pHeap->NodeAmount = 0;
	pHeap->CurIndex = 0;
	memset((void*)pHeapArray, 0, NodeSize*HeapMax);
	return;
}


int BaseList_Add(BASE_LIST_T* pList, u32* pIndex)
{
	u32 NodeSize = pList->NodeSize;
	u32 HeapMax = pList->HeapMax;
	int Ret = 0;
	BASE_NODEHEAP_T* pHeap = NULL;
	BASE_NODE_T* pBaseNode = NULL;
	BASE_NODE_T* pTailNode = NULL;
	void* pVoid = (void*)pList;
	u32 Index = 0;
	pHeap = (BASE_NODEHEAP_T*)(pVoid+sizeof(u32)*5);
	//         
	Ret = BaseNode_Malloc(pHeap, &Index, NodeSize, HeapMax);
	if(Ret < 0)
	{
		//            
		return -1;
	}
	//                        
	pBaseNode = (BASE_NODE_T*)(pHeap+sizeof(u32)*2+Index*NodeSize);
	if(pList->ListSize == 0)
	{
		//      
		pList->ListSize = 1;
		pList->HeadIndex = Index;
		pList->TailIndex = Index;		
		pBaseNode->PrevIndex = NODE_HEAD_INDEX;
		pBaseNode->NextIndex = NODE_TAIL_INDEX;
		*pIndex = Index;
		return 0;
	}
	else
	{
		//      
		pList->ListSize++;
		pTailNode = (BASE_NODE_T*)(pHeap+sizeof(u32)*2+pList->TailIndex*NodeSize);
		pTailNode->NextIndex = Index;
		pBaseNode->PrevIndex = pList->TailIndex;
		pBaseNode->NextIndex = NODE_TAIL_INDEX;
		pList->TailIndex = Index;
		*pIndex = Index;
		return 0;
	}
}


void BaseList_Del(BASE_LIST_T* pList, u32 Index)
{
	BASE_NODEHEAP_T* pHeap = NULL;
	void* pVoid = (void*)pList;
	BASE_NODE_T* pBaseNode = NULL;
	BASE_NODE_T* pNextNode = NULL;
	BASE_NODE_T* pPrevNode = NULL;
	u32 NodeSize = pList->NodeSize;
	u32 HeapMax = pList->HeapMax;
	u32 NextIndex = 0;
	u32 PrevIndex = 0;
	
	if(pList->ListSize == 0)
	{
		//                   
		return;
	}
	
	pHeap = (BASE_NODEHEAP_T*)(pVoid+sizeof(u32)*5);
	pBaseNode = (BASE_NODE_T*)(pHeap+sizeof(u32)*2+Index*NodeSize);
	//        
	if(!(pBaseNode->NodeFlag&NODE_FLAG_USED))
	{
		//                  
		return;
	}


	//            
	if(pBaseNode->PrevIndex == NODE_HEAD_INDEX)		//    
	{
		if(pBaseNode->NextIndex == NODE_TAIL_INDEX)	//    
		{
			//            
			pList->ListSize = 0;
			pList->HeadIndex = 0;
			pList->TailIndex = 0;
		}
		else
		{
			NextIndex = pBaseNode->NextIndex;
			pNextNode = (BASE_NODE_T*)(pHeap+sizeof(u32)*2+NextIndex*NodeSize);
			pNextNode->PrevIndex = NODE_HEAD_INDEX;
			pList->HeadIndex = NextIndex;
			pList->ListSize--;
		}
	}
	else if(pBaseNode->NextIndex == NODE_TAIL_INDEX)	//    
	{
		if(pBaseNode->PrevIndex == NODE_HEAD_INDEX)		//    
		{
			//            
			pList->ListSize = 0;
			pList->HeadIndex = 0;
			pList->TailIndex = 0;
		}
		else
		{
			PrevIndex = pBaseNode->PrevIndex;
			pPrevNode = (BASE_NODE_T*)(pHeap+sizeof(u32)*2+PrevIndex*NodeSize);
			pPrevNode->NextIndex = NODE_TAIL_INDEX;
			pList->TailIndex = PrevIndex;
			pList->ListSize--;
		}
	}
	else
	{
		//             
		NextIndex = pBaseNode->NextIndex;
		pNextNode = (BASE_NODE_T*)(pHeap+sizeof(u32)*2+NextIndex*NodeSize);
		PrevIndex = pBaseNode->PrevIndex;
		pPrevNode = (BASE_NODE_T*)(pHeap+sizeof(u32)*2+PrevIndex*NodeSize);
		pNextNode->PrevIndex = PrevIndex;
		pPrevNode->NextIndex = NextIndex;
		pList->ListSize--;
	}


	//  Heap       
	BaseNode_Free(pHeap, Index, NodeSize, HeapMax);
	return ;
}

후기 에는 편리 하 게 사용 할 수 있 도록 응용 절 차 를 제시 할 것 이다.
입력 및 출력이 있는 저장 프로세스 만들기
PTA 데이터 구조 - 06 - 그림 1 연결 집합 목록

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage