Code reuse

[MartinBroadhurst]

Now that Jon is safely tucked up, I'd like to ask a C question.

Suppose I have a linked list package, and I want to make a stack out
of it.
I don't want to do this:

typedef linkedlist stack;

#define stack_create linkedlist_create
#define stack_delete linkedlist_delete
#define stack_push linkedlist_add_head
#define stack_pop linkedlist_remove_head

Because that doesn't prevent someone from doing this:

stack *s = stack_create();
/* Some time later */
linkedlist_add_tail(s, "FISH");

So I need to make stack a new type, but I still want to reuse the
linked list.
As far as I can see, there are two ways of doing this.

Firstly, I could declare a stack as an indentical structure to the
linked list...

typedef struct {
/* Exactly the same as linkedlist */
} stack;

....and then implement the functions by calling the corresponding
linkedlist ones with a cast:

stack *stack_create(void)
{
return (stack*)linkedlist_create();
}

void stack_delete(stack *s)
{
linkedlist_delete((linkedlist*)s);
}

void stack_push(stack *s, void *data)
{
linkedlist_add_head((linkedlist*)s, data);
}

void *stack_pop(stack *s)
{
return linkedlist_remove_head((linkedlist*)s);
}

Second, I could put a pointer to a linkedlist inside the stack...

typedef struct {
linkedlist *list;
} stack;

....and then implement the functions by forwarding to the contained
list:

stack *stack_create(void)
{
stack *s = malloc(sizeof(stack));
if (s) {
s->list = linkedlist_create();
}
return s;
}

void stack_delete(stack *s)
{
if (s) {
linkedlist_delete(s->list);
free(s);
}
}

void stack_push(stack *s, void *data)
{
linkedlist_add_head(s->list, data);
}

void *stack_pop(stack *s)
{
return linkedlist_remove_head(s->list);
}

Are both of these methods valid, and if so, is there a reason to
prefer one over the other?
Is there another way?

Martin

 

[MartinBroadhurst]

If you're using pointers, you can use incomplete types.

typedef struct stack stack;

stack *stack_create(void);
void stack_delete(stack*);
stack *stack_push(stack*,void*);
void *stack_pop(stack*);
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
struct stack {linkedlist s;}

stack *stack_create(void) {return (stack*)(linkedlist_create());}
void stack_delete(stack *S) {linkedlist_delete(&(S->s));}
stack *stack_push(stack *S,void *X) {
    return (stack*)(linkedlist_add_head(&(S->s),X));}

void *stack_pop(stack *S) {return linkedlist_remove_head(&(S->s));}

I like this solution. It obviates the need to allocate the stack
separately.

I suppose if someone is truly determined to violate the interface they
can do this:

typedef struct {
linkedlist s;
} imposter;

linkedlist_add_tail(&((imposter*)s)->s, "FISH");

Martin

 

[Chad]

I like this solution. It obviates the need to allocate the stack
separately.

I suppose if someone is truly determined to violate the interface they
can do this:

typedef struct {
    linkedlist s;

} imposter;

linkedlist_add_tail(&((imposter*)s)->s, "FISH");

Isn't code reuse just a fancy name for plagarism?

Chad

 

[Keith Thompson]

Isn't code reuse just a fancy name for plagarism?

No.

 

[jacob navia]

Le 01/11/10 14:39, MartinBroadhurst a écrit :

Are both of these methods valid, and if so, is there a reason to
prefer one over the other?
Is there another way?

Martin

Both methods are valid, but I would prefer a third one

(1)
stack.h:

struct stack;

// Returns NULL on failure, the pushed element if OK
void *Push(struct stack *Stack,void *element);
// Returns NULL if stack empty.
void *Pop(struct stack *Stack);
// Returns NULL on failure
struct stack *Create(void);

(2)
The implementation would be in some OTHER file called
"Stack.c", that would not be accessible...

Within it, you do not really need all the linked list functionality
since you will never do anything else than push and pop.

You could reuse linkedlist however but the users have no way of knowing
it unless you give them stack.c

In my implementation of the container library stacks are derived objects
that can be implemented either with linked lists or with
flexible arrays.

Stacks, Queues, Deques, and other data structures are examples of
derived containers, i.e. containers that use other containers as
implementation.

 

[MartinBroadhurst]

Isn't code reuse just a fancy name for plagarism?

I'm not sure what you mean.
Code reuse is layering new functionality on top of existing
functionality, while plagiarism is passing another's work off as one's
own.
Copy-and-paste is the hallmark of plagiarism, while in code reuse the
intention is to *avoid* copy-and-paste, because copy and paste makes
the code base and executables larger needlessly, causes redundancy, is
difficult to maintain, and can duplicate bugs which then need to be
fixed more than once.
Code reuse can happen at the binary level; one doesn't need the source
code of a component if one is just using its capabilities, rather than
changing it.
The example I gave was of implementing a stack on top of my own linked
list, so if reuse is plagiarism then I would have been plagiarising
myself.

Martin

 

[MartinBroadhurst]

You could reuse linkedlist however but the users have no way of knowing
it unless you give them stack.c

That's a good point. Pushing the type into the .c file allows the
implementation to be switched without affecting clients.

In my implementation of the container library stacks are derived objects
that can be implemented either with linked lists or with
flexible arrays.

I would have 3 layers; the abstract interface, the raw data
structures, and in between them the implementations of the interface
in terms of the raw data structures, and possibly a "stack factory"
that can construct an implementation wrapped in the interface. That
way:

1) The abstract interface doesn't know about the specific
implementations.
2) The implementations don't know about the interface.
3) A client can use a raw implemention directly for efficiency if
necessary.

Martin

 

[Eric Sosman]

Isn't code reuse just a fancy name for plagarism?

No, Chiad, it's not.

 

[Jon]

Suppose I have a linked list package, and I want to make a stack out
of it.

Trust me, you don't want to. It is "wrong" to do that. You may have to
reinvent your containers a few times before you realize it though.

Is there another way?

Yes, of course.

 

[Jon]

Code reuse is layering new functionality on top of existing
functionality,

Well that is one form of it anyway. Is code reuse good if it makes
maintenance harder and software less-reliable? Code reuse for code
reuse's sake is the wrong way of thinking. IOW, code reuse is *not*
inherently a good thing that is to be done "whenever possible no matter
how much it hurts to get it".