When variables of array, struct and numeric types are declared, the C compiler sets aside (allocates) memory to hold the values of these variables. The size of all such variables is known when the program is compiled. Consequences for programs that use only variables of these types:
Solution: allow a program to ask for more memory as it runs, and let programs give up memory that is no longer needed
The function malloc() from <stdlib.h>
returns the address of a chunk of memory newly allocated to the
program. When allocating memory this way, an address is called a
pointer.
Prototype of malloc():
void *malloc(size_t size);
malloc() returns a pointer to size bytes of newly
allocated memory. Type size_t is basically int.
Type void * is the generic pointer (address) type. The result
of calling malloc() must be cast (coerced) to the appropriate
address type before it can be used.
Example: allocating memory to hold an int. Function
sizeof() takes a typename and returns the number of bytes of
memory needed to store a value of that type.
#include <stdio.h>
#include <stdlib.h>
main() {
int *ptr;
ptr = (int *) malloc(sizeof(int));
/* here:
we don't write *ptr because malloc() returns
an address, not a value
the cast (int *) converts pointer to void
to pointer to int
the call: sizeof(int) returns the number of
bytes needed to store an int
*/
/* put a value in the newly allocated memory */
*ptr = 27;
}
malloc() returns NULL if sufficient memory
isn't available to satisfy the memory request.
Example: what happens if malloc() isn't used:
#include <stdlib.h>
main() {
int *ptr;
*ptr = 27;
}
This can cause the program to crash or misbehave, because the assignment writes to memory that isn't allocated to the program.
Example:
#include <stdio.h>
#include <stdlib.h>
main() {
int i;
int *ptr;
ptr = &i;
*ptr = 27;
/* the following prints 27 */
printf("%d", i);
}
This is not an error - the compiler allocates memory for variable
i, and the first assignment makes ptr point
to that memory. Because *ptr and i both refer
to the value stored at the same location in memory, the printf()
prints 27.
Two expressions (names) are aliased if they refer to the value of the same location in memory.
Example:
#include <stdio.h>
#include <stdlib.h>
main() {
int i;
int *ptr;
ptr = &i;
*ptr = 27;
/* the following prints 27 */
printf("%d", i);
i = 34;
/* the following prints 34 */
printf("%d", *ptr);
}
Because i and *ptr refer to the same spot in
memory, any change in one changes the other.
idea:
Example:
#include <stdio.h>
#define BIG 297
main() {
int memory[BIG];
int ptr1, ptr2;
/* A */ ptr1 = 3;
/* B */ ptr2 = ptr1;
/* now ptr2 refers to the same spot in
memory as ptr1 */
/* C */ memory[ptr1] = 7;
/* like: *ptr1 = 7; */
printf("The value at ptr2 is: %d", memory[ptr2]);
}
Discussion: what value is printed?
A picture of memory:
With real pointers:
#include <stdio.h>
#include <stdlib.h>
main() {
int *ptr1, *ptr2;
/* A */ ptr1 = (int *) malloc(sizeof(int));
/* B */ ptr2 = ptr1;
/* now ptr2 refers to the same spot in
memory as ptr1 -- they are aliased */
/* C */ *ptr1 = 7;
printf("The value at ptr2 is: %d", *ptr2);
}
Discussion: what value is printed?
Memory is returned to the system using the free() function
from <stdlib.h>.
Its prototype is:
void free(void *genptr);
so the memory being freed must be referred to by a pointer to
void. This is done by calling free() with the
argument pointer cast to void *.
Example:
#include <stdio.h>
#include <stdlib.h>
main() {
double *dptr;
dptr = (double *) malloc(sizeof(double));
/* code using dptr here */
/* done using dptr -- free the memory */
free((void *) dptr);
/* don't refer to dptr here -- it no longer
refers to memory that belongs to this
program */
}
Programs should never refer to (or write to) memory that has been returned
using free(), because some other part of the program could
be using it (and so bad things will happen).
If the size needed for an array can only be determined after the program starts running, allocate memory for it at runtime. Ideas:
#include <stdio.h>
#include <stdlib.h>
main() {
int size; int count;
double *newarray;
printf("How many numbers do you need to store?");
scanf("%d", &size);
/* should check that size >= 0 */
newarray = (double *) malloc(sizeof(double) * size);
/* pointer newarray can now be treated just like
an array of doubles */
for (count = 0; count < size; count++) {
printf("Enter next number: ");
scanf("%lf", &newarray[count]);
}
/* do something with the numbers in the
"array" newarray */
/* done with newarray, so free the memory */
free((void *) newarray);
}
Note that the program still needs to specify a size for the array.
Ideas:
Example:
NULL
to indicate that there is no more valid data
double
typedef struct node {
double data;
struct node *next;
/* pointer to the next node
in the list */
} listnode;
next is declared, type listnode is not
yet defined.
We'll use a variable head to keep track of the list. Initially
the list is empty:
listnode *head = NULL;
Example: a program that inserts doubles into a linked list.
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
double data;
struct node *next;
} listnode;
listnode *insert(double, listnode *);
main() {
listnode *head = NULL;
listnode *cur;
head = insert(5.1, head);
head = insert(68.4, head);
/* print out all the values in the list */
cur = head;
while (cur != NULL) {
printf("Current value: %lf.\n", cur->data);
cur = cur->next;
}
}
listnode *insert(double d, listnode *thelist) {
/* d is the data
thelist is the current list
return the new list (with d as the first item) */
listnode * tem;
tem = (listnode *) malloc(sizeof(listnode));
if (tem == NULL) {
/* check that memory could be allocated */
printf("Out of memory. Halting.\n");
exit(1);
} else {
/* fill in the data field */
tem->data = d;
/* set the next field of tem to point to the
rest of the list */
tem->next = thelist;
}
/* return the new list */
return(tem);
}
It is safe to return tem from insert, because
the memory tem points to has been allocated. See
~taw2/pub/linked.c for a more complete
example.