I need to write AVL-tree with generic type in C. The best way I know is to use [ void* ] and to write some functions for creating, copying, assignment and destruction. Please, tell me some better way.
What Alex said. In c, void *
is what there is.
Assuming you must work in C, though... Why do you need to provide the create/copy/assignment/destruction functions to the library? Which features of this library require the AVL-tree code to use those operations?
The major operations on a search tree are insert, delete and lookup, correct? You will need to provide a comparison function for all of those operations, but you should let the clients of this library handle all of the other operations. Simple is probably better in this case.
I will give you an example on how you can achieve generics functionality in C. The example is on a linked list, but I am sure you can adapt it on your AVL tree if necessary.
First of all you will need to define a structure for list element. A possible (most simple implementation):
struct list_element_s {
void *data;
struct list_element_s *next;
};
typedef struct list_element_s list_element;
Where 'data' will act as the "container" where you are going to keep your information, and 'next' is the reference to the direct linked element. (NOTE: Your binary tree element should include a reference to the right / left children elements).
After you create you element structure, you will need to create your list structure. A good practice is to have some members that are pointing to functions: destructor (needed to free the memory being hold by 'data'), and comparator (to be able to compare two of your list elements).
A list structure implementation could look like this:
struct list_s {
void (*destructor)(void *data);
int (*cmp)(const void *e1, const void *e2);
unsigned int size;
list_element *head;
list_element *tail;
};
typedef struct list_s list;
After you design your data structure, you should design your data structure interface. Let's say our list will have the following, most simple, interface:
nmlist *list_alloc(void (*destructor)(void *data));
int list_free(list *l);
int list_insert_next(list *l, list_element *element, const void *data);
void *list_remove_next(list *l, list_element *element);
Where:
- list_alloc : will alocate memory for your list.
- list_free : will free memory allocated for list, and all 'data' being held by list_element(s).
- list_insert_next : will insert a new element next to 'element' . If 'element' is NULL, the insertion will be made at the head of the list.
- list_remove_next : will remove & return (void*)'data' being held by 'element->next' . If 'element' is NULL, it will perform "list->head removal".
And now the functions implementation:
list *list_alloc(void (*destructor)(void *data))
{
list *l = NULL;
if ((l = calloc(1,sizeof(*l))) != NULL) {
l->size = 0;
l->destructor = destructor;
l->head = NULL;
l->tail = NULL;
}
return l;
}
int list_free(list *l)
{
void *data;
if(l == NULL || l->destructor == NULL){
return (-1);
}
while(l->size>0){
if((data = list_remove_next(l, NULL)) != NULL){
list->destructor(data);
}
}
free(l);
return (0);
}
int list_insert_next(list *l, list_element *element, const void *data)
{
list_element *new_e = NULL;
new_e = calloc(1, sizeof(*new_e));
if (l == NULL || new_e == NULL) {
return (-1);
}
new_e->data = (void*) data;
new_e->next = NULL;
if (element == NULL) {
if (l->size == 0) {
l->tail = new_e;
}
new_e->next = l->head;
l->head = new_e;
} else {
if (element->next == NULL) {
l->tail = new_e;
}
new_e->next = element->next;
element->next = new_e;
}
l->size++;
return (0);
}
void *list_remove_next(list *l, list_element *element)
{
void *data = NULL;
list_element *old_e = NULL;
if (l == NULL || l->size == 0) {
return NULL;
}
if (element == NULL) {
data = l->head->data;
old_e = l->head;
l->head = l->head->next;
if (l->size == 1) {
l->tail = NULL;
}
} else {
if (element->next == NULL) {
return NULL;
}
data = element->next->data;
old_e = element->next;
element->next = old_e->next;
if (element->next == NULL) {
l->tail = element;
}
}
free(old_e);
l->size--;
return data;
}
And now, how to use your simple generic linked list implementation. In the following example the list is acting like a stack:
#include <stdlib.h>
#include <stdio.h>
#include "nmlist.h"
void simple_free(void *data){
free(data);
}
int main(int argc, char *argv[]){
list *l = NULL;
int i, *j;
l = list_alloc(simple_free);
for(i = 0; i < 10; i++){
j = calloc(1, sizeof(*j));
if(j != NULL){
*j = i;
list_insert_next(l, NULL, (void*) j);
}
}
for(i = 0; i < 10; i++){
j = (int*) list_remove_next(l, NULL);
if(j != NULL){
printf("%d \n", *j);
}
}
list_free(l);
return (0);
}
Note that instead of "int *j" you can use a pointer that references more complex structures. If you do, don't forget to modify your 'list->destructor' function accordingly.
To do true, performant generics in C, you hack with the preprocessor. This approach has many of the same disadvantages of the C++ template approach; namely that all (most, anyway) code must live in header files, and debugging and testing are a pain. The advantages are also there; that you can get superior performance and let the compiler do all sorts of inlining to speed things up, minimize allocations by reducing indirection, and a modicum of type safety.
The definition looks like (let's imagine we have a hash set)
int my_int_set(int x);
#define HASH_SET_CONTAINED_TYPE int
#define HASH_SET_TYPE my_int_set
#define HASH_SET_FUNC hash_int
#include "hash_set.h"
And then to use it, you simply use the type you created above:
my_int_set x;
my_int_set_init(&x);
my_int_set_add(&x, 7);
if (my_int_set_check(&x, 7)) printf("It worked!\n");
...
// or, if you prefer
my_int_set *x = my_int_set_create();
Internally, this is implemented by a whole bunch of token pasting, etc., and (as noted above) is a huge pain to test.
So something like:
#ifndef HASH_SET_CONTAINED_TYPE
#error Must define HASH_SET_CONTAINED_TYPE
#endif
... /// more parameter checking
#define HASH_SET_ENTRY_TYPE HASH_SET_TYPE ## _entry
typedef struct HASH_SET_ENTRY_TYPE ## _tag {
HASH_SET_CONTAINED_TYPE key;
bool present;
} HASH_SET_ENTRY_TYPE;
typedef struct HASH_SET_TYPE ## _tag {
HASH_SET_TYPE ## _entry data[];
size_t elements;
} HASH_SET_TYPE;
void HASH_SET_TYPE ## _add(HASH_SET_CONTAINED_TYPE value) {
...
}
...
#undef HASH_SET_CONTAINED_TYPE
... // remaining uninitialization
You can even add options; like #define HASH_SET_VALUE_TYPE or #define HASH_SET_DEBUG.