dynamic expansion of multi-dimensional arrays (or array of pointers)

**cfanatic** · 10-23-2012

Hi all.

The code works as expected(display words starting with brown). What if I don't know in advance how many words of this type a document contains? How can I dynamically increase the size of a multi-dimensional array, or an array of pointers? Is there a function in the C library that can do this?

Thanks in advance.

test.txt

Code:

How now "brownone" cow. A cow has four "browntwo" legs.

output

Code:

brownone
browntwo

Code:

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

#define DOCUMENT_LENGTH 100

int main(void)
{
    char *loc, *search_string = "brown";
    char buffer[DOCUMENT_LENGTH], string[2][10];
    char temp[DOCUMENT_LENGTH];
    FILE *file;
    int bufferctr, ctr1 = 0, ctr2 = 0, ch, ctr;

    if((file = fopen("test.txt", "r")) == NULL)
    {
        perror("Error");
        exit(EXIT_FAILURE);
    }
    if(fgets(buffer, DOCUMENT_LENGTH, file) == NULL)
    {
        perror("Error");
        exit(EXIT_FAILURE);
    }
    while((loc = strstr(buffer, search_string)) != NULL)
    {
        bufferctr = loc - buffer;
        while((ch = buffer[bufferctr]) != '"')
        {
            string[ctr1][ctr2] = ch;
            ctr2++;
            bufferctr++;
        }
        string[ctr1][ctr2] = '\0';
        bufferctr++;
        strcpy(temp, &buffer[bufferctr]); // temp needed because strcpy(buffer, &buffer[buffer[ctr]) overlap
        strcpy(buffer, temp);
        ctr1++;
        ctr2 = 0; // reset
        bufferctr = 0; // reset
    }
    for(ctr = 0; ctr < 2; ctr++)
    {
        printf("%s\n", string[ctr]);
    }

    return 0;
}

**std10093** · 10-23-2012

Hello cfanatic!!! I would suggest these functions for dynamic allocations of memory malloc and realloc .I would say that you are asking for the first one, malloc

I think the link explains it good and have a nice example

**qny** · 10-23-2012

In C, after you define an array

Code:

char words[100][50]; /* capacity for 100 words of up to 49 characters each */

you cannot change its capacity.

One "solution" is to reserve space for enough members, but this is bad if enough members are too many members or if the data is rarely that big. In the first situation the "solution" doesn't work; in the second situation the "solution" wastes memory.

