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