src/third_party/sqlite/src/tool/mkkeywordhash.c

   1 /*
   2 ** Compile and run this standalone program in order to generate code that
   3 ** implements a function that will translate alphabetic identifiers into
   4 ** parser token codes.
   5 */
   6 #include <stdio.h>
   7 #include <string.h>
   8 #include <stdlib.h>
   9 #include <assert.h>
  10
  11 /*
  12 ** A header comment placed at the beginning of generated code.
  13 */
  14 static const char zHdr[] =
  15   "/***** This file contains automatically generated code ******\n"
  16   "**\n"
  17   "** The code in this file has been automatically generated by\n"
  18   "**\n"
  19   "**   sqlite/tool/mkkeywordhash.c\n"
  20   "**\n"
  21   "** The code in this file implements a function that determines whether\n"
  22   "** or not a given identifier is really an SQL keyword.  The same thing\n"
  23   "** might be implemented more directly using a hand-written hash table.\n"
  24   "** But by using this automatically generated code, the size of the code\n"
  25   "** is substantially reduced.  This is important for embedded applications\n"
  26   "** on platforms with limited memory.\n"
  27   "*/\n"
  28 ;
  29
  30 /*
  31 ** All the keywords of the SQL language are stored in a hash
  32 ** table composed of instances of the following structure.
  33 */
  34 typedef struct Keyword Keyword;
  35 struct Keyword {
  36   char *zName;         /* The keyword name */
  37   char *zTokenType;    /* Token value for this keyword */
  38   int mask;            /* Code this keyword if non-zero */
  39   int id;              /* Unique ID for this record */
  40   int hash;            /* Hash on the keyword */
  41   int offset;          /* Offset to start of name string */
  42   int len;             /* Length of this keyword, not counting final \000 */
  43   int prefix;          /* Number of characters in prefix */
  44   int longestSuffix;   /* Longest suffix that is a prefix on another word */
  45   int iNext;           /* Index in aKeywordTable[] of next with same hash */
  46   int substrId;        /* Id to another keyword this keyword is embedded in */
  47   int substrOffset;    /* Offset into substrId for start of this keyword */
  48   char zOrigName[20];  /* Original keyword name before processing */
  49 };
  50
  51 /*
  52 ** Define masks used to determine which keywords are allowed
  53 */
  54 #ifdef SQLITE_OMIT_ALTERTABLE
  55 #  define ALTER      0
  56 #else
  57 #  define ALTER      0x00000001
  58 #endif
  59 #define ALWAYS       0x00000002
  60 #ifdef SQLITE_OMIT_ANALYZE
  61 #  define ANALYZE    0
  62 #else
  63 #  define ANALYZE    0x00000004
  64 #endif
  65 #ifdef SQLITE_OMIT_ATTACH
  66 #  define ATTACH     0
  67 #else
  68 #  define ATTACH     0x00000008
  69 #endif
  70 #ifdef SQLITE_OMIT_AUTOINCREMENT
  71 #  define AUTOINCR   0
  72 #else
  73 #  define AUTOINCR   0x00000010
  74 #endif
  75 #ifdef SQLITE_OMIT_CAST
  76 #  define CAST       0
  77 #else
  78 #  define CAST       0x00000020
  79 #endif
  80 #ifdef SQLITE_OMIT_COMPOUND_SELECT
  81 #  define COMPOUND   0
  82 #else
  83 #  define COMPOUND   0x00000040
  84 #endif
  85 #ifdef SQLITE_OMIT_CONFLICT_CLAUSE
  86 #  define CONFLICT   0
  87 #else
  88 #  define CONFLICT   0x00000080
  89 #endif
  90 #ifdef SQLITE_OMIT_EXPLAIN
  91 #  define EXPLAIN    0
  92 #else
  93 #  define EXPLAIN    0x00000100
  94 #endif
  95 #ifdef SQLITE_OMIT_FOREIGN_KEY
  96 #  define FKEY       0
  97 #else
  98 #  define FKEY       0x00000200
  99 #endif
 100 #ifdef SQLITE_OMIT_PRAGMA
 101 #  define PRAGMA     0
 102 #else
 103 #  define PRAGMA     0x00000400
 104 #endif
 105 #ifdef SQLITE_OMIT_REINDEX
 106 #  define REINDEX    0
 107 #else
 108 #  define REINDEX    0x00000800
 109 #endif
 110 #ifdef SQLITE_OMIT_SUBQUERY
 111 #  define SUBQUERY   0
 112 #else
 113 #  define SUBQUERY   0x00001000
 114 #endif
 115 #ifdef SQLITE_OMIT_TRIGGER
 116 #  define TRIGGER    0
 117 #else
 118 #  define TRIGGER    0x00002000
 119 #endif
 120 #if defined(SQLITE_OMIT_AUTOVACUUM) && \
 121     (defined(SQLITE_OMIT_VACUUM) || defined(SQLITE_OMIT_ATTACH))
 122 #  define VACUUM     0
 123 #else
 124 #  define VACUUM     0x00004000
 125 #endif
 126 #ifdef SQLITE_OMIT_VIEW
 127 #  define VIEW       0
 128 #else
 129 #  define VIEW       0x00008000
 130 #endif
 131 #ifdef SQLITE_OMIT_VIRTUALTABLE
 132 #  define VTAB       0
 133 #else
 134 #  define VTAB       0x00010000
 135 #endif
 136 #ifdef SQLITE_OMIT_AUTOVACUUM
 137 #  define AUTOVACUUM 0
 138 #else
 139 #  define AUTOVACUUM 0x00020000
 140 #endif
 141
 142 /*
 143 ** These are the keywords
 144 */
 145 static Keyword aKeywordTable[] = {
 146   { "ABORT",            "TK_ABORT",        CONFLICT|TRIGGER       },
 147   { "ACTION",           "TK_ACTION",       FKEY                   },
 148   { "ADD",              "TK_ADD",          ALTER                  },
 149   { "AFTER",            "TK_AFTER",        TRIGGER                },
 150   { "ALL",              "TK_ALL",          ALWAYS                 },
 151   { "ALTER",            "TK_ALTER",        ALTER                  },
 152   { "ANALYZE",          "TK_ANALYZE",      ANALYZE                },
 153   { "AND",              "TK_AND",          ALWAYS                 },
 154   { "AS",               "TK_AS",           ALWAYS                 },
 155   { "ASC",              "TK_ASC",          ALWAYS                 },
 156   { "ATTACH",           "TK_ATTACH",       ATTACH                 },
 157   { "AUTOINCREMENT",    "TK_AUTOINCR",     AUTOINCR               },
 158   { "BEFORE",           "TK_BEFORE",       TRIGGER                },
 159   { "BEGIN",            "TK_BEGIN",        ALWAYS                 },
 160   { "BETWEEN",          "TK_BETWEEN",      ALWAYS                 },
 161   { "BY",               "TK_BY",           ALWAYS                 },
 162   { "CASCADE",          "TK_CASCADE",      FKEY                   },
 163   { "CASE",             "TK_CASE",         ALWAYS                 },
 164   { "CAST",             "TK_CAST",         CAST                   },
 165   { "CHECK",            "TK_CHECK",        ALWAYS                 },
 166   { "COLLATE",          "TK_COLLATE",      ALWAYS                 },
 167   { "COLUMN",           "TK_COLUMNKW",     ALTER                  },
 168   { "COMMIT",           "TK_COMMIT",       ALWAYS                 },
 169   { "CONFLICT",         "TK_CONFLICT",     CONFLICT               },
 170   { "CONSTRAINT",       "TK_CONSTRAINT",   ALWAYS                 },
 171   { "CREATE",           "TK_CREATE",       ALWAYS                 },
 172   { "CROSS",            "TK_JOIN_KW",      ALWAYS                 },
 173   { "CURRENT_DATE",     "TK_CTIME_KW",     ALWAYS                 },
 174   { "CURRENT_TIME",     "TK_CTIME_KW",     ALWAYS                 },
 175   { "CURRENT_TIMESTAMP","TK_CTIME_KW",     ALWAYS                 },
 176   { "DATABASE",         "TK_DATABASE",     ATTACH                 },
 177   { "DEFAULT",          "TK_DEFAULT",      ALWAYS                 },
 178   { "DEFERRED",         "TK_DEFERRED",     ALWAYS                 },
 179   { "DEFERRABLE",       "TK_DEFERRABLE",   FKEY                   },
 180   { "DELETE",           "TK_DELETE",       ALWAYS                 },
 181   { "DESC",             "TK_DESC",         ALWAYS                 },
 182   { "DETACH",           "TK_DETACH",       ATTACH                 },
 183   { "DISTINCT",         "TK_DISTINCT",     ALWAYS                 },
 184   { "DROP",             "TK_DROP",         ALWAYS                 },
 185   { "END",              "TK_END",          ALWAYS                 },
 186   { "EACH",             "TK_EACH",         TRIGGER                },
 187   { "ELSE",             "TK_ELSE",         ALWAYS                 },
 188   { "ESCAPE",           "TK_ESCAPE",       ALWAYS                 },
 189   { "EXCEPT",           "TK_EXCEPT",       COMPOUND               },
 190   { "EXCLUSIVE",        "TK_EXCLUSIVE",    ALWAYS                 },
 191   { "EXISTS",           "TK_EXISTS",       ALWAYS                 },
 192   { "EXPLAIN",          "TK_EXPLAIN",      EXPLAIN                },
 193   { "FAIL",             "TK_FAIL",         CONFLICT|TRIGGER       },
 194   { "FOR",              "TK_FOR",          TRIGGER                },
 195   { "FOREIGN",          "TK_FOREIGN",      FKEY                   },
 196   { "FROM",             "TK_FROM",         ALWAYS                 },
 197   { "FULL",             "TK_JOIN_KW",      ALWAYS                 },
 198   { "GLOB",             "TK_LIKE_KW",      ALWAYS                 },
 199   { "GROUP",            "TK_GROUP",        ALWAYS                 },
 200   { "HAVING",           "TK_HAVING",       ALWAYS                 },
 201   { "IF",               "TK_IF",           ALWAYS                 },
 202   { "IGNORE",           "TK_IGNORE",       CONFLICT|TRIGGER       },
 203   { "IMMEDIATE",        "TK_IMMEDIATE",    ALWAYS                 },
 204   { "IN",               "TK_IN",           ALWAYS                 },
 205   { "INDEX",            "TK_INDEX",        ALWAYS                 },
 206   { "INDEXED",          "TK_INDEXED",      ALWAYS                 },
 207   { "INITIALLY",        "TK_INITIALLY",    FKEY                   },
 208   { "INNER",            "TK_JOIN_KW",      ALWAYS                 },
 209   { "INSERT",           "TK_INSERT",       ALWAYS                 },
 210   { "INSTEAD",          "TK_INSTEAD",      TRIGGER                },
 211   { "INTERSECT",        "TK_INTERSECT",    COMPOUND               },
 212   { "INTO",             "TK_INTO",         ALWAYS                 },
 213   { "IS",               "TK_IS",           ALWAYS                 },
 214   { "ISNULL",           "TK_ISNULL",       ALWAYS                 },
 215   { "JOIN",             "TK_JOIN",         ALWAYS                 },
 216   { "KEY",              "TK_KEY",          ALWAYS                 },
 217   { "LEFT",             "TK_JOIN_KW",      ALWAYS                 },
 218   { "LIKE",             "TK_LIKE_KW",      ALWAYS                 },
 219   { "LIMIT",            "TK_LIMIT",        ALWAYS                 },
 220   { "MATCH",            "TK_MATCH",        ALWAYS                 },
 221   { "NATURAL",          "TK_JOIN_KW",      ALWAYS                 },
 222   { "NO",               "TK_NO",           FKEY                   },
 223   { "NOT",              "TK_NOT",          ALWAYS                 },
 224   { "NOTNULL",          "TK_NOTNULL",      ALWAYS                 },
 225   { "NULL",             "TK_NULL",         ALWAYS                 },
 226   { "OF",               "TK_OF",           ALWAYS                 },
 227   { "OFFSET",           "TK_OFFSET",       ALWAYS                 },
 228   { "ON",               "TK_ON",           ALWAYS                 },
 229   { "OR",               "TK_OR",           ALWAYS                 },
 230   { "ORDER",            "TK_ORDER",        ALWAYS                 },
 231   { "OUTER",            "TK_JOIN_KW",      ALWAYS                 },
 232   { "PLAN",             "TK_PLAN",         EXPLAIN                },
 233   { "PRAGMA",           "TK_PRAGMA",       PRAGMA                 },
 234   { "PRIMARY",          "TK_PRIMARY",      ALWAYS                 },
 235   { "QUERY",            "TK_QUERY",        EXPLAIN                },
 236   { "RAISE",            "TK_RAISE",        TRIGGER                },
 237   { "REFERENCES",       "TK_REFERENCES",   FKEY                   },
 238   { "REGEXP",           "TK_LIKE_KW",      ALWAYS                 },
 239   { "REINDEX",          "TK_REINDEX",      REINDEX                },
 240   { "RELEASE",          "TK_RELEASE",      ALWAYS                 },
 241   { "RENAME",           "TK_RENAME",       ALTER                  },
 242   { "REPLACE",          "TK_REPLACE",      CONFLICT               },
 243   { "RESTRICT",         "TK_RESTRICT",     FKEY                   },
 244   { "RIGHT",            "TK_JOIN_KW",      ALWAYS                 },
 245   { "ROLLBACK",         "TK_ROLLBACK",     ALWAYS                 },
 246   { "ROW",              "TK_ROW",          TRIGGER                },
 247   { "SAVEPOINT",        "TK_SAVEPOINT",    ALWAYS                 },
 248   { "SELECT",           "TK_SELECT",       ALWAYS                 },
 249   { "SET",              "TK_SET",          ALWAYS                 },
 250   { "TABLE",            "TK_TABLE",        ALWAYS                 },
 251   { "TEMP",             "TK_TEMP",         ALWAYS                 },
 252   { "TEMPORARY",        "TK_TEMP",         ALWAYS                 },
 253   { "THEN",             "TK_THEN",         ALWAYS                 },
 254   { "TO",               "TK_TO",           ALWAYS                 },
 255   { "TRANSACTION",      "TK_TRANSACTION",  ALWAYS                 },
 256   { "TRIGGER",          "TK_TRIGGER",      TRIGGER                },
 257   { "UNION",            "TK_UNION",        COMPOUND               },
 258   { "UNIQUE",           "TK_UNIQUE",       ALWAYS                 },
 259   { "UPDATE",           "TK_UPDATE",       ALWAYS                 },
 260   { "USING",            "TK_USING",        ALWAYS                 },
 261   { "VACUUM",           "TK_VACUUM",       VACUUM                 },
 262   { "VALUES",           "TK_VALUES",       ALWAYS                 },
 263   { "VIEW",             "TK_VIEW",         VIEW                   },
 264   { "VIRTUAL",          "TK_VIRTUAL",      VTAB                   },
 265   { "WHEN",             "TK_WHEN",         ALWAYS                 },
 266   { "WHERE",            "TK_WHERE",        ALWAYS                 },
 267 };
 268
 269 /* Number of keywords */
 270 static int nKeyword = (sizeof(aKeywordTable)/sizeof(aKeywordTable[0]));
 271
 272 /* An array to map all upper-case characters into their corresponding
 273 ** lower-case character.
 274 */
 275 const unsigned char sqlite3UpperToLower[] = {
 276       0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17,
 277      18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35,
 278      36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53,
 279      54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 97, 98, 99,100,101,102,103,
 280     104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,
 281     122, 91, 92, 93, 94, 95, 96, 97, 98, 99,100,101,102,103,104,105,106,107,
 282     108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,
 283     126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,
 284     144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,
 285     162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,
 286     180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,
 287     198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,
 288     216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,
 289     234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,
 290     252,253,254,255
 291 };
 292 #define UpperToLower sqlite3UpperToLower
 293
 294 /*
 295 ** Comparision function for two Keyword records
 296 */
 297 static int keywordCompare1(const void *a, const void *b){
 298   const Keyword *pA = (Keyword*)a;
 299   const Keyword *pB = (Keyword*)b;
 300   int n = pA->len - pB->len;
 301   if( n==0 ){
 302     n = strcmp(pA->zName, pB->zName);
 303   }
 304   assert( n!=0 );
 305   return n;
 306 }
 307 static int keywordCompare2(const void *a, const void *b){
 308   const Keyword *pA = (Keyword*)a;
 309   const Keyword *pB = (Keyword*)b;
 310   int n = pB->longestSuffix - pA->longestSuffix;
 311   if( n==0 ){
 312     n = strcmp(pA->zName, pB->zName);
 313   }
 314   assert( n!=0 );
 315   return n;
 316 }
 317 static int keywordCompare3(const void *a, const void *b){
 318   const Keyword *pA = (Keyword*)a;
 319   const Keyword *pB = (Keyword*)b;
 320   int n = pA->offset - pB->offset;
 321   if( n==0 ) n = pB->id - pA->id;
 322   assert( n!=0 );
 323   return n;
 324 }
 325
 326 /*
 327 ** Return a KeywordTable entry with the given id
 328 */
 329 static Keyword *findById(int id){
 330   int i;
 331   for(i=0; i<nKeyword; i++){
 332     if( aKeywordTable[i].id==id ) break;
 333   }
 334   return &aKeywordTable[i];
 335 }
 336
 337 /*
 338 ** This routine does the work.  The generated code is printed on standard
 339 ** output.
 340 */
 341 int main(int argc, char **argv){
 342   int i, j, k, h;
 343   int bestSize, bestCount;
 344   int count;
 345   int nChar;
 346   int totalLen = 0;
 347   int aHash[1000];  /* 1000 is much bigger than nKeyword */
 348   char zText[2000];
 349
 350   /* Remove entries from the list of keywords that have mask==0 */
 351   for(i=j=0; i<nKeyword; i++){
 352     if( aKeywordTable[i].mask==0 ) continue;
 353     if( j<i ){
 354       aKeywordTable[j] = aKeywordTable[i];
 355     }
 356     j++;
 357   }
 358   nKeyword = j;
 359
 360   /* Fill in the lengths of strings and hashes for all entries. */
 361   for(i=0; i<nKeyword; i++){
 362     Keyword *p = &aKeywordTable[i];
 363     p->len = strlen(p->zName);
 364     assert( p->len<sizeof(p->zOrigName) );
 365     strcpy(p->zOrigName, p->zName);
 366     totalLen += p->len;
 367     p->hash = (UpperToLower[(int)p->zName[0]]*4) ^
 368               (UpperToLower[(int)p->zName[p->len-1]]*3) ^ p->len;
 369     p->id = i+1;
 370   }
 371
 372   /* Sort the table from shortest to longest keyword */
 373   qsort(aKeywordTable, nKeyword, sizeof(aKeywordTable[0]), keywordCompare1);
 374
 375   /* Look for short keywords embedded in longer keywords */
 376   for(i=nKeyword-2; i>=0; i--){
 377     Keyword *p = &aKeywordTable[i];
 378     for(j=nKeyword-1; j>i && p->substrId==0; j--){
 379       Keyword *pOther = &aKeywordTable[j];
 380       if( pOther->substrId ) continue;
 381       if( pOther->len<=p->len ) continue;
 382       for(k=0; k<=pOther->len-p->len; k++){
 383         if( memcmp(p->zName, &pOther->zName[k], p->len)==0 ){
 384           p->substrId = pOther->id;
 385           p->substrOffset = k;
 386           break;
 387         }
 388       }
 389     }
 390   }
 391
 392   /* Compute the longestSuffix value for every word */
 393   for(i=0; i<nKeyword; i++){
 394     Keyword *p = &aKeywordTable[i];
 395     if( p->substrId ) continue;
 396     for(j=0; j<nKeyword; j++){
 397       Keyword *pOther;
 398       if( j==i ) continue;
 399       pOther = &aKeywordTable[j];
 400       if( pOther->substrId ) continue;
 401       for(k=p->longestSuffix+1; k<p->len && k<pOther->len; k++){
 402         if( memcmp(&p->zName[p->len-k], pOther->zName, k)==0 ){
 403           p->longestSuffix = k;
 404         }
 405       }
 406     }
 407   }
 408
 409   /* Sort the table into reverse order by length */
 410   qsort(aKeywordTable, nKeyword, sizeof(aKeywordTable[0]), keywordCompare2);
 411
 412   /* Fill in the offset for all entries */
 413   nChar = 0;
 414   for(i=0; i<nKeyword; i++){
 415     Keyword *p = &aKeywordTable[i];
 416     if( p->offset>0 || p->substrId ) continue;
 417     p->offset = nChar;
 418     nChar += p->len;
 419     for(k=p->len-1; k>=1; k--){
 420       for(j=i+1; j<nKeyword; j++){
 421         Keyword *pOther = &aKeywordTable[j];
 422         if( pOther->offset>0 || pOther->substrId ) continue;
 423         if( pOther->len<=k ) continue;
 424         if( memcmp(&p->zName[p->len-k], pOther->zName, k)==0 ){
 425           p = pOther;
 426           p->offset = nChar - k;
 427           nChar = p->offset + p->len;
 428           p->zName += k;
 429           p->len -= k;
 430           p->prefix = k;
 431           j = i;
 432           k = p->len;
 433         }
 434       }
 435     }
 436   }
 437   for(i=0; i<nKeyword; i++){
 438     Keyword *p = &aKeywordTable[i];
 439     if( p->substrId ){
 440       p->offset = findById(p->substrId)->offset + p->substrOffset;
 441     }
 442   }
 443
 444   /* Sort the table by offset */
 445   qsort(aKeywordTable, nKeyword, sizeof(aKeywordTable[0]), keywordCompare3);
 446
 447   /* Figure out how big to make the hash table in order to minimize the
 448   ** number of collisions */
 449   bestSize = nKeyword;
 450   bestCount = nKeyword*nKeyword;
 451   for(i=nKeyword/2; i<=2*nKeyword; i++){
 452     for(j=0; j<i; j++) aHash[j] = 0;
 453     for(j=0; j<nKeyword; j++){
 454       h = aKeywordTable[j].hash % i;
 455       aHash[h] *= 2;
 456       aHash[h]++;
 457     }
 458     for(j=count=0; j<i; j++) count += aHash[j];
 459     if( count<bestCount ){
 460       bestCount = count;
 461       bestSize = i;
 462     }
 463   }
 464
 465   /* Compute the hash */
 466   for(i=0; i<bestSize; i++) aHash[i] = 0;
 467   for(i=0; i<nKeyword; i++){
 468     h = aKeywordTable[i].hash % bestSize;
 469     aKeywordTable[i].iNext = aHash[h];
 470     aHash[h] = i+1;
 471   }
 472
 473   /* Begin generating code */
 474   printf("%s", zHdr);
 475   printf("/* Hash score: %d */\n", bestCount);
 476   printf("static int keywordCode(const char *z, int n){\n");
 477   printf("  /* zText[] encodes %d bytes of keywords in %d bytes */\n",
 478           totalLen + nKeyword, nChar+1 );
 479   for(i=j=k=0; i<nKeyword; i++){
 480     Keyword *p = &aKeywordTable[i];
 481     if( p->substrId ) continue;
 482     memcpy(&zText[k], p->zName, p->len);
 483     k += p->len;
 484     if( j+p->len>70 ){
 485       printf("%*s */\n", 74-j, "");
 486       j = 0;
 487     }
 488     if( j==0 ){
 489       printf("  /*   ");
 490       j = 8;
 491     }
 492     printf("%s", p->zName);
 493     j += p->len;
 494   }
 495   if( j>0 ){
 496     printf("%*s */\n", 74-j, "");
 497   }
 498   printf("  static const char zText[%d] = {\n", nChar);
 499   zText[nChar] = 0;
 500   for(i=j=0; i<k; i++){
 501     if( j==0 ){
 502       printf("    ");
 503     }
 504     if( zText[i]==0 ){
 505       printf("0");
 506     }else{
 507       printf("'%c',", zText[i]);
 508     }
 509     j += 4;
 510     if( j>68 ){
 511       printf("\n");
 512       j = 0;
 513     }
 514   }
 515   if( j>0 ) printf("\n");
 516   printf("  };\n");
 517
 518   printf("  static const unsigned char aHash[%d] = {\n", bestSize);
 519   for(i=j=0; i<bestSize; i++){
 520     if( j==0 ) printf("    ");
 521     printf(" %3d,", aHash[i]);
 522     j++;
 523     if( j>12 ){
 524       printf("\n");
 525       j = 0;
 526     }
 527   }
 528   printf("%s  };\n", j==0 ? "" : "\n");
 529
 530   printf("  static const unsigned char aNext[%d] = {\n", nKeyword);
 531   for(i=j=0; i<nKeyword; i++){
 532     if( j==0 ) printf("    ");
 533     printf(" %3d,", aKeywordTable[i].iNext);
 534     j++;
 535     if( j>12 ){
 536       printf("\n");
 537       j = 0;
 538     }
 539   }
 540   printf("%s  };\n", j==0 ? "" : "\n");
 541
 542   printf("  static const unsigned char aLen[%d] = {\n", nKeyword);
 543   for(i=j=0; i<nKeyword; i++){
 544     if( j==0 ) printf("    ");
 545     printf(" %3d,", aKeywordTable[i].len+aKeywordTable[i].prefix);
 546     j++;
 547     if( j>12 ){
 548       printf("\n");
 549       j = 0;
 550     }
 551   }
 552   printf("%s  };\n", j==0 ? "" : "\n");
 553
 554   printf("  static const unsigned short int aOffset[%d] = {\n", nKeyword);
 555   for(i=j=0; i<nKeyword; i++){
 556     if( j==0 ) printf("    ");
 557     printf(" %3d,", aKeywordTable[i].offset);
 558     j++;
 559     if( j>12 ){
 560       printf("\n");
 561       j = 0;
 562     }
 563   }
 564   printf("%s  };\n", j==0 ? "" : "\n");
 565
 566   printf("  static const unsigned char aCode[%d] = {\n", nKeyword);
 567   for(i=j=0; i<nKeyword; i++){
 568     char *zToken = aKeywordTable[i].zTokenType;
 569     if( j==0 ) printf("    ");
 570     printf("%s,%*s", zToken, (int)(14-strlen(zToken)), "");
 571     j++;
 572     if( j>=5 ){
 573       printf("\n");
 574       j = 0;
 575     }
 576   }
 577   printf("%s  };\n", j==0 ? "" : "\n");
 578
 579   printf("  int h, i;\n");
 580   printf("  if( n<2 ) return TK_ID;\n");
 581   printf("  h = ((charMap(z[0])*4) ^\n"
 582          "      (charMap(z[n-1])*3) ^\n"
 583          "      n) %% %d;\n", bestSize);
 584   printf("  for(i=((int)aHash[h])-1; i>=0; i=((int)aNext[i])-1){\n");
 585   printf("    if( aLen[i]==n &&"
 586                    " sqlite3StrNICmp(&zText[aOffset[i]],z,n)==0 ){\n");
 587   for(i=0; i<nKeyword; i++){
 588     printf("      testcase( i==%d ); /* %s */\n",
 589            i, aKeywordTable[i].zOrigName);
 590   }
 591   printf("      return aCode[i];\n");
 592   printf("    }\n");
 593   printf("  }\n");
 594   printf("  return TK_ID;\n");
 595   printf("}\n");
 596   printf("int sqlite3KeywordCode(const unsigned char *z, int n){\n");
 597   printf("  return keywordCode((char*)z, n);\n");
 598   printf("}\n");
 599   printf("#define SQLITE_N_KEYWORD %d\n", nKeyword);
 600
 601   return 0;
 602 }