Sha*_*baz 9 c interface abstract-data-type data-structures
我正在为C(这里)实现一组常见但又不那么简单(或容易出错)的数据结构,并且只是提出了让我思考的想法.
简而言之,问题是,实现两个使用类似算法但具有不同接口的结构的最佳方法是什么,而无需复制粘贴/重写算法？最好的,我的意思是最可维护和可调试.
我认为很明显为什么你不想要同一算法的两个副本.
假设你有一组结构(称之为map),带有一组相关的函数(map_*()).由于地图需要将任何东西映射到任何东西,我们通常会使用a void *key和void *data.然而,认为地图上的int到int.在这种情况下,您需要将所有密钥和数据存储在另一个阵列中并将其地址提供给map,这不太方便.
现在想象一下,如果有一个类似的结构(称之为mapc,C为"副本")期间初始化需要sizeof(your_key_type)和sizeof(your_data_type)并给予void *key与void *data上插入,它将使用memcpy的密钥和数据复制在地图上,而不是仅仅维持指针.用法示例:
int i;
mapc m;
mapc_init(&m, sizeof(int), sizeof(int));
for (i = 0; i < n; ++i)
{
int j = rand(); /* whatever */
mapc_insert(&m, &i, &j);
}
这是非常好的,因为我不需要保留另一个is和js 数组.
在上面的例子,map并mapc有非常密切的关系.如果你想想看,map和set结构和功能也很相似.我已经想到了以下几种方法来实现它们的算法只用一次并将它用于所有这些算法.然而,他们都不是很满意我.
使用宏.将函数代码写入头文件,将结构相关的东西保留为宏.对于每个结构,定义适当的宏并包含文件:
map_generic.h
#define INSERT(x) x##_insert
int INSERT(NAME)(NAME *m, PARAMS)
{
// create node
ASSIGN_KEY_AND_DATA(node)
// get m->root
// add to tree starting from root
// rebalance from node to root
// etc
}
map.c
#define NAME map
#define PARAMS void *key, void *data
#define ASSIGN_KEY_AND_DATA(node) \
do {\
node->key = key;\
node->data = data;\
} while (0)
#include "map_generic.h"
mapc.c
#define NAME mapc
#define PARAMS void *key, void *data
#define ASSIGN_KEY_AND_DATA(node) \
do {\
memcpy(node->key, key, m->key_size);\
memcpy(node->data, data, m->data_size);\
} while (0)
#include "map_generic.h"
这种方法不是一半坏,但它不是那么优雅.
使用函数指针.对于依赖于结构的每个部分,传递一个函数指针.
map_generic.c
int map_generic_insert(void *m, void *key, void *data,
void (*assign_key_and_data)(void *, void *, void *, void *),
void (*get_root)(void *))
{
// create node
assign_key_and_data(m, node, key, data);
root = get_root(m);
// add to tree starting from root
// rebalance from node to root
// etc
}
map.c
static void assign_key_and_data(void *m, void *node, void *key, void *data)
{
map_node *n = node;
n->key = key;
n->data = data;
}
static map_node *get_root(void *m)
{
return ((map *)m)->root;
}
int map_insert(map *m, void *key, void *data)
{
map_generic_insert(m, key, data, assign_key_and_data, get_root);
}
mapc.c
static void assign_key_and_data(void *m, void *node, void *key, void *data)
{
map_node *n = node;
map_c *mc = m;
memcpy(n->key, key, mc->key_size);
memcpy(n->data, data, mc->data_size);
}
static map_node *get_root(void *m)
{
return ((mapc *)m)->root;
}
int mapc_insert(mapc *m, void *key, void *data)
{
map_generic_insert(m, key, data, assign_key_and_data, get_root);
}
这种方法需要编写宏方法中可以避免的更多函数(如您所见,这里的代码更长)并且不允许优化器内联函数(因为它们对map_generic.c文件不可见).
那么,你将如何实现这样的事情呢？
注意:我在堆栈溢出问题表单中编写了代码,如果有小错误,请原谅.
附带问题:任何人都有一个更好的想法,后缀说"这个结构复制数据而不是指针"？我用c那个说"副本",但是我不知道的英语可能会有更好的词.
我想出了第三个解决方案.在此解决方案中,只map编写了一个版本,即保留data(mapc)副本的版本.此版本将用于memcpy复制数据.其它map与当前的接口,以void *key与void *data指针和发送&key和&data以mapc使它们包含的地址将被(使用复制memcpy).
这个解决方案的缺点是正常的指针分配完成memcpy,但它完全解决了问题,并且非常干净.
可替代地,一次只能实现map和使用额外的vectorc与mapc该数据载体中,然后第一拷贝赋予地址给一个map.这具有副作用,即删除mapc将要么基本上更慢,要么留下垃圾(或需要其他结构来重复使用垃圾).
我得出结论,粗心的用户可能会像编写C++一样使用我的库,复制后复制后复制.因此,我放弃了这个想法,只接受指针.
还有您没有考虑过的第三个选项：您可以创建一个外部脚本（用另一种语言编写）来从一系列模板生成代码。这与宏方法类似，但您可以使用 Perl 或 Python 等语言来生成代码。由于这些语言比 C 预处理器更强大，因此您可以避免通过宏创建模板时固有的一些潜在问题。当我想使用复杂的宏（如示例#1 中所示）时，我使用了此方法。最后，事实证明它比使用 C 预处理器更不易出错。缺点是在编写生成器脚本和更新 makefile 之间，最初的设置有点困难（但 IMO 最终值得）。