C语言 普通 C 语言中的类型安全通用数据结构？

Type-safe generic data structures in plain-old C?

提问by Brad Larsen

I have done far more C++ programming than "plain old C" programming. One thing I sorely miss when programming in plain C is type-safe generic data structures, which are provided in C++ via templates.

我完成的 C++ 编程比“普通的旧 C”编程要多得多。在用纯 C 编程时，我非常想念的一件事是类型安全的通用数据结构，它是通过模板在 C++ 中提供的。

For sake of concreteness, consider a generic singly linked list. In C++, it is a simple matter to define your own template class, and then instantiate it for the types you need.

为了具体起见，考虑一个通用的单链表。在 C++ 中，定义自己的模板类，然后将其实例化为您需要的类型是一件简单的事情。

In C, I can think of a few ways of implementing a generic singly linked list:

在C中，我可以想到几种实现通用单向链表的方法：

1. Write the linked list type(s) and supporting procedures once, using void pointers to go around the type system.
2. Write preprocessor macros taking the necessary type names, etc, to generate a type-specific version of the data structure and supporting procedures.
3. Use a more sophisticated, stand-alone tool to generate the code for the types you need.

1. 一次编写链表类型和支持过程，使用空指针绕过类型系统。
2. 使用必要的类型名称等编写预处理器宏，以生成数据结构和支持过程的特定于类型的版本。
3. 使用更复杂的独立工具为您需要的类型生成代码。

I don't like option 1, as it is subverts the type system, and would likely have worse performance than a specialized type-specific implementation. Using a uniform representation of the data structure for all types, and casting to/from void pointers, so far as I can see, necessitates an indirection that would be avoided by an implementation specialized for the element type.

我不喜欢选项 1，因为它颠覆了类型系统，并且可能比专门的特定于类型的实现具有更差的性能。就我所见，对所有类型使用数据结构的统一表示，并转换到/从空指针，需要一个间接的，这将被专门用于元素类型的实现所避免。

Option 2 doesn't require any extra tools, but it feels somewhat clunky, and could give bad compiler errors when used improperly.

选项 2 不需要任何额外的工具，但感觉有点笨拙，如果使用不当，可能会产生严重的编译器错误。

Option 3 could give better compiler error messages than option 2, as the specialized data structure code would reside in expanded form that could be opened in an editor and inspected by the programmer (as opposed to code generated by preprocessor macros). However, this option is the most heavyweight, a sort of "poor-man's templates". I have used this approach before, using a simple sed script to specialize a "templated" version of some C code.

选项 3 可以提供比选项 2 更好的编译器错误消息，因为专用数据结构代码将以扩展形式驻留，可以在编辑器中打开并由程序员检查（与预处理器宏生成的代码相反）。然而，这个选项是最重量级的，一种“穷人的模板”。我以前使用过这种方法，使用一个简单的 sed 脚本来专门化一些 C 代码的“模板化”版本。

I would like to program my future "low-level" projects in C rather than C++, but have been frightened by the thought of rewriting common data structures for each specific type.

我想用 C 而不是 C++ 来编写我未来的“低级”项目，但被为每种特定类型重写通用数据结构的想法吓坏了。

What experience do people have with this issue? Are there good libraries of generic data structures and algorithms in C that do not go with Option 1 (i.e. casting to and from void pointers, which sacrifices type safety and adds a level of indirection)?

人们对这个问题有什么经验？C 中是否有不符合选项 1 的通用数据结构和算法的良好库（即转换到空指针和从空指针转换，这牺牲了类型安全并增加了一个间接级别）？

采纳答案by Michael Burr

Option 1 is the approach taken by most C implementations of generic containers that I see. The Windows driver kit and the Linux kernel use a macro to allow links for the containers to be embedded anywhere in a structure, with the macro used to obtain the structure pointer from a pointer to the link field:

