Хороший дизайн библиотеки для «перекрывающихся» функций

Question

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

Дело в том, что я хочу иметь разные типы с их собственными "частными" функциями, чтобы вы не использовали "stack_pull (my_queue);" или «queue_pull (my_stack)», что может привести к неправильному поведению для этого конкретного типа списка. Единственный способ представить, как это будет работать сейчас, - это обернуть базовую структуру связанного списка в другие структуры для их собственных типов, как это в основном

typedef struct node
{
    void *data;
    list_node *next;
} list_node

typedef struct list
{
    list_node *root;
} linked_list;

typedef struct queue
{
    linked_list *base;
} queue;

typedef struct stack
{
    linked_list *base;
} stack;

linked_list *list_create();
void list_dispose(linked_list **, void (*free_content)(void *));

queue *queue_create();
void queue_dispose(queue **, void (*free_content)(void *));

stack *stack_create()
void stack_dispose(stack **, void (*free_content)(void *));

Таким образом, мне придется написать специализированные функции, чтобы использовать базовые функции и постоянное развертывание, чтобы добраться до фактических данных, например,

queue *queue_create()
{
    [...] /* Allocate a new queue struct */
    tmp_queue->base = list_create();
    [...]
    return tmp_queue
}

void *stack_pull(stack *s)
{
    [...] /* Error checking */
    return list_pop_last(s->base);
}

void *queue_pull(queue *q)
{
    [...] /* Error checking */
    return list_pop_first(s->base);
}

Это накладные расходы, с которыми мне придется смириться, если я хочу специализироваться из базового списка, или есть хороший и чистый способ?

Answer 1

Обертывание структуры списка в другую структуру - хороший способ справиться с этим.Не должно быть никаких дополнительных накладных расходов во время выполнения или использования памяти, поскольку требования к выравниванию и заполнению должны быть одинаковыми для внутренних и внешних структур (поскольку выравнивание и заполнение внешних структур происходят только из внутренней структуры).

Что касается функций / методов, которые работают с ними, вы можете использовать inline, чтобы покончить с любыми накладными расходами, которые могут возникнуть в случаях, когда функция стека или очереди представляет собой простое переименование (или специальный вызов) или списокfunction.

inline void queue_dispose(queue **Q, void (*free_content)(void *)) {
      list_dispose(&&(*Q->base), free_content);
}

Это гарантирует, что вы получите тот же уровень проверки типов, но без затрат времени выполнения или дополнительного кода.Вы не должны сталкиваться с проблемами, если вы не используете указатели на эти функции, и если вы это сделаете, то можете также включить в них обычную реализацию.

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

Answer 2

Этот подход хорош, за исключением того, что нет необходимости в структуре linked_list - это ненужный уровень косвенности. Список полностью описывается указателем заголовка, поэтому вам нужно только включить указатели заголовка в ваш стек и очередь:

typedef struct queue
{
    list_node *queue_head;
} queue;

typedef struct stack
{
    list_node *stack_head;
} stack;

Отдельные структуры вполне уместны - например, стеку нужен только указатель заголовка, но очередь более эффективна, если в нем есть как заголовок, так и хвостовой указатель на список.

Answer 3

Если вы согласны с меньшим количеством проверок типов компилятором, вы можете использовать typedef s вместо структур-оболочек, например ,
typedef struct queue list
#define queue_create list_create
или
inline queue *queue_create() {return (queue *) list_create
- для последнего варианта требуется C99 или расширения для C89.

Если у вас есть ключевое слово inline, вы также можете заключить операцию в макрос:

#define WRAP_LIST(wrapper)                                  \
    struct wrapper {linked_list *root;};                    \
    inline struct wrapper *wrapper ##_create {              \
        …                                                   \
        tmp_queue->base = list_create();                    \
        …                                                   \
    }                                                       \
    …                                                       \
    typedef struct wrapper wrapper
// note lack of ‘;’ at end of last line

WRAP_LIST(queue);
WRAP_LIST(stack);

(или используйте C ++.)