c - 一种Linked List但不完全理解

Question

我之前问过这个，但是没有人回答所以修改我的问题。我试图分析这些代码，但对我来说没有意义。这次希望有人给我一个想法或纠正我的误解。

char * p 指向 command 数组在通过几个函数后被类型转换为 CMD_BLOCK *。

                         extern CHGR_CMD command[96]
                          +---+---+---+---+
(CMD_BLOCK *(char *p)) -> | CHGR_CMD      | command[0]
                          +---+---+---+---+
                          | CHGR_CMD      | command[1]
                          +---+---+---+---+ ....
                          | ....          | command[95]
                          +---+---+---+---+

这里是CMD_BLOCK和 union CHGR_CMD的结构

typedef struct cmd_block {
 struct cmd_block *next;
 short type;
 short unused;
 CHGR_CMD c; //Union
} CMD_BLOCK;


typedef union chgr_cmd {
  NET_HDR n; //struct
  CHGR_SC_SETUP    su;//struct
  CHGR_SC_START    st;//struct
  CHGR_SC_STOP     sp;//struct
  ....
} CHGR_CMD;

cmd_init()中使用了以下变量

#define CMD_OFFSET  (sizeof(struct cmd_block *) + 2*sizeof(short))
block_size = sizeOf(CHGR_CMD)
size = 96*sizeOf(CHGR_CMD)

特别是，我没有得到下面的 for 循环:

int cmd_init(register char* p, register long size, int block_size)
{
  int i;

  if((size <= 0) || (block_size <= 0) || (block_size > size))
    return(-1);

  cmd_out_head = NULL;//extern var
  cmd_out_tail = NULL;//extern var
  cmd_free_space = NULL;//extern var
  block_size += CMD_OFFSET;// turn to be size of CMD_BLOCK

  cmd_blocks_free = 0;
  cmd_blocks_used = 0;

  for(i=0; size >= block_size; size-=block_size, i++, p+=block_size) {
    ((CMD_BLOCK *)(p))->next = cmd_free_space;
    cmd_free_space = (CMD_BLOCK *)(p);
    cmd_blocks_free++;
  }

  cmd_b = NULL;
  status_seq_clear();

  return(i);
}

for 循环 迭代直到 96，这是 command 数组的大小。

p+=block_size 不断增加 CMD_BLOCK 的大小 ---> 我不明白这是怎么回事？ 数组的初始类型是 CHGR_CMD 并类型转换为 char * 然后另一个转换为 CMD_BLOCK * 然后增加 CMD_BLOCK 的大小for 循环??

我不确定，但假设经过几次类型转换后，命令数组的类型现在变成了 CMD_BLOCK。

我不明白的另一件事是这段代码:

((CMD_BLOCK *)(p))->next = cmd_free_space;
cmd_free_space = (CMD_BLOCK *)(p);

好像没有联系在一起。 cmd_free_space 似乎指向数组的最后一个元素，而 * p 增加了 CMD_BLOCK 的大小。

Answer 1

关于从 char* 到 CMD_BLOCK* 的转换，如果不查看更多代码很难判断，但很可能是原始程序员想给一些不透明性p 参数，也就是说，他/她可能不想暴露函数正在接收 CMD_BLOCK 结构数组的事实。

有时会在某些 API 上使用这种不透明性，以尽量减少程序员绕过测试 API 直接操纵数据结构的可能性。

参见 here有关不透明指针的更多详细信息。

为了消除不透明性，程序员需要将不透明指针显式转换为实际传递的具体类型。这似乎是通过行 ((CMD_BLOCK *)(p))->next = cmd_free_space;

完成的

至于for block 是做什么的，它实际上是从一个连续的CMD_BLOCK结构数组构建一个反向链表。第一个节点的next指针初始化为NULL，成为链表的尾部，第二个节点的next指针指向第一个节点依此类推，直到最后一个 block 成为列表的头部并且似乎可以通过您指出的 cmd_free_space 变量访问。

** 编辑 **为了更好地说明列表是如何构建的，我将尝试逐步完成前两次迭代。

iteration 1
   State at the beginning of the iteration:
      cmd_free_space is NULL;
      p is pointing to the first element of the array.
   Execution:
      p->next = cmd_free_space; p->next becomes NULL;
      cmd_free_space = p;       cmd_free_space is pointing to the first element of the array
      p += block_size;          p is now pointing to the second element of the array

iteration 2
    State at the beginning of the iteration:
       cmd_free_space is pointing to the first element of the array
       p is pointing to the second element of the array.
    Execution:
       p->next = cmd_free_space; p->next = first element of the array (link is done)
       cmd_free_space = p;       cmd_free_space is now pointing to the second element of the array
       p += block_size;          p is now pointing to the third element of the array

等等……

** 编辑结束 **

我将从 for block 中删除 i 变量，因为它没用(它既不控制迭代次数也不索引任何内容)。

** 编辑:**我没有注意到“i”变量是从函数返回的，所以它很可能在函数之外有一个目的。该函数实际上是返回在 for 循环中实际处理的元素数。** 编辑结束 **

blocksize 是一个可变参数而不是简单的 sizeof(CMD_BLOCK) 这一事实也可能表明该函数可以使用包含的结构数组初始化链表作为第一个成员 CMD_BLOCK 结构，但它也携带额外的数据。通过将 blocksize 添加到遍历数组的指针，for 循环将有效地跳过额外的数据。

将数组初始化为链表似乎是一件奇怪的事情，但我猜想程序员需要在列表中间插入命令的灵 active ，而不必复制/移动原始数组中的元素腾出空间。