c - Is it possible to create generic functions in C?

Question

I am getting back into using C, but I've been spoiled by generics in other languages. I have made it to the following piece of code in my implementation of a resizable array:

typdef struct {
  void** array;
  int length;
  int capacity;
  size_t type_size;
} Vector;

void vector_add(Vector* v, void* entry) {
  // ... code for adding to the array and resizing
}

int main() {
  Vector* vector = vector_create(5, sizeof(int));
  vector_add(vector, 4); // This is erroneous...
  // ...
}

In my attempt to make this generic, I'm now unable to add an integer to the vector without storing it in memory somewhere else.

Is there any way to make this work (either as is, or possibly a better approach to generics)?

score 7 · Accepted Answer

对于我的回答，我假设您不熟悉内存部分（即内存池的使用）。

为了使这个通用化，我现在无法将整数添加到向量而不将其存储在内存中的其他地方。

如果您想创建一个通用结构（就像您所做的那样），那么您将需要使用 void 指针。因此，通过使用 void 指针，您将需要将每个字段的值存储在内存池中，或者在不常见的情况下存储在堆栈中。请注意，该结构由 void 指针组成，因此结构中仅包含内存地址，指向内存中值所在的其他位置。

如果您在堆栈上声明它们，请小心，因为一旦从调用堆栈中弹出堆栈帧，这些内存地址就被认为是无效的，因此可能会被另一个堆栈帧使用（覆盖该内存地址集合中的现有值） .

另外：如果您迁移到 C++，那么您可以考虑使用 C++ 模板。

score 2 · Accepted Answer

是的; 您可以接受Greenspun 的第十条规则并用 C 开发一门成熟的动态语言，并在此过程中开发一个可以在 C 中使用的相对干净的 C 运行时。

在这个项目中，我就是这样做的，就像我之前的其他人一样。

在这个项目的 C 运行时，一个通用编号将从 C 编号创建，如下所示：

val n = num(42);

由于val表示方式，它只占用一个机器字。类型标签的几位用于区分数字与指针、字符等。

还有这个：

val n = num_fast(42);

这要快得多（一个位操作宏），因为它不会对数字 42 是否适合“fixnum”范围进行任何特殊检查；它用于小整数。

将其参数添加到向量的每个元素的函数可以这样编写（非常低效）：

val vector_add(val vec, val delta)
{
   val iter;
   for (iter = zero; lt(iter, length(vec)); iter = plus(iter, one)) {
      val *pelem = vecref_l(vec, iter);
      *pelem = plus(*pelem, delta);
   }
   return nil;
}

由于plus是通用的，这将适用于 fixnums、bignums 和 reals，以及字符，因为可以通过plus.

类型不匹配错误将被较低级别的函数捕获并变成异常。例如如果vec不是length可以应用的东西，length就会抛出。

带_l后缀的函数返回一个位置。而返回向量vecref(v, i)中偏移处的值，则返回指向向量中存储该值的类型化位置的指针。ivvecref_l(v, i)val

都是 C，只是 ISO C 规则有点弯曲：你不能val在严格符合 C 的情况下高效地创建一个类型，但是你可以很容易地将它移植到你关心支持的体系结构和编译器中。

我们vector_add的不够通用。有可能做得更好：

val sequence_add(val vec, val delta)
{
   val iter;
   for (iter = zero; lt(iter, length(vec)); iter = plus(iter, one)) {
      val elem = ref(vec, iter);
      refset(vec, iter, plus(elem, delta));
   }
   return nil;
}

通过使用通用refand refset，这现在也适用于列表和字符串，而不仅仅是向量。我们可以这样做：

val str = string(L"abcd");
sequence_add(str, num(2));

的内容str将更改为，因为在每个字符cdef上都添加了一个位移。2

score 1 · Accepted Answer

这种方法可能会让你感到恐惧，但如果你不需要任何类型专用逻辑，它就可以工作：

// vector.h
#ifndef VECTOR_H
#define VECTOR_H

#define VECTOR_IMP(itemType) \
   typedef struct {          \
      itemType * array;      \
      int length;            \
      int capacity;          \
   } itemType##_Vector;      \
                             \
   static inline void itemType##_vector_add(itemType##_Vector* v, itemType v) { \
      // implementation of adding an itemType object to the array goes here     \
   }                                                                            \
                                                                                \
   [... other static-inline generic vector methods would go here ...]           \

