龙芯开源社区

 找回密码
 注册新用户(newuser)
查看: 3078|回复: 3

[已解决]glibc/misc/sys/queue.h使用的问题

[复制链接]
发表于 2010-10-9 14:00:37 | 显示全部楼层 |阅读模式
本帖最后由 moosewoler 于 2010-10-11 13:42 编辑

我在用queue.h里的宏建立SIMPLEQ队列的时候遇到了问题。
问题在代码中“注意“的部分,我把我的想法都写在那里了。如果不手工挂起队尾的话,就会出现死循环。
哪位遇到过这种情况,帮我解答一下,谢谢。

代码如下:
  1. moose@iBookG4:~/code/demo$ cat libc-queue.c
  2. #include <stdlib.h>
  3. #include <queue.h>
  4. #include <string.h>
  5. #include <stdio.h>

  6. SIMPLEQ_HEAD(TQueue, TElement);
  7. /* 等同于
  8. * struct TQueue
  9. * {
  10. *      struct  TElement *sqh_first;
  11. *      struct  TElement **sqh_last;
  12. * };
  13. */

  14. struct TElement
  15. {
  16.     // 声明你需要的结构
  17.     char data[16];
  18.     SIMPLEQ_ENTRY(TElement) next;    // 下一个节点
  19. };

  20. int main(void)
  21. {
  22.     struct TQueue head = SIMPLEQ_HEAD_INITIALIZER(head);
  23.     struct TElement *node1, *node2, *nodep;

  24.     // 初始化队列, 与SIMPLEQ_HEAD_INITIALIZER()等效
  25.     //SIMPLEQ_INIT(&head);
  26.     // 分配两个节点
  27.     node1 = malloc(sizeof(struct TElement));
  28.     strcpy(node1->data,"node1");
  29.     SIMPLEQ_INSERT_HEAD(&head, node1, next);
  30.     printf("%x,%s\n",node1,node1->data);

  31.     node2 = malloc(sizeof(struct TElement));
  32.     strcpy(node2->data,"node2");
  33.     SIMPLEQ_INSERT_AFTER(&head, node1, node2, next);
  34.     printf("%x,%s\n",node2,node2->data);

  35.     // 遍历队列
  36.     for (nodep=head.sqh_first; nodep!=NULL; nodep = nodep->next.sqe_next)
  37.     {
  38.         printf("%s\n",nodep->data);
  39.     }

  40.     free(node1);
  41.     free(node2);
  42.     // 访问不到两个节点的数据
  43.     for (nodep=head.sqh_first; nodep!=NULL; nodep = nodep->next.sqe_next)
  44.     {
  45.         printf("%s\n",nodep->data);
  46.     }
  47.     // 应该先删除节点,再将节点空间释放
  48.     // 再分配两个节点,这次改变一下添加顺序
  49.     SIMPLEQ_EMPTY(&head);

  50.     node1 = malloc(sizeof(struct TElement));
  51.     strcpy(node1->data,"again node1");
  52.     SIMPLEQ_INSERT_HEAD(&head, node1, next);
  53.     printf("%x,%s\n",node1,node1->data);

  54.     node2 = malloc(sizeof(struct TElement));
  55.     strcpy(node2->data,"again node2");
  56.     SIMPLEQ_INSERT_HEAD(&head, node2, next);
  57.     printf("%x,%s\n",node2,node2->data);

  58.     // 注意:因为queue.h中的SIMPLEQ_INSERT_HEAD宏并不将
  59.     // 队尾的sqe_next指针悬挂起来
  60.     // 所以要手工悬挂
  61.     // 否则因为node1和node2使用了之前使用过的空间(??),会形成循环队列
  62.     // 让下面的遍历成为死循环
  63.     // !!可是!!按理说SIMPLEQ_EMPTY()之后会将sqh_first挂起,并后续的添加
  64.     // 会继承这个挂起
  65.     // PS:SIMPLEQ_INSERT_TAIL()会悬挂队尾
  66.     node1->next.sqe_next=NULL;

  67.     // 用queue.h中提供的宏来遍历。和之前的方法是等效的
  68.     for (nodep=SIMPLEQ_FIRST(&head);
  69.             nodep!=NULL;
  70.             nodep = SIMPLEQ_NEXT(nodep, next))
  71.     {
  72.         printf("%s\n",nodep->data);
  73.     }

  74.     // 从头部删除所有节点
  75.     for (nodep=SIMPLEQ_FIRST(&head);
  76.             nodep!=NULL;
  77.             nodep = SIMPLEQ_NEXT(nodep, next))
  78.     {
  79.         SIMPLEQ_REMOVE_HEAD(&head, next);
  80.     }
  81.     free(node1);
  82.     free(node2);
  83.     printf("queue has been removed completely.\n");
  84.     // 这次再遍历队列就完全没有输出了。
  85.     for (nodep=head.sqh_first; nodep!=NULL; nodep = nodep->next.sqe_next)
  86.     {
  87.         printf("%s\n",nodep->data);
  88.     }

  89.     return 0;
  90. }
