So, I was doing this exercise:
Write a C function void occurrences(char* s, char c, char*** occp, int* n) that, given a string s and a char c, counts the number of occurrences of char c in the string s, returns that number in n and returns in occp the adress of a new array of char that contains the adresses of each c occurrence in s
main sample:
#include <stdio.h>
int main(){
int i, n;
char** occ;
occorrenze("engineering", 'n', &occ, &n);
for (i=0; i<n; ++i) printf("%s\n", occ[i]); // prints ngineering neering ng
free(occ);
}
Initially I wrote the function this way:
void occurrences(char* s1, char c, char*** s, int* n){
*n=0;
char* arr[2];
int length=strlen(s1);
int i;
for(i=0; i<length; i++){
if(s1[i]==c)(*n)++;
}
*s=(malloc((*n)*sizeof(char**)));
int a=0;
for(i=0; i<length; i++){
if(s1[i]==c){
(*s)[a]= &s1[i];
a++;
}
}
}
Worked well, but I wanted to try and re-write it iterating the string just one time. I thought of using realloc(), function which I never used before and eventually I came up with this:
void occurrences(char* s1, char c, char*** s, int* n){
*n=0;
*s=malloc(0);
char* arr[2];
int length=strlen(s1);
int i,a=0;
for(i=0; i<length; i++){
if(s1[i]==c){
(*n)++;
*s=realloc(*s,(*n)*sizeof(char**));
(*s)[a]= &s1[i];
a++;
}
}
}
This one seemed to work well too, but then I run Valgrind:
==4893== HEAP SUMMARY:
==4893== in use at exit: 0 bytes in 0 blocks
==4893== total heap usage: 4 allocs, 4 frees, 48 bytes allocated
==4893==
==4893== All heap blocks were freed -- no leaks are possible
==4893==
==4893== For counts of detected and suppressed errors, rerun with: -v
==4893== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)
48 bytes allocated ? It should've been 24 bytes, right ? The total heap size is 8*n! instead of 8*n... I guess I am missing something XD
EDIT: copied the right function lol
HEAP USAGE:
If you malloc(1)
, the system allocates a chunk of memory for you that is capable of holding one byte. What you might not realize though, the system would generally never allocate a single byte. In reality, the allocated chunk of memory is most likely much larger; perhaps a minimum of 8, 16 or 32 bytes. Hence, malloc()
ed space does not equal heap space
-used.
And due to the above 'minimum' system memory allocations, the function realloc()
may return the same address as it was given; if the system allocation at that address is large enough to accomidate the (in your case) larger size. Once the system allocation becomes too small, realloc()
will return a new address to a larger chunk of system memory (and most likely larger than requested by realloc).
A few comments:
void occurrences(char* s1, char c, char*** s, int* n){
*n=0;
*s=NULL;
Changed the above line. No need to malloc(0);
. The value of s
(NULL
) will be passed in to realloc()
, which then works just like malloc()
,
char* arr[2];
int length=strlen(s1);
int i,a=0;
for(i=0; i<length; i++){
if(s1[i]==c){
(*n)++;
*s=realloc(*s,(*n) * sizeof(char**)); // !DANGER!
Instead of the above line, consider the following replacement:
if(s1[i]==c){
char *tmp;
(*n)++;
tmp=realloc(*s,(*n) * sizeof(char**)); // Much better.
if(NULL == tmp)
{
/* Handle realloc() failure. */
...
}
else
*s = tmp;
...
If you don't do it as shown above, if realloc()
fails, the previously allocated memory (pointed to by s
) is lost; replaced by NULL
.
(*s)[a]= &s1[i];
a++;
}
}
}