Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Solved

Posted on 1997-05-31

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)

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,att

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,att

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)

9 Comments

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

}

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=attrLeng

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

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

.luc.

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(<t

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

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.

typedef ROOT_NODE *ROOT_NODEPTR;

and reduce all the pointer stuff

gosh...see less stars then

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->attrLe

}

return tmp;

}

And so on.

Question has a verified solution.

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

Course of the Month19 days, 1 hour left to enroll

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