This is a fundamental and important issue. You need to not only know how to handle dynamic allocation, but how to handle it in the structured way. To begin with, you need two counters. One counter tracking the number of integers you have allocated for and the second counter tracking the number of integers used. You do not need to reallocate when you "remove" an integer, only when adding and when used == allocated. Otherwise, if used < allocated, there is no need to allocate for the next integer following "add".
Ideally you want to allocate for some anticipated number of integers and only reallocate when you run out of space in the initially allocate block of memory (generally doubling the size of the currently allocated block each time reallocaion is needed) to minimize the number of relatively costly call to realloc()1. It does add a minor bit of complexity. For a learning exercise, allocating for each new int is fine.
One other note before looking at the allocation scheme is taking input with scanf(). That leads to a horribly fragile input scheme. One stray character in input will result in a matching-failure where the bad character is left unread in stdin breaking your next (and if you rely on input ordering -- the rest of your) inputs. It is far better to read input with a line-oriented input function (like fgets() or POSIX getline()) so that an entire line of input is consumed with each read. You can then parse the values you need from the buffer (character array) filled by fgets() using sscanf(). That way regardless of whether the conversion with sscanf() succeeds or fails, nothing is left unread in stdin.
Additionally, avoid the use of global variables. Instead, declare your variables in the scope where they are needed and then pass any needed information to a function as a parameter rather than relying on global variables. (they have their proper place -- but none you will find as you are learning C, unless you are programming on a microcontroller)
Now for your allocation scheme, changing your name of number_of_elems to allocated to track the number of integers allocated for and adding used to track the number of int used within your allocated block, your scheme would be:
- initialize
ptr = NULL; to begin,
- after reading an
"add" and using strcmp() to confirm (you compare string equality in C with strcmp(), not ==), you will read and VALIDATE the conversion of the integer that follows, then
- compare
if (used == allocated) to determine if allocation for a new integer is needed, if so
- use
realloc() for all allocations (realloc() behaves like malloc() when the pointer is NULL),
- After you VALIDATE the allocation you increment
allocated += 1; and after storing the integer value to the new block of memory, you increment used += 1;,
- if
"remove" is chosen, all that is needed is you VALIDATE used > 0 and if so, just decrement used, there is no need to adjust the allocation at this point -- that only happens with an "add".
- [Optionally] after you read and
"add"/"remove" loop completes, you can make one final realloc() to resize the allocated block of memory to just what is needed to store used number of integers.
So, how would you implement that? Let's' start with the declarations for main() initializing all variables:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXC 256 /* if you need a constant, #define one (or more) */
int main()
{
/* avoid global variables, initialize all vars (good practice) */
char action[MAXC] = ""; /* buffer (array) to hold every input */
int allocated = 0, /* number of integers allocated */
used = 0, /* number of integers used */
*ptr = NULL;
Now let's look at your read loop and work through reading action and determining if we need to "add" a value:
while (1) {
int b = 0; /* declare variables in scope needed */
/* control read-loop with function return, end if EOF or [Enter] on empty-line */
if (fgets (action, MAXC, stdin) == NULL || *action == '\n')
break;
action[strcspn (action, "\n")] = 0; /* trim '\n' from end of action */
if (strcmp (action, "add") == 0) { /* compare strings with strcmp() */
/* reused action to read integer value */
if (!fgets (action, MAXC, stdin) || *action == '\n')
break;
if (sscanf (action, "%d", &b) != 1) { /* validate conversion to int */
fputs ("error: invalid integer input.\n", stderr);
return 1;
}
At this point we have validated all inputs and all conversions and we know we need to "add" the value in b to our allocated block holding integers that we will assign to pointer. But note, since we are using realloc(), you ALWAYS realloc() to a temporary pointer so if realloc() fails returning NULL, you don't overwrite your pointer address with NULL creating a memory leak due to your loss of the address held by your pointer (which can now not be passed to free() to recover the memory). So when calling realloc() DO NOT do:
ptr = realloc (ptr, size);
Instead DO:
void *tmp = realloc (ptr, (allocated + 1) * sizeof *ptr);
if (tmp == NULL) { /* validate EVERY allocation */
perror ("realloc-tmp");
break; /* don't exit, ptr still good */
}
ptr = tmp; /* assign reallocaed block to ptr */
It is only after validating the reallocation succeeds that you assign the newly allocate block of memory to your original pointer. If realloc() fails, the address for your original allocation in ptr is unchanged and still good, you can simply break at that point making use of all data stored to that point.
With that in mind, the rest of your "add" block is:
/* realloc() behaves as malloc() if ptr is NULL, no need for separate malloc()
* (realloc() using temporary pointer to avoid mem-leak if realloc() fails)
*/
if (used == allocated) {
void *tmp = realloc (ptr, (allocated + 1) * sizeof *ptr);
if (tmp == NULL) { /* validate EVERY allocation */
perror ("realloc-tmp");
break; /* don't exit, ptr still good */
}
ptr = tmp; /* assign reallocaed block to ptr */
allocated += 1; /* increment after validation */
}
ptr[used] = b; /* assing b to ptr at index */
used += 1; /* increment after assignment */
/* debug output - remove if desired */
printf ("\nadding %d, used = %d, allocated = %d\n", b, used, allocated);
}
Your "remove" block simply validates that you have integers to remove and then subtracts 1 from used. After the if ... else if ... block, then you can output the current contents of your allocated block that are used:
else if (strcmp (action, "remove") == 0) { /* ditto strmcp() */
if (used > 0) /* only decrement used if > 0, and */
used -= 1; /* (no need to adjust allocation) */
/* debug output, remove if desired */
printf ("\nremove, used = %d, allocated = %d\n", used, allocated);
}
/* debug output (no need to duplicate in each if .. else ...) */
puts ("\ncurrent content");
for (int i = 0; i < used; i++)
printf ("%d\n", ptr[i]);
}
Now, Optionally after your read loop completes you can resize your allocation to only the memory required to hold the integers used. This isn't mandatory, and usually isn't even necessary, but for completeness you could do:
/* [optional] final realloc to resize to exact size needed for used integers */
if (used < allocated) {
void *tmp = realloc (ptr, used * sizeof *ptr);
if (tmp) /* validate reallocation */
ptr = tmp; /* only assign after validation */
else /* otherwise just warn -- but original ptr still good */
perror ("realloc-ptr-to-used");
}
That is basically your program, the only thing that remains is using the stored values however you like and then calling free (ptr); when you are done to free the allocated memory. If you put it altogether, and outputting the complete list before freeing the allocated memory, you would have:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXC 256 /* if you need a constant, #define one (or more) */
int main()
{
/* avoid global variables, initialize all vars (good practice) */
char action[MAXC] = ""; /* buffer (array) to hold every input */
int allocated = 0, /* number of integers allocated */
used = 0, /* number of integers used */
*ptr = NULL;
while (1) {
int b = 0; /* declare variables in scope needed */
/* control read-loop with function return, end if EOF or [Enter] on empty-line */
if (fgets (action, MAXC, stdin) == NULL || *action == '\n')
break;
action[strcspn (action, "\n")] = 0; /* trim '\n' from end of action */
if (strcmp (action, "add") == 0) { /* compare strings with strcmp() */
/* reused action to read integer value */
if (!fgets (action, MAXC, stdin) || *action == '\n')
break;
if (sscanf (action, "%d", &b) != 1) { /* validate conversion to int */
fputs ("error: invalid integer input.\n", stderr);
return 1;
}
/* realloc() behaves as malloc() if ptr is NULL, no need for separate malloc()
* (realloc() using temporary pointer to avoid mem-leak if realloc() fails)
*/
if (used == allocated) {
void *tmp = realloc (ptr, (allocated + 1) * sizeof *ptr);
if (tmp == NULL) { /* validate EVERY allocation */
perror ("realloc-tmp");
break; /* don't exit, ptr still good */
}
ptr = tmp; /* assign reallocaed block to ptr */
allocated += 1; /* increment after validation */
}
ptr[used] = b; /* assing b to ptr at index */
used += 1; /* increment after assignment */
/* debug output - remove if desired */
printf ("\nadding %d, used = %d, allocated = %d\n", b, used, allocated);
}
else if (strcmp (action, "remove") == 0) { /* ditto strmcp() */
if (used > 0) /* only decrement used if > 0, and */
used -= 1; /* (no need to adjust allocation) */
/* debug output, remove if desired */
printf ("\nremove, used = %d, allocated = %d\n", used, allocated);
}
/* debug output (no need to duplicate in each if .. else ...) */
puts ("\ncurrent content");
for (int i = 0; i < used; i++)
printf ("%d\n", ptr[i]);
}
/* [optional] final realloc to resize to exact size needed for used integers */
if (used < allocated) {
void *tmp = realloc (ptr, used * sizeof *ptr);
if (tmp) /* validate reallocation */
ptr = tmp; /* only assign after validation */
else /* otherwise just warn -- but original ptr still good */
perror ("realloc-ptr-to-used");
}
printf ("\nfinal statistics and stored values\n"
" allocated : %d\n"
" used : %d\n\n"
"stored values :\n", allocated, used);
for (int i = 0; i < used; i++)
printf ("%d\n", ptr[i]);
free (ptr); /* don't forget to free allocated memory */
}
Example Input File
Let's use an example input file (redirecting the file on stdin for program input) that exercises all parts of the program and includes garbage text that the program should ignore:
$ cat dat/add_remove.txt
alligators and other garbage
add
1 is the loneliest number that you ever knew.... (Three Dog Night)
add
2
add
3
add
4
remove
add
5
remove
remove
remove
remove
remove
add
6
add
7
remove
add
8
add
9
add
10
remove
This will add 1-10 and remove more integers than are stored at points and then pick up adding and removing more integers until all input is exhausted.
Example Use/Output
With the debug output shown in the code above the program output would be the following which at the end 6, 8, 9 are stored in your allocated block of memory:
$ ./bin/dyn_add_remove < dat/add_remove.txt
adding 1, used = 1, allocated = 1
current content
1
adding 2, used = 2, allocated = 2
current content
1
2
adding 3, used = 3, allocated = 3
current content
1
2
3
adding 4, used = 4, allocated = 4
current content
1
2
3
4
remove, used = 3, allocated = 4
current content
1
2
3
adding 5, used = 4, allocated = 4
current content
1
2
3
5
remove, used = 3, allocated = 4
current content
1
2
3
remove, used = 2, allocated = 4
current content
1
2
remove, used = 1, allocated = 4
current content
1
remove, used = 0, allocated = 4
current content
remove, used = 0, allocated = 4
current content
adding 6, used = 1, allocated = 4
current content
6
adding 7, used = 2, allocated = 4
current content
6
7
remove, used = 1, allocated = 4
current content
6
adding 8, used = 2, allocated = 4
current content
6
8
adding 9, used = 3, allocated = 4
current content
6
8
9
adding 10, used = 4, allocated = 4
current content
6
8
9
10
remove, used = 3, allocated = 4
current content
6
8
9
final statistics and stored values
allocated : 4
used : 3
stored values :
6
8
9
Memory Use/Error Check
In any code you write that dynamically allocates memory, you have 2 responsibilities regarding any block of memory allocated: (1) always preserve a pointer to the starting address for the block of memory so, (2) it can be freed when it is no longer needed.
It is imperative that you use a memory error checking program to ensure you do not attempt to access memory or write beyond/outside the bounds of your allocated block, attempt to read or base a conditional jump on an uninitialized value, and finally, to confirm that you free all the memory you have allocated.
For Linux valgrind is the normal choice. There are similar memory checkers for every platform. They are all simple to use, just run your program through it.
$ valgrind ./bin/dyn_add_remove < dat/add_remove.txt
==2698== Memcheck, a memory error detector
==2698== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2698== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2698== Command: ./bin/dyn_add_remove
==2698==
current content
adding 1, used = 1, allocated = 1
current content
1
<snip>
final statistics and stored values
allocated : 4
used : 3
stored values :
6
8
9
==2698==
==2698== HEAP SUMMARY:
==2698== in use at exit: 0 bytes in 0 blocks
==2698== total heap usage: 7 allocs, 7 frees, 5,172 bytes allocated
==2698==
==2698== All heap blocks were freed -- no leaks are possible
==2698==
==2698== For counts of detected and suppressed errors, rerun with: -v
==2698== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Always confirm that you have freed all memory you have allocated and that there are no memory errors.
There is a lot of subtle detail here, so slow down and take the time to go through it and understand why each part of the program is structured the way it was. Specifically understand why the check of if (used == allocated) allows you to reduce the "remove" actions to a check and subtracting 1 from used following else if (strcmp (action, "remove") == 0).
Look things over and let me know if you have further questions.
Footnotes:
malloc, calloc and realloc have changed from moving the program break (with brk) to provide allocations through memmap() which has reduced the allocation penalty but has not eliminated it entirely. An efficient allocation scheme that balances the growth in the allocated block against the number of reallocation calls is still good practice.