The proper solution is to use dynamic memory allocation. You use pointers instead of arrays (luckily, in C, usage of pointers and arrays is very similar) and allocate memory with malloc(), calloc(), or realloc() (Don't forget to release the memory when you are finished using it, with free()).

You might like to read sections 4, 5, 6, and 7 (and all the others) of the comp.lang.c FAQ.

**std10093** · 10-23-2012

Originally Posted by qny

calloc(), or realloc() (Don't forget to release the memory when you are finished using it, with free()).

You might like to read sections 4, 5, 6, and 7 (and all the others) of the comp.lang.c FAQ.

Good statement about free.Always de-allocate your memory when you do not need it.Why?Imagine that you have a function that allocates memory in every call and does not free the memory(which might be useful if you need this memory to be accessible by the rest of your code).Every call allocates blocks of memory.Memory is big ,but not infinite.So let's say you do not need what you allocated after the function terminates.Then you keep memory blocks allocated and after many calls of the function in a large program for example,you will run out of memory.You do not want this to happen.If this happens malloc will return an NULL pointer.

As for calloc i did not reference it because of this Is it better to use malloc or calloc to allocate memory
Also before some other user suggests you alloca, read this c - Why is alloca not considered good practice? - Stack Overflow
In other words,use malloc for usual code!

**cfanatic** · 10-23-2012

I don't have access to a compiler at the moment, but I have changed the code so that you can get a rough idea of what I want to do.

In the while loop, how would I be able to generate a new char pointer for every iteration? A new pointer for every new matching string(starting with "brown").

Basically, I would like something like:

Code:

stringx = malloc(10);

where x(I don't know x in advance) keeps increasing with every iteration. And then later on I can use a for loop to print all the pointers.

Code:

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

#define DOCUMENT_LENGTH 100

int main(void)
{
    char *loc, *search_string = "brown";
    char buffer[DOCUMENT_LENGTH], *string;
    char temp[DOCUMENT_LENGTH];
    FILE *file;
    int bufferctr, ctr1 = 0, ch, ctr;

    if((file = fopen("test.txt", "r")) == NULL)
    {
        perror("Error");
        exit(EXIT_FAILURE);
    }
    if(fgets(buffer, DOCUMENT_LENGTH, file) == NULL)
    {
        perror("Error");
        exit(EXIT_FAILURE);
    }
    while((loc = strstr(buffer, search_string)) != NULL)
    {
        bufferctr = loc - buffer;
        while((ch = buffer[bufferctr]) != '"')
        {
            string = malloc(10);
            string[ctr1] = ch;
            ctr1++;
            bufferctr++;
        }
        string[ctr1] = '\0';
        bufferctr++;
        strcpy(temp, &buffer[bufferctr]); // temp needed because strcpy(buffer, &buffer[buffer[ctr]) overlap
        strcpy(buffer, temp);
        // need new char pointer here
        ctr1 = 0; // reset
        bufferctr = 0; // reset
    }
    
    return 0;
}

**std10093** · 10-23-2012

I do not see where ctr is used.Maybe you do not need it?

Maybe you misunderstood something.Malloc will not generate new pointers that do not exist into your code.You supply for what the malloc returns a pointer that is already declared in your code.I thought that what you needed is an array of char pointers==double pointer char

**cfanatic** · 10-23-2012

Originally Posted by std10093

Malloc will not generate new pointers that do not exist into your code.You supply for what the malloc returns a pointer that is already declared in your code.

Yes, this is the problem that I am having. I know how to use malloc, and I know that a pointer needs to be declared before malloc can be used. But how do I declare a new different pointer for every iteration of the while loop?

At the top, I can't keep declaring *char *string, *string1, *string2 forever. And even if I could, how would I increment the pointer in the while loop?

**std10093** · 10-23-2012

I do not if this is a good ,or even more, an implementable idea.Let me give you an idea,not ideal and not efficient but i think it will be a good lesson for how malloc works

Maybe a combination of malloc and realloc is the answer here.Declare an array of char pointers.Give it a logical size for start,that is going to be filled up for 80% at least in all cases(i mean for every data that the .txt file has).Every cell will host a string that is found at every loop.The memory for this string should be allocated by you,with malloc!
When the array fills up,use realloc to increase it's size by say 50% of the size,or even smarter think a way that will be analogous to the point of file that you are know in order to make the minimum increments of size,which of course is costly(if you would like i can explain why

).For example if you are two lines before EOF it wouldn't be so smart to increase the size of the array with the same factor you did when you were at the 1/6 of the file for example.Well you could first implement it with increasing size always by 50% and then do it more efficiently.
Then ,when you are done ,this array will hold in every cell the strings you found.Every cell will have a pointer that will point to a string.Remember that this space for the strings has to be allocated by you with malloc.

Then when you are done you have to free your memory.Do not do the same mistake to just free the array(which you can have allocated with realloc).First free the memory that you allocated for every string and then free the array.Do these operations as i said and not in reverse,because if you first free the array then you won't have access to the where the strings are!

PS- yes i know these is challenging and has a factor of difficulty

**std10093** · 10-23-2012

Originally Posted by cfanatic

Code:

...
int main(void)
{
    ...
    int bufferctr, ctr1 = 0, ch, ctr;
  
   .....

ctr here i think you do not use it.Maybe you do not need or you will use it in future

**cfanatic** · 10-23-2012

Originally Posted by std10093

I do not if this is a good ,or even more, an implementable idea.Let me give you an idea,not ideal and not efficient but i think it will be a good lesson for how malloc works

Maybe a combination of malloc and realloc is the answer here.Declare an array of char pointers.Give it a logical size for start,that is going to be filled up for 80% at least in all cases(i mean for every data that the .txt file has).Every cell will host a string that is found at every loop.The memory for this string should be allocated by you,with malloc!
When the array fills up,use realloc to increase it's size by say 50% of the size,or even smarter think a way that will be analogous to the point of file that you are know in order to make the minimum increments of size,which of course is costly(if you would like i can explain why

).For example if you are two lines before EOF it wouldn't be so smart to increase the size of the array with the same factor you did when you were at the 1/6 of the file for example.Well you could first implement it with increasing size always by 50% and then do it more efficiently.
Then ,when you are done ,this array will hold in every cell the strings you found.Every cell will have a pointer that will point to a string.Remember that this space for the strings has to be allocated by you with malloc.

Then when you are done you have to free your memory.Do not do the same mistake to just free the array(which you can have allocated with realloc).First free the memory that you allocated for every string and then free the array.Do these operations as i said and not in reverse,because if you first free the array then you won't have access to the where the strings are!

PS- yes i know these is challenging and has a factor of difficulty

Thanks, I will give this a go.

**std10093** · 10-23-2012

Originally Posted by cfanatic

Thanks, I will give this a go.

I am not sure.Maybe we should think twice before we act

In my first programming class,we had some projects to do.We had a description of the problem and what the program should do or simulate.I remember clearly that in every assignment i would ask this to myself when i had choose how i would go for memory management.To i know the number of things that i am going to save or not?If yes use an array,if not use a list.A beautiful and elegant simple linked list.Now we do not know how many strings we are going to store.
Do not get confused with the case that the user inputs the number of things that are going to be stored.There you know how many things are going to be saved.Of course you do not know what the user will input, so what you know is that (let's say you have declared an int n variable) that n things are going to be stored.In this case you know the size of the array.It is n.In this case you are dealing with we do not know the size of the array.
When i was at my very first class of programming i had a question.This was inspired by the fact that first we learned to use arrays and then lists.So i had learned and used in code arrays where list was only on the book.We used list when we didn't know how many things are going to be saved.Every time you have a new thing to save,you insert a node to the list and there you put the new thing to be stored.So my question was why not use realloc?We could use arrays that were more easy to use(you do not had to write an insert function for example) and when the array was fulled you would increase it's size and that's all.
So big was that question to my mind that i decided to ask at the official programming forum of the university.So an excellent professor, mr. Stamatopoulos from DIT,answered me when you realloc an array ,because this is our case, from your point of you ,you just add after the last cell more cells.From the point of view of the system,it will not just go after the last cell and allocate some other cells too after it.Of course ,as you know, array cells are stores adjacent in memory,one after the other.
For example you have an array of 1000000 elements,stored in adjacent memory cells,and right after the lass cell of memory that is allocated for your array,the memory is not available - it is allocated for some variable,some array of the same or different program or whatever).Let's say you want to enlarge this array with ten more elements,then realloc will copy the initial array to another block of memory where at least 1000010 memory cells are available for you.However, the procedure of copying 1000000 elements is very very costly.And if you do this realloc's often then you have a problem.
Let alone the fact,that it very likely that there are no so many adjacent memory cells available for you ,so realloc will return NULL and set error code to ENOMEM.However the list,which it's nodes are not stored in adjacent memory cells will find memory cells to go and store the new element to be stored.Well if it can find available memory , then the problem does not lie to the decision to use realloc or lists!
So the result ,is that using a list is more efficient.As a result i had the idea that lists have conquered the world and realloc is dead!And of course i said that to the forum.And one TA said that everything is used where it should be used.No more details were given to me in order not to confuse me.
Now i know why.With lists you have these issues

hardware prefetching not available
much more cache misses
there are some dependencies that cause CPU pipelining stall

This has to do with performance.For simple code like that you are writing,list is just fine

Of course there are some mixed implementations,where every node of the list has an array for example 1000 cells.So you amortize the cost of accessing the elements with good performance.This is called "vectorization".

PS- i thought of this post while eating my burnt -literally the bread had got black

- toasts.The toasts were burnt because of post number 8 and 9 i made before.So i thought i should post my idea.Sorry for the long post

Hope this helps!!!

**cfanatic** · 10-23-2012

So I should use a list? Ok, I'll give that a go.

Your long posts are always good reading.

**std10093** · 10-24-2012

Originally Posted by cfanatic

So I should use a list? Ok, I'll give that a go.

Your long posts are always good reading.

Yes this is what i am suggesting

Of course if you have problems post back :-) I will more than glad to help you.

Thank you for reading all this :-D

Thread: dynamic expansion of multi-dimensional arrays (or array of pointers)

Thread Tools

Search Thread

Display

dynamic expansion of multi-dimensional arrays (or array of pointers)

Similar Threads

Dynamic, multi-dimensional pointers!

Multi-dimensional Dynamic Arrays

Pointers to multi dimensional arrays.

Array pointers to Multi-Dimensional Arrays

Hello all and pointers to multi-dimensional arrays