tags:

views:

185

answers:

3

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.

+3  A: 

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.

Jesse Millikan
Well, you're right, I also need a comparison function... And yes, I just need to get from users of my strange struct their functions for creation(with default value), copying, deletion and assignment. But in my little project I must provide an example of usage of my data structure (with C-strings). I'm just looking for simplier way...
Ribtoks
Why do you need to get those functions from them? Like I'm saying, they aren't necessary for any of the basic tree operations; the more C-like way here would be to only provide the insert/delete/lookup operations on void pointers and let outside code handle their own datatypes.
Jesse Millikan
+3  A: 

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.

Andrei Ciobanu
Uhm... assigning the result of a memory allocation and testing it for NULL within the same if(), without any need, as you do in list_alloc I consider as bad style, but assigning it and dereferencing it in the same expression without any check for NULL is such a major WTF that I have to add -1 to your post.
Secure
Can you please be more specific ? Any suggestions on how to re-write list_alloc ?
Andrei Ciobanu
l = calloc(1,sizeof(*l)); if (l != NULL) ...
Secure
I've modified main(). I don't consider memory allocation and testing for NULL a bad style, still I am not a professional C programmer and I might be wrong.
Andrei Ciobanu
In main(), l should be checked for NULL after calling list_alloc()
Tim Post
You are right regarding check in main(). I won't edit the code anymore, but you are right :).
Andrei Ciobanu
+1  A: 

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.

For "superior performance" and "to speed things up"... Looking at it alone is enough to really understand why premature optimization is the root of all evil.
Secure