C dynamically growing array

Question

I have a program that reads a  raw  list of in-game entities  and I intend to make an array holding an index number  int  of an indeterminate number of entities  for processing various things  I would like to avoid using too much memory or CPU for keeping such indexes     A quick and dirty solution I use so far is to declare  in the main processing function  local focus  the array with a size of the maximum game entities  and another integer to keep track of how many have been added to the list  This isn t satisfactory  as every list holds 3000  arrays  which isn t that much  but feels like a waste  since I ll possible use the solution for 6-7 lists for varying functions   I haven t found any C  not C   or C   specific solutions to achieve this  I can use pointers  but I am a bit afraid of using them  unless it s the only possible way    The arrays do not leave the local function scope  they are to be passed to a function  then discarded   in case that changes things   If pointers are the only solution  how can I keep track of them to avoid leaks

User · Answer

These posts apparently are in the wrong order! This is #3 in a series of 3 posts. Sorry.

I've "taken a few MORE liberties" with Lie Ryan's code. The linked list admittedly was time-consuming to access individual elements due to search overhead, i.e. walking down the list until you find the right element. I have now cured this by maintaining an address vector containing subscripts 0 through whatever paired with memory addresses. This works because the address vector is allocated all-at-once, thus contiguous in memory. Since the linked-list is no longer required, I've ripped out its associated code and structure.

This approach is not quite as efficient as a plain-and-simple static array would be, but at least you don't have to "walk the list" searching for the proper item. You can now access the elements by using a subscript. To enable this, I have had to add code to handle cases where elements are removed and the "actual" subscripts wouldn't be reflected in the pointer vector's subscripts. This may or may not be important to users. For me, it IS important, so I've made re-numbering of subscripts optional. If renumbering is not used, program flow goes to a dummy "missing" element which returns an error code, which users can choose to ignore or to act on as required.

From here, I'd advise users to code the "elements" portion to fit their needs and make sure that it runs correctly. If your added elements are arrays, carefully code subroutines to access them, seeing as how there's extra array structure that wasn't needed with static arrays. Enjoy!

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


// Code from https://stackoverflow.com/questions/3536153/c-dynamically-growing-array
// For pointer-to-pointer info see:
// https://stackoverflow.com/questions/897366/how-do-pointer-to-pointers-work-in-c-and-when-might-you-use-them
typedef struct STRUCT_SS_VECTOR
{   size_t size; // # of vector elements
    void** items; // makes up one vector element's component contents
    int subscript; // this element's subscript nmbr, 0 thru whatever
 //   struct STRUCT_SS_VECTOR* this_element; // linked list via this ptr
 //   struct STRUCT_SS_VECTOR* next_element; // and next ptr
} ss_vector;

ss_vector* vector; // ptr to vector of components
ss_vector* missing_element(int subscript) // intercepts missing elements
{   printf("missing element at subscript %i\n",subscript);
    return NULL;
}

typedef struct TRACKER_VECTOR
{   int subscript;
    ss_vector* vector_ptr;
} tracker_vector;  // up to 20 or so, max suggested

tracker_vector* tracker;
int max_tracker=0; // max allowable # of elements in "tracker_vector"
int tracker_count=0; // current # of elements in "tracker_vector"
int tracker_increment=5; // # of elements to add at each expansion

void bump_tracker_vector(int new_tracker_count)
{   //init or lengthen tracker vector
    if(max_tracker==0) // not yet initialized
    { tracker=calloc(tracker_increment, sizeof(tracker_vector));
        max_tracker=tracker_increment;
printf("initialized %i-element tracker vector of size %lu at %lu\n",max_tracker,sizeof(tracker_vector),(size_t)tracker);
        tracker_count++;
        return;
    }
    else if (max_tracker<=tracker_count) // append to existing tracker vector by writing a new one, copying old one
    {   tracker_vector* temp_tracker=calloc(max_tracker+tracker_increment,sizeof(tracker_vector));  
        for(int i=0;(i<max_tracker);i++){   temp_tracker[i]=tracker[i];} // copy old tracker to new
        max_tracker=max_tracker+tracker_increment;
        free(tracker);
        tracker=temp_tracker;
printf("  re-initialized %i-element tracker vector of size %lu at %lu\n",max_tracker,sizeof(tracker_vector),(size_t)tracker);
        tracker_count++;
        return;
    } // else if
    // fall through for most "bumps"
    tracker_count++;
    return;
}  // bump_tracker_vector()

