Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Generic ADT

Reply
Thread Tools

Generic ADT

 
 
Alberto =?iso-8859-1?Q?Gim=E9nez?=
Guest
Posts: n/a
 
      05-01-2004
-----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+7ooKdkoxzF Toh0mJdwCfXENC
57YRs3DhVy2+NzxN0829v7k=
=Cs6G
-----END PGP SIGNATURE-----
 
Reply With Quote
 
 
 
 
Malcolm
Guest
Posts: n/a
 
      05-01-2004

"Alberto Giménez" <(E-Mail Removed)> wrote in message
> 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.


 
Reply With Quote
 
 
 
 
CBFalconer
Guest
Posts: n/a
 
      05-02-2004
Alberto Giménez wrote:
>
> 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>

--
A: Because it fouls the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?


 
Reply With Quote
 
Alberto =?iso-8859-1?Q?Gim=E9nez?=
Guest
Posts: n/a
 
      05-02-2004
-----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/+0keCtzuqveERAvGYAJwOyp7U8701vcJl7iQyR9UlQjeEngCeO JhZ
Aty9ckDBmGClfx94xEjUWa8=
=sSlS
-----END PGP SIGNATURE-----
 
Reply With Quote
 
Kamilche
Guest
Posts: n/a
 
      05-02-2004
Alberto Giménez <(E-Mail Removed)> wrote in message news:<mn917c.7d6.ln@127.0.0.1>...

> 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...=4550&lngWId=3
 
Reply With Quote
 
Arthur J. O'Dwyer
Guest
Posts: n/a
 
      05-02-2004

On Sun, 2 May 2004, Kamilche wrote:
>
> Alberto Giménez <(E-Mail Removed)> wrote:
> > 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.../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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Tree ADT vs Database djcredo@gmail.com Java 9 04-08-2006 06:15 PM
Binary Search Tree Dictionary ADT Gaz Java 2 01-28-2006 10:22 PM
Heirarchical ADT supporting column and row objects Dr Ann Huxtable C++ 1 11-29-2004 03:43 PM
New in C++:Abstract Data Types(ADT) - Base Class SunScreen C++ 2 11-18-2004 04:43 PM
difference between java built in classes and ADT Kenneth Java 4 11-11-2004 09:11 AM



Advertisments