Like Tree7Likes
  • 1 Post By std10093
  • 1 Post By qny
  • 1 Post By std10093
  • 1 Post By std10093
  • 1 Post By std10093
  • 1 Post By std10093
  • 1 Post By std10093

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

This is a discussion on dynamic expansion of multi-dimensional arrays (or array of pointers) within the C Programming forums, part of the General Programming Boards category; Hi all. The code works as expected(display words starting with brown). What if I don't know in advance how many ...

  1. #1
    Registered User
    Join Date
    Jul 2012
    Location
    Australia
    Posts
    242

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

    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;
    }
    IDE: Code::Blocks | Compiler Suite for Windows: TDM-GCC (MingW, gdb)

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    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
    cfanatic likes this.

  3. #3
    qny
    qny is offline
    Registered User
    Join Date
    Sep 2012
    Posts
    355
    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.
    cfanatic likes this.

  4. #4
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    Quote Originally Posted by qny View Post

    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 likes this.

  5. #5
    Registered User
    Join Date
    Jul 2012
    Location
    Australia
    Posts
    242
    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;
    }
    IDE: Code::Blocks | Compiler Suite for Windows: TDM-GCC (MingW, gdb)

  6. #6
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    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

  7. #7
    Registered User
    Join Date
    Jul 2012
    Location
    Australia
    Posts
    242
    Quote Originally Posted by std10093 View Post
    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?
    IDE: Code::Blocks | Compiler Suite for Windows: TDM-GCC (MingW, gdb)

  8. #8
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    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
    cfanatic likes this.

  9. #9
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    Quote Originally Posted by cfanatic View Post
    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 likes this.

  10. #10
    Registered User
    Join Date
    Jul 2012
    Location
    Australia
    Posts
    242
    Quote Originally Posted by std10093 View Post
    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.
    IDE: Code::Blocks | Compiler Suite for Windows: TDM-GCC (MingW, gdb)

  11. #11
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    Quote Originally Posted by cfanatic View Post
    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 likes this.

  12. #12
    Registered User
    Join Date
    Jul 2012
    Location
    Australia
    Posts
    242
    So I should use a list? Ok, I'll give that a go.

    Your long posts are always good reading.
    IDE: Code::Blocks | Compiler Suite for Windows: TDM-GCC (MingW, gdb)

  13. #13
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,681
    Quote Originally Posted by cfanatic View Post
    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
    cfanatic likes this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dynamic, multi-dimensional pointers!
    By Lionmane in forum C Programming
    Replies: 16
    Last Post: 07-07-2005, 01:43 AM
  2. Multi-dimensional Dynamic Arrays
    By Quasar in forum C++ Programming
    Replies: 2
    Last Post: 06-11-2004, 06:48 AM
  3. Pointers to multi dimensional arrays.
    By bartybasher in forum C++ Programming
    Replies: 2
    Last Post: 08-25-2003, 02:41 PM
  4. Array pointers to Multi-Dimensional Arrays
    By MethodMan in forum C Programming
    Replies: 3
    Last Post: 03-18-2003, 08:53 PM
  5. Hello all and pointers to multi-dimensional arrays
    By Mario in forum C++ Programming
    Replies: 16
    Last Post: 05-17-2002, 08:05 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21