复制代码


编译环境
内核:
  1. moose@iBookG4:~/code/glibc-2.11.2$ uname -a
  2. Linux iBookG4 2.6.34.6-mwo #1 Thu Sep 30 03:40:00 CST 2010 ppc GNU/Linux
复制代码

GCC:
  1. moose@iBookG4:~/code/glibc-2.11.2$ gcc -v
  2. Using built-in specs.
  3. Target: powerpc-linux-gnu
  4. Configured with: ../src/configure -v --with-pkgversion='Debian 4.4.4-8' --with-bugurl=file:///usr/share/doc/gcc-4.4/README.Bugs --enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr --enable-shared --enable-multiarch --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.4 --program-suffix=-4.4 --enable-nls --enable-clocale=gnu --enable-libstdcxx-debug --enable-objc-gc --enable-secureplt --disable-softfloat --enable-targets=powerpc-linux,powerpc64-linux --with-cpu=default32 --with-long-double-128 --enable-checking=release --build=powerpc-linux-gnu --host=powerpc-linux-gnu --target=powerpc-linux-gnu
  5. Thread model: posix
  6. gcc version 4.4.5 20100728 (prerelease) (Debian 4.4.4-8)
复制代码

OS:
  1. moose@iBookG4:~/code/glibc-2.11.2$ cat /etc/debian_version
  2. squeeze/sid
复制代码
发表于 2010-10-10 15:15:05 | 显示全部楼层
DaDa, 竟敢使用apple,:)。

你的“挂起”是神马意思?
 楼主| 发表于 2010-10-11 13:40:54 | 显示全部楼层
就是字面意思,把队尾的next设为NULL
SIMPLEQ是简单队列——一个单向遍历的链表。
教科书的做法嘛。。。
  1. struct QueueElement{
  2.         Sometype data;
  3.         struct QueueElement *next;
  4. }
复制代码

这样来构造一个链表的节点。
gligc用SIMPLEQ_ENTRY(type)这个宏完成同样的事情。
然后。。。在添加新节点到队尾的时候,应该把队尾挂起——置NULL。
head->node1->node2->.....->noden->新node->NULL
形成这样的队列。可是在我的代码中,先mallaoc两个节点node1,node2;然后,添加到队列;然后,遍历。。。输出如下:
  1. moose@iBookG4:~/code/demo$ ./libc-queue
  2. 100ae008,node1
  3. 100ae020,node2
  4. node1
  5. node2
复制代码

这里是没问题的,node2挂起了队尾。
但是,后边将它两个free之后,重新malloc呢。。。再添加一次,遍历。。。。就会循环输出node2,node1,node2,node1,node2,node1
部分输出
  1. again node1
  2. again node2
  3. again node1
  4. again node2
  5. again node1
  6. again node2
  7. again node1
  8. again node2
  9. again node1
  10. again node2
  11. ^Cmoose@iBookG4:~/code/demo$
复制代码

就像是node1.next.sqe_next仍然指向node2一样,成了循环队列。
可是,队列一经清空(SIMPLEQ_EMPTY(&head)),head.sqh_first就指向NULL。此后的添加动作。。。。。
啊,我明白了。。。。
  1. #define        SIMPLEQ_EMPTY(head)                ((head)->sqh_first == NULL)
复制代码

SIMPLEQ_EMPTY()这么写不是清空队列,是判断队列是否为空啊。。。。这名字真是搞笑了
呜。。解决了
 楼主| 发表于 2010-10-11 14:33:20 | 显示全部楼层
事后看man queue,才发现人家写的清清楚楚的。教训啊

本版积分规则

Archiver|手机版|小黑屋|Lemote Inc.

GMT+8, 2020-9-20 12:28 , Processed in 0.146078 second(s), 15 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表