// Now we can "instantiate" versions of the Vector struct and methods for
// whatever types we want to use.
VECTOR_IMP(int);
VECTOR_IMP(float);
VECTOR_IMP(char);

#endif

...以及一些示例调用代码：

#include "vector.h"

int main(int argc, char ** argv)
{
   float_Vector fv = {0};
   int_Vector iv = {0};
   char_Vector cv = {0};

   int_vector_add(&iv, 5);
   float_vector_add(&fv, 3.14f);
   char_vector_add(&cv, 'A');

   return 0;
}

score 1 · Accepted Answer

你的想法可以做到：

int *new_int = (int*)malloc(sizeof(int));
*new_int = 4;
vector_add(vector, new_int);

自然，做一个int *create_int(int x)函数或类似的东西是个好主意：

int *create_int(int x)
{
    int *n = (int*)malloc(sizeof(int));
    *n = 4;
    return n;
}
//...
vector_add(vector, create_int(4));

如果您的环境允许，您可以考虑使用经过良好测试、广泛使用且已经管理所有这些的库，例如 Glib。甚至是 C++。

score 1 · Accepted Answer

您可以通过存储数据而不是指向它的指针来避免进行许多小分配，例如

typedef struct {
  char* array;
  int length;
  int capacity;
  size_t type_size;
} Vector;

bool vector_add(Vector* v, void* entry)
{
    if (v->length < v->capacity || vector_expand(v)) {
        char* location = v->array + (v->length++)*(v->type_size);
        memcpy(location, entry, v->type_size);
        return 1;
    }
    return 0; // didn't fit
}

int main()
{
    Vector* vector = vector_create(5, sizeof(int));
    int value = 4;
    vector_add(vector, &value); // pointer to local is ok because the pointer isn't stored, only used for memcpy
}

score 1 · Accepted Answer

是的，这是我的一个实现（类似于你的），它可能会有所帮助。它使用可以用函数调用包装的宏来获取立即值。

#ifndef VECTOR_H
# define VECTOR_H

# include <stddef.h>
# include <string.h>

# define VECTOR_HEADROOM 4

/* A simple library for dynamic
 * string/array manipulation
 *
 * Written by: Taylor Holberton
 * During: July 2013
 */

struct vector {
    void * data;
    size_t  size, len;
    size_t  headroom;
};

int vector_init (struct vector *);

size_t vector_addc  (struct vector *, int index, char c);
size_t vector_subc  (struct vector *, int index);

// these ones are just for strings (I haven't yet generalized them)
size_t vector_adds (struct vector *, int index, int iend, const char * c);
size_t vector_subs (struct vector *, int ibegin, int iend);

size_t vector_addi (struct vector *, int index, int i);
size_t vector_subi (struct vector *, int index);

# define vector_addm(v, index, datatype, element)                        \
do {                                                                    \
    if (!v) return 0;                                               \
                                                                    \
    if (!v->size){                                                  \
            v->data = calloc (v->headroom, sizeof (datatype));      \
            v->size = v->headroom;                                  \
    }                                                               \
                                                                    \
    datatype * p = v->data;                                         \
                                                                    \
    if (v->len >= (v->size - 2)){                                   \
            v->data = realloc (v->data,                             \
                    (v->size + v->headroom) * sizeof (datatype));   \
            p = v->data;                                            \
            memset (&p[v->size], 0, v->headroom * sizeof(datatype));\
            v->size += v->headroom;                                 \
    }                                                               \
                                                                    \
    if ((index < 0) || (index > v->len)){                           \
            index = v->len;                                         \
    }                                                               \
                                                                    \
    for (int i = v->len; i >= index; i--){                          \
            p[i + 1] = p[i];                                        \
    }                                                               \
                                                                    \
    p[index] = element;                                             \
                                                                    \
    v->len++;                                                       \
                                                                    \
} while (0)


# define vector_subm(v, index, datatype)                                 \
do {                                                                    \
    if (!v || !v->len){                                             \
            return 0;                                               \
    }                                                               \
                                                                    \
    if ((index < 0) || (index > (v->len - 1))){                     \
            index = v->len - 1;                                     \
    }                                                               \
                                                                    \
    datatype * p = v->data;                                         \
                                                                    \
    for (int i = index; i < v->len; i++){                           \
            p[i] = p[i + 1];                                        \
    }                                                               \
                                                                    \
    v->len--;                                                       \
                                                                    \
    if ((v->size - v->len) > v->headroom){                          \
            v->data = realloc (v->data, ((v->size - v->headroom) + 1) * sizeof (datatype));\
            v->size -= v->headroom;                                 \
    }                                                               \
                                                                    \
} while (0)

#endif

我通常像这样包装它们：

size_t vector_addi (struct vector * v, int index, int i){
    vector_addm (v, index, int, i);
    return v->len;
}

我没有对此代码进行审查，但我一直在我正在编写的一个大型程序中使用它，并且我没有遇到任何内存错误（使用valgrind）。

唯一真正缺少的东西（我一直想添加）从数组中添加和减去数组的能力。

编辑：我相信你也可以用做同样的事情stdarg.h，但我从未尝试过。

score 1 · Accepted Answer

您要求更好的方法吗？这里是：https ://github.com/me-leypold/glitzersachen-demos/tree/master/generix/v0-2011 （披露：这是我的代码）。

让我简短地解释一下：

我想要类型安全的泛型容器（在其他语言中将由适当的泛型 (Ada) 或参数多态性 (OCaml) 提供。这是 C 中最缺少的特性。
宏无法做到这一点（我不打算详细解释。我只想说：模板扩展或通用实例化的结果本身应该是一个模块：在 C 中，这意味着导出了预处理器符号分别可用于模块配置（如 -DUSE_PROCESS_QUEUE_DEBUGCODE），如果您使用 C 宏生成实例，则无法做到这一点。
我通过将元素大小和所有相关操作移动到描述性结构中来抽象元素类型。这将传递给通用代码的每次调用。请注意，描述符描述了元素类型，因此每个通用实例都需要一个描述符实例。
我正在使用模板处理器为通用代码创建一个瘦类型安全前端模块。

例子：

这是检索元素的通用代码的原型：

void fifo_get ( fifo_DESCRIPTOR* inst, fifo* , void* var );

这是描述符类型：

typedef struct fifo_DESCRIPTOR {
  size_t maxindex;
  size_t element_size;
} fifo_DESCRIPTOR;

这是类型安全包装器模板中的模板代码：

<<eT>>  <<>>get  ( <<T>>* f ) { 
   <<eT>> e; fifo_get( &DESCRIPTOR, (fifo*) f, (void*) &e ); return e; 
}

这就是模板扩展器（实例化泛型）从模板产生的内容：

float   floatq_get  ( floatq* f ) { 
    float e; fifo_get( &DESCRIPTOR, (fifo*) f, (void*) &e ); return e; 
}

所有这些都有一个很好的 make 集成，但在实例化中几乎没有任何类型安全性。每个错误只有在使用 cc 编译时才会出现。

我目前无法证明为什么要坚持使用 C 中的源文本模板而不是迁移到 C++。对我来说，这只是一个实验。

问候。

score 0 · Accepted Answer

您可以只返回一个指向调用者可以存储它的位置的指针，而不是让向量类存储添加的对象：

typdef struct {
    char *buffer;
    size_t length;
    size_t capacity;
    size_t type_size;
} Vector;

void *vector_add(Vector* v)
{
    if (v->length == v->capacity) {
        // ... increase capacity by at least one
        // ... realloc buffer to capacity * type_size
    }
    return v->buffer + v->type_size * v->length++;
}

// in main:
*(int*)vector_add(v) = 4;

score 0 · Accepted Answer

使用一些非标准的GNU C 扩展，可以定义具有推断参数类型的通用函数。该宏在语句表达式中定义了一个嵌套函数，并使用以下方法推断参数类型：typeof

#include <stdio.h>

#define fib(n1) ({\
        typeof(n1) func(typeof(n1) n){\
            if (n <= 1)\
              return n;\
            return func(n-1) + func(n-2);\
        }\
        func(n1);\
    })

int main()
{
    printf("%d\n",fib(3));
    printf("%f\n",fib(3.0));
    return 0;
}

c - Is it possible to create generic functions in C?

9 回答 9

Related

Reference