ss_vector* ss_init_vector(size_t item_size) // item_size is size of one array member
{   ss_vector* vector= malloc(sizeof(ss_vector)); 
    vector->size = 0; // initialize count of vector component elements
    vector->items = calloc(1, item_size); // allocate & zero out memory for one linked list element
    vector->subscript=0;
    bump_tracker_vector(0); // init/store the tracker vector
    tracker[0].subscript=0;
    tracker[0].vector_ptr=vector; 
    return vector; //->this_element;
} // ss_init_vector()

ss_vector* ss_vector_append( int i) // ptr to this element, element nmbr
{   ss_vector* local_vec_element=0;
    local_vec_element= calloc(1,sizeof(ss_vector)); // memory for one component
    local_vec_element->subscript=i; //vec_element->size; 
    local_vec_element->size=i; // increment # of vector components
    bump_tracker_vector(i);  // increment/store tracker vector
    tracker[i].subscript=i;
    tracker[i].vector_ptr=local_vec_element; //->this_element;
    return local_vec_element;
}  // ss_vector_append()

void bubble_sort(void)
{   //  bubble sort
    struct TRACKER_VECTOR local_tracker;
    int i=0;
    while(i<tracker_count-1)
    {   if(tracker[i].subscript>tracker[i+1].subscript)
        {   local_tracker.subscript=tracker[i].subscript; // swap tracker elements
            local_tracker.vector_ptr=tracker[i].vector_ptr;
            tracker[i].subscript=tracker[i+1].subscript;
            tracker[i].vector_ptr=tracker[i+1].vector_ptr;
            tracker[i+1].subscript=local_tracker.subscript;
            tracker[i+1].vector_ptr=local_tracker.vector_ptr;
            if(i>0) i--; // step back and go again
        }
        else 
        {   if(i<tracker_count-1) i++;
        }
    } // while()
} // void bubble_sort()

void move_toward_zero(int target_subscript) // toward zero
{   struct TRACKER_VECTOR local_tracker;
    // Target to be moved must range from 1 to max_tracker
    if((target_subscript<1)||(target_subscript>tracker_count)) return; // outside range
    // swap target_subscript ptr and target_subscript-1 ptr
    local_tracker.vector_ptr=tracker[target_subscript].vector_ptr;
    tracker[target_subscript].vector_ptr=tracker[target_subscript-1].vector_ptr;
    tracker[target_subscript-1].vector_ptr=local_tracker.vector_ptr;
}

void renumber_all_subscripts(gboolean arbitrary)
{   // assumes tracker_count has been fixed and tracker[tracker_count+1]has been zeroed out
    if(arbitrary)  // arbitrary renumber, ignoring "true" subscripts
    {   for(int i=0;i<tracker_count;i++) 
        {   tracker[i].subscript=i;}
    }
    else // use "true" subscripts, holes and all
    {   for(int i=0;i<tracker_count;i++) 
        {   if ((size_t)tracker[i].vector_ptr!=0) // renumbering "true" subscript tracker & vector_element
            {   tracker[i].subscript=tracker[i].vector_ptr->subscript;}
            else // renumbering "true" subscript tracker & NULL vector_element
            {   tracker[i].subscript=-1;}
        } // for()
        bubble_sort(); 
    } // if(arbitrary) ELSE
} // renumber_all_subscripts()

void collapse_tracker_higher_elements(int target_subscript)
{   // Fix tracker vector by collapsing higher subscripts toward 0.
    //  Assumes last tracker element entry is discarded.
    int j;
    for(j=target_subscript;(j<tracker_count-1);j++)
    {   tracker[j].subscript=tracker[j+1].subscript;
        tracker[j].vector_ptr=tracker[j+1].vector_ptr;
    }
    // Discard last tracker element and adjust count
    tracker_count--;
    tracker[tracker_count].subscript=0;
    tracker[tracker_count].vector_ptr=(size_t)0;
} // void collapse_tracker_higher_elements()

