普通旧式C中的types安全通用数据结构
我做了比“普通的老C”编程更多的C ++编程。 在纯C编程时，我非常想念的一件事是通过模板在C ++中提供的types安全的通用数据结构。
为了具体，请考虑一个通用的单向链表。 在C ++中，定义自己的模板类是一件简单的事情，然后将其实例化为您需要的types。
在C中，我可以想到实现一个通用单链表的几种方法：
- 一次写入链表types和支持过程，使用void指针绕过types系统。
- 编写预处理macros以获取必要的types名称等，以生成数据结构和支持过程的特定于types的版本。
- 使用更复杂的独立工具来生成所需types的代码。
我不喜欢选项1，因为它颠覆了types系统，而且可能比特定types的实现具有更差的性能。 使用所有types的数据结构的统一表示，以及从void指针转换到/从void指针，据我所知，需要一个间接的，这是一个专门的元素types实现将避免。
选项2不需要任何额外的工具，但是感觉有些笨重，并且在使用不当时可能会给编译器带来不好的错误。
选项3可以提供比选项2更好的编译器错误消息，因为专用数据结构代码将以扩展forms存在，可以在编辑器中打开并由程序员检查（而不是由预处理器macros生成的代码）。 不过，这个选项是最重的，是一种“穷人的模板”。 我以前使用过这种方法，使用简单的sed脚本来专门化一些C代码的“模板化”版本。
我想用C而不是C ++来编写我的未来“低级”项目，但是由于想重写每种特定types的通用数据结构而感到害怕。
人们对这个问题有什么经验？ 在C中有没有很好的通用数据结构和algorithm库，它们不会与选项1一起使用（即，从void指针进行转换，这会牺牲types安全性并增加间接级别）？
选项1是我看到的通用容器的大多数C实现所采用的方法。 Windows驱动程序工具包和Linux内核使用macros来允许将容器的链接embedded到结构中的任何位置，使用macros从指向链接字段的指针获取结构指针：
- Linux中的
list_entry()macros - 在Windows中
CONTAINING_RECORD()macros
选项2是BSD的tree.h和queue.h容器的实现：
我不认为我会考虑这些方法中的任何一种安全。 有用的，但不是types安全的。
C有着与C ++不同的美感，并且types安全，并且能够始终明白什么是通过代码进行跟踪而不涉及debugging器中的强制转换，通常不是其中之一。
C的美丽来源于它缺乏types安全，围绕types系统以及位和字节的原始水平。 正因为如此，有些事情可以更轻松地做，而不需要像可变长度的结构体那样对抗语言，即使对于在运行时确定大小的数组，也可以使用堆栈。对于保持ABI，当你在这个较低的水平工作。
所以这里有一种不同的美学，也有不同的挑战，当你在C工作的时候，我会build议你改变一下思维模式。为了真正体会到这一点，我build议现在很多人认为理所当然的事情就像实现你自己的内存分配器或设备驱动程序。 当你在这么低的水平工作时，你不能不把所有的东西看作是位和字节的内存布局，而不是附有行为的“对象”。 而且，在这样的低级别的位/字节操作代码中，C代码比C ++代码更容易被理解，比如reinterpret_casts 。
至于你的链表的例子，我会build议一个非侵入式的链接节点（一个不需要存储列表指针到元素typesT本身，允许链接列表逻辑和表示从T本身解耦），如下所示：
struct ListNode { struct ListNode* prev; struct ListNode* next; MAX_ALIGN char element[1]; // Watch out for alignment here. // see your compiler's specific info on // aligning data members. };
现在我们可以像这样创build一个列表节点：
struct ListNode* list_new_node(int element_size) { // Watch out for alignment here. return malloc_max_aligned(sizeof(struct ListNode) + element_size - 1); } // create a list node for 'struct Foo' void foo_init(struct Foo*); struct ListNode* foo_node = list_new_node(sizeof(struct Foo)); foo_init(foo_node->element);
从列表中检索元素为T *：
T* element = list_node->element;
既然是C，那么在这种方式下投入指针的时候就没有types检查，如果你来自C ++的背景，那么也许会给你一个不安的感觉。
这里棘手的部分是要确保这个成员element正确alignment，无论你想存储什么types。 当你可以随心所欲地解决这个问题时，你将拥有一个强大的解决scheme来创build高效的内存布局和分配器。 通常情况下，这只需要使用max alignment就可能看起来很浪费，但是如果你使用的是适当的数据结构和分配器，而这些数据结构和分配器并不是在单独的基础上为许多小的元素支付这种开销，
现在这个解决scheme仍然涉及到types转换。 对于这个列表节点的单独版本的代码以及相应的逻辑来处理每种types的T，你想要支持（缺lessdynamic多态性），你可以做的事情很less。 但是，它并不涉及额外的间接级别，因为您可能认为是需要的，仍然会将整个列表节点和元素分配到一个单独的分配中。
在许多情况下，我会推荐这种简单的方法在C中实现通用性。 简单地用一个长度匹配sizeof(T)的缓冲区replaceT ，并且正确alignment。 如果你有一个合理的便携和安全的方式，你可以推广，以确保适当的alignment，你将有一个非常强大的方式处理内存的方式，往往提高caching命中，减less堆分配/释放的频率，所需间接，build造时间等
如果你需要更多的自动化，比如让list_new_node自动初始化struct Foo ，我会build议创build一个通用types的表结构，你可以传递这个表结构，它包含诸如T是多大的信息，一个函数指针指向一个函数来创build一个默认实例T ，另一个是复制T，克隆T，销毁T，比较器等。在C ++中，可以使用模板和内置的语言概念（如复制构造函数和析构函数）自动生成此表。 C需要更多的手工工作，但是你仍然可以用macros来减less样板。
另一个有用的方法是使用更加面向macros代码的代码生成path，这样就可以获得标识符的前缀或后缀名称约定。 例如，可以定义CLONE（Type，ptr）来返回Type##Clone(ptr) ，所以CLONE(Foo, foo)可以调用FooClone(foo) 。 这是一种骗取类似于C中的函数重载的东西，而且在批量生成代码（当CLONE被用来实现另一个macros的时候）或者甚至是一些复制和粘贴样板types的代码时是有用的提高样板的均匀性。
选项1，使用void *或某些基于union的变体是大多数C程序所使用的，它可以为您提供比不同types的多重实现的C ++ /macros风格更好的性能，因为它具有较less的代码重复，因此较lessicache压力和更less的icache未命中。
GLib有一堆通用的数据结构， http://www.gtk.org/
CCAN有一些有用的片段，例如http://ccan.ozlabs.org/
你的select1是大多数以前的C程序员会去做的，可能会用一点2来腌制，以减less重复的input， 也许只是用一些函数指针来表示多态。
选项1有一个共同的变化，它更有效，因为它使用联合将值存储在列表节点中，即没有额外的间接。 这有一个缺点，即列表只接受某些types的值，如果types的大小不同，可能会浪费一些内存。
但是，如果您愿意打破严格的别名，则可以使用灵活的数组成员来摆脱union 。 C99示例代码：
#include <assert.h> #include <stdio.h> #include <stdlib.h> #include <string.h> struct ll_node { struct ll_node *next; long long data[]; // use `long long` for alignment }; extern struct ll_node *ll_unshift( struct ll_node *head, size_t size, void *value); extern void *ll_get(struct ll_node *head, size_t index); #define ll_unshift_value(LIST, TYPE, ...) \ ll_unshift((LIST), sizeof (TYPE), &(TYPE){ __VA_ARGS__ }) #define ll_get_value(LIST, INDEX, TYPE) \ (*(TYPE *)ll_get((LIST), (INDEX))) struct ll_node *ll_unshift(struct ll_node *head, size_t size, void *value) { struct ll_node *node = malloc(sizeof *node + size); if(!node) assert(!"PANIC"); memcpy(node->data, value, size); node->next = head; return node; } void *ll_get(struct ll_node *head, size_t index) { struct ll_node *current = head; while(current && index--) current = current->next; return current ? current->data : NULL; } int main(void) { struct ll_node *head = NULL; head = ll_unshift_value(head, int, 1); head = ll_unshift_value(head, int, 2); head = ll_unshift_value(head, int, 3); printf("%i\n", ll_get_value(head, 0, int)); printf("%i\n", ll_get_value(head, 1, int)); printf("%i\n", ll_get_value(head, 2, int)); return 0; }
一个古老的问题，我知道，但如果它仍然是有趣的：我今天正在试验选项2）（预处理器macros），并提出了我将在下面粘贴的例子。 确实有些笨重，但并不可怕。 该代码不完全types安全，但包含健全性检查，以提供合理的安全水平。 编写错误消息时，处理编译器的错误信息与我在C ++模板发挥作用时所看到的相比是温和的。 您可能最好从“main”函数的示例使用代码开始阅读。
#include <stdio.h> #define LIST_ELEMENT(type) \ struct \ { \ void *pvNext; \ type value; \ } #define ASSERT_POINTER_TO_LIST_ELEMENT(type, pElement) \ do { \ (void)(&(pElement)->value == (type *)&(pElement)->value); \ (void)(sizeof(*(pElement)) == sizeof(LIST_ELEMENT(type))); \ } while(0) #define SET_POINTER_TO_LIST_ELEMENT(type, pDest, pSource) \ do { \ ASSERT_POINTER_TO_LIST_ELEMENT(type, pSource); \ ASSERT_POINTER_TO_LIST_ELEMENT(type, pDest); \ void **pvDest = (void **)&(pDest); \ *pvDest = ((void *)(pSource)); \ } while(0) #define LINK_LIST_ELEMENT(type, pDest, pSource) \ do { \ ASSERT_POINTER_TO_LIST_ELEMENT(type, pSource); \ ASSERT_POINTER_TO_LIST_ELEMENT(type, pDest); \ (pDest)->pvNext = ((void *)(pSource)); \ } while(0) #define TERMINATE_LIST_AT_ELEMENT(type, pDest) \ do { \ ASSERT_POINTER_TO_LIST_ELEMENT(type, pDest); \ (pDest)->pvNext = NULL; \ } while(0) #define ADVANCE_POINTER_TO_LIST_ELEMENT(type, pElement) \ do { \ ASSERT_POINTER_TO_LIST_ELEMENT(type, pElement); \ void **pvElement = (void **)&(pElement); \ *pvElement = (pElement)->pvNext; \ } while(0) typedef struct { int a; int b; } mytype; int main(int argc, char **argv) { LIST_ELEMENT(mytype) el1; LIST_ELEMENT(mytype) el2; LIST_ELEMENT(mytype) *pEl; el1.value.a = 1; el1.value.b = 2; el2.value.a = 3; el2.value.b = 4; LINK_LIST_ELEMENT(mytype, &el1, &el2); TERMINATE_LIST_AT_ELEMENT(mytype, &el2); printf("Testing.\n"); SET_POINTER_TO_LIST_ELEMENT(mytype, pEl, &el1); if (pEl->value.a != 1) printf("pEl->value.a != 1: %d.\n", pEl->value.a); ADVANCE_POINTER_TO_LIST_ELEMENT(mytype, pEl); if (pEl->value.a != 3) printf("pEl->value.a != 3: %d.\n", pEl->value.a); ADVANCE_POINTER_TO_LIST_ELEMENT(mytype, pEl); if (pEl != NULL) printf("pEl != NULL.\n"); printf("Done.\n"); return 0; }
我使用void指针（void *）来表示通过structs和typedefs定义的通用数据结构。 下面我分享我正在执行的一个lib的实现。
通过这种实现，您可以将每个使用typedef定义的新types想象为一个伪类。 在这里，这个伪类是源代码（some_type_implementation.c）及其头文件（some_type_implementation.h）的集合。
在源代码中，您必须定义将呈现新types的结构。 注意“node.c”源文件中的结构。 在那里我做了一个void指针的“信息”属性。 这个指针可以携带任何types的指针（我认为），但是你必须支付的价格是struct（int type）中的一个types标识符，以及所有的开关来定义每种types的propper句柄。 因此，在node.h头文件中，我定义了“Node”types（只是为了避免每次都inputstruct node），还必须定义常量“EMPTY_NODE”，“COMPLEX_NODE”和“MATRIX_NODE ”。
您可以用“gcc * .c -lm”手动执行编译。
main.c源文件
#include <stdio.h> #include <math.h> #define PI M_PI #include "complex.h" #include "matrix.h" #include "node.h" int main() { //testCpx(); //testMtx(); testNode(); return 0; }
node.c源文件
#include <stdio.h> #include <stdlib.h> #include <math.h> #include "node.h" #include "complex.h" #include "matrix.h" #define PI M_PI struct node { int type; void* info; }; Node* newNode(int type,void* info) { Node* newNode = (Node*) malloc(sizeof(Node)); newNode->type = type; if(info != NULL) { switch(type) { case COMPLEX_NODE: newNode->info = (Complex*) info; break; case MATRIX_NODE: newNode->info = (Matrix*) info; break; } } else newNode->info = NULL; return newNode; } int emptyInfoNode(Node* node) { return (node->info == NULL); } void printNode(Node* node) { if(emptyInfoNode(node)) { printf("Type:%d\n",node->type); printf("Empty info\n"); } else { switch(node->type) { case COMPLEX_NODE: printCpx(node->info); break; case MATRIX_NODE: printMtx(node->info); break; } } } void testNode() { Node *node1,*node2, *node3; Complex *Z; Matrix *M; Z = mkCpx(POLAR,5,3*PI/4); M = newMtx(3,4,PI); node1 = newNode(COMPLEX_NODE,Z); node2 = newNode(MATRIX_NODE,M); node3 = newNode(EMPTY_NODE,NULL); printNode(node1); printNode(node2); printNode(node3); }
node.h头文件
#define EMPTY_NODE 0 #define COMPLEX_NODE 1 #define MATRIX_NODE 2 typedef struct node Node; Node* newNode(int type,void* info); int emptyInfoNode(Node* node); void printNode(Node* node); void testNode();
matrix.c源文件
#include <stdio.h> #include <stdlib.h> #include <math.h> #include "matrix.h" struct matrix { // Meta-information about the matrix int rows; int cols; // The elements of the matrix, in the form of a vector double** MTX; }; Matrix* newMtx(int rows,int cols,double value) { register int row , col; Matrix* M = (Matrix*)malloc(sizeof(Matrix)); M->rows = rows; M->cols = cols; M->MTX = (double**) malloc(rows*sizeof(double*)); for(row = 0; row < rows ; row++) { M->MTX[row] = (double*) malloc(cols*sizeof(double)); for(col = 0; col < cols ; col++) M->MTX[row][col] = value; } return M; } Matrix* mkMtx(int rows,int cols,double** MTX) { Matrix* M; if(MTX == NULL) { M = newMtx(rows,cols,0); } else { M = (Matrix*)malloc(sizeof(Matrix)); M->rows = rows; M->cols = cols; M->MTX = MTX; } return M; } double getElemMtx(Matrix* M , int row , int col) { return M->MTX[row][col]; } void printRowMtx(double* row,int cols) { register int j; for(j = 0 ; j < cols ; j++) printf("%g ",row[j]); } void printMtx(Matrix* M) { register int row = 0, col = 0; printf("\vSize\n"); printf("\tRows:%d\n",M->rows); printf("\tCols:%d\n",M->cols); printf("\n"); for(; row < M->rows ; row++) { printRowMtx(M->MTX[row],M->cols); printf("\n"); } printf("\n"); } void testMtx() { Matrix* M = mkMtx(10,10,NULL); printMtx(M); }
matrix.h头文件
typedef struct matrix Matrix; Matrix* newMtx(int rows,int cols,double value); Matrix* mkMatrix(int rows,int cols,double** MTX); void print(Matrix* M); double getMtx(Matrix* M , int row , int col); void printRowMtx(double* row,int cols); void printMtx(Matrix* M); void testMtx();
complex.c源文件
#include <stdio.h> #include <stdlib.h> #include <math.h> #include "complex.h" struct complex { int type; double a; double b; }; Complex* mkCpx(int type,double a,double b) { /** Doc - {{{ * This function makes a new Complex number. * * @params: * |-->type: Is an interger that denotes if the number is in * | the analitic or in the polar form. * | ANALITIC:0 * | POLAR :1 * | * |-->a: Is the real part if type = 0 and is the radius if * | type = 1 * | * `-->b: Is the imaginary part if type = 0 and is the argument * if type = 1 * * @return: * Returns the new Complex number initialized with the values * passed *}}} */ Complex* number = (Complex*)malloc(sizeof(Complex)); number->type = type; number->a = a; number->b = b; return number; } void printCpx(Complex* number) { switch(number->type) { case ANALITIC: printf("Re:%g | Im:%g\n",number->a,number->b); break; case POLAR: printf("Radius:%g | Arg:%g\n",number->a,number->b); break; } } void testCpx() { Complex* Z = mkCpx(ANALITIC,3,2); printCpx(Z); }
complex.h头文件
#define ANALITIC 0 #define POLAR 1 typedef struct complex Complex; Complex* mkCpx(int type,double a,double b); void printCpx(Complex* number); void testCpx();
我希望我没有遗漏任何东西。
我想用C而不是C ++来编写我的未来“低级”项目。
为什么？ 您的目标是否缺乏C ++编译器或C ++运行时？
我正在使用选项2来实现一些高性能的集合，而且通过执行任何真正的编译时通用的值得使用的macros逻辑的数量是非常耗时的。 我纯粹是为了原始表演（游戏）。 使用Xmacros的方法。
选项2不断出现的一个令人痛苦的问题是：“假设一些有限数量的选项，比如8/16/32/64比特键，是否使所述值保持不变，并定义几个函数，每个函数都有不同的元素常量可以采取的一组值，还是我只是使它成为一个成员variables？ 前者意味着一个性能较低的指令caching，因为你有很多重复的函数，只有一个或两个不同的数字，而后者意味着你必须引用分配的variables，这在最糟糕的情况下意味着数据caching未命中。 由于选项1纯粹是dynamic的，因此您将不必考虑这些成员variables。 不过，这确实是微观优化。
还要记住返回指针与值之间的折中：当数据项的大小小于或等于指针大小时，后者是最高性能的; 而如果数据项较大，则最好返回指针，而不是通过返回值强制大对象的副本。
我强烈build议在任何情况下select第一种方式，在这种情况下，您不能100％确定收集性能将成为您的瓶颈。 即使使用了选项2，我的集合库也提供了类似选项1的“快速设置”，即在列表和地图中使用void *值。 这对于90％以上的情况已经足够了。