选项 1 是我看到的大多数通用容器的 C 实现所采用的方法。Windows 驱动程序工具包和 Linux 内核使用宏来允许将容器的链接嵌入到结构中的任何位置，宏用于从指向链接字段的指针获取结构指针：

• list_entry()macro in Linux
• CONTAINING_RECORD()macro in Windows

• list_entry()Linux 中的宏
• CONTAINING_RECORD()Windows 中的宏

Option 2 is the tack taken by BSD's tree.h and queue.h container implementation:

选项 2 是 BSD 的 tree.h 和 queue.h 容器实现所采用的策略：

• http://openbsd.su/src/sys/sys/queue.h
• http://openbsd.su/src/sys/sys/tree.h

• http://openbsd.su/src/sys/sys/queue.h
• http://openbsd.su/src/sys/sys/tree.h

I don't think I'd consider either of these approaches type safe. Useful, but not type safe.

我不认为我会认为这些方法中的任何一种都是安全的。有用，但不是类型安全的。

回答by Dragon Energy

C has a different kind of beauty to it than C++, and type safety and being able to always see what everything is when tracing through code without involving casts in your debugger is typically not one of them.

C 与 C++ 相比具有不同的美感，类型安全以及在跟踪代码时始终查看所有内容而不涉及调试器中的强制转换通常不是其中之一。

C's beauty comes a lot from its lack of type safety, of working around the type system and at the raw level of bits and bytes. Because of that, there's certain things it can do more easily without fighting against the language like, say, variable-length structs, using the stack even for arrays whose sizes are determined at runtime, etc. It also tends to be a lot simpler to preserve ABI when you're working at this lower level.

C 的美妙之处在于它缺乏类型安全、围绕类型系统以及位和字节的原始级别工作。正因为如此，它可以更轻松地完成某些事情，而无需与语言作斗争，例如可变长度结构，甚至将堆栈用于其大小在运行时确定的数组等。它也往往更简单在较低级别工作时保留 ABI。

So there's a different kind of aesthetic involved here as well as different challenges, and I'd recommend a shift in mindset when you work in C. To really appreciate it, I'd suggest doing things many people take for granted these days, like implementing your own memory allocator or device driver. When you're working at such a low level, you can't help but look at everything as memory layouts of bits and bytes as opposed to 'objects' with behaviors attached. Furthermore, there can come a point in such low-level bit/byte manipulation code where C becomes easier to comprehend than C++ code littered with reinterpret_casts, e.g.

所以这里涉及到不同类型的美学以及不同的挑战，我建议你在使用 C 语言时转变思维方式。为了真正欣赏它，我建议做现在很多人认为理所当然的事情，比如实现您自己的内存分配器或设备驱动程序。当您在如此低的级别上工作时，您会情不自禁地将所有内容视为位和字节的内存布局，而不是带有附加行为的“对象”。此外，在这种低级位/字节操作代码中，C 变得比 C++ 代码更容易理解reinterpret_casts，例如

As for your linked list example, I would suggest a non-intrusive version of a linked node (one that does not require storing list pointers into the element type, T, itself, allowing the linked list logic and representation to be decoupled from Titself), like so:

至于您的链表示例，我建议使用非侵入式链接节点版本（不需要将列表指针存储到元素类型T, 本身，允许链表逻辑和表示与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.
};

Now we can create a list node like so:

现在我们可以像这样创建一个列表节点：

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

To retrieve the element from the list as T*:

从列表中检索元素为 T*：

T* element = list_node->element;

Since it's C, there's no type checking whatsoever when casting pointers in this way, and that will probably also give you an uneasy feeling if you're coming from a C++ background.

由于它是 C 语言，因此在以这种方式投射指针时没有任何类型检查，如果您来自 C++ 背景，这可能也会给您带来不安的感觉。

The tricky part here is to make sure that this member, element, is properly aligned for whatever type you want to store. When you can solve that problem as portably as you need it to be, you'll have a powerful solution for creating efficient memory layouts and allocators. Often this will have you just using max alignment for everything which might seem wasteful, but typically isn't if you are using appropriate data structures and allocators which aren't paying this overhead for numerous small elements on an individual basis.

