Warning! This site is under development.
This class will be recorded! Its use will be limited to members of the class. Please do not share with others.
Approximate overview
getopt and getopt_long.cat, that takes the following options.
--version or -v: Prints out the version and exits.--helper or -h: Gives a succinct summary of the options.--outfile or -o: Sends output to the given file. (There
may be many calls to -o.)--pipe or -p: Also sends output to standard output. (This
is the default behavior; only overrriden by -o.)--verbose or -v: Prints information about what’s happening
to stderr.--stdin: Reads from stdin in addition to from any files
given on the command line. (You can decide if you want
this to be before all the files, after all the files, or in-between
all of the files.)--safe or -s: Does not overwrite any files specified by -o.--dryrun or -d: Does not actually do the work, but does verify
that it has permission to read and write all of the files.struct sq
{
int size; // Not everyone
struct sq_node *front;
struct sq_node *back;
}
struct sq_node
{
char *contents;
struct sq_node *next;
}
Design choice 1: Why use size?
size procedure constant time rather than linear time.size remains correct.size is a good way of checking whether or not the queue is empty.Design choice 2: Testing
Design choice 3: Dummy nodes
siz hed tal
+---+---+---+
| 3 | * | *------------------\
+---+-|-+---+ |
v v
+---+---+ +---+---+ +---+---+
| | *----> | | *---> | | / |
+---+---+ +---+---+ +---+---+
Traditional problem with linked structures: You need special cases for adding to the empty structure and removing the last element in the empty the structure.
int
sq_enqueue (SQ *q, char *contents)
{
if (0 == q->size)
{
q->front = (struct sq_node *) malloc (sizeof (struct sq_node));
if (q->front == NULL) return 0;
q->front->contents = contents;
q->front->next = NULL;
q->back = q->front;
}
else
{
struct sq_node *tmp = (struct sq_node *) malloc (sizeof (struct sq_node));
if (tmp == NULL) return 0;
tmp->contents = contents;
tmp->next = NULL;
back->next = tmp;
}
} // sq_enqueue
char *
sq_dequeue(SQ *q)
{
// Special case for the queue becoming empty
}
When you write special case code, you sometimes make mistakes.
siz hed tal
+---+---+---+
| 3 | * | *------------------\
+---+-|-+---+ |
v v
+---+---+ +---+---+ +---+---+ +---+---+
| / | *--->| | *----> | | *---> | | *----+
+---+---+ +---+---+ +---+---+ +---+---+ |
^ |
| |
+--------------------------------------------+
Whoops! Detour failed. Dummy nodes won’t help us.
Design choice 4: Where do we declare the structs?
sq.h
sq.c
What if we decide to go from a queue of strings to a queue of ints?
int rather char *int instead of char * for variables and parameters and …INT_MIN as the error value rather than NULL.sq to iq and SQ to IQProblem: What if the original code was wrong?
malloc works correctly.dequeue or free.new.We’ll look at some issues.
sq-d.csq *
sq_new(){
return malloc(sizeof(sq));
}
Assumes that malloc zeroes the memory. But does it?
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "sq.h"
int
main (int argc, char *argv[])
{
SQ *q = sq_new ();
assert (q);
assert (0 == sq_size (q)); // 0
assert(sq_enqueue (q, "Alpha"));
assert(sq_enqueue (q, "Bravo"));
sq_free (q);
q = sq_new ();
assert (q);
assert (0 == sq_size (q)); // 0
} // main
Whoops!
Change to calloc.
sq-a.cIn dequeue, if the size is 1, we set front and back to NULL,
but don’t free the old node. (Memory leak!)
if (q->size == 1)
{
q->front = NULL;
q->back = NULL;
q->size--;
return first;
}
It’s good practice to cast the return value from malloc. (But the
code should still work fine.)
Don’t put main in your utility code! Create two files that you link
together.
The following code is problematic. If the malloc fails,
assigning new->string or new->next will result in a seqfault.
/* declares and initializes new node */
struct node *new = malloc(sizeof(struct node));
new->string = str;
new->next = NULL;
/* if malloc failed, return 0 */
if (!new)
{
return 0;
}
sq-b.cDoes not free the struct (misunderstanding)
void sq_free (SQ *q){
// deQ until the q is empty.
while(sq_dequeue(q));
// the Q can be used after it is sq_freed, will just have 0 elements,
// unless i want to free it here
}
Don’t chain arrows, even with parens?
return q->front->str;
Make sure that malloc succeeds.
// Make space for a new node
node_t* node = malloc(sizeof(node_t));
// Fill the node with the string
node->str = str;
Order of nodes matters. For queues, we want front linking to a series of nodes that link to back. For stacks, we want top linking to the prior nodes.
sq-c.cNot valid C.
Look at the code.
Writing programs that generate code is called “meta-programming”.
Instead of manually copy/paste/change for our different kinds of queues, we should write programs to generate our queues.
In C, you can use macros to do some kinds of meta-programming (that is, to generate code).
For example, if we wanted versions of square for different types
(e.g., isquare for ints and dsquare for doubles, etc.)
#define SQUARE_FUN(NAME, TYPE) \
TYPE \
NAME (TYPE X) \
{ \
print ("Squaring"); \
return X*X; \
}
We can do something similar to generalize queues. See old reading.
When you find yourself programming by copy/paste/change, you should find a way to avoid that. Sometimes writing programs that generate your code is the way to go.
See https://rebelsky.cs.grinnell.edu/musings/cnix-macros-generics
We’ll consider some issues and their effects.
Example
int *ip = (int *) malloc (sizeof (int));
int *jp = ip;
*jp = 5;
free (ip);
printf ("%d\n", *jp);
*ip = (int *) malloc (sizeof (int));
*ip = 11;
printf ("%d\n", *jp);
Effects? What do you see happening if you try to use memory after you’ve freed it?
malloc, they may get that memory,
change it, and your value will change unexpectedly.How do you know if your code inadvertently uses memory that has been freed (other than, “Hmmm, my value changed inadvertently.”)
valgrind.Why doesn’t C have a garbage collector?
Examples
Effects?
Examples
Effects?
Examples
Effects?
Examples
Effects?
Examples
Effects?
How do we diagnose these errors?
/**
* example.c
* An example for our discussions.
*/
// +---------+---------------------------------------------------------
// | Headers |
// +---------+
#include <assert.h>
#include <stdio.h>
// +---------+---------------------------------------------------------
// | Helpers |
// +---------+
/**
* Allocate an array.
*/
void
vals (int *result[])
{
int values[10];
*result = values;
} // vals
/**
* A function that fills in some values in an array.
*/
void
f (int n)
{
int i;
int values[10];
for (i = 0; i < 10; i++)
{
values[i] = n;
assert(values[i] == n);
} // for
} // f
// +------+------------------------------------------------------------
// | Main |
// +------+
int
main (void)
{
int *stuff;
vals (&stuff);
stuff[0] = 42;
f (5);
assert (42 = stuff[0]);
return 0;
} // main
#include <stdlib.h>
#include <stdio.h>
void
f (int *ip)
{
int i = *ip;
free (ip);
ip = malloc (sizeof (int));
*ip = i + 1;
}
int
main (int argc, char *argv[])
{
int *stuff;
stuff = malloc (sizeof (int));
*stuff = 5;
f (stuff);
assert (6 == *stuff);
*stuff = 1;
assert (1 == *stuff);
free (stuff);
return 0;
} // main
/**
* example.c
* An example for our discussion of lldb and such.
*/
// +---------+---------------------------------------------------------
// | Headers |
// +---------+
#include <assert.h>
#include <stdio.h>
// +---------+---------------------------------------------------------
// | Helpers |
// +---------+
/**
* Allocate an array.
*/
void
vals (int *result[])
{
int values[10];
*result = values;
} // vals
/**
* A function that fills in some values in an array.
*/
void
f (int n)
{
int i;
int values[10];
for (i = 0; i < 10; i++)
{
values[i] = n;
assert(values[i] == n);
} // for
} // f
// +------+------------------------------------------------------------
// | Main |
// +------+
int
main (void)
{
int *stuff;
vals (&stuff);
stuff[0] = 42;
f (5);
assert (stuff[0] == 42);
return 0;
} // main