Runtime type-safety (for linked lists)

[Dave]

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

 

[Arthur J. O'Dwyer]

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

 

[goose]

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 ;-)