void ss_vector_free_one_element(int target_subscript, gboolean Keep_subscripts) 
{   // Free requested element contents.
    //      Adjust subscripts if desired; otherwise, mark NULL.
    // ----special case: vector[0]
    if(target_subscript==0) // knock out zeroth element no matter what
    {   free(tracker[0].vector_ptr);} 
    // ----if not zeroth, start looking at other elements
    else if(tracker_count<target_subscript-1)
    {   printf("vector element not found\n");return;}
    // Requested subscript okay. Freeit. 
    else
    {   free(tracker[target_subscript].vector_ptr);} // free element ptr
    // done with removal.
    if(Keep_subscripts) // adjust subscripts if required.
    {   tracker[target_subscript].vector_ptr=missing_element(target_subscript);} // point to "0" vector
    else // NOT keeping subscripts intact, i.e. collapsing/renumbering all subscripts toward zero
    {   collapse_tracker_higher_elements(target_subscript);
        renumber_all_subscripts(TRUE); // gboolean arbitrary means as-is, FALSE means by "true" subscripts
    } // if (target_subscript==0) else
// show the new list
// for(int i=0;i<tracker_count;i++){printf("   remaining element[%i] at %lu\n",tracker[i].subscript,(size_t)tracker[i].vector_ptr);}
} // void ss_vector_free_one_element()

void ss_vector_free_all_elements(void) 
{   // Start at "tracker[0]". Walk the entire list, free each element's contents, 
    //      then free that element, then move to the next one.
    //      Then free the "tracker" vector.
    for(int i=tracker_count;i>=0;i--) 
    {   // Modify your code to free vector element "items" here
        if(tracker[i].subscript>=0) free(tracker[i].vector_ptr);
    }
    free(tracker);
    tracker_count=0;
} // void ss_vector_free_all_elements()

// defining some sort of struct, can be anything really
typedef struct APPLE_STRUCT
{   int id; // one of the data in the component
    int other_id; // etc
    struct APPLE_STRUCT* next_element;
} apple; // description of component

apple* init_apple(int id) // make a single component
{   apple* a; // ptr to component
    a = malloc(sizeof(apple)); // memory for one component
    a->id = id; // populate with data
    a->other_id=id+10;
    a->next_element=NULL;
    // don't mess with aa->last_rec here
    return a; // return pointer to component
}

int return_id_value(int i,apple* aa) // given ptr to component, return single data item
{   printf("was inserted as apple[%i].id = %i     ",i,aa->id);
    return(aa->id);
}

ss_vector* return_address_given_subscript(int i) 
{   return tracker[i].vector_ptr;} 

int Test(void)  // was "main" in the example
{   int i;
    ss_vector* local_vector;
    local_vector=ss_init_vector(sizeof(apple)); // element "0"
    for (i = 1; i < 10; i++) // inserting items "1" thru whatever
    {local_vector=ss_vector_append(i);}   // finished ss_vector_append()
    // list all tracker vector entries
    for(i=0;(i<tracker_count);i++) {printf("tracker element [%i] has address %lu\n",tracker[i].subscript, (size_t)tracker[i].vector_ptr);}
    // ---test search function
    printf("\n NEXT, test search for address given subscript\n");
    local_vector=return_address_given_subscript(5);
printf("finished return_address_given_subscript(5) with vector at %lu\n",(size_t)local_vector);
    local_vector=return_address_given_subscript(0);
printf("finished return_address_given_subscript(0) with vector at %lu\n",(size_t)local_vector);
    local_vector=return_address_given_subscript(9);
printf("finished return_address_given_subscript(9) with vector at %lu\n",(size_t)local_vector);
    // ---test single-element removal
    printf("\nNEXT, test single element removal\n");
    ss_vector_free_one_element(5,TRUE); // keep subscripts; install dummy error element
printf("finished ss_vector_free_one_element(5)\n");
    ss_vector_free_one_element(3,FALSE);
printf("finished ss_vector_free_one_element(3)\n");
    ss_vector_free_one_element(0,FALSE);
    // ---test moving elements
printf("\n Test moving a few elements up\n");
    move_toward_zero(5);
    move_toward_zero(4);
    move_toward_zero(3);
    // show the new list
    printf("New list:\n");
    for(int i=0;i<tracker_count;i++){printf("   %i:element[%i] at %lu\n",i,tracker[i].subscript,(size_t)tracker[i].vector_ptr);}
    // ---plant some bogus subscripts for the next subscript test
    tracker[3].vector_ptr->subscript=7;
    tracker[3].subscript=5;
    tracker[7].vector_ptr->subscript=17;
    tracker[3].subscript=55;
printf("\n RENUMBER to use \"actual\" subscripts\n");   
    renumber_all_subscripts(FALSE);
    printf("Sorted list:\n");
    for(int i=0;i<tracker_count;i++)
    {   if ((size_t)tracker[i].vector_ptr!=0)
        {   printf("   %i:element[%i] or [%i]at %lu\n",i,tracker[i].subscript,tracker[i].vector_ptr->subscript,(size_t)tracker[i].vector_ptr);
        }
        else 
        {   printf("   %i:element[%i] at 0\n",i,tracker[i].subscript);
        }
    }
printf("\nBubble sort to get TRUE order back\n");
    bubble_sort();
    printf("Sorted list:\n");
    for(int i=0;i<tracker_count;i++)
    {   if ((size_t)tracker[i].vector_ptr!=0)
        {printf("   %i:element[%i] or [%i]at %lu\n",i,tracker[i].subscript,tracker[i].vector_ptr->subscript,(size_t)tracker[i].vector_ptr);}
        else {printf("   %i:element[%i] at 0\n",i,tracker[i].subscript);}
    }
    // END TEST SECTION
    // don't forget to free everything
    ss_vector_free_all_elements(); 
    return 0;
}

