безопасный способ выделения памяти для узла списка - PullRequest
Новая
       24

безопасный способ выделения памяти для узла списка

3 голосов
/ 03 апреля 2009

В простом списке, например: 

struct Node {  
    Node *next;  
    void *data;  
}

есть ли проблема, если я выделяю Узел и Данные в одном выделении (если я знаю размер), как 

Node * t = (Node*)malloc(sizeof(Node) + DataSize));

и всегда назначать данные в конце выделенного фрагмента, 

t->data = (BYTE*)t+ sizeof(Node); /* BYTE is byte length, can use char in gcc */

Узел и данные будут удалены за один проход, поэтому нет реальной проблемы их связывания (по замыслу)

Я смотрю на проблемы переносимости (особенно с упаковкой) или другие неизвестные проблемы?

Является ли этот способ распределения безопасным и переносимым?

Ответы [ 4 ]

4 голосов
/ 03 апреля 2009

Как уже говорилось, не стоит возвращать malloc() в C, это бесполезно и может скрывать ошибки.

Кроме того, чтобы вычислить адрес, следующий за заголовком узла, я считаю более понятным сделать это следующим образом: 

t->data = t + 1;

Это работает, потому что t является типизированным указателем, поэтому арифметика на нем работает нормально. Добавление одного увеличивает его на размер указанных данных, то есть sizeof (Node) в этом случае. Я нахожу это использование идиоматичным для этого конкретного случая вычисления адреса, следующего сразу за чем-то просто malloc() ed (когда это «что-то» является четко определенным типом со статически известным размером, как структура Node в этом случае, конечно).

Это имеет следующие преимущества:

  • Нет повторения имени типа.
  • Нет sizeof, так что короче.
  • Опять же, нет актеров.
  • Очень простая арифметика, легко читаемая.

Я понял, что при использовании типа Node произошла ошибка до того, как он был должным образом объявлен. Я не согласен с решением Диркгентли, вот как оно должно выглядеть, в C: 

/* This introduces the type name "Node", as an alias for an undefined struct. */
typedef struct Node Node;

struct Node {
  Node *next; /* This is OK, the compiler only needs to know size of pointer. */
  void *data;
};

Для полноты, и поскольку я не устаю показывать, как я считаю, код должен быть написан следующим образом, вот пример функции для создания нового узла для хранения n байтов данных: 

Node * node_new(size_t n)
{
  Node *node;

  if((node = malloc(sizeof *node + n)) != NULL)
  {
    node->next = NULL;
    node->data = node + 1;
  }
  return node;
}

Вот и все. Обратите внимание на использование sizeof для цели указателя в вызове malloc(), чтобы избежать повторения имени типа и создания легко забываемой зависимости, если тип когда-либо изменится.

3 голосов
/ 03 апреля 2009

Технически, это может быть небезопасно, если данные имеют требования к выравниванию. malloc () возвращает указатель, соответствующим образом выровненный для всех типов, и вполне вероятно, что t+1 также выровнен. Скорее всего, но не гарантировано.

2 голосов
/ 03 апреля 2009

Вы не можете использовать Node в качестве типа, пока не создадите псевдоним. Использование: 

typedef struct Node {
   struct Node* n;
   void* data;
}Node;

Не нужно приводить результат malloc, если вы собираетесь придерживаться компилятора C. Мне легче читать и читать: 

Node* t = malloc(sizeof *t + DataSize);

BYTE не является стандартным типом, определяемым языком, и, следовательно, непереносим . Что пытается выполнить следующая строка? 

t->data = (BYTE*)t+ sizeof(Node);

Если вы хотите назначить что-то, достаточно следующего: 

t->data = pointer to some data ...

Если вы хотите получить смещение в байтах, используйте макрос offsetof.

Упаковка зависит от реализации. Вы должны обратиться к соответствующей документации компилятора и посмотреть, что вам доступно.

Кроме того, вы можете захотеть иметь объект head, который хранит некоторую служебную информацию о списке (длина и т. Д.).

1 голос
/ 03 апреля 2009

Я согласен с @MSalters. Пока у вас есть уровень косвенности (указатель data), вы также можете делать все правильно и выделять для него отдельный блок.

Теперь альтернативой будет использование гибкого элемента массива , определенного в C99: 

typedef struct Node {
    struct Node *next;
    char data[];
} Node;

Node *n = malloc(sizeof(*n) + DataSize * sizeof(*data));
//if (n != NULL), access data[0 ~ DataSize-1]

sizeof(struct Node) дополняется соответствующим количеством отступов (если оно есть), так что требования выравнивания data выполнены, а data[] действует так, как если бы он был объявлен как массив максимально возможного размера, соответствовать блоку памяти, возвращенному malloc(). Это касается всех типов data, а не только char (отсюда и второй sizeof).

...