Generic ADT

[Alberto =?iso-8859-1?Q?Gim=E9nez?=]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


Hello, I have a simple question, and after a *very long* google search
I still can't get it.

It's about generic abstract data types (for example, a list). I've
coded it in ADA, and its quite easy to do, but there is a thing I cannot
decide when doing it in C. This is about the actual data storing in a
node. I've seen lots of examples where what is stored is the pointer to
data, but I think it would be better to store the actual object (of
course, you need the element size). For example, this can be the node:

struct node {
void *object;
struct node *next;
}

struct ADT {
struct node *head;
size_t obj_size;
}

and a function could be, for example:

int myfunction (struct ADT *list, void *elem)
{
struct node *tmp;
...
tmp = malloc (sizeof (struct node));
/* Option 1: examples seen googling, store pointer */
tmp->object = elem;

/* Option 2: Seen 1 or 2 times, copying the object itself */
memcpy (&(tmp->object), elem, list->obj_size);
...

I personally think Option 2 is more useful, because you can mess with
stored items by modifying the element in the caller function (please,
correct me

The implementation can also change, without using memcpy, by passing a
user-supplied object copy function, this is trivial (I think).

Just looking for some advice, how could you do it? TIA

- --
Alberto Giménez, SimManiac en el IRC
http://www.almorranasozial.es.vg
GnuPG ID: 0x3BAABDE1
Don't compare Linux with Windows. There's no colour (except blue).
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQFAlCo20keCtzuqveERAgBOAJ9OUDqLSOE+7ooKdkoxzFToh0mJdwCfXENC
57YRs3DhVy2+NzxN0829v7k=
=Cs6G
-----END PGP SIGNATURE-----

 

[Malcolm]

It's about generic abstract data types (for example, a list). I've
coded it in ADA, and its quite easy to do, but there is a thing I
cannot decide when doing it in C. This is about the actual data
storing in a node. I've seen lots of examples where what is stored is
the pointer to data, but I think it would be better to store the actual
object (of course, you need the element size). For example, this can
be the node:

struct node {
void *object;
struct node *next;
}

struct ADT {
struct node *head;
size_t obj_size;
}

If you want to go heavily into abstaract data types then you will find that
C++ has far more support.

If you use C, you will find that the langauge works nicely as long as
everything is passed around as a void * to dynamically-allocated memory.
Unfortunately for heavily-used small objects the overhead can be
considerable, in allocation, storing the pointer itself, and dereferencing
to do anything usual. The normal way round this is to abandon ADTs and write
hard-coded functions for your performance-critical types.
You can of course retain some abstraction at the cost of messing about with
the langauge trying to force it to define extensible structures, copy them
without a call to memcpy(), etc. This isn't generally good programming.

 

[CBFalconer]

It's about generic abstract data types (for example, a list). I've
coded it in ADA, and its quite easy to do, but there is a thing I
cannot decide when doing it in C. This is about the actual data
storing in a node. I've seen lots of examples where what is stored
is the pointer to data, but I think it would be better to store
the actual object (of course, you need the element size). For
example, this can be the node:

.... snip ...

You might take a look at the techniques used in hashlib, available
at:

<http://cbfalconer.home.att.net/download/hashlib.zip>

 

[Alberto =?iso-8859-1?Q?Gim=E9nez?=]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

El Sun, 02 May 2004 01:11:37 GMT, CBFalconer escribió:

<http://cbfalconer.home.att.net/download/hashlib.zip>

Hey! I've seen it before. I was just investigating webpages from this
group's members

I think hashlib is great, but it uses a user-defined copy function
(or duplication). I wonder if my memcpy option can be as portable as
your approximation, or there any problem with the standard or
portability issues. Thanks a lot.

- --
Alberto Giménez, SimManiac en el IRC
http://www.almorranasozial.es.vg
GnuPG ID: 0x3BAABDE1
Don't compare Linux with Windows. There's no colour (except blue).
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQFAlN/+0keCtzuqveERAvGYAJwOyp7U8701vcJl7iQyR9UlQjeEngCeOJhZ
Aty9ckDBmGClfx94xEjUWa8=
=sSlS
-----END PGP SIGNATURE-----

 

[Kamilche]

It's about generic abstract data types (for example, a list). I've
coded it in ADA, and its quite easy to do, but there is a thing I cannot
decide when doing it in C.

Here's a link to a generic container type for C, that can store a list
of anything that's all the same size - strings, structs, what have
you.

http://www.planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=4550&lngWId=3

 

[Arthur J. O'Dwyer]

Here's a link to a generic container type for C, that can store a list
of anything that's all the same size - strings, structs, what have
you.

http://www.planet-source-code.com/vb/scripts/ShowCode.asp?
txtCodeId=4550&lngWId=3

The example 'main' program is very nice and clean. Unfortunately,
it gets to be so clean by pushing all the dirty bits into "container.c".
Comments:
Style points: "container.c" ought to #include "container.h"; the
inner parentheses in 'malloc(sizeof(*p))' are just visual clutter;
and there ought to be comments in the header describing what the
functions do. Particularly 'Container_Remove' is confusing unless
you have the code right in front of you.
Inconsistency: Why does every function 'assert(p)' except for
'Container_Add', which handles null pointers silently? You should be
consistent: either 'assert' all the time (IMHO a bad idea), or check
for the null pointer every time (IMHO a better idea). Also, as long
as you're checking for NULL, I think it would be nice if
'Container_Add(NULL, foo)' behaved the same way as
'Container_Add(Container_Create(sizeof foo), foo)'. Of course, you
can't do that in a standards-conforming way without macro magic;
but read on.
Big big problem: 'Container_Add' is majorly broken. It tries to
'memcpy' out of a 'va_list', which first of all isn't even possible
if 'va_list' is not a pointer or array type, and secondly is probably
going to crash on a *lot* of systems. There is no portable way to
do what you're trying to do; the simplest solution involves the client
creating a temporary and passing its address as a 'void *' to
'Container_Add'.
Also problem: 'Container_Add' never checks or asserts for NULL on
'Argument'. But since 'Argument' is not needed, you can fix this
pretty easily.
Design bug: 'Container_DupeData' is all well and good, but you have
provided no way for the client to duplicate an entire container (i.e.,
a copy constructor). Rule of Three applies to C ADTs as well, y'know!

[Also, there's an empty 'New Folder' in the ZIP file. Is that
something Planet Source Code sticks in there, or an error?]

HTH,
-Arthur