Is there something in C like C ++ templates? If not, how to reuse structures and functions for different data types?

Question

I want to write a linked list that can have a data field to store any types of built-in or user-defined types. In C ++, I would just use a template, but how to do it in C?

Should I rewrite the structure of the linked list and a bunch of its operations for each data type that I want to keep? Unions will not work, because what type it can store is predetermined.

Answer 1

There are various approaches to this problem:

• using the void* data type: this means that you have pointers to memory cells whose type is not further specified. If you extract such a pointer, you can explicitly indicate that inside it: *(int*)(mystruct->voidptr) tells the compiler: look at the memory cell mystruct->voidptr and interpret the contents as int .

• Another thing can be a complicated preprocessor directive. However, this is usually a very non-trivial problem:

• I also found http://sglib.sourceforge.net/

Edit: for preprocessor trick:

  #include <stdio.h> #define mytype(t) struct { t val; } int main(int argc, char *argv[]) { mytype(int) myint; myint.val=6; printf ("%d\n", myint.val); return 0; } 

This will be a simple wrapper for types, but I think it can become quite complex.

Answer 2

There is a reason that people use languages ​​other than C .... :-)

In C, you will have your own data structure with void* members, and you should discard to where you used them for the correct types. Macros can help with some of this noise.

Answer 3

This is less convenient in C (there is a reason C ++ is called C incremented), but this can be done using shared pointers (void *), and applocation handles the control type itself.

A very good implementation of common data structures in C can be found in ubiqx modules , the sources are certainly noteworthy.

Answer 4

With some caution, you can do this with macros that build and manage structures. One of the most proven examples of this is the BSD queue library. It works on every platform I tried (Unix, Windows, VMS) and consists of one header file (without a C file).

It has an unfortunate flaw that it is a little more difficult to use, but it retains as much security as in C.

The header file is here: http://www.openbsd.org/cgi-bin/cvsweb/src/sys/sys/queue.h?rev=1.34;content-type=text%2Fplain , and the documentation on how to use, located here: http://www.openbsd.org/cgi-bin/man.cgi?query=queue .

Also, no, you are stuck with a type of security loss (using (void *) everywhere) or going into STL.

Answer 5

Here's an option that is very flexible, but requires a lot of work.

In the node list, save the data pointer as void * :

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

Then you will create a set of functions for each type that handles tasks such as comparing, assigning, duplicating, etc.:

 // create a new instance of the data item and copy the value // of the parameter to it. void *copyInt(void *src) { int *p = malloc(sizeof *p); if (p) *p = *(int *)src; return p; } void assignInt(void *target, void *src) { // we create a new instance for the assignment *(int *)target = copyInt(src); } // returns -1 if lhs < rhs, 0 if lhs == rhs, 1 if lhs > rhs int testInt(void *lhs, void *rhs) { if (*(int *)lhs < *(int *)rhs) return -1; else if (*(int *)lhs == *(int *)rhs) return 0; else return 1; } char *intToString(void *data) { size_t digits = however_many_digits_in_an_int(); char *s = malloc(digits + 2); // sign + digits + terminator sprintf(s, "%d", *(int *)data); return s; } 

