Memory Allocation and Linked Lists

Memory Allocation


Memory allocation allows the programmer to allocate a block of memory of a desired size, and then store data into the block, along with initializing a pointer pointing to this block of memory. In order to do so, I'll explain the use of malloc(), realloc(), free(), and calloc().


malloc() will allocate a block of memory, although it will not initialize it, and returns a pointer to the block of memory allocated. The prototype of malloc() looks like: void malloc(size_t size);. size_t is an integer type defined in the C library, which is an unsigned integer. So, size is just an integer and represents the amount of bytes to be allocated. Since malloc() will return a pointer to a block of allocated memory, you need a pointer in order to make use of a call to malloc(), like so:

//Memory allocation for a character array of n number of elements

char *p;
p = malloc(n + 1);

//you could also do:

p = (char *) malloc(n + 1);

Since a character in C is one byte the, numerical argument for malloc() ends up just being a simple integer. However, if you were allocating memory for any other type of data you would need to use the sizeof() function to determine how much memory to allocate.

int *p;
p = malloc(sizeof(int));

//you could also do:

p = (char *) malloc(sizeof(int));

Just as a reminder, if you ever need to figure out how many elements an array has, use the following idiom: num_Elements = (sizeof(array) / sizeof(array[0])). That will take the size of all the elements divided by the size of a single element, giving you an integer resultant.


realloc() will change the size of a previously allocated block of memory. The prototype for realloc() is: void *realloc(void *ptr, size_t size);. ptr must point to a block of memory that was previously used in a call to malloc() or realloc(). The size parameter can be either larger or smaller than the original block.


calloc() is similar to malloc() in all ways except in that it initializes the bytes to 0 within the block.


free() is very easy to use; simply pass a pointer that points to a memory block we no longer need, and it will be available for reuse later on.


Linked Lists


A linked list is a chain of structures (called nodes), where each node contains a pointer to the next node in the chain. The last node in the list would contain a null pointer. The advantages of using a linked list over an array, is that you can add in nodes anywhere in the list you want, and you can delete nodes anywhere you want. You can also create many types of data structures like graphs and trees using linked lists.


Here are the barebones of a basic node:

struct node {
  //... here would be the node's data
  struct node *next;
};

To access a member of a structure through a pointer to a structure there is a "shortcut" operator called the right arrow selection operator ->. The right arrow selection operator allows you to access the member of a value pointed by a pointer. The following are equal:

(*node).data = 10;

//this is the same as:

node->data = 10;

In order to add a node to the beginning of the linked list, all you need to do is create a temporary variable to hold your new node, assign the value of your new node to the variable, and modify your new node to point to the old first node. Since adding a new node to the beginning of a list is such a common task, I'll show a sample function on how to do so. In order for a function to directly add a new node to a list, you need to be able to pass a pointer to the function and make it point elsewhere. Since arguments are passed by value, you can't simply pass a pointer to a function, since the function will then only be able to modify a copy of the pointer passed to it. Instead, you would need to pass a pointer to a pointer, then, you can make the pointer point elsewhere.

void add(struct node **list, int n)
{
  struct node *new_node;

  new_node = malloc(sizeof(struct node));
  if (new_node == NULL) //the macro NULL is defined in stdlib.h
  {
    printf("Error: Malloc failed to allocate necessary space.");
    exit(EXIT_FAILURE);
  }
  new_node->value = n;
  new_node->mext = *list;
  *list = new_node; //modifies the value pointed by list, which is a pointer
}

In the above example, list is a pointer to the first node in a linked list. Since we pass a pointer to a pointer (when we call this function we would use &first in the first argument, being the address of the first node), we are able to update the list pointer to point to our newly added node.


In order to search through a list, from beginning to end, you would usually use a for loop. The idiom is actually very simple. You scan the value and make your comparison on the first node, then make your iteration point to the next node:

for (p = first; p != NULL; p -> next)
  ... //whatever code you want to loop

Remember how I mentioned that the last node in the list contains a null pointer? The NULL macro defined in stdlib.h has the value of a NULL pointer, and as such the loop will stop on the last node of the list.


