yc_client/components/c_linked_list/list.c

#include "list.h"
#include "string.h"
#include <stdint.h>
#include<string.h>
#include <stdlib.h>
#include<stdbool.h>
#include "esp_heap_caps.h"

#if 1
Node *newNode(int x,int cmd,char *data,int len) 
#else
Node *newNode(int x) 
#endif
{
	

	#if 0
	Node *pnt = (Node *) malloc (sizeof(Node)); /* allocates physical memory for the node */
	#else
	Node *pnt = (Node *) heap_caps_malloc(sizeof(Node),MALLOC_CAP_RTCRAM); /* allocates physical memory for the node */
	#endif
	
	pnt -> n = x;  
	                             /* inserts the information received as input in the field(s) in the list */
	/* entering additional information if necessary...
	 * pnt -> b = y;
	 * pnt -> c = z;
	 * ... and so on
	 */

	pnt -> cmd = cmd;
	#if 0
	pnt -> data = malloc(len);
	#else
	pnt -> data = heap_caps_malloc(len,MALLOC_CAP_RTCRAM);
	if(pnt -> data == NULL)
	{
		printf("-------pnt -> data == NULL-------\n");
	}
	#endif

	#include "string.h"
	memcpy(pnt -> data,data,len);

	pnt -> len = len;
	pnt -> next = NULL;                         /* initialize the pointer */
	/* an insert function will take care of properly setting the next variable */
	return pnt;
}

//cmd,data,len

Node *preInsert(Node *top, int x,int cmd,char *data,int len) {
	Node *tmp = newNode(x,cmd,data,len);						/* create a node with input information */
	tmp -> next = top;							/* top corresponds to the first element of the list BEFORE this operation,
												 * which provides to put "tmp" at the top of the list,
												 * thus becoming the new "top" */
	return tmp;									/* returns the new first element of the list */
}

Node *orderInsert(Node *top, int x,int cmd,char *data,int len) {
	if (top == NULL || top -> n > x) {
		/* if top == NULL is true then the element will be positioned at the bottom of the list,
		 * if top -> n > x then the element will be positioned in the middle of the list.
		 * OBSERVATION: the first condition is fundamental to the function of the function
		 * while the second one can be modeled according to the needs, in this case the condition
		 * top -> n > x imposes an increasing order of the elements of the list, but it could well
		 * be top -> n < x if you wanted to insert elements in descending order. */
		Node *tmp = newNode(x,cmd,data,len);						/* creates a node with the information entered as input */
		tmp -> next = top;							/* points to the next node in the list */
		top = tmp;									/* inserts the node in the list */
		return top;
	}
	else
		top -> next = orderInsert(top -> next, x,cmd,data,len);	/* "scrolls" the list, examining the next node */
	return top;
}

Node *postInsert(Node *top, int x,int cmd,char *data,int len) {
	if (top == NULL)
		return newNode(x,cmd,data,len);							/* inserts the item at the bottom of the list */
	else
		top -> next = postInsert(top -> next, x,cmd,data,len);	/* if it is not at the bottom, move on */
	return top;
}

Node *findNode(Node *top, int k) {
	if (top == NULL || top -> n == k)
		return top;							/* returns the found node (NULL if it was not found) */
	else
		return findNode(top -> next, k);	/* scrolls the list to search for the item */
}

Node *deleteNode(Node *top, int k) {
	Node *tmp;					/* temporary node */
	if (top != NULL) {
		if (top -> n == k) {	/* if the element was found, it is deleted */


			top -> n = 0;
			top -> cmd= 0;
			memset(top ->data,0x00,top -> len);
			top -> len = 0;

			// 释放一个已分配的msgid_num
		    deallocateMsgIdNum(top->n); 
			tmp = top -> next;	/* set the temporary node to the next element (in order not to "lose" the list) */
			heap_caps_free(top->data);//释放data
			heap_caps_free(top);			/* frees the physical memory associated with the node to be deleted */
			top = tmp;			/* set the pointer to the next node */
		}
		else
			top -> next = deleteNode(top -> next, k);	/* scrolls the list in order to search the item to be deleted */
	}
	return top;
}



Node *deleteNode_head(Node *top) {
	Node *tmp;					/* temporary node */
	if (top != NULL) {
		 if (1)
		 {	/* if the element was found, it is deleted */
			// 释放一个已分配的msgid_num
		    deallocateMsgIdNum(top->n); 
			tmp = top -> next;	/* set the temporary node to the next element (in order not to "lose" the list) */
			//free(top->data);//释放data
			free(top);			/* frees the physical memory associated with the node to be deleted */
			top = tmp;			/* set the pointer to the next node */
		}
		else
			top -> next = deleteNode_head(top -> next);	/* scrolls the list in order to search the item to be deleted */
	}
	return top;
}