Then you can create a list type with pointers to these functions, for example

 struct list { struct node *head; void *(*cpy)(void *); // copy operation int (*test)(void *, void *); // test operation void (*asgn)(void *, void *); // assign operation char *(*toStr)(void *); // get string representation ... } struct list myIntList; struct list myDoubleList; myIntList.cpy = copyInt; myIntList.test = testInt; myIntList.asgn = assignInt; myIntList.toStr = intToString; myDoubleList.cpy = copyDouble; myDoubleList.test = testDouble; myDoubleList.asgn = assignDouble; myDoubleList.toStr = doubleToString; ... 

Then, when you pass the list to an insert or search operation, you call the functions from the list object:

 void addToList(struct list *l, void *value) { struct node *new, *cur = l->head; while (cur->next != NULL && l->test(cur->data, value) <= 0) cur = cur->next; new = malloc(sizeof *new); if (!new) { // handle error here } else { new->data = l->cpy(value); new->next = cur->next; cur->next = new; if (logging) { char *s = l->toStr(new->data); fprintf(log, "Added value %s to list\n", s); free(s); } } } ... i = 1; addToList(&myIntList, &i); f = 3.4; addToList(&myDoubleList, &f); 

By delegating type-related operations to separate functions that are called using function pointers, you now have a list structure that can hold values ​​of any type. To add support for new types, you only need to implement the new functions of copy, destination, toString, etc. For this new type.

There are flaws. Firstly, you cannot use constants as parameters of a function (for example, you cannot do something simple, for example addToList(&myIntList, 1); ) - first you must assign everything to a variable and pass the address of the variable (which is why you you need to create new instances of the data item when you add it to the list, if you just assigned an address to a variable, each item in the list will point to the same object, which may no longer exist depending on the context).

Secondly, you complete a lot of memory management; you are not just creating a new instance of the node list, but you must also create a new instance of the data item. Remember to free the item before freeing the node. Then you create a new instance of the row every time you want to display data, and you must remember to free this row when you are done with it.

Finally, this solution gives type safety directly from the window and into the oncoming traffic (after its ignition). Delegate functions expect you to keep types straight; there is nothing stopping you from passing the address of the double variable to one of the int processing functions.

Between memory management and the fact that you have to make a function call for almost every operation, performance will suffer. This is not a quick fix.

Of course, this assumes that each item in the list is the same type; if you want to store elements of different types in one list, then you will need to do something else, for example, associate functions with each node, and not with a general list.

Answer 6

I wrote a generic “linked list” template in C using a preprocessor, but it's pretty awful to look at, and heavily processed code is not easy to debug.

These days, I think you would be better off using another tool for creating code, such as Python / Cog: http://www.python.org/about/success/cog/

Answer 7

I agree with JonathanPatschke to answer that you should look at sys / queue.h , although I have never tried this myself, as it is not on some platforms that I work with. I also agree with Vicki's answer to use Python .

But I found that five or six very simple C macros meet most of my gardening needs. These macros help clean up ugly, error-prone code without clogging it with hidden void * that destroy type safety. Some of these macros:

 #define ADD_LINK_TO_END_OF_LIST(add, head, tail) \ if (!(head)) \ (tail) = (head) = (add); \ else \ (tail) = (tail)->next = (add) #define ADD_DOUBLE_LINK_TO_END_OF_LIST(add, head, tail) \ if (!(head)) \ (tail) = (head) = (add); \ else \ (tail) = ((add)->prev = (tail), (tail)->next = (add)) #define FREE_LINK_IN_LIST(p, dtor) do { /* singly-linked */ \ void *myLocalTemporaryPtr = (p)->next; \ dtor(p); \ (p) = myLocalTemporaryPtr;} while (0) #define FREE_LINKED_LIST(p, dtor) do { \ while (p) \ FREE_LINK_IN_LIST(p, dtor);} while (0) // copy "ctor" (shallow) #define NEW_COPY(p) memcpy(myMalloc(sizeof *(p)), p, sizeof *(p)) // iterator #define NEXT_IN_LIST(p, list) ((p) ? (p)->next : (list)) 

So for example:

 struct MyContact { char *name; char *address; char *telephone; ... struct MyContact *next; } *myContactList = 0, *myContactTail; // the tail doesn't need to be init'd ... struct MyContact newEntry = {}; ... ADD_LINK_TO_END_OF_LIST(NEW_COPY(newEntry), myContactList, myContactTail); ... struct MyContact *i = 0; while ((i = NEXT_IN_LIST(i, myContactList))) // iterate through list // ... 

The next and prev members have hardcoded names. They should not be void * , which avoids problems with strict anti-aliasing. They do must be zeroed out when creating the data item.

The dtor argument for FREE_LINK_IN_LIST usually a function of type free or (void) to do nothing, or another macro, such as:

 #define MY_CONTACT_ENTRY_DTOR(p) \ do { if (p) { \ free((p)->name); \ free((p)->address); \ free((p)->telephone); \ free(p); \ }} while (0) 

So, for example, FREE_LINKED_LIST(myContactList, MY_CONTACT_ENTRY_DTOR) free all members of the list (duck) led by myContactList .

There is one void * , but maybe it can be deleted via gcc typeof .

Answer 8

If you need a list that can contain elements of different types at the same time, for example. a int followed by three char * , followed by struct tm , and then using void * for the data is the solution. But if you need only a few types of lists with the same methods, the best solution depends on whether you want to avoid generating many instances of almost identical machine code or just not print the source code.

Structure declaration does not generate machine code ...

 struct int_node { void *next; int data; }; struct long_node { void *next; long data; }; 

... and one single function that uses the void * parameter and / or return value can handle all of them.

 struct generic_node { void *next; }; void *insert(void *before_this, void *element, size_t element_sizes);