Runtime type-safety (for linked lists)

Discussion in 'C Programming' started by Dave, Sep 28, 2003.

  1. Dave

    Dave Guest

    Hello all,

    I am creating a linked list implementation which will be used in a
    number of contexts. As a result, I am defining its value node as type
    (void *). I hope to pass something in to its "constructor" so that I
    will be able to manipulate my list without the need for constant
    casting; some sort of runtime type-safety mechanism.

    For example, I want a linked lists of ints. I want to be able to say:

    Newguy = ll_new(int); //so that in the future i can say:
    Newguy.next.val++;

    Or alternatively a list of bools:

    Newerguy = ll_new([type]bool) //so that in the future i can say:
    Newerguy.next.val = false;

    Anyhow, I'm looking for ways to enforce runtime type-safety. Any
    thoughts are appreciated, especially since I know for a fact this can
    be done (and without unions...).

    Dave
    Dave, Sep 28, 2003
    #1
    1. Advertising

  2. On Sun, 28 Sep 2003, Dave wrote:
    >
    > I am creating a linked list implementation which will be used in a
    > number of contexts. As a result, I am defining its value node as type
    > (void *). I hope to pass something in to its "constructor" so that I
    > will be able to manipulate my list without the need for constant
    > casting; some sort of runtime type-safety mechanism.


    Can't be done easily. If you have a variable of type (void *), then
    you're going to have to cast it to something else in order to dereference
    it. That's just the way C works. But read on.

    > For example, I want a linked lists of ints. I want to be able to say:
    >
    > Newguy = ll_new(int); //so that in the future i can say:
    > Newguy.next.val++;



    Well, here are two things I've thought of. You can go the whole hog
    and create a big dispatch table inside your linked list class, so
    that one can write


    struct llnode {
    void *val; /* data stored through here */
    };
    struct my_crazy_llist {
    struct llnode *head;
    struct llnode *tail;
    struct llnode *current; /* for iteration */
    [...dispatch stuff...]
    };

    int ll_add_dispatch(struct llist *who, const char *method,
    void *(*how)(void *, va_list));
    void *ll_dispatch(struct llist *who, struct llnode *where,
    const char *method, ...);

    void *int_inc(void *val, va_list ap)
    {
    ++ *(int *)val;
    }

    void *int_asgn(void *val, va_list ap)
    {
    *(int *)val = va_arg(ap, int);
    return 0;
    }

    [...]

    my_crazy_llist *Newguy = ll_new();
    ll_add_dispatch(Newguy, "++", int_inc);
    ll_add_dispatch(Newguy, "=", int_asgn);
    [...]

    ll_dispatch(Newguy, Newguy->current->val, "++");
    ll_dispatch(Newguy, Newguy->current->val, "=", 42);

    Now, whether you want to go this route is completely up to you
    and your asylum warden. A simpler route might be to create
    just a few generic routines via #define, and use those for the
    commonplace things -- write your own for the complicated things.
    E.g.,

    #define ASGN(var, type, val) ((*(type *)(var)) = (val))

    ASGN(Newguy->current->val, int, 42);


    > Anyhow, I'm looking for ways to enforce runtime type-safety. Any
    > thoughts are appreciated, especially since I know for a fact this can
    > be done (and without unions...).


    And how, exactly, *do* you know this can be done? Have you seen
    it done before? (Why not just copy that implementation, then?)

    My recommendation: Use C++ and templates for this stuff. Don't
    mess around with polymorphism in C, because the language simply
    isn't designed for that. (Not that hacking around like this isn't
    fun; it's just not very productive in the long run.)

    -Arthur
    Arthur J. O'Dwyer, Sep 28, 2003
    #2
    1. Advertising

  3. Dave

    goose Guest

    (Dave) wrote in message news:<>...
    > Hello all,
    >
    > I am creating a linked list implementation which will be used in a
    > number of contexts. As a result, I am defining its value node as type
    > (void *). I hope to pass something in to its "constructor" so that I
    > will be able to manipulate my list without the need for constant
    > casting; some sort of runtime type-safety mechanism.
    >
    > For example, I want a linked lists of ints. I want to be able to say:
    >
    > Newguy = ll_new(int); //so that in the future i can say:
    > Newguy.next.val++;
    >
    > Or alternatively a list of bools:
    >
    > Newerguy = ll_new([type]bool) //so that in the future i can say:
    > Newerguy.next.val = false;
    >


    You should, if you really need this, listen to Authers advice
    and use C++ with templates (in fact, dont "create" anything, just
    use the stl to store whatever you want to).

    if you are doing it purely for the fun aspect, then a way around
    the "dont know what to cast this to" in the code (like the
    Newguy = ll_new(int)
    above) is to use macros combined with a function that implements
    a lookup table based on the type.

    ----hw.c----
    #include <stdio.h>
    #include <stdlib.h>

    /* the following two arrays must be
    kept in synch with one another.
    */
    enum the_type_t {
    INT,
    CHAR,
    FLOAT,
    DOUBLE,
    UNKNOWN
    };

    char *all_type_strings[] = {
    "int",
    "char",
    "float",
    "double",
    NULL
    };

    /* your structure for a single node in a ll */
    struct node_t {
    void *data;
    struct node_t *next;
    };

    enum the_type_t get_type (char *the_type_string) {
    enum the_type_t retvalue = UNKNOWN;
    int i;
    for (i=0; all_type_strings!=NULL; i++) {
    if (strcmp (all_type_strings, the_type_string)==0) {
    retvalue = i;
    break;
    }
    }
    return retvalue;
    }

    struct node_t *fll_new (enum the_type_t the_type) {
    void *data;
    struct node_t *node = malloc (sizeof *node);
    if (!node) {
    return NULL;
    }
    switch (the_type) {
    case INT: data = malloc (sizeof (int)); break;
    case CHAR: data = malloc (sizeof (char)); break;
    case FLOAT: data = malloc (sizeof (float)); break;
    case DOUBLE: data = malloc (sizeof (double)); break;
    case UNKNOWN:
    default:
    data = NULL;
    };
    node->data = data;

    return node;
    }


    #define ll_new(the_type) fll_new (get_type (#the_type))

    int main (void) {
    struct node_t *MyData = ll_new (int);

    if (!MyData) {
    printf ("no mem ?\n");
    return EXIT_FAILURE;
    }

    *(int *)MyData->data = 42;
    printf ("data stored = %i\n", *(int *)MyData->data);

    /* this can possibly be wrapped into a macro as well */
    free (MyData->data);
    free (MyData);

    return EXIT_SUCCESS;
    }

    ----end of hw.c----

    its not too hard to massage the above (rather ugly) code into
    a linked list, as the non-intuitive parts of it is already
    done. If you know how to implement a normal linked list, then
    you could do it.

    > Anyhow, I'm looking for ways to enforce runtime type-safety. Any
    > thoughts are appreciated, especially since I know for a fact this can
    > be done (and without unions...).
    >


    I dont think that that (runtime safety) *can* be done properly. but
    good luck anyway.


    goose,
    post a link to the finished goods, will you? i'm interested ;-)
    goose, Sep 29, 2003
    #3
    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. Chris Ritchey
    Replies:
    7
    Views:
    463
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    453
    emerth
    Jul 10, 2003
  3. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    384
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  4. fool
    Replies:
    14
    Views:
    491
    Barry Schwarz
    Jul 3, 2006
  5. jawdoc
    Replies:
    9
    Views:
    734
    Chris Thomasson
    Mar 10, 2008
Loading...

Share This Page