Dynamically growing array of strings

Hi bbcac,

The malloc() statement that you've crafted with return a single block that isn't really useful to the *lines[] definition.  It is reserving space for 88 * (rowcount-1) pointers, not an arbitrary number of strings 88 characters long.

*lines[] expects a buffer of size (elements * sizeof (char*)).  lines[x] contains a pointer to a string.  If you want to populate the buffer yourself, you'll need to do this:

  lines = (char **)malloc (number of items in lines[] * sizeof (char **));
  for (idx = 0; idx < number of items in lines[]; ++idx)
    lines[idx] = (char  *)malloc (length of a line, presumably 88);


Kent

what about making lines grow with each iteration?

lines = (char **)malloc (number of items in lines[] * sizeof (char **)); <--- this line doesnt' work... it says that there is not linkage to line.

I changed the decleration of the line array as suck

char *line[] = {""};


Then the error that i get says that lines is not an LValue

>> lines = (char **)malloc (number of items in lines[] * sizeof (char **));

That was meant to be pseudo-code.   :)

How many items do you need in the array for the first result set?  Assuming 50 (for example) an array large enough for a single return is generated like this:

  lines = (char **) malloc (50 * sizeof (char*));

50 becomes ((row_count - 1) * 50) if you want to return multiple sets.

Are all the lines going to be the same size?  How do you expect to control the growth of each line?


Kent

essentially the size of the row will never be more than 88 ( the width of the screen)
For each row in the result set (there is only one result set), I need to make the array 1 item (a string of 88 chars) larger

I realized that your line was meant to be pseudo-code and I changed it as such


If all I have in the function is the following, then i get an error that says there is no linkage


int process_poker_lotto_prog(DBPROCESS * lams_dbproc, struct PRODINFO pi)
{

   char         *line[];
   int          row_count = -1;
   int return_code;
   
   line = (char **) malloc (0 * sizeof (char **));
   

   return TRUE;
}

"no linkage"?  Weird.....

Can you post the entire error message?

This is the code:
int function ()
{
   char         *line[];
   line = (char **) malloc (0 * sizeof (char **));
   
   printf("\nstarting\n");

   return TRUE;
}

Here is the exact error

   char         *line[];
................^
%CC-E-INCOMPNOLINK, In this declaration, "line" has no linkage and is of
an incomplete type.

How about using:
http://developer.gnome.org/doc/API/2.0/glib/glib-Pointer-Arrays.html 
?
Regards
Friedrich

Hi bbcac,

A linked list may be a more useful structure to use.

Paul

It's difficult to guess exactly what you're trying to do, but I think incrementing the table size by a fixed amount will make your program much more efficient - reallocating for each entry will cause serious memory fragmentation. I think you're trying to do somethign like:



#define INCREMENT 512                  /* Increment size when you're reallocating the table */
#define MAXIMUM_LENGTH 1024     /* This is the max length of the buffer in which you're formatting your text */


   char **lines;
   int row_count = -1;
   int max_rows = INCREMENT;
   int return_code;
   char wrkBuffer[MAXIMUM_LENGTH]; /* Formatting area */
   
   lines = (char **) malloc(max_rows * sizeof(char *)); /* Initial size = 512 */

   /** Runs a database query that works fine here ***/
   
   while (RESULTS_REMAIN())
   {
         /** BIND RESULTS TO VARIABLES: Working ***/
        while (ROWS_REMAIN())
        {
           if (++row_count >= max_rows) { /* If the table is full, allocate another bunch of pointers */
              max_rows += INCREMENT;
              lines = realloc(lines, max_rows * sizeof(char *));
           }
           sprintf (wrkBuffer , "    %-20s$%-23s%s",pok_prg_date, prize, city);
           lines[row_count] = malloc((strlen(wrkBuffer) + 1) * sizeof(char)); /* This is where you allocate the size */
           strcpy(lines[row_count], wrkBuffer);
               
        }
   }

You have two issues:  (1) you need a growable array of string pointers, and (2) You need growable strings.

for problem (1) you need code something like:

int GrowAmount = 10;  int Used = 0;

char ** ArrayOfPtrs;

void Init() {
ArrayOfPtrs = malloc( GrowAmount * sizeof( char * ) );
for( i = 0; i < GrowAmount; i++ ) ArrayOfPtr[ i ] = NULL:
}