int main(int argc, char *argv[])
{   char cmd[5],main_buffer[50]; // Intentionally big for "other" I/O purposes
    cmd[0]=32; // blank = ASCII 32
    //  while(cmd!="R"&&cmd!="W"  &&cmd!="E"        &&cmd!=" ") 
    while(cmd[0]!=82&&cmd[0]!=87&&cmd[0]!=69)//&&cmd[0]!=32) 
    {   memset(cmd, '\0', sizeof(cmd));
        memset(main_buffer, '\0', sizeof(main_buffer));
        // default back to the cmd loop
        cmd[0]=32; // blank = ASCII 32
        printf("REad, TEst, WRITe, EDIt, or EXIt? ");
        fscanf(stdin, "%s", main_buffer);
        strncpy(cmd,main_buffer,4);
        for(int i=0;i<4;i++)cmd[i]=toupper(cmd[i]);
        cmd[4]='\0';
        printf("%s received\n ",cmd);
        // process top level commands
        if(cmd[0]==82) {printf("READ accepted\n");} //Read
        else if(cmd[0]==87) {printf("WRITe accepted\n");} // Write
        else if(cmd[0]==84) 
        {   printf("TESt accepted\n");// TESt
            Test();
        }
        else if(cmd[0]==69) // "E"
        {   if(cmd[1]==68) {printf("EDITing\n");} // eDit
            else if(cmd[1]==88) {printf("EXITing\n");exit(0);} // eXit
            else    printf("  unknown E command %c%c\n",cmd[0],cmd[1]);
        }
        else    printf("  unknown command\n");
        cmd[0]=32; // blank = ASCII 32
    } // while()
    // default back to the cmd loop
}   // main()

User · Answer

