如何写一个foreach般的宏来访问图形

假设我有以下节点图的所有节点：如何写一个foreach般的宏来访问图形

typedef struct node node_t; 
struct node { 
    size_t adjacent_node_count; 
    node_t **adjacent_nodes; 
    void* data; 
};

该图表示为一个指向其中一个节点（即，我没有所有节点的单个列表，但是每个节点都保证可以从这个“根”节点到达）。

现在，我需要访问此图中的每个节点，并将其中的每个节点的data只应用一次函数一次。我想最简单的方法就是DFS。

让我们添加一些的Fileds到node简化实施

typedef struct node node_t; 
struct node { 
    size_t adjacent_node_count; 
    node_t **adjacent_nodes; 
    void* data; 
    node_t *dfs_stack_next; 
    bool dfs_visited; 
};

而且穿越本身就是

void dfs(node_t *root, void* context, void (*function)(void* context, void* data)) { 
    node_t *stack_top = root; 
    while (stack_top != NULL) { 
     node_t *current_node = stack_top; 
     stack_top = stack_top->dfs_stack_next; 
     if (!current_node->dfs_visited) { 
      current_node->dfs_visited = true; 
      for (int i = 0; i < current_node->adjacent_node_count; ++i) { 
       node_t *adjacent_node = current_node->adjacent_nodes[i]; 
       adjacent_node->dfs_stack_next = stack_top; 
       stack_top = adjacent_node; 
      } 
      function(context, current_node->data); 
     } 
    } 
}

这是failry简单。但是写功能和结构包裹当地情况变得痛苦快，所以我想在foreach样宏来包装这个：

for_each_node(n, root) { 
    // do stuff with n->data 
}

我在循环中部分入门顶级节点从堆栈

#define for_each_node(current_node, root) \ 
    for (state_t *current_node, *stack_top = root; \ 
     stack_top \ 
      ? (current_node = stack_top, stack_top = stack_top->dfs_stack_next, stack_top) \ 
      : stack_top; \ 
    ) /* ??? */

现在我被卡住了。我意识到，这是相当简单的写了两个部分的宏，像

for_each_node_begin(n, root) 
    // do stuff with n->data 
for_each_node_end(n, root)

，将简单的两线与function通话分裂dfs，但是我发现，相当难看。

那么，我该如何去执行for_each_node？这是否可能？它不需要是DFS，任何订单都可以，只要data被处理一次。

来源

2014-01-06 yuri kilochek

如果你想要一些语法糖只是一个宏前缀的块，并避免你有一个“结束”的宏，这可以通过使用“dummy”for系统完成，一旦。写作这样的事情有点讨厌，但根据我的经验，它使代码使用它更容易掌握。

P99有很多帮助宏可以简化这些宏的编程。 P99_GUARDED_BLOCK似乎适合您的使用情况。

来源

2014-01-06 13:51:22

诀窍是写一个函数next_node。接收节点并使用dfs/bfs/whatever返回下一个节点的函数。

宏将是：

for_each_node(n, root) \ 
    for (struct node* n = root; n != NULL; n = next_node(n))

注意，一个节点必须指向其父和儿童这个工作。还假定该图是一个DAG。带圆圈的非定向图需要不同的处理。

来源

2014-01-06 14:27:30 egur

如何写一个foreach般的宏来访问图形

回答

相关问题