CS
11 C track: lecture 6
n Last week: pointer arithmetic
n This week:
n The gdb program
n struct
n typedef
n linked lists
gdb for debugging (1)
n gdb: the Gnu DeBugger
n [Link]
/c/mike/misc/[Link]
n Use when program crashes
n e.g. from a segmentation violation
n or when want to walk through execution
of program line-by-line
gdb for debugging (2)
n Before using gdb:
n Must compile C code with additional flag: -g
n This puts all the source code into the binary
executable
n Then can execute as: gdb myprogram
n Brings up an interpreted environment
gdb for debugging (3)
gdb> run
n Program runs...
n If all is well, program exits successfully,
returning you to prompt
n If there is (e.g.) a crash, gdb will tell you
and abort the program
gdb for debugging (4)
n If your program needs command-line
arguments, e.g. myprogram 1 2 3,
then you should do this in gdb:
gdb> run 1 2 3
n This will run myprogram with the
command-line arguments 1, 2, and 3
gdb – basic commands (1)
n Stack backtrace ("where")
n Your program crashes
n Where was the last line in the program that
was executed before the crash?
n That's what the where command tells you
gdb – basic commands (2)
gdb> where last call last call in your code
#0 0x4006cb26 in free () from /lib/[Link].6
#1 0x4006ca0d in free () from /lib/[Link].6
#2 0x8048951 in board_updater (array=0x8049bd0,
ncells=2) at 1dCA2.c:148
#3 0x80486be in main (argc=3, argv=0xbffff7b4) at
1dCA2.c:44
#4 0x40035a52 in __libc_start_main () from
/lib/[Link].6
stack backtrace
gdb – basic commands (3)
n Look for topmost location in stack backtrace that
corresponds to your code
n Watch out for
n freeing memory you didn't allocate
n accessing arrays beyond their maximum elements
n dereferencing pointers that don't point to part of a
malloc()ed block
gdb – basic commands (4)
n break, continue, next, step commands
n break causes execution to stop on a given line
gdb> break foo.c: 100 (setting a breakpoint)
n continue resumes execution from that point
n next executes the next line, then stops
n step executes the next statement
n goes into functions if necessary (next doesn't)
gdb – basic commands (5)
n print and display commands
n print prints the value of any program expression
gdb> print i
$1 = 100
n display prints a particular value every time
execution stops
gdb> display i
gdb – printing arrays (1)
n print will print arrays as well
int arr[] = { 1, 2, 3 };
gdb> print arr
$1 = {1, 2, 3}
n N.B. the $1 is just a name for the result
print $1
$2 = {1, 2, 3}
gdb – printing arrays (2)
n print has problems with dynamically-allocated arrays
int *arr;
arr = (int *)malloc(3 * sizeof(int));
arr[0] = 1; arr[1] = 2; arr[2] = 3;
gdb> print arr
$1 = (int *) 0x8094610
n Not very useful...
gdb – printing arrays (3)
n Can print this array by using @ (gdb special syntax)
int *arr;
arr = (int *)malloc(3 * sizeof(int));
arr[0] = 1; arr[1] = 2; arr[2] = 3;
gdb> print *arr@3
$2 = {1, 2, 3}
gdb – abbreviations
n Common gdb commands have abbreviations
p (same as print)
c (same as continue)
n (same as next)
s (same as step)
n More convenient to use when interactively
debugging
structs (1)
n Way to package primitive data objects into an
aggregate data object
n struct declaration:
struct point {
int x;
int y;
double dist; /* from origin */
}; /* MUST have semicolon! */
structs (2)
n struct declaration usually done outside of
function, like a function prototype
n Create/initialize struct like this:
struct point p;
p.x = 0; /* "dot syntax" */
p.y = 0;
[Link] = sqrt(p.x*p.x + p.y*p.y);
structs (3)
n Using a struct:
void foo(void) {
struct point p;
p.x = 10; p.y = -3;
[Link] = sqrt(p.x*p.x + p.y*p.y);
/* do stuff with p */
}
structs (4)
n Using malloc() with structs:
struct point *make_point(void) {
struct point *p;
p = (struct point *)
malloc(sizeof(struct point));
return p;
} /* free struct elsewhere */
structs (5)
n Using pointers to structs :
void init_point(struct point *p) {
(*p).x = (*p).y = 0;
(*p).dist = 0.0;
/* syntactic sugar: */
p->x = p->y = 0;
p->dist = 0.0;
}
structs (6)
n structs can contain arrays or other structs
n Usually use pointers to structs instead of just
plain structs
struct foo {
int x;
struct point p1; /* Unusual */
struct point *p2; /* Typical */
};
structs (7)
n structs can be "recursive":
struct node {
int value;
struct node *next;
};
n but can't have struct node next inside
declaration (why?)
typedef (1)
n Typing struct point all the time is tedious
n Use a typedef (type alias):
original type new name
typedef struct point Point;
typedef int Length;
n Original type comes first
n New name is at the end
typedef (2)
n Type component of typedef can also be a struct
typedef struct { /* no name for struct */
int x;
int y;
double dist;
} Point;
Point p1, p2; /* no "struct" */
n N.B. This is an anonymous struct
typedef (3)
n Recursively defined structs:
typedef struct _node {
int value;
struct _node *next;
} node;
typedef (4)
n Read this as:
typedef
struct _node {
int value;
struct _node *next;
}
node;
Linked lists
n node is the linked list struct!
n Set next pointer to next node in list
n If next is NULL, then at end of list
n Linked lists are just chains of nodes
Creating a linked list (1)
node *list, *n, *prev;
Linked list (diagram)
list
prev
Creating a linked list (2)
n = (node *)malloc(sizeof(node));
list = n; /* list points to first node */
n->value = 10;
prev = n; /* pointer to previous node */
Linked list (diagram)
list
n
prev
Linked list (diagram)
list
n (node)
prev
Linked list (diagram)
list
n (node)
prev
Linked list (diagram)
list
value: 10
n (node)
next:
prev
Linked list (diagram)
list
value: 10
n (node)
next:
prev
Creating a linked list (3)
n = (node *)malloc(sizeof(node));
prev->next = n; /* connect nodes */
prev = n;
n->value = 20;
/* ... continued on next slide ... */
Linked list (diagram)
list
value: 10
n (node)
next:
prev
Linked list (diagram)
list
value: 10
n (node)
next:
prev
(node)
Linked list (diagram)
list
value: 10
n (node)
next:
prev
(node)
Linked list (diagram)
list
value: 10
n (node)
next:
prev
(node)
Linked list (diagram)
list
value: 10
n (node)
next:
prev
(node)
Linked list (diagram)
list
value: 10
n (node)
next:
prev
value: 20
(node)
next:
Creating a linked list (4)
/* Continued... */
n = (node *) malloc(sizeof(node));
prev->next = n;
prev = n;
n->value = 30;
n->next = NULL; /* End of list marker. */
Linked list (diagram)
list
value: 10
n (node)
next:
prev
value: 20
(node)
next:
Linked list (diagram)
list
value: 10
n (node)
next:
prev
value: 20
(node)
next:
(node)
Linked list (diagram)
list
value: 10
n (node)
next:
prev
value: 20
(node)
next:
(node)
Linked list (diagram)
list
value: 10
n (node)
next:
prev
value: 20
(node)
next:
(node)
Linked list (diagram)
list
value: 10
n (node)
next:
prev
value: 20
(node)
next:
(node)
Linked list (diagram)
list
value: 10
n (node)
next:
prev
value: 20
(node)
next:
value: 30
(node)
next:
Linked list (diagram)
list
value: 10
n (node)
next:
prev
value: 20
(node)
next:
value: 30
(node)
next: NULL
Linked list (final diagram)
list
value: 10
(node)
next:
value: 20
(node)
next:
value: 30
(node)
next: NULL
Creating a linked list (5)
n Can also create linked lists from the end back
to the front
n Actually easier to do it that way when possible
n example: lab 6 command-line arguments
n End-of-list is represented as NULL pointer
n add nodes to previous list (or to NULL)
Creating a linked list (6)
list = NULL; /* Empty list. */
node *n = (node *) malloc(sizeof(node));
n->value = 30;
n->next = list;
list = n; /* now 1-node list */
Linked list (diagram)
list NULL
Linked list (diagram)
n (node)
list NULL
Linked list (diagram)
value: 30 (node)
n
list NULL
Linked list (diagram)
value: 30 (node)
n
next: NULL
list NULL
Linked list (diagram)
value: 30 (node)
n
next: NULL
list
Linked list (diagram)
list value: 30 (node)
n next: NULL
Creating a linked list (7)
node *n = (node *) malloc(sizeof(node));
n->value = 20;
n->next = list;
list = n; /* now 2-node list */
Linked list (diagram)
list value: 30 (node)
n next: NULL
Linked list (diagram)
(node)
n
list value: 30 (node)
next: NULL
Linked list (diagram)
value: 20 (node)
n
list value: 30 (node)
next: NULL
Linked list (diagram)
value: 20 (node)
n next:
list value: 30 (node)
next: NULL
Linked list (diagram)
list value: 20 (node)
n next:
value: 30 (node)
next: NULL
Creating a linked list (8)
node *n = (node *) malloc(sizeof(node));
n->value = 10;
n->next = list;
list = n; /* now 3-node list */
Linked list (diagram)
list value: 20 (node)
n next:
value: 30 (node)
next: NULL
Linked list (diagram)
n (node)
list value: 20 (node)
next:
value: 30 (node)
next: NULL
Linked list (diagram)
n value: 10 (node)
list value: 20 (node)
next:
value: 30 (node)
next: NULL
Linked list (diagram)
n value: 10 (node)
next:
list value: 20 (node)
next:
value: 30 (node)
next: NULL
Linked list (diagram)
n value: 10 (node)
list next:
value: 20 (node)
next:
value: 30 (node)
next: NULL
Linked list (final diagram)
value: 10 (node)
list
next:
value: 20 (node)
next:
value: 30 (node)
next: NULL
Checking malloc()
n Previous code simplified to fit on slide
n Actually should check every malloc call for
failure
n = (node *)malloc(sizeof(node));
if (n == NULL)
{
fprintf(stderr,
"Error: out of memory.\n");
exit(1);
}
Iterating through a linked list
n Standard idiom for going through linked lists:
node *n;
/* Set all node values to zero. */
for (n = list; n != NULL; n = n->next) {
n->value = 0;
n You should be able to figure out how this works
Lab 6
n This week's lab:
n New sorting algorithm: "quicksort"
n More efficient than ME sort, bubblesort
n Use on linked lists, not arrays
n Memory management will be a challenge!
Next time
n Hash tables
n More "fun" with pointers ;;-)
