Keith Thompson wrote:
pete <pf*****@mindspring.comwrites:
>Tammy wrote:
>>Hello all,
I am wondering what is the best way to declare a struct to be used in
other c and c++ files. Such as for a C API that will be used by
others.
1. Declaring the typedef and the struct in the header file and
including this file in all source files that need it?
I define the typedef in the header file
and include this file in all source files that need it.
http://www.mindspring.com/~pfilandr/...ver/e_driver.h
#define E_TYPE struct {char array[40]; d_type data;} e_type
#define D_TYPE long double d_type
typedef D_TYPE;
typedef E_TYPE;
http://www.mindspring.com/~pfilandr/C/e_driver/
That's a very odd use of macros; I find it extremely counterintuitive.
Looking at the web page, it makes *some* sense in context. You have
(I'm abbreviating this):
#define STRUCTURES 0 /* 0 or 1, This is the line to change */
#if STRUCTURES == 0 /* Not this one */
#define E_TYPE long unsigned e_type
#define D_TYPE long unsigned d_type
#else
#define E_TYPE struct {char array[40]; d_type data;} e_type
#define D_TYPE long double d_type
#endif
typedef D_TYPE;
typedef E_TYPE;
I'm sure there's some good reason to conditionally define E_TYPE and
D_TYPE either as unsigned long or as a struct and a long double;
I prefer to have the readily changeable parts of the program,
be macros.
The program also prints out the stringized macros.
The proper use of of the e_type interface,
is to define at least these three macros in a header file,
(there may be other macros depending on the sort algorithm)
for sorting functions which can then be used to sort
arrays of elements of any type, including arrays of arrays:
#define E_TYPE
#define MOV(A, B)
#define GT(A, B)
For example, I was looking at:
http://www.pobox.com/~qed/sort.html
which redirected me to
http://www.azillionmonkeys.com/qed/sort.html
and I downloaded the program at this link:
http://www.azillionmonkeys.com/qed/sorttest.c
and since I like to race sorting functions,
I changed the name of the program to pq_test
and replaced the definition of main with this:
#include "test_sort.h"
#define str(s) # s
#define xstr(s) str(s)
int main (void)
{
int seed = 0;
double r0, r1, r2, r3, r4, r5, r6, r7;
/* Warm up the cache */
{
int i;
for (i = 0; i < NUM_ITEMS; i++) numbers[i] = i;
heapSort (numbers, NUM_ITEMS);
}
r0 = timetest (seed, heapSort);
r1 = timetest (seed, quickSort);
r2 = timetest (seed, mergeSort);
r3 = NUM_ITEMS 600 ? 0 : timetest (seed, insertSort);
r4 = timetest (seed, hsortmwrapper);
r5 = timetest (seed, pqsortwrapper);
r6 = timetest (seed, stablewrapper);
r7 = NUM_ITEMS 600 ? 0 : timetest (seed, sisortwrapper);
puts("/* BEGIN pq_test.c output */\n");
puts("#define NUM_ITEMS " xstr(NUM_ITEMS) "\n");
printf (" heapsort: %.3f\n", r0);
printf (" quicksort: %.3f\n", r1);
printf (" mergesort: %.3f\n", r2);
printf ("insertsort: %.3f\n", r3);
putchar('\n');
printf (" hsortm: %.3f\n", r4);
printf (" pqsort: %.3f\n", r5);
printf (" stable: %.3f\n", r6);
printf (" sisort: %.3f\n", r7);
puts("\n/* END pq_test.c output */");
return 0;
}
Then I got these results:
/* BEGIN pq_test.c output */
#define NUM_ITEMS 6000
heapsort: 4.594
quicksort: 3.375
mergesort: 4.531
insertsort: 0.000
hsortm: 4.296
pqsort: 2.562
stable: 3.640
sisort: 0.000
/* END pq_test.c output */
Then I changed NUM_ITEMS to 600 and got these results:
/* BEGIN pq_test.c output */
#define NUM_ITEMS 600
heapsort: 0.375
quicksort: 0.265
mergesort: 0.359
insertsort: 2.406
hsortm: 0.344
pqsort: 0.203
stable: 0.281
sisort: 1.125
/* END pq_test.c output */
I also wrote 4 files to complete the program:
test_sort.h
test_sort.c
pqsort.h
pqsort.c
The point of doing it that way, is that the file,
pqsort.c, can be used as is, to sort arrays of any type,
without changing even a single byte.
The files look like this:
/* BEGIN test_sort.h */
#ifndef H_TEST_SORT_H
#define H_TEST_SORT_H
void hsortmwrapper(int numbers[], int qty);
void pqsortwrapper(int numbers[], int qty);
void stablewrapper(int numbers[], int qty);
void sisortwrapper(int numbers[], int qty);
#endif
/* END test_sort.h */
/* BEGIN test_sort.c */
#include <assert.h>
#include "test_sort.h"
#include "pqsort.h"
void hsortmwrapper(int numbers[], int qty)
{
hsortm(numbers, qty);
}
void pqsortwrapper(int numbers[], int qty)
{
assert(SMALL_PARTITION >= 4);
pqsort(numbers, qty);
}
void stablewrapper(int numbers[], int qty)
{
assert(SMALL_MERGE >= 1);
stable(numbers, qty);
}
void sisortwrapper(int numbers[], int qty)
{
sisort(numbers, qty);
}
/* END test_sort.c */
/* BEGIN pqsort.h */
#ifndef H_PQSORT_H
#define H_PQSORT_H
#include <stddef.h>
#define E_TYPE int e_type
#define MOV(A, B) ((void)(*(A) = *(B)))
#define GT(A, B) (*(A) *(B))
#define SMALL_PARTITION 24
#define SMALL_MERGE 32
typedef E_TYPE;
/*
** (hsortm) is a double siftdown, casual heapsort.
*/
void hsortm(e_type *array, size_t nmemb);
/*
** (pqsort) is an introspective, median of three, quicksort.
*/
void pqsort(e_type *array, size_t nmemb);
/*
** (stable) is a stable merge sort / insertion sort.
*/
void stable(e_type *array, size_t nmemb);
/*
** (sisort) is a stable insertion sort.
*/
void sisort(e_type *array, size_t nmemb);
#endif
/* END pqsort.h */
/* BEGIN pqsort.c */
#include <stdlib.h>
#include "pqsort.h"
#define SWAP(A, B, T) \
(MOV((T), (A)), MOV((A), (B)), MOV((B), (T)))
#define SORT_3(A, B, C, T) \
if (GT((A), (B))) { \
MOV((T), (A)); \
if (GT((C), (B))) { \
MOV((A), (B)); \
if (GT((T), (C))) { \
MOV((B), (C)); \
MOV((C), (T)); \
} else { \
MOV((B), (T)); \
} \
} else { \
MOV((A), (C)); \
MOV((C), (T)); \
} \
} else { \
if (GT((B), (C))) { \
MOV((T), (B)); \
if (GT((A), (C))) { \
MOV((B), (A)); \
MOV((A), (C)); \
} else { \
MOV((B), (C)); \
} \
MOV((C), (T)); \
} \
}
#define SIFTDOWNM(P) \
{ \
parent = (P); \
child = parent * 2; \
MOV(&temp, array + parent); \
while (nmemb - parent parent) { \
if (GT(array + child + 1, array + child)) { \
++child; \
} \
if (GT(array + child, &temp)) { \
MOV(array + parent, array + child); \
parent = child; \
child *= 2; \
} else { \
break; \
} \
} \
if (nmemb == child && GT(array + child, &temp)) { \
MOV(array + parent, array + child); \
parent = child; \
} \
MOV(array + parent, &temp); \
}
static void pqloop(e_type *array, size_t nmemb, size_t d);
static void merge(e_type *array, size_t nmemb, e_type *buff);
void hsortm(e_type *array, size_t nmemb)
{
size_t p, child, parent;
e_type temp;
if (nmemb 1) {
p = --nmemb / 2;
do {
SIFTDOWNM(p);
} while (p-- != 0);
SWAP(array, array + nmemb, &temp);
while (--nmemb != 0) {
SIFTDOWNM(0);
SWAP(array, array + nmemb, &temp);
}
}
}
void pqsort(e_type *array, size_t nmemb)
{
size_t d, n;
d = 2;
for (n = nmemb / 4; n != 0; n /= 2) {
++d;
}
pqloop(array, nmemb, 2 * d);
}
void stable(e_type *array, size_t nmemb)
{
e_type *buff = malloc(nmemb / 2 * sizeof *buff);
if (buff != NULL) {
merge(array, nmemb, buff);
free(buff);
} else {
sisort(array, nmemb);
}
}
void sisort(e_type *array, size_t nmemb)
{
e_type *base, *low, *high, temp;
if (nmemb-- 1) {
base = array;
do {
low = array++;
if (GT(low, array)) {
high = array;
MOV(&temp, high);
do {
MOV(high, low);
if (--high == base) {
break;
}
--low;
} while (GT(low, &temp));
MOV(high, &temp);
}
} while (--nmemb != 0);
}
}
static void pqloop(e_type *array, size_t nmemb, size_t d)
{
e_type *i, *j, temp;
while (nmemb SMALL_PARTITION) {
if (!d--) {
hsortm(array, nmemb);
return;
}
i = 1 + array;
j = --nmemb + array;
SORT_3(j, array, i, &temp);
do {
SWAP(j, i, &temp);
do {
++i;
} while (GT(array, i));
do {
--j;
} while (GT(j, array));
} while (j i);
SWAP(array, j, &temp);
pqloop(j + 1, nmemb + array - j, d);
nmemb = j - array;
}
sisort(array, nmemb);
}
static void merge(e_type *array, size_t nmemb, e_type *buff)
{
if (nmemb SMALL_MERGE) {
e_type *mid_ptr;
size_t const half = nmemb / 2;
e_type *const after_buff = buff + half;
e_type *const middle = array + half;
e_type *const after_array = array + nmemb;
merge(middle, nmemb - half, buff);
merge(array, half, buff);
do {
if (GT(array, middle)) {
mid_ptr = middle;
buff = after_buff;
do {
--buff;
--mid_ptr;
MOV(buff, mid_ptr);
} while (array != mid_ptr);
MOV(array, middle);
mid_ptr = middle + 1;
while (middle != ++array) {
if (GT(buff, mid_ptr)) {
MOV(array, mid_ptr);
++mid_ptr;
} else {
MOV(array, buff);
++buff;
}
}
while (after_buff != buff) {
if (after_array != mid_ptr) {
if (GT(buff, mid_ptr)) {
MOV(array, mid_ptr);
++mid_ptr;
} else {
MOV(array, buff);
++buff;
}
++array;
} else {
do {
MOV(array, buff);
++array;
++buff;
} while (after_buff != buff);
break;
}
}
break;
} else {
++array;
}
} while (middle != array);
} else {
sisort(array, nmemb);
}
}
/* END pqsort.c */
--
pete
