C binary search tree with custom data

Question

Suppose I got an external library bst that handles custom data types insertion in a bst

Here are the new_node,insert and search functions :

//new node

struct bst_node* new_node(void* data) 
{
    struct bst_node* result = malloc(sizeof(struct bst_node));
    assert(result);

    result->data = data;
    result->left = result->right = NULL;
    return result;
}

//insert node

void insert(struct bst_node** root, void* data) {
    struct bst_node** node = search(root, data);
    if (*node == NULL) {
        *node = new_node(data);
    }
}

//search node

    struct bst_node** search(struct bst_node** root, void* data) {
        struct bst_node** node = root;
        while (*node != NULL) {

        if (data, (*node)->data < 0)
            node = &(*node)->left;
        else if (compare_result > 0)
            node = &(*node)->right;
        else
            break;
    }
    return node;
}

and the main.c ,suppose i read the models from a txt file :

#include <stdio.h>
#include <stdlib.h>
#include "bst.h"
#include <string.h>

#define MAX 50

typedef struct data_t{
    int gg,mm,aaaa;    
}data;

typedef struct accesories_t{
    char name[MAX];
    int price;
    struct accesories_t *next;    
}accesories;

typedef struct model_t{
    //int index;
    char name[MAX];
    char file_a[MAX];
    data date;
    int price;
    accesories *acs;
}model;


int main(int argc, char *argv[])
{
    int menu=0;

    char nf[MAX];

    char name[MAX];
    char fa[MAX];
    int price,gg,mm,a;

    strcpy(nf,argv[1]);

    FILE *fp=fopen(nf,"+r");
    model m;
    struct bst_node* root = NULL;

    while(fscanf(fp,"%s %d//%d//%d %d %s",name,gg,mm,a,price,fa)!=EOF){
        strcpy(m.name,name);
        strcpy(m.file_a,fa);
        m.date.gg=gg;
        m.date.mm=mm;
        m.date.aaaa=a;
        m.price=price;
        m.index=index++;  

        insert(&root ,m);  
    }

  system("PAUSE");  
  return 0;
}

So my question arises in the search function, how can i manage a comparator on custom data (let's say insert the models ordered by name (strcmp) ? I'm very confused on how can i pass the names to the bst.c given that bst.c has no idea how my model struct is made.

Should I modify the bst library and maybe on bst struct add before data some sort of index and use that as comparator ?

OK I've managed to fix that by adding a string key inside the struct bst

What I'm trying to achieve now is to return the void* data type casted into struct model, suppose _I got the tree with nodes containing the data, once I do a search I'd like to return for example the data contained in a node and work on it, any clues ????

tried someting like without any success suppose node is a returned node from a search function

model *m;
m=(model*)node->data;

how could I achieve this?

You could pass it as a function pointer in an extra argument to all functions that need the comparison. — wildplasser
– wildplasser, Commented Feb 26, 2012 at 15:10
Exactly. (but that would create the need for a special "head" nodetype) There you go. At your service.... — wildplasser
– wildplasser, Commented Feb 26, 2012 at 15:14
Holy crap, this question would be answered in about 5 minutes by digging through existing generic tree API implementations demanded of the standard C library. man tsearch, find the code that implements it, and with it enlightenment. — tbert
– tbert, Commented Feb 26, 2012 at 20:47

wildplasser · Accepted Answer · 2012-02-26 15:22:36Z

0

Example for using compare functions as callbacks. Definitions omitted for brevity.

int llist_cmp(struct llist *l, struct llist *r)
{
if (!l) return 1;
if (!r) return -1;
return strcmp(l->payload,r->payload);
}

struct llist * llist_split(struct llist **hnd, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *this, *save, **tail;

for (save=NULL, tail = &save; this = *hnd; ) {
        if (! this->next) break;
        if ( cmp( this, this->next) <= 0) { hnd = &this->next; continue; }
        *tail = this->next;
        this->next = this->next->next;
        tail = &(*tail)->next;
        *tail = NULL;
        }
return save;
}

struct llist * llist_merge(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *result, **tail;

for (result=NULL, tail = &result; one && two; tail = &(*tail)->next ) {
        if (cmp(one,two) <=0) { *tail = one; one=one->next; }
        else { *tail = two; two=two->next; }
        }
*tail = one ? one: two;
return result;
}

BTW: the above snippet handles linked lists, but the mechanism for passing function pointers is the same as with trees, of course. And after all it was homework ;-)

edited Feb 26, 2012 at 15:22

answered Feb 26, 2012 at 15:16

wildplasser

44.5k9 gold badges72 silver badges116 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Lucian Enache Over a year ago

Still I can't find a way on how to manage model.name inside my bst.c functions, something tells me that I should use the void pointers but for example when i call the new_node function when I pass the model item to it I have no Ideea on how to compare that item.name

wildplasser Over a year ago

Well, in your main() you have declared m to be a (struct) model. Change that into a pointer, and malloc the space for m once you need it (inside the fscanf() loop) The insert function may also have to be changed (it already takes a void* pointer as an argument). And create the compare function, probably it will compare the names inside the structs, similar to my snippet.

Collectives™ on Stack Overflow

C binary search tree with custom data

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related