CS50 - Section 7

Section Information


malloc and friends

malloc

Ask UNIX for a new chunk of memory. The chunk initially contains undefined (random) values.

free

Give a chunk of memory back to UNIX.

Note- only free memory that was allocated with malloc (or one of the related functions). Do not free other memory!

sizeof

A C operator that returns the number of bytes in an variable or type.

Note- sizeof does not work properly with strings. If you want to find the number of bytes used by a string, you must do it different way- by using strlen or StringLength to compute the length (and then adding one to hold space for the '\0' that lives on the ends of all strings!).

NULL

The canonical ``invalid'' or ``empty'' pointer is called NULL. A value of NULL is used to indicate that the pointer doesn't point anywhere valid.

If you call a function that is supposed to return a pointer, and the pointer it returns to you is NULL, it generally means that something has gone wrong.

void pointers

A void pointer is a pointer to anything. Unlike void, (which is C's way to say ``nothing'') a void pointer can point at anything. Before it can be dereferenced, however, it must be cast to be a pointer of the appropriate type.


Structs and Pointers

Given any variable of some struct type, we access elements inside the structure in the following way:

	struct_variable.field

Things are a bit different if we have a pointer to a given structure type. In that case, elements inside the structure are accessed (via dereferencing) in the following manner :

	struct_pointer->field

For example:

	struct date {
	       int year, month, day;
	};

	struct date	today, tomorrow;
	struct date	*tomorrowp;
	int		month, year;

	tomorrowp = &tomorrow;
	month = today.month;
	year = tomorrowp->year;

Questions:

Be careful not to dereference NULL pointers! Make sure that the struct pointer (or any pointer for that matter) that you wish to dereference is a valid pointer before deref'ing it!


Arrays and Pointers in C

In C, there are strong relationships between pointers and arrays. For any one-dimensional array A and integer expression x, the following relationships are always true:

&A[0] == A

As far as C is concerned, A is just the address of the first element of the array A itself.

&A[x] == A + x

This is one of the great truths of the C programming language, and a defining characteristic of the language.

This equality defines the nature of pointer arithmetic, which defines how the + (aka addition) operator works with pointers.

When an integer x is added to the a pointer A, the result is a pointer that points to the memory location of the x'th thing of whatever type A points to.

For example, if A is a pointer to an int, then A + 5 points to the memory address that is "five ints after" A. On the HP machines, where sizeof(int) is 4, this is the same as adding 20 to the value of A.

Note that the first relation (&A[0] == A) can be seen as a special case of this condition.

A[x] == *(A + x)

Looking closely at this relationship and bringing your powerful knowledge of pointers to bear, you should notice that this relationship follows immediately from the previous relationship-- we're just deref'ing both sides of the equality, so that instead of dealing with pointers we're dealing with the things being pointed at.

We can use these relationships in either direction-- we can treat arrays like pointers (useful in some situations), and we can treat pointers like arrays (very useful in many situations, including some you will face in assignment 6).

For example, consider the following code:

double		*array_of_doubles;

array_of_doubles = (double *) malloc (20 * sizeof (double));

In this code snippet, we've declared a variable named array_of_doubles to be a pointer to a double, and then allocated (via malloc) enough space to hold 20 consecutive doubles, and assigned the resulting pointer to array_of_doubles.

Now, thanks to the properties of C stated earlier and the fact that array_of_doubles points to enough space to hold 20 doubles, we can treat array_of_doubles as if it had been defined to be an array of 20 doubles all along. Even better, we can decide at runtime whether the array should be 20, 200, or 2,000,000 million doubles in length (while there is no way to dynamically chose the size of arrays). Best of all, when we're finished with this memory, we can give it back to the system (via free).

Pointers allow us to write code that uses exactly as much memory as we need, when we need it (and then give it back when we don't need it any longer) while still allowing us to write code using the notational simplicity of arrays. Splendid!

Also note that we can have arrays of pointers:

double		**double_pointers;

double_pointers = (double **) malloc (16 * sizeof (double *));

This is as if we had created an array of 16 pointers to doubles.

Since we know that a string (from the Roberts libraries) is nothing more than a char *, we can create an array of 10 strings in a similar manner:

char		**strings;

strings = (char **) malloc (10 * sizeof (char *));


Assignment 6

This assignment is relatively hard, and may take a lot of time to complete. Get started on it early!

Doubly Linked Lists

Doubly linked lists are similar to singly linked lists, except that each list cell contains pointers to both the previous and next elements (instead of just the next element). This may seem like it will make things more complicated; but actually it makes many operations easier.

For this assignment, pay close attention to the descriptions of the functions you must write. You should also use the llist program in order to see how your program should behave- when the Student List looks the same as the Debugging List, your code is working. If the two look different, then something is wrong with your code.

When you are writing your routines, you should feel free to use the llist_dbg routines as placeholders for your own routines. Your routines should do exactly the same things as these routines, so until you are finished with your own functions, you can just use these functions as placeholders. This can be very useful when you are debugging!

Errata

There are two errors that have been noted on assignment 6. Both may have the potential to cause some amount of confusion, so please make a note of this:

  1. At the bottom of pages 1 and 4: llist_destroy returns void, not void *. The correct prototype is:

    	void llist_destroy (llist_t *cell); 
    	

    It is correct in the llist.h and llist.c files that are online.

  2. The description of llist_destroy is incorrect. At the bottom of page 4, the second to last paragraph should read:

    This function releases the resources allocated to a single llist_t struct by llist_create, by free'ing that element (to return it to the pool of memory available to your program).

    The stuff about "each element of the list" is all wrong; llist_destroy destroys exactly one list element, not a whole lists' worth.


UNIX Utilities

Rather than include a handful more vi commands, this week I'd rather mention some other useful UNIX utilities that manipulate text.

spell

The spell program is the original spell checker for UNIX. It makes it easy to check your text files (such as the answers to your written exercises) for spelling errors. See the manual page for more information.

A more interactive spell-checking program, called ispell, is becoming more popular.

adjust

UNIX also includes a tool named adjust, which helps to format text so that it looks good on the screen or printed page. The manual page for adjust includes instructions for running it from inside vi.

indent

The indent reformats C programs into a ``standard'' form. Most people don't personally prefer the standard form (which is one reason why this command has so many options) but nearly everyone agrees that this tool is very useful for cleaning up ugly C code.

Different people use different styles, and most are readable. However, someone may someday hand you a piece of code that is indented in a hideous manner, and rather than waste time reformatting it, you can use this tool. Remember to always checkin code before using indent, just in case you change your mind!

My favorite options are:

		-cd41 -i8 -d-1 -br
	

Note- indent is only for C. Also note that indent seems to have vanished from the HPs recently. I'll see if I can dig up another copy.


Please bring any errors or inconsistencies in this document to the attention of the author.

Dan Ellard <ellard@deas.harvard.edu>