这里的棘手部分是确保该成员 ,element与您要存储的任何类型正确对齐。当您可以根据需要以便携方式解决该问题时，您将拥有一个强大的解决方案来创建高效的内存布局和分配器。通常这会让你只对所有看起来很浪费的东西使用最大对齐，但如果你使用适当的数据结构和分配器，这些数据结构和分配器不会单独为大量小元素支付这种开销，那么通常不会。

Now this solution still involves the type casting. There's little you can do about that short of having a separate version of code of this list node and the corresponding logic to work with it for every type, T, that you want to support (short of dynamic polymorphism). However, it does not involve an additional level of indirection as you might have thought was needed, and still allocates the entire list node and element in a single allocation.

现在这个解决方案仍然涉及类型转换。如果没有这个列表节点的单独版本的代码和相应的逻辑来处理你想要支持的每种类型 T，你几乎无能为力（缺乏动态多态性）。但是，它不涉及您可能认为需要的额外的间接级别，并且仍然在单个分配中分配整个列表节点和元素。

And I would recommend this simple way to achieve genericity in C in many cases. Simply replace Twith a buffer that has a length matching sizeof(T)and aligned properly. If you have a reasonably portable and safe way you can generalize to ensure proper alignment, you'll have a very powerful way of working with memory in a way that often improves cache hits, reduces the frequency of heap allocations/deallocations, the amount of indirection required, build times, etc.

在许多情况下，我会推荐这种简单的方法来实现 C 中的通用性。只需用T长度匹配sizeof(T)并正确对齐的缓冲区替换即可。如果您有一种合理的可移植和安全的方法，您可以进行概括以确保正确对齐，那么您将拥有一种非常强大的内存处理方式，这种方式通常可以提高缓存命中率，减少堆分配/解除分配的频率，需要间接访问，构建时间等。

If you need more automation like having list_new_nodeautomatically initialize struct Foo, I would recommend creating a general type table struct that you can pass around which contains information like how big T is, a function pointer pointing to a function to create a default instance of T, another to copy T, clone T, destroy T, a comparator, etc. In C++, you can generate this table automatically using templates and built-in language concepts like copy constructors and destructors. C requires a bit more manual effort, but you can still reduce it the boilerplate a bit with macros.

如果您需要更多自动化，例如list_new_node自动初始化struct Foo，我建议您创建一个通用类型表结构，您可以传递它，其中包含诸如 T 有多大的信息，一个指向函数的函数指针以创建 T 的默认实例，另一个指向复制 T、克隆 T、销毁 T、比较器等。在 C++ 中，您可以使用模板和内置语言概念（如复制构造函数和析构函数）自动生成此表。C 需要更多的手动工作，但您仍然可以使用宏将其减少为样板文件。

Another trick that can be useful if you go with a more macro-oriented code generation route is to cash in a prefix or suffix-based naming convention of identifiers. For example, CLONE(Type, ptr) could be defined to return Type##Clone(ptr), so CLONE(Foo, foo)could invoke FooClone(foo). This is kind of a cheat to get something akin to function overloading in C, and is useful when generating code in bulk (when CLONE is used to implement another macro) or even a bit of copying and pasting of boilerplate-type code to at least improve the uniformity of the boilerplate.

如果您采用更面向宏的代码生成路线，另一个有用的技巧是兑现基于前缀或后缀的标识符命名约定。例如， CLONE(Type, ptr) 可以定义为 return Type##Clone(ptr)，因此CLONE(Foo, foo)可以调用FooClone(foo). 这是在 C 中获得类似于函数重载的一种欺骗，并且在批量生成代码（当 CLONE 用于实现另一个宏时）或什至将样板类型代码复制和粘贴到至少时很有用提高样板的一致性。

回答by Chris Dodd