As with everything that seems scarier at first than it was later  the best way to get over the initial fear is to immerse yourself into the discomfort of the unknown  It is at times like that which we learn the most  after all   Unfortunately  there are limitations  While you re still learning to use a function  you shouldn t assume the role of a teacher  for example  I often read answers from those who seemingly don t know how to use realloc  i e  the currently accepted answer   telling others how to use it incorrectly  occasionally under the guise that they ve omitted error handling  even though this is a common pitfall which needs mention  Here s an answer explaining how to use realloc correctly  Take note that the answer is storing the return value into a different variable in order to perform error checking   Every time you call a function  and every time you use an array  you are using a pointer  The conversions are occurring implicitly  which if anything should be even scarier  as it s the things we don t see which often cause the most problems  For example  memory leaks     Array operators are pointer operators  array x  is really a shortcut for   array   x   which can be broken down into    and  array   x   It s most likely that the   is what confuses you  We can further eliminate the addition from the problem by assuming x to be 0  thus  array 0  becomes  array because adding 0 won t change the value         and thus we can see that  array is equivalent to array 0   You can use one where you want to use the other  and vice versa  Array operators are pointer operators   malloc  realloc and friends don t invent the concept of a pointer which you ve been using all along  they merely use this to implement some other feature  which is a different form of storage duration  most suitable when you desire drastic  dynamic changes in size   It is a shame that the currently accepted answer also goes against the grain of some other very well-founded advice on StackOverflow  and at the same time  misses an opportunity to introduce a little-known feature which shines for exactly this usecase  flexible array members  That s actually a pretty broken answer        When you define your struct  declare your array at the end of the structure  without any upper bound  For example   struct int list       size t size      int value         This will allow you to unite your array of int into the same allocation as your count  and having them bound like this can be very handy   sizeof  struct int list  will act as though value has a size of 0  so it ll tell you the size of the structure with an empty list  You still need to add to the size passed to realloc to specify the size of your list   Another handy tip is to remember that realloc NULL  x  is equivalent to malloc x   and we can use this to simplify our code  For example   int push back struct int list   fubar  int value        size t x    fubar   fubar 0 - gt size   0            y   x   1       if   x  amp  y     0            void  temp   realloc  fubar  sizeof   fubar                                       x   y    sizeof fubar 0 - gt value 0            if   temp    return 1             fubar   temp     or  if you like   fubar 0    temp              fubar 0 - gt value x    value      fubar 0 - gt size   y      return 0     struct int list  array   NULL    The reason I chose to use struct int list    as the first argument may not seem immediately obvious  but if you think about the second argument  any changes made to value from within push back would not be visible to the function we re calling from  right  The same goes for the first argument  and we need to be able to modify our array  not just here but possibly also in any other function s we pass it to     array starts off pointing at nothing  it is an empty list  Initialising it is the same as adding to it  For example   struct int list  array   NULL  if   push back  amp array  42            success      P S  Remember to free array   when you re done with it

User · Answer

To create an array of unlimited items of any sort of type   typedef struct STRUCT SS VECTOR       size t size      void   items    ss vector    ss vector  ss init vector size t item size        ss vector  vector      vector   malloc sizeof ss vector        vector- gt size   0      vector- gt items   calloc 0  item size        return vector     void ss vector append ss vector  vec  void  item        vec- gt size        vec- gt items   realloc vec- gt items  vec- gt size   sizeof item        vec- gt items vec- gt size - 1    item      void ss vector free ss vector  vec        for  int i   0  i  lt  vec- gt size  i            free vec- gt items i         free vec- gt items       free vec       and how to use it      defining some sort of struct  can be anything really typedef struct APPLE STRUCT       int id    apple   apple  init apple int id        apple  a      a   malloc sizeof apple        a- gt  id   id      return a       int main int argc  char  argv          ss vector  vector   ss init vector sizeof apple            inserting some items     for  int i   0  i  lt  10  i            ss vector append vector  init apple i             dont forget to free it     ss vector free vector        return 0      This vector array can hold any type of item and it is completely dynamic in size

User · Answer

There are a couple of options I can think of    Linked List  You can use a linked list to make a dynamically growing array like thing  But you won t be able to do array 100  without having to walk through 1-99 first  And it might not be that handy for you to use either  Large array  Simply create an array with more than enough space for everything Resizing array  Recreate the array once you know the size and or create a new array every time you run out of space with some margin and copy all the data to the new array  Linked List Array combination  Simply use an array with a fixed size and once you run out of space  create a new array and link to that  it would be wise to keep track of the array and the link to the next array in a struct     It is hard to say what option would be best in your situation  Simply creating a large array is ofcourse one of the easiest solutions and shouldn t give you much problems unless it s really large

User · Answer

Well  I guess if you need to remove an element you will make a copy of the array despising the element to be excluded      inserting some items void  element 2 remove   getElement2BRemove     for  int i   0  i  lt  vector- gt size  i            if vector i   element 2 remove  copy2TempVector vector i              free vector- gt items   free vector   fillFromTempVector vector        Assume that getElement2BRemove    copy2TempVector  void       and fillFromTempVector      are auxiliary methods to handle the temp vector

User · Answer

