First, let me say, this is *NOT* the FAQ.

Rather...

Everyone knows switch() switches on integer expressions.

Wouldn't It Be Nice if you could select from strings, though...

Well, perhaps one could write "str_switch()", which takes a string,
and an array of strings, and returns the index in the array of a matching
string.  Of course, this would be horribly inefficient - presumably at
least as expensive as the iterative strcmp() so often used as an
alternative, and possibly as bad as the endless if-else-if-else-if...
used in some programs.

But what if one were to build a table?  In every application I've had
where I wish to see which of a set of strings I have, I've had a known
predefined set of strings.  So, the behavior could be something like
        {
                static ss_table *sst;

                if (!sst) {
                        sst = str_stable(stringtable);
                        if (!sst)
                                return 0;
                }
                switch (str_switch(str, sst)) {
                case -1: /* failure */
                        break;
                case 0: /* 1st string in table */
                ...
                }
        }

The idea would be that "str_stable" would build a somewhat more efficient
table representation of what the strings are like.  I could see it being
done with hashes, or with something like what fgrep traditionally uses.

Any prior art?  Ideas I've missed?  I'm thinking about developing this,
since it would be useful in a current application, and I'd like to do it
right, so I don't repeat the work.

My simplest suggestion --> Steal whatever VAX BASIC does.  Cram it into the
next iteration of the standard.  All mortal C programmers will sing your
praises.

Another solution: Have the COMPILER sort the strings AT COMPILE TIME and
place them in an internal array.  Then do a BSEARCH of the array for the
input string to switch on.  Not only portable, but also efficient.  Not
only would they sing your praises, they would recount your glories to their
grandchildren and their great grandchildren.
;-)

