On 2003-10-12, Fronsac <fr*************@hotmail.com> wrote:
I've been asked in a job interview how to make C code look like C++
code, and honestly I didn't know what to answer because I have never
really done a lot of C. Now, I've been searching around the web about
web sites that talk about this subject, but I've had no luck. Can
anyone point me to some web site about this subject? Thanks a lot!
Let's consider a simple example: providing an integer stack.
Here's a typical way of doing it:
+---
| /* -- stack.h -- */
| extern int push(int value);
| extern int pop(int *value);
| extern void popall(void);
+---
| /* -- stack.c -- */
| #include "stack.h"
|
| #define MAX_STACK 100
| static int stack[MAX_STACK];
| static unsigned count;
|
| int push(int value) {
| if (count >= MAX_STACK) return -1;
| stack[count++] = value;
| return 0;
| }
|
| int pop(int *value) {
| if (count == 0) return -1;
| *value = stack[--count];
| return 0;
| }
|
| void popall(void) {
| count = 0;
| }
+---
There may be other deficiencies with this implementation, but at least
one of them is that any application that uses this implementation is
limited to only one stack. There are various ways of addressing this
issue, but one of the most short sighted ways is to simply copy off
stack.c to another file stack2.c and rename the functions push2 and
pop2 to create a second stack.
Better is to encapsulate the stack in a structure so that an
application can create as many stacks as it needs without having to
apply cut and paste coding.
+---
| /* -- stack.h -- */
| #define MAX_STACK 100
| typedef struct stacktype {
| int stack[MAX_STACK];
| unsigned count;
| } stacktype;
|
| extern int push(stacktype *s, int value);
| extern int pop(stacktype *s, int *value);
| extern void popall(stacktype *s);
+---
| /* -- stack.c -- */
| #include "stack.h"
|
| int push(stacktype *s, int value) {
| if (s->count >= MAX_STACK) return -1;
| s->stack[s->count++] = value;
| return 0;
| }
|
| int pop(stacktype *s, int *value) {
| if (s->count == 0) return -1;
| *value = s->stack[--s->count];
| return 0;
| }
|
| void popall(stacktype *s) {
| s->count = 0;
| }
+---
This implementation is sufficient for most applications needing an
integer stack. However, another minor drawback is that all stacks
are always of the same size. In order to avoid the cut and paste
solution to allow different sized stacks, this property should also be
encapsulated within the stack data structure. However, now the stack
implementation is exposed to the extent that users of the interface must
muck around inside the encapsulation to use the interface. In order to
decouple the interface from the implementaiton, we make the stacktype
opaque. The result provides a limited form of polymorphism, since
the stack interface client need not be aware of how the stack was
created to use the stack.
+---
| /* -- stack.h -- */
| typedef struct stacktype stacktype;
|
| extern stacktype *create_bounded_stack(unsigned stacksize);
| extern void destroy_stack(stacktype *s);
|
| extern int push(stacktype *s, int value);
| extern int pop(stacktype *s, int *value);
| extern void popall(stacktype *s);
+---
| /* -- stack.c -- */
| #include <stdlib.h>
| #include "stack.h"
|
| struct stacktype {
| unsigned max_stack;
| unsigned count;
| int stack[];
| };
|
| int push(stacktype *s, int value) {
| if (s->count >= s->max_stack) return -1;
| s->stack[s->count++] = value;
| return 0;
| }
|
| int pop(stacktype *s, int *value) {
| if (s->count == 0) return -1;
| *value = s->stack[--s->count];
| return 0;
| }
|
| void popall(stacktype *s) {
| s->count = 0;
| }
|
| void destroy_stack(stacktype *s) {
| free(s);
| }
|
| stacktype *create_bounded_stack(unsigned stacksize) {
| stacktype *s;
| if (stacksize == 0) return 0;
| s = malloc(sizeof(stacktype) + stacksize*sizeof(int));
| if (s != 0) {
| s->max_stack = stacksize;
| s->count = 0;
| }
| return s;
| }
+---
The final point we will address is that the interface only provides
a bounded stack implementation. Suppose an application is utilizing
the stack in multiple modules. In some modules, the bounded stack
is required, because it is used to throttle the work load. In other
modules, it has been determined that a bounded stack is unacceptable,
since pre-allocating the maximum required memory is too wasteful, and
and the most common cases only require a small amount of memory.
Again, one could perform cut and paste, rename the stack interfaces
for an unbounded implementation, and alter the modules that need the
unbounded implementation to use the new interface. However, to avoid
the pitfalls of cut and paste programming, an alternative solution
is to make the interface inheritable and extensible. Then, applying
reuse on the interface, implement the unbounded stack.
+---
| /* -- stack.h -- */
| typedef struct stacktype stacktype;
| struct stacktype {
| int (*push)(stacktype *s, int value);
| int (*pop)(stacktype *s, int *value);
| void (*popall)(stacktype *s);
| void (*destroy)(stacktype *s);
| };
|
| static inline int push(stacktype *s, int value) {return s->push(s, value);}
| static inline int pop(stacktype *s, int *value) {return s->pop(s, value);}
| static inline void popall(stacktype *s) {s->popall(s);}
| static inline void destroy_stack(stacktype *s) {s->destroy(s);}
+---
| /* -- bounded_stack.h -- */
| #include "stack.h"
| extern stacktype *create_bounded_stack(unsigned stacksize);
+---
| /* -- bounded_stack.c -- */
| #include <stdlib.h>
| #include "bounded_stack.h"
|
| typedef struct bounded_stacktype {
| stacktype interface;
| unsigned max_stack;
| unsigned count;
| int stack[];
| } bounded_stacktype;
|
| static int bounded_push(stacktype *s, int value) {
| bounded_stacktype *bs = (void *)s;
| if (bs->count >= bs->max_stack) return -1;
| bs->stack[bs->count++] = value;
| return 0;
| }
|
| static int bounded_pop(stacktype *s, int *value) {
| bounded_stacktype *bs = (void *)s;
| if (bs->count == 0) return -1;
| *value = bs->stack[--bs->count];
| return 0;
| }
|
| static void bounded_popall(stacktype *s) {
| bounded_stacktype *bs = (void *)s;
| bs->count = 0;
| }
|
| static void destroy_bounded_stack(stacktype *s) {
| free(s);
| }
|
| static const stacktype bounded_stack_interface = {
| bounded_push,
| bounded_pop,
| bounded_popall,
| destroy_bounded_stack,
| };
|
| stacktype *create_bounded_stack(unsigned stacksize) {
| bounded_stacktype *bs;
| if (stacksize == 0) return 0;
| bs = malloc(sizeof(bounded_stacktype) + stacksize*sizeof(int));
| if (bs == 0) return 0;
| bs->interface = bounded_stack_interface;
| bs->max_stack = stacksize;
| bs->count = 0;
| return &bs->interface;
| }
+---
| /* -- unbounded_stack.h -- */
| #include "stack.h"
| extern stacktype *create_unbounded_stack(void);
+---
| /* -- unbounded_stack.c -- */
| #include <stdlib.h>
| #include "unbounded_stack.h"
| #include "bounded_stack.h"
|
| #define UB_STACK_DEFAULT 100
| static unsigned UB_STACK_SIZE = UB_STACK_DEFAULT;
|
| typedef struct unbounded_substacktype {
| struct unbounded_substacktype *link;
| stacktype *substack;
| } unbounded_substacktype;
|
| static unbounded_substacktype *create_unbounded_substack(void) {
| unbounded_substacktype *s;
| s = malloc(sizeof(unbounded_substacktype));
| if (s == 0) return 0;
| s->substack = create_bounded_stack(UB_STACK_SIZE);
| if (s->substack == 0) {
| free(s);
| return 0;
| }
| s->link = 0;
| return s;
| }
|
| static void destroy_unbounded_substack(unbounded_substacktype *s) {
| destroy_stack(s->substack);
| free(s);
| }
|
| typedef struct unbounded_stacktype {
| stacktype interface;
| unbounded_substacktype *current_stack;
| unbounded_substacktype *free_stack;
| } unbounded_stacktype;
|
| static int unbounded_push(stacktype *s, int value) {
| unbounded_stacktype *us = (void *)s;
| unbounded_substacktype *cs = us->current_stack;
| unbounded_substacktype *fs;
| if (cs == 0 || push(cs->substack, value) == -1) {
| fs = us->free_stack;
| if (fs == 0) {
| if ((fs = create_unbounded_substack()) == 0) return -1;
| } else us->free_stack = 0;
| fs->link = cs;
| cs = us->current_stack = fs;
| return push(cs->substack, value);
| }
| return 0;
| }
|
| static int unbounded_pop(stacktype *s, int *value) {
| unbounded_stacktype *us = (void *)s;
| unbounded_substacktype *cs = us->current_stack;
| unbounded_substacktype *fs;
| if (cs == 0) return -1;
| if (pop(cs->substack, value) == -1) {
| fs = cs;
| cs = us->current_stack = cs->link;
| if (us->free_stack == 0) us->free_stack = fs;
| else destroy_unbounded_substack(fs);
| return pop(cs->substack, value);
| }
| return 0;
| }
|
| static void unbounded_popall(stacktype *s) {
| unbounded_stacktype *us = (void *)s;
| unbounded_substacktype *cs = us->current_stack;
| unbounded_substacktype *fs = us->free_stack;
| if (cs == 0) return;
| if (fs == 0) {
| fs = us->free_stack = cs;
| cs = us->current_stack = cs->link;
| fs->link = 0;
| popall(fs->substack);
| }
| while (cs != 0) {
| cs = cs->link;
| destroy_unbounded_substack(us->current_stack);
| us->current_stack = cs;
| }
| }
|
| static void destroy_unbounded_stack(stacktype *s) {
| unbounded_stacktype *us = (void *)s;
| unbounded_popall(s);
| if (us->free_stack) destroy_unbounded_substack(us->free_stack);
| free(s);
| }
|
| static const stacktype unbounded_stack_interface = {
| unbounded_push,
| unbounded_pop,
| unbounded_popall,
| destroy_unbounded_stack,
| };
|
| stacktype *create_unbounded_stack(void) {
| unbounded_stacktype *us;
| us = malloc(sizeof(unbounded_stacktype));
| if (us == 0) return 0;
| us->interface = unbounded_stack_interface;
| us->current_stack = 0;
| us->free_stack = 0;
| return &us->interface;
| }
+---
The final example shows an extensible polymorphic interface in C. The
interface is exposed in an object that can be inherited. The example
leverages the inheritance to provide multiple implementations of the
interface. Code utilizing the interface can be simultaneously reused to
manipulate either a bounded or unbounded stack. Code can furthermore
inherit the interface and provide their own implementations.
This is of course only an example, and the techniques applied here is
arguably overkill for such a simple data structure. The simplicity,
however, allows the techniques to be illustrated in a relatively
straight forward and compact manner. These techniques here are nothing
new to the experienced software professional. They will be found in OS
kernel code, I/O interface APIs, protocol stacks, GUI APIs, and many
other places.
-- James
