Guter Bibliotheksentwurf für "überlappende" Funktionalität

Question

Ich versuche, eine Bibliothek zu erstellen, die eine einfache Verkettungslistenimplementierung und auch einige Verallgemeinerungen dieser verketteten Liste, wie Stapel und Warteschlangen, alle basierend auf der verknüpften Basisliste bereitstellt.

Die Sache ist, ich möchte unterschiedliche Typen mit ihren eigenen "privaten" Funktionen haben, so dass Sie nicht "stack_pull (my_queue)" verwenden würden; oder "queue_pull (my_stack)", was zu einem falschen Verhalten für diesen speziellen Listentyp führen würde. Der einzige Weg, kann ich mir vorstellen, wie das jetzt funktionieren würde, ist durch die Grund verknüpften Liste Struktur in anderen Strukturen für ihre eigenen Arten wickeln, wie dieser im Grunde

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 *)); 

Auf diese Weise werde ich die speziellen Funktionen schreiben müssen, um Nutzung der Basisfunktionen und konstant machen auspackt um die tatsächlichen Daten zu erhalten, zum Beispiel

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); 
} 

ist das ein Overhead, mit dem ich leben würde, wenn ich von einer Grundliste spezialisieren will, oder ist es ein schöne und sauberer Weg?

Answer 1

die Liste Struktur in eine andere Struktur Wrapping ist ein guter Weg, um geh damit um. Es sollte keinen zusätzlichen Laufzeitaufwand oder Speicherverbrauch geben, da die Anforderungen für Ausrichtung und Auffüllung für innere und äußere Strukturen genau gleich sein sollten (da die Ausrichtung und Auffüllung der äußeren Strukturen nur von der inneren Struktur stammen).

Soweit die Funktionen/Methoden, die auf ihnen arbeiten, können Sie inline verwenden, um alle Overhead, die für Fälle, in denen eine Stapel - oder Warteschlangenfunktion ist nur eine einfache Umbenennung (oder ein spezieller Aufruf) oder a Listenfunktion.

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

Dies wird sicherstellen, dass Sie die gleiche Art der Typprüfung erhalten, aber ohne Laufzeit über Kopf oder zusätzlichen Code. Sie sollten nicht auf Probleme stoßen, es sei denn, Sie verwenden Zeiger zu diesen Funktionen, und wenn Sie dann sind, können Sie auch eine reguläre Implementierung für sie einschließen.

Sie sollten feststellen, dass das Einfügen eines Knotenzeigers in die Listenstruktur als das einzige Element bereits eine Anwendung war, die dasselbe zum Umhüllen einer Liste in einer Stapel- oder Warteschlangenstruktur verwendet.

Answer 2

Wenn Sie mit weniger Typprüfung durch den Compiler in Ordnung sind, können Sie typedef s statt Wrapping-Strukturen, z.,
typedef struct queue list
#define queue_create list_create
oder
inline queue *queue_create() {return (queue *) list_create
letztere Option -Das ist erforderlich C99 oder Erweiterungen C89.

Wenn Sie das inline Schlüsselwort haben, können Sie auch den Betrieb in einem Makro wickeln:

#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); 

(. Oder verwenden C++)

Answer 3

Dieser Ansatz ist in Ordnung, außer dass die Struktur linked_list nicht benötigt wird - es ist eine unnötige Ebene der Indirektion.Eine Liste wird vollständig durch den Kopf Zeiger beschrieben, so müssen Sie nur die Kopfzeiger in Ihrem Stapel und Warteschlange enthalten:

typedef struct queue 
{ 
    list_node *queue_head; 
} queue; 

typedef struct stack 
{ 
    list_node *stack_head; 
} stack; 

Seperate structs ist durchaus angebracht - beispielsweise ein Stapel benötigt nur einen Kopfzeiger, aber Eine Warteschlange ist effizienter, wenn sie sowohl einen Kopf- als auch einen Endzeiger auf die Liste hat.