E
Eric Sosman
[...]Generally, true. I don't even consciously notice adding a small
list implementation -- it's too trivial to notice.
I'm curious what you consider a plain vanilla linked list?
I'll assume a basic familiarity with the notions of "list"
and of "link" (if these are lacking, ask any IUT student). As
expressed in C, a list's nodes are usually structs because this
is a convenient way to package payload and link(s) together in
one easily-managed blob. Each node contains a link to its
successor and perhaps also to its predecessor. The links are
usually struct pointers, sometimes array indices (if all the
nodes inhabit a single array), with a null pointer (or a special
index value) indicating "no successor/predecessor." There'll
also be some metadata: At the very least, a link to the list's
first node and often a link to the last as well (sometimes a
pointer-to-struct, sometimes a pointer-to-pointer-to-struct).
The metadata may be free-standing, or may inhabit a special
"list header" (especially for a circular list).
I'd consider the variations covered by the above to be
"plain vanilla" linked lists. Programmers should be familiar
with -- and comfortable with -- the basic operations of inserting,
deleting, searching, and traversing such lists. These operations
are so basic, in my view, that hiding the details away behind an
interface is (1) overkill and (2) obfuscatory. It makes about
as much sense to me as
int fetchFromIntArray(const int *array, size_t index) {
return array[index];
}
void storeIntoIntArray(int *array, size_t index, int value) {
array[index] = value;
}
What things might change a list's flavor to something other
than vanilla, to some flavor that might justify more opacity? A
non-exhaustive, er, list:
- Unusual links. If the links are self-relative offsets (as
might be used in lists shared between processes that map them
to different virtual addresses), or if the stored values are
the XOR of a forward and backward link, or some other odd
encoding is used, link manipulation may become intricate
enough to justify being packaged away somewhere.
- Bit-diddling. If the bits of the links' representation are
twiddled to encode additional information (e.g., by using
a few low-order "known to be zero" bits as flags), it's
probably best to put the encoding and decoding out of sight
somewhere. (The writers of LISP interpreters seem particularly
attracted to such techniques.)
- Peculiar nodes. If the list nodes are not structs, there's
usually something slightly exotic going on, worthy of being
hidden from us easily-scandalized maiden aunts.
- Mammoth metadata. If a list carries more than the usual
amount of metadata -- a node count, a link to the node most
recently inserted (at whatever position), a link to the node
at the midmost position, whatever -- it's probably best to
let a function package take care of the maintenance.
- Additional linkage. If there are additional links, as in
a skip list or some such, the burden of maintaining them
grows to the point where pre-packaging becomes justifiable.
.... and so on. However, it doesn't seem to me that a "generic"
package is what's needed for this sort of thing; the oddities are,
well, odd, and not easily generified. If you've got a list in
shared memory, using self-relative links whose low-order bits
encode extra information about the pointed-to nodes, you'll most
likely write a few functions to manage lists of exactly that
description; the IUT Senior Thesis Generic List Package simply
won't suffice.
Perhaps if
you could describe the vanilla list feature subset, maybe by listing
functions of an existing implementation like GLib or the C++ STL list,
or is there even a function interface to it?
I'm not intimate with GLib, and I have an irrational dislike
for all things C++, so I'll take a pass on this one.
Do you feel that adding a c_compare_function_t makes it a 'chocolate
twist with jimmies' linked list?
Sorry; I don't even know what a c_compare_function_t might be.