Mar 95 Challenge
- Jan 95 Challenge
- Feb 95 Challenge
- Apr 95 Challenge
- May 95 Challenge
- Jun 95 Challenge
- Jul 95 Challenge
- Aug 95 Challenge
- Sep 95 Challenge
- Oct 95 Challenge
- Nov 95 Challenge
- Dec 95 Challenge
Volume Number: 11
Issue Number: 3
Column Tag: Programmer’s Challenge
Programmer’s Challenge 
By Mike Scanlin, Mountain View, CA
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
Method Dispatcher
One of the main reasons why I don’t like object oriented languages is because of the
inefficiencies the language usually introduces on the runtime code. If you’ve ever
traced through a method dispatch routine then you know what I mean (what ever
happened to the days of simple, direct JSR’s?). This month you have a chance to write
a fast method dispatcher. Who knows? If it’s efficient enough I might just toss my
assembler and use your dispatcher with a high level language instead...
The prototype of the function you write is:
typedef unsigned short ushort;
typedef ushort ClassID;
typedef ushort MethodNumber;
MethodAddress
FindMethod(theClassID, theMethodNumber)
ClassID theClassID;
MethodNumber theMethodNumber;
TheMethodNumber is the number of the method you’re trying to find the address of and
theClassID is the ID of the class you want it for. You’ll pass theClassID to a function
called GetClassPtr to get a pointer to a Class data structure, which looks like this:
typedef void *MethodAddress;
typedef struct {
MethodNumber methodNumber;
MethodAddress methodAddress;
} MethodEntry;
typedef struct {
ushort inheritedCount;
ushort inheritedClasses[15];
MethodNumber largestMethodNumber;
ushort methodCount;
MethodEntry methods[];
} Class, *ClassPtr;
The function GetClassPtr will be part of my test bench, although you’ll have to
implement at least a rudimentary version of it to test your program (or you can
e-mail me for a sample version):
ClassPtr
GetClassPtr(classID)
unsigned short classID;
If GetClassPtr returns -1 (kClassNotFound) then the class cannot be found and your
FindMethod routine should return 0 (kMethodNotFound). I will be providing sample
data and a sample GetClassPtr function for those who are interested. To get a copy, send
me e-mail at scanlin@genmagic.com (internet) or any of the Programmer Challenge
addresses listed on page 2.
Once you have a ClassPtr you should look in that class’s methods[] array to see if
you can find an entry whose methodNumber is equal to theMethodNumber. Methods[] is
a variable-length array (thus, making Class a variable-size structure) containing
methodCount number of entries which are sorted smallest to largest by methodNumber.
MethodCount is 1-based and is always greater than zero. If you find a match then you
should return the corresponding methodAddress.
If you don’t find a match then you should look at the inherited classes (starting
with index zero) to see if the method is implemented by one of this class’s
superclasses. We support multiple inheritance here and the number of classes we
inherit from is stored in inheritedCount (which will be from zero to 15). The class
IDs of the classes we inherit from are stored in the inheritedClasses[ ] array. You can
pass any of the entries in inheritedClasses to GetClassPtr to get a ClassPtr to that class.
If you can’t find the requested methodNumber in any part of the inheritance tree
then FindMethod should return zero (kMethodNotFound).
Here’s a simple example. These 54 bytes (starting at location 0x1000)
represent class ID 5:
1000:00000000 00000000 00000000 00000000
1010:00000000 00000000 00000000 00000000
1020:00680003 0023AAAA AAAA0057 BBBBBBBB
1030:0068CCCC CCCC
The short at location 1000 (inheritedCount) tells us that there are no inherited
classes for this class. The short at location 1022 (methodCount) tells us that this class
has 3 methods. Methods[0] is from 1024 to 1029; the methodNumber is 23 and the
methodAddress is AAAAAAAA (this is just test data to illustrate the structure).
Methods[1] is from 102A to 102F and methods[2] is from 1030 to 1035. The short at
location 1020 (largestMethodNumber) is equal to the methodNumber of the last
MethodEntry in the list (which is the largest methodNumber overall since the list is
sorted). In other words, the expression theClassPtr->largestMethodNumber ==
theClassPtr-> methods[theClassPtr->methodCount-1].methodNumber is always
true.
If this class had inherited from class 7 and class 9 then it would have looked like
this instead:
1000:00020007 00090000 00000000 00000000
1010:00000000 00000000 00000000 00000000
1020:00680003 0023AAAA AAAA0057 BBBBBBBB
1030:0068CCCC CCCC
In either case, if you call GetClassPtr(5), since this is class 5 we’re looking at, you
would have the value 0x1000 (as type ClassPtr) returned to you.
Since I’ll be calling FindMethod several thousand times with the same set of
classes (just like a real runtime system!) you’ll probably want to implement some
kind of cache. And since it is desirable for runtime systems to take as little memory as
possible, we’re going to have a rule that says your code cannot use more than 16K of
memory for its cache (use a static to keep a pointer to it). The total number of methods
in the set of classes I’ll be testing with is about 5000, numbered from 1 to 5000. The
total number of classes is about 400, numbered from 1 to 400. Those 400 classes will
implement an average of 15 methods each and will inherit from an average of 5 other
classes (that’s 5 total, once you’ve walked the entire inheritance tree for a particular
class). Of course, some methods will be called frequently while others are hardly ever
called.
Because this is a little complex, I’m going to give you the brute force way of doing
what I’ve described. I’m sure you can do better than this (I’ve used short variable
names so that the code will fit in the magazine column):
MethodAddress
FindMethod(cid, mn)
ClassID cid;
MethodNumber mn;
{
ClassPtr cp;
MethodAddress addr;
int i;
cp = GetClassPtr(cid);
if (cp == kClassNotFound)
return kMethodNotFound;
/* look in this class */
i = 0;
do {
if (mn == cp->methods[i].methodNumber)
return cp->methods[i].methodAddress;
i++;
} while (i < cp->methodCount);
/* look in superclasses */
i = 0;
while (i < cp->inheritedCount) {
addr = FindMethod( cp->inheritedClasses[i], mn);
if (addr != kMethodNotFound)
return addr;
i++;
}
return kMethodNotFound;
}
E-mail me if you have any questions or if you want the sample data and
GetClassPtr function. And if you want to see your name in print all you have to do is
either enter a challenge or have me use one of your suggested challenges.
Two Months Ago Winner
Congratulations to Kevin Cutts (Schaumburg, IL) for winning the Poker Hand
Evaluator Challenge. And kudos to Gustav Larsson (Mountain View, CA) for being
60% smaller and only about 4% slower than Kevin.
Here are the times and code sizes for each entry. Numbers in parens after a
person’s name indicate how many times that person has finished in the top 5 places of
all previous Programmer Challenges, not including this one:
Name time code
Kevin Cutts (3) 317 6022
Gustav Larsson 331 2656
Jeff Mallett (3) 331 9428
Ernst Munter (5) 457 2516
Dave Darrah (1) 749 2996
Raffi Kasparian (1) 1230 7394
Kevin wrote four different versions of his BestHand routine; one for every
combination of the Booleans wildCardAllowed and straightsAndFlushesValid. That’s a
great idea for performance but because of space constraints, we’re only listing the
BestHandNoWild version which is for the case where wild cards are not allowed but
straights and flushes are valid (which is probably the typical case for poker). The
source code to the remaining cases can be found on-line or on this month’s code disk.
Here is Kevin’s winning solution:
January Solution -Poker-
by Kevin M. Cutts
#include
#include
typedef unsigned char Card;
typedef struct SevenCardHand
{
Card cards[7];
} SevenCardHand;
typedef struct FiveCardHand
{
Card cards[5];
} FiveCardHand;
short ComparePokerHands(
SevenCardHand *,
SevenCardHand *,
FiveCardHand *,
FiveCardHand *,
Boolean,
Card,
Boolean,
void *);
/* Used to remove the suit information and leave only the count from the card */
unsigned char theValue[] = {
0,1,2,3,4,5,6,7,8,9,10,11,12,
0,1,2,3,4,5,6,7,8,9,10,11,12,
0,1,2,3,4,5,6,7,8,9,10,11,12,
0,1,2,3,4,5,6,7,8,9,10,11,12,
};
/* Used to remove card value and leave the suit indicator */
unsigned char theSuit[] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,1,1,1,1,1,1,1,1,1,1,1,
2,2,2,2,2,2,2,2,2,2,2,2,2,
3,3,3,3,3,3,3,3,3,3,3,3,3,
};
/* A bit for each card value (aces have two bits) */
unsigned short theValueBit[] = {
0x1000,0x800,0x400,0x200,0x100,0x80,0x40,
0x20,0x10,0x8,0x4,0x2,0x2001,
0x1000,0x800,0x400,0x200,0x100,0x80,0x40,
0x20,0x10,0x8,0x4,0x2,0x2001,
0x1000,0x800,0x400,0x200,0x100,0x80,0x40,
0x20,0x10,0x8,0x4,0x2,0x2001,
0x1000,0x800,0x400,0x200,0x100,0x80,0x40,
0x20,0x10,0x8,0x4,0x2,0x2001,
};
#define fiveAlike 0xa000
#define straightFlush 0x9000
#define fourAlike 0x8000
#define fullHouse 0x7000
#define flush 0x6000
#define straight 0x5000
#define threeAlike 0x4000
#define twoPair 0x3000
#define pair 0x2000
#define nonCard 0xff
/* These four functions are custom to handle the four bools wild and flush */
unsigned int BestHandNoWild(SevenCardHand *theHand,
FiveCardHand *theBest);
unsigned int BestHand(SevenCardHand *theHand,
FiveCardHand *theBest, Card wildCard);
unsigned int BestHandNoFlush(SevenCardHand *theHand,
FiveCardHand *theBest, Card wildCard);
unsigned int BestHandNoFlushNoWild(SevenCardHand *theHand,
FiveCardHand *theBest);
BestHandNoWild
unsigned int BestHandNoWild(SevenCardHand *theHand,
FiveCardHand *theBest)
{
/* How many of each card value encountered */
unsigned char handValues[13];
/* How many of each suit encountered */
unsigned char handSuits[4];
/* Bit field describing on a suit by suit basis how populated the hand is */
short handRuns[4];
register short i;
short j;
Card bestCard, bestPair, goodPair, bestTri, bestQuad;
Card *cardPtr;
short runSweep, runResult, runCount;
/* Zero out all of the counts */
*(long *)&handValues[0] =