Node *deleteList(Node *top) {
	if (top != NULL) {				/* if not reached end of the list... */
		deleteList(top -> next);	/* ...move on */
		//free(top->data);
		free(top);					/* delete the node */
		return NULL;
	}
	//else
		return NULL;
}




// 函数用于复制链表
 Node* copyList( Node* originalList) {
    if (originalList == NULL) {
        return NULL;
    }

     Node* current = originalList; // 用于遍历原链表
     Node* newList = NULL;         // 新链表的头节点
     Node* tail = NULL;            // 新链表的尾节点

    // 遍历原链表
    while (current != NULL) {
        // 创建新节点
         Node* newNode = (Node*)malloc(sizeof(Node));

		newNode->n = current->n; 
		newNode->cmd = current->cmd; 
		newNode->len = current->len; 
        newNode->data = malloc(current->len);
		memcpy(newNode->data,current->data,current->len);
	
        newNode->next = NULL;

        // 如果新链表为空，设置新链表的头节点
        if (newList == NULL) {
            newList = newNode;
            tail = newNode;
        } else {
            // 否则，将新节点连接到新链表的尾部
            tail->next = newNode;
            tail = newNode;
        }

        current = current->next;
    }

    return newList; // 返回新链表的头节点
}


void printList(Node *top) {
	if (top != NULL) {
		printf("n=%d ", top -> n);
		printf(" data=%s", top -> data);
		printf("  len=%d\r\n", top -> len);
		printList(top -> next);
	}
	else
		printf("NULL\n");
}

void MergeSort(Node **top) {
	Node *tmp = *top, *a, *b;

    if (tmp != NULL && tmp -> next != NULL) {
		Split(tmp, &a, &b);				/* (divide) split head into "a" and "b" sublists */
	  
		/* (conquer) sort the sublists */
		MergeSort(&a); 
		MergeSort(&b); 
	  
		*top = Merge(a, b);				/* (combine) merge the two sorted lists together */
	}
} 

Node* Merge(Node *top1, Node *top2) {
    if (top1 == NULL) 
		return top2; 
    else
		if (top2 == NULL) 
			return top1;   

    Node* pnt = NULL;
    /* pick either top1 or top2, and merge them */
    if (top1 -> n <= top2 -> n) { 
		pnt = top1;
		pnt -> next = Merge(top1 -> next, top2); 
    } 
    else {
        pnt = top2; 
        pnt -> next = Merge(top1, top2 -> next); 
    }
    return pnt; 
} 

void Split(Node *top, Node **front, Node **back) {
	Node* fast = top -> next;
	Node* slow = top;

    /* fast pointer advances two nodes, slow pointer advances one node */
	while (fast != NULL) {
		fast = fast -> next;		/* "fast" moves on first time */
		if (fast != NULL) { 
			slow = slow -> next;	/* "slow" moves on first time */
			fast = fast -> next;	/* "fast" moves on second time */
        }
    }
	
    /* "slow" is before the middle in the list, so split it in two at that point */
	*front = top;
	*back = slow -> next;
	slow -> next = NULL;			/* end of the input list */
}

int countNodes(Node *top) {
    if (top == NULL)
        return 0;
    else
        return 1 + countNodes(top -> next);
}

int countClockNodes_byCMD(Node *top,char type_cmd) 
{   
    if (top == NULL)
        return 0;
    else
    {
        if(top->cmd == type_cmd)
            return 1 + countClockNodes_byCMD(top->next,type_cmd);
        else
            return countClockNodes_byCMD(top->next,type_cmd);
    }   
}




















bool msgidNumAllocated[MAX_MSG_ID_NUM] = {false};


// 分配一个可用的msgid_num
int allocateMsgIdNum() {
    for (int i = 1; i <= MAX_MSG_ID_NUM; i++) {
        if (!msgidNumAllocated[i - 1]) {
            msgidNumAllocated[i - 1] = true; // 标记为已分配
            return i;
        }
    }
    return -1; // 没有可用的msgid_num
}

// 释放一个已分配的msgid_num
void deallocateMsgIdNum(int idNum) {
    if (idNum >= 1 && idNum <= MAX_MSG_ID_NUM) {
        msgidNumAllocated[idNum - 1] = false; // 标记为未分配
    }
}



void wait_Send_Data_Insert(int msgid,uint8_t *data,int len)
{

}




void wait_Send_Data_Delete(int msgid)
{
    
}