faqcat1067.html

this is a mirrored site c-faq. thought might need offline

<a name="qsort1">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../lib/qsort1.html"><!-- qtag -->Question 13.8</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
I'm trying to sort an array of strings with <TT>qsort</TT>,
using
<TT>strcmp</TT>
as the comparison function,
but it's not working.
</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
By ``array of strings'' you probably mean
``array of pointers to <TT>char</TT>.''
The arguments to <TT>qsort</TT>'s comparison function are pointers to the
objects being sorted, in this case, pointers to pointers to <TT>char</TT>.
<TT>strcmp</TT>,
however,
accepts simple pointers to <TT>char</TT>.
Therefore, <TT>strcmp</TT> can't be used directly.
Write
an intermediate
comparison function like this:
<pre>
/* compare strings via pointers */
int pstrcmp(const void *p1, const void *p2)
{
	return strcmp(*(char * const *)p1, *(char * const *)p2);
}
</pre>
</p><p>The comparison function's
arguments are expressed as ``generic pointers,''
<TT>const&nbsp;void&nbsp;*</TT>.
They
are
converted
back to what they ``really are''
(pointers to pointers to <TT>char</TT>)
and dereferenced,
yielding <TT>char&nbsp;*</TT>'s which can be
passed to <TT>strcmp</TT>.
</p><p>The call to <TT>qsort</TT> might look like
<pre>
#include &lt;stdlib.h&gt;
char *strings[NSTRINGS];
int nstrings;
/* nstrings cells of strings[] are to be sorted */
qsort(strings, nstrings, sizeof(char *), pstrcmp);
</pre>
</p><p>(Don't be misled by
the discussion in K&amp;R2 Sec. 5.11 pp.&nbsp;119-20,
which is not discussing
the
Standard library's
<TT>qsort</TT>,
and
makes a quiet,
unnecessary assumption about the equivalence of <TT>char&nbsp;*</TT>
and <TT>void&nbsp;*</TT>).
</p><p>For more information
on

<TT>qsort</TT> comparison
functions--how
they are called and how they must be
declared--see
question <a href="faqcat1067.html?sec=lib#qsort2">13.9</a>.
</p>


<p>References:

ISO Sec. 7.10.5.2
<br>
H&amp;S Sec. 20.5 p. 419
<hr><hr><hr>
<a name="qsort2">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../lib/qsort2.html"><!-- qtag -->Question 13.9</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
Now I'm trying to sort an array of structures
with <TT>qsort</TT>.
My comparison function takes pointers to structures,
but the compiler
complains
that the function is
of the wrong type for <TT>qsort</TT>.
How can I cast the function pointer to shut off the warning?
</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
The
conversions
must be in the
comparison function,
which
must be declared as accepting ``generic pointers''
(<TT>const&nbsp;void&nbsp;*</TT>)
as discussed
in question
<a href="faqcat1067.html?sec=lib#qsort1">13.8</a> 
above.
For a hypothetical
little
date structure
<pre>
struct mystruct {
	int year, month, day;
};
</pre>
the
comparison function
might look like
<a href="../../lib/compare.html" rel=subdocument>[footnote]</a>

<pre>
int mystructcmp(const void *p1, const void *p2)
{
	const struct mystruct *sp1 = p1;
	const struct mystruct *sp2 = p2;
	if(sp1-&gt;year &lt; sp2-&gt;year) return -1;
	else if(sp1-&gt;year &gt; sp2-&gt;year) return 1;
	else if(sp1-&gt;month &lt; sp2-&gt;month) return -1;
	else if(sp1-&gt;month &gt; sp2-&gt;month) return 1;
	else if(sp1-&gt;day &lt; sp2-&gt;day) return -1;
	else if(sp1-&gt;day &gt; sp2-&gt;day) return 1;
	else return 0;
}
</pre>
(The conversions
from generic pointers
to <TT>struct mystruct</TT> pointers
happen in the initializations
<TT>sp1&nbsp;=&nbsp;p1</TT> and <TT>sp2&nbsp;=&nbsp;p2</TT>;
the compiler performs the
conversions implicitly
since
<TT>p1</TT> and <TT>p2</TT> are
<TT>void</TT> pointers.)