/* what the programmer codes: */
char *Animal;
/* ... */
switch (Animal)
{
   case "BEAR":
        /* do stuff */
        break;
   case "LION":
        /* do stuff */
        break;
   case "TIGER":
        /* do stuff */
        break;
   case "EAGLE":
        /* do stuff */
        break;
   case "FROG":
        /* do stuff */
        break;
   case "PYTHON":
        /* do stuff */
        break;
   default:
        /* Warn about the 5 million other possibilities */

char *SwitchStrings[] =
{
         "BEAR",
         "EAGLE",
         "FROG",
         "LION",
         "PYTHON",
         "TIGER"

Peter Seebach <se...@solon.com> wrote in article
<5bdvof$...@solutions.solon.com>...

Then I just switch on MAKETYPE(myString, long) to turn into a long and
use #defines for the cases so I'll have meaningful labels there.

Note that this works for me.  It is definitely not portable, primarily
because byte-swapping will significantly alter the result.

John Currier                      john.curr...@checksol.com
Software Development Engineer     Check Solutions

Well, with some trepidation I'll enter the fray here ...
Be warned this answer gets rather long ;-)

After reading this if anyone wants the perl pre-processor discussed
I'll happily mail it out.

My solution may not be general enough - it is a compile time not run
time solution. Anyway, I had to parse a config file of key/value pairs
and wanted users to be able to write the text corresponding to the name
of the key rather than the numeric #define constant.

Given over 100 constants, I wasn't interested in the strcmp noise.
So I whipped out a perl critter that takes a data file and
gens a header file with #defines and a source file with a hashed array
(257 buckets) and a lookup function that returns the numeric equivalent
of each tag and deals with the collisions.  

Input:

    DB_USER                                 1
    DB_GROUP                                2
    DB_MEMBER                               3
    DB_APPT                                 4
    DB_CONTACT                              5
    DB_KEEPER                               6
    DB_SESSION                              7

Generated Header:

    #define DB_USER                 1
    #define DB_GROUP                2
    #define DB_MEMBER               3
    #define DB_APPT                 4
    #define DB_CONTACT              5
    #define DB_KEEPER               6
    #define DB_SESSION              7

    typedef struct tag_def_dtd
    {
        int         tag;                /* Field tag            */
        char        name[25];           /* Tag name             */
    } tag_def;
    extern tag_def         tag_array[];
    extern int tag_lookup(char *name);

Generated Source:

    tag_def tag_array[] = {
        { 0,                       "-",                     },
        { 0,                       "-",                     },
        ( ... snip ... )
        { DB_USER,                 "DB_USER"                },
        { 0,                       "-",                     },
        { 0,                       "-",                     },
        { DB_SESSION,              "DB_SESSION"             },
        ( ... snip ... )
        { 0,                       "",                      }
    };

    int
    tag_lookup(char *name)
    {
        int     hash;

        strupper (name);
        hash = hash_gen(name);

        while( tag_array[hash].tag != 0 )   /* collision resolution */
        {
            if ( strcmp(name, tag_array[hash].name) == 0 ) break;
            hash++;
        }

        return tag_array[hash].tag;
    }

Sample Usage:

    if ( (table = tag_lookup(argv[1])) == 0 )
    {
            fprintf(stderr, "\n");
            fprintf(stderr, "%s is not a known table name\n\n", argv[1]);
            exit (1);
    }

    or

    switch(tag_lookup(char *str))
    {
        ( ... snip ... )
    }

  For instance:

struct entry
{
  char  *name;
  void (*funct)(void);

        /* code ... */
        struct entry *pse;
        char         *input;

        input = getinput();
        pse = bsearch(input,tabstring,TABSTRINGSIZE,sizeof(struct entry),cmp);
        if (pse) (*pse->funct)();

typedef (*funptr)();

typedef struct {
    char *name;
    funptr action;

entry_t actions[] = {
   E(act1),
   E(act2),
   E(act3),
   E(act4)

This is also the example I use when people say token quoting and token
pasting are useless and should be avoided.  In this case, writing it
out can even introduce bugs, along the lines of:

    { "fmoo", do_foo },

Peter Seebach <se...@solon.com> wrote in article <5bdvof$...@solutions.solon.com>...

I intentionally made the names short, i.e., aaPut and aaGet to
make it convenient to use.  I have to say that this is one of
those libraries that you just didn't know you needed until you
have it available, cheap and easy (kind of like Perl associative
arrays :-) )

I should note that my legal language (which I deleted here)
allows this library to be used in commercial applications.

--------

1.0     Description

This document describes subroutines that may be used in a manner similiar
to "Associative Arrays" as in Perl.  They use a very efficient hash
table algorithm for quick translation of C string Keys to strings or
general pointers.  Features:

    * Use external or internal storage for key string.
    * Use external or internal storage for key value.  In the case of
      internal storage, the value must be a string.  For external
      storage, the value may be any general pointer.
    * Dynamically increases/decreases size of hash table depending on
      ratio of entries / hash table size.
    * Uses 'CRC' algorithm for good distributions, even on similiar keys.

1.1     Files

aa.c            Associative array library routines
aa.h            Associative array public definitions
aaP.h           Associative array private definitions

2.0     Subroutines

2.1     aaContext *aaCreateContext(long flags)

        flags
            AA_CASEINSIG        Use case insignificant keys

Creates Associative Array context.

2.2     void aaDestroyContext(aaContext *aa)

        aa              Context to destroy.

Destroys Associative Array context, and all internally allocated keys
and values.  If a key or value was specified as external, nothing is
done to that key or value. Parameters:

2.3     int aaPut(aaContext *aa, char *key, void *value, long flags)

        aa              Associative array
        key             Key to store.
        value           Value, string or general pointer.
        flags
            AA_DUPKEY   Duplicate key using internal storage.
            AA_DUPVAL   Duplicate string value using internal storage.
            AA_EXTKEY   Store pointer to passed key, rather than duplicate
                        key internally.
            AA_EXTVAL   Store pointer to external value, rather than
                        duplicate internally.  May be general pointer in
                        this case (such as to a structure).
            AA_NOREP    Do not replace value if key already exists.

One of (AA_DUPKEY,AA_EXTKEY) and (AA_DUPVAL,AA_EXTVAL) must be given.

Store a key/value pair into an associative array.  Overwrites previous
value if key already exists, unless the AA_NOREP flag is given.
Key is case significant, unless AA was created with AA_CASEINSIG flag.
Returns -1 if error (No KEY or VAL flag specified, allocation error),
0 if key did not exist, and 1 if key already existed.  May be used
from within an aaScanBegin loop.

The intention of having no default for internal or external storage
is to cut down the risk of errors, even though it makes it a bit more
long-winded.  A default can obviously be added easily.

2.4     void *aaGet(aaContext *aa, char *key)

        aa              Associative array
        key             Key to search.

Retrieve value of key; returns NULL if key not found.

2.4     int aaDelete(aaContext *aa, char *key)

        aa              Associative array
        key             Key to delete.

Delete key from associative array.  Returns 0 if key existed, otherwise -1.
May be used within an aaScanBegin loop.

2.5     int aaScanBegin(aaContext *aa, char *key)

        aa              Associative array context.
        key             Optional starting key, or NULL.  Key must exist.

Scan keys in hash table (that is, random) order.  In practice, passing
in a start key is not that useful, but it could be used to restart a
scan for whatever reason.  aaScanEnd() should be used when the scan is
complete.  Note that during an active scan, the hash table will
not be reconfigured from adds or deletes in order to preserve a stable
hash order.  When the scan is completed by calling aaScanEnd, the hash
table's size is reconfigured (if necessary).

2.6     char *aaScanNext(aaContext *aa, void **value)

        aa              Associative array context.
        value           Optional value of key, or NULL.

After calling aaScanBegin, returns pointer to next key, or NULL.  Note
it is safe to use aaDelete and aaPut from within an aaScanBegin loop.

2.7     void aaScanEnd(aaContext *aa)

        aa              Associative array context.

Terminates a scan.  If any aaDelete's or aaPut's where done during a scan,
then the hash table is reconfigured at this time.

2.8     void aaDumpTable(aaContext *aa)

        aa              Associative array context.

Dumps out an associative array to stdout for debugging purposes.

3.0     Sample program

#include <stdio.h>
#include "aa.h"

int main(void)
{
    struct aaContext *aa;
    char *p;
    char key[20], value[20];
    char key2[20];
    int i;

    aa = aaCreateContext(0);

    /* Create some entries */

    for (i = 0; i < 100; ++i) {
        sprintf(key, "KEY%d", i);
        sprintf(value, "VALUE%d", i);
        aaPut(aa, key, value, AA_DUPKEY|AA_DUPVAL);
    }
    aaDumpTable(aa);

    /* Read back the entries */

    for (i = 0; i < 100; ++i) {
        sprintf(key2, "KEY%d", i);
        p = aaGet(aa, key2);
        printf("aaGet (%s): value = '%s'\n", key2, p);
    }

    /* Scan and delete 90% of the entries */

    aaScanBegin(aa, NULL);
    i = 0;
    while ((p = aaScanNext(aa, NULL)) != NULL) {
        if (i++ % 10 == 0)      /* Leave some left over */
            continue;
        printf("Deleting: %s\n", p);
        aaDelete(aa, p);
    }
    aaScanEnd(aa);

    /* Dump out the entries that are left */

    printf("After delete:\n");
    aaDumpTable(aa);

    aaDestroyContext(aa);
    return;

Write 100 times:
        hardwired strings in a program are a barrier to localisation.

It has always been true that hardwiring strings into a program was
a silly thing to do unless you had no alternative.  For the past 10
or 12 years it has been OBVIOUSLY silly.  By now, when Windows NT
uses Unicode inside, and UNIX systems come with support for multibyte
characters, and the X Window System has support for this stuff, it is
PAINFULLY obvious that hardwiring ASCII string literals into your
program is a good way to produce a product with no market outside
your own country.

: >Wouldn't It Be Nice if you could select from strings, though...

: Whenever I've needed to switch on a string there's usually just
: a small portion (sizeof long or less) of the string that's significant.
: A technique that I've used is to turn those bytes into something that I
: can switch on.  The OS that I use provides a MAKETYPE macro that, given
: the address of something, will cast that something into another specified
: type:
:    #define MAKETYPE(v, type)  (*((type *)&v))

: Then I just switch on MAKETYPE(myString, long) to turn into a long and
: use #defines for the cases so I'll have meaningful labels there.

: Note that this works for me.  It is definitely not portable, primarily
: because byte-swapping will significantly alter the result.

Seems to me like what you guys are trying to re-invent (seebs used
the term "prior art") are associative arrays, indexed on a string,
with an integer data type as data.  I.e., the *opposite* of an array of
char pointers.  To my knowledge, a good implementation for this
must be in the source code for Perl, because that language lives and
dies by the efficiency of its $value("some string") constructs.  I thinks
it's done by means of hash tables.

In article <5bdvof$...@solutions.solon.com>,

If you want to code your state machine yourself, more power to you.  I'd
use lex.

Although there is something to be said for hand-tuning them when your
set of input strings is small.  I can write a state machine for the
strings { "this", "that", "other" } without much difficulty at all, and
it'll likely be smaller and faster than lex.

Martin Sohnius x24031 (msohn...@novell.co.uk) wrote:

: *******************************************************************
: *        if (status = UNDER_NUCLEAR_ATTACK)                       *
: *               launch_full_counterstrike();                      *
: *******************************************************************

We can only hope for one of two things --

- that's not meant to be C, or:
- you've never done any contract work for NORAD.

Ok, I'll try to say something usefel here as well ... Actually I have no
time to think about this, just couldn't resist to pass on some partial
thoughts. Fasten seatbelts, here we go:

(Really, this is Q about algorithms rather than C, but who cares these
days anymore)

After trying it all I have come to the conclusion that sorting
alphbetically is a good idea.

(I tried sort by stringlength as well, but it won't buy you anything.
Hashing is off since there is a lot of more useful things you could have
done while racing through your teststring.)

----------------------------------------------------------------------
The way I understand the problem, the set of valid strings won't change
during runtime.

The set of strings to test might, on the other hand, be supplied by the
user (so there is always one more.)
----------------------------------------------------------------------

What did I say? Oh yes, the strings are _already_sorted_ alphabetically.
The proper way would then be to perform a bSearch for the first letter in
your test string

Assume you found it, Ok? Then test the second letter, and it was
(surprise) also valid.

But! In this example, as you go on, the third letter was not valid ...
 (Oh shit)

Since the strings are sorted, the value will either be too small, meaning
you still have a chance, or too big, meaning that there is no such
string ...

At this point it would be nice to have a bit of help, no? Simply testing
the next string at index 'n' will most probably send you into the void
space of undefined behaviour.

So we cheat and do some precalculations (on the valid strings)!

Lets have an array of int (or short, or char). One for each string in our
valid library.

The value of this int is equal to the number of chars that are unchanged
between "this string" and "the next string".

If that (next) value is less than our current index, then we have lost.
Else there is still a chance ... (repeat from top :)

Richard A. O'Keefe <o...@cs.rmit.edu.au> wrote in article
<5bmugt$...@solutions.solon.com>...

Several library routines to do different types of string look ups
and map to a integer that is switched on is more useful.
Sometimes exact matches and speed are important, in which case
binary searches of perfact hash look ups are what is needed.
Other times you really want to define a "pattern" (not necessarily
a GREP type pattern), that defines what should match.

 Sean> When faced with this, I typically define a structure with two
 Sean> members, a string (char *) and a function pointer, then I have
 Sean> an array (usually sorted alphabetically) of such structures.
 Sean> The parameters the function takes usually depends upon the
 Sean> application, but it gives me a nice blend between speed and
 Sean> flexibility.

Have you considered using a perfect hash function rather than searching
the array?

GNU gperf (a tool for generating perfect hash functions from arbitrary
strings) is part of the libg++ distribution (it can generate either C or
C++ code). All the GNU compilers use this method for handling keywords.

msohn...@novell.co.uk (Martin Sohnius x24031) wrote:

[snip]

     Assuming UNDER_NUCLEAR_ATTACK != 0, you've just launched a
nuclear strike on quite possibly friendly neighbours!

     If builders built buildings the programmers write programs, the
first woodpecker to come along would destroy civilization - unless
Martin F. Sohnius gets there first.

Gene Wirchenko

However, no solution (that I've ever thought of) puts real live string
literals on case labels, and failing that I wouldn't bother trying to
generalize a string switch.

Martin Sohnius x24031 <msohn...@novell.co.uk> wrote in article

    hash = symbol[0] + symbol[1] * 128 + symbol[symlen-1] * 128;

which is OK for most purposes, but beware if you have very similiar
strings.  Perl 5 is a little better, it uses

   char *s = key;
   int i = strlen(key);
   int hash = 0;
   while (i--)
      hash = hash * 33 + *s++;

: [snip]

: >*******************************************************************
: >Martin F. Sohnius                             msohn...@novell.co.uk
: >Novell IS & T, Bracknell, England             +44-1344-724031
: >*******************************************************************
: >*        if (status = UNDER_NUCLEAR_ATTACK)                       *
:                      ^
:      Hey, warmonger!  That's supposed to be ==!

:      Assuming UNDER_NUCLEAR_ATTACK != 0, you've just launched a
: nuclear strike on quite possibly friendly neighbours!

:      If builders built buildings the programmers write programs, the
: first woodpecker to come along would destroy civilization - unless
: Martin F. Sohnius gets there first.

: >*               launch_full_counterstrike();                      *

:      Temper, temper!

WhoA!  I never thought I'd get this response from posting my little
.sig to c.l.c.moderated (where's the moderator?)

[Easily amused. -mod]

Look, guys, don't EVER judge from a code snippet if you haven't seen
the whole thing!

What I didn't tell you is this:

#ifdef PACIFIST

        enum {UNDER_NUCLEAR_ATTACK, ALL_CLEAR};

#else   /* Armageddon */

        enum {ALL_CLEAR, UNDER_NUCLEAR_ATTACK};
#endif

And, yes, I didn't share the belief that SDI was a good idea!  :-)

In article <5c0tb4$...@solutions.solon.com> "Tim Behrendsen"

   unsigned char *s = key;
   int i = strlen(key);
   unsigned hash = 0;
   while (i--)
      hash = hash * 33U + *s++;

Also, Aho, Sethi and Ulman in "Compilers: Principles, Techniques, and
Tools" imply that it would be beneficial to replace 33 by a prime
number close to 2^(CHAR_BIT * sizeof(hash)) to encourage the
randomizing bit-truncation that occurs with unsigned overflows. They
suggest 65599 for 16 bit ints. Can anyone suggest a prime that is less
than but close to 2^32?

Martin Shepherd <m...@goblin.caltech.edu> wrote in article
<5c80ko$...@solutions.solon.com>...
[snip]

I also hope that the declaration: "int hash" is a miscopy.  I really
can't believe that you want signed arithmetic here.  (Remember that
overflow in signed arithmetic is not defined.  Using signed arithmetic
in such cases is an error waiting to happen.)