When we declare an array, we need to reserve some memory to store the elements of this array. This memory allocation and it is static. That is when we declare an array, we specify the number of elements in that array and a fixed memory is allocated. Once declared the size of the array cannot be changed.
But there are situations in which we may want to declare the variable and not allocate memory for it until we use that variable. We may also want to free the memory allocated for a variable after its use is over.
Dynamic allocation is a pretty unique feature to C (amongst high level languages). It enables us to create data types and structures of any size and length to suit our programs need within the program.
We will look at two common applications of this:
dynamic arrays
dynamic data structure e.g. linked lists
Malloc, Sizeof, and Free
The Function malloc is most commonly used to attempt to ``grab'' a continuous portion of memory. It is defined by:
void *malloc(size_t number_of_bytes)
That is to say it returns a pointer of type void * that is the start in memory of the reserved portion of size number_of_bytes. If memory cannot be allocated a NULL pointer is returned.
Since a void * is returned the C standard states that this pointer can be converted to any type. The size_t argument type is defined in stdlib.h and is an unsigned type.
So:
char *cp;
cp = malloc(100);
attempts to get 100 bytes and assigns the start address to cp.
Also it is usual to use the sizeof() function to specify the number of bytes:
int *ip;
ip = (int *) malloc(100*sizeof(int));
Some C compilers may require to cast the type of conversion. The (int *) means coercion to an integer pointer. Coercion to the correct pointer type is very important to ensure pointer arithmetic is performed correctly. I personally use it as a means of ensuring that I am totally correct in my coding and use cast all the time.
It is good practice to use sizeof() even if you know the actual size you want -- it makes for device independent (portable) code.
sizeof can be used to find the size of any data type, variable or structure. Simply supply one of these as an argument to the function.
SO:
int i;
struct COORD {float x,y,z};
typedef struct COORD PT;
sizeof(int), sizeof(i),
sizeof(struct COORD) and
sizeof(PT) are all ACCEPTABLE
In the above we can use the link between pointers and arrays to treat the reserved memory like an array. i.e we can do things like:
ip[0] = 100;
or
for(i=0;i<100;++i) scanf("%d",ip++);
When you have finished using a portion of memory you should always free() it. This allows the memory freed to be aavailable again, possibly for further malloc() calls
The function free() takes a pointer as an argument and frees the memory to which the pointer refers.
Calloc and Realloc
There are two additional memory allocation functions, Calloc() and Realloc(). Their prototypes are given below:
void *calloc(size_t num_elements, size_t element_size};
void *realloc( void *ptr, size_t new_size);
Malloc does not initialise memory (to zero) in any way. If you wish to initialise memory then use calloc. Calloc there is slightly more computationally expensive but, occasionally, more convenient than malloc. Also note the different syntax between calloc and malloc in that calloc takes the number of desired elements, num_elements, and element_size, element_size, as two individual arguments.
Thus to assign 100 integer elements that are all initially zero you would do:
int *ip;
ip = (int *) calloc(100, sizeof(int));
Realloc is a function which attempts to change the size of a previous allocated block of memory. The new size can be larger or smaller. If the block is made larger then the old contents remain unchanged and memory is added to the end of the block. If the size is made smaller then the remaining contents are unchanged.
If the original block size cannot be resized then realloc will attempt to assign a new block of memory and will copy the old block contents. Note a new pointer (of different value) will consequently be returned. You must use this new value. If new memory cannot be reallocated then realloc returns NULL.
Thus to change the size of memory allocated to the *ip pointer above to an array block of 50 integers instead of 100, simply do:
ip = (int *) calloc( ip, 50);
Linked Lists
Let us now return to our linked list example:
typedef struct { int value;
ELEMENT *next;
} ELEMENT;
We can now try to grow the list dynamically:
link = (ELEMENT *) malloc(sizeof(ELEMENT));
This will allocate memory for a new link.
If we want to deassign memory from a pointer use the free() function:
free(link)
See Example programs (queue.c) below and try exercises for further practice.
Full Program: queue.c
A queue is basically a special case of a linked list where one data element joins the list at the left end and leaves in a ordered fashion at the other end.
The full listing for queue.c is as follows:
/* */
/* queue.c */
/* Demo of dynamic data structures in C */
#include <stdio.h>
#define FALSE 0
#define NULL 0
typedef struct {
int dataitem;
struct listelement *link;
} listelement;
void Menu (int *choice);
listelement * AddItem (listelement * listpointer, int data);
listelement * RemoveItem (listelement * listpointer);
void PrintQueue (listelement * listpointer);
void ClearQueue (listelement * listpointer);
main () {
listelement listmember, *listpointer;
int data,
choice;
listpointer = NULL;
do {
Menu (&choice);
switch (choice) {
case 1:
printf ("Enter data item value to add ");
scanf ("%d", &data);
listpointer = AddItem (listpointer, data);
break;
case 2:
if (listpointer == NULL)
printf ("Queue empty!\n");
else
listpointer = RemoveItem (listpointer);
break;
case 3:
PrintQueue (listpointer);
break;
case 4:
break;
default:
printf ("Invalid menu choice - try again\n");
break;
}
} while (choice != 4);
ClearQueue (listpointer);
} /* main */
void Menu (int *choice) {
char local;
printf ("\nEnter\t1 to add item,\n\t2 to remove item\n\
\t3 to print queue\n\t4 to quit\n");
do {
local = getchar ();
if ((isdigit (local) == FALSE) && (local != '\n')) {
printf ("\nyou must enter an integer.\n");
printf ("Enter 1 to add, 2 to remove, 3 to print, 4 to quit\n");
}
} while (isdigit ((unsigned char) local) == FALSE);
*choice = (int) local - '0';
}
listelement * AddItem (listelement * listpointer, int data) {
listelement * lp = listpointer;
if (listpointer != NULL) {
while (listpointer -> link != NULL)
listpointer = listpointer -> link;
listpointer -> link = (struct listelement *) malloc (sizeof (listelement));
listpointer = listpointer -> link;
listpointer -> link = NULL;
listpointer -> dataitem = data;
return lp;
}
else {
listpointer = (struct listelement *) malloc (sizeof (listelement));
listpointer -> link = NULL;
listpointer -> dataitem = data;
return listpointer;
}
}
listelement * RemoveItem (listelement * listpointer) {
listelement * tempp;
printf ("Element removed is %d\n", listpointer -> dataitem);
tempp = listpointer -> link;
free (listpointer);
return tempp;
}
void PrintQueue (listelement * listpointer) {
if (listpointer == NULL)
printf ("queue is empty!\n");
else
while (listpointer != NULL) {
printf ("%d\t", listpointer -> dataitem);
listpointer = listpointer -> link;
}
printf ("\n");
}
void ClearQueue (listelement * listpointer) {
while (listpointer != NULL) {
listpointer = RemoveItem (listpointer);
}
}
C Programming:
Dynamic Memory Allocation in C program Example
Dynamic Memory Allocation For 2D Array in C Program Example
According to wikipedia.org
But there are situations in which we may want to declare the variable and not allocate memory for it until we use that variable. We may also want to free the memory allocated for a variable after its use is over.
Dynamic Memory Allocation and Dynamic Structures
Dynamic allocation is a pretty unique feature to C (amongst high level languages). It enables us to create data types and structures of any size and length to suit our programs need within the program.
We will look at two common applications of this:
dynamic arrays
dynamic data structure e.g. linked lists
Malloc, Sizeof, and Free
The Function malloc is most commonly used to attempt to ``grab'' a continuous portion of memory. It is defined by:
void *malloc(size_t number_of_bytes)
That is to say it returns a pointer of type void * that is the start in memory of the reserved portion of size number_of_bytes. If memory cannot be allocated a NULL pointer is returned.
Since a void * is returned the C standard states that this pointer can be converted to any type. The size_t argument type is defined in stdlib.h and is an unsigned type.
So:
char *cp;
cp = malloc(100);
attempts to get 100 bytes and assigns the start address to cp.
Also it is usual to use the sizeof() function to specify the number of bytes:
int *ip;
ip = (int *) malloc(100*sizeof(int));
Some C compilers may require to cast the type of conversion. The (int *) means coercion to an integer pointer. Coercion to the correct pointer type is very important to ensure pointer arithmetic is performed correctly. I personally use it as a means of ensuring that I am totally correct in my coding and use cast all the time.
It is good practice to use sizeof() even if you know the actual size you want -- it makes for device independent (portable) code.
sizeof can be used to find the size of any data type, variable or structure. Simply supply one of these as an argument to the function.
SO:
int i;
struct COORD {float x,y,z};
typedef struct COORD PT;
sizeof(int), sizeof(i),
sizeof(struct COORD) and
sizeof(PT) are all ACCEPTABLE
In the above we can use the link between pointers and arrays to treat the reserved memory like an array. i.e we can do things like:
ip[0] = 100;
or
for(i=0;i<100;++i) scanf("%d",ip++);
When you have finished using a portion of memory you should always free() it. This allows the memory freed to be aavailable again, possibly for further malloc() calls
The function free() takes a pointer as an argument and frees the memory to which the pointer refers.
Calloc and Realloc
There are two additional memory allocation functions, Calloc() and Realloc(). Their prototypes are given below:
void *calloc(size_t num_elements, size_t element_size};
void *realloc( void *ptr, size_t new_size);
Malloc does not initialise memory (to zero) in any way. If you wish to initialise memory then use calloc. Calloc there is slightly more computationally expensive but, occasionally, more convenient than malloc. Also note the different syntax between calloc and malloc in that calloc takes the number of desired elements, num_elements, and element_size, element_size, as two individual arguments.
Thus to assign 100 integer elements that are all initially zero you would do:
int *ip;
ip = (int *) calloc(100, sizeof(int));
Realloc is a function which attempts to change the size of a previous allocated block of memory. The new size can be larger or smaller. If the block is made larger then the old contents remain unchanged and memory is added to the end of the block. If the size is made smaller then the remaining contents are unchanged.
If the original block size cannot be resized then realloc will attempt to assign a new block of memory and will copy the old block contents. Note a new pointer (of different value) will consequently be returned. You must use this new value. If new memory cannot be reallocated then realloc returns NULL.
Thus to change the size of memory allocated to the *ip pointer above to an array block of 50 integers instead of 100, simply do:
ip = (int *) calloc( ip, 50);
Linked Lists
Let us now return to our linked list example:
typedef struct { int value;
ELEMENT *next;
} ELEMENT;
We can now try to grow the list dynamically:
link = (ELEMENT *) malloc(sizeof(ELEMENT));
This will allocate memory for a new link.
If we want to deassign memory from a pointer use the free() function:
free(link)
See Example programs (queue.c) below and try exercises for further practice.
Full Program: queue.c
A queue is basically a special case of a linked list where one data element joins the list at the left end and leaves in a ordered fashion at the other end.
The full listing for queue.c is as follows:
/* */
/* queue.c */
/* Demo of dynamic data structures in C */
#include <stdio.h>
#define FALSE 0
#define NULL 0
typedef struct {
int dataitem;
struct listelement *link;
} listelement;
void Menu (int *choice);
listelement * AddItem (listelement * listpointer, int data);
listelement * RemoveItem (listelement * listpointer);
void PrintQueue (listelement * listpointer);
void ClearQueue (listelement * listpointer);
main () {
listelement listmember, *listpointer;
int data,
choice;
listpointer = NULL;
do {
Menu (&choice);
switch (choice) {
case 1:
printf ("Enter data item value to add ");
scanf ("%d", &data);
listpointer = AddItem (listpointer, data);
break;
case 2:
if (listpointer == NULL)
printf ("Queue empty!\n");
else
listpointer = RemoveItem (listpointer);
break;
case 3:
PrintQueue (listpointer);
break;
case 4:
break;
default:
printf ("Invalid menu choice - try again\n");
break;
}
} while (choice != 4);
ClearQueue (listpointer);
} /* main */
void Menu (int *choice) {
char local;
printf ("\nEnter\t1 to add item,\n\t2 to remove item\n\
\t3 to print queue\n\t4 to quit\n");
do {
local = getchar ();
if ((isdigit (local) == FALSE) && (local != '\n')) {
printf ("\nyou must enter an integer.\n");
printf ("Enter 1 to add, 2 to remove, 3 to print, 4 to quit\n");
}
} while (isdigit ((unsigned char) local) == FALSE);
*choice = (int) local - '0';
}
listelement * AddItem (listelement * listpointer, int data) {
listelement * lp = listpointer;
if (listpointer != NULL) {
while (listpointer -> link != NULL)
listpointer = listpointer -> link;
listpointer -> link = (struct listelement *) malloc (sizeof (listelement));
listpointer = listpointer -> link;
listpointer -> link = NULL;
listpointer -> dataitem = data;
return lp;
}
else {
listpointer = (struct listelement *) malloc (sizeof (listelement));
listpointer -> link = NULL;
listpointer -> dataitem = data;
return listpointer;
}
}
listelement * RemoveItem (listelement * listpointer) {
listelement * tempp;
printf ("Element removed is %d\n", listpointer -> dataitem);
tempp = listpointer -> link;
free (listpointer);
return tempp;
}
void PrintQueue (listelement * listpointer) {
if (listpointer == NULL)
printf ("queue is empty!\n");
else
while (listpointer != NULL) {
printf ("%d\t", listpointer -> dataitem);
listpointer = listpointer -> link;
}
printf ("\n");
}
void ClearQueue (listelement * listpointer) {
while (listpointer != NULL) {
listpointer = RemoveItem (listpointer);
}
}
C Programming:
Dynamic Memory Allocation in C program Example
Dynamic Memory Allocation For 2D Array in C Program Example
Dynamic Memory Allocation
Dynamic memory allocation is when an executing program requests that the operating system give it a block of main memory. The program then uses this memory for some purpose. Usually the purpose is to add a node to a data structure. In object oriented languages, dynamic memory allocation is used to get the memory for a new object.
The memory comes from above the static part of the data segment. Programs may request memory and may also return previously dynamically allocated memory. Memory may be returned whenever it is no longer needed. Memory can be returned in any order without any relation to the order in which it was allocated. The heap may develop "holes" where previously allocated memory has been returned between blocks of memory still in use.
A new dynamic request for memory might return a range of addresses out of one of the holes. But it might not use up all the hole, so further dynamic requests might be satisfied out of the original hole.
If too many small holes develop, memory is wasted because the total memory used by the holes may be large, but the holes cannot be used to satisfy dynamic requests. This situation is called memory fragmentation. Keeping track of allocated and deallocated memory is complicated. A modern operating system does all this.
C dynamic memory allocation refers to performing manual memory management for dynamic memory allocation in the C programming language via a group of functions in the C standard library, namely malloc, realloc, calloc and free.
Many different implementations of the actual memory allocation mechanism, used by malloc, are available. Their performance varies in both execution time and required memory.
The C programming language manages memory statically, automatically, or dynamically. Static-duration variables are allocated in main memory, usually along with the executable code of the program, and persist for the lifetime of the program; automatic-duration variables are allocated on the stack and come and go as functions are called and return. For static-duration and automatic-duration variables, the size of the allocation must be compile-time constant (except in C99, which allowed variable-length automatic arrays). If the required size is not known until run-time (for example, if data of arbitrary size is being read from the user or from a disk file), then using fixed-size data objects is inadequate.
The lifetime of allocated memory can also cause concern. Neither static- nor automatic-duration memory is adequate for all situations. Automatic-allocated data cannot persist across multiple function calls, while static data persists for the life of the program whether it is needed or not. In many situations the programmer requires greater flexibility in managing the lifetime of allocated memory.
These limitations are avoided by using dynamic memory allocation in which memory is more explicitly (but more flexibly) managed, typically, by allocating it from the free store (informally called the "heap"), an area of memory structured for this purpose. In C, the library function malloc is used to allocate a block of memory on the heap. The program accesses this block of memory via a pointer that malloc returns. When the memory is no longer needed, the pointer is passed to free which deallocates the memory so that it can be used for other purposes.
malloc() can also avoid system calls by utilising fast bins.
Some platforms provide library calls which allow run-time dynamic allocation from the C stack rather than the heap (e.g. alloca()). This memory is automatically freed when the calling function ends.