void Grow() {  char ** NewArrayOfPtrs ;  int OldSize;
OldSize = GrowAmount;
GrowAmount *= 2;

NewArrayOfPtrs = malloc( GrowAmount * sizeof( char * ) );
for( i = 0; i < OldSize; i++ ) NewArrayOfPtrs [ i ] = ArrayOfPtrs [ i ]:
for( i = OldSize; i < GrowAmount; i++ ) NewArrayOfPtrs [ i ] = NULL:

free( ArrayOfPtrs  );   ArrayOfPtrs  = NewArrayOfPtrs [ i ];

}

for step (2), you jsut malloc string ptrs into the array.

so my question is, if i have a loop how would I implment that code?

For example here is some simple pseudo

declare array of string pointers here

Loop (results_remain)
{
    -Increase the size of the string pointer array
    -assign the new position the value of "a String"
}

Pretty easily, actually.   :)

GrowAmount is the current size of the pointer array.  And since this implementation doubles the size of the array every time it needs to grow, it's also the current size.  (Doubling the size is a performance boon as simple increasing the array by say 10 items can make for a lot of calls to Grow().)

  /*  Need to insert pointer NewPointer into the table  */

  if (Used+1 >= GrowAmount)
    Grow ();
  ArrayOfPtrs[Used++] = NewPointer;


Kent

Wow.  That was a pretty bad sentence.  (Note to self -- PROOFREAD!!!!!)

GrowAmount is the current size of the pointer array AND the amount by which it will grow since this implementation doubles the array's size every time it grows.

whew....   :)

I can't get it to work... Here is the exact function.. perhaps you could implment it in here?
int process_results(DBPROCESS * dbproc, struct PRODINFO pi)
{

   DBCHAR       *result_attribute = "";

   char         *wins[100]= {''};


   int return_code;
   
   /*** Run Stored Proc Here ***/

   dbcancel( dbproc );
   
   dbfcmd( dbproc, "  EXECUTE DB..MYSTOREDPROC '%s', '%s'  ",  
             date, date );

   if ((return_code = dbsqlexec(dbproc)) != SUCCEED)
         return(FALSE);
   
   while ((result_sets_remain())
   {
       bind_to_vars();      
         
        while (dbnextrow(dbproc) != NO_MORE_ROWS)
        {
            /** Increase size of array **/
            /** add result_attribute string to this position **/
        }
   }

   
   return TRUE;
}

Actually - you don't need MAXIMUM_LENGTH, so you can delete that line.

To be simpler and more efficient, I would recommend a linked list which grows up on the lines it read of variable length. Each node (of list) would have a char* to hold a line/row and a linking pointer to point the next node in the list.  

I am not that fond of realloc() and I dont recommend it for a better performance. It does not only slow down the process and also creates of lots of memory fragmentation.

Check the following example I wrote for you.  Similar to reading data from database for your program, the example reads the lines from stdin and puts the read lines of variable-length into a list and keeps adding as it grows.  Once the data has been read and list is created successfully, it will print out the lines it added.

Check it out how it works for you after you can tailor it to your purpose.
I tested the program reading a file from online, like

C:\> myRowList  < myRowList.c  

It read its own code and generated a list successfully.

Good luck :)


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

typedef struct Row {
      char *row;
      struct Row *next;
} Row;


int addRow(Row **lRow, char *line)
{
      
      Row *newRow = NULL;
      Row *list;

      /* create a new data row to be added to the list */
      newRow = (struct Row *) malloc(sizeof(struct Row));
      if (newRow == NULL) {  /* failed to allocate memory */
            printf("\nMemory error occured");
            return -1;
      }
      /* allocate enough memory for the line to be copied */
      newRow->row = (char *) malloc(sizeof(char) * (strlen(line) + 1)); /* +1 is for null terminator */
      /* copy the line now */
      strcpy(newRow->row, line);
      newRow->next = NULL;
      
      /* if List is empty */
      if (*lRow == NULL)       {
            *lRow = newRow;
            return 1;
      }


      /* if list was already created, bring the storing point to the end and append the new one */
      list = *lRow;
      while (list->next) {
            list = list->next;
      }

      /* now add the new one */
      list->next = newRow;

      return 1;

}

void listRow(Row *lRow)
{
      if (lRow == NULL)
      {
            printf("\nList is empty ");
            return;
      }


      /* fetch the rows from list and print them out */
      while (lRow) {
            printf("%s",lRow->row);
            lRow = lRow->next;
      }

}