Option 1, either using void *or some unionbased variant is what most C programs use, and it may give you BETTER performance than the C++/macro style of having multiple implementations for different types, as it has less code duplication, and thus less icache pressure and fewer icache misses.

选项 1，使用void *或某些union基于变体是大多数 C 程序使用的，并且它可能为您提供比 C++/宏风格更好的性能，因为它具有针对不同类型的多个实现，因为它具有更少的代码重复，因此更少的 icache 压力和更少的 icache 未命中。

回答by Spudd86

GLib is has a bunch of generic data structures in it, http://www.gtk.org/

GLib 中有一堆通用数据结构，http://www.gtk.org/

CCAN has a bunch of useful snippets and such http://ccan.ozlabs.org/

CCAN 有很多有用的片段，例如http://ccan.ozlabs.org/

回答by michaeljt

An old question, I know, but in case it is still of interest: I was experimenting with option 2) (pre-processor macros) today, and came up with the example I will paste below. Slightly clunky indeed, but not terrible. The code is not fully type safe, but contains sanity checks to provide a reasonable level of safety. And dealing with the compiler error messages while writing it was mild compared to what I have seen when C++ templates came into play. You are probably best starting reading this at the example use code in the "main" function.

我知道一个老问题，但如果它仍然有趣：我今天正在试验选项 2)（预处理器宏），并提出了我将粘贴在下面的示例。确实有点笨重，但并不可怕。该代码不是完全类型安全的，但包含完整性检查以提供合理的安全级别。与我在 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;
}

回答by michaeljt

I use void pointers (void*) to represent generic data structures defined with structs and typedefs. Below I share my implementation of a lib which I'm working on.

我使用空指针 (void*) 来表示用结构和类型定义定义的通用数据结构。下面我分享我正在开发的一个库的实现。

With this kind of implementation, you can think of each new type, defined with typedef, like a pseudo-class. Here, this pseudo-class is the set of the source code (some_type_implementation.c) and its header file (some_type_implementation.h).

通过这种实现，您可以将使用 typedef 定义的每个新类型视为伪类。这里，这个伪类是源代码（some_type_implementation.c）及其头文件（some_type_implementation.h）的集合。

In the source code, you have to define the struct that will present the new type. Note the struct in the "node.c" source file. There I made a void pointer to the "info" atribute. This pointer may carry any type of pointer (I think), but the price you have to pay is a type identifier inside the struct (int type), and all the switchs to make the propper handle of each type defined. So, in the node.h" header file, I defined the type "Node" (just to avoid have to type struct node every time), and also I had to define the constants "EMPTY_NODE", "COMPLEX_NODE", and "MATRIX_NODE".

在源代码中，您必须定义将呈现新类型的结构。请注意“node.c”源文件中的结构。在那里我创建了一个指向“信息”属性的空指针。这个指针可以携带任何类型的指针（我认为），但你必须付出的代价是结构内部的类型标识符（int 类型），以及定义每种类型的正确句柄的所有开关。因此，在 node.h" 头文件中，我定义了类型 "Node"（只是为了避免每次都必须键入 struct node），并且还必须定义常量 "EMPTY_NODE"、"COMPLEX_NODE" 和 "MATRIX_NODE" ”。

You can perform the compilation, by hand, with "gcc *.c -lm".

您可以使用“gcc *.c -lm”手动执行编译。

main.c Source File

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 Source File

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 Header File

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 Source File

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 Header File

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 Source File

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 Header File

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

I hope I hadn't missed nothing.

我希望我没有错过任何东西。

回答by Christoph

There's a common variation to option 1 which is more efficient as it uses unions to store the values in the list nodes, ie there's no additional indirection. This has the downside that the list only accepts values of certain types and potentially wastes some memory if the types are of different sizes.

选项 1 有一个常见的变体，它更有效，因为它使用联合将值存储在列表节点中，即没有额外的间接性。这样做的缺点是列表只接受某些类型的值，如果类型的大小不同，可能会浪费一些内存。

