allbery@uunet.UU.NET (Brandon S. Allbery - comp.sources.misc) (03/05/89)
Posting-number: Volume 6, Issue 43
Submitted-by: rae@b.UUCP (Reid Ellis)
Archive-name: lookup.c++
The following shar implements a lookup table in C++. Two alternate
algorithms are presented, binary and linear search, in the files lookup.c
and lookup2.c, respectively. See the README file for more details. Don't
worry -- there's an "exit" before my .signature.
Reid
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of shell archive."
# Contents: Makefile README lookup.c lookup.h lookup2.c test.c
# testcmd.c testhelp.c
# Wrapped by rae@geaclib on Tue Feb 7 05:37:45 1989
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f Makefile -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"Makefile\"
else
echo shar: Extracting \"Makefile\" \(419 characters\)
sed "s/^X//" >Makefile <<'END_OF_Makefile'
XCC = CC -c -I/usr/include/CC
XLD = CC
X
X.c.o:
X $(CC) $(CFLAGS) $<
X
X# lookup2 does a linear search -- good for unsorted table
X# lookup does a binary search -- good for a sorted table
XOBJ = test.o lookup2.o testcmd.o testhelp.o
X#OBJ = test.o lookup.o testcmd.o testhelp.o
XTARG = tt
X
X$(TARG): $(OBJ)
X $(LD) -o $(TARG) $(OBJ) $(LDFLAGS)
X @strip $(TARG)
X
Xlookup.o lookup2.o : lookup.h
Xtest.o : lookup.h
Xtesthelp.o : lookup.h
END_OF_Makefile
if test 419 -ne `wc -c <Makefile`; then
echo shar: \"Makefile\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f README -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"README\"
else
echo shar: Extracting \"README\" \(2827 characters\)
sed "s/^X//" >README <<'END_OF_README'
XDESCRIPTION
X
XUsing the files lookup.c [or lookup2.c] and lookup.h, you can easily maintain
Xa command lookup table. The table must be of type "entry *", and you can see
Xin the example code [test.c, testcmd.c, testhelp.c] that I used an aggreagate
Xarray of the form:
X
Xentry list[] = { ... };
X
XThe first "entry" in the list must have a count and a pointer to an error
Xfunction. If you have no error function, create a null function, which
Xdoes nothing, and use a pointer to it. Since the number occupies the
Xposition of a char*, you have to cast it to such. i.e., if you have
X#define'd NUM to the number of elements, you would say
X
Xentry list[] = {
X (char *)NUM, &err,
X ...
X };
X
Xwhere err is the error-handling function. err would be called when a string
Xnot in the list is referenced.
X
XNow, the list is not the object that does the work. Another object, of class
X"lookup" is initialized with a pointer to an "entry *". e.g., given the
Xabove example, you could say:
X
Xlookup cmd(list);
X
XThereafter, to retrieve the function pointer desired, you simply reference
X"cmd" with a string:
X
Xint (*proc)(const char *);
Xproc=cmd["query"];
X
XThis would cause "proc" to point to the function associated with the
Xword "query", if any; otherwise, it would point to the error function,
Xwhich we designated above to be "err". Now you can happily dereference the
Xpointer and pass it a "const char *":
X
Xproc("testing");
X
XNow note that you can do both of these at once:
X
Xcmd["query"]("Testing");
X
XIsn't that special?
X
XThe only difference between lookup.c and lookup2.c is the implementation.
XEach gives you an advantage. If your list of names is sorted, use
Xlookup.c since it uses a binary search. Obviously, if they are not
Xin any order, a binary search will not work, so lookup2.c just does
Xa linear search. This is the only difference between the two.
X
X
XARGUMENT TYPE
X
XAll of the function pointers in the "entry" list must take the same
Xargument[s], if any, and return the same value type. I haven't built
Xany elegant macros, but there are #defines in "lookup.h" to handle both
Xof these problems in a less than elegant manner.
X
XThe two macros ARG_TYPE and RET_TYPE define the argument type and value
Xvalue returned by the function pointers. Just change these to handle whatever
Xtypes you like.
X
X
XCAVEATS
X
XThis is one of my first attempts at C++; I hope you find it useful. If
Xyou make any major modifications, or even more importantly, if you find any
Xbugs, please let me know so I can fix my source and post the patches for
Xone and all.
X
X
XCOPYRIGHT
X
XI the author hereby place this code in the public domain. Make enough
Xmoney to buy Canada and hire me as Prime Minister!
X
X
XAUTHOR
X
XReid Ellis
X176 Brookbanks Drive
XDon Mills, Ontario
XM3A 2T5
XCANADA
X+1 416 446 1644
Xrae@geaclib.uucp if you're lucky, or else geaclib!rae@geac.uucp
END_OF_README
if test 2827 -ne `wc -c <README`; then
echo shar: \"README\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lookup.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lookup.c\"
else
echo shar: Extracting \"lookup.c\" \(652 characters\)
sed "s/^X//" >lookup.c <<'END_OF_lookup.c'
X#include <stream.h>
X#include <string.h>
X#include "lookup.h"
X
Xproc lookup::operator[](const char *str)
X {
X int n;
X entry
X *upper = table + max - 1,
X *lower = table,
X *mid = lower + (upper-lower)/2;
X
X for(n=1; n && upper - lower > 1; )
X {
X n = strcmp(str, mid->name);
X if(n == 0)
X upper = lower = mid;
X else
X {
X if(n < 0) upper = mid;
X else lower = mid;
X mid = lower + (upper - lower)/2;
X }
X }
X
X if(n < 0) n = strcmp(str, mid->name);
X else if(n > 0)
X {
X mid = upper;
X n = strcmp(str, mid->name);
X }
X
X if(n) return dflt; // not in table
X else return mid->f; // found it
X }
END_OF_lookup.c
if test 652 -ne `wc -c <lookup.c`; then
echo shar: \"lookup.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lookup.h -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lookup.h\"
else
echo shar: Extracting \"lookup.h\" \(392 characters\)
sed "s/^X//" >lookup.h <<'END_OF_lookup.h'
X#ifndef LOOKUPH
X#define LOOKUPH
X
X#define ARG_TYPE const char *
X#define RET_TYPE int
X
Xtypedef RET_TYPE (*proc)(ARG_TYPE);
X
Xstruct entry {
X const char *name;
X proc f;
X };
X
Xclass lookup {
X entry *table;
X proc dflt;
X int max;
Xpublic:
X lookup(entry *t) {
X dflt = t->f;
X max = int(t->name);
X table = t + 1;
X }
X // This really does take a const char *
X proc operator[](const char *);
X };
X#endif
END_OF_lookup.h
if test 392 -ne `wc -c <lookup.h`; then
echo shar: \"lookup.h\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f lookup2.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"lookup2.c\"
else
echo shar: Extracting \"lookup2.c\" \(263 characters\)
sed "s/^X//" >lookup2.c <<'END_OF_lookup2.c'
X#include <stream.h>
X#include <string.h>
X#include "lookup.h"
X
Xproc lookup::operator[](const char *str)
X {
X entry *t=table;
X
X for(; t-table < max; t++)
X if(!strcmp(t->name, str))
X break;
X
X if(t-table<max) return t->f;
X else return dflt;
X }
END_OF_lookup2.c
if test 263 -ne `wc -c <lookup2.c`; then
echo shar: \"lookup2.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f test.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"test.c\"
else
echo shar: Extracting \"test.c\" \(882 characters\)
sed "s/^X//" >test.c <<'END_OF_test.c'
X#include <stream.h>
X#include <string.h>
X#include "lookup.h"
X
Xextern RET_TYPE
X a(ARG_TYPE),
X b(ARG_TYPE),
X c(ARG_TYPE),
X help(ARG_TYPE),
X oops(ARG_TYPE);
X
Xentry list[] = {
X (char *)4, &oops,
X "acmd", &a,
X "bcmd", &b,
X "c", &c,
X "help", &help,
X };
X
Xint main(int argc, char *argv[])
X {
X char *progname = argv[0];
X lookup command(list);
X char word[200]; // of type ARG_TYPE
X int i;
X
X argc--; // to shut up CC
X
X while(cout << "% ", cin >> word && strcmp(word, "quit"))
X {
X
X // Note that in the next statement, we are in
X // fact saying command[const char *](ARG_TYPE)
X // In this case, ARG_TYPE *is* const char *, so we
X // are just passing the same thing to both [] and ().
X
X if(i = command[word](word))
X {
X // the function returned a non-zero result
X cerr << form("%s: %s returned %d\n", progname, word, i);
X }
X }
X return 0;
X }
END_OF_test.c
if test 882 -ne `wc -c <test.c`; then
echo shar: \"test.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f testcmd.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"testcmd.c\"
else
echo shar: Extracting \"testcmd.c\" \(328 characters\)
sed "s/^X//" >testcmd.c <<'END_OF_testcmd.c'
X#include <stream.h>
X
Xint a(const char *s)
X {
X cout << form("a: %s\n", s);
X return 0;
X }
X
Xint b(const char *s)
X {
X cout << form("b: %s\n", s);
X return 0;
X }
X
Xint c(const char *s)
X {
X cout << form("c: %s\n", s);
X return 0;
X }
X
Xint oops(const char *s)
X {
X cout << form("command %s unavailable\n", s);
X return 0;
X }
END_OF_testcmd.c
if test 328 -ne `wc -c <testcmd.c`; then
echo shar: \"testcmd.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f testhelp.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"testhelp.c\"
else
echo shar: Extracting \"testhelp.c\" \(341 characters\)
sed "s/^X//" >testhelp.c <<'END_OF_testhelp.c'
X#include <stream.h>
X#include "lookup.h"
X
Xextern entry list[];
X
Xint help(const char *s)
X {
X entry *t = list;
X
X (void) s; // "use" s so that CC won't complain
X cout << "Available commands:\n\n";
X cout << "quit\t";
X
X for(int max=1+int((t++)->name); t-list < max; t++)
X cout << form("%s\t", t->name);
X
X cout.put('\n');
X return 0;
X }
END_OF_testhelp.c
if test 341 -ne `wc -c <testhelp.c`; then
echo shar: \"testhelp.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
echo shar: End of shell archive.
exit 0
--
Reid Ellis, geaclib!rae@geac.uucp, rae@geaclib.uucp [if you're lucky]