From 92cfc83903884f5e532294858d41aa54340d5db3 Mon Sep 17 00:00:00 2001 From: CSRG Date: Sun, 1 Oct 1989 16:07:30 -0800 Subject: [PATCH] BSD 4_3_Net_2 development Work on file usr/src/lib/libg++/grot/etc/ADT-examples/keyhash.cc Synthesized-from: CSRG/cd2/net.2 --- .../libg++/grot/etc/ADT-examples/keyhash.cc | 158 ++++++++++++++++++ 1 file changed, 158 insertions(+) create mode 100644 usr/src/lib/libg++/grot/etc/ADT-examples/keyhash.cc diff --git a/usr/src/lib/libg++/grot/etc/ADT-examples/keyhash.cc b/usr/src/lib/libg++/grot/etc/ADT-examples/keyhash.cc new file mode 100644 index 0000000000..7da898deab --- /dev/null +++ b/usr/src/lib/libg++/grot/etc/ADT-examples/keyhash.cc @@ -0,0 +1,158 @@ +// Date: Tue, 20 Sep 88 01:03:21 -0700 +// From: "Douglas C. Schmidt" +// +// +// The following is an Obstack-based program, which outputs all the GCC +// reserved words in an input file redirected from cin +// In addition, I found a neat use for +// derived types by defining a word-by-word input class that is based +// upon the class Obstack. Finally, there is the added bonus of seeing +// how the O (1) time GCC perfect hash function recognizer from GCC 1.35 +// works; I've incorporated the relevant code in this short routine. +// Feel free to fold, spindle, or mutilate this code. +// + +#include +#include +#include + +#define NIL(TYPE) ((TYPE *)0) + +class Word_Read : private Obstack +{ +public: + Obstack::free; // Allow the derived type to inherit only this member function. + + // Make the default something reasonable, like 80 columns. + Word_Read (int Default_Len = 80): (Default_Len) + { + ; + } + + // A very rudimentary method for carving out the next word + // from the input. Ignores most error conditions. All non- + // words are skipped entirely. A word is defined as a + // letter, followed by a sequence of letters, digits, and/or + // underbars `_'. + + char *operator ()(int& Len = 0) + { + char c; + + while (cin.get (c) && !(isalpha (c) || c == '_')) + ; + + do + Obstack::grow (c); + while (cin.get (c) && (isalnum (c) || c == '_')); + + Len = Obstack::size (); + return cin.good () ? Obstack::finish (0) : 0; + } + + // Make the destructor print out something useful, like + // output a diagnostic. + + ~Word_Read () + { + cout << "chunk_size = " << Obstack::chunk_size () << "\n"; + cout << "size = " << Obstack::size () << "\n"; + cout << "room = " << Obstack::room () << "\n"; + } +}; + +// Provides a nice example of the perfect hash function used to recognize +// GCC reserved words in O(1) steps. + +class Lookup_Table +{ +private: + const int MIN_WORD_SIZE = 2; + const int MAX_WORD_SIZE = 12; + const int MIN_KEY_SIZE = 4; + const int MAX_KEY_SIZE = 64; + + static int Hash_Table[] = + { + 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, + 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, + 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, + 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, + 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, + 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, + 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, + 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, + 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, + 64, 64, 64, 64, 64, 1, 64, 9, 17, 15, + 28, 19, 29, 15, 64, 2, 64, 64, 25, 4, + 16, 22, 40, 64, 11, 23, 1, 1, 16, 2, + 64, 64, 8, 64, 64, 64, 64, 64, + }; + + static char *Reswords[] = + { + "", "", "", "", "if", "", "int", "", "union", "while", "__typeof", + "__inline", "__typeof__", "__inline__", "auto", "__asm", "asm", "__asm__", + "return", "__alignof", "goto", "__alignof__", "void", "__const", + "enum", "__const__", "extern", "__volatile", "char", "__volatile__", + "do", "switch", "unsigned", "inline", "register", "double", "const", + "sizeof", "static", "continue", "struct", "break", "case", "for", + "signed", "long", "else", "typeof", "typedef", "volatile", "short", + "", "", "", "", "", "float", "", "", "", "", "", "", "", "default", + }; + + // And here it is.... Very simple, guaranteed to work! + + int Hash (char *Str,int Len) + { + switch (Len) + { + default: + case 3: + Len += Hash_Table[Str[2]]; + case 2: + case 1: + return Len + Hash_Table[Str[0]]; + } + } + +public: + + // Carries out the O (1) lookup for GCC reserved words! + int operator () (char *Str,int Len) + { + if (Len <= MAX_WORD_SIZE && Len >= MIN_WORD_SIZE) + { + register int Key = Hash (Str,Len); + + if (Key >= MIN_KEY_SIZE && Key <= MAX_KEY_SIZE) + if (*Reswords[Key] == *Str && !strcmp (Reswords[Key] + 1,Str + 1)) + return 1; + } + return 0; + } +}; + +static void Store_Buf (char *Buf) +{ + cout << "Storing reserved word " << Buf << "\n"; + // Just kidding! But you get the idea.... +} + +main (int argc, char *argv[]) +{ + Word_Read Get_Next_Word; + Lookup_Table Is_Reserved_Word; + char *Buf; + int Len; + + while (Buf = Get_Next_Word (Len)) + if (Is_Reserved_Word (Buf,Len)) + Store_Buf (Buf); // Keep reserved words + else + Get_Next_Word.free (Buf); // Discard non-reserved words + + return 0; +} + + -- 2.20.1