I can use pointers  but I am a bit afraid of using them   If you need a dynamic array  you can t escape pointers  Why are you afraid though  They won t bite  as long as you re careful  that is   There s no built-in dynamic array in C  you ll just have to write one yourself  In C    you can use the built-in std  vector class  C  and just about every other high-level language also have some similar class that manages dynamic arrays for you  If you do plan to write your own  here s something to get you started  most dynamic array implementations work by starting off with an array of some  small  default size  then whenever you run out of space when adding a new element  double the size of the array  As you can see in the example below  it s not very difficult at all   I ve omitted safety checks for brevity  typedef struct     int  array    size t used    size t size    Array   void initArray Array  a  size t initialSize      a- gt array   malloc initialSize   sizeof int      a- gt used   0    a- gt size   initialSize     void insertArray Array  a  int element         a- gt used is the number of used entries  because a- gt array a- gt used    updates a- gt used only  after  the array has been accessed       Therefore a- gt used can go up to a- gt size    if  a- gt used    a- gt size        a- gt size    2      a- gt array   realloc a- gt array  a- gt size   sizeof int          a- gt array a- gt used      element     void freeArray Array  a      free a- gt array     a- gt array   NULL    a- gt used   a- gt size   0     Using it is just as simple  Array a  int i   initArray  amp a  5       initially 5 elements for  i   0  i  lt  100  i      insertArray  amp a  i       automatically resizes as necessary printf  quot  d n quot   a array 9        print 10th element printf  quot  d n quot   a used       print number of elements freeArray  amp a

User · Answer

