home *** CD-ROM | disk | FTP | other *** search
/ Fish 'n' More 2 / fishmore-publicdomainlibraryvol.ii1991xetec.iso / dirs / mkid_448.lzh / Mkid / src / mkid.c < prev    next >
C/C++ Source or Header  |  1991-02-01  |  18KB  |  792 lines
  1. static char copyright[] = "@(#)Copyright (c) 1986, Greg McGary";
  2. static char sccsid[] = "@(#)mkid.c    1.4 86/11/06";
  3.  
  4. /* #define register */
  5.  
  6. #include    "bool.h"
  7. #ifdef UNIX
  8. #include    <sys/types.h>
  9. #include    <sys/stat.h>
  10. #endif
  11. #include    <stdio.h>
  12. #include    "string.h"
  13. #include    <ctype.h>
  14. #include    "id.h"
  15. #include    "bitops.h"
  16. #include    <errno.h>
  17. #include    "extern.h"
  18. #ifdef AMIGA
  19. #include    <time.h>
  20. #include    <dos.h>
  21. #endif
  22.  
  23. int idnHashCmp();
  24. int idnQsortCmp();
  25. int round2();
  26. struct idname *newIdName();
  27. void extractId();
  28. void fileIdArgs();
  29. void initHashTable();
  30. void oldIdArgs();
  31. void rehash();
  32. void updateID();
  33. void writeID();
  34.  
  35. long    NameCount;        /* Count of names in database */
  36. long    NumberCount;        /* Count of numbers in database */
  37. long    StringCount;        /* Count of strings in database */
  38. long    SoloCount;        /* Count of identifiers that occur only once */
  39.  
  40. long    HashSize;        /* Total Slots in hash table */
  41. long    HashMaxLoad;        /* Maximum loading of hash table */
  42. long    HashFill;        /* Number of keys inserted in table */
  43. long    HashProbes;        /* Total number of probes */
  44. long    HashSearches;        /* Total number of searches */
  45. struct idname    **HashTable;    /* Vector of idname pointers */
  46.  
  47. bool    Verbose = FALSE;
  48.  
  49. int    ArgsCount = 0;        /* Count of args to save */
  50. int    ScanCount = 0;        /* Count of files to scan */
  51. int    PathCount = 0;        /* Count of files covered in database */
  52. int    BitArraySize;        /* Size of bit array slice (per name) */
  53.  
  54.  
  55. char    *MyName;
  56. static void
  57. usage()
  58. {
  59.     fprintf(stderr, "Usage: %s [-f<idfile>] [-s<dir>] [-r<dir>] [(+|-)l[<lang>]] [-v] [(+|-)S<scanarg>] [-a<argfile>] [-] [-u] [files...]\n", MyName);
  60.     exit(1);
  61. }
  62. main(argc, argv)
  63.     int        argc;
  64.     char        **argv;
  65. {
  66.     char        *arg;
  67.     int        op;
  68.     FILE        *argFILE = NULL;
  69.     char        *idFile = IDFILE;
  70.     char        *rcsDir = NULL;
  71.     char        *sccsDir = NULL;
  72.     struct idarg    *idArgs, *idArgHead;
  73.     bool        keepLang = FALSE;
  74.     int        argsFrom = 0;
  75. #define    AF_CMDLINE    0x1    /* file args came on command line */
  76. #define    AF_FILE        0x2    /* file args came from a file (-f<file>) */
  77. #define    AF_IDFILE    0x4    /* file args came from an old ID file (-u) */
  78. #define    AF_QUERY    0x8    /* no file args necessary: usage query */
  79.  
  80.     MyName = basename(GETARG(argc, argv));
  81. #ifdef ERRLINEBUF
  82.     setlinebuf(stderr);
  83. #endif
  84.  
  85.     idArgs = idArgHead = NEW(struct idarg);
  86.  
  87.     /*
  88.         Process some arguments, and snarf-up some
  89.         others for processing later.
  90.     */
  91.     while (argc) {
  92.         arg = GETARG(argc, argv);
  93.         if (*arg != '-' && *arg != '+') {
  94.             argsFrom |= AF_CMDLINE;
  95.             idArgs->ida_arg = arg;
  96.             idArgs->ida_flags = IDA_SCAN|IDA_PATH;
  97.             idArgs->ida_index = postIncr(&PathCount);
  98.             ScanCount++;
  99.             idArgs = (idArgs->ida_next = NEW(struct idarg));
  100.             continue;
  101.         }
  102.         op = *arg++;
  103.         switch (*arg++)
  104.         {
  105.         case 'u':
  106.             argsFrom |= AF_IDFILE;
  107.             oldIdArgs(idFile, &idArgs);
  108.             break;
  109.         case '\0':
  110.             argsFrom |= AF_FILE;
  111.             fileIdArgs(stdin, &idArgs);
  112.             break;
  113.         case 'a':
  114.             if ((argFILE = fopen(arg, "r")) == NULL) {
  115.                 filerr("open", arg);
  116.                 exit(1);
  117.             }
  118.             argsFrom |= AF_FILE;
  119.             fileIdArgs(argFILE, &idArgs);
  120.             fclose(argFILE);    /* added REJ */
  121.             break;
  122.         case 'f':
  123.             idFile = arg;
  124.             break;
  125.         case 'v':
  126.             Verbose = TRUE;
  127.             break;
  128.         case 'S':
  129.             if (strchr(&arg[-2], '?')) {
  130.                 setScanArgs(op, arg);
  131.                 argsFrom |= AF_QUERY;
  132.             }
  133.             /*FALLTHROUGH*/
  134.         case 'l':
  135.         case 's':
  136.         case 'r':
  137.             idArgs->ida_arg = &arg[-2];
  138.             idArgs->ida_index = -1;
  139.             idArgs->ida_flags = IDA_ARG;
  140.             idArgs = (idArgs->ida_next = NEW(struct idarg));
  141.             ArgsCount++;
  142.             break;
  143.         default:
  144.             usage();
  145.         }
  146.     }
  147.  
  148.     if (argsFrom & AF_QUERY)
  149.         exit(0);
  150.     /*
  151.         File args should only come from one place.  Ding the
  152.         user if arguments came from multiple places, or if none
  153.         were supplied at all.
  154.     */
  155.     switch (argsFrom)
  156.     {
  157.     case AF_CMDLINE:
  158.     case AF_FILE:
  159.     case AF_IDFILE:
  160.         if (PathCount > 0)
  161.             break;
  162.         /*FALLTHROUGH*/
  163.     case 0:
  164.         fprintf(stderr, "%s: Use -u, -f<file>, or cmd-line for file args!\n", MyName);
  165.         usage();
  166.     default:
  167.         fprintf(stderr, "%s: Use only one of: -u, -f<file>, or cmd-line for file args!\n", MyName);
  168.         usage();
  169.     }
  170.  
  171.     if (ScanCount == 0)
  172.         exit(0);
  173.  
  174.     BitArraySize = (PathCount + 7) >> 3;
  175.     initHashTable(ScanCount);
  176.  
  177.     if (access(idFile, 06) < 0
  178.     && (errno != ENOENT || access(dirname(idFile), 06) < 0)) {
  179.         filerr("modify", idFile);
  180.         exit(1);
  181.     }
  182.  
  183.     for (idArgs = idArgHead; idArgs->ida_next; idArgs = idArgs->ida_next) {
  184.         char        *(*scanner)();
  185.         FILE        *srcFILE;
  186.         char        *arg, *lang = NULL, *suff;
  187. /* added = NULL - it assumed locals were zeroed! REJ */
  188.  
  189.         arg = idArgs->ida_arg;
  190.         if (idArgs->ida_flags & IDA_ARG) {
  191.             op = *arg++;
  192.             switch (*arg++)
  193.             {
  194.             case 'l':
  195.                 if (*arg == '\0') {
  196.                     keepLang = FALSE;
  197.                     lang = NULL;
  198.                     break;
  199.                 }
  200.                 if (op == '+')
  201.                     keepLang = TRUE;
  202.                 lang = arg;
  203.                 break;
  204.             case 's':
  205.                 sccsDir = arg;
  206.                 break;
  207.             case 'r':
  208.                 rcsDir = arg;
  209.                 break;
  210.             case 'S':
  211.                 setScanArgs(op, strsav(arg));
  212.                 break;
  213.             default:
  214.                 usage();
  215.             }
  216.             continue;
  217.         }
  218.         if (!(idArgs->ida_flags & IDA_SCAN))
  219.             goto skip;
  220.         if (lang == NULL) {
  221.             if ((suff = strrchr(arg, '.')) == NULL)
  222.                 suff = "";
  223.             if ((lang = getLanguage(suff)) == NULL) {
  224.                 fprintf(stderr, "%s: No language assigned to suffix: `%s'\n", MyName, suff);
  225.                 goto skip;
  226.             }
  227.         }
  228.         if ((scanner = getScanner(lang)) == NULL) {
  229.             fprintf(stderr, "%s: No scanner for language: `%s'\n",
  230.                 MyName, lang);
  231.             goto skip;
  232.         }
  233.         if ((srcFILE = openSrcFILE(arg, sccsDir, rcsDir)) == NULL)
  234.             goto skip;
  235.         if (Verbose)
  236.             fprintf(stderr, "%s: %s\n", lang, arg);
  237.         extractId(scanner, srcFILE, idArgs->ida_index);
  238.         fclose(srcFILE);
  239.     skip:
  240.         if (!keepLang)
  241.             lang = NULL;
  242.     }
  243.  
  244.     if (HashFill == 0)
  245.         exit(0);
  246.  
  247.     if (Verbose)
  248.         fprintf(stderr, "Compressing Hash Table...\n");
  249.     hashCompress(HashTable, HashSize);
  250.     if (Verbose)
  251.         fprintf(stderr, "Sorting Hash Table...\n");
  252.     qsort(HashTable, HashFill, sizeof(struct idname *), idnQsortCmp);
  253.  
  254.     if (argsFrom == AF_IDFILE) {
  255.         if (Verbose)
  256.             fprintf(stderr, "Merging Tables...\n");
  257.         updateID(idFile, idArgHead);
  258.     }
  259.  
  260.     if (Verbose)
  261.         fprintf(stderr, "Writing `%s'...\n", idFile);
  262.     writeID(idFile, idArgHead);
  263.  
  264.     if (Verbose) {
  265.         float loadFactor = (float)HashFill / (float)HashSize;
  266.         float aveProbes = (float)HashProbes / (float)HashSearches;
  267.         float aveOccur = (float)HashSearches / (float)HashFill;
  268.         fprintf(stderr, "Names: %ld, ", NameCount);
  269.         fprintf(stderr, "Numbers: %ld, ", NumberCount);
  270.         fprintf(stderr, "Strings: %ld, ", StringCount);
  271.         fprintf(stderr, "Solo: %ld, ", SoloCount);
  272.         fprintf(stderr, "Total: %ld\n", HashFill);
  273.         fprintf(stderr, "Occurances: %.2f, ", aveOccur);
  274.         fprintf(stderr, "Load: %.2f, ", loadFactor);
  275.         fprintf(stderr, "Probes: %.2f\n", aveProbes);
  276.     }
  277.     exit(0);
  278. }
  279.  
  280. void
  281. extractId(getId, srcFILE, index)
  282.     register char    *(*getId)();
  283.     register FILE    *srcFILE;
  284.     int        index;
  285. {
  286.     register struct idname    **slot;
  287.     register char    *key;
  288.     int        flags;
  289.  
  290.     while ((key = (*getId)(srcFILE, &flags)) != NULL) {
  291.         slot = (struct idname **)hashSearch(key, HashTable, HashSize, sizeof(struct idname *), h1str, h2str, idnHashCmp, &HashProbes);
  292.         HashSearches++;
  293.         if (*slot != NULL) {
  294.             (*slot)->idn_flags |= flags;
  295.             BITSET((*slot)->idn_bitv, index);
  296.             continue;
  297.         }
  298.         *slot = newIdName(key);
  299.         (*slot)->idn_flags = IDN_SOLO|flags;
  300.         BITSET((*slot)->idn_bitv, index);
  301.         if (HashFill++ >= HashMaxLoad)
  302.             rehash();
  303.     }
  304. }
  305.  
  306. void
  307. writeID(idFile, idArgs)
  308.     char        *idFile;
  309.     struct idarg    *idArgs;
  310. {
  311.     register struct idname    **idnp;
  312.     register struct idname    *idn;
  313.     register int    i;
  314.     char        *vecBuf;
  315.     FILE        *idFILE;
  316.     int        count;
  317.     int        lasti;
  318.     long        before, after;
  319.     int        length, longest;
  320.     struct idhead    idh;
  321.  
  322. /* note: for -u to work on non-unix, updateID MUST close idFILE so open */
  323. /* can succeed REJ                             */
  324.     if ((idFILE = fopen(idFile, "w+")) == NULL) {
  325.         filerr("create", idFile);
  326.         exit(1);
  327.     }
  328.     fseek(idFILE, (long)sizeof(struct idhead), 0);
  329.  
  330.     /* write out the list of pathnames */
  331.     idh.idh_argo = ftell(idFILE);
  332.     for (i = lasti = 0; idArgs->ida_next; idArgs = idArgs->ida_next) {
  333.         if (idArgs->ida_index > 0)
  334.             while (++lasti < idArgs->ida_index)
  335.                 i++, putc('\0', idFILE);
  336.         fputs(idArgs->ida_arg, idFILE);
  337.         i++, putc('\0', idFILE);
  338.     }
  339.     idh.idh_argc = i;
  340.     idh.idh_pthc = PathCount;
  341.  
  342.     /* write out the list of identifiers */
  343.     i = 1;
  344.     if (idh.idh_pthc >= 0x000000ff)
  345.         i++;
  346.     if (idh.idh_pthc >= 0x0000ffff)
  347.         i++;
  348.     if (idh.idh_pthc >= 0x00ffffff)
  349.         i++;
  350.     idh.idh_vecc = i;
  351.  
  352.     vecBuf = malloc((idh.idh_pthc + 1) * idh.idh_vecc);
  353.  
  354.     putc('\377', idFILE);
  355.     before = idh.idh_namo = ftell(idFILE);
  356.     longest = 0;
  357.     for (idnp = HashTable, i = 0; i < HashFill; i++, idnp++) {
  358.         idn = *idnp;
  359.         if (idn->idn_name[0] == '\0') {
  360.             HashFill--; i--;
  361.             continue;
  362.         }
  363.         if (idn->idn_flags & IDN_SOLO)
  364.             SoloCount++;
  365.         if (idn->idn_flags & IDN_NUMBER)
  366.             NumberCount++;
  367.         if (idn->idn_flags & IDN_NAME)
  368.             NameCount++;
  369.         if (idn->idn_flags & IDN_STRING)
  370.             StringCount++;
  371.  
  372.         putc((*idnp)->idn_flags, idFILE);
  373.         fputs(idn->idn_name, idFILE);
  374.         putc('\0', idFILE);
  375.  
  376.         count = bitsToVec(vecBuf, (*idnp)->idn_bitv, idh.idh_pthc, idh.idh_vecc);
  377.         fwrite(vecBuf, idh.idh_vecc, count, idFILE);
  378.         putc('\377', idFILE);
  379.         after = ftell(idFILE);
  380.         
  381.         if ((length = (after - before)) > longest)
  382.             longest = length;
  383.         before = after;
  384.     }
  385.     idh.idh_namc = i;
  386.     putc('\377', idFILE);
  387.     idh.idh_endo = ftell(idFILE);
  388.     idh.idh_bsiz = longest;
  389.  
  390.     /* write out the header */
  391.     strncpy(idh.idh_magic, IDH_MAGIC, sizeof(idh.idh_magic));
  392.     idh.idh_vers = IDH_VERS;
  393.     fseek(idFILE, 0L, 0);
  394.     fwrite((char *) &idh, sizeof(struct idhead), 1, idFILE);
  395.  
  396.     fclose(idFILE);
  397. }
  398.  
  399. /*
  400.     Build an idarg vector from pathnames contained in an existing
  401.     id file.  Only include pathnames for files whose modification
  402.     time is later than that of the id file itself.
  403. */
  404. void
  405. oldIdArgs(idFile, idArgsP)
  406.     char        *idFile;
  407.     struct idarg    **idArgsP;
  408. {
  409. #ifdef UNIX
  410.     struct stat    statBuf;
  411. #endif
  412.     struct idhead    idh;
  413.     FILE        *idFILE;
  414.     register int    i;
  415.     register char    *strings;
  416.     time_t        idModTime;
  417. #ifdef AMIGA
  418.     time_t        tmptime;
  419. #endif
  420.  
  421.     if ((idFILE = fopen(idFile, "r")) == NULL) {
  422.         filerr("open", idFile);
  423.         usage();
  424.     }
  425.     /*
  426.     *  Open the id file, get its mod-time, and read its header.
  427.     */
  428. #ifdef UNIX
  429.     if (fstat(fileno(idFILE), &statBuf) < 0) {
  430.         filerr("stat", idFile);
  431.         usage();
  432.     }
  433.     idModTime = statBuf.st_mtime;
  434. #endif
  435. #ifdef AMIGA
  436.     if ((idModTime = getft(idFile)) == -1) {
  437.         filerr("getft(stat)",idFile);
  438.         usage();
  439.     }
  440. #endif
  441.     fread((char *) &idh, sizeof(struct idhead), 1, idFILE);
  442.     if (!strnequ(idh.idh_magic, IDH_MAGIC, sizeof(idh.idh_magic))) {
  443.         fprintf(stderr, "%s: Not an id file: `%s'\n", MyName, idFile);
  444.         exit(1);
  445.     }
  446.     if (idh.idh_vers != IDH_VERS) {
  447.         fprintf(stderr, "%s: ID version mismatch (%ld,%ld)\n", MyName, idh.idh_vers, IDH_VERS);
  448.         exit(1);
  449.     }
  450.  
  451.     /*
  452.     *  Read in the id pathnames, compare their mod-times with
  453.     *  the id file, and incorporate the pathnames of recently modified 
  454.     *  files in the idarg vector.  Also, construct a mask of
  455.     *  bit array positions we want to turn off when we build the
  456.     *  initial hash-table.
  457.     */
  458.     fseek(idFILE, idh.idh_argo, 0);
  459.     strings = malloc(i = idh.idh_namo - idh.idh_argo);
  460.     fread(strings, i, 1, idFILE);
  461.     ScanCount = 0;
  462.     for (i = 0; i < idh.idh_argc; i++) {
  463.         (*idArgsP)->ida_arg = strings;
  464.         if (*strings == '+' || *strings == '-') {
  465.             (*idArgsP)->ida_flags = IDA_ARG;
  466.             (*idArgsP)->ida_index = -1;
  467.         } else {
  468.             (*idArgsP)->ida_flags = IDA_PATH;
  469.             (*idArgsP)->ida_index = postIncr(&PathCount);
  470. #ifdef UNIX
  471.             if (stat(strings, &statBuf) < 0) {
  472.                 filerr("stat", strings);
  473.             } else if (statBuf.st_mtime >= idModTime) {
  474. #endif
  475. #ifdef AMIGA
  476.             if ((tmptime = getft(strings)) == -1)
  477.                 filerr("getft(stat)",strings);
  478.             else if (tmptime >= idModTime) {
  479. #endif
  480.                 (*idArgsP)->ida_flags |= IDA_SCAN;
  481.                 ScanCount++;
  482.             }
  483.         }
  484.         (*idArgsP) = ((*idArgsP)->ida_next = NEW(struct idarg));
  485.         while (*strings++)
  486.             ;
  487.     }
  488.     fclose(idFILE);
  489.  
  490.     if (ScanCount == 0) {
  491.         exit(0);
  492.     }
  493. }
  494.  
  495. void
  496. updateID(idFile, idArgs)
  497.     char        *idFile;
  498.     struct idarg    *idArgs;
  499. {
  500.     struct idname    *idn;
  501.     struct idhead    idh;
  502.     register char    *bitArray;
  503.     char        *entry0;
  504.     register int    i;
  505.     FILE        *idFILE;
  506.     int        cmp, count, size;
  507.     char        *bitsOff;
  508.     struct idname    **newTable, **mergeTable;
  509.     struct idname    **t1, **t2, **tm;
  510.  
  511.     if ((idFILE = fopen(idFile, "r")) == NULL)
  512.         filerr("open", idFile);
  513.     fread((char *) &idh, sizeof(struct idhead), 1, idFILE);
  514.  
  515.     entry0 = malloc(idh.idh_bsiz);
  516.  
  517.     bitsOff = malloc(BitArraySize);
  518.     bzero(bitsOff, BitArraySize);
  519.     for (i = 0; idArgs->ida_next; idArgs = idArgs->ida_next)
  520.         if (idArgs->ida_flags & IDA_SCAN)
  521.             BITSET(bitsOff, idArgs->ida_index);
  522.  
  523.     bitArray = malloc(BitArraySize);
  524.     bzero(bitArray, BitArraySize);
  525.     t2 = newTable = (struct idname **)malloc((idh.idh_namc + 1) * sizeof(struct idname *));
  526. #ifdef UNIX
  527.     fseek(idFILE, idh.idh_namo, 0);
  528. #endif
  529. #ifdef AMIGA    /* paranoia */
  530.     if (fseek(idFILE, idh.idh_namo, 0) == -1)
  531.         filerr("fseek",idFILE);
  532. #endif
  533.     count = 0;
  534.     for (i = 0; i < idh.idh_namc; i++) {
  535.         size = 1 + fgets0(entry0, idh.idh_bsiz, idFILE);
  536.         getsFF(&entry0[size], idFILE);
  537.         vecToBits(bitArray, &entry0[size], idh.idh_vecc);
  538.         bitsclr(bitArray, bitsOff, BitArraySize);
  539.         if (!bitsany(bitArray, BitArraySize))
  540.             continue;
  541.         *t2 = newIdName(ID_STRING(entry0));
  542.         bitsset((*t2)->idn_bitv, bitArray, BitArraySize);
  543.         (*t2)->idn_flags = ID_FLAGS(entry0);
  544.         bzero(bitArray, BitArraySize);
  545.         t2++; count++;
  546.     }
  547.     *t2 = NULL;
  548. #ifdef AMIGA    /* and probably others! */
  549.     if (fclose(idFILE) == -1)
  550.         filerr("close",idFILE);
  551. #endif
  552.  
  553.     t1 = HashTable;
  554.     t2 = newTable;
  555.     tm = mergeTable = (struct idname **)calloc(HashFill + count + 1, sizeof(struct idname *));
  556.     while (*t1 && *t2) {
  557.         cmp = strcmp((*t1)->idn_name, (*t2)->idn_name);
  558.         if (cmp < 0)
  559.             *tm++ = *t1++;
  560.         else if (cmp > 0)
  561.             *tm++ = *t2++;
  562.         else {
  563.             (*t1)->idn_flags |= (*t2)->idn_flags;
  564.             (*t1)->idn_flags &= ~IDN_SOLO;
  565.             bitsset((*t1)->idn_bitv, (*t2)->idn_bitv, BitArraySize);
  566.             *tm++ = *t1;
  567.             t1++, t2++;
  568.         }
  569.     }
  570.     while (*t1)
  571.         *tm++ = *t1++;
  572.     while (*t2)
  573.         *tm++ = *t2++;
  574.     *tm = NULL;
  575.     HashTable = mergeTable;
  576.     HashFill = tm - mergeTable;
  577. }
  578.  
  579. /*
  580.     Cons up a list of idArgs as supplied in a file.
  581. */
  582. void
  583. fileIdArgs(argFILE, idArgsP)
  584.     FILE        *argFILE;
  585.     struct idarg    **idArgsP;
  586. {
  587. /*    int        fileCount; not really used REJ */
  588.     char        buf[BUFSIZ];
  589.     char        *arg;
  590.  
  591. /*     fileCount = 0; see? REJ */
  592.     while (fgets(buf, sizeof(buf), argFILE)) {
  593.         if (strlen(buf) <= 1)
  594.             continue;    /* don't save null args REJ */
  595.         (*idArgsP)->ida_arg = arg = strnsav(buf, strlen(buf)-1);
  596.         if (*arg == '+' || *arg == '-') {
  597.             (*idArgsP)->ida_flags = IDA_ARG;
  598.             (*idArgsP)->ida_index = -1;
  599.         } else {
  600.             (*idArgsP)->ida_flags = IDA_SCAN|IDA_PATH;
  601.             (*idArgsP)->ida_index = postIncr(&PathCount);
  602.             ScanCount++;
  603.         }
  604.         (*idArgsP) = ((*idArgsP)->ida_next = NEW(struct idarg));
  605.     }
  606. }
  607.  
  608. void
  609. initHashTable(pathCount)
  610.     int        pathCount;
  611. {
  612.     if ((HashSize = round2((pathCount << 6) + 511)) > 0x8000)
  613.         HashSize = 0x8000;
  614.     HashMaxLoad = HashSize - (HashSize >> 4);    /* about 94% */
  615.     HashTable = (struct idname **)calloc(HashSize, sizeof(struct idname *));
  616. }
  617.  
  618. /*
  619.     Double the size of the hash table in the
  620.     event of overflow...
  621. */
  622. void
  623. rehash()
  624. {
  625.     long        oldHashSize = HashSize;
  626.     struct idname    **oldHashTable = HashTable;
  627.     register struct idname    **htp;
  628.     register struct idname    **slot;
  629.  
  630.     HashSize *= 2;
  631.     if (Verbose)
  632.         fprintf(stderr, "Rehashing... (doubling size to %ld)\n", HashSize);
  633.     HashMaxLoad = HashSize - (HashSize >> 4);
  634.     HashTable = (struct idname **)calloc(HashSize, sizeof(struct idname *));
  635.  
  636.     HashFill = 0;
  637.     for (htp = oldHashTable; htp < &oldHashTable[oldHashSize]; htp++) {
  638.         if (*htp == NULL)
  639.             continue;
  640.         slot = (struct idname **)hashSearch((*htp)->idn_name, (char *)HashTable, HashSize, sizeof(struct idname *), h1str, h2str, idnHashCmp, &HashProbes);
  641.         if (*slot) {
  642.             fprintf(stderr, "%s: Duplicate hash entry!\n");
  643.             exit(1);
  644.         }
  645.         *slot = *htp;
  646.         HashSearches++;
  647.         HashFill++;
  648.     }
  649.     free(oldHashTable);
  650. }
  651.  
  652. /*
  653.     Round a given number up to the nearest power of 2.
  654. */
  655. int
  656. round2(rough)
  657.     int        rough;
  658. {
  659.     int        round;
  660.  
  661.     round = 1;
  662.     while (rough) {
  663.         round <<= 1;
  664.         rough >>= 1;
  665.     }
  666.     return round;
  667. }
  668.  
  669. /*
  670.     `compar' function for hashSearch()
  671. */
  672. int
  673. idnHashCmp(key, idn)
  674.     char        *key;
  675.     struct idname    **idn;
  676. {
  677.     int        collate;
  678.  
  679.     if (*idn == NULL)
  680.         return 0;
  681.     
  682.     if ((collate = strcmp(key, (*idn)->idn_name)) == 0)
  683.         (*idn)->idn_flags &= ~IDN_SOLO;    /* we found another occurance */
  684.  
  685.     return collate;
  686. }
  687.  
  688. /*
  689.     `compar' function for qsort().
  690. */
  691. int
  692. idnQsortCmp(idn1, idn2)
  693.     struct idname    **idn1;
  694.     struct idname    **idn2;
  695. {
  696.     if (*idn1 == *idn2)
  697.         return 0;
  698.     if (*idn1 == NULL)
  699.         return 1;
  700.     if (*idn2 == NULL)
  701.         return -1;
  702.  
  703.     return strcmp((*idn1)->idn_name, (*idn2)->idn_name);
  704. }
  705.  
  706. /*
  707.     Allocate a new idname struct and fill in the name field.
  708.     We allocate memory in large chunks to avoid frequent
  709.     calls to malloc() which is a major pig.
  710. */
  711. struct idname *
  712. newIdName(name)
  713.     char        *name;
  714. {
  715.     register struct idname    *idn;
  716.     register char    *allocp;
  717.     register int    allocsiz;
  718.     static char    *allocBuf = NULL;
  719.     static char    *allocEnd = NULL;
  720. #define    ALLOCSIZ    (8*1024)
  721.  
  722.     allocsiz = sizeof(struct idname) + strlen(name) + 1 + BitArraySize;
  723.     allocsiz += (sizeof(long) - 1);
  724.     allocsiz &= ~(sizeof(long) - 1);
  725.  
  726.     allocp = allocBuf;
  727.     allocBuf += allocsiz;
  728.     if (allocBuf > allocEnd) {
  729.         allocBuf = malloc(ALLOCSIZ);
  730.         allocEnd = &allocBuf[ALLOCSIZ];
  731.         allocp = allocBuf;
  732.         allocBuf += allocsiz;
  733.     }
  734.  
  735.     idn = (struct idname *)allocp;
  736.     allocp += sizeof(struct idname);
  737.     idn->idn_bitv = allocp;
  738.     for (allocsiz = BitArraySize; allocsiz--; allocp++)
  739.         *allocp = '\0';
  740.     idn->idn_name = strcpy(allocp, name);
  741.  
  742.     return idn;
  743. }
  744.  
  745. int
  746. postIncr(ip)
  747.     int        *ip;
  748. {
  749.     register int    i;
  750.     int        save;
  751.  
  752.     save = *ip;
  753.     i = save + 1;
  754.     if ((i & 0x00ff) == 0x00ff)
  755.         i++;
  756.     if ((i & 0xff00) == 0xff00)    /* This isn't bloody likely */
  757.         i += 0x100;
  758.     *ip = i;
  759.  
  760.     return save;
  761. }
  762.  
  763. /*
  764.     Move all non-NULL table entries to the front of the table.
  765.     return the number of non-NULL elements in the table.
  766. */
  767. int
  768. hashCompress(table, size)
  769.     char        **table;
  770.     int        size;
  771. {
  772.     register char    **front;
  773.     register char    **back;
  774.  
  775.     front = &table[-1];
  776.     back = &table[size];
  777.  
  778.     for (;;) {
  779.         while (*--back == NULL)
  780.             ;
  781.         if (back < front)
  782.             break;
  783.         while (*++front != NULL)
  784.             ;
  785.         if (back < front)
  786.             break;
  787.         *front = *back;
  788.     }
  789.  
  790.     return (back - table + 1);
  791. }
  792.