Linking to pages and resources on this site is encouraged, but the links MUST be placed on a publically-accessible page. Placing links behind any form of login or access restriction is strictly forbidden.
Pigeon's Device
Many may have heard tell of Duff's device, a rather neat
loop optimisation technique in C.
This page provides details of Pigeon's device - a related but independently-originated technique. The original
instantiation of Pigeon's device was in a piece of C code written for MS-DOS before the days of the internet,
so I had not heard of Duff's device. When I did, the similarity between the techniques was immediately apparent.
The original Pigeon's device was in a function for comparing two date/time records in various different manners
according to the desired sort order - FORWARD, forward chronological order; REVERSE, reverse chrononological order;
and REVDFWDT, dates in reverse but times within each day sorted forwards.
int lfdcmp(const void *a, const void *b) {
static int mode;
struct date d1, d2;
struct time t;
if (b==NULL) return(mode);
if (a==NULL) {
mode=*(int *)b;
return(0);
}
/* Isn't C a wonderful language? */
switch (mode) {
case REVDFWDT: unixtodos(((lfdy *)a)->stamplog, &d1, &t);
unixtodos(((lfdy *)b)->stamplog, &d2, &t);
if ((d1.da_day==d2.da_day) && (d1.da_mon==d2.da_mon) \
&& (d1.da_year==d2.da_year)) {
case FORWARD : return(longsub(((lfdy *)a)->stamplog,((lfdy *)b)->stamplog));
break;
} else {
case REVERSE : return(longsub(((lfdy *)b)->stamplog,((lfdy *)a)->stamplog));
break;
}
default : pigeonerror(FATAL,"Bad lfdcmp mode: %d\n\r",mode);
break;
}
return(0);
}
The function starts with a Gruesome Hack to set and read the comparison mode. I did this because
the function is called from a library sort routine and there is no way to get that routine to pass
a third "mode" parameter. There are various other ways to get the mode into the function but since
it was intended in any case to specify that one should not set the mode directly but should instead
use the functions setsortmode() and getsortmode(), I made the hidden workings inside those functions
do it this way because it was more fun.
Then we move on to the Pigeon's Device proper. In the case of FORWARD sorting the function simply
returns a value whose sign depends on the forward order of two date records - longsub() is a function
which subtracts one value of type long from another and returns the result as a value of type int;
such a value will satisfy the requirements of the library sort function without further processing. In
the case of REVERSE sorting the two records are simply compared the other way round.
In the case of REVDFWDT sorting - Reverse Date Forward Time - the first operation is to extract the
date information from the records, which are in UNIX timestamp format which obfuscates midnight.
So the dates are converted to a DOS format with separate values for date and time. Then we reach
the if statement intertwined with the switch statement. If the two records relate to the same date,
they are compared in forward order; if they relate to different dates, they are compared in reverse
order. The result of this is that the overall list comes out sorted with the dates backwards but
the times within each day still forwards.
The default case is a "bug catcher"; if the function is used as intended with the mode set by
calling setsortmode() invalid values shouldn't get in there in the first place.
And that is Pigeon's device, in context.
Back to Pigeon's Nest
Be kind to pigeons