CODEWITHSUNDEEP
c
chmod222
chmod222

Reputation: 5722

Good library design for "overlapping" functionality

I'm trying to create a library that provides a simple linked list implementation and also a few generalizations of that linked list, like stacks and queues, all based on the basic linked list.

The thing is, I want to have distinct types with their own "private" functions so you wouldn't use "stack_pull(my_queue);" or "queue_pull(my_stack)" which would result in wrong behaviour for that particular type of list. The only way I can imagine how that would work right now is by wrapping the basic linked list structure in other structures for their own types, like this basically

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

That way I'll have to write the specialized functions to make use of the base functions and constant unwrapping to get to the actual data, for example

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

Is this an overhead I would have to live with if I want to specialize from a basic list, or is there a nice and clean way?

Upvotes: 0

Views: 305

Answers (3)

caf
caf

Reputation: 239181

This approach is fine, except that there is no need for the linked_list structure - it is an unnecessary level of indirection. A list is entirely described by its head pointer, so you only need to include the head pointers in your stack and queue:

typedef struct queue
{
    list_node *queue_head;
} queue;

typedef struct stack
{
    list_node *stack_head;
} stack;

Seperate structs are quite appropriate - for example, a stack only needs a head pointer, but a queue is more efficient if it has both a head and tail pointer to the list.

Upvotes: 1

nategoose
nategoose

Reputation: 12392

Wrapping the list struct in another struct is a good way to handle this. There should not be any extra runtime overhead or memory usage because the alignment and padding requirements should be exactly the same for the inner and outer structs (since the outer structs' alignment and padding come only from the inner struct).

As far as the functions/methods that work on them you can use inline to do away with any overhead that would be incurred for cases where a stack or queue function is just a simple renaming (or a special calling) or a list function.

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

This will make sure that you get the same level of type checking, but without runtime over head or extra code. You shouldn't run into problems unless you are using pointers to these functions, and if you are then you can include a regular implementation for them as well.

You should notice that putting a node pointer in the list struct as the sole member was already an application of the same thing as wrapping a list up in a stack or queue structure.

Upvotes: 1

J. C. Salomon
J. C. Salomon

Reputation: 4313

If you’re OK with less type-checking by the compiler, you could use typedefs rather than wrapping structures, e.g.,
typedef struct queue list
#define queue_create list_create
or
inline queue *queue_create() {return (queue *) list_create
—this latter option is requires C99 or extensions to C89.

If you have the inline keyword, you can also wrap the operation in a macro:

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

(Or use C++.)

Upvotes: 0

Related Questions