3

Давеча написал зачаток библиотеки для работы с двусвязными списками. Товарищи, дайте критику:

// ---------------------------------------------- //
// Doubly linked list implementation by maksspace //
// ---------------------------------------------- //

#ifndef maksspace_list_h
#define maksspace_list_h

typedef struct { void *prev, *next; } node_link_t;

/* this macros through the list starting from the $head while     maintaining the current node in $current */
#define list_foreach(head, current) \
for(typeof(head) current = head; current != NULL; current = current->next)

/* insert $node before $head, and return pointer on new head of list */
void* list_prepend(void* node, void* head) {
    *(node_link_t*)node = (node_link_t){NULL, head};
    return ((node_link_t*)head)->prev = node;
}

/* insert $node after $tail, and return pointer on new tail of list */
void* list_append(void* tail, void* node) {
    *(node_link_t*)node = (node_link_t){tail, NULL};
    return ((node_link_t*)tail)->next = node;
}

/* insert $new_node between $prev and $next, return pointer on $new_node */
void* list_insert(void* new_node, void* prev, void* next) {
    *(node_link_t*)new_node = (node_link_t){prev, next};
    return ((node_link_t*)prev)->next = ((node_link_t*)next)->prev = new_node;
}

/* delete nodes between $from and $to */
void list_nodes_del(void* from, void* to) {
    ((node_link_t*)from)->next = to;
    ((node_link_t*)to)->prev = from;
}

/* -----------------------------------
 * Each node of the list must contain:
 * struct node_name *prev, *next;
 * at the beginning.
 * -----------------------------------
 * Example:

   typedef struct your_node_name {
       struct your_node_name *prev, *next;
       int my_cool_int;
       float my_cool_float;
       ...
       struct { ... } name;
   } me_node_name;
 */

#endif /* maksspace_list_h */
7
  • 2
    Неудачная попытка изобрести шаблоны там, где их нет. В утиль.
    – gbg
    2 фев 2016 в 22:00
  • Почему же сразу в утиль?)
    – maksspace
    2 фев 2016 в 22:12
  • Для начала, с этой реализацией github.com/torvalds/linux/blob/master/include/linux/list.h уже ознакомились?
    – avp
    2 фев 2016 в 22:19
  • @avp да. но api там ужасное
    – maksspace
    2 фев 2016 в 22:41
  • Дело вкуса, меня не коробит, хотя самому частенько линейные списки кажутся проще циклических.
    – avp
    2 фев 2016 в 22:43

1 ответ 1

1

Посмотрел ваш https://github.com/maksspace/mylist

list_insert(void* new, void* prev, void* next), возвращающий new, какой-то неочевидный.

Понимаете, если между prev и next есть элементы списка, то они теряются. Я бы подумал над тем, чтобы возвращать исключаемый подсписок (причем с аккуратно модифицированными головой и хвостом) и переименовал этот insert во что-то более отражающее суть дела.

В таком случае аналогичные изменения надо внести и в void list_nodes_del(void* from, void* to).

И мелочь, конечно, но new я бы заменил, поскольку в крестах это ключевое слово.

(за смелость +1)

И еще, а почему, собственно

Each node of the list must contain: struct node_name *prev, *next; at the beginning.

IMHO Ваш код позволяет вставлять эти структуры связи в любое место структур, образующих список (и также, как и linux/list.h, иметь в структуре много разных связей, т.е. одна структура может входить в несколько разных списков).

5
  • нет, только в начало, потому что gist.github.com/maksspace/b074f0530ad37cc60860
    – maksspace
    2 фев 2016 в 22:59
  • указатель на структуру приводтися к указателю на struct { void *prev, *next; }
    – maksspace
    2 фев 2016 в 23:01
  • а разве это критично иметь способность размешаться в любом месте целевой структуры?
    – maksspace
    2 фев 2016 в 23:03
  • Если передавать адрес вашей node_link_t, расположенной в середине объемлющей структуры (а не ее адрес), то все будет работать, как и у Линуса (да вы linux/list.h повнимательней посмотрите)
    – avp
    2 фев 2016 в 23:09
  • @maksspace Критично или нет? Если стремиться к общности (т.е. одни и те же данные могут быть в разных списках), то критично.
    – avp
    2 фев 2016 в 23:10

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.