The idea behind deleting a node is to search for your desired deletion and make the previous node point to the node directly ahead of your node to be deleted. One method of doing so, is to keep a "trailing pointer". You scan through each node and keep a pointer to the node previously scanned, so that you can delete the current node and make the previous node point the next one in the list. Here is a sample function that searches for a node with a value inside of it (this value could be the node's ID, or whatever you are searching for) and deletes the node using free().

struct node *delete(struct node *list, val)
{
  struct node *current, *previous;

  for (current = list, previous = NULL;
       current != NULL && current -> data_Member != val;
       previous = current, current = current -> next)
    ;

  if (current == NULL)  //val was not found, end of list reached
    return list
  if (previous == NULL) //val was in the first node
    list = list -> next;
  else                  //val was found within a node
    prev -> next;
  
  free(current);
  return list;
}

The for loop in this function actually just has a null statement, because all the actions are done in the iteration portion of the for loop; the previous node is set to the currently being scanned, and the currently being scanned is set to the next node. The for loop stops once the value you are searching for is found, or if the end of the list is found. The two if and the else statements catch all the possible outcomes of the for loop. If the first node in the list is going to be deleted (if previous equals NULL), you need to make your list pointer point to the second node.

Structures Unions and Enumerations

Structures


Out of the three data types structures are the most important, so I'll start by going over them. Structures are similar to arrays in that they hold data. However, a structure's data is referenced by name rather than numerical index. The data inside structures is private; each new structure provides a new scope. Here is an example of how to declare a structure with a couple variables of that structure type:

struct {
  int ident;
  char name[LEN + 1];
  int val;
} part1, part2;

part1 and part2 are now both the exact same data-type, and each have the same members as each other. A structure can also be initialized while it is declared, like so:

struct {
  int ident;
  char name[LEN + 1];
  int val;
} part1 = {1, "Mobo", 200},
  part2 = {2, "PSU", 75};

Alternatively you can use the designator operator "." to assign values to structure members, like so:

struct {
  int ident;
  char name[LEN + 1];
  int val;
} part1 = {.ident = 1, .name = "Mobo", .val = 200},
  part2 = {.ident = 2, .name = "PSU", .val = 75};

It doesn't matter where in the initializer that a member is given a value if it is given a value by a designator. However, is there is no designator, then the value will be given to the corresponding member in the order from top to bottom of the structure, and from left to right of the initializer. LEN is just a constant defined in a preprocessor directive, and could be whatever the coder chose. You must add one to compensate for an end of line null character.

Structures of the same type can be copied with the = operator. Although, you cannot use the == or != whether or not structures are of the same type. part1 and part2 from the above example are both the exact same structure type. However, in the following example, part1 and part2 are not the exact same, and cannot be used with the = operator:

struct {
  int ident;
  char name[LEN + 1];
  int val;
} part1;

struct {
  int ident;
  char name[LEN + 1];
  int val;
} part2;

Since you can use the assignment operator with structures it is a slight surprise that arrays within structures will be copied from one to another. This can be useful for creating "dummy" structures that are used just for the purpose of copying one array to another.


So far I've shown two examples of declaring structures without using a structure tag. Once you've created a tag for a structure, you can treat a structure as a data type, like so:

struct pc_Hardware{
  int ident;
  char name[LEN + 1];
  int val;
};

struct pc_Hardware part1 =  {.ident = 1, .name = "Mobo", .val = 200};

It is also possible for a function to use a structure as an argument. However, using a structure as an argument can cause a lot of overhead. It's actually usually better to pass a pointer to a structure to a function, and then use the pointer to modify the members as needed. Functions can also return structures. Similarly, you might have a function return a pointer to a structure instead of an actual structure.

A structure can also be nested within another structure, as a data member. This is useful to create "categories" of members within a structure. Suppose you have a structure that holds data about computer hardware, and there are a total of four different brands of hardware. You could have each member of the structure represent a type of hardware, and within each structure you could hold information about the hardware brand.


Unions


A union is similar to a structure in all ways, except in that the compiler will allocate enough space for only the largest of all the union members. This means that all members of a union will all share the same space in memory. Altering one member of a union will overwrite the data of all others. This means that only one member of a union can hold data at any given time. Unions are usually used as a means of saving space. In my last computer hardware example, a union could have been used in place of a structure for holding the names of the brand, as the hardware usually wouldn't be made by two different companies at once (as long as the brand name doesn't go over the LEN limit, which is just a constant that can be defined as any amount you want to specify).