void destroyRow(Row *list)
{
      if (list == NULL)
            return;

      /* call the function to destroy the list recursively */
      destroyRow(list->next);
}


                  

void main()
{
      
      Row *myRowList = NULL;
      char line[128];

      /* add the lines to the list as you need/fetch from database/file */
      while(  fgets(line, 128, stdin) )
      {
            addRow(&myRowList,line);
      }

      /* display the lines you stored in the list */
      listRow(myRowList);

      /* finally release the memory you held for the list */
      destroyRow(myRowList);

      return;
}

Sorry, I missed a couple lines for releasing the memory in destroyRow() function. The revised function should look like:

void destroyRow(Row *list)
{
      if (list == NULL)
            return;

      /* call the function to destroy the list recursively */
      destroyRow(list->next);
      
      /* release the memory held for char* and row node */
      free(list->row);
      free(list);
}


Good luck :)

Hi bbcac,

Just a couple of points I would like to add to SJT's excellent work.

1. A recursive destructor, although cute, would never be a good choice.

2. Much efficiency could be gained by retaining a pointer to the last entry added to the list.

Please SJT, do not take this as criticism.

Paul

Paul: Not taking it as a criticism, but for discussion sake,

>>Much efficiency could be gained by retaining a pointer to the last entry added to the list.

Unless you have two pointers enabling you move back and forth in the list, you can not release a node even if you retains the last node/pointer, hence I wrote it as a recursive.
When bit careful, the recursive always works for any dynamic lists/trees and it is faster.

In the above example, with a single linking pointer, I would rather go for recursive. You have any thing better in mind, please advise, at least it will show me there is some thing better :)

And the example, as it has no fixed size row / character string, I say, for a dynamically growing list, a linked list is a good (say, better) option. The basic input line length is given of a max size, say 128, but can be increased.

Check it out :)

>>Not taking it as a criticism, but for discussion sake,
Excellent! I love a good technique discussion.

On the 'Much efficiency could be gained ...' point I was referring to the

    list = *lRow;
     while (list->next) {
          list = list->next;
     }

code. If you retain a pointer to the last node added at the end of the tree then you never have to walk the tree while adding. I would use something like:

typedef struct List {
     struct Row * head;
     struct Row * tail;
} Row;

and the obvious uses of this.

On the Destructor,

void destroyRow(Row *list)
{
     if (list == NULL)
          return;

     /* call the function to destroy the list recursively */
     destroyRow(list->next);
     
     /* release the memory held for char* and row node */
     free(list->row);
     free(list);
}

could be coded more safely as:

void destroyList(Row *list)
{
     while (list != NULL)
     {
       Row * kill = list;
       list = list->next;

       /* release the memory held for char* and row node */
       if ( kill->row != NULL ) free(kill->row);
       free(kill);
     }
}

This will make no reliance at all on stack size and will therefore be more portable and stable. It may even be more efficient as hardware cacheing would not have to deal with stack access. Think big, if there were 10,000,000 entries in your list the recursive solution would almost certainly blow chunks while the looped destructor would not be effected at all.

I am a great believer in making the algorithm fit the structure. Tree destructors are often best recursive because a tree is recursive in structure wile lists are linear and lend themselves to loops more cleanly.

Paul

I hope this isn't OTT but there's another argument over the recursive/loop destructor issue.

If I was offered two algorithms from two of my staff with the following properties:

Algorithm 1

a) Will always function correctly if the list is well-structured.

Algorithm 2

a) Will always function correctly if the list is well-structured.
b) Will always function correctly if the stack is sufficiently large.

I think I would choose Algorithm 1 any day so long as the efficiency of 2 does not significantly rebalance the choice. In my opinion in this case Algorithm 1 may even be slightly more efficient.

Paul

I agree, it would blow off if the list is too big and the recursive destructor would add too much overhead on stack. In that case (of too heavy list), I would not use a recursive function and I would rather go removing the list from top-bottom (as you suggested) instead of bottom-up (as in recursive).

As you stated in your example, it stores the current node/pointer in a temp copy and frees the current node and move onto next using other copy. Yes it works, avoiding a recursive, but I don't see a need to create a another structure storing head and tail pointers (however, it is developer's convenience/choice) to note down the beginning and ending points of list.

When it comes to efficiency, the list works perfectly alright, and is a simple list storing the lines and removing the row nodes safely.

Good luck :)

Try the List structure one day. It's a small step towards the encapsulation you get from the C++ List objects and you may be a little surprised at how much tidier the code can then be written.

Paul