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(stacktyp e *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(stacktyp e *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(s tacktype *s);
|
| extern int push(stacktype *s, int value);
| extern int pop(stacktype *s, int *value);
| extern void popall(stacktyp e *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(stacktyp e *s) {
| s->count = 0;
| }
|
| void destroy_stack(s tacktype *s) {
| free(s);
| }
|
| stacktype *create_bounded _stack(unsigned stacksize) {
| stacktype *s;
| if (stacksize == 0) return 0;
| s = malloc(sizeof(s tacktype) + stacksize*sizeo f(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)(stackty pe *s, int value);
| int (*pop)(stacktyp e *s, int *value);
| void (*popall)(stack type *s);
| void (*destroy)(stac ktype *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(stacktyp e *s) {s->popall(s);}
| static inline void destroy_stack(s tacktype *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_stackty pe {
| stacktype interface;
| unsigned max_stack;
| unsigned count;
| int stack[];
| } bounded_stackty pe;
|
| static int bounded_push(st acktype *s, int value) {
| bounded_stackty pe *bs = (void *)s;
| if (bs->count >= bs->max_stack) return -1;
| bs->stack[bs->count++] = value;
| return 0;
| }
|
| static int bounded_pop(sta cktype *s, int *value) {
| bounded_stackty pe *bs = (void *)s;
| if (bs->count == 0) return -1;
| *value = bs->stack[--bs->count];
| return 0;
| }
|
| static void bounded_popall( stacktype *s) {
| bounded_stackty pe *bs = (void *)s;
| bs->count = 0;
| }
|
| static void destroy_bounded _stack(stacktyp e *s) {
| free(s);
| }
|
| static const stacktype bounded_stack_i nterface = {
| bounded_push,
| bounded_pop,
| bounded_popall,
| destroy_bounded _stack,
| };
|
| stacktype *create_bounded _stack(unsigned stacksize) {
| bounded_stackty pe *bs;
| if (stacksize == 0) return 0;
| bs = malloc(sizeof(b ounded_stacktyp e) + stacksize*sizeo f(int));
| if (bs == 0) return 0;
| bs->interface = bounded_stack_i nterface;
| bs->max_stack = stacksize;
| bs->count = 0;
| return &bs->interface;
| }
+---
| /* -- unbounded_stack .h -- */
| #include "stack.h"
| extern stacktype *create_unbound ed_stack(void);
+---
| /* -- unbounded_stack .c -- */
| #include <stdlib.h>
| #include "unbounded_stac k.h"
| #include "bounded_stack. h"
|
| #define UB_STACK_DEFAUL T 100
| static unsigned UB_STACK_SIZE = UB_STACK_DEFAUL T;
|
| typedef struct unbounded_subst acktype {
| struct unbounded_subst acktype *link;
| stacktype *substack;
| } unbounded_subst acktype;
|
| static unbounded_subst acktype *create_unbound ed_substack(voi d) {
| unbounded_subst acktype *s;
| s = malloc(sizeof(u nbounded_substa cktype));
| 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_unbound ed_substack(unb ounded_substack type *s) {
| destroy_stack(s->substack);
| free(s);
| }
|
| typedef struct unbounded_stack type {
| stacktype interface;
| unbounded_subst acktype *current_stack;
| unbounded_subst acktype *free_stack;
| } unbounded_stack type;
|
| static int unbounded_push( stacktype *s, int value) {
| unbounded_stack type *us = (void *)s;
| unbounded_subst acktype *cs = us->current_stac k;
| unbounded_subst acktype *fs;
| if (cs == 0 || push(cs->substack, value) == -1) {
| fs = us->free_stack;
| if (fs == 0) {
| if ((fs = create_unbounde d_substack()) == 0) return -1;
| } else us->free_stack = 0;
| fs->link = cs;
| cs = us->current_stac k = fs;
| return push(cs->substack, value);
| }
| return 0;
| }
|
| static int unbounded_pop(s tacktype *s, int *value) {
| unbounded_stack type *us = (void *)s;
| unbounded_subst acktype *cs = us->current_stac k;
| unbounded_subst acktype *fs;
| if (cs == 0) return -1;
| if (pop(cs->substack, value) == -1) {
| fs = cs;
| cs = us->current_stac k = cs->link;
| if (us->free_stack == 0) us->free_stack = fs;
| else destroy_unbound ed_substack(fs) ;
| return pop(cs->substack, value);
| }
| return 0;
| }
|
| static void unbounded_popal l(stacktype *s) {
| unbounded_stack type *us = (void *)s;
| unbounded_subst acktype *cs = us->current_stac k;
| unbounded_subst acktype *fs = us->free_stack;
| if (cs == 0) return;
| if (fs == 0) {
| fs = us->free_stack = cs;
| cs = us->current_stac k = cs->link;
| fs->link = 0;
| popall(fs->substack);
| }
| while (cs != 0) {
| cs = cs->link;
| destroy_unbound ed_substack(us->current_stack) ;
| us->current_stac k = cs;
| }
| }
|
| static void destroy_unbound ed_stack(stackt ype *s) {
| unbounded_stack type *us = (void *)s;
| unbounded_popal l(s);
| if (us->free_stack) destroy_unbound ed_substack(us->free_stack);
| free(s);
| }
|
| static const stacktype unbounded_stack _interface = {
| unbounded_push,
| unbounded_pop,
| unbounded_popal l,
| destroy_unbound ed_stack,
| };
|
| stacktype *create_unbound ed_stack(void) {
| unbounded_stack type *us;
| us = malloc(sizeof(u nbounded_stackt ype));
| if (us == 0) return 0;
| us->interface = unbounded_stack _interface;
| us->current_stac k = 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
