Solved

Strange problem with b-trees, and C functions in general

Posted on 1997-05-31
9
214 Views
Last Modified: 2010-04-15
Subject: Strange problem with b-trees, and C functions in general

Hi to everyone...
I need your answer to a strange subject
that has to do with b-trees.
I want to built a function that will create a b-tree and will return its root node.
As parameters to the function I must pass the degree of the tree, the type of key and the key size.
For example:

CreateTree(root,degree,attrType,attrLength)

This function creats a tree of 'degree' and returns its root.

attrType here gives the type of he key
('i' for int,'f' for float and 'c' for string)
attLength gives the size of the key
(4 for int,4 for float and 1-255 for the string)

struct item{
                    'attrType' key;
                    struct node *p;
                    };

                    struct node{
                    struct node *p0;
                    struct item matrix[2*('degree')];
                    };

                    Where ' ' indicate a parameter to function
                    CreateTree(root,degree,attrType,attrLength)

Please help me... How can I do this????
I think this problem is impossible....

ps. (I think unions can't be used since I must pass the       key length...)

Thanks for your help...(if any)
0
Comment
Question by:kkarnez
9 Comments
 

Author Comment

by:kkarnez
ID: 1250574
Lets see your programming strength guys...

0
 
LVL 10

Expert Comment

by:rbr
ID: 1250575
Try this 2 functions.

typedef struct node {
    void *pdata;  
    struct node **pplinks;
} NODE;


typedef struct {
    char type;
    int length;
    int degree;
    NODE *pnode;
} ROOT_NODE;


void CreateNodeEntry(ROOT_NODE *proot, NODE **ppnode)
{
    *ppnode = (NODE *)calloc (1, sizeof(NODE));
   
    (*ppnode)->pdata = calloc (proot->length, 1);
   
    (*ppnode)->pplinks=(struct node **)calloc (proot->degree, sizeof(NODE *));
}

void CreateTree (ROOT_NODE **pproot, int degree, char attrType, int attrLength)
{
    *pproot = (ROOT_NODE *)calloc (1, sizeof(ROOT_NODE));
   
    (*pproot)->type=attrType;
    (*pproot)->degree=degree;
    (*pproot)->length=attrLength;
    CreateNodeEntry (*pproot, &((*pproot)->pnode));
}


CreateTree will create your tree and with CreateNodeEntry you will allocate memory for every node you need. There are no error checkings inside these to functions (Enough memory free, attrLength == 4 for attrType == 'i', ...) but I hope this will help to solve your problems.

Robert B. Rossmann


0
 
LVL 3

Expert Comment

by:LucHoltkamp
ID: 1250579
I suggest you move to C++, then you can do this in a typesave and elegant way, using templates.

Furthermore I think rbr's idea of using pointers is the best way to go in C.
.luc.
0
 

Expert Comment

by:y_lestr
ID: 1250580
I have all the sources to create and use Btrees in Pascal, I have done it when I was student, it's possible to easily translate the sources in C
0
Control application downtime with dependency maps

Visualize the interdependencies between application components better with Applications Manager's automated application discovery and dependency mapping feature. Resolve performance issues faster by quickly isolating problematic components.

 
LVL 4

Accepted Solution

by:
jos010697 earned 200 total points
ID: 1250581
The problem can be solved, although in a 'dirty' way. What
you actually want, is an array of things embedded in a struct,
while the size of the array is not known in advance. For
the sake of the example, here's a simplified structure:

struct varlen_t {
   int size;
   <type> a[1];
}

We're assuming at least one element present in the array. Here's
a way to allocate a structure containing an array with 'n' elements:

varlen_t* struct_alloc(int n) {

varlen_t* v;

v== malloc(sizeof(struct varlen_t)+(n-1)*(sizeof(<type>));

v->size= n;

return v;

}

Note that I simply allocated n-1 elements more for the
entire thingy. This'll work for any array being the last
element of a struct ... (ANSI/ISO tried to rule out this
'feature', but they only succeeded half way ;-)

Also note that you have to store the actual size of the
array in the structure somewhere (nowhere else the
size is known, so you have to ...)

kind regards,

Jos aka jos@and.nl
0
 

Expert Comment

by:stardate
ID: 1250582
I was looking at writing a b-tree myself, but opted for some source code that I found in simtel.  This code will do the job I need, with minor tinkering.  You may find that this code will do what you need.  The code will most certainly demonstrate how to create a (new)root node.

This source code is located at this URL

http://oak.oakland.edu/pub/simtelnet/msdos/c/bplus11.zip

Please note that this is shareware code.
0
 

Expert Comment

by:nate091597
ID: 1250576
It's not impossible, but it sounds like an assignment.
0
 

Expert Comment

by:NewGuy
ID: 1250577
Won't things become easier if we use

typedef ROOT_NODE *ROOT_NODEPTR;

and reduce all the pointer stuff
gosh...see less stars then
0
 
LVL 1

Assisted Solution

by:qed070297
qed070297 earned 200 total points
ID: 1250578
C's typing implementation does not allow for this degree of
flexibility from mere declarations.  In particular, you cannot
pass types as parameters to functions.  All typing is considered
fixed in one way or another.  I would recommend a more
brute force mechanism for solving this problem:

struct keytag {
    int attrLength;
    char KeyContents[];
};

struct itemtag {
    struct node *p;
    struct keytag *key;
};

struct node {
    struct node *p0;
    int degrees;
    struct item matrix[];
};

struct node * CreateNode(int degree,int attrLength) {
int i;
struct node * tmp;

    tmp = (struct node *)malloc(sizeof(struct node)+\
                                degree*sizeof(struct item));
    for(i=0;i<degree;i++) {
        tmp->matrix[i].node = tmp;
        tmp->matrix[i].key = (struct keytag*)\
            malloc(sizeof(struct keytag)+\
                   attrLength*sizeof(char));
        tmp->matrix[i].key->attrLength = attrLength;
    }

    return tmp;
}

And so on.
0

Featured Post

ScreenConnect 6.0 Free Trial

Check out the updates in one game-changing release, ScreenConnect 6.0, based on partner feedback. New features include a redesigned UI that improves session organization and overall user experience. See the enhancements for yourself!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
In desperate need of help 8 132
Compile VxWorks Toronado project under Visual Studio 11 181
cURL: stopping a http transaction before it's finished 3 116
negation in C function 14 144
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

895 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now