Abstract Data Types in C

[Eric S. Raymond]

In article <116 at capshaw.UUCP> sdc at capshaw.UUCP (Dan Capshaw) writes:
>Is anyone out there using ADTs in C?  If so, am I missing something here? 

ADT programming is more a style of problem decomposition than a language-
dependent bag of tricks. If you *think* in ADT terms, you can write ADT
programs in assembler! -- which is not to deny that good facilities like C++'s
make it a lot easier.

C wasn't built for ADT programming, but can support it quite nicely. The basic
method is to implement each ADT as a separate C module (or, in some cases, a
module library) with an associated header file that completely defines the ADT
interface.

My netnews rewrite is explicitly ADT-structured, all 156,638 code lines of it.
I think this qualifies as a real-world project of significant size. Here are
some ADT principles I've applied.

Minimizing shared global information is important. You need to get into the
habit of declaring everything static that doesn't absolutely *need* to be
externally visible. And globals that 'float', i.e. are not owned and used for
interface presentation by some ADT, are a big no-no. I only have one such in
my entire suite, and that's a 1K scratch buffer that I never assume stays
un-munged across function-calls.

I like to write things so that the information in the ADT interface is packaged
in a single visible struct, named the same as the file where that's reasonable;
that way every reference to the interface points back at the ADT.

Function pointers are important. They give you a way for ADTs to pass around
and use each others' capabilities without exposing their internals and without
tying the capabilities to fixed names that the linker has to know about. For
example, I use a macroexpansion function that takes three arguments; a
get-character function, an unget-character function and a result buffer. This
way, by having different ADTs pass it different arguments, it can handle
macroexpansion of (a) file contents, (b) a tty input stream, or (c) an in-
memory buffer.

Method tables -- name-indexed arrays of function pointers -- are another useful
trick to keep in mind, especially if you're writing anything that looks like
a command interpreter (and I claim that almost *any* interactive program can
gain from being considered as a special-purpose language interpreter, but
that's another soapbox).

In NNTP, for example, each NNTP command keyword is dispatched through a method
table to a separate ADT-like handler module, almost like an object invocation
in Smalltalk. I do similar things to dispatch netnews control messages.

But I repeat; ADTness, like "structured programming" is a design attitude, not
a collection of rules or coding tricks. If you grok the ADT philosophy in
fullness, you can apply it even in very impoverished laanguages. If you don't,
even the most zealous application of the above guidelines isn't likely to get
you the kind of code coherence and cleanness you want.
-- 
      Eric S. Raymond                     (the mad mastermind of TMN-Netnews)
      UUCP: ...!{uunet,att,rutgers}!snark!eric = eric at snark.UUCP
      Post: 22 S. Warren Avenue, Malvern, PA 19355      Phone: (215)-296-5718