CODEWITHSUNDEEP
cstructmallocrecursive-datastructures
kh4r4
kh4r4

Reputation: 65

Recursive struct and malloc()

I have a recursive struct which is:

typedef struct dict dict;
struct dict {
    dict *children[M];
    list *words[M];
};

Initialized this way:

dict *d = malloc(sizeof(dict));
bzero(d, sizeof(dict));

I would like to know what bzero() exactly does here, and how can I malloc() recursively for children.

Edit: This is how I would like to be able to malloc() the children and words:

void dict_insert(dict *d, char *signature, unsigned int current_letter, char *w) {
    int occur;
    occur = (int) signature[current_letter];
    if (current_letter == LAST_LETTER) {
        printf("word found : %s!\n",w);
        list_print(d->words[occur]);
        char *new;
        new = malloc(strlen(w) + 1);
        strcpy(new, w);
        list_append(d->words[occur],new);
        list_print(d->words[occur]);
    }
    else {
        d = d->children[occur];
        dict_insert(d,signature,current_letter+1,w);
    }
}

Upvotes: 1

Views: 2016

Answers (3)

Randall Cook
Randall Cook

Reputation: 6776

In general, when you are unsure what the compiler is generating for you, it is a good idea to use a printf to report the size of the struct. In this case, the size of dict should be 2 * M * the size of a pointer. In this case, bzero will fill a dict with zeros. In other words, all M elements of the children and words arrays will be zero.

To initialize the structure, I recommend creating a function that takes a pointer to a dict and mallocs each child and then calls itself to initialize it:

void init_dict(dict* d)
{
    int i;
    for (i = 0; i < M; i++)
    {
        d->children[i] = malloc(sizeof(dict));
        init_dict(d->children[i]);

        /* initialize the words elements, too */
    }
}

+1 to you if you can see why this code won't work as is. (Hint: it has an infinite recursion bug and needs a rule that tells it how deep the children tree needs to be so it can stop recursing.)

Upvotes: 1

Jerry Coffin
Jerry Coffin

Reputation: 490408

bzero just zeros the memory. bzero(addr, size) is essentially equivalent to memset(addr, 0, size). As to why you'd use it, from what I've seen around half the time it's used, it's just because somebody though zeroing the memory seemed like a good idea, even though it didn't really accomplish anything. In this case, it looks like the effect would be to set some pointers to NULL (though it's not entirely portable for that purpose).

To allocate recursively, you'd basically just keep track of a current depth, and allocate child nodes until you reached the desired depth. Code something on this order would do the job:

void alloc_tree(dict **root, size_t depth) { 
    int i;
    if (depth == 0) {
        (*root) = NULL;
        return;
    }

    (*root) = malloc(sizeof(**root));

    for (i=0; i<M; i++)
        alloc_tree((*root)->children+i, depth-1);       
}

I should add that I can't quite imagine doing recursive allocation like this though. In a typical case, you insert data, and allocate new nodes as needed to hold the data. The exact details of that will vary depending on whether (and if so how) you're keeping the tree balanced. For a multi-way tree like this, it's fairly common to use some B-tree variant, in which case the code I've given above won't normally apply at all -- with a B-tree, you fill a node, and when it's reached its limit, you split it in half and promote the middle item to the parent node. You allocate a new node when this reaches the top of the tree, and the root node is already full.

Upvotes: 1

Adam Rosenfield
Adam Rosenfield

Reputation: 400512

bzero(3) initializes the memory to zero. It's equivalent to calling memset(3) with a second parameter of 0. In this case, it initializes all of the member variables to null pointers. bzero is considered deprecated, so you should replace uses of it with memset; alternatively, you can just call calloc(3) instead of malloc, which automatically zeroes out the returned memory for you upon success.

You should not use either of the two casts you have written—in C, a void* pointer can be implicitly cast to any other pointer type, and any pointer type can be implicitly cast to void*. malloc returns a void*, so you can just assign it to your dict *d variable without a cast. Similarly, the first parameter of bzero is a void*, so you can just pass it your d variable directly without a cast.

To understand recursion, you must first understand recursion. Make sure you have an appropriate base case if you want to avoid allocating memory infinitely.

Upvotes: 2

Related Questions