Errata

"first-in, last-out" (at end of line) now reads "first-in, first-out."

"Linux 5.1" now reads "RedHat Linux 5.1."

"char b[20]" now reads "char b[20];".

At the bottom of the page, the last line of code did read:


retval = list_ins_next(...

Now reads:

retval = list_rem_next(...

The equation at the bottom of the page did read:

T(n) = 1 if n = 0
2T(n/2) + n if n > 0

Now reads:

T(n) = 1 if n = 2
2T(n/2) + n if n = 1, n > 2

"first-in, last-out" (at beginning of line) now reads "first-in, first-out."

Line 5 from top did read:


if (list_size(list) == 0)

Now reads:

if (list_size(list) == 1)

old_element = element->next;
element->next = element->next->next;

ARE NOW FOLLOWED by the two additional lines:

if (old_element == clist_head(list))
list->head = old_element->next;

All occurrences of "int" in the implementation of hashpjw HAVE BEEN CHANGED to
"unsigned int".

1 / (1 - 0.50) < 2

now reas:

< 1 / (1 - 0.50) = 2

2nd line says

"... by calling bitree_merge."

This now reads

"...by calling bitree_init."

A line of code has been added at the end of the page to read:

static void destroy_right(BisTree *tree, BiTreeNode *node);

In the function destroy_left, the calls did read:


bitree_rem_left(tree, *position);
bitree_rem_right(tree, *position);

Now read:

destroy_left(tree, *position);
destroy_right(tree, *position);

It is the responsibility of the caller to manage the storage
associated with data2.

"data2" is now in ConstantWidth italics font.

now reads:

...graph->match, NULL);

The line that reads:
set_init(&adjlist->adjacent, graph->match, graph->destroy);

NOW READS:
set_init(&adjlist->adjacent, graph->match, NULL);

**AUTHOR'S RESPONSE

It is important to note that when inserting an edge into a graph, the data2
parameter of graph_ins_edge must have *its own* storage allocated for it. For
example, data2 cannot share storage with a vertex passed to graph_ins_vertex
at some earlier time. For example, to create the graph below, we should do
something like the following:

Graph:
---------
a -> b
b
---------

data2 = (char *)malloc(2);
strcpy(data2, "b");
graph_ins_vertex(&graph, data2);

data1 = (char *)malloc(2);
strcpy(data1, "a");
graph_ins_vertex(&graph, data1);

data2 = (char *)malloc(2);
strcpy(data2, "b");
graph_ins_edge(&graph, data1, data2);

Note that before the call to graph_ins_edge, we allocate new storage for
data2. This is because inside of graph_ins_vertex, set_init initializes each
new adjacency list with graph->destroy, which will be called once for each
vertex in the adjacency list when the graph is destroyed. Since every vertex
also appears in the list of AdjList structures, without its own storage each
vertex will be destroyed more than once. One solution is to set the destroy
parameter of set_init to NULL. However, this alternative poses problems in the
form of consistency issues. The important thing to remember, therefore, is
simply this: Before any piece of data is inserted into a data structure, it
must have *its own* storage allocated for it. (Notice that it is perfectly
acceptable in the call to graph_ins_edge, however, not to allocate new storage
for data1 because data1 is used only to look up in which adjacency list data2
will be inserted; in other words, the graph does not have a pointer to data1
once the operation completes.

In Example 12.5, change the line of code:
int mgsort(void *data, int size, int esize, int i, ...
to:
int mgsort(void *data, int esize, int i, ...

That is, remove "int size, " since this parameter is not used. We
should also make sure that this is changed in the code on disk.

In Example 12.5, change the line of code:
int mgsort(void *data, int size, int esize, int i, ...
to:
int mgsort(void *data, int esize, int i, ...

That is, remove "int size, " since this parameter is not used. We
should also make sure that this is changed in the code on disk.

free the storage just allocated for the counts before returning. Thus, the
lines:

if ((temp = (int *)malloc(size * sizeof(int))) == NULL)
return -1;

should read:

if ((temp = (int *)malloc(size * sizeof(int))) == NULL) {

free(counts);
return -1;

}

The values in the first three columns for i=4 in Figure 13.1 should be
4, 0.0, 0.5. That is, changed the value in the third column of this
row, 1.5, to 0.5.

The values in the first three columns for i=4 in Figure 13.1 should be
4, 0.0, 0.5. That is, changed the value in the third column of this
row, 1.5, to 0.5.

"i < k" now reads "i < j".

The straddle test determines the orientation of p3 relative to
p2 and of p4 relative to p2 with respect to p1.

The following HAS BEEN ADDED:
It then determines the orientation of [p1] relative to [p4] and of
[p2] relative to [p4] with respect to [p3].

Note that [ ] above indicates an item in constant width italic font.

ALSO the sentence that begins:
If the orientations are different, or if either orientation is 0...

NOW READS:
If the orientations of the points in either computation are
different or 0, the straddle test succeeds, and the algorithm returns
that the line segments intersect; otherwise, the line segments do not
intersect.

Code should be this:

/*****************************************************************************
* *
* -------------------------------- lint.c ------------------------------- *
* *
*****************************************************************************/

#include "geometry.h"

/*****************************************************************************
* *
* --------------------------------- lint --------------------------------- *
* *
*****************************************************************************/

int lint(Point p1, Point p2, Point p3, Point p4) {

double z1,
z2,
z3,
z4;

int s1,
s2,
s3,
s4;

/*****************************************************************************
* *
* Perform the quick rejection test. *
* *
*****************************************************************************/

if (!(MAX(p1.x, p2.x) >= MIN(p3.x, p4.x) && MAX(p3.x, p4.x)
>= MIN(p1.x, p2.x) && MAX(p1.y, p2.y) >= MIN(p3.y, p4.y)
&& MAX(p3.y, p4.y) >= MIN(p1.y, p2.y))) { {
return 0;

}

/*****************************************************************************
* *
* Determine whether the line segments straddle each other. *
* *
*****************************************************************************/

if ((z1 = ((p3.x - p1.x)*(p2.y - p1.y)) - ((p3.y - p1.y)*(p2.x - p1.x))) < 0)
s1 = -1;
else if (z1 > 0)
s1 = 1;
else
s1 = 0;

if ((z2 = ((p4.x - p1.x)*(p2.y - p1.y)) - ((p4.y - p1.y)*(p2.x - p1.x))) < 0)
s2 = -1;
else if (z2 > 0)
s2 = 1;
else
s2 = 0;

if ((z3 = ((p1.x - p3.x)*(p4.y - p3.y)) - ((p1.y - p3.y)*(p4.x - p3.x))) < 0)
s3 = -1;
else if (z3 > 0)
s3 = 1;
else
s3 = 0;

if ((z4 = ((p2.x - p3.x)*(p4.y - p3.y)) - ((p2.y - p3.y)*(p4.x - p3.x))) < 0)
s4 = -1;
else if (z4 > 0)
s4 = 1;
else
s4 = 0;

if ((s1 * s2 <= 0) && (s3 * s4 <= 0))
return 1;

/*****************************************************************************
* *
* Return that the line segments do not intersect. *
* *
*****************************************************************************/

return 0;

}

Code should be this:

/*****************************************************************************
* *
* -------------------------------- lint.c ------------------------------- *
* *
*****************************************************************************/

#include "geometry.h"

/*****************************************************************************
* *
* --------------------------------- lint --------------------------------- *
* *
*****************************************************************************/

int lint(Point p1, Point p2, Point p3, Point p4) {

double z1,
z2,
z3,
z4;

int s1,
s2,
s3,
s4;

/*****************************************************************************
* *
* Perform the quick rejection test. *
* *
*****************************************************************************/

if (!(MAX(p1.x, p2.x) >= MIN(p3.x, p4.x) && MAX(p3.x, p4.x)
>= MIN(p1.x, p2.x) && MAX(p1.y, p2.y) >= MIN(p3.y, p4.y)
&& MAX(p3.y, p4.y) >= MIN(p1.y, p2.y))) { {
return 0;

}

/*****************************************************************************
* *
* Determine whether the line segments straddle each other. *
* *
*****************************************************************************/

if ((z1 = ((p3.x - p1.x)*(p2.y - p1.y)) - ((p3.y - p1.y)*(p2.x - p1.x))) < 0)
s1 = -1;
else if (z1 > 0)
s1 = 1;
else
s1 = 0;

if ((z2 = ((p4.x - p1.x)*(p2.y - p1.y)) - ((p4.y - p1.y)*(p2.x - p1.x))) < 0)
s2 = -1;
else if (z2 > 0)
s2 = 1;
else
s2 = 0;

if ((z3 = ((p1.x - p3.x)*(p4.y - p3.y)) - ((p1.y - p3.y)*(p4.x - p3.x))) < 0)
s3 = -1;
else if (z3 > 0)
s3 = 1;
else
s3 = 0;

if ((z4 = ((p2.x - p3.x)*(p4.y - p3.y)) - ((p2.y - p3.y)*(p4.x - p3.x))) < 0)
s4 = -1;
else if (z4 > 0)
s4 = 1;
else
s4 = 0;

if ((s1 * s2 <= 0) && (s3 * s4 <= 0))
return 1;

/*****************************************************************************
* *
* Return that the line segments do not intersect. *
* *
*****************************************************************************/

return 0;

}