However, it's possible to get rid of the unionby using flexible array member instead if you're willing to break strict aliasing. C99 example code:

但是，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;
}

回答by dmckee --- ex-moderator kitten

Your option 1 is what most old time c programmers would go for, possibly salted with a little of 2 to cut down on the repetitive typing, and just maybeemploying a few function pointers for a flavor of polymorphism.

您的选项 1 是大多数旧时 c 程序员会选择的选项，可能会添加一点 2 以减少重复键入，并且可能只是使用一些函数指针来获得多态性。

回答by mg979

You could check out https://github.com/clehner/ll.c

你可以查看https://github.com/clehner/ll.c

It's easy to use:

它易于使用：

#include <stdio.h>
#include <string.h>
#include "ll.h"

int main()
{
   int *numbers = NULL;
   *( numbers = ll_new(numbers) ) = 100;
   *( numbers = ll_new(numbers) ) = 200;

   printf("num is %d\n", *numbers);
   numbers = ll_next(numbers);
   printf("num is %d\n", *numbers);

   typedef struct _s {
      char *word;
   } s;

   s *string = NULL;
   *( string = ll_new(string) ) = (s) {"a string"};
   *( string = ll_new(string) ) = (s) {"another string"};

   printf("string is %s\n", string->word);
   string = ll_next( string );
   printf("string is %s\n", string->word);

   return 0;
}

Output:

输出：

num is 200
num is 100
string is another string
string is a string

回答by Engineer

I am using option 2 for a couple of high performance collections, and it is extremely time-consuming working through the amount of macro logic needed to do anything truly compile-time generic and worth using. I am doing this purely for raw performance (games). An X-macrosapproach is used.

我将选项 2 用于几个高性能集合，并且处理执行任何真正编译时通用且值得使用的事情所需的宏逻辑量非常耗时。我这样做纯粹是为了原始性能（游戏）。使用X 宏方法。

A painful issue that constantly comes up with Option 2 is, "Assuming some finite number of options, such as 8/16/32/64 bit keys, do I make said value a constant and define several functions each with a different element of this set of values that constant can take on, or do I just make it a member variable?" The former means a less performant instruction cache since you have a lot of repeated functions with just one or two numbers different, while the latter means you have to reference allocated variables which in the worst case means a data cache miss. Since Option 1 is purely dynamic, you will make such values member variables without even thinking about it. This truly is micro-optimisation, though.

选项 2 经常出现的一个痛苦问题是，“假设有一些有限数量的选项，例如 8/16/32/64 位密钥，我是否将所述值设为常量并定义多个函数，每个函数具有不同的元素？常量可以采用的一组值，还是我只是将其设为成员变量？” 前者意味着指令缓存的性能较低，因为您有很多重复的函数，只有一两个不同的数字，而后者意味着您必须引用分配的变量，在最坏的情况下意味着数据缓存未命中。由于选项 1 是纯动态的，因此您无需考虑即可将这些值设为成员变量。不过，这确实是微优化。

Also bear in mind the trade-off between returning pointers vs. values: the latter is most performant when the size of the data item is less than or equal to pointer size; whereas if the data item is larger, it is most likely better to return pointers than to force a copy of a large object by returning value.

还要记住返回指针与返回值之间的权衡：当数据项的大小小于或等于指针大小时，后者的性能最好；而如果数据项较大，则返回指针很可能比通过返回值强制复制大对象更好。

I would strongly suggest going for Option 1 in any scenario where you are not 100% certain that collection performance will be your bottleneck. Even with my use of Option 2, my collections library supplies a "quick setup" which is like Option 1, i.e. use of void *values in my list and map. This is sufficient for 90+% of circumstances.

我强烈建议在您不能 100% 确定收集性能将成为您的瓶颈的任何情况下使用选项 1。即使我使用了选项 2，我的收藏库也提供了类似于选项 1 的“快速设置”，即void *在我的列表和地图中使用值。这足以满足 90+% 的情况。