Generic ADT

Discussion in 'C Programming' started by Alberto =?iso-8859-1?Q?Gim=E9nez?=, May 1, 2004.

  1. -----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-----
     
    Alberto =?iso-8859-1?Q?Gim=E9nez?=, May 1, 2004
    #1
    1. Advertising

  2. Alberto =?iso-8859-1?Q?Gim=E9nez?=

    Malcolm Guest

    "Alberto Giménez" <> 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.
     
    Malcolm, May 2, 2004
    #2
    1. Advertising

  3. Alberto =?iso-8859-1?Q?Gim=E9nez?=

    CBFalconer Guest

    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?
     
    CBFalconer, May 2, 2004
    #3
  4. -----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-----
     
    Alberto =?iso-8859-1?Q?Gim=E9nez?=, May 2, 2004
    #4
  5. Alberto =?iso-8859-1?Q?Gim=E9nez?=

    Kamilche Guest

    Alberto Giménez <> 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/scripts/ShowCode.asp?txtCodeId=4550&lngWId=3
     
    Kamilche, May 2, 2004
    #5
  6. On Sun, 2 May 2004, Kamilche wrote:
    >
    > 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.

    >
    > 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
     
    Arthur J. O'Dwyer, May 2, 2004
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kenneth
    Replies:
    4
    Views:
    725
    Tony Morris
    Nov 11, 2004
  2. Gaz
    Replies:
    2
    Views:
    1,575
  3. Tree ADT vs Database

    , Apr 8, 2006, in forum: Java
    Replies:
    9
    Views:
    1,433
    Roedy Green
    Apr 8, 2006
  4. SunScreen
    Replies:
    2
    Views:
    2,943
    Howard
    Nov 18, 2004
  5. Dr Ann Huxtable
    Replies:
    1
    Views:
    379
    Howard
    Nov 29, 2004
Loading...

Share This Page