These posts may be in the wrong order  This is  2 in a series of 3 posts  Sorry  I ve  quot taken a few liberties quot  with Lie Ryan s code  implementing a linked list so individual elements of his vector can be accessed via a linked list  This allows access  but admittedly it is time-consuming to access individual elements due to search overhead  i e  walking down the list until you find the right element  I ll cure this by maintaining an address vector containing subscripts 0 through whatever paired with memory addresses  This is still not as efficient as a plain-and-simple array would be  but at least you don t have to  quot walk the list quot  searching for the proper item         Based on code from https   stackoverflow com questions 3536153 c-dynamically-growing-array typedef struct STRUCT SS VECTOR     size t size       of vector elements     void   items     makes up one vector element s component contents     int subscript     this element s subscript nmbr  0 thru whatever     struct STRUCT SS VECTOR  this element     linked list via this ptr     struct STRUCT SS VECTOR  next element     and next ptr   ss vector   ss vector  vector     ptr to vector of components  ss vector  ss init vector size t item size     item size is size of one array member     vector  malloc sizeof ss vector         vector- gt this element   vector       vector- gt size   0     initialize count of vector component elements     vector- gt items   calloc 1  item size      allocate  amp  zero out memory for one linked list element     vector- gt subscript 0      vector- gt next element NULL              If there s an array of element addresses subscripts  install it now      return vector- gt this element     ss vector  ss vector append ss vector  vec element                  int i                                                                                --ptr to this element   --element nmbr     ss vector  local vec element 0         If there is already a next element  recurse to end-of-linked-list     if vec element- gt next element   size t 0           local vec element  ss vector append vec element- gt next element i      recurse to end of list         return local vec element               vec element is NULL  so make a new element and add at end of list     local vec element  calloc 1 sizeof ss vector       memory for one component     local vec element- gt this element local vec element     save the address     local vec element- gt next element 0      vec element- gt next element local vec element- gt this element      local vec element- gt subscript i    vec element- gt size       local vec element- gt size i     increment   of vector components             If there s an array of element addresses subscripts  update it now      return local vec element     void ss vector free one element int i gboolean Update subscripts          Walk the entire linked list to the specified element  patch up              the element ptrs before next  then free its contents  then free it              Walk the rest of the list  updating subscripts  if requested              If there s an array of element addresses subscripts  shift it along the way      ss vector  vec element      struct STRUCT SS VECTOR  this one      struct STRUCT SS VECTOR  next one      vec element vector      while  vec element- gt this element- gt subscript  i  amp  amp  vec element- gt next element   size t  0      skip         this one vec element- gt this element     trailing ptr         next one vec element- gt next element     will become current ptr         vec element next one                now at either target element or end-of-list     if vec element- gt this element- gt subscript  i          printf  quot vector element not found n quot   return          free this one     this one- gt next element next one- gt next element    previous element points to element after current one     printf  quot freeing element  i  at  lu quot  next one- gt subscript  size t next one       printf  quot  between  lu and  lu n quot   size t this one  size t next one- gt next element       vec element next one- gt next element       free next one      free the current element        renumber if requested     if Update subscripts          i 0          vec element vector          while vec element   size t  0              vec element- gt subscript i              i                vec element vec element- gt next element                               If there s an array of element addresses subscripts  update it now         Check  temporarily show the new list     vec element vector      while vec element   size t  0          printf  quot    remaining element  i  at  lu n quot  vec element- gt subscript  size t vec element- gt this element           vec element vec element- gt next element               return       void ss vector free one element    void ss vector insert one element ss vector  vec element int place          Walk the entire linked list to specified element  quot place quot   patch up              the element ptrs before next  then calloc an element and store its contents at  quot place quot               Increment all the following subscripts              If there s an array of element addresses subscripts  make a bigger one               copy the old one  then shift appropriate members            Not yet implemented         void ss vector insert one element    void ss vector free all elements void          Start at  quot vector quot  Walk the entire linked list  free each element s contents               free that element  then move to the next one              If there s an array of element addresses subscripts  free it      ss vector  vec element      struct STRUCT SS VECTOR  next one      vec element vector      while vec element- gt next element   size t  0          next one vec element- gt next element             free vec element- gt items     don t forget to free these         free vec element- gt this element           vec element next one          next one vec element- gt this element               get rid of the last one         free vec element- gt items      free vec element       vector NULL              If there s an array of element addresses subscripts  free it now  printf  quot  nall vector elements  amp  contents freed n quot         void ss vector free all elements       defining some sort of struct  can be anything really typedef struct APPLE STRUCT     int id     one of the data in the component     int other id     etc     struct APPLE STRUCT  next element    apple     description of component  apple  init apple int id     make a single component     apple  a     ptr to component     a   malloc sizeof apple       memory for one component     a- gt id   id     populate with data     a- gt other id id 10      a- gt next element NULL         don t mess with aa- gt last rec here     return a     return pointer to component     int return id value int i apple  aa     given ptr to component  return single data item     printf  quot was inserted as apple  i  id    i      quot  i aa- gt id       return aa- gt id      ss vector  return address given subscript ss vector  vec element int i      always make the first call to this subroutine with global vbl  quot vector quot      ss vector  local vec element 0         If there is a next element  recurse toward end-of-linked-list     if vec element- gt next element   size t 0          if  vec element- gt this element- gt subscript  i               return vec element- gt this element           local vec element  return address given subscript vec element- gt next element i      recurse to end of list         return local vec element            else         if  vec element- gt this element- gt subscript  i      last element             return vec element- gt this element              otherwise  none match         printf  quot reached end of list without match n quot            return  size t  0             return address given subscript    int Test void      was  quot main quot  in the original example     ss vector  local vector      local vector ss init vector sizeof apple       element  quot 0 quot      for  int i   1  i  lt  10  i       inserting items  quot 1 quot  thru whatever         local vector ss vector append vector i              test search function     printf  quot  n NEXT  test search for address given subscript n quot        local vector return address given subscript vector 5       printf  quot finished return address given subscript 5  with vector at  lu n quot   size t local vector       local vector return address given subscript vector 0       printf  quot finished return address given subscript 0  with vector at  lu n quot   size t local vector       local vector return address given subscript vector 9       printf  quot finished return address given subscript 9  with vector at  lu n quot   size t local vector          test single-element removal     printf  quot  nNEXT  test single element removal n quot        ss vector free one element 5 FALSE      without renumbering subscripts     ss vector free one element 3 TRUE     WITH renumbering subscripts        ---end of program---        don t forget to free everything     ss vector free all elements         return 0

User · Answer

