home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: Product / Product.zip / ISPSRC.ZIP / tree.c < prev    next >
C/C++ Source or Header  |  1992-09-10  |  24KB  |  855 lines
  1. /* -*- Mode:Text -*- */
  2. #ifndef lint
  3. static char Rcs_Id[] =
  4.     "$Id: tree.c,v 1.44 91/08/10 14:09:49 geoff Exp $";
  5. #endif
  6.  
  7. /*
  8.  * tree.c - a hash style dictionary for user's personal words
  9.  *
  10.  * Pace Willisson, 1983
  11.  * Hash support added by Geoff Kuenning, 1987
  12.  *
  13.  * Copyright 1987, 1988, 1989, by Geoff Kuenning, Manhattan Beach, CA
  14.  * Permission for non-profit use is hereby granted.
  15.  * All other rights reserved.
  16.  * See "version.h" for a more complete copyright notice.
  17.  */
  18.  
  19. /*
  20.  * $Log:    tree.c,v $
  21.  * Revision 1.44  91/08/10  14:09:49  geoff
  22.  * Don't issue TREE_C_CANT_UPDATE if the personal dictionary doesn't
  23.  * exist at all.  Sleep for 2 seconds after issuing the message, so that
  24.  * the user has a chance to see it before ispell clears the screen.
  25.  * 
  26.  * Revision 1.43  91/07/27  20:48:39  geoff
  27.  * Major rewrite of the personal-dictionary initialization to support a
  28.  * personal dictionary in the local directory, and to merge it with the
  29.  * one from the home directory if possible.  Fix a compile error and a
  30.  * bug in the REGEX_LOOKUP code.
  31.  * 
  32.  * Revision 1.42  91/07/15  19:27:14  geoff
  33.  * Make tinsert static.  Mention that the argument to treeinsert must be
  34.  * canonical.  Provide the "canonical" parameter to all strtoichar,
  35.  * strtosichar, and casecmp calls.  Make sure the argument to casecmp is
  36.  * canonical.
  37.  * 
  38.  * Revision 1.41  91/07/11  19:52:29  geoff
  39.  * Remove the include of stdio.h, since ispell.h now does this.
  40.  * 
  41.  * Revision 1.40  91/07/05  20:32:00  geoff
  42.  * Fix some more lint complaints.
  43.  * 
  44.  * Revision 1.39  91/07/03  18:21:14  geoff
  45.  * Don't include types.h, dir.h, or param.h, since config.h now does that.
  46.  * 
  47.  * Revision 1.38  91/06/23  22:01:04  geoff
  48.  * On non-USG systems, include sys/dir.h for MAXNAMLEN
  49.  * 
  50.  * Revision 1.37  91/01/24  02:28:12  geoff
  51.  * Modify dictionary-finding code to be more consistent and predictable
  52.  * about where it looks, to create nonexistent dictionaries in $HOME, and
  53.  * to fix a bug that caused private dictionaries in the home to be clobbered.
  54.  * 
  55.  * Revision 1.36  90/12/31  00:59:34  geoff
  56.  * Reformat to follow a consistent convention throughout ispell
  57.  * 
  58.  * Revision 1.35  90/04/26  22:44:31  geoff
  59.  * Add the canonicalize parameter to the call to ichartostr.
  60.  * 
  61.  * Revision 1.34  89/12/27  03:19:02  geoff
  62.  * Move all messages to msgs.h so they can be reconfigured
  63.  * 
  64.  * Revision 1.33  89/07/11  00:25:41  geoff
  65.  * Add REGEX_LOOKUP support and Amiga support, based on that from
  66.  * luis@rice.edu.  Also change the name of the personal hash table to better
  67.  * distinguish it from the main one.
  68.  * 
  69.  * Revision 1.32  89/06/09  15:56:53  geoff
  70.  * Add support for the internal "character" type, ichar_t.
  71.  * 
  72.  * Revision 1.31  89/04/28  01:17:36  geoff
  73.  * Change Header to Id;  nobody cares about my pathnames.
  74.  * 
  75.  * Revision 1.30  89/04/03  01:59:15  geoff
  76.  * Fix a bunch of lint complaints.
  77.  * 
  78.  * Revision 1.29  88/12/26  02:33:53  geoff
  79.  * Add a copyright notice.
  80.  * 
  81.  * Revision 1.28  88/10/20  20:53:27  geoff
  82.  * Add support for getting a different personal dictionary when the -d
  83.  * switch is specified, for multilingual use of ispell.
  84.  * 
  85.  * Revision 1.27  88/04/30  22:16:25  geoff
  86.  * Fix some lint complaints.
  87.  * 
  88.  * Revision 1.26  88/03/27  01:06:03  geoff
  89.  * Fix a whole bunch of problems with the CAPITALIZATION option.
  90.  * 
  91.  * Revision 1.25  88/03/12  02:46:03  geoff
  92.  * Check the return status from makedent, and don't idiotically try to
  93.  * continue if it fails.
  94.  * 
  95.  * Revision 1.24  88/02/20  23:15:06  geoff
  96.  * Major changes to support the new capitalization handling, and to use
  97.  * the new subroutines in the "makedent.c" module.
  98.  * 
  99.  * Revision 1.23  87/09/30  23:32:04  geoff
  100.  * Move some globals to ispell.h.
  101.  * 
  102.  * Revision 1.22  87/09/26  15:53:07  geoff
  103.  * Make buffer sizes be more consistent.
  104.  * 
  105.  * Revision 1.21  87/09/24  23:24:35  geoff
  106.  * When changing a lowercase word to followcase, remember to set the
  107.  * capitalize flags.  (Bart Schaefer).
  108.  * 
  109.  * Revision 1.20  87/09/09  00:20:10  geoff
  110.  * Fix treeoutput() to be nondestructive (Doug Lind, Michael Wester).  It's
  111.  * faster too, since it now uses qsort.  Also fix several bugs in
  112.  * treeinsert:  capitalization information wasn't checked on memory
  113.  * overflow, and duplicate followcase entries weren't detected.
  114.  * 
  115.  * Revision 1.19  87/09/03  19:26:59  geoff
  116.  * Simplify the hash-size table now that we don't read entire dictionaries
  117.  * into the personal-hash tree.
  118.  * 
  119.  * Revision 1.18  87/07/20  23:23:27  geoff
  120.  * Modify to support the new flag format used with language tables.
  121.  * 
  122.  * Revision 1.17  87/06/07  15:04:25  geoff
  123.  * Don't refer to capitalization flags if CAPITALIZE is off (Gary Johnson)
  124.  * 
  125.  * Revision 1.16  87/05/27  23:28:40  geoff
  126.  * Reset hasslash in toutword so every word gets a slash
  127.  * 
  128.  * Revision 1.15  87/05/11  11:50:35  geoff
  129.  * Speed up SORTPERSONAL dramatically by not scanning unkept words repeatedly.
  130.  * 
  131.  * Revision 1.14  87/04/19  22:53:55  geoff
  132.  * Add SORTPERSONAL and capitalization support.
  133.  * 
  134.  * Revision 1.13  87/04/02  12:25:55  geoff
  135.  * Remove the obsolete treeprint() routine.  Put the "can't update
  136.  * personal dict" error message onto stderr, not stdout.
  137.  * 
  138.  * Revision 1.12  87/04/01  15:23:06  geoff
  139.  * Integrate Joe Orost's V7/register changes into the main branch
  140.  * 
  141.  * Revision 1.11  87/03/28  19:33:24  geoff
  142.  * Put the personal dictionary out in compressed (no extra slashes) form
  143.  * 
  144.  * Revision 1.10  87/03/27  17:21:48  geoff
  145.  * Accept (but don't require) new-format dictionaries without extra slashes.
  146.  * However, don't generate them on dumps yet.
  147.  * 
  148.  * Revision 1.9  87/03/22  23:28:03  geoff
  149.  * Integrate Perry Smith's changes into the main branch
  150.  * 
  151.  * Revision 1.8  87/03/12  23:36:54  geoff
  152.  * Fix treeprint, which didn't catch up to the latest changes.  Remove the
  153.  * list-link following in the main hash table in treeoutput, since the
  154.  * entries will eventually be found by the linear search.
  155.  * 
  156.  * Revision 1.7  87/03/10  23:33:13  geoff
  157.  * Add code to deal gracefully with memory allocation failures.  If small
  158.  * allocations fail, put out a message and exit.  If a big hash table allocation
  159.  * fails, put out a message, but continue anyway, just filling the existing
  160.  * table overfull.
  161.  * 
  162.  * Revision 1.6  87/03/08  20:31:27  geoff
  163.  * Improve the hash sizes table to be appropriate to really big dictionaries.
  164.  * Change the personal-dictionary opening code to be more flexible about
  165.  * where it looks, so that relative pathnames will work sensibly.
  166.  * Make lots of changes in the hashing so it works better and faster.
  167.  * 
  168.  * Revision 1.5  87/03/01  00:57:17  geoff
  169.  * Major changes to use a hash table instead of a binary tree, allow
  170.  * user dictionaries to have suffixes, and integrate the user dictionary
  171.  * with the main one.
  172.  * 
  173.  * Revision 1.4  87/02/28  14:58:44  geoff
  174.  * Modify to support suffix flags in the user dictionary.
  175.  * 
  176.  * Revision 1.3  87/02/26  00:25:23  geoff
  177.  * Integrate McQueer's enhancements into the main branch
  178.  * 
  179.  * Revision 1.2  87/01/17  13:12:28  geoff
  180.  * Add RCS ID keywords
  181.  * 
  182.  */
  183.  
  184. #include <ctype.h>
  185. #include <errno.h>
  186. #include "config.h"
  187. #include "ispell.h"
  188. #include "msgs.h"
  189.  
  190. static int        cantexpand = 0;    /* NZ if an expansion fails */
  191. static struct dent *    pershtab;    /* Aux hash table for personal dict */
  192. static int        pershsize = 0;    /* Space available in aux hash table */
  193. static int        hcount = 0;    /* Number of items in hash table */
  194.  
  195. /*
  196.  * Hash table sizes.  Prime is probably a good idea, though in truth I
  197.  * whipped the algorithm up on the spot rather than looking it up, so
  198.  * who knows what's really best?  If we overflow the table, we just
  199.  * use a double-and-add-1 algorithm.
  200.  */
  201. static int goodsizes[] =
  202.     {
  203.     53, 223, 907, 3631
  204.     };
  205.  
  206. static void        treeload ();
  207. void            treeinsert ();
  208. static struct dent *    tinsert ();
  209. struct dent *        treelookup ();
  210.  
  211. static char        personaldict[MAXPATHLEN];
  212. static FILE *        dictf;
  213. static            newwords = 0;
  214.  
  215. extern struct dent *    lookup();
  216. extern void        upcase();
  217.  
  218. void            myfree ();
  219.  
  220. extern char *        index ();
  221. extern char *        calloc ();
  222. extern char *        malloc ();
  223. extern char *        realloc ();
  224. extern void        free ();
  225. extern void        exit ();
  226. extern void        perror ();
  227. extern char *        getenv();
  228. extern char *        strcpy ();
  229. extern void        qsort ();
  230.  
  231. treeinit (p, LibDict)
  232.     char *        p;        /* Value specified in -p switch */
  233.     char *        LibDict;    /* Root of default dict name */
  234.     {
  235.     int            abspath;    /* NZ if p is abs path name */
  236.     char *        h;        /* Home directory name */
  237.     char        seconddict[MAXPATHLEN]; /* Name of secondary dict */
  238.  
  239.     /*
  240.     ** If -p was not specified, try to get a default name from the
  241.     ** configuration file settings, and next from the
  242.     ** environment.  After this point, if p is null, the the value in
  243.     ** personaldict is the only possible name for the personal dictionary.
  244.     ** If p is non-null, then there is a possibility that we should
  245.     ** prepend HOME to get the correct dictionary name.
  246.     */
  247.  
  248. #ifdef OS2      /* try to get config file info  8/24/92 */
  249.     if ( (p == NULL) && (cfpersonaldict[0] != NULL) )
  250.                 p = cfpersonaldict;
  251. #endif /* OS2 */
  252.  
  253.     if (p == NULL)
  254.         p = getenv (PDICTVAR);
  255.     /*
  256.     ** if p exists and begins with '/' we don't really need HOME,
  257.     ** but it's not very likely that HOME isn't set anyway.
  258.     ** The HOME environment variable will not be sought under os/2.
  259.     ** jbh  8/26/92
  260.     */
  261.  
  262. #ifdef OS2
  263.     h=cflibdir;  /* For os/2 home is going to be where ispell.exe is located */
  264. #else 
  265.     if ((h = getenv ("HOME")) == NULL) 
  266. #ifdef AMIGA
  267.         h = LIBDIR;
  268. #else /* AMIGA */
  269.         return;
  270. #endif /* AMIGA */
  271. #endif /* OS2 */
  272.  
  273.     if (p == NULL)
  274.     {
  275.     /*
  276.      * No -p and no PDICTVAR.  We will use LibDict and DEFPAFF to
  277.      * figure out the name of the personal dictionary and where it
  278.      * is.  The rules are as follows:
  279.      *
  280.      * (1) If there is a dictionary in the local directory which
  281.      *     is named after the hash file, this will become
  282.      *     "personaldict", which is where any changes will be saved.
  283.      * (2) If there is also a dictionary in $HOME, we will load
  284.      *     it, regardless of whether the dictionary listed in (1)
  285.      *     exists.  If step (1) failed, this will also become
  286.      *     "personaldict".
  287.      * (3) If both previous steps fail, we will try them again,
  288.      *     using DEFPAFF as the suffix.
  289.      */
  290.     (void) sprintf (personaldict, "%s%s", DEFPDICT, LibDict);
  291.     (void) sprintf (seconddict, "%s/%s%s", h, DEFPDICT, LibDict);
  292.     if ((dictf = fopen (personaldict, "r")) == NULL)
  293.         personaldict[0] = '\0';
  294.     else
  295.         {
  296.         treeload (dictf);
  297.         (void) fclose (dictf);
  298.         }
  299.     if ((dictf = fopen (seconddict, "r")) == NULL)
  300.         seconddict[0] = '\0';
  301.     else
  302.         {
  303.         treeload (dictf);
  304.         (void) fclose (dictf);
  305.         }
  306.     if (personaldict[0] == '\0')
  307.         {
  308.         if (seconddict[0] != '\0')
  309.         (void) strcpy (personaldict, seconddict);
  310.         else
  311.         {
  312.         (void) sprintf (personaldict, "%s%s", DEFPDICT, DEFPAFF);
  313.         (void) sprintf (seconddict, "%s/%s%s", h, DEFPDICT, DEFPAFF);
  314.         if ((dictf = fopen (personaldict, "r")) == NULL)
  315.             (void) strcpy (personaldict, seconddict);
  316.         else
  317.             {
  318.             treeload (dictf);
  319.             (void) fclose (dictf);
  320.             }
  321.         if ((dictf = fopen (seconddict, "r")) != NULL)
  322.             {
  323.             treeload (dictf);
  324.             (void) fclose (dictf);
  325.             }
  326.         }
  327.         }
  328.     }
  329.     else
  330.     {
  331.     /*
  332.     ** Figure out if p is an absolute path name.  Note that beginning
  333.     ** with "./" and "../" is considered an absolute path, since this
  334.     ** still means we can't prepend HOME.
  335.     **
  336.         ** added by jbh 8/15/92: Must also look for drive specifiers
  337.         ** as an indicator of absolute path under os/2. The filename is 
  338.         ** searched for the ":" character, since this indicates an 
  339.         ** absolute path
  340.         */
  341. #ifdef OS2
  342.     abspath = (*p == '/'  ||  strncmp (p, "./", 2) == 0
  343.       ||  strncmp (p, "../", 3) == 0  ||  strchr (p , ':') != NULL );
  344. #else
  345.     abspath = (*p == '/'  ||  strncmp (p, "./", 2) == 0
  346.       ||  strncmp (p, "../", 3) == 0);
  347. #endif /* OS2 */
  348.  
  349.     if (abspath)
  350.         {
  351.         (void) strcpy (personaldict, p);
  352.         if ((dictf = fopen (personaldict, "r")) != NULL)
  353.         {
  354.         treeload (dictf);
  355.         (void) fclose (dictf);
  356.         }
  357.         }
  358.     else
  359.         {
  360.         /*
  361.         ** The user gave us a relative pathname.  We will try it
  362.         ** locally, and if that doesn't work, we'll try the home
  363.         ** directory.  If neither exists, it will be created in
  364.         ** the home directory if words are added.
  365.         */
  366.         (void) strcpy (personaldict, p);
  367.         if ((dictf = fopen (personaldict, "r")) != NULL)
  368.         {
  369.         treeload (dictf);
  370.         (void) fclose (dictf);
  371.         }
  372.         else if (!abspath)
  373.         {
  374.         /* Try the home */
  375.         (void) sprintf (personaldict, "%s/%s", h, p);
  376.         if ((dictf = fopen (personaldict, "r")) != NULL)
  377.             {
  378.             treeload (dictf);
  379.             (void) fclose (dictf);
  380.             }
  381.         }
  382.         /*
  383.          * If dictf is null, we couldn't open the dictionary
  384.          * specified in the -p switch.  Complain.
  385.          */
  386.         if (dictf == NULL)
  387.         {
  388.         (void) fprintf (stderr, CANT_OPEN, p);
  389.         perror ("");
  390.         return;
  391.         }
  392.         }
  393.     }
  394.  
  395.     if (!lflag  &&  !aflag
  396.       &&  access (personaldict, 2) < 0  &&  errno != ENOENT)
  397.     {
  398.     (void) fprintf (stderr, TREE_C_CANT_UPDATE, personaldict);
  399.     (void) sleep (2);
  400.     }
  401.     }
  402.  
  403. static void treeload (dictf)
  404.     register FILE *    dictf;        /* File to load words from */
  405.     {
  406.     char        buf[BUFSIZ];    /* Buffer for reading pers dict */
  407.  
  408.     while (fgets (buf, sizeof buf, dictf) != NULL)
  409.     treeinsert (buf, 1);
  410.     newwords = 0;
  411.     }
  412.  
  413. void treeinsert (word, keep)
  414.     char *        word;    /* Word to insert - must be canonical */
  415.     int            keep;
  416.     {
  417.     register int    i;
  418.     struct dent        wordent;
  419.     register struct dent * dp;
  420.     struct dent *    olddp;
  421. #ifdef CAPITALIZATION
  422.     struct dent *    newdp;
  423. #endif
  424.     struct dent *    oldhtab;
  425.     int            oldhsize;
  426.     ichar_t        nword[INPUTWORDLEN + MAXAFFIXLEN];
  427. #ifdef CAPITALIZATION
  428.     int            isvariant;
  429. #endif
  430.  
  431.     /*
  432.      * Expand hash table when it is MAXPCT % full.
  433.      */
  434.     if (!cantexpand  &&  (hcount * 100) / MAXPCT >= pershsize)
  435.     {
  436.     oldhsize = pershsize;
  437.     oldhtab = pershtab;
  438.     for (i = 0;  i < sizeof goodsizes / sizeof (goodsizes[0]);  i++)
  439.         {
  440.         if (goodsizes[i] > pershsize)
  441.         break;
  442.         }
  443.     if (i >= sizeof goodsizes / sizeof goodsizes[0])
  444.         pershsize += pershsize + 1;
  445.     else
  446.         pershsize = goodsizes[i];
  447.     pershtab =
  448.       (struct dent *) calloc ((unsigned) pershsize, sizeof (struct dent));
  449.     if (pershtab == NULL)
  450.         {
  451.         (void) fprintf (stderr, TREE_C_NO_SPACE);
  452.         /*
  453.          * Try to continue anyway, since our overflow
  454.          * algorithm can handle an overfull (100%+) table,
  455.          * and the malloc very likely failed because we
  456.          * already have such a huge table, so small mallocs
  457.          * for overflow entries will still work.
  458.          */
  459.         if (oldhtab == NULL)
  460.         exit (1);        /* No old table, can't go on */
  461.         (void) fprintf (stderr, TREE_C_TRY_ANYWAY);
  462.         cantexpand = 1;        /* Suppress further messages */
  463.         pershsize = oldhsize;    /* Put things back */
  464.         pershtab = oldhtab;        /* ... */
  465.         newwords = 1;        /* And pretend it worked */
  466.         }
  467.     else
  468.         {
  469.         /*
  470.          * Re-insert old entries into new table
  471.          */
  472.         for (i = 0;  i < oldhsize;  i++)
  473.         {
  474.         dp = &oldhtab[i];
  475.         if (dp->flagfield & USED)
  476.             {
  477. #ifdef CAPITALIZATION
  478.             newdp = tinsert (dp);
  479.             isvariant = (dp->flagfield & MOREVARIANTS);
  480. #else
  481.             (void) tinsert (dp);
  482. #endif
  483.             dp = dp->next;
  484. #ifdef CAPITALIZATION
  485.             while (dp != NULL)
  486.             {
  487.             if (isvariant)
  488.                 {
  489.                 isvariant = dp->flagfield & MOREVARIANTS;
  490.                 olddp = newdp->next;
  491.                 newdp->next = dp;
  492.                 newdp = dp;
  493.                 dp = dp->next;
  494.                 newdp->next = olddp;
  495.                 }
  496.             else
  497.                 {
  498.                 isvariant = dp->flagfield & MOREVARIANTS;
  499.                 newdp = tinsert (dp);
  500.                 olddp = dp;
  501.                 dp = dp->next;
  502.                 free ((char *) olddp);
  503.                 }
  504.             }
  505. #else
  506.             while (dp != NULL)
  507.             {
  508.             (void) tinsert (dp);
  509.             olddp = dp;
  510.             dp = dp->next;
  511.             free ((char *) olddp);
  512.             }
  513. #endif
  514.             }
  515.         }
  516.         if (oldhtab != NULL)
  517.         free ((char *) oldhtab);
  518.         }
  519.     }
  520.  
  521.     /*
  522.     ** We're ready to do the insertion.  Start by creating a sample
  523.     ** entry for the word.
  524.     */
  525.     if (makedent (word, &wordent) < 0)
  526.     return;            /* Word must be too big or something */
  527.     if (keep)
  528.     wordent.flagfield |= KEEP;
  529.     /*
  530.     ** Now see if word or a variant is already in the table.  We use the
  531.     ** capitalized version so we'll find the header, if any.
  532.     **/
  533.     strtoichar (nword, word, 1);
  534.     upcase (nword);
  535.     if ((dp = lookup (nword, 1)) != NULL)
  536.     {
  537.     /* It exists.  Combine caps and set the keep flag. */
  538.     if (combinecaps (dp, &wordent) < 0)
  539.         {
  540.         free (wordent.word);
  541.         return;
  542.         }
  543.     }
  544.     else
  545.     {
  546.     /* It's new. Insert the word. */
  547.     dp = tinsert (&wordent);
  548. #ifdef CAPITALIZATION
  549.     if (captype (dp->flagfield) == FOLLOWCASE)
  550.        (void) addvheader (dp);
  551. #endif
  552.     }
  553.     newwords |= keep;
  554.     }
  555.  
  556. static struct dent * tinsert (proto)
  557.     struct dent *    proto;        /* Prototype entry to copy */
  558.     {
  559.     ichar_t        iword[INPUTWORDLEN + MAXAFFIXLEN];
  560.     register int    hcode;
  561.     register struct dent * hp;        /* Next trial entry in hash table */
  562.     register struct dent * php;        /* Prev. value of hp, for chaining */
  563.  
  564.     strtoichar (iword, proto->word, 1);
  565. #ifndef CAPITALIZATION
  566.     upcase (iword);
  567. #endif
  568.     hcode = hash (iword, pershsize);
  569.     php = NULL;
  570.     hp = &pershtab[hcode];
  571.     if (hp->flagfield & USED)
  572.     {
  573.     while (hp != NULL)
  574.         {
  575.         php = hp;
  576.         hp = hp->next;
  577.         }
  578.     hp = (struct dent *) calloc (1, sizeof (struct dent));
  579.     if (hp == NULL)
  580.         {
  581.         (void) fprintf (stderr, TREE_C_NO_SPACE);
  582.         exit (1);
  583.         }
  584.     }
  585.     *hp = *proto;
  586.     if (php != NULL)
  587.     php->next = hp;
  588.     hp->next = NULL;
  589.     return hp;
  590.     }
  591.  
  592. struct dent * treelookup (word)
  593.     register ichar_t *    word;
  594.     {
  595.     register int    hcode;
  596.     register struct dent * hp;
  597.     char        chword[INPUTWORDLEN + MAXAFFIXLEN];
  598.  
  599.     if (pershsize <= 0)
  600.     return NULL;
  601.     (void) ichartostr (chword, word, 1);
  602.     hcode = hash (word, pershsize);
  603.     hp = &pershtab[hcode];
  604.     while (hp != NULL  &&  (hp->flagfield & USED))
  605.     {
  606.     if (strcmp (chword, hp->word) == 0)
  607.         break;
  608. #ifdef CAPITALIZATION
  609.     while (hp->flagfield & MOREVARIANTS)
  610.         hp = hp->next;
  611. #endif
  612.     hp = hp->next;
  613.     }
  614.     if (hp != NULL  &&  (hp->flagfield & USED))
  615.     return hp;
  616.     else
  617.     return NULL;
  618.     }
  619.  
  620. #if SORTPERSONAL != 0
  621. /* Comparison routine for sorting the personal dictionary with qsort */
  622. pdictcmp (enta, entb)
  623.     struct dent **    enta;
  624.     struct dent **    entb;
  625.     {
  626.  
  627.     /* The parentheses around *enta/*entb below are NECESSARY!
  628.     ** Otherwise the compiler reads it as *(enta->word), or
  629.     ** enta->word[0], which is illegal (but pcc takes it and
  630.     ** produces wrong code).
  631.     **/
  632.     return casecmp ((*enta)->word, (*entb)->word, 1);
  633.     }
  634. #endif
  635.  
  636. treeoutput ()
  637.     {
  638.     register struct dent *    cent;    /* Current entry */
  639.     register struct dent *    lent;    /* Linked entry */
  640. #if SORTPERSONAL != 0
  641.     int                pdictsize; /* Number of entries to write */
  642.     struct dent **        sortlist; /* List of entries to be sorted */
  643.     register struct dent **    sortptr; /* Handy pointer into sortlist */
  644. #endif
  645.     register struct dent *    ehtab;    /* End of pershtab, for fast looping */
  646.  
  647.     if (newwords == 0)
  648.     return;
  649.  
  650.     if ((dictf = fopen (personaldict, "w")) == NULL)
  651.     {
  652.     (void) fprintf (stderr, CANT_CREATE, personaldict);
  653.     return;
  654.     }
  655.  
  656. #if SORTPERSONAL != 0
  657.     /*
  658.     ** If we are going to sort the personal dictionary, we must know
  659.     ** how many items are going to be sorted.
  660.     */
  661.     if (hcount >= SORTPERSONAL)
  662.     sortlist = NULL;
  663.     else
  664.     {
  665.     pdictsize = 0;
  666.     for (cent = pershtab, ehtab = pershtab + pershsize;
  667.       cent < ehtab;
  668.       cent++)
  669.         {
  670.         for (lent = cent;  lent != NULL;  lent = lent->next)
  671.         {
  672.         if ((lent->flagfield & (USED | KEEP)) == (USED | KEEP))
  673.             pdictsize++;
  674. #ifdef CAPITALIZATION
  675.         while (lent->flagfield & MOREVARIANTS)
  676.           lent = lent->next;
  677. #endif
  678.         }
  679.         }
  680.     for (cent = hashtbl, ehtab = hashtbl + hashsize;
  681.       cent < ehtab;
  682.       cent++)
  683.         {
  684.         if ((cent->flagfield & (USED | KEEP)) == (USED | KEEP))
  685.         {
  686.         /*
  687.         ** We only want to count variant headers
  688.         ** and standalone entries.  These happen
  689.         ** to share the characteristics in the
  690.         ** test below.  This test will appear
  691.         ** several more times in this routine.
  692.         */
  693. #ifdef CAPITALIZATION
  694.         if (captype (cent->flagfield) != FOLLOWCASE
  695.           &&  cent->word != NULL)
  696. #endif
  697.             pdictsize++;
  698.         }
  699.         }
  700.     sortlist = (struct dent **) malloc (pdictsize * sizeof (struct dent));
  701.     }
  702.     if (sortlist == NULL)
  703.     {
  704. #endif
  705.     for (cent = pershtab, ehtab = pershtab + pershsize;
  706.       cent < ehtab;
  707.       cent++)
  708.         {
  709.         for (lent = cent;  lent != NULL;  lent = lent->next)
  710.         {
  711.         if ((lent->flagfield & (USED | KEEP)) == (USED | KEEP))
  712.             {
  713.             toutent (dictf, lent, 1);
  714. #ifdef CAPITALIZATION
  715.             while (lent->flagfield & MOREVARIANTS)
  716.             lent = lent->next;
  717. #endif
  718.             }
  719.         }
  720.         }
  721.     for (cent = hashtbl, ehtab = hashtbl + hashsize;
  722.       cent < ehtab;
  723.       cent++)
  724.         {
  725.         if ((cent->flagfield & (USED | KEEP)) == (USED | KEEP))
  726.         {
  727. #ifdef CAPITALIZATION
  728.         if (captype (cent->flagfield) != FOLLOWCASE
  729.           &&  cent->word != NULL)
  730. #endif
  731.             toutent (dictf, cent, 1);
  732.         }
  733.         }
  734. #if SORTPERSONAL != 0
  735.     return;
  736.     }
  737.     /*
  738.     ** Produce dictionary in sorted order.  We used to do this
  739.     ** destructively, but that turns out to fail because in some modes
  740.     ** the dictionary is written more than once.  So we build an
  741.     ** auxiliary pointer table (in sortlist) and sort that.  This
  742.     ** is faster anyway, though it uses more memory. 
  743.     */
  744.     sortptr = sortlist;
  745.     for (cent = pershtab, ehtab = pershtab + pershsize;  cent < ehtab;  cent++)
  746.     {
  747.     for (lent = cent;  lent != NULL;  lent = lent->next)
  748.         {
  749.         if ((lent->flagfield & (USED | KEEP)) == (USED | KEEP))
  750.         {
  751.         *sortptr++ = lent;
  752. #ifdef CAPITALIZATION
  753.         while (lent->flagfield & MOREVARIANTS)
  754.             lent = lent->next;
  755. #endif
  756.         }
  757.         }
  758.     }
  759.     for (cent = hashtbl, ehtab = hashtbl + hashsize;  cent < ehtab;  cent++)
  760.     {
  761.     if ((cent->flagfield & (USED | KEEP)) == (USED | KEEP))
  762.         {
  763. #ifdef CAPITALIZATION
  764.         if (captype (cent->flagfield) != FOLLOWCASE
  765.           &&  cent->word != NULL)
  766. #endif
  767.         *sortptr++ = cent;
  768.         }
  769.     }
  770.     /* Sort the list */
  771.     qsort ((char *) sortlist, (unsigned) pdictsize,
  772.       sizeof (sortlist[0]), pdictcmp);
  773.     /* Write it out */
  774.     for (sortptr = sortlist;  --pdictsize >= 0;  )
  775.     toutent (dictf, *sortptr++, 1);
  776.     free ((char *) sortlist);
  777. #endif
  778.  
  779.     newwords = 0;
  780.  
  781.     (void) fclose (dictf);
  782.     }
  783.  
  784. char * mymalloc (size)
  785.     {
  786.  
  787.     return malloc ((unsigned) size);
  788.     }
  789.  
  790. void myfree (ptr)
  791.     char * ptr;
  792.     {
  793.     if (hashstrings != NULL  &&  ptr >= hashstrings
  794.       &&  ptr <= hashstrings + hashheader.stringsize)
  795.     return;            /* Can't free stuff in hashstrings */
  796.     free (ptr);
  797.     }
  798.  
  799. #ifdef REGEX_LOOKUP
  800.  
  801. /* check the hashed dictionary for words matching the regex. return the */
  802. /* a matching string if found else return NULL */
  803. char * do_regex_lookup (expr, whence)
  804.     char *    expr;    /* regular expression to use in the match   */
  805.     int        whence;    /* 0 = start at the beg with new regx, else */
  806.             /* continue from cur point w/ old regex     */
  807.     {
  808.     static struct dent *    curent;
  809.     static int            curindex;
  810.     static struct dent *    curpersent;
  811.     static int            curpersindex;
  812.     static char *        cmp_expr;
  813.     char            dummy[INPUTWORDLEN + MAXAFFIXLEN];
  814.     ichar_t *            is;
  815.  
  816.     if (whence == 0)
  817.     {
  818.     is = strtosichar (expr, 0);
  819.     upcase (is);
  820.     expr = ichartosstr (is, 1);
  821.         cmp_expr = REGCMP (expr);
  822.         curent = hashtbl;
  823.         curindex = 0;
  824.         curpersent = pershtab;
  825.         curpersindex = 0;
  826.     }
  827.     
  828.     /* search the dictionary until the word is found or the words run out */
  829.     for (  ; curindex < hashsize;  curent++, curindex++)
  830.     {
  831.         if (curent->word != NULL
  832.           &&  REGEX (cmp_expr, curent->word, dummy) != NULL)
  833.         {
  834.         curindex++;
  835.         /* Everybody's gotta write a wierd expression once in a while! */
  836.         return curent++->word;
  837.         }
  838.     }
  839.     /* Try the personal dictionary too */
  840.     for (  ; curpersindex < pershsize;  curpersent++, curpersindex++)
  841.     {
  842.         if ((curpersent->flagfield & USED) != 0
  843.           &  curpersent->word != NULL
  844.           &&  REGEX (cmp_expr, curpersent->word, dummy) != NULL)
  845.         {
  846.         curpersindex++;
  847.         /* Everybody's gotta write a wierd expression once in a while! */
  848.         return curpersent++->word;
  849.         }
  850.     }
  851.     return NULL;
  852.     }
  853.  
  854. #endif /* REGEX_LOOKUP */
  855.