this is my count and say problem from leetcode solution. But with memory leaks https://leetcode.com/problems/count-and-say/
My makefile
build:
gcc main.c -Wall -g -o main; \
$(PWD)/main; \
My build commands
make
Or with valgrind:
make
valgrind --leak-check=yes ./main
Output: (correct, tested)
count and say 30 = 3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211
From Valgrind
==1796== Memcheck, a memory error detector
==1796== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et
al.
==1796== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright
info
==1796== Command: ./main
==1796==
==1796== Invalid read of size 1
==1796== at 0x100000930: countAndSay (main.c:62)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Address 0x100df6f80 is 0 bytes inside a block of size 2
free'd
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Block was alloc'd at
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000892: countAndSay (main.c:40)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== Invalid read of size 1
==1796== at 0x10000096B: countAndSay (main.c:73)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Address 0x100df6f80 is 0 bytes inside a block of size 2
free'd
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Block was alloc'd at
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000892: countAndSay (main.c:40)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== Invalid read of size 1
==1796== at 0x1000009D7: countAndSay (main.c:89)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Address 0x100df6f80 is 0 bytes inside a block of size 2
free'd
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Block was alloc'd at
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000892: countAndSay (main.c:40)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== Invalid read of size 16
==1796== at 0x100655A65: _platform_memchr$VARIANT$Base (in
/usr/lib/system/libsystem_platform.dylib)
==1796== by 0x1002E99E9: __sfvwrite (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002F35FE: __vfprintf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x100318058: __v2printf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002EF741: vfprintf_l (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002ED7CA: printf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x100000EE0: main (main.c:210)
==1796== Address 0x10545d410 is 1 bytes after a block of size 4,463
alloc'd
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x1000AC30C: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000C67: countAndSay (main.c:157)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== Conditional jump or move depends on uninitialised value(s)
==1796== at 0x100655A7D: _platform_memchr$VARIANT$Base (in
/usr/lib/system/libsystem_platform.dylib)
==1796== by 0x1002E99E9: __sfvwrite (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002F35FE: __vfprintf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x100318058: __v2printf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002EF741: vfprintf_l (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002ED7CA: printf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x100000EE0: main (main.c:210)
==1796==
count and say 30 = 3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211
==1796==
==1796== HEAP SUMMARY:
==1796== in use at exit: 29,301,895 bytes in 40,712 blocks
==1796== total heap usage: 80,412 allocs, 39,700 frees, 58,326,719
bytes allocated
==1796==
==1796== 72 bytes in 3 blocks are possibly lost in loss record 25 of 51
==1796== at 0x1000ABD72: calloc (vg_replace_malloc.c:755)
==1796== by 0x10075A7C2: map_images_nolock (in
/usr/lib/libobjc.A.dylib)
==1796== by 0x10076D4E0: map_images (in /usr/lib/libobjc.A.dylib)
==1796== by 0x100007C64: dyld::notifyBatchPartial(dyld_image_states,
bool, char const* (*)(dyld_image_states, unsigned int, dyld_image_info
const*), bool, bool) (in /usr/lib/dyld)
==1796== by 0x100007E39: dyld::registerObjCNotifiers(void (*)
(unsigned int, char const* const*, mach_header const* const*), void (*)
(char const*, mach_header const*), void (*)(char const*, mach_header
const*)) (in /usr/lib/dyld)
==1796== by 0x10022571D: _dyld_objc_notify_register (in /
/usr/lib/system/libdyld.dylib)
==1796== by 0x10075A073: _objc_init (in /usr/lib/libobjc.A.dylib)
==1796== by 0x1001AFB34: _os_object_init (in
/usr/lib/system/libdispatch.dylib)
==1796== by 0x1001AFB1B: libdispatch_init (in
/usr/lib/system/libdispatch.dylib)
==1796== by 0x1000BE9C2: libSystem_initializer (in
/usr/lib/libSystem.B.dylib)
==1796== by 0x100019AC5:
ImageLoaderMachO::doModInitFunctions(ImageLoader::LinkContext const&)
(in /usr/lib/dyld)
==1796== by 0x100019CF5:
ImageLoaderMachO::doInitialization(ImageLoader::LinkContext const&) (in
/usr/lib/dyld)
==1796==
==1796== 168 bytes in 56 blocks are definitely lost in loss record 28
of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x1000AC30C: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 570 bytes in 1 blocks are possibly lost in loss record 37 of
51
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000DCD: countAndSay (main.c:184)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 1,512 bytes in 378 blocks are definitely lost in loss record
38 of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x1000AC30C: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000DCD: countAndSay (main.c:184)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 4,462 bytes in 1 blocks are definitely lost in loss record 45
of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000867: countAndSay (main.c:29)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 17,848 bytes in 1 blocks are definitely lost in loss record 46
of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000857: countAndSay (main.c:28)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 19,257 (240 direct, 19,017 indirect) bytes in 1 blocks are d
definitely lost in loss record 48 of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000839: countAndSay (main.c:19)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 61,644 bytes in 406 blocks are definitely lost in loss record
49 of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x1000AC30C: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000C67: countAndSay (main.c:157)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 80,493 bytes in 379 blocks are definitely lost in loss record
50 of 51
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 29,093,648 bytes in 39,299 blocks are definitely lost in loss
record 51 of 51
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000DCD: countAndSay (main.c:184)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== LEAK SUMMARY:
==1796== definitely lost: 29,260,015 bytes in 40,521 blocks
==1796== indirectly lost: 19,017 bytes in 29 blocks
==1796== possibly lost: 642 bytes in 4 blocks
==1796== still reachable: 200 bytes in 6 blocks
==1796== suppressed: 22,021 bytes in 152 blocks
==1796== Reachable blocks (those to which a pointer was found) are not
shown.
==1796== To see them, rerun with: --leak-check=full --show-leak-
kinds=all
==1796==
==1796== For counts of detected and suppressed errors, rerun with: -v
==1796== Use --track-origins=yes to see where uninitialised values come
from
==1796== ERROR SUMMARY: 124 errors from 15 contexts (suppressed: 11
from 11)
main.c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SEQUENCE_COUNT 30
#define BUFFER_MAX 4462
char* countAndSay(int n) {
int msc;
if (n > 0 && n <= 30) {
msc = MAX_SEQUENCE_COUNT;
} else {
fprintf(stderr, "Error: The range for this count and say method is 1...30\n");
exit(1);
}
//Holds the array of sequences
char **out_buffer = malloc(msc * sizeof(char*));
//Holds current sequence
char *out;
int size = n;
//Holds previous sequence
char *prev_chunk = NULL;
//memory for the counts and says
int *counts = malloc(BUFFER_MAX*sizeof(int));
char *says = malloc(BUFFER_MAX*sizeof(char));
//index into the buffer memory of sequences
int index = 0;
//solve iteratively
while (size > 0) {
//base condition
//size counts down to 0, filling chunks, populating the next chunk to be processed
//filled chunks are placed in the out buffer at the index which is counting
if (index == 0) {
out = malloc(2 * sizeof(char));
out[0] = '1';
out[1] = '\0';
prev_chunk = out;
size -= 1;
index += 1;
out_buffer[0] = out;
continue;
}
//from 0 to index - 1 get the chunk to be processed, use it to put together
//the count and say chunk for adding to the index slot
for (int s = 0; s < index; s++) {
if (s == 0) {
prev_chunk = out_buffer[0];
} else {
prev_chunk = out_buffer[index];
}
//count the length of the current chunk
int length = 0;
for (int e = 0; e <= BUFFER_MAX; e++) {
if (prev_chunk[e]) {
length += 1;
} else {
break;
}
}
//The count of says at each iteration
int count = 0;
//say is a char byte from the previous chunk memory
char say = prev_chunk[0];
//skip is used in the iteration process
int skip = 0;
//The idx into memory for the counts and says
int idx = 0;
//iteratively generate the count and say chunk for this index
for (int i = 0; i < length; i++) {
if (skip > 0) {
if (i < length - 1) {
say = prev_chunk[i + 1];
}
skip -= 1;
continue;
}
if (prev_chunk[i] == say) {
count += 1;
counts[idx] = count;
says[idx] = say;
//if at the end of the iteration add one
//as a terminator for the counts, says, pairs
if (i == length - 1) {
idx += 1;
break;
}
} else {
count = 0;
if (i == length - 1) {
//finish off
idx += 1;
count += 1;
counts[idx] = count;
says[idx] = prev_chunk[i];
say = says[idx];
idx += 1;
} else {
idx += 1;
count += 1;
counts[idx] = count;
says[idx] = prev_chunk[i];
char next_say = prev_chunk[i + 1];
say = prev_chunk[i];
//Takes care of itself with idx
if (next_say != prev_chunk[i]) {
count = 0;
continue;
}
int y = i;
while (next_say == say && y < length -1) {
count += 1;
//dont need to up the index because we are counting howmany there are
says[idx] = say;
counts[idx] = count;
//skip because this is the next loop
skip += 1;
//subtract 1 because we want this to be in the final index slot
//count because we added an index
y += 1;
next_say = prev_chunk[y + 1];
}
idx += 1;
count = 0;
}
}
}
//Could have just generated the sequence from above but felt like doing this manually at the time
//If I get around to it ill change
int chunk_offset = 0;
char *temp = NULL;
for (int u = 0; u < idx; u++) {
int c = counts[u];
//TODO: factor out or use sprintf, or maybe not, maybe this is just faster
char cc;
if (c >= 10) {
cc = 'A' + c - 10;
} else {
cc = '0' + c;
}
char say = says[u];
if (u == idx - 1) {
temp = realloc(temp, chunk_offset + 3);
if (chunk_offset > 0) {
for (int y = 0; y < chunk_offset; y++) {
temp[y] = out[y];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
temp[chunk_offset + 2] = '\0';
} else {
temp[0] = cc;
temp[1] = say;
temp[2] = '\0';
}
out = realloc(out, chunk_offset + 3);
out = temp;
temp = NULL;
free(temp);
} else {
temp = realloc(temp, chunk_offset + 2);
for (int ii = 0; ii < chunk_offset; ii++) {
temp[ii] = out[ii];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
chunk_offset += 2;
out = realloc(out, chunk_offset + 2);
out = temp;
temp = NULL;
free(temp);
}
}
out_buffer[index] = out;
out = NULL;
free(out);
}
index += 1;
size -= 1;
}
free(prev_chunk);
prev_chunk = NULL;
free(counts);
counts = NULL;
free(says);
says = NULL;
return out_buffer[n - 1];
}
int main(int argc, char **argv) {
char *cs = countAndSay(30);
printf("count and say 30 = %s\n", cs);
}
I know it is not the best algorithm but it works. It is my understanding that realloc can be used in a way to avoid piling up malloc'd memory to the heap inside of loop's kinda like this which works. My suspicion is that by doing so it moves memory into places that are not easily found and free'd. Am I on the right path with that line of thinking? Simple realloc
char *e = NULL;
for (int i = 0; i < 10; i++) {
e = realloc(e, i + 1);
if (i == 9) {
e[i] = '\0';
} else {
e[i] = 'e';
}
}
printf("%s\n", e);
free(e);
Yields from valgrind:
==4421== LEAK SUMMARY:
==4421== definitely lost: 0 bytes in 0 blocks
==4421== indirectly lost: 0 bytes in 0 blocks
==4421== possibly lost: 72 bytes in 3 blocks
==4421== still reachable: 200 bytes in 6 blocks
==4421== suppressed: 22,021 bytes in 152 blocks
I have been running this with valgrind trying to pin down the leaking issue. I have also seen solution such as this and tried them with no luck: "Pointer being freed was not allocated." error after malloc, realloc.
I believe the main problem I am having here is that I malloc "out" the first time. After that I realloc it each time in the loop(s). Valgrind is giving the biggest leaks at line main.c:184 "out = realloc(out, chunk_offset + 2);". It seems like realloc is just deciding to put that memory somewhere in the heap and I cant get to it. I know the address can change from a realloc, but I still havent been able to get at it. How can I get definitely lost down to 0 in my countandsay.
Let's start with this block:
if (u == idx - 1) {
temp = realloc(temp, chunk_offset + 3);
if (chunk_offset > 0) {
for (int y = 0; y < chunk_offset; y++) {
temp[y] = out[y];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
temp[chunk_offset + 2] = '\0';
} else {
temp[0] = cc;
temp[1] = say;
temp[2] = '\0';
}
out = realloc(out, chunk_offset + 3);
// *** MEMORY LEAK ***
out = temp;
temp = NULL;
// NOT NEEDED
free(temp);
} else {
temp = realloc(temp, chunk_offset + 2);
for (int ii = 0; ii < chunk_offset; ii++) {
temp[ii] = out[ii];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
chunk_offset += 2;
out = realloc(out, chunk_offset + 2);
// *** MEMORY LEAK ***
out = temp;
temp = NULL;
// NOT NEEDED
free(temp);
}
In both parts of the if, you expand the size of out, but then you immediately overwrite out with the value of temp, leaking the memory that out was pointing to.
Since temp contains the values you want, you no longer need what's in out, so get rid of the realloc on out and instead free what was there previously. Also, there's no need to free(temp) since it points to NULL, and you can replace the realloc calls with malloc since temp will always be NULL at that point:
if (u == idx - 1) {
temp = malloc(chunk_offset + 3);
if (chunk_offset > 0) {
for (int y = 0; y < chunk_offset; y++) {
temp[y] = out[y];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
temp[chunk_offset + 2] = '\0';
} else {
temp[0] = cc;
temp[1] = say;
temp[2] = '\0';
}
} else {
temp = malloc(chunk_offset + 2);
for (int ii = 0; ii < chunk_offset; ii++) {
temp[ii] = out[ii];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
chunk_offset += 2;
}
free(out);
out = temp;
Then you have this at the bottom of your for loop:
for (int s = 0; s < index; s++) {
...
out_buffer[index] = out;
out = NULL;
free(out);
}
You overwrite the contents of out_buffer[index] on each iteration which leaks memory. You'll need to free the old contents first, and also get rid of the unneeded free(out) at the end since it contains NULL at that point. This also means you need to initialize out_buffer[index] to NULL before entering the loop.
out_buffer[index] = NULL;
for (int s = 0; s < index; s++) {
...
free(out_buffer[index]);
out_buffer[index] = out;
out = NULL;
}
Then you have an issue here:
if (index == 0) {
out = malloc(2 * sizeof(char));
out[0] = '1';
out[1] = '\0';
prev_chunk = out;
size -= 1;
index += 1;
out_buffer[0] = out;
continue;
}
Which fails to set out to NULL before the next iteration of the loop, which will result in out_buffer[0] getting free'ed and subsequently reading from free'ed memory. So add that here:
if (index == 0) {
out = malloc(2 * sizeof(char));
out[0] = '1';
out[1] = '\0';
prev_chunk = out;
size -= 1;
index += 1;
out_buffer[0] = out;
out = NULL;
continue;
}
Then at the end:
free(prev_chunk);
prev_chunk = NULL;
free(counts);
counts = NULL;
free(says);
says = NULL;
return out_buffer[n - 1];
You don't want to free(prev_chunk); since it points to an old copy of out that was already free'ed. You're also not freeing out_buffer or any of the strings it points to. You don't want to free the string you return, of course, so skip that one:
char *rval = out_buffer[n - 1];
for (int i = 0; i < n - 1; i++) {
free(out_buffer[i]);
}
free(out_buffer);
free(counts);
free(says);
return rval;
Finally, make sure you free the result of this function once main is done with it:
char *cs = countAndSay(30);
printf("count and say 30 = %s\n", cs);
free(cs);
Now you have a clean run through valgrind with no memory leaks or invalid read/write/free errors.
On a side note, there are a lot of inefficiencies in this code. On each iteration of the outer while loop, you generate the entire list from 1 to the current value of n. So on the first iteration you calculate n=1, then on the next you calculate n=1,2, then on the next you calculate n=1,2,3, etc.
You only need one loop here. That also means you don't have to reuse the current value of out_buffer but can instead just reference the previous one. I'll leave those changes as an exercise to the reader.