Building on Matteo Furlans design  when he said  most dynamic array implementations work by starting off with an array of some  small  default size  then whenever you run out of space when adding a new element  double the size of the array   The difference in the  work in progress  below is that it doesn t double in size  it aims at using only what is required  I have also omitted safety checks for simplicity   Also building on brimboriums idea  I have tried to add a delete function to the code     The storage h file looks like this      ifndef STORAGE H  define STORAGE H   ifdef   cplusplus extern  C     endif      typedef struct                int  array          size t size        Array       void Array Init Array  array       void Array Add Array  array  int item       void Array Delete Array  array  int index       void Array Free Array  array     ifdef   cplusplus    endif   endif    STORAGE H      The storage c file looks like this      include  lt stdio h gt   include  lt stdlib h gt   include  storage h      Initialise an empty array    void Array Init Array  array         int  int pointer       int pointer    int   malloc sizeof int         if  int pointer    NULL                       printf  Unable to allocate memory  exiting  n            free int pointer           exit 0             else               array- gt array   int pointer           array- gt size   0              Dynamically add to end of an array    void Array Add Array  array  int item         int  int pointer       array- gt size    1       int pointer    int   realloc array- gt array  array- gt size   sizeof int         if  int pointer    NULL                       printf  Unable to reallocate memory  exiting  n            free int pointer           exit 0             else               array- gt array   int pointer          array- gt array array- gt size-1    item              Delete from a dynamic array    void Array Delete Array  array  int index         int i      Array temp      int  int pointer       Array Init  amp temp        for i index  i lt array- gt size  i                  array- gt array i    array- gt array i   1              array- gt size -  1       for  i   0  i  lt  array- gt size  i                  Array Add  amp temp  array- gt array i               int pointer    int   realloc temp array  temp size   sizeof int         if  int pointer    NULL                       printf  Unable to reallocate memory  exiting  n            free int pointer           exit 0             else               array- gt array   int pointer                Free an array    void Array Free Array  array       free array- gt array     array- gt array   NULL    array- gt size   0        The main c looks like this      include  lt stdio h gt   include  lt stdlib h gt   include  storage h   int main int argc  char   argv         Array pointers      int i       Array Init  amp pointers        for  i   0  i  lt  60  i                  Array Add  amp pointers  i                      Array Delete  amp pointers  3        Array Delete  amp pointers  6        Array Delete  amp pointers  30        for  i   0  i  lt  pointers size  i                          printf  Value   d Size  d  n   pointers array i   pointers size              Array Free  amp pointers        return  EXIT SUCCESS       Look forward to the constructive criticism to follow

User · Answer

When you re saying     make an array holding an index number  int  of an indeterminate number of entities   you re basically saying you re using  pointers   but one which is a array-wide local pointer instead of memory-wide pointer  Since you re conceptually already using  pointers   i e  id numbers that refers to an element in an array   why don t you just use regular pointers  i e  id numbers that refers to an element in the biggest array  the whole memory    Instead of your objects storing a resource id numbers  you can make them store a pointer instead  Basically the same thing  but much more efficient since we avoid turning  array   index  into a  pointer    Pointers are not scary if you think of them as array index for the whole memory  which is what they actually are

User · Answer

These posts apparently are in the wrong order  This is  1 in a series of 3 posts  Sorry  In attempting to use Lie Ryan s code  I had problems retrieving stored information  The vector s elements are not stored contiguously as you can see by  quot cheating quot  a bit and storing the pointer to each element s address  which of course defeats the purpose of the dynamic array concept  and examining them  With a bit of tinkering  via  ss vector  vector     pull this out to be a global vector     Then add the following to attempt to recover stored values   int return id value int i apple  aa     given ptr to component return data item     printf  quot showing apple  i  id    i and  other id  i n quot  i aa- gt id aa- gt other id       return aa- gt id      int Test void      Used to be  quot main quot  in the example     apple  aa 10      stored array element addresses     vector   ss init vector sizeof apple           inserting some items     for  int i   0  i  lt  10  i            aa i  init apple i           printf  quot apple id  i and  other id  i n quot  aa i - gt id aa i - gt other id           ss vector append vector  aa i                  report the number of components  printf  quot nmbr of components in vector    i n quot   int vector- gt size    printf  quot     array access   component 5     i n quot  return id value 5 aa 5      printf  quot components of size  i n quot   int sizeof apple     printf  quot  n    pointer initial access   component 0     i n quot  return id value 0  apple    amp vector 0                     etc     followed by  for  int i   0  i  lt  10  i         printf  quot apple  i  id    i at address  i  delta  i n quot  i     return id value i aa i     int aa i   int  aa i -aa i 1              don t forget to free it ss vector free vector   return 0     It s possible to access each array element without problems  as long as you know its address  so I guess I ll try adding a  quot next quot  element and use this as a linked list  Surely there are better options  though  Please advise

[c] C dynamically growing array

Examples related to c

Examples related to dynamic-arrays