list.c 8.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339
  1. #include "list.h"
  2. #include "string.h"
  3. #include <stdint.h>
  4. #include<string.h>
  5. #include <stdlib.h>
  6. #include<stdbool.h>
  7. #include "esp_heap_caps.h"
  8. //添加消息池,防止lora消息没发出去一直增加
  9. RTC_FAST_ATTR LORA_POOL_t lora_pool[LORA_INFO_END];
  10. #if 1
  11. Node *newNode(int x,int cmd,char *data,int len)
  12. #else
  13. Node *newNode(int x)
  14. #endif
  15. {
  16. #if 0
  17. Node *pnt = (Node *) malloc (sizeof(Node)); /* allocates physical memory for the node */
  18. #else
  19. Node *pnt = (Node *) heap_caps_malloc(sizeof(Node),MALLOC_CAP_RTCRAM); /* allocates physical memory for the node */
  20. #endif
  21. pnt -> n = x;
  22. /* inserts the information received as input in the field(s) in the list */
  23. /* entering additional information if necessary...
  24. * pnt -> b = y;
  25. * pnt -> c = z;
  26. * ... and so on
  27. */
  28. pnt -> cmd = cmd;
  29. #if 0
  30. pnt -> data = malloc(len);
  31. #else
  32. pnt -> data = heap_caps_malloc(len,MALLOC_CAP_RTCRAM);
  33. if(pnt -> data == NULL)
  34. {
  35. printf("-------pnt -> data == NULL-------\n");
  36. }
  37. #endif
  38. #include "string.h"
  39. memcpy(pnt -> data,data,len);
  40. pnt -> len = len;
  41. pnt -> next = NULL; /* initialize the pointer */
  42. /* an insert function will take care of properly setting the next variable */
  43. return pnt;
  44. }
  45. //cmd,data,len
  46. Node *preInsert(Node *top, int x,int cmd,char *data,int len) {
  47. Node *tmp = newNode(x,cmd,data,len); /* create a node with input information */
  48. tmp -> next = top; /* top corresponds to the first element of the list BEFORE this operation,
  49. * which provides to put "tmp" at the top of the list,
  50. * thus becoming the new "top" */
  51. return tmp; /* returns the new first element of the list */
  52. }
  53. Node *orderInsert(Node *top, int x,int cmd,char *data,int len) {
  54. if (top == NULL || top -> n > x) {
  55. /* if top == NULL is true then the element will be positioned at the bottom of the list,
  56. * if top -> n > x then the element will be positioned in the middle of the list.
  57. * OBSERVATION: the first condition is fundamental to the function of the function
  58. * while the second one can be modeled according to the needs, in this case the condition
  59. * top -> n > x imposes an increasing order of the elements of the list, but it could well
  60. * be top -> n < x if you wanted to insert elements in descending order. */
  61. Node *tmp = newNode(x,cmd,data,len); /* creates a node with the information entered as input */
  62. tmp -> next = top; /* points to the next node in the list */
  63. top = tmp; /* inserts the node in the list */
  64. return top;
  65. }
  66. else
  67. top -> next = orderInsert(top -> next, x,cmd,data,len); /* "scrolls" the list, examining the next node */
  68. return top;
  69. }
  70. Node *postInsert(Node *top, int x,int cmd,char *data,int len) {
  71. if (top == NULL)
  72. return newNode(x,cmd,data,len); /* inserts the item at the bottom of the list */
  73. else
  74. top -> next = postInsert(top -> next, x,cmd,data,len); /* if it is not at the bottom, move on */
  75. return top;
  76. }
  77. Node *findNode(Node *top, int k) {
  78. if (top == NULL || top -> n == k)
  79. return top; /* returns the found node (NULL if it was not found) */
  80. else
  81. return findNode(top -> next, k); /* scrolls the list to search for the item */
  82. }
  83. Node *deleteNode(Node *top, int k) {
  84. Node *tmp; /* temporary node */
  85. if (top != NULL) {
  86. if (top -> n == k) { /* if the element was found, it is deleted */
  87. top -> n = 0;
  88. top -> cmd= 0;
  89. memset(top ->data,0x00,top -> len);
  90. top -> len = 0;
  91. // 释放一个已分配的msgid_num
  92. deallocateMsgIdNum(top->n);
  93. tmp = top -> next; /* set the temporary node to the next element (in order not to "lose" the list) */
  94. heap_caps_free(top->data);//释放data
  95. heap_caps_free(top); /* frees the physical memory associated with the node to be deleted */
  96. top = tmp; /* set the pointer to the next node */
  97. }
  98. else
  99. top -> next = deleteNode(top -> next, k); /* scrolls the list in order to search the item to be deleted */
  100. }
  101. return top;
  102. }
  103. Node *deleteNode_head(Node *top) {
  104. Node *tmp; /* temporary node */
  105. if (top != NULL) {
  106. if (1)
  107. { /* if the element was found, it is deleted */
  108. // 释放一个已分配的msgid_num
  109. deallocateMsgIdNum(top->n);
  110. tmp = top -> next; /* set the temporary node to the next element (in order not to "lose" the list) */
  111. //free(top->data);//释放data
  112. free(top); /* frees the physical memory associated with the node to be deleted */
  113. top = tmp; /* set the pointer to the next node */
  114. }
  115. else
  116. top -> next = deleteNode_head(top -> next); /* scrolls the list in order to search the item to be deleted */
  117. }
  118. return top;
  119. }
  120. Node *deleteList(Node *top) {
  121. if (top != NULL) { /* if not reached end of the list... */
  122. deleteList(top -> next); /* ...move on */
  123. //free(top->data);
  124. free(top); /* delete the node */
  125. return NULL;
  126. }
  127. //else
  128. return NULL;
  129. }
  130. // 函数用于复制链表
  131. Node* copyList( Node* originalList) {
  132. if (originalList == NULL) {
  133. return NULL;
  134. }
  135. Node* current = originalList; // 用于遍历原链表
  136. Node* newList = NULL; // 新链表的头节点
  137. Node* tail = NULL; // 新链表的尾节点
  138. // 遍历原链表
  139. while (current != NULL) {
  140. // 创建新节点
  141. Node* newNode = (Node*)malloc(sizeof(Node));
  142. newNode->n = current->n;
  143. newNode->cmd = current->cmd;
  144. newNode->len = current->len;
  145. newNode->data = malloc(current->len);
  146. memcpy(newNode->data,current->data,current->len);
  147. newNode->next = NULL;
  148. // 如果新链表为空,设置新链表的头节点
  149. if (newList == NULL) {
  150. newList = newNode;
  151. tail = newNode;
  152. } else {
  153. // 否则,将新节点连接到新链表的尾部
  154. tail->next = newNode;
  155. tail = newNode;
  156. }
  157. current = current->next;
  158. }
  159. return newList; // 返回新链表的头节点
  160. }
  161. void printList(Node *top) {
  162. if (top != NULL) {
  163. printf("n=%d ", top -> n);
  164. printf(" data=%s", top -> data);
  165. printf(" len=%d\r\n", top -> len);
  166. printList(top -> next);
  167. }
  168. else
  169. printf("NULL\n");
  170. }
  171. void MergeSort(Node **top) {
  172. Node *tmp = *top, *a, *b;
  173. if (tmp != NULL && tmp -> next != NULL) {
  174. Split(tmp, &a, &b); /* (divide) split head into "a" and "b" sublists */
  175. /* (conquer) sort the sublists */
  176. MergeSort(&a);
  177. MergeSort(&b);
  178. *top = Merge(a, b); /* (combine) merge the two sorted lists together */
  179. }
  180. }
  181. Node* Merge(Node *top1, Node *top2) {
  182. if (top1 == NULL)
  183. return top2;
  184. else
  185. if (top2 == NULL)
  186. return top1;
  187. Node* pnt = NULL;
  188. /* pick either top1 or top2, and merge them */
  189. if (top1 -> n <= top2 -> n) {
  190. pnt = top1;
  191. pnt -> next = Merge(top1 -> next, top2);
  192. }
  193. else {
  194. pnt = top2;
  195. pnt -> next = Merge(top1, top2 -> next);
  196. }
  197. return pnt;
  198. }
  199. void Split(Node *top, Node **front, Node **back) {
  200. Node* fast = top -> next;
  201. Node* slow = top;
  202. /* fast pointer advances two nodes, slow pointer advances one node */
  203. while (fast != NULL) {
  204. fast = fast -> next; /* "fast" moves on first time */
  205. if (fast != NULL) {
  206. slow = slow -> next; /* "slow" moves on first time */
  207. fast = fast -> next; /* "fast" moves on second time */
  208. }
  209. }
  210. /* "slow" is before the middle in the list, so split it in two at that point */
  211. *front = top;
  212. *back = slow -> next;
  213. slow -> next = NULL; /* end of the input list */
  214. }
  215. int countNodes(Node *top) {
  216. if (top == NULL)
  217. return 0;
  218. else
  219. return 1 + countNodes(top -> next);
  220. }
  221. int countClockNodes_byCMD(Node *top,char type_cmd)
  222. {
  223. if (top == NULL)
  224. return 0;
  225. else
  226. {
  227. if(top->cmd == type_cmd)
  228. return 1 + countClockNodes_byCMD(top->next,type_cmd);
  229. else
  230. return countClockNodes_byCMD(top->next,type_cmd);
  231. }
  232. }
  233. bool msgidNumAllocated[MAX_MSG_ID_NUM] = {false};
  234. // 分配一个可用的msgid_num
  235. int allocateMsgIdNum() {
  236. for (int i = 1; i <= MAX_MSG_ID_NUM; i++) {
  237. if (!msgidNumAllocated[i - 1]) {
  238. msgidNumAllocated[i - 1] = true; // 标记为已分配
  239. return i;
  240. }
  241. }
  242. return -1; // 没有可用的msgid_num
  243. }
  244. // 释放一个已分配的msgid_num
  245. void deallocateMsgIdNum(int idNum) {
  246. if (idNum >= 1 && idNum <= MAX_MSG_ID_NUM) {
  247. msgidNumAllocated[idNum - 1] = false; // 标记为未分配
  248. }
  249. }
  250. void wait_Send_Data_Insert(int msgid,uint8_t *data,int len)
  251. {
  252. }
  253. void wait_Send_Data_Delete(int msgid)
  254. {
  255. }