These posts may be in the wrong order! This is #2 in a series of 3 posts. Sorry.
I've "taken a few liberties" 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 "walk the list" 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->this_element = 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;
vector->next_element=NULL;
// If there's an array of element addresses/subscripts, install it now.
return vector->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->next_element!=(size_t)0)
{ local_vec_element= ss_vector_append(vec_element->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->this_element=local_vec_element; // save the address
local_vec_element->next_element=0;
vec_element->next_element=local_vec_element->this_element;
local_vec_element->subscript=i; //vec_element->size;
local_vec_element->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->this_element->subscript!=i)&&(vec_element->next_element!=(size_t) 0)) // skip
{ this_one=vec_element->this_element; // trailing ptr
next_one=vec_element->next_element; // will become current ptr
vec_element=next_one;
}
// now at either target element or end-of-list
if(vec_element->this_element->subscript!=i)
{ printf("vector element not found\n");return;}
// free this one
this_one->next_element=next_one->next_element;// previous element points to element after current one
printf("freeing element[%i] at %lu",next_one->subscript,(size_t)next_one);
printf(" between %lu and %lu\n",(size_t)this_one,(size_t)next_one->next_element);
vec_element=next_one->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->subscript=i;
i++;
vec_element=vec_element->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(" remaining element[%i] at %lu\n",vec_element->subscript,(size_t)vec_element->this_element);
vec_element=vec_element->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 "place", patch up
// the element ptrs before/next, then calloc an element and store its contents at "place".
// 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 "vector".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->next_element!=(size_t) 0)
{ next_one=vec_element->next_element;
// free(vec_element->items) // don't forget to free these
free(vec_element->this_element);
vec_element=next_one;
next_one=vec_element->this_element;
}
// get rid of the last one.
// free(vec_element->items)
free(vec_element);
vector=NULL;
// If there's an array of element addresses/subscripts, free it now.
printf("\nall vector elements & contents freed\n");
} // 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(ss_vector* vec_element,int i)
// always make the first call to this subroutine with global vbl "vector"
{ ss_vector* local_vec_element=0;
// If there is a next element, recurse toward end-of-linked-list
if(vec_element->next_element!=(size_t)0)
{ if((vec_element->this_element->subscript==i))
{ return vec_element->this_element;}
local_vec_element= return_address_given_subscript(vec_element->next_element,i); // recurse to end of list
return local_vec_element;
}
else
{ if((vec_element->this_element->subscript==i)) // last element
{ return vec_element->this_element;}
// otherwise, none match
printf("reached end of list without match\n");
return (size_t) 0;
}
} // return_address_given_subscript()
int Test(void) // was "main" in the original example
{ ss_vector* local_vector;
local_vector=ss_init_vector(sizeof(apple)); // element "0"
for (int i = 1; i < 10; i++) // inserting items "1" thru whatever
{ local_vector=ss_vector_append(vector,i);}
// test search function
printf("\n NEXT, test search for address given subscript\n");
local_vector=return_address_given_subscript(vector,5);
printf("finished return_address_given_subscript(5) with vector at %lu\n",(size_t)local_vector);
local_vector=return_address_given_subscript(vector,0);
printf("finished return_address_given_subscript(0) with vector at %lu\n",(size_t)local_vector);
local_vector=return_address_given_subscript(vector,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,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;
}