没有复制粘贴实现不同但类似的结构/功能集 [英] Implementing different yet similar structure/function sets without copy-paste

问题描述

我执行C（一组通用尚未那么微不足道（或出错）的数据结构的这里），只是带着一个想法，我开始思考。

I'm implementing a set of common yet not so trivial (or error-prone) data structures for C (here) and just came with an idea that got me thinking.

总之现在的问题是，什么是实现使用类似的算法，但有不同的接口两种结构，无需进行复制粘贴的最佳方式/重写算法？按最好的，我的意思最易维护和调试的能力。

The question in short is, what is the best way to implement two structures that use similar algorithms but have different interfaces, without having to copy-paste/rewrite the algorithm? By best, I mean most maintainable and debug-able.

我认为这是显而易见的，为什么你不希望有相同算法的两个副本。

I think it is obvious why you wouldn't want to have two copies of the same algorithm.

假设你有一个结构（称之为地图）与一组相关的功能（地图_ *（） ）。由于地图需要映射任何东西，我们通常会实现它采取了无效*键和 void *的数据 。不过，联想的地图 INT 的以 INT 的。在这种情况下，你需要所有的密钥和数据存储在另一个数组并给他们的地址到地图，这是不那么方便了。

Say you have a structure (call it map) with a set of associated functions (map_*()). Since the map needs to map anything to anything, we would normally implement it taking a void *key and void *data. However, think of a map of int to int. In this case, you would need to store all the keys and data in another array and give their addresses to the map, which is not so convenient.

现在想象一下，如果有一个类似的结构（称之为 MAPC ，C为份），在初始化需要的sizeof（your_key_type）和的sizeof（your_data_type）并给予无效*键和无效*在插入数据，它将使用的memcpy 的密钥和数据复制在地图上，而不是仅仅维持指针。用法的例子：

Now imagine if there was a similar structure (call it mapc, c for "copies") that during initialization takes sizeof(your_key_type) and sizeof(your_data_type) and given void *key and void *data on insert, it would use memcpy to copy the keys and data in the map instead of just keeping the pointers. An example of usage:

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);
}

这是相当不错的，因为我并不需要保持的另一个阵列I 和Ĵ取值

在上面的例子中，地图和 MAPC 的关系非常密切。如果你仔细想想，地图和设置结构和功能也很相似。我也曾想过通过以下方法来实现他们的算法只有一次，并用它为所有这些。他们既不是却相当令人满意给我。

In the example above, map and mapc are very closely related. If you think about it, map and set structures and functions are also very similar. I have thought of the following ways to implement their algorithm only once and use it for all of them. Neither of them however are quite satisfying to me.

1. 使用宏。写在一个头文件中的函数code，而使结构相关的东西，如宏。对于每一个结构，定义适当的宏和包含文件：

1. Use macros. Write the function code in a header file, leaving the structure dependent stuff as macros. For each structure, define the proper macros and include the file:

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"

这方法不是一半坏，但它不是那么优雅。

This method is not half bad, but it's not so elegant.

使用函数指针。因为这是依赖于结构的各部件，通过一个函数指针。

Use function pointers. For each part that is dependent on the structure, pass a function pointer.

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);
}

此方法需要编写本来是可以避免的宏观方法的更多功能（如你所看到的，code这里是更长的时间），不允许优化内联函数（因为它们不可见 map_generic.c 文件）。

This method requires writing more functions that could have been avoided in the macro method (as you can see, the code here is longer) and doesn't allow optimizers to inline the functions (as they are not visible to map_generic.c file).

那么，你将如何去实现这样的事情？

So, how would you go about implementing something like this?

注：我写的堆栈溢出问题的形式code，所以原谅我，如果有轻微错误

Note: I wrote the code in the stack-overflow question form, so excuse me if there are minor errors.

侧的问题：任何人有一个后缀，说：这个结构拷贝数据，而不是指针一个更好的主意吗？我使用 C ，上面写着拷贝，但也可能是一个更好的词用英文，我不知道。

Side question: Anyone has a better idea for a suffix that says "this structure copies the data instead of the pointer"? I use c that says "copies", but there could be a much better word for it in English that I don't know about.

我想出了第三种解决方案。在这个解决方案中，地图的只有一个版本上所写的，保持数据的副本之一（ MAPC ） 。该版本将使用的memcpy 来复制数据。另地图是这样的一个接口，以无效*键和 void *的数据指针和发送＆放大器;关键和＆放大器;数据到 MAPC ，使它们包含的地址会（使用的memcpy ）进行复制。

I have come up with a third solution. In this solution, only one version of the map is written, the one that keeps a copy of data (mapc). This version would use memcpy to copy data. The other map is an interface to this, taking void *key and void *data pointers and sending &key and &data to mapc so that the address they contain would be copied (using memcpy).

该解决方案有一个正常的指针分配由的memcpy 所做的缺点，但它完全解决了，否则这个问题，是非常干净的。

This solution has the downside that a normal pointer assignment is done by memcpy, but it completely solves the issue otherwise and is very clean.

另外，一次只能执行地图，并使用一个额外的 vectorc 与 MAPC 它首先将数据复制到向量，然后会向地址到地图。这有副作用，就是从删除 MAPC 要么会更慢，或留下垃圾（或要求其他结构重用垃圾）。

Alternatively, one can only implement the map and use an extra vectorc with mapc which first copies the data to vector and then gives the address to a map. This has the side effect that deletion from mapc would either be substantially slower, or leave garbage (or require other structures to reuse the garbage).

我得出的结论是粗心的用户可能会使用我的图书馆他们写的方式C ++，复印后复印件后进行复制。所以，我放弃了这个想法，只接受指针。

I came to the conclusion that careless users might use my library the way they write C++, copy after copy after copy. Therefore, I am abandoning this idea and accepting only pointers.

推荐答案

还有，你有没有考虑第三种选择：你可以​​创建一个外部脚本（写在另一种语言）从生成你的code一系列模板。这与宏观方法，但你可以使用如Perl或Python语言来产生code。由于这些语言都更强大的比C pre处理器，可以避免一些在通过宏做模板固有的潜在问题。我已经在我真想在你的例子＃1使用像复杂的宏的情况下使用此方法。最后，它竟然是容易出错比使用C preprocessor少。不足之处是写生成器脚本和更新的makefile之间，这是一个有点更难以得到初步建立起（IMO但值得它到底）。

There's also a third option that you haven't considered: you can create an external script (written in another language) to generate your code from a series of templates. This is similar to the macro method, but you can use a language like Perl or Python to generate the code. Since these languages are more powerful than the C pre-processor, you can avoid some of the potential problems inherent in doing templates via macros. I have used this method in cases where I was tempted to use complex macros like in your example #1. In the end, it turned out to be less error-prone than using the C preprocessor. The downside is that between writing the generator script and updating the makefiles, it's a little more difficult to get set up initially (but IMO worth it in the end).

这篇关于没有复制粘贴实现不同但类似的结构/功能集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！