需要慢速插入链表多线程吗？ [英] Slow Inserts Linked List multi-threading needed?
本文介绍了需要慢速插入链表多线程吗？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
在下面的代码中，我正在寻找方法来优化当时处理数百万个刀片的插入速度。该代码运行良好，但是在执行大量插入时非常慢。我已经尝试过一些想法，但是总是很慢。我猜解决方案是使用多线程执行插入，并使用全局变量 truct Node * nodeObj。
我对C，C ++中的多线程和同步经验很少/没有经验，如果您能根据下面的代码给我一个例子，我将不胜感激。
欢迎其他任何想法。
规则是：
1-最后（在插入所有数字之后）必须对链接列表进行排序，这意味着每个Node-> data的起始编号从最低编号到最大编号。
2-调用者正在使用for循环，此for循环无法在Insert函数内启动。
3-任何代码，调用者或插入函数都可以优化，只要插入函数不会自行自行添加插入，那就是调用者的工作。
＃include< stdio.h>
＃include< stdlib.h>
＃include< conio.h>
结构节点{
int数据；
struct Node * nextAddr;
};
struct Node * Insert（Node * p，int data）;
void Print（struct Node * p）;
void RevPrint（struct Node * p）;
int main（）{
struct Node * nodeObj = NULL;
printf（ --------------------------------- \n
插入（）\n --------------------------------- \n）；
for（int i = 1; i <1000000; i ++）{
nodeObj = Insert（nodeObj，i）;
printf（％d，i）;
}
printf（ \n --------------------------------- \ n
Print（）\n --------------------------------- \n ）;
Print（nodeObj）;
printf（ --------------------------------- \n
RevPrint （）\n ---------------------------------）;
RevPrint（nodeObj）;
printf（ \n按任意键继续...）;
_getch（）;
}
结构节点* Insert（Node * _pToNode，int _nbr）
{
Node * newValue =（struct Node *）malloc（sizeof（struct Node） ）;
newValue-> data = _nbr;
newValue-> nextAddr = NULL;
如果（_pToNode == NULL）_pToNode = newValue;
else {
Node * pLocal = _pToNode;
而（pLocal-> nextAddr！= NULL）{
pLocal = pLocal-> nextAddr;
}
pLocal-> nextAddr = newValue;
}
return _pToNode;
}
void Print（struct Node * p）{
if（p == NULL）{
printf（ \n） ;
的回报；
}
printf（％d，p-> data）;
Print（p-> nextAddr）;
}
void RevPrint（struct Node * p）{
if（p == NULL）{
printf（ \n） ;
的回报；
}
RevPrint（p-> nextAddr）;
printf（％d，p-> data）;
}
谢谢。
解决方案
注意：仅适用于尾部插入/附加：
int
main（）
{
struct Node * nodeObj = NULL;
struct Node * nodeTail = NULL;
//您的其他东西...
for（int i = 1; i <1000000; i ++）{
nodeObj = Insert（nodeObj，& ; nodeTail，i）;
printf（％d，i）;
}
//您的其他东西...
}
struct Node * Insert（Node * _pToNode，Node ** tail，int _nbr ）
{
Node * newValue =（struct Node *）malloc（sizeof（struct Node））;
newValue-> data = _nbr;
newValue-> nextAddr = NULL;
if（_pToNode == NULL）{
_pToNode = newValue;
}
else {
（* tail）-> nextAddr = newValue;
}
* tail = newValue;
return _pToNode;
}
您可以使用列表结构清理该结构，该结构具有两个头部
更新：
很酷/很聪明，但不幸的是仍然很慢...
malloc 等。等大量小分配可能会很慢。一种加快处理速度的方法是使用分配的子池（如WeatherVane所建议的那样。）
正如我提到的，添加列表结构可以使处理起来更加整洁在两个地方使用过它。承诺之后，您可以添加头/尾以外的其他内容，例如计数。另外，如果您愿意的话，将来也可以很容易地从单链接列表转换为双链接列表。
旁注：使用双向链接的列表，插入会[稍微]复杂一些，但是在列表的中间中的插入要快得多，因为您不必遍历列表即可找到前一个指针（例如，节点中将具有 prev 指针）。而且， RevPrintList 会变得与 PrintList 一样简单。
请注意，[在我的系统上]反向打印用完了堆栈空间[并且已分段存储]，所以我将打印功能重新编码为不是递归的。
这是一个清理后的版本，由于单独的 malloc 调用数量减少，因此插入速度应更快。
旁注：我没有为 malloc 等添加必需的检查，等等，返回空值。
#include< stdio.h>
#include< stdlib.h>
//＃include< conio.h>
typedef struct Node_ {
int数据；
struct Node_ *接下来；
}节点；
typedef struct List_ {
int count;
Node *头；
Node *尾；
}清单；
Node * NewNode（void）;
Node * Insert（List * p，int data）;
void Print（Node * p）;
void PrintList（List * list）;
void RevPrint（Node * p）;
void RevPrintList（List * list）;
列出自由列表；
int
main（）
{
List nodelist = {0，NULL，NULL};
printf（ --------------------------------- \n
Insert（）\n --------------------------------- \n）;
for（int i = 1; i <1000000; i ++）{
Insert（& nodelist，i）;
#if 0
printf（％d，i）;
#endif
}
printf（ \n ------------------------- -------- \n
Print（）\n --------------------------- ------ \n）;
#if 0
打印（nodelist.head）;
#else
PrintList（& nodelist）;
#endif
printf（ --------------------------------- \n
RevPrint（）\n ---------------------------------） ;
#if 0
RevPrint（nodelist.head）;
#else
RevPrintList（& nodelist）;
#endif
printf（ \n按任意键继续...）;
#if 0
_getch（）;
#else
getchar（）;
#endif
}
节点*
NewNode（void）
{
Node * node;
//注意：将计数设置（例如1000）调整为想要的值
if（freelist.count< = 0）{
freelist.count = 1000 ;
freelist.head = calloc（freelist.count，sizeof（Node））;
}
node = freelist.head ++;
freelist.count-= 1;
返回节点；
}
Node *
Insert（List * list，int _nbr）
{
Node * node = NewNode（）;
node-> data = _nbr;
node-> next = NULL;
if（list-> head == NULL）{
list-> head = node;
}
else {
list-> tail-> next =节点；
}
list-> tail =节点；
list-> count + = 1;
返回节点；
}
void
Print（Node * p）
{
if（p == NULL）{
printf （ \n）;
的回报；
}
printf（％d，p-> data）;
Print（p-> next）;
}
void
PrintList（List * list）
{
Node * node;
for（node = list-> head; node！= NULL; node = node-> next）
printf（％d，node-> data）;
printf（ \n）;
}
void
RevPrint（Node * p）
{
if（p == NULL）{
printf （ \n）;
的回报；
}
RevPrint（p-> next）;
printf（％d，p-> data）;
}
void
RevPrintList（List * list）
{
Node ** rlist = malloc（sizeof（Node **）* list-> ;计数）;
节点* node;
int ridx;
ridx = list-> count-1;
用于（node = list-> head; node！= NULL; node = node-> next，--ridx）
rlist [ridx] = node;
for（ridx = 0; ridx< list-> count; ++ ridx）{
node = rlist [ridx];
printf（％d，node-> data）;
}
printf（ \n）;
free（rlist）;
}
更新＃ 2：
您可以使freeList成为列表列表（使用不同的 node结构，该结构具有指向列表而不是数字），以便在程序完成后释放内存。
这里是修改版本：
#include< stdio.h>
#include< stdlib.h>
//＃include< conio.h>
typedef struct Node_ {
int数据；
struct Node_ *接下来；
}节点；
typedef struct List_ {
int count;
Node *头；
Node *尾；
}清单；
typedef struct Freelist_ {
int count;
Node *头；
Node *尾；
个节点*可用；
} FreeList;
Node * NewNode（void）;
Node * Insert（List * p，int data）;
void Print（Node * p）;
void PrintList（List * list）;
void RevPrint（Node * p）;
void RevPrintList（List * list）;
void FreeAll（void）;
FreeList freelist = {0};
int
main（）
{
List nodelist = {0，NULL，NULL};
printf（ --------------------------------- \n
Insert（）\n --------------------------------- \n）;
for（int i = 1; i <1000000; i ++）{
Insert（& nodelist，i）;
//这个printf会从根本上减慢
#if 0
printf（％d，i）;的速度。
#endif
}
printf（ \n ------------------------- -------- \n
Print（）\n --------------------------- ------ \n）;
#if 0
打印（nodelist.head）;
#else
PrintList（& nodelist）;
#endif
printf（ --------------------------------- \n
RevPrint（）\n ---------------------------------） ;
#if 0
RevPrint（nodelist.head）;
#else
RevPrintList（& nodelist）;
#endif
//将所有节点释放回malloc空闲池
FreeAll（）;
printf（ \n按任意键继续...）;
#if 0
_getch（）;
#else
getchar（）;
#endif
}
节点*
NewNode（void）
{
Node * node;
//注意：将计数设置（例如1000）调整为想要的值
if（freelist.count< = 0）{
freelist.count = 1000 ;
node = calloc（freelist.count，sizeof（Node））;
//维护位于
_start_处的节点的链表// malloc区域/区域
if（freelist.head == NULL）
freelist .head =节点;
else
freelist.tail-> next =节点；
freelist.tail =节点；
//将第一个节点刻录为占位符
freelist.avail = node + 1;
freelist.count-= 1;
}
node = freelist.avail ++;
freelist.count-= 1;
返回节点；
}
void
FreeAll（void）
{
Node *节点；
节点*接下来；
for（node = freelist.head; node！= NULL; node = next）{
next = node-> next;
free（node）;
}
}
Node *
Insert（List * list，int _nbr）
{
Node * node = NewNode（）;
node-> data = _nbr;
node-> next = NULL;
if（list-> head == NULL）{
list-> head = node;
}
else {
list-> tail-> next =节点；
}
list-> tail =节点；
list-> count + = 1;
返回节点；
}
void
Print（Node * p）
{
if（p == NULL）{
printf （ \n）;
的回报；
}
printf（％d，p-> data）;
Print（p-> next）;
}
void
PrintList（List * list）
{
Node * node;
for（node = list-> head; node！= NULL; node = node-> next）
printf（％d，node-> data）;
printf（ \n）;
}
void
RevPrint（Node * p）
{
if（p == NULL）{
printf （ \n）;
的回报；
}
RevPrint（p-> next）;
printf（％d，p-> data）;
}
void
RevPrintList（List * list）
{
Node ** rlist = malloc（sizeof（Node **）*（list- > count + 1））;
节点* node;
int ridx;
ridx = list-> count-1;
代表（node = list-> head; node！= NULL; node = node-> next，--ridx）
rlist [ridx] = node;
for（ridx = 0; ridx< list-> count; ++ ridx）{
node = rlist [ridx];
printf（％d，node-> data）;
}
printf（ \n）;
free（rlist）;
}
更新＃ 3：
这里是通过向<$添加 reuse 成员来增加节点重用的版本c $ c> FreeList 和 FreeOne 函数，可在删除节点时调用该函数。
#include< stdio.h>
#include< stdlib.h>
#include< string.h>
//＃include< conio.h>
typedef struct Node_ {
int数据；
struct Node_ * next;
}节点；
typedef struct List_ {
int count;
节点* head;
节点* tail;
}清单；
typedef struct Freelist_ {
int count;
节点* head;
节点* tail;
节点*可用；
节点*重用；
} FreeList;
节点* NewNode（void）;
节点*插入（列出* p，int数据）;
void Print（Node * p）;
void PrintList（List * list）;
void RevPrint（Node * p）;
void RevPrintList（List * list）;
void FreeOne（Node * p）;
void FreeAll（void）;
FreeList freelist = {0};
int
main（）
{
List nodelist = {0，NULL，NULL};
printf（ --------------------------------- \n插入（）\n --------------------------------- \n）；
for（int i = 1; i< 1000000; i ++）{
Insert（& nodelist，i）;
//此printf将从根本上降低
#if 0的速度
printf（％d，i）;
#endif
}
printf（ \n ------------------------- -------- \n Print（）\n ------------------------------- --\n）;
#if 0
打印（nodelist.head）;
#else
PrintList（& nodelist）;
#endif
printf（ --------------------------------- \n RevPrint（）\n ---------------------------------）;
#if 0
RevPrint（nodelist.head）;
#else
RevPrintList（& nodelist）;
#endif
//将所有节点释放回malloc空闲池
FreeAll（）;
printf（ \n按任意键继续...）;
#if 0
_getch（）;
#else
getchar（）;
#endif
}
节点*
NewNode（void）
{
FreeList * list;
节点* node;
list =& freelist;
do {
//尝试重用FreeOne已释放的节点
node = list-> reuse;
if（node！= NULL）{
list-> reuse = node-> next;
node-> next = NULL;
休息时间；
}
//注意：如果（list-> count&=== 0）{$ b，请将计数设置（例如1000）调整为想要的值
$ b list-> count = 1000;
node = calloc（list-> count，sizeof（Node））;
//维护在
_start_处的节点的链表// malloc区域/区域
if（list-> head == NULL）
list-> head =节点；
else
list-> tail-> next =节点；
list-> tail =节点；
//将第一个节点刻录为占位符
list-> avail = node + 1;
list-> count-= 1;
}
//从当前分配数组中获取一个
node = list-> avail ++;
list-> count-= 1;
}而（0）;
返回节点；
}
void
FreeOne（Node * node）
{
FreeList * list;
list =& freelist;
//将这个节点推送到重用列表的前面（即速度很快）
node-> next = list-> reuse;
list-> reuse =节点；
}
void
FreeAll（void）
{
Node * node;
节点* next;
for（node = freelist.head; node！= NULL; node = next）{
next = node-> next;
free（node）;
}
memset（& freelist，0，sizeof（FreeList））;
}
Node *
Insert（List * list，int _nbr）
{
Node * node = NewNode（）;
node-> data = _nbr;
node-> next = NULL;
if（list-> head == NULL）{
list-> head = node;
}
else {
list-> tail-> next =节点；
}
list-> tail =节点；
list-> count + = 1;
返回节点；
}
void
Print（Node * p）
{
if（p == NULL）{
printf （ \n）;
的回报；
}
printf（％d，p-> data）;
Print（p-> next）;
}
void
PrintList（List * list）
{
Node * node;
for（node = list-> head; node！= NULL; node = node-> next）
printf（％d，node-> data）;
printf（ \n）;
}
void
RevPrint（Node * p）
{
if（p == NULL）{
printf （ \n）;
的回报；
}
RevPrint（p-> next）;
printf（％d，p-> data）;
}
void
RevPrintList（List * list）
{
Node ** rlist = malloc（sizeof（Node **）*（list- > count + 1））;
节点* node;
int ridx;
ridx = list-> count-1;
用于（node = list-> head; node！= NULL; node = node-> next，--ridx）
rlist [ridx] = node;
for（ridx = 0; ridx< list-> count; ++ ridx）{
node = rlist [ridx];
printf（％d，node-> data）;
}
printf（ \n）;
free（rlist）;
}
In the code bellow, I'm searching for ways to optimize the speed of insertions when dealing with Millions of inserts at the time. the code runs fine but is very slow when performing large amounts of inserts. I already tried some ideas but is always slow. I guess the solution is to use Multi-threading to perform the inserts, and use a global variable "truct Node* nodeObj". I have very few/no experience with Multi-threading and Synchronization in C, C++, If you could give me an example based on the code bellow I would be very appreciated. Any additional Ideas are welcome.
The rules are: 1- In the end (after insert all numbers) the linked list must be ordered, meaning that each Node->data starts at lowest number up to the Largest number. 2 - The caller is using a for loop, this for loop cannot be started inside the Insert function. 3 - Any of the code, caller or insert function can be optimized as long as the insert function does not automatically add inserts by it self, that's the caller s job.
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
struct Node {
int data;
struct Node* nextAddr;
};
struct Node* Insert(Node* p, int data);
void Print(struct Node* p);
void RevPrint(struct Node* p);
int main() {
struct Node* nodeObj = NULL;
printf("---------------------------------\n"
"Insert()\n---------------------------------\n");
for (int i = 1; i < 1000000; i++) {
nodeObj = Insert(nodeObj, i);
printf(" %d", i);
}
printf("\n---------------------------------\n"
"Print()\n---------------------------------\n");
Print(nodeObj);
printf("---------------------------------\n"
"RevPrint()\n---------------------------------");
RevPrint(nodeObj);
printf("\nPress any key to continue...");
_getch();
}
struct Node* Insert(Node* _pToNode, int _nbr)
{
Node *newValue = (struct Node*)malloc(sizeof(struct Node));
newValue->data = _nbr;
newValue->nextAddr = NULL;
if (_pToNode == NULL) _pToNode = newValue;
else {
Node* pLocal = _pToNode;
while (pLocal->nextAddr != NULL) {
pLocal = pLocal->nextAddr;
}
pLocal->nextAddr = newValue;
}
return _pToNode;
}
void Print(struct Node* p) {
if (p == NULL) {
printf("\n");
return;
}
printf(" %d", p->data);
Print(p->nextAddr);
}
void RevPrint(struct Node* p) {
if (p == NULL) {
printf("\n");
return;
}
RevPrint(p->nextAddr);
printf(" %d", p->data);
}
Thank you.
解决方案
Caveat: This works only for tail insertion/append:
int
main()
{
struct Node* nodeObj = NULL;
struct Node* nodeTail = NULL;
// your other stuff ...
for (int i = 1; i < 1000000; i++) {
nodeObj = Insert(nodeObj, &nodeTail, i);
printf(" %d", i);
}
// your other stuff ...
}
struct Node* Insert(Node* _pToNode, Node **tail,int _nbr)
{
Node *newValue = (struct Node*)malloc(sizeof(struct Node));
newValue->data = _nbr;
newValue->nextAddr = NULL;
if (_pToNode == NULL) {
_pToNode = newValue;
}
else {
(*tail)->nextAddr = newValue;
}
*tail = newValue;
return _pToNode;
}
You could clean this up with a "list" struct that has both the head and tail in it (vs. the separate args)
UPDATE:
Very cool/smart, but unfortunately is still slow...
malloc et. al. can be slow for a large number of small allocations. One way to speed things up is to use a subpool of allocations [as WeatherVane suggested].
As I mentioned, adding a "list" struct can make things tidier and I used it in two places. Once you commit to that, you can add other things besides head/tail, such as count. Also, it makes it easier to convert from a singly-linked list to a doubly-linked in the future, if you so choose.
Side note: With a doubly-linked list, insertions are [slightly] more complex, but insertions in the middle of the list are much faster because you don't have to traverse the list to find the previous pointer (e.g. the node would have a prev pointer in it). Also, RevPrintList would become as simple as PrintList.
Note that [on my system], the reverse print ran out of stack space [and segfaulted], so I recoded the print functions to not be recursive.
Here's a cleaned up version that should do the insertions faster because of the reduced number of individual malloc calls.
Side note: I didn't add the requisite checks for malloc, etc. returning null.
#include <stdio.h>
#include <stdlib.h>
//#include <conio.h>
typedef struct Node_ {
int data;
struct Node_* next;
} Node;
typedef struct List_ {
int count;
Node* head;
Node* tail;
} List;
Node* NewNode(void);
Node* Insert(List* p, int data);
void Print(Node* p);
void PrintList(List *list);
void RevPrint(Node* p);
void RevPrintList(List *list);
List freelist;
int
main()
{
List nodelist = { 0, NULL, NULL };
printf("---------------------------------\n"
"Insert()\n---------------------------------\n");
for (int i = 1; i < 1000000; i++) {
Insert(&nodelist, i);
#if 0
printf(" %d", i);
#endif
}
printf("\n---------------------------------\n"
"Print()\n---------------------------------\n");
#if 0
Print(nodelist.head);
#else
PrintList(&nodelist);
#endif
printf("---------------------------------\n"
"RevPrint()\n---------------------------------");
#if 0
RevPrint(nodelist.head);
#else
RevPrintList(&nodelist);
#endif
printf("\nPress any key to continue...");
#if 0
_getch();
#else
getchar();
#endif
}
Node*
NewNode(void)
{
Node *node;
// NOTE: adjust the count setup (e.g. 1000) to what ever value you want
if (freelist.count <= 0) {
freelist.count = 1000;
freelist.head = calloc(freelist.count,sizeof(Node));
}
node = freelist.head++;
freelist.count -= 1;
return node;
}
Node*
Insert(List* list,int _nbr)
{
Node *node = NewNode();
node->data = _nbr;
node->next = NULL;
if (list->head == NULL) {
list->head = node;
}
else {
list->tail->next = node;
}
list->tail = node;
list->count += 1;
return node;
}
void
Print(Node* p)
{
if (p == NULL) {
printf("\n");
return;
}
printf(" %d", p->data);
Print(p->next);
}
void
PrintList(List* list)
{
Node *node;
for (node = list->head; node != NULL; node = node->next)
printf(" %d", node->data);
printf("\n");
}
void
RevPrint(Node* p)
{
if (p == NULL) {
printf("\n");
return;
}
RevPrint(p->next);
printf(" %d", p->data);
}
void
RevPrintList(List *list)
{
Node **rlist = malloc(sizeof(Node**) * list->count);
Node *node;
int ridx;
ridx = list->count - 1;
for (node = list->head; node != NULL; node = node->next, --ridx)
rlist[ridx] = node;
for (ridx = 0; ridx < list->count; ++ridx) {
node = rlist[ridx];
printf(" %d",node->data);
}
printf("\n");
free(rlist);
}
UPDATE #2:
you could make freeList a list of lists (using a different "node" struct which would have a pointer to list instead of a number), so that memory could be released when the program is done.
Here is a modified version that does that:
#include <stdio.h>
#include <stdlib.h>
//#include <conio.h>
typedef struct Node_ {
int data;
struct Node_* next;
} Node;
typedef struct List_ {
int count;
Node* head;
Node* tail;
} List;
typedef struct Freelist_ {
int count;
Node* head;
Node* tail;
Node* avail;
} FreeList;
Node* NewNode(void);
Node* Insert(List* p, int data);
void Print(Node* p);
void PrintList(List *list);
void RevPrint(Node* p);
void RevPrintList(List *list);
void FreeAll(void);
FreeList freelist = { 0 };
int
main()
{
List nodelist = { 0, NULL, NULL };
printf("---------------------------------\n"
"Insert()\n---------------------------------\n");
for (int i = 1; i < 1000000; i++) {
Insert(&nodelist, i);
// this printf will radically slow things down
#if 0
printf(" %d", i);
#endif
}
printf("\n---------------------------------\n"
"Print()\n---------------------------------\n");
#if 0
Print(nodelist.head);
#else
PrintList(&nodelist);
#endif
printf("---------------------------------\n"
"RevPrint()\n---------------------------------");
#if 0
RevPrint(nodelist.head);
#else
RevPrintList(&nodelist);
#endif
// release all nodes back to the malloc free pool
FreeAll();
printf("\nPress any key to continue...");
#if 0
_getch();
#else
getchar();
#endif
}
Node*
NewNode(void)
{
Node *node;
// NOTE: adjust the count setup (e.g. 1000) to what ever value you want
if (freelist.count <= 0) {
freelist.count = 1000;
node = calloc(freelist.count,sizeof(Node));
// maintain linked list of nodes that are at the _start_ of a
// malloc area/arena
if (freelist.head == NULL)
freelist.head = node;
else
freelist.tail->next = node;
freelist.tail = node;
// burn the first node as a placeholder
freelist.avail = node + 1;
freelist.count -= 1;
}
node = freelist.avail++;
freelist.count -= 1;
return node;
}
void
FreeAll(void)
{
Node* node;
Node* next;
for (node = freelist.head; node != NULL; node = next) {
next = node->next;
free(node);
}
}
Node*
Insert(List* list,int _nbr)
{
Node *node = NewNode();
node->data = _nbr;
node->next = NULL;
if (list->head == NULL) {
list->head = node;
}
else {
list->tail->next = node;
}
list->tail = node;
list->count += 1;
return node;
}
void
Print(Node* p)
{
if (p == NULL) {
printf("\n");
return;
}
printf(" %d", p->data);
Print(p->next);
}
void
PrintList(List* list)
{
Node *node;
for (node = list->head; node != NULL; node = node->next)
printf(" %d", node->data);
printf("\n");
}
void
RevPrint(Node* p)
{
if (p == NULL) {
printf("\n");
return;
}
RevPrint(p->next);
printf(" %d", p->data);
}
void
RevPrintList(List *list)
{
Node **rlist = malloc(sizeof(Node**) * (list->count + 1));
Node *node;
int ridx;
ridx = list->count - 1;
for (node = list->head; node != NULL; node = node->next, --ridx)
rlist[ridx] = node;
for (ridx = 0; ridx < list->count; ++ridx) {
node = rlist[ridx];
printf(" %d",node->data);
}
printf("\n");
free(rlist);
}
UPDATE #3:
Here's a version that adds reuse of nodes by adding a reuse member to FreeList and a FreeOne function that can be called when a node is deleted.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//#include <conio.h>
typedef struct Node_ {
int data;
struct Node_ *next;
} Node;
typedef struct List_ {
int count;
Node *head;
Node *tail;
} List;
typedef struct Freelist_ {
int count;
Node *head;
Node *tail;
Node *avail;
Node *reuse;
} FreeList;
Node *NewNode(void);
Node *Insert(List *p,int data);
void Print(Node *p);
void PrintList(List *list);
void RevPrint(Node *p);
void RevPrintList(List *list);
void FreeOne(Node *p);
void FreeAll(void);
FreeList freelist = { 0 };
int
main()
{
List nodelist = { 0, NULL, NULL };
printf("---------------------------------\n" "Insert()\n---------------------------------\n");
for (int i = 1; i < 1000000; i++) {
Insert(&nodelist,i);
// this printf will radically slow things down
#if 0
printf(" %d",i);
#endif
}
printf("\n---------------------------------\n" "Print()\n---------------------------------\n");
#if 0
Print(nodelist.head);
#else
PrintList(&nodelist);
#endif
printf("---------------------------------\n" "RevPrint()\n---------------------------------");
#if 0
RevPrint(nodelist.head);
#else
RevPrintList(&nodelist);
#endif
// release all nodes back to the malloc free pool
FreeAll();
printf("\nPress any key to continue...");
#if 0
_getch();
#else
getchar();
#endif
}
Node *
NewNode(void)
{
FreeList *list;
Node *node;
list = &freelist;
do {
// try to reuse a node that has been released by FreeOne
node = list->reuse;
if (node != NULL) {
list->reuse = node->next;
node->next = NULL;
break;
}
// NOTE: adjust the count setup (e.g. 1000) to what ever value you want
if (list->count <= 0) {
list->count = 1000;
node = calloc(list->count,sizeof(Node));
// maintain linked list of nodes that are at the _start_ of a
// malloc area/arena
if (list->head == NULL)
list->head = node;
else
list->tail->next = node;
list->tail = node;
// burn the first node as a placeholder
list->avail = node + 1;
list->count -= 1;
}
// grab one from the current allocation array
node = list->avail++;
list->count -= 1;
} while (0);
return node;
}
void
FreeOne(Node *node)
{
FreeList *list;
list = &freelist;
// push this node onto the front of the reuse list (i.e. it's fast)
node->next = list->reuse;
list->reuse = node;
}
void
FreeAll(void)
{
Node *node;
Node *next;
for (node = freelist.head; node != NULL; node = next) {
next = node->next;
free(node);
}
memset(&freelist,0,sizeof(FreeList));
}
Node *
Insert(List *list,int _nbr)
{
Node *node = NewNode();
node->data = _nbr;
node->next = NULL;
if (list->head == NULL) {
list->head = node;
}
else {
list->tail->next = node;
}
list->tail = node;
list->count += 1;
return node;
}
void
Print(Node *p)
{
if (p == NULL) {
printf("\n");
return;
}
printf(" %d",p->data);
Print(p->next);
}
void
PrintList(List *list)
{
Node *node;
for (node = list->head; node != NULL; node = node->next)
printf(" %d",node->data);
printf("\n");
}
void
RevPrint(Node *p)
{
if (p == NULL) {
printf("\n");
return;
}
RevPrint(p->next);
printf(" %d",p->data);
}
void
RevPrintList(List *list)
{
Node **rlist = malloc(sizeof(Node **) * (list->count + 1));
Node *node;
int ridx;
ridx = list->count - 1;
for (node = list->head; node != NULL; node = node->next, --ridx)
rlist[ridx] = node;
for (ridx = 0; ridx < list->count; ++ridx) {
node = rlist[ridx];
printf(" %d",node->data);
}
printf("\n");
free(rlist);
}
这篇关于需要慢速插入链表多线程吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
