[OCLUG-devel] Single Element Structures

[Dan Stromberg]

You've hit on one of my favorite topics.  Apologies if this is too
long-winded.  :)


The purpose of a struct that people usually discuss is simply grouping
heterogeneous types into a single collection, which may then be referred
to collectively.


Another, and at least as important, function of a struct, which isn't
usually discussed in the context of procedural languages like C or
Pascal, but is a central topic in Object Based languages like Ada, or
Object Oriented languages like C++ or Smalltalk or Python, is to create
abstract data types (ADT's).  C can do ADT's pretty well really, except
for the information hiding part (which it has in common with Python, in
a sense), and also C doesn't do inheritance well (C++, Smalltalk and
Python do - this being the primary distinction between a mere "Object
Based" language like Ada, and these "Object Oriented" languages).

The point of an ADT is to, for example, have a single API for a kind of
data and the operations performed on that data, but implementing the
data representation and operations in different ways, but with different
tradeoffs - hence insulating the dependent code from being heavily
impacted when the data representation needs to change.

One of the classic examples of why you might want an ADT, is
implementing a stack.  A stack is where you put items in at one end of a
"list" (in the generic sense, not the Computer Science sense), and pull
items back out from the same end, just like with a pile of plates at
Soup Plantation.  :)

Two common data representations that might be used internally by a stack
ADT (abstract data type) would be an array, or a linked list.

The array implementation of a stack is nice because it's fast, and
because it has low memory requirements when the stack is full, but it'll
tend to lead to messiness if the array fills up (which C can get around
with realloc, but a language like Pascal (the Niklaus Wirth definition -
Borland likely extended for this) doesn't have much in the way of an
equivalent).

The linked list implementation of a stack is nice because it has no
fixed limit on how large the stack can grow (other than available
memory, at least on non-segmented architectures), but it'll tend to be a
little bit slower, and it'll use more memory than an array
implementation when the two stack implementations hold a number of
elements near the capacity of the array implementation.

If you implement both of these with identical API's, then you can very
quickly and easily change your programs from using the plusses and
minuses of one implementation (array) to the other (linked list - or
vice versa).

As a further example of an abstract type, say you have a program that
uses a singly-linked list (linked only forward, but not back again), and
suddenly you find that the changing needs of the program require you to
be able to quickly start at the end of the list, and work backward.  You
could easily approach this with a recursive algorithm (if you aren't
worried about the CPU and memory requirements), but often a slight
change in data representation is better.

In such a case, you have pretty much three choices:

1) If you were using a library of C functions that implements both
singly-linked lists, as well as doubly-linked lists (forward and back),
and the doubly-linked list API is already a superset of the
singly-linked list API, then you can just switch to the doubly-linked
list implementation, and all of your existing code that required only a
singly-linked list should continue functioning just fine (so long as
they do not violate the ADT definition by reaching inside the struct's
inappropriately), so you can dive right into adding the new
functionality, rather rearranging the old singly-linked code first.

2) If you are implementing your own linked list functions (seldom a good
idea anymore, but a lot of CS students are required to do it, since it's
a good example of ADT's/Objects), and you've carefully abstracted your
singly-linked list implementation, then you can just add another ADT
(possibly via inheritance in a fully object oriented language like C++
or Smalltalk or Python, but not C or Ada) that does doubly linked lists,
and other than the (perhaps partially) new ADT and the new code for
doubly-linked lists, your existing code doesn't need to be modified
much, if at all.

3) If you weren't abstracting your code well, then you could easily end
up doing a near-complete rewrite due to what may actually be a
relatively small change in the program's requirements.

So by having this typedef/struct with a single element, if there is a
well defined set of functions that can look inside the typedef/struct
(and only they are allowed to do it - IE the inspection/changing of the
struct isn't scattered throughout your program) that opens the door to
easy changes - like switching to a doubly-linked list, or adding a field
that keeps a count of the members in the list, or even switching to an
entirely different kind of data structure behind the scenes, while the
rest of your code happily takes an afternoon nap.  :)

Put another way, if you have poorly abstracted code, when you need to
change a data representation, you can easily get a sort of "ripple
effect", where changes in the code start in one small place, and kind of
"ripple outward" into ever further parts of the code.  But if things are
well abstracted, than most of the time (some would argue all of the
time), the "ripples of change" stop at the ADT boundaries, which can be
quite a time-saver.


There's another reason I would sometimes use a struct with a single
element, which is far less significant than what's described above, and
some would argue it's a Very Bad Thing, so please take it with a grain
of salt.  That is, sometimes when I am working in C code that requires
callbacks, and there are parameters passed to the callback functions
that must accept a "void *", in order to be able to pass a variety of
types (a union just wouldn't be flexible enough sometimes), I'll
sometimes avoid the poor type checking attendant with casting a variable
to void * and back, by just using globals to keep decent type checking
(or similarly for static variables in a global context, IE variables
that are global only to a particular .c file).  But globals are evil,
right?!  I try to alleviate the evils of using global variables,
believing they're sometimes better than screwing around with the type
system, by using a struct that contains all the global variables, and
hopefully there's a small number of items in that struct - in fact,
hopefully only one.  That way, any time I want to use a global variable
named "foo", I instead refer to "global.foo", making it a hair less
confusing when another programmer works on my code, or I revisit my own
code years later.  :)


HTH!

On Mon, 2005-08-29 at 14:17 -0400, Doug Jolley wrote:
> Hi --
> 
> I am a real newbie to C and in way over my head on a project that I'd
> really like to get to work.  I'm thinking that the thing to do may be
> to try to get some help at the next OCLUG meeting; but, in the
> meantime I'm going to try to muddle along as best I can.
> 
> To continue my muddling, I have encountered the following type
> definition:
> 
> typedef struct {
>     node* head;
> } llist;
> 
> My question is:  Why would anyone go to the trouble of defining a
> structure with only one element in it?  I thought the essence of
> structures was that they contained a collection of dissimilar data
> elements.  I'm sure the guy that did this had a very good reason and I
> realize that I'm asking a question without giving a lot of context;
> so, from what I've given there may be no answer.  Anyway, if an answer
> may be deduced from what I've given, I'd love to hear it.  Thanks for
> any input.
> 
>       ... doug
> _______________________________________________
> OCLUG-devel mailing list -- OCLUG-devel at oclug.org
> http://mailman.oclug.org/mailman/listinfo/oclug-devel