Arrays of unions can also be useful. Suppose you need an array that can hold either integers or floats. You can't simply create an array that can hold either, since an array must be universally one type. You can however create an array of unions rather easily. Consider this example:

union {
  int i;
  float f;
} Number;

Number a[100];

Now the array a can hold in each element either a float or integer type. Here is how one could assign either a float or integer into the array:

a[0].i = 1;
a[1].f = 10.01;

The biggest problem with using unions is that there is no way to tell which data member was last altered, and thus knowing which member actually holds a value. Often times programmers will nest a union within a structure, having the structure have one other data member. This other member within the structure will act as a "tag field" so that the programmer can keep track of which member holds a value.


Enumerations


Enumerations are good for creating new definitions of data types that have only a few different possible values. An enumeration would be good for creating a boolean variable, or perhaps a variable to represent suit in a deck of cards. The benefits of using an enumeration over preprocessor directives for defining such things is that anyone reading your code can easily see all the possible variants of your variable, and see that each one is of the same type. Enumerations can increase readability and code cleanliness.

enum suit { CLUBS, SPADES, DIAMONDS, HEARTS };

The above example shows how set up an enumeration for the different suits of a deck. This is much better than using #define directives, in that it obeys C's scope rules; an enumeration declared within a function won't affect the rest of the program. The members of this enumeration can be used just the same as #define directives.


The members of an enumeration are actually integers. CLUBS is equivalent to the integer 0, and HEARTS 3. One could use the suits defined in the above enumeration just as if SPADES were the integer 1, and so on. You can also specify exactly the integer amount that a member will equal, like so:

enum suit { CLUBS, SPADES = 7, DIAMONDS, HEARTS = 20 } s;

s = CLUBS;
s++;

CLUBS would default to 0, although DIAMONDS would default to 8, which is one more than the previous member. s was assigned the value of CLUBS (zero), then in the next line was incremented to 1.


Enumerations are perfect creating "tag fields" for unions to determine which of the members of a union were last modified. Here is an example:

struct {
  enum { INT, FLOAT } kind;
  union {
    int i;
    float f;
  } u;
} Number;

The above struct can be used in our original union example where an array of unions was created. This structure has advantages in that the programmer will be able to tell whether or not each array element holds an integer or float with the "tag field" kind.


Sources:  C Programming: A Modern Approach 2nd Ed. (particularly chapter 16)

Pointers: Basics

A pointer in C is a data type that holds the address to a specific block of memory within your computer's memory. The address in the pointer can be used to modify the contents thereof, or to cycle through other addresses in memory adjacent to such. It is also possible to use pointer arithmetic (addition and subtraction), though you cannot multiply or divide pointers. Take a look at the following diagram:

P is a pointer that has been declared and initialized with the value of the address 1884. P points to the block in memory next to the blocks with addresses of 1883 and 1885. C requires that every pointer point to only a specific type. There are no restrictions on what type of referenced data a pointer may reference to; pointers can even point to pointers.

int *p;
double *q;
char *r;


The above shows three ways of declaring a pointer as three different types of data. The only difference between declaring a pointer and a variable, is that a pointer's identifier must be preceded by the asterisk symbol.


Address and Dereference Operators


There are two different operators that are very commonly used with pointers. The first, which you've seen in the form of multiplication and when declaring a pointer, is the asterisk *, which is called the dereference operator (or also known as the indirection operator). You can translate the * literally into "the value pointed by". So, if we take P from our example above, and type *P, then *P means "the value pointed by" P. *P would equal whatever value is within the block of memory 1884. Actually, *P would be another alias for the value within the address 1884. This is because by modifying *P we actually directly modify the value within the address 1884. Suppose *P is an int value:

*p = 76;


This line of code would change the value within the address 1884 into the integer 76.


The second operator is the Address operator &. & can be translated literally into "the address of". This operator is particularly useful for assigning a value to a pointer, like so:

int val = 7;
int *p;
p = &val;

//You could also do:

int *p = &val;


Usually you wouldn't know exactly what the address of val is before assigning it to a pointer, as it could be anywhere within memory while your program is running. What is important, is that you can assign the address to a pointer.

Uses of Pointers

Imagine you need a function that modifies a variable. You cannot simply pass the variable to the function, since you can only pass the value of your variable to the function. This is due to the fact that the data within functions is private. You could however, pass a pointer to the function, and then use the dereference operator to directly modify the value pointed by the address. Consider the following:

#include <stdio.h>

int clear(int *x)
{
  *x = 0;
}

int main(void)
{
  int a = 5;

  clear(a);

  printf("%d", a);

  return 0;
}

You can also have a function return a pointer, like the following:

#include <stdio.h>

int *max( int *a, int *b)
{
  if (*a > *b)
    return a;
  else
    return b;
}

This function, when given pointers to two integers, will return a pointer to whichever integer is larger.


Pointers and arrays are used together all the time. Say we initialize pointer P and make it point to the first element of a[4]:

int a[4], *p;

p = &a[0];

Here is what we have just done graphically:

P now points to the first element of array a[]. Suppose we do the following:

*p = 7;

a[0] now equals 7. Here is what we have just done graphically:

So far this whole process doesn't seem too useful, but, where things start getting really useful is when you use pointer arithmetic to cycle through each element of the array using a pointer. C allows the following combinations of pointer arithmetic, and only these combination:

Adding an integer to a pointer

Subtracting an integer from a pointer

Subtracting one pointer from another pointer

Adding integer i to pointer P will cause P to point i elements ahead from where P originally pointed to. Similarly, if P points to a[x], then P + i points to a[x + i] (assuming a[x + i] even exists).

If P points to element a[x], then P - i points to a[x - i].

When one pointer is subtracted from another, the result is the distance in array elements from the two pointers.

It is also valid to compare pointers with the comparisons ==, !=, <=, and >=. However, in order for these comparisons to actually have meaning the two pointers being compared would need to point within the same array.

Pointers are also good for processing arrays, since you can apply addition and subtraction upon pointers. Though one could just as easily use array subscripting for such a task, pointers can be faster and less resource intensive (depending on the compiler; some compilers have no efficiency discrepancy between array subscripting and array processing via pointers).

#define VAL 10

int a[VAL], *p;

sum = 0;
for (p = &a[0]; p < &a[VAL]; p++)
  sum += *p;

The above code fragment shows how to sum all elements of an array with p. Note that this loop will not fire once p equals a[VAL], due to the properties of a for loop, thus the address a[VAL] won't actually be analyzed and the program will not produce an error during compilation.


A very important thing to note, is that the name of an array can be used as a pointer to the first element of an array.

int a[5];

*a = 7; //stores 7 in a[0]

*(a + 1) = 12; //stores 12 in a[1]

In general, a + i is the same as &a[i]. Also, *(a + i) is equivalent to a[i]. Also, the fact that an array name can serve as a pointer makes it easier to process them with for loops.

for (p = &a[0]; p < &a[VAL]; p++)
  sum += *p;

//this is the same as the following:

for (p =a; p < a + VAL; p++)
  sum += *p;

When passing an array to a function, the compiler passes a pointer to the first element in the array to the function. This is important to know.


Using all that I've explained so far, you can write loops to process both rows or columns of 2D arrays using pointers, like so (processing a row):

//loop that clears a row of a 2D array

int a[rows][cols], *p, row;

row = x; //x is an integer that represents our selected row 

for (p = a[row]; p < a[i] + cols; p++)
  *p = 0;

Processing a column isn't as simple, since a 2D array has the first array be an array of arrays, meaning it's an array of rows.

//loop that clears a column of a 2D array

int a[rows][cols], (*p)[cols], col;

col = x; //x is an integer that represents our selected column

for (p = a; p < a[rows]; p++)
  (*p)[col] = 0;

I have declared p to be a pointer to an array of integers, which will be used as a row in the loop. The parentheses are necessary to be around the *p, otherwise p would be an array of pointers rather than a pointer to an array. In the expression p = a, a is equal to the address of a[0]. We know this from recalling the earlier quote:

In general, a + i is the same as &a[i]. Also, *(a + i) is equivalent to a[i].

Sources for this post:
* C Programming: A Modern Approach 2nd Ed. (particularly chapter 12)

2D Array Practice

In the book C Programming a Moder Approach Second Edition there is a programming project at the end of chapter 8 that asks you to write a program that creates a randomized walk across a 10x10 field, where each step is shown as a letter from the alphabet, and each blank space is shown as a period. The end result should look something like this:

a . . . . . . . . .
b c . . . . . . . .
e d . . . p q r . .
f . . . . o . s . .
g h i j . n u t . .
. . . k l m v . . .
. . . . . . w . . .
. . . . z y x . . .
. . . . . . . . . .
. . . . . . . . . .


In order to do this, you initialize a 2D array, fill it with periods, randomly choose a number between 0-3 to represent a direction to move, detect if the move was a valid move (and re-randomize the move if it wasn't), then make the move chosen. Each time a move is chosen, use a new letter from the alphabet.


Overall, this was extremely simple. If I were writing this program without such specific rules as the programming book gave me, I would have made the array 12x12 instead of 10x10. This would allow me to line the edges with a value other than ".", and I could use that value on the edges to detect collision. This is a lot simpler than detecting if it is the edge of the array, since I can't simply use if board[y][x + 1] != '.', as a period can't exist out of the edge of the arrays.


I'll post the source code the most interesting part of the program:

for (column = 0; column < 10; column++)
{
  for (row = 0; row < 10; row++)
  {
    printf("%c ", board[column][row]);
  }
  printf("\n");
}

This cycles through the first row, and prints out all the contents. It does this by adding one to column during each iteration, and printing out a piece of the board using the token column as a coordinate. The same thing happens with the row token as well. Then, the next row, and the next row. Just before these two for loops I modify the current field and place a letter in wherever the current coordinates are, so that these two loops print out the move that just occurred as a letter.


Overall I didn't learn anything new, but I still needed to write this program in order to get used to the syntax of C. Here is the source and .exe for the full program.


PRNGs (Pseudo-Random Number Generator)

Computers cannot truly generate random numbers, as computers are simply mechanisms that react to actions that are enacted upon them. In order to compensate for this, to generate a random number computers use a PRNG (pseudo random number generator). PRNGs can generate seemingly random numbers rather effectively.

One way to generate a random number in C is to use the rand() function, which is lies within the standard library of C. Here is an example:

#include <stdio.h> /* included for printf */
#include <stdlib.h> /* included for rand */

int main(void)
{
  int i;

  for (i = 0; i < 10; i++)
    printf("%i\n", rand());

  return 0;
}

Depending on your compiler, the output of this program will output ten numbers. However, this program will always output the same ten numbers in the same order. I've learned that the GCC compiler will have the rand() function return a value with an upper bound of 2,147,483,647 (2³²-1), compared to upper bounds of 32,767 (2¹⁶-1) from most other compilers.


In order to have this program output different numbers each time it is run, you need to do what is called seeding the PRNG. Seeding will affect the sequence in which the rand() function begins outputting numbers. In order to seed the rand() function, you use srand(). Here is an example:

#include <stdio.h> /* included for printf */
#include <stdlib.h> /* included for rand */

int main(void)
{
  int i;

  srand(1)
  for (i = 0; i < 10; i++)
    printf("%i\n", rand());

  return 0;
}

This seeded the PRNG with the integer 1, and will now output ten different numbers than the last program. Although, this still doesn't solve our problem; how do we randomly seed the PRNG? In order to do so, you can use the time() function. The time() function will return the number of seconds elapsed since Jan 1st 1970. This is the method of randomly seeding that DigiPen has shown their Freshman incoming students. Example:

#include <stdio.h> /* included for printf */
#include <stdlib.h> /* included for rand */

int main(void)
{
  int i;

  srand(time(0));
  for (i = 0; i < 10; i++)
    printf("%i\n", rand());

  return 0;
}

Now this program will produce a different set of numbers every time it is run. Although, what if you wanted to produce a random number within a specific range? You could use the modulo operator, like so:

#include <stdio.h> /* included for printf */
#include <stdlib.h> /* included for rand */

int main(void)
{
  int i;

  srand(time(0));
  for (i = 0; i < 10; i++)
    printf("%i\n", rand() % 10 + 1); //Random int from 1-10

  return 0;
}

Although I've been told this is error-prone and tedious, and it is much preferred to create your own wrapper function around rand().

int randomInt(int low, int high)
{
  return (rand() % (high - low + 1) + low);
}