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 #ifdef SQLITE_OMIT_CTE
 142 #  define CTE        0
 143 #else
 144 #  define CTE        0x00040000
 145 #endif
 146 #ifdef SQLITE_OMIT_UPSERT
 147 #  define UPSERT     0
 148 #else
 149 #  define UPSERT     0x00080000
 150 #endif
 151
 152 /*
 153 ** These are the keywords
 154 */
 155 static Keyword aKeywordTable[] = {
 156   { "ABORT",            "TK_ABORT",        CONFLICT|TRIGGER       },
 157   { "ACTION",           "TK_ACTION",       FKEY                   },
 158   { "ADD",              "TK_ADD",          ALTER                  },
 159   { "AFTER",            "TK_AFTER",        TRIGGER                },
 160   { "ALL",              "TK_ALL",          ALWAYS                 },
 161   { "ALTER",            "TK_ALTER",        ALTER                  },
 162   { "ANALYZE",          "TK_ANALYZE",      ANALYZE                },
 163   { "AND",              "TK_AND",          ALWAYS                 },
 164   { "AS",               "TK_AS",           ALWAYS                 },
 165   { "ASC",              "TK_ASC",          ALWAYS                 },
 166   { "ATTACH",           "TK_ATTACH",       ATTACH                 },
 167   { "AUTOINCREMENT",    "TK_AUTOINCR",     AUTOINCR               },
 168   { "BEFORE",           "TK_BEFORE",       TRIGGER                },
 169   { "BEGIN",            "TK_BEGIN",        ALWAYS                 },
 170   { "BETWEEN",          "TK_BETWEEN",      ALWAYS                 },
 171   { "BY",               "TK_BY",           ALWAYS                 },
 172   { "CASCADE",          "TK_CASCADE",      FKEY                   },
 173   { "CASE",             "TK_CASE",         ALWAYS                 },
 174   { "CAST",             "TK_CAST",         CAST                   },
 175   { "CHECK",            "TK_CHECK",        ALWAYS                 },
 176   { "COLLATE",          "TK_COLLATE",      ALWAYS                 },
 177   { "COLUMN",           "TK_COLUMNKW",     ALTER                  },
 178   { "COMMIT",           "TK_COMMIT",       ALWAYS                 },
 179   { "CONFLICT",         "TK_CONFLICT",     CONFLICT               },
 180   { "CONSTRAINT",       "TK_CONSTRAINT",   ALWAYS                 },
 181   { "CREATE",           "TK_CREATE",       ALWAYS                 },
 182   { "CROSS",            "TK_JOIN_KW",      ALWAYS                 },
 183   { "CURRENT_DATE",     "TK_CTIME_KW",     ALWAYS                 },
 184   { "CURRENT_TIME",     "TK_CTIME_KW",     ALWAYS                 },
 185   { "CURRENT_TIMESTAMP","TK_CTIME_KW",     ALWAYS                 },
 186   { "DATABASE",         "TK_DATABASE",     ATTACH                 },
 187   { "DEFAULT",          "TK_DEFAULT",      ALWAYS                 },
 188   { "DEFERRED",         "TK_DEFERRED",     ALWAYS                 },
 189   { "DEFERRABLE",       "TK_DEFERRABLE",   FKEY                   },
 190   { "DELETE",           "TK_DELETE",       ALWAYS                 },
 191   { "DESC",             "TK_DESC",         ALWAYS                 },
 192   { "DETACH",           "TK_DETACH",       ATTACH                 },
 193   { "DISTINCT",         "TK_DISTINCT",     ALWAYS                 },
 194   { "DO",               "TK_DO",           UPSERT                 },
 195   { "DROP",             "TK_DROP",         ALWAYS                 },
 196   { "END",              "TK_END",          ALWAYS                 },
 197   { "EACH",             "TK_EACH",         TRIGGER                },
 198   { "ELSE",             "TK_ELSE",         ALWAYS                 },
 199   { "ESCAPE",           "TK_ESCAPE",       ALWAYS                 },
 200   { "EXCEPT",           "TK_EXCEPT",       COMPOUND               },
 201   { "EXCLUSIVE",        "TK_EXCLUSIVE",    ALWAYS                 },
 202   { "EXISTS",           "TK_EXISTS",       ALWAYS                 },
 203   { "EXPLAIN",          "TK_EXPLAIN",      EXPLAIN                },
 204   { "FAIL",             "TK_FAIL",         CONFLICT|TRIGGER       },
 205   { "FOR",              "TK_FOR",          TRIGGER                },
 206   { "FOREIGN",          "TK_FOREIGN",      FKEY                   },
 207   { "FROM",             "TK_FROM",         ALWAYS                 },
 208   { "FULL",             "TK_JOIN_KW",      ALWAYS                 },
 209   { "GLOB",             "TK_LIKE_KW",      ALWAYS                 },
 210   { "GROUP",            "TK_GROUP",        ALWAYS                 },
 211   { "HAVING",           "TK_HAVING",       ALWAYS                 },
 212   { "IF",               "TK_IF",           ALWAYS                 },
 213   { "IGNORE",           "TK_IGNORE",       CONFLICT|TRIGGER       },
 214   { "IMMEDIATE",        "TK_IMMEDIATE",    ALWAYS                 },
 215   { "IN",               "TK_IN",           ALWAYS                 },
 216   { "INDEX",            "TK_INDEX",        ALWAYS                 },
 217   { "INDEXED",          "TK_INDEXED",      ALWAYS                 },
 218   { "INITIALLY",        "TK_INITIALLY",    FKEY                   },
 219   { "INNER",            "TK_JOIN_KW",      ALWAYS                 },
 220   { "INSERT",           "TK_INSERT",       ALWAYS                 },
 221   { "INSTEAD",          "TK_INSTEAD",      TRIGGER                },
 222   { "INTERSECT",        "TK_INTERSECT",    COMPOUND               },
 223   { "INTO",             "TK_INTO",         ALWAYS                 },
 224   { "IS",               "TK_IS",           ALWAYS                 },
 225   { "ISNULL",           "TK_ISNULL",       ALWAYS                 },
 226   { "JOIN",             "TK_JOIN",         ALWAYS                 },
 227   { "KEY",              "TK_KEY",          ALWAYS                 },
 228   { "LEFT",             "TK_JOIN_KW",      ALWAYS                 },
 229   { "LIKE",             "TK_LIKE_KW",      ALWAYS                 },
 230   { "LIMIT",            "TK_LIMIT",        ALWAYS                 },
 231   { "MATCH",            "TK_MATCH",        ALWAYS                 },
 232   { "NATURAL",          "TK_JOIN_KW",      ALWAYS                 },
 233   { "NO",               "TK_NO",           FKEY                   },
 234   { "NOT",              "TK_NOT",          ALWAYS                 },
 235   { "NOTHING",          "TK_NOTHING",      UPSERT                 },
 236   { "NOTNULL",          "TK_NOTNULL",      ALWAYS                 },
 237   { "NULL",             "TK_NULL",         ALWAYS                 },
 238   { "OF",               "TK_OF",           ALWAYS                 },
 239   { "OFFSET",           "TK_OFFSET",       ALWAYS                 },
 240   { "ON",               "TK_ON",           ALWAYS                 },
 241   { "OR",               "TK_OR",           ALWAYS                 },
 242   { "ORDER",            "TK_ORDER",        ALWAYS                 },
 243   { "OUTER",            "TK_JOIN_KW",      ALWAYS                 },
 244   { "PLAN",             "TK_PLAN",         EXPLAIN                },
 245   { "PRAGMA",           "TK_PRAGMA",       PRAGMA                 },
 246   { "PRIMARY",          "TK_PRIMARY",      ALWAYS                 },
 247   { "QUERY",            "TK_QUERY",        EXPLAIN                },
 248   { "RAISE",            "TK_RAISE",        TRIGGER                },
 249   { "RECURSIVE",        "TK_RECURSIVE",    CTE                    },
 250   { "REFERENCES",       "TK_REFERENCES",   FKEY                   },
 251   { "REGEXP",           "TK_LIKE_KW",      ALWAYS                 },
 252   { "REINDEX",          "TK_REINDEX",      REINDEX                },
 253   { "RELEASE",          "TK_RELEASE",      ALWAYS                 },
 254   { "RENAME",           "TK_RENAME",       ALTER                  },
 255   { "REPLACE",          "TK_REPLACE",      CONFLICT               },
 256   { "RESTRICT",         "TK_RESTRICT",     FKEY                   },
 257   { "RIGHT",            "TK_JOIN_KW",      ALWAYS                 },
 258   { "ROLLBACK",         "TK_ROLLBACK",     ALWAYS                 },
 259   { "ROW",              "TK_ROW",          TRIGGER                },
 260   { "SAVEPOINT",        "TK_SAVEPOINT",    ALWAYS                 },
 261   { "SELECT",           "TK_SELECT",       ALWAYS                 },
 262   { "SET",              "TK_SET",          ALWAYS                 },
 263   { "TABLE",            "TK_TABLE",        ALWAYS                 },
 264   { "TEMP",             "TK_TEMP",         ALWAYS                 },
 265   { "TEMPORARY",        "TK_TEMP",         ALWAYS                 },
 266   { "THEN",             "TK_THEN",         ALWAYS                 },
 267   { "TO",               "TK_TO",           ALWAYS                 },
 268   { "TRANSACTION",      "TK_TRANSACTION",  ALWAYS                 },
 269   { "TRIGGER",          "TK_TRIGGER",      TRIGGER                },
 270   { "UNION",            "TK_UNION",        COMPOUND               },
 271   { "UNIQUE",           "TK_UNIQUE",       ALWAYS                 },
 272   { "UPDATE",           "TK_UPDATE",       ALWAYS                 },
 273   { "USING",            "TK_USING",        ALWAYS                 },
 274   { "VACUUM",           "TK_VACUUM",       VACUUM                 },
 275   { "VALUES",           "TK_VALUES",       ALWAYS                 },
 276   { "VIEW",             "TK_VIEW",         VIEW                   },
 277   { "VIRTUAL",          "TK_VIRTUAL",      VTAB                   },
 278   { "WITH",             "TK_WITH",         CTE                    },
 279   { "WITHOUT",          "TK_WITHOUT",      ALWAYS                 },
 280   { "WHEN",             "TK_WHEN",         ALWAYS                 },
 281   { "WHERE",            "TK_WHERE",        ALWAYS                 },
 282 };
 283
 284 /* Number of keywords */
 285 static int nKeyword = (sizeof(aKeywordTable)/sizeof(aKeywordTable[0]));
 286
 287 /* Map all alphabetic characters into lower-case for hashing.  This is
 288 ** only valid for alphabetics.  In particular it does not work for '_'
 289 ** and so the hash cannot be on a keyword position that might be an '_'.
 290 */
 291 #define charMap(X)   (0x20|(X))
 292
 293 /*
 294 ** Comparision function for two Keyword records
 295 */
 296 static int keywordCompare1(const void *a, const void *b){
 297   const Keyword *pA = (Keyword*)a;
 298   const Keyword *pB = (Keyword*)b;
 299   int n = pA->len - pB->len;
 300   if( n==0 ){
 301     n = strcmp(pA->zName, pB->zName);
 302   }
 303   assert( n!=0 );
 304   return n;
 305 }
 306 static int keywordCompare2(const void *a, const void *b){
 307   const Keyword *pA = (Keyword*)a;
 308   const Keyword *pB = (Keyword*)b;
 309   int n = pB->longestSuffix - pA->longestSuffix;
 310   if( n==0 ){
 311     n = strcmp(pA->zName, pB->zName);
 312   }
 313   assert( n!=0 );
 314   return n;
 315 }
 316 static int keywordCompare3(const void *a, const void *b){
 317   const Keyword *pA = (Keyword*)a;
 318   const Keyword *pB = (Keyword*)b;
 319   int n = pA->offset - pB->offset;
 320   if( n==0 ) n = pB->id - pA->id;
 321   assert( n!=0 );
 322   return n;
 323 }
 324
 325 /*
 326 ** Return a KeywordTable entry with the given id
 327 */
 328 static Keyword *findById(int id){
 329   int i;
 330   for(i=0; i<nKeyword; i++){
 331     if( aKeywordTable[i].id==id ) break;
 332   }
 333   return &aKeywordTable[i];
 334 }
 335
 336 /*
 337 ** This routine does the work.  The generated code is printed on standard
 338 ** output.
 339 */
 340 int main(int argc, char **argv){
 341   int i, j, k, h;
 342   int bestSize, bestCount;
 343   int count;
 344   int nChar;
 345   int totalLen = 0;
 346   int aKWHash[1000];  /* 1000 is much bigger than nKeyword */
 347   char zKWText[2000];
 348
 349   /* Remove entries from the list of keywords that have mask==0 */
 350   for(i=j=0; i<nKeyword; i++){
 351     if( aKeywordTable[i].mask==0 ) continue;
 352     if( j<i ){
 353       aKeywordTable[j] = aKeywordTable[i];
 354     }
 355     j++;
 356   }
 357   nKeyword = j;
 358
 359   /* Fill in the lengths of strings and hashes for all entries. */
 360   for(i=0; i<nKeyword; i++){
 361     Keyword *p = &aKeywordTable[i];
 362     p->len = (int)strlen(p->zName);
 363     assert( p->len<sizeof(p->zOrigName) );
 364     memcpy(p->zOrigName, p->zName, p->len+1);
 365     totalLen += p->len;
 366     p->hash = (charMap(p->zName[0])*4) ^
 367               (charMap(p->zName[p->len-1])*3) ^ (p->len*1);
 368     p->id = i+1;
 369   }
 370
 371   /* Sort the table from shortest to longest keyword */
 372   qsort(aKeywordTable, nKeyword, sizeof(aKeywordTable[0]), keywordCompare1);
 373
 374   /* Look for short keywords embedded in longer keywords */
 375   for(i=nKeyword-2; i>=0; i--){
 376     Keyword *p = &aKeywordTable[i];
 377     for(j=nKeyword-1; j>i && p->substrId==0; j--){
 378       Keyword *pOther = &aKeywordTable[j];
 379       if( pOther->substrId ) continue;
 380       if( pOther->len<=p->len ) continue;
 381       for(k=0; k<=pOther->len-p->len; k++){
 382         if( memcmp(p->zName, &pOther->zName[k], p->len)==0 ){
 383           p->substrId = pOther->id;
 384           p->substrOffset = k;
 385           break;
 386         }
 387       }
 388     }
 389   }
 390
 391   /* Compute the longestSuffix value for every word */
 392   for(i=0; i<nKeyword; i++){
 393     Keyword *p = &aKeywordTable[i];
 394     if( p->substrId ) continue;
 395     for(j=0; j<nKeyword; j++){
 396       Keyword *pOther;
 397       if( j==i ) continue;
 398       pOther = &aKeywordTable[j];
 399       if( pOther->substrId ) continue;
 400       for(k=p->longestSuffix+1; k<p->len && k<pOther->len; k++){
 401         if( memcmp(&p->zName[p->len-k], pOther->zName, k)==0 ){
 402           p->longestSuffix = k;
 403         }
 404       }
 405     }
 406   }
 407
 408   /* Sort the table into reverse order by length */
 409   qsort(aKeywordTable, nKeyword, sizeof(aKeywordTable[0]), keywordCompare2);
 410
 411   /* Fill in the offset for all entries */
 412   nChar = 0;
 413   for(i=0; i<nKeyword; i++){
 414     Keyword *p = &aKeywordTable[i];
 415     if( p->offset>0 || p->substrId ) continue;
 416     p->offset = nChar;
 417     nChar += p->len;
 418     for(k=p->len-1; k>=1; k--){
 419       for(j=i+1; j<nKeyword; j++){
 420         Keyword *pOther = &aKeywordTable[j];
 421         if( pOther->offset>0 || pOther->substrId ) continue;
 422         if( pOther->len<=k ) continue;
 423         if( memcmp(&p->zName[p->len-k], pOther->zName, k)==0 ){
 424           p = pOther;
 425           p->offset = nChar - k;
 426           nChar = p->offset + p->len;
 427           p->zName += k;
 428           p->len -= k;
 429           p->prefix = k;
 430           j = i;
 431           k = p->len;
 432         }
 433       }
 434     }
 435   }
 436   for(i=0; i<nKeyword; i++){
 437     Keyword *p = &aKeywordTable[i];
 438     if( p->substrId ){
 439       p->offset = findById(p->substrId)->offset + p->substrOffset;
 440     }
 441   }
 442
 443   /* Sort the table by offset */
 444   qsort(aKeywordTable, nKeyword, sizeof(aKeywordTable[0]), keywordCompare3);
 445
 446   /* Figure out how big to make the hash table in order to minimize the
 447   ** number of collisions */
 448   bestSize = nKeyword;
 449   bestCount = nKeyword*nKeyword;
 450   for(i=nKeyword/2; i<=2*nKeyword; i++){
 451     for(j=0; j<i; j++) aKWHash[j] = 0;
 452     for(j=0; j<nKeyword; j++){
 453       h = aKeywordTable[j].hash % i;
 454       aKWHash[h] *= 2;
 455       aKWHash[h]++;
 456     }
 457     for(j=count=0; j<i; j++) count += aKWHash[j];
 458     if( count<bestCount ){
 459       bestCount = count;
 460       bestSize = i;
 461     }
 462   }
 463
 464   /* Compute the hash */
 465   for(i=0; i<bestSize; i++) aKWHash[i] = 0;
 466   for(i=0; i<nKeyword; i++){
 467     h = aKeywordTable[i].hash % bestSize;
 468     aKeywordTable[i].iNext = aKWHash[h];
 469     aKWHash[h] = i+1;
 470   }
 471
 472   /* Begin generating code */
 473   printf("%s", zHdr);
 474   printf("/* Hash score: %d */\n", bestCount);
 475   printf("/* zKWText[] encodes %d bytes of keyword text in %d bytes */\n",
 476           totalLen + nKeyword, nChar+1 );
 477   for(i=j=k=0; i<nKeyword; i++){
 478     Keyword *p = &aKeywordTable[i];
 479     if( p->substrId ) continue;
 480     memcpy(&zKWText[k], p->zName, p->len);
 481     k += p->len;
 482     if( j+p->len>70 ){
 483       printf("%*s */\n", 74-j, "");
 484       j = 0;
 485     }
 486     if( j==0 ){
 487       printf("/*   ");
 488       j = 8;
 489     }
 490     printf("%s", p->zName);
 491     j += p->len;
 492   }
 493   if( j>0 ){
 494     printf("%*s */\n", 74-j, "");
 495   }
 496   printf("static const char zKWText[%d] = {\n", nChar);
 497   zKWText[nChar] = 0;
 498   for(i=j=0; i<k; i++){
 499     if( j==0 ){
 500       printf("  ");
 501     }
 502     if( zKWText[i]==0 ){
 503       printf("0");
 504     }else{
 505       printf("'%c',", zKWText[i]);
 506     }
 507     j += 4;
 508     if( j>68 ){
 509       printf("\n");
 510       j = 0;
 511     }
 512   }
 513   if( j>0 ) printf("\n");
 514   printf("};\n");
 515
 516   printf("/* aKWHash[i] is the hash value for the i-th keyword */\n");
 517   printf("static const unsigned char aKWHash[%d] = {\n", bestSize);
 518   for(i=j=0; i<bestSize; i++){
 519     if( j==0 ) printf("  ");
 520     printf(" %3d,", aKWHash[i]);
 521     j++;
 522     if( j>12 ){
 523       printf("\n");
 524       j = 0;
 525     }
 526   }
 527   printf("%s};\n", j==0 ? "" : "\n");
 528
 529   printf("/* aKWNext[] forms the hash collision chain.  If aKWHash[i]==0\n");
 530   printf("** then the i-th keyword has no more hash collisions.  Otherwise,\n");
 531   printf("** the next keyword with the same hash is aKWHash[i]-1. */\n");
 532   printf("static const unsigned char aKWNext[%d] = {\n", nKeyword);
 533   for(i=j=0; i<nKeyword; i++){
 534     if( j==0 ) printf("  ");
 535     printf(" %3d,", aKeywordTable[i].iNext);
 536     j++;
 537     if( j>12 ){
 538       printf("\n");
 539       j = 0;
 540     }
 541   }
 542   printf("%s};\n", j==0 ? "" : "\n");
 543
 544   printf("/* aKWLen[i] is the length (in bytes) of the i-th keyword */\n");
 545   printf("static const unsigned char aKWLen[%d] = {\n", nKeyword);
 546   for(i=j=0; i<nKeyword; i++){
 547     if( j==0 ) printf("  ");
 548     printf(" %3d,", aKeywordTable[i].len+aKeywordTable[i].prefix);
 549     j++;
 550     if( j>12 ){
 551       printf("\n");
 552       j = 0;
 553     }
 554   }
 555   printf("%s};\n", j==0 ? "" : "\n");
 556
 557   printf("/* aKWOffset[i] is the index into zKWText[] of the start of\n");
 558   printf("** the text for the i-th keyword. */\n");
 559   printf("static const unsigned short int aKWOffset[%d] = {\n", nKeyword);
 560   for(i=j=0; i<nKeyword; i++){
 561     if( j==0 ) printf("  ");
 562     printf(" %3d,", aKeywordTable[i].offset);
 563     j++;
 564     if( j>12 ){
 565       printf("\n");
 566       j = 0;
 567     }
 568   }
 569   printf("%s};\n", j==0 ? "" : "\n");
 570
 571   printf("/* aKWCode[i] is the parser symbol code for the i-th keyword */\n");
 572   printf("static const unsigned char aKWCode[%d] = {\n", nKeyword);
 573   for(i=j=0; i<nKeyword; i++){
 574     char *zToken = aKeywordTable[i].zTokenType;
 575     if( j==0 ) printf("  ");
 576     printf("%s,%*s", zToken, (int)(14-strlen(zToken)), "");
 577     j++;
 578     if( j>=5 ){
 579       printf("\n");
 580       j = 0;
 581     }
 582   }
 583   printf("%s};\n", j==0 ? "" : "\n");
 584   printf("/* Check to see if z[0..n-1] is a keyword. If it is, write the\n");
 585   printf("** parser symbol code for that keyword into *pType.  Always\n");
 586   printf("** return the integer n (the length of the token). */\n");
 587   printf("static int keywordCode(const char *z, int n, int *pType){\n");
 588   printf("  int i, j;\n");
 589   printf("  const char *zKW;\n");
 590   printf("  if( n>=2 ){\n");
 591   printf("    i = ((charMap(z[0])*4) ^ (charMap(z[n-1])*3) ^ n) %% %d;\n",
 592           bestSize);
 593   printf("    for(i=((int)aKWHash[i])-1; i>=0; i=((int)aKWNext[i])-1){\n");
 594   printf("      if( aKWLen[i]!=n ) continue;\n");
 595   printf("      j = 0;\n");
 596   printf("      zKW = &zKWText[aKWOffset[i]];\n");
 597   printf("#ifdef SQLITE_ASCII\n");
 598   printf("      while( j<n && (z[j]&~0x20)==zKW[j] ){ j++; }\n");
 599   printf("#endif\n");
 600   printf("#ifdef SQLITE_EBCDIC\n");
 601   printf("      while( j<n && toupper(z[j])==zKW[j] ){ j++; }\n");
 602   printf("#endif\n");
 603   printf("      if( j<n ) continue;\n");
 604   for(i=0; i<nKeyword; i++){
 605     printf("      testcase( i==%d ); /* %s */\n",
 606            i, aKeywordTable[i].zOrigName);
 607   }
 608   printf("      *pType = aKWCode[i];\n");
 609   printf("      break;\n");
 610   printf("    }\n");
 611   printf("  }\n");
 612   printf("  return n;\n");
 613   printf("}\n");
 614   printf("int sqlite3KeywordCode(const unsigned char *z, int n){\n");
 615   printf("  int id = TK_ID;\n");
 616   printf("  keywordCode((char*)z, n, &id);\n");
 617   printf("  return id;\n");
 618   printf("}\n");
 619   printf("#define SQLITE_N_KEYWORD %d\n", nKeyword);
 620   printf("int sqlite3_keyword_name(int i,const char **pzName,int *pnName){\n");
 621   printf("  if( i<0 || i>=SQLITE_N_KEYWORD ) return SQLITE_ERROR;\n");
 622   printf("  *pzName = zKWText + aKWOffset[i];\n");
 623   printf("  *pnName = aKWLen[i];\n");
 624   printf("  return SQLITE_OK;\n");
 625   printf("}\n");
 626   printf("int sqlite3_keyword_count(void){ return SQLITE_N_KEYWORD; }\n");
 627   printf("int sqlite3_keyword_check(const char *zName, int nName){\n");
 628   printf("  return TK_ID!=sqlite3KeywordCode((const u8*)zName, nName);\n");
 629   printf("}\n");
 630
 631   return 0;
 632 }