</p><p>For this version of <TT>mystructcmp</TT>,
the call to <TT>qsort</TT> might look like
<pre>
#include &lt;stdlib.h&gt;
struct mystruct dates[NDATES];
int ndates;
/* ndates cells of dates[] are to be sorted */
qsort(dates, ndates, sizeof(struct mystruct), mystructcmp);
</pre>
</p><p>If,
on the other hand,
you're sorting pointers to structures,
you'll need indirection,
as in question
<a href="faqcat1067.html?sec=lib#qsort1">13.8</a>;
the
head of
the
comparison function would
look
like
<pre>
int myptrstructcmp(const void *p1, const void *p2)
{
	struct mystruct *sp1 = *(struct mystruct * const *)p1;
	struct mystruct *sp2 = *(struct mystruct * const *)p2;
</pre>
and the call would look like
<pre>
struct mystruct *dateptrs[NDATES];
qsort(dateptrs, ndates, sizeof(struct mystruct *), myptrstructcmp);
</pre>
</p><p>To understand why the curious
pointer conversions
in a <TT>qsort</TT> comparison function are necessary
(and why a cast of the function pointer when calling
<TT>qsort</TT>
can't help),
it's useful to think about how <TT>qsort</TT> works.
<TT>qsort</TT> doesn't know anything about the type or
representation of the data being sorted:
it just shuffles around little chunks of memory.
(All it knows about the chunks is their size,
which you specify
in <TT>qsort</TT>'s third argument.)
To determine whether two chunks need swapping,
<TT>qsort</TT> calls your comparison function.
(To swap them,
it
uses the equivalent of <TT>memcpy</TT>.)
</p><p>Since <TT>qsort</TT> deals in a generic way
with chunks of memory of unknown
type,
it uses generic pointers
(<TT>void&nbsp;*</TT>)

to refer to them.
When <TT>qsort</TT> calls your comparison function,
it passes as arguments
two generic pointers to the chunks to be compared.
Since it passes generic pointers,
your comparison function must
<em>accept</em> generic pointers,
and
convert
the pointers back to their appropriate type
before manipulating them
(i.e. before performing the comparison).
A <TT>void</TT> pointer is not the same type as a structure pointer,
and on some machines it may have a different size or representation
(which is why these casts are required for correctness).
</p><p>If you were sorting an array of structures,
and had a comparison function accepting structure pointers:
<pre>
	int mywrongstructcmp(struct mystruct *, struct mystruct *);
</pre>
and if you called <TT>qsort</TT> as
<pre>
	qsort(dates, ndates, sizeof(struct mystruct),
		(int (*)(const void *, const void *))mywrongstructcmp);
							/* WRONG */
</pre>
the
cast
<TT>(int&nbsp;(*)(const&nbsp;void&nbsp;*, const&nbsp;void&nbsp;*))</TT>
would do nothing
except perhaps
silence the message from the compiler telling you that this
comparison function
may
<em>not</em> work with <TT>qsort</TT>.
The
implications
of any cast you use
when calling qsort
will have been forgotten
by the time <TT>qsort</TT>
gets around to calling your comparison function:
it will call them with <TT>const&nbsp;void&nbsp;*</TT> arguments,
so that is what your function must accept.
No prototype mechanism exists
which could operate down inside <TT>qsort</TT>
to convert the <TT>void</TT> pointers to <TT>struct&nbsp;mystruct</TT> 
pointers just before calling <TT>mywrongstructcmp</TT>.
</p><p>
In general,
it is a bad idea to insert casts just to
``shut the compiler up.''
Compiler warnings are usually trying to tell you something,
and unless you really know what you're doing,
you ignore or
muzzle
them at your peril.
See also question <a href="faqcatabdc.html?sec=ptrs#genericpp">4.9</a>.

</p><p><a href="../../lib/sd14.html" rel=subdocument>Additional links</a>
</p>

<p>References:

ISO Sec. 7.10.5.2
<br>
H&amp;S Sec. 20.5 p. 419
<hr><hr><hr>
<a name="listsort">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../lib/listsort.html"><!-- qtag -->Question 13.10</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
How can I sort a linked list?
</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
Sometimes it's easier to keep the list in order as you build it
(or perhaps to use a tree instead).
Algorithms like insertion sort and merge sort
lend themselves ideally to use with linked lists.
If you want to use a standard library function,
you can allocate a
temporary
array of pointers,
fill it in with pointers to all your list nodes,
call <TT>qsort</TT>,
and finally rebuild the list pointers based on the sorted array.
</p><p>Additional links:
<a href="../../lib/mergesort.ct.html">example by Chris Torek</a>
</p>



<p>References:

Knuth Sec. 5.2.1 pp. 80-102, Sec. 5.2.4 pp. 159-168
<br>
Sedgewick Sec. 8 pp. 98-100, Sec. 12 pp. 163-175
<hr><hr><hr>
<a name="extsort">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../lib/extsort.html"><!-- qtag -->Question 13.11</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
How can I sort more data than will fit in memory?
</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
You want an ``external sort,''
which
you can read about
in Knuth,
Volume 3.
The basic idea is to sort the data in chunks
(as much as will fit in memory at one time),
write each sorted chunk to a temporary file,
and then merge the files.
Your operating system may provide a general-purpose sort utility,
and if so,
you can try invoking it from within your program:
see questions <a href="faqcatea63.html?sec=osdep#system">19.27</a> and <a href="faqcatea63.html?sec=osdep#popen">19.30</a>,
and the example in question <a href="faqcatea63.html?sec=osdep#system2">19.28</a>.
</p>

<p>References:

Knuth Sec. 5.4 pp. 247-378
<br>
Sedgewick Sec. 13 pp. 177-187
<hr><hr><hr>
<a name="curtime">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../lib/curtime.html"><!-- qtag -->Question 13.12</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
How can I get the
current date
or
time of day in a C program?
</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
Just use the <TT>time</TT>,
<TT>ctime</TT>,
<TT>localtime</TT>
and/or <TT>strftime</TT>
functions.
Here is a simple example:
<a href="../../lib/timefail.html" rel=subdocument>[footnote]</a>
<pre>
#include &lt;stdio.h&gt;
#include &lt;time.h&gt;

int main()
{
	time_t now;
	time(&amp;now);
	printf("It's %s", ctime(&amp;now));
	return 0;
}
</pre>

</p><p>Calls to <TT>localtime</TT> and <TT>strftime</TT>
look like this:
<pre>
	struct tm *tmp = localtime(&amp;now);
	char fmtbuf[30];
	printf("It's %d:%02d:%02d\n",
		tmp-&gt;tm_hour, tmp-&gt;tm_min, tmp-&gt;tm_sec);
	strftime(fmtbuf, sizeof fmtbuf, "%A, %B %d, %Y", tmp);
	printf("on %s\n", fmtbuf);
</pre>



(Note that these functions take a <em>pointer</em>
to the <TT>time_t</TT> variable,
even when they will not be modifying it.<a href="../../lib/prelong.html" rel=subdocument>[footnote]</a>
)
</p><p>If you need sub-second resolution,
see question <a href="faqcatea63.html?sec=osdep#subsecond">19.37</a>.
</p>


<p>References:

K&amp;R2 Sec. B10 pp. 255-7
<br>
ISO Sec. 7.12
<br>
H&amp;S Sec. 18
<hr><hr><hr>
<a name="mktime">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../lib/mktime.html"><!-- qtag -->Question 13.13</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
I know that the library function <TT>localtime</TT>
will convert a <TT>time_t</TT> into a broken-down <TT>struct&nbsp;tm</TT>,
and that <TT>ctime</TT>
will convert a
<TT>time_t</TT> to a printable string.
How can I
perform the inverse operations of converting
a <TT>struct&nbsp;tm</TT> or a string into a <TT>time_t</TT>?
</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
ANSI C specifies a library function, <TT>mktime</TT>, which converts a
<TT>struct&nbsp;tm</TT> to a <TT>time_t</TT>.
</p><p>Converting a string to a <TT>time_t</TT> is harder, because of the wide
variety of date and time formats which
might be encountered.
Some systems

provide a <TT>strptime</TT> function,
which is basically the inverse of <TT>strftime</TT>.
Other popular functions are
<TT>partime</TT>
(widely distributed with the RCS package)
and
<TT>getdate</TT>

(and a few others,

from the C news distribution).
See question <a href="faqcatccbd.html?sec=resources#sources">18.16</a>.
</p>



<p>References:

K&amp;R2 Sec. B10 p. 256
<br>
ISO Sec. 7.12.2.3
<br>
H&amp;S Sec. 18.4 pp. 401-2
<hr><hr><hr>
<a name="calendar">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../lib/calendar.html"><!-- qtag -->Question 13.14</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
How can I add
N
days to a date?


How can I find the difference between two dates?

</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
The ANSI/ISO Standard C <TT>mktime</TT> and
<TT>difftime</TT> functions
provide
some
(limited)
support for
both problems.
<TT>mktime</TT> accepts non-normalized dates,
so it is straightforward to
take a filled-in <TT>struct&nbsp;tm</TT>,
add or subtract from the <TT>tm_mday</TT> field,
and call <TT>mktime</TT> to normalize the year, month, and day fields
(and
incidentally
convert to a <TT>time_t</TT> value).
<TT>difftime</TT> computes the difference,
in seconds,
between two <TT>time_t</TT> values;
<TT>mktime</TT> can be used to compute <TT>time_t</TT> values for two dates to
be subtracted.
</p><p>However,
these solutions
are guaranteed to work correctly
only
for dates



in the range
which can be represented as <TT>time_t</TT>'s
<a href="../../lib/fn73.html" rel=subdocument>[footnote]</a>
.
The <TT>tm_mday</TT> field is an <TT>int</TT>,
so day offsets of more than 32,736

or so
may cause overflow.

(See below for an alternative solution without these limitations.)
Note also



that


at
daylight saving time
changeovers,
local days
are not
24 hours long,
so be careful

if you try to divide
by 86,400 seconds/day.
</p><p>Here is a code fragment to
compute the date 90 days past October 24, 1994:
<pre>
#include &lt;stdio.h&gt;
#include &lt;time.h&gt;

tm1.tm_mon = 10 - 1;
tm1.tm_mday = 24;
tm1.tm_year = 1994 - 1900;
tm1.tm_hour = tm1.tm_min = tm1.tm_sec = 0;
tm1.tm_isdst = -1;

tm1.tm_mday += 90;

if(mktime(&amp;tm1) == -1)
	fprintf(stderr, "mktime failed\n");
else	printf("%d/%d/%d\n",
		tm1.tm_mon+1, tm1.tm_mday, tm1.tm_year+1900);
</pre>
(Setting <TT>tm_isdst</TT> to -1
helps to guard against daylight saving time anomalies;
setting <TT>tm_hour</TT> to 12 would, too.)
</p><p>Here is
a piece of
code to
compute the difference
in days
between
February 28 and March 1 in the year 2000:
<pre>
	struct tm tm1, tm2;
	time_t t1, t2;

	tm1.tm_mon = 2 - 1;
	tm1.tm_mday = 28;
	tm1.tm_year = 2000 - 1900;
	tm1.tm_hour = tm1.tm_min = tm1.tm_sec = 0;
	tm1.tm_isdst = -1;