D. J. Bernstein
Data structures and program structures
MCS 275, Fall 2001

# What I did in class

20010820: Substitute: Professor Verschelde. Review of problems 1-4 from the MCS 260 final. Read chapter 8.

20010822: Substitute: Professor Verschelde. Review of some remaining problems from the MCS 260 final.

20010824: Announcements. Several examples of how int variables x, y, z might be laid out in memory, including byte numbers. &x is the location of x. Picture of Memory Lane. Terminology: ``address'' means location.

20010827: Terminology: ``pointer'' means location. Pictures. When p is a location, *p means the variable at that location. When x is a variable, *&x means x. Examples.

20010829: When x is an array, the expression x means &x, i.e., &(x). Examples. &x[i]+j means &x[i+j]. Examples. Warning that +j moves j ints, not j bytes. When p is a location, p[i] means *(p+i); p means *p. Examples.

20010831: Read chapters 9, 10. &x[i]-&x[j] equals i-j. In parameter list, int x or int x[] means int *x. Example: void sumarray(int a[],int alen) { int result; while (alen-- > 0) result += *a++; return result; } to add a+a+...+a[alen-1]. Tracing sumarray(x,5). Tracing sumarray(x + 2,2).

20010903: Labor Day. No class.

20010905: How should data be stored in a computer? Depends on operations performed on the data. Desirable features of code: correct; easy to write; easy to read; easy to modify; fast; etc. How should a list of characters be stored in a computer? Obvious way: pointer x and integer xlen, representing x, x, ..., x[xlen-1]. C string: pointer p representing p, p, ..., until p[n] == 0. Example: storing Joe in each form. Example: extracting oe from Joe. Example: extracting Jo from Joe; harder to do with C string. Initializing an array x so that x is a C string. Abbreviating the initializer with "...". Examples. What "..." means in other contexts. Example: char *p = "...".

20010907: More on strings.

20010910: Command-line arguments.

20010912: More on command-line arguments.

20010914: Class cancelled.

20010917: Review.

20010919: Review.

20010921: Midterm 1.

20010924: Comments on midterm problems 1 through 7.

20010926: Comments on midterm problems 8 and 9. Reread sections on malloc() and free().

20010928: Last comments on midterm. Goal of dynamic memory allocation: use just enough memory for your data. Sometimes can predict memory use in advance: set aside variables. Sometimes can't: need about 1000 bytes if user types 1000 bytes, need about 10 megabytes if user types 10 megabytes. A constant-size array is wasteful if there is less data, insufficient if there is more data. malloc(1000) returns a pointer to the first byte of a newly allocated 1000-byte array, or 0 if not enough memory is available. Can use malloc(n) with variable n. What free() does; warning about using array after free(). Reverse-input program using char *x=malloc(1000) instead of char x. Using malloc for an int array.

20011001: Common malloc idiom: a dynamically allocated partially filled array of double. Initializations: double *x = 0 and int xspace = 0 and int xlen = 0. Meaning: x is either 0 or a pointer to the first element of a dynamically allocated array of xspace doubles; we're using the first xlen doubles, namely x,...,x[xlen-1]. Types other than double. Another common malloc idiom: dynamically allocated C strings. Allocating an array of 10 doubles. Freeing the array. Expanding the array to 30 doubles. A program to read numbers into a dynamically allocated array and compute their median, using xspace * 2 + 1 for reallocation.

20011003: Memory pictures for computing median of 3 1 4 1 5 9 2 6 5 3 5. Some other xspace formulas that work for reallocation. Anything at least xspace + 1 will work. Problem with xspace + 1: many reallocations. Problem with xspace * 2 + 1: waste quite a bit of space. Common compromise: xspace + (xspace / 8) + 10; notation xspace >> 3 for xspace / 8. Defining a dynamically allocated C string: char *x = 0 and int xspace = 0.

20011005: Read chapter 13. Code for ds_copy(). Memory pictures for ds_copy(&x,&xspace,"less fried food"). Memory pictures for ds_copy(&x,&xspace,"and"). Memory pictures for ds_copy(&x,&xspace,"more aerobic exercise"). Code for ds_print(). Code for ds_free().

20011008: ds_concat(). The standard realloc() function. The standard strcat() function.

20011010: The concept of a file in stdio: any device that reads or writes a stream of characters. Examples of files: disk files; network connections; the user's keyboard; the user's terminal. The concept of a randomly accessible file. Essential elements of reading from files: fopen(...,"r"), FILE, fscanf. Other important functions: fclose, fgetc/getc, ferror, strerror. Overly simple fopen/fscanf example. Possible failures. Relating scanf to fscanf; stdin. Revised example, checking for errors.

20011012: Essential elements of writing to files: fopen(...,"w"), FILE, fprintf, fflush. Other important functions: fclose, fputc/putc, ferror, strerror. Overly simple fopen/fprintf/fflush example. Relating printf to fprintf; stdout. The requirement to call fflush. Situations where fflush happens autmoatically. Revised example, checking for errors. The normal meaning of stdin, stdout, stderr. Input redirection: prog args < infile to run prog args with stdin reading from infile. Output redirection: prog args > outfile to run prog args with stdout writing to outfile. What happens to stderr; why error messages are normally written to stderr.

20011015: General shape of a two-program pipeline. Difference between pipe and temporary file. Table of stdin, stdout, stderr. General shape of a three-program pipeline. Table of stdin, stdout, stderr. There are ways to redirect stderr. Example of a program reading two files at once: compare f1 f2.

20011017: savearray(). loadarray(). A simple program using savearray() and loadarray(). The importance of using fclose. The errno variable. Some possible values of the errno variable: 0; ENOMEM; ENOENT. Many functions set errno when they encounter errors. What strerror does. Input buffers. A program that creates a file, starts reading it, changes it, and continues reading it.

20011019: Memory + file picture for the program. Dependence of the output on the buffer size. Output buffers. General shape of the fprintf function. The first argument is a nonzero return value from fopen(), popen(), etc., or stdout or stderr. How stdout and stderr are defined. The second argument is a string. Portions of the string starting with % are handled specially. How fprintf handles other portions of the string. How fprintf handles %%. Memory picture and output picture for fprintf(stdout,"... %% ...\n"). %d for int in decimal; %u for unsigned int; %x for hexadecimal; %o for octal. %f or %lf for double in decimal; float is automatically converted to double. %e for double in scientific notation. %g for a mixture of %e and %f. %c for int as one byte; char is automatically converted to int. %s for a C string.

20011022: %ld, %hd. %5d for printing at least 5 bytes. Additional fprintf features. sprintf. Warning about space needed for sprintf. printf, fputc, fputs, puts. The first argument to fscanf.

20011024: How fscanf handles most characters. Space. %%. %d, %ld, %hd, %f, %lf, %o, %x, %u. %c. %5d for matching at most 5 bytes. Do not use %s and %[...]. Additional fscanf features; why %s and %[...] are bad; safe variants. What fscanf returns.

20011026: scanf, fgetc, getchar. Do not use gets. sscanf. Review.

20011029: Midterm 2.

20011031: Substitute: Professor Teitelbaum. Comments on midterm.

20011102: Substitute: Professor Teitelbaum. Comments on midterm.

20011105: int x0; int y0; int x1; int y1; int x2; int y2. int x; int y. struct point { int x; int y; } ; struct point p0; struct point p1; struct point p2. struct point { int x; int y; } p0; struct point p1; struct point p2. struct point { int x; int y; } p0, p1, p2. struct point { int x; int y; } ; struct point p. What structure types look like in general. A struct initializer. Difference between struct and array: there is no space between array elements; there may be space between struct components.

20011107: Why compilers sometimes put space between struct components. More differences between struct and array: struct can have components of different types; array can easily have a huge number of elements; struct types are first-class. typedef. The da structure.

20011109: Read chapter 11. More on da.

20011112: Disk files are randomly accessible. fopen(...,"rb+"). What the b means. What the + means. Requirement to use fseek before switching between read and write. fseek(f,pos,SEEK_SET). ftell(f). Code for loadbyte(). Example: reading byte 3 from hello world. Code for storebyte(). Example: changing byte 2 of hello world. Advantages of arrays over disk files. Advantages of disk files over arrays.

20011114: Memory segments: text, data, heap, stack. Functions, static const variables, and const variables outside functions are in the text segment: created when the program is compiled, cannot be changed while the program is running. Other static variables and variables outside functions are in the data segment: created when the program starts, destroyed when the program exits. Non-static variables inside functions are in the stack segment: created when the function starts, destroyed when the function exits. Variables created by malloc are in the heap segment: destroyed by free. Example with many text variables, data variables, stack variables. Stack frames; recursion.