C: Более хороший синтаксис для общих структур данных, использующих пустые указатели? - PullRequest
Новая
       43

C: Более хороший синтаксис для общих структур данных, использующих пустые указатели?

3 голосов
/ 24 марта 2012

В настоящее время я пишу реализацию стека на C. Мне нужно, чтобы она использовала как можно меньше памяти и работала как можно быстрее, сохраняя при этом каждый тип данных, который я могу использовать, с несколькими типами в каждом стеке. Я решил использовать для этого пустые указатели и заставил его работать относительно быстро, несмотря на мой ржавый C. Однако на самом деле использовать его довольно некрасиво.

Для тестирования стека я помещаю целые числа с помощью цикла. На самом деле проблема заключается в передаче int как пустого указателя.

Мое первое желание было использовать &: 

for (int i = 0; i < 20; i++){
    stack_push(s, &i); //s is the stack_t pointer
}

Однако при ближайшем рассмотрении это, очевидно, не сработает, поскольку i разрушительно обновляется на каждом этапе. Каждый элемент в стеке заканчивается как 20.

С тех пор я обратился к очень уродливому решению: 

for (int i = 0; i < 20; i++){
    int* p = malloc(sizeof(void*));
    *p = i;
    stack_push(s, p);
}

Это работает , но представляет две проблемы:

  1. Это некрасиво

  2. Мне нужно беспокоиться об управлении памятью для каждого элемента стека. (и по какой-то причине ручной обход стека и освобождение каждого элемента все еще приводит к утечке памяти ...)

Есть ли лучший способ сделать это, не тратя ненужную память на объединение и все еще быть быстрым? Спасибо.

Ответы [ 2 ]

2 голосов
/ 24 марта 2012

если я не понял неправильно, то вам нужен стек, в который вы можете помещать в него данные любого типа.Вот идея "структурировать любой".Я думаю, что это помогло бы. 

union multitype
{
    int     asInt;
    void    *asVPtr;
    TYPE_A  *asA;
    TYPE_B  *asB;
    ...
}

typedef struct _any {
    int              type;
    union multitype  value;
} Any;

void any_put_int(Any *pAny, int value);
void any_put_v_ptr(Any *pAny, void *value);
void any_put_typeA_ptr(Any *pAny, TYPE_A *value);
void any_put_typeB_ptr(Any *pAny, TYPE_B *value);
...

int     any_get_int(Any *pAny);
void*   any_get_v_ptr(Any *pAny);
TYPE_A* any_get_typeA_ptr(Any *pAny);
TYPE_B* any_get_typeB_ptr(Any *pAny);
...

Если бы мы получили стек, основанный на struct Any, коды в вопросе были бы такими: 

for (int i = 0; i < 20; i++){
    Any anAny;
    any_put_int(&anAny, i);
    stack_push(s, anAny); // or stack_push(s, &anAny);
}
1 голос
/ 24 марта 2012

Если типы будут смешанными, что-то должно знать, что это за тип.

Если клиент (или пользователь) стека преобразует типы обратно в правильную форму, то это нормально, но размер все еще должен быть доступен для стека.

Если звонящий знает это тоже, интерфейс может выглядеть так:

void push (const int size, void * value); void pop (const int size, void ** valueptr);

Я не думаю, что в целом это будет надежно, но если вы пишете компилятор, он может сгенерировать весь правильный код, так же, как и компилятор C.

Внутренне, у меня было бы две версии, одна для отладки, которая сохраняет значение размера, а другая для «производительности», которая не имеет. Сначала я буду отлаживать.

Я бы отказался от идеи указателей, потому что

  1. используется дополнительное пространство
  2. выделенное пространство должно чем-то управляться.

Если в стеке хранятся значения, то после извлечения он не несет никакой ответственности.

Реализация: 

unsigned char space[BIG];
unsigned char *stack = &space[0];
int top = 0;
void push(const int size, void* value) {
    unsigned char* valp = (char *)value;
    *(int *)stack = size;
    stack += sizeof(int);
    for (int i=0; i<size; ++i) {
       *stack++ = *val++;
    }
}

поп наоборот,

...