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