home *** CD-ROM | disk | FTP | other *** search
/ ProfitPress Mega CDROM2 …eeware (MSDOS)(1992)(Eng) / ProfitPress-MegaCDROM2.B6I / COMM / MISC / SRC26_2.ZIP / SRC / INDEXER.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-07-13  |  11.2 KB  |  514 lines
  1. /*
  2.  * indexer: tiny database index generation utility
  3.  *
  4.  * Author: HIRAHO Satoshi
  5.  * (C) 1989  Halca Computer Science Laboratory TM
  6.  *
  7.  * Edition History:
  8.  * 1.1 89/07/14 Halca.Hirano creation for hterm set-up help system
  9.  *     simple linear search version (but fast enough than grep way)
  10.  * 1.2 89/07/29 Halca.Hirano permit to include comment line
  11.  *        change command system
  12.  *        add -s strip option to strip indexer command
  13.  * 1.3 89/08/14 Halca.Hirano binary-tree version
  14.  *     ---- V2.4.0 distribution ----
  15.  * 1.4 90/05/27 Halca.Hirano
  16.  *    compress text by mad@keio
  17.  *    add include command '@filename'
  18.  * 1.5 90/07/13 Halca.Hirano
  19.  *    add version number to header
  20.  *
  21.  *
  22.  * Description:
  23.  * Indexer generates index to pick up variable length record from given key.
  24.  * There are three components for indexer.
  25.  *
  26.  * Record text; This is a plain text file including keys and appropriate
  27.  * records. e.g,
  28.  * 
  29.  *    comment
  30.  *    > "key1"
  31.  *    this is a text line. '>' means key.
  32.  *    And this is also test for key1.
  33.  *    < end key1
  34.  *    comment
  35.  *    > "key2"
  36.  *    text lines for key2.
  37.  *    < end key2
  38.  * Lines beginning with # character in record are written to a file
  39.  * after removed # character.
  40.  * 
  41.  * Database file; This is generated by indexer from Record text.
  42.  * Index information is included in head part of the file.
  43.  *
  44.  *    header
  45.  *    records
  46.  *    index part (key and index to records)
  47.  *
  48.  * Library; indexlib.c is a access facility to the database file.
  49.  * This should be linked with users application program to use database.
  50.  *
  51.  */
  52.  
  53. static char version[] = "$Header: indexer.cv  1.8  90/07/04 01:07:40  hirano  Exp $";
  54.  
  55. char help[] = "\
  56. Function: generate index file\n\
  57. Syntax: indexer [options] <input text file> <output file>\n\
  58. Options: -s   strip indexer command\n\
  59. Example: indexer help.doc help.db\n\
  60. ";
  61.  
  62. #include <stdio.h>
  63. #include <ctype.h>
  64. #include <string.h>
  65. #include <stdlib.h>
  66. #include "indexer.h"
  67.  
  68. #define YES        1
  69. #define NO        0
  70. #define MAX_LINE    256
  71. #define skipSpace(x) {while (*(x) == ' ' || *(x) == '\t') (x)++;}
  72. #define MAX_KEY    500
  73. #define S_COMMENT    1
  74. #define S_RECORD    2
  75.  
  76. #ifdef MSDOS
  77. #define OUT_ATTR "wb"
  78. #else
  79. #define OUT_ATTR "w"
  80. #endif /* MSDOS */
  81.  
  82.  
  83. char headerString[] = "Generated by indexer %d.%d. Don't edit this file.\n";
  84.  
  85. FILE     *ifp;                /* input file             */
  86. FILE     *ofp;                /* output file            */
  87. FILE     *tfp;                /* temporary file        */
  88. long    root;                /* binary-tree root        */
  89. Index    keys[MAX_KEY];        /* keys                    */
  90. int        numKey;                /* keys index            */
  91. int        lineNo;
  92. char    *fileName;            /* input file name        */
  93. char    line[MAX_LINE];
  94. struct _header header;
  95. int        state;
  96. int        stripMode = NO;        /* default non stip mode */
  97. long    RecordSize;            /* Size of current record. */
  98.  
  99. struct _fileStack {
  100.     FILE *ifp;
  101.     int lineNo;
  102.     char fileName[50];
  103. } fileStack[30];
  104. int fileStackPtr = 0;
  105.  
  106. typedef unsigned char u_char;
  107.  
  108. void stripper(void );
  109. void indexer(void );
  110. void keyStart(void);
  111. void keyEnd(char *line);
  112. void text(char *s);
  113. void cutKey(char *p,char *key);
  114. void newFile(char *file);
  115. int oldFile(void );
  116. void error(char *s,char *line);
  117. void bInsert(char *s,int indexNo);
  118. int WriteCode(unsigned short code,FILE *fp,int bits);
  119. void ResetWrite(void );
  120. int EndWrite(FILE *fp);
  121. int SearchCode(unsigned short code,unsigned char c);
  122. int WriteChar(unsigned char c, FILE *fp);
  123.  
  124. main(argc, argv)
  125. char **argv;
  126. {
  127.     register char *p;
  128.     while (--argc > 0)
  129.         if (*(p = *++argv) == '-')
  130.             for (++p; *p; p++)
  131.                 switch (tolower(*p)) {
  132.                 case 's': stripMode = YES; break;
  133.                 case 'h':
  134.                 case '?':
  135.                 default:
  136.                     fprintf(stderr, help);
  137.                     exit(1);
  138.                 }
  139.         else
  140.             break;
  141.     if (argc != 2) {
  142.         fprintf(stderr, help);
  143.         exit(1);
  144.     }
  145.  
  146.     if ((ifp = fopen(*argv, "r")) == NULL) {
  147.         fprintf(stderr, help);
  148.         fprintf(stderr, "indexer: can't open input file %s\n", *argv);
  149.         exit(1);
  150.     }
  151.     fileName = *argv;
  152.     fprintf(stderr, "File %s\n", fileName);
  153.     
  154.     if ((ofp = fopen(*++argv, stripMode ? "w" : OUT_ATTR)) == NULL) {
  155.         fprintf(stderr, help);
  156.         fprintf(stderr, "can't open output file %s\n", *argv);
  157.         exit(1);
  158.     }
  159.  
  160.     if (stripMode)
  161.         stripper();
  162.     else
  163.         indexer();
  164.     fclose(ifp);
  165.     fclose(ofp);
  166. }
  167.  
  168. static void stripper()
  169. /*
  170.  * strip mode; strip indexer command
  171.  */
  172. {
  173.     do {
  174.         while (fgets(line, MAX_LINE, ifp) > 0) {
  175.             switch (line[0]) {
  176.             case KEY:
  177.             case KEY_END:
  178.             case STRIP:
  179.                 break;
  180.             case INCLUDE:
  181.                 *strchr(line, '\n') = '\0';
  182.                 newFile(&line[1]);
  183.             default:
  184.                 fputs(line, ofp);
  185.             }
  186.         }
  187.     } while (oldFile());
  188. }
  189.  
  190. static void indexer()
  191. /*
  192.  * indexer: generate indexed file
  193.  */
  194. {
  195.     int i;
  196.  
  197.     lineNo = 0;
  198.     state = S_COMMENT;
  199.     numKey = 0;
  200.     root = -1;
  201.     for (i = 0; i < MAX_KEY; i++)
  202.         keys[i].right = keys[i].left = -1;
  203.  
  204.     sprintf(header.header, "incomplete\n");
  205.     fwrite(&header, sizeof(header), 1, ofp);
  206.      ResetWrite();
  207.  
  208.      do {
  209.         while (fgets(line, MAX_LINE, ifp) > 0) {
  210.             lineNo++;
  211.             if (line[0] == KEY)
  212.                 keyStart();
  213.             else if (line[0] == KEY_END)
  214.                 keyEnd(line);
  215.             else if (line[0] == INCLUDE) {
  216.                 *strchr(line, '\n') = '\0';
  217.                 newFile(&line[1]);
  218.             } else if (state == S_RECORD)
  219.                 text(line);
  220.             /* else ignore */
  221.         }
  222.     } while (oldFile());
  223.  
  224.     if (state == S_RECORD)
  225.         keyEnd(line);
  226.  
  227.     sprintf(header.header, headerString, I_VERSION, I_REVISION);
  228.     fflush(ofp);        /* need because MSC5.1 ftell() bug */
  229.     header.numIndex = numKey;
  230.     header.indexOffset = ftell(ofp);
  231.     header.version = I_VERSION;
  232.     header.revision = I_REVISION;
  233.     fseek(ofp, 0L, 0);            /* head of file        */
  234.     fwrite(&header, sizeof(header), 1, ofp);
  235.  
  236.     fseek(ofp, 0L, 2);            /* end of file        */
  237.     /*
  238.      * We may sort index here. 
  239.      */
  240.     for (i = 0; i < numKey; i++) {
  241.         keys[i].right = keys[i].right * sizeof(Index) + header.indexOffset;
  242.         keys[i].left = keys[i].left * sizeof(Index) + header.indexOffset;
  243.         fwrite(&keys[i], sizeof(keys[i]), 1, ofp);
  244.     }
  245. }
  246.  
  247. static void keyStart()
  248. {
  249.     if (state == S_RECORD) {
  250.         fprintf(stderr, "warning: missing '<' line %d, assume end of record\n", line);
  251.         keyEnd(line);
  252.     }
  253.     if (numKey > MAX_KEY) {
  254.         fprintf(stderr, "indexer: sorry, too many key (max %d)\n", MAX_KEY);
  255.         exit(1);
  256.     }
  257.     keys[numKey].offset = ftell(ofp);
  258.     cutKey(&line[1], keys[numKey].key);
  259.     if (strlen(keys[numKey].key) == 0)
  260.         error("key length is zero", line);
  261.     bInsert(keys[numKey].key, numKey);
  262.     fprintf(stderr, "%d %d: '%s'", numKey+1, lineNo, keys[numKey].key);
  263.     numKey++;
  264.     state = S_RECORD;
  265. }
  266.  
  267. static void keyEnd(line)
  268. char *line;
  269. {
  270.     if (state != S_RECORD)
  271.         error("no key", line);
  272.     EndWrite(ofp);
  273.     keys[numKey-1].size = RecordSize;
  274.     if (keys[numKey-1].size == 0)
  275.         fprintf(stderr, "warning: no record for key '%s'\n", keys[numKey-1].key);
  276.     cutKey(&line[1], keys[numKey-1].nextKey);
  277.     fprintf(stderr, " -> '%s'\n", keys[numKey-1].nextKey);
  278.     RecordSize = 0;
  279.     state = S_COMMENT;
  280. }
  281.  
  282. static void text(s)
  283. char *s;
  284. {
  285.     if (*s == STRIP)
  286.         s++;        /* remove force strip command    */
  287.     while (*s) {
  288.         RecordSize++;
  289.         WriteChar(*s++, ofp);
  290.     }
  291. }
  292.  
  293. static void cutKey(p, key)
  294. char *p;
  295. char *key;
  296. {
  297.     char term = '\n';
  298.     char *k = key;
  299.     int i;
  300.  
  301.     skipSpace(p);
  302.     if (*p == KEY_PAREN1 || *p == KEY_PAREN2) {
  303.         term = *p;
  304.         p++;
  305.     }
  306.     for (i = 0; *p != term; i++) {
  307.         if (i >= KEY_LEN)
  308.             error("key too long line", line);
  309.         *k++ = *p++;
  310.     }
  311.     *k = '\0';
  312. }
  313.  
  314. static void newFile(file)
  315. char *file;
  316. {
  317.     fileStack[fileStackPtr].ifp = ifp;
  318.     fileStack[fileStackPtr].lineNo = lineNo;
  319.     strcpy(fileStack[fileStackPtr].fileName, fileName);
  320.     fileStackPtr++;
  321.     if ((ifp = fopen(file, "r")) == NULL) {
  322.         fprintf(stderr, "indexer: can't open input file %s\n", file);
  323.         exit(1);
  324.     }
  325.     fprintf(stderr, "File %s\n", file);
  326.     lineNo = 1;
  327. }
  328.  
  329. static int oldFile()
  330. {
  331.     if (--fileStackPtr < 0)
  332.         return(NO);
  333.     fclose(ifp);
  334.     ifp = fileStack[fileStackPtr].ifp;
  335.     lineNo = fileStack[fileStackPtr].lineNo;
  336.     fileName = fileStack[fileStackPtr].fileName;
  337.     return(YES);
  338. }    
  339.  
  340. static void error(s, line)
  341. char *s, *line;
  342. {
  343.     fprintf(stderr, "indexer: %s\n", s);
  344.     fprintf(stderr, "%s(%d): %s", fileName, lineNo, line);
  345.     exit(1);
  346. }
  347.  
  348. static void bInsert(s, indexNo)
  349. /*
  350.  * binary-tree insert
  351.  */
  352. char *s;            /* new key string     */
  353. int indexNo;            /* new key no        */
  354. {
  355.     register long *p = &root;
  356.     register int bs;
  357.  
  358.     while (*p != -1) {
  359.         if ((bs = strcmp(s, keys[*p].key)) > 0)
  360.             p = &(keys[*p].right);
  361.         else if (bs < 0)
  362.             p = &(keys[*p].left);
  363.         else {
  364.             fprintf(stderr, "duplicated key %s\n", s);
  365.             exit(1);
  366.         }    
  367.     }
  368.     *p = (long)indexNo;
  369. }
  370.  
  371. #ifdef COMPRESS_DB
  372. /* #define TABLESIZE 1500 */
  373. #define TABLESIZE 1000
  374.  
  375. static unsigned short MaxCode;
  376. static int    BitLength;
  377. static int    BitsLeft;
  378. static unsigned long    BitBuff;
  379. static unsigned short LastCode;
  380. static int     NotFirstTime;
  381.  
  382. static unsigned short mask[] = 
  383. {
  384.     0, 1, 3, 7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff,    0x3ff
  385. };
  386.  
  387. static struct {
  388.     unsigned short code;
  389.     unsigned char    next;
  390.     unsigned short NewCode;
  391. } table[TABLESIZE];
  392.  
  393. static int WriteCode(unsigned short code, FILE *fp, int bits)
  394. /* Convert n-bit code to 8 bit stream and write to file. */
  395. {
  396.     int    value;
  397.     int    NextBitsLeft;
  398.  
  399.     if (code > MaxCode) {
  400.         fprintf(stderr, "I'm sorry -- %d, MaxCode = %d\n",
  401.             (int)code, (int) MaxCode);
  402.     }
  403.     NextBitsLeft = BitsLeft + bits - 8;
  404.     value = putc((BitBuff << (8 - BitsLeft)) +
  405.              (code >> NextBitsLeft), fp);
  406.     BitBuff = code & mask[NextBitsLeft];
  407.     BitsLeft = NextBitsLeft;
  408.  
  409.     if (BitsLeft >= 8) {
  410.         BitsLeft -= 8;
  411.         value = putc(BitBuff >> BitsLeft, fp);
  412.         BitBuff = BitBuff & mask[BitsLeft];
  413.     }
  414.     return value;
  415. }
  416.  
  417. static void ResetWrite(void)
  418. {
  419.     int    i;
  420.  
  421.     BitsLeft = 0;
  422.     BitBuff = 0;
  423.     NotFirstTime = 0;
  424.     MaxCode = 255;
  425.     BitLength = 9;
  426.     for (i = 0; i < TABLESIZE; i++) {
  427.         table[i].code = 0;
  428.         table[i].next = 0;
  429.         table[i].NewCode = 0;
  430.     }
  431. }
  432.  
  433. static int EndWrite(FILE *fp)
  434. {
  435.     int    value;
  436.  
  437.     WriteCode(LastCode, fp, BitLength);
  438.     value = WriteCode((unsigned short) 0, fp, BitLength);
  439.     ResetWrite();
  440.     return value;
  441. }
  442.  
  443. static int SearchCode(unsigned short code, unsigned char c)
  444. /* Search hash table and return index to the table.
  445.    The result entry may be empty or may have code and char
  446.    equal to args. */
  447. {
  448.     unsigned hash = code ^ c;
  449.     int i;
  450.  
  451.     i = hash;
  452.     do {
  453.         if (table[i].NewCode == 0)
  454.             /* This entry is empty. */
  455.             return i;
  456.         if (table[i].code == code && table[i].next == c)
  457.             return i;
  458.         if (++i > TABLESIZE)
  459.             i = 0;
  460.     } while (i != hash);
  461.  
  462.     /* This can never happen because table can never be full. */
  463.     return 0;
  464. }
  465.  
  466. static int WriteChar(unsigned char c, FILE *fp)
  467. {
  468.     int    i;
  469.     int    value;
  470.  
  471.     if (! NotFirstTime) {
  472.         NotFirstTime = 1;
  473.         LastCode = c;
  474.         return (int) c;
  475.     }
  476.     i = SearchCode(LastCode, c);
  477.     if (table[i].NewCode == MaxCode) {
  478.         /* This code is not yet known to uncompressor. */
  479.         MaxCode++;
  480.         value = WriteCode(LastCode, fp, BitLength);
  481.         LastCode = c;
  482.         return value;
  483.     }
  484.     if (table[i].NewCode == 0) {
  485.         /* New code */
  486.         value = WriteCode(LastCode, fp, BitLength);
  487.         if (MaxCode < 1023) {
  488.             MaxCode++;
  489.             if (MaxCode == 512)
  490.                 BitLength = 10;
  491.             table[i].NewCode = MaxCode;
  492.             table[i].code = LastCode;
  493.             table[i].next = c;
  494.         }
  495.         LastCode = c;
  496.         return value;
  497.     } else {
  498.         LastCode = table[i].NewCode;
  499.         return c;
  500.     }
  501. }
  502. #else
  503. static void ResetWrite()
  504. {}
  505. static void EndWrite()
  506. {}
  507. static int WriteChar(c, fp)
  508. u_char c;
  509. FILE *fp;
  510. {
  511.     fwrite(&c, 1, 1, fp);
  512. }
  513. #endif /* COMPRESS_DB */
  514.