获取void *的大小来创建一个简单的通用动态分配数组 - C.

I have created a simple dynamic array in C.

我在C中创建了一个简单的动态数组。

typedef struct varray_t
{
    void **memory;
    size_t allocated;
    size_t used;
    int index;              
} varray;

void
varray_init(varray **array)
{
    *array = (varray*) malloc (sizeof(varray));    
    (*array)->memory = NULL;
    (*array)->allocated = 0;
    (*array)->used = 0;
    (*array)->index = -1;
}

void
varray_push(varray *array, void *data, size_t size)
{
    if ((array->allocated - array->used) < size) {
        array->memory = realloc(array->memory, array->allocated + size);
        array->allocated = array->allocated + size;
    }

    array->used = array->used + size;   
    array->memory[++array->index] = data;
}

int
varray_length(varray *array)
{
    return array->index + 1;
}

void
varray_clear(varray *array)
{
    int i;
    for(i = 0; i < varray_length(array); i++)
    {
        array->memory[i] = NULL;
    }    
    array->used = 0;
    array->index = -1;
}

void 
varray_free(varray *array)
{
    free(array->memory);
    free(array);
}

void*
varray_get(varray *array, int index)
{
    if (index < 0 || index > array->index)
        return NULL;

    return array->memory[index];
}

This is working fine. But to add an item into the array, caller has to pass in the size of the element getting added. I can't figure out another way to get the size from the passed in void*. I am wondering is there a better way to design varray_push(varray *array, void *data, size_t size) so that size can be infered?

这工作正常。但是要将一个项添加到数组中,调用者必须传入要添加的元素的大小。我无法想出另一种方法来从传递的void *中获取大小。我想知道是否有更好的方法来设计varray_push(varray * array,void * data,size_t size)以便可以推测尺寸?

Any help would be great

任何帮助都会很棒

Edited code after the suggestions

建议后编辑代码

My array will contain only pointer elements. I have modified the code according to Blastfurnace's suggestion. New code will use sizeof(void*) and resize memory by a constant propotion to get amortized constant time on inserts.

我的数组只包含指针元素。我根据Blastfurnace的建议修改了代码。新代码将使用sizeof(void *)并通过常量propotion调整内存大小以在插入上获得分摊的常量时间。

void
varray_push(varray *array, void *data)
{
    size_t toallocate;
    size_t size = sizeof(void*);
    if ((array->allocated - array->used) < size) {
        toallocate = array->allocated == 0 ? size : (array->allocated * 2);
        array->memory = realloc(array->memory, toallocate);
        array->allocated = array->allocated + toallocate;
    }

    array->memory[++array->index] = data;
    array->used = array->used + size;
}

2 个解决方案

#1

If the array is going to contain only one type at a time, then you can store the size of the type of the array in varray_init.

如果数组一次只包含一种类型,那么可以在varray_init中存储数组类型的大小。

Also, my suggestion is that instead of allocating memory fresh for each element, you can allocate memory for constant size each time, i.e. first allocate memory for 16 elements and then when you find that array is full when pushing an element realloc for 16 + 16 = 32 elements. In this way, you can avoid calling malloc again and again and also it is not good idea to keep mallocing for small size data seperately.

另外,我的建议是,不是为每个元素分配新鲜内存,而是每次都可以为常量大小分配内存,即首先为16个元素分配内存,然后在推送元素realloc为16 + 16时发现该数组已满= 32个元素。通过这种方式,您可以避免一次又一次地调用malloc,并且单独继续对小尺寸数据进行mallocing也不是一个好主意。

EDIT: After considering Blastfurnace comment, I feel that you should actually be doing a memcpy of the data rather than assignment if your intention is to store the data and not the pointer to the data.

编辑:在考虑了Blastfurnace的评论之后,我觉得如果您的意图是存储数据而不是指向数据的指针,我应该实际上是在做数据的memcpy而不是分配。

#2

I have a simple to use linked list implementation that you can use. I wouldn't say it is text book quality but it is easy: https://github.com/inorton/xrlist

我有一个简单易用的链表实现,你可以使用。我不会说它是教科书的质量但很容易:https://github.com/inorton/xrlist

#include <stdio.h>
#include "xrlist.h"

xr_list_t * mylist = xrlist_new();

xrlist_push(mylist, (void*) ptr1);
xrlist_push(mylist, (void*) ptr2);

You iterate like so:-

你像这样迭代: -

xr_list_item_t * iter = mylist->head;
while ( iter != NULL ) 
{
  printf(" * item [0x%x] contains [%s]\n",
    (unsigned int) iter->object, (char*) iter->object );
  iter = iter->next; 
}

You also have the usual remove/add/free functions too. See more examples here.

你也有通常的删除/添加/免费功能。在此处查看更多示例。

If you want random access data like a dictionary you can also try out https://github.com/inorton/xrhash

如果你想要随机访问数据,如字典,你也可以尝试https://github.com/inorton/xrhash

#1