home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1514 < prev    next >
Encoding:
Internet Message Format  |  1990-12-28  |  40.4 KB
  1. From: gtoal@tharr.UUCP (Graham Toal)
  2. Newsgroups: alt.sources
  3. Subject: Spelling utilities in C (Part 2 of 3)
  4. Message-ID: <808@tharr.UUCP>
  5. Date: 28 Jun 90 07:07:54 GMT
  6.  
  7. #!/bin/sh-----cut here-----cut here-----cut here-----cut here-----
  8. # shar:    Shell Archiver
  9. #    Run the following text with /bin/sh to create:
  10. #    check.c #    correct.c #    dyntrie.c #    init.c #    locate.c #    print.c #    similcmp.c #    soundex.c #    utils.c 
  11. cat - << \SHAR_EOF > check.c
  12. /*
  13.  
  14.     File:    check.c
  15.     Author:  Graham Toal
  16.     Purpose: Check a word using DAWG or TRIE.
  17.     Functions exported:  dawg_check, pack_check
  18.     Internal function:   dawg_ck, pack_ck
  19.  
  20. Description:
  21.  
  22.     call as:     dawg_check(dawg, "word")
  23.                  pack_check(trie, "word")
  24.  
  25.    Simple spelling-check. Unfortunately the two interfaces for
  26.    DAWGs and TRIEs are different, and even DAWG stuff differs from
  27.    program to program.  The problem is primarily in how to spot
  28.    the end of a search; at the moment it is done when a particular
  29.    pointer points to the root. Unfortunately we enter the data
  30.    structure either at root+1 or at some arbitrary point, so this
  31.    scheme means passing in two pointers.  The next idea is to check
  32.    that the *data* pointed to by the terminating pointer is 0; this
  33.    would be OK but I was hoping to leave the initial word in the
  34.    dawg free for expansion... (dawg contains [0, Node1..NodeN])
  35.  
  36.    *best* idea would be to terminate on *INDEX* being 0.  This is
  37.    probably also simplest & I'll code it up properly when I'm awake...
  38.  
  39. */
  40.  
  41. static int
  42. #ifdef PROTOTYPES
  43. dawg_ck(NODE PCCRAP *dict, NODE PCCRAP *edge, char *word)
  44. #else
  45. dawg_ck(dict, edge, word)
  46. NODE PCCRAP *dict;
  47. NODE PCCRAP *edge;
  48. char *word;
  49. #endif
  50. {
  51.   if (edge == dict) return(0!=0);
  52.   for (;;) {
  53.     if (*word == (((*edge >> V_LETTER) & M_LETTER))) {
  54.       if (*++word == '\0') {
  55.         return((*edge & M_END_OF_WORD) != 0);
  56.       } else {
  57.         if ((edge = dict+(*edge & M_NODE_POINTER)) == dict) break;
  58.         continue;
  59.       }
  60.     }
  61.     if (((*edge++) & M_END_OF_NODE) != 0) break;
  62.   }
  63.   return(0!=0);
  64. }
  65.  
  66. int
  67. #ifdef PROTOTYPES
  68. dawg_check(NODE PCCRAP *dict, char *word)
  69. #else
  70. dawg_check(dict, word)
  71. NODE PCCRAP *dict;
  72. char *word;
  73. #endif
  74. {
  75.   return(dawg_ck(dict, dict+ROOT_NODE, word));
  76. }
  77.  
  78. static int
  79. #ifdef PROTOTYPES
  80. pack_ck(NODE PCCRAP *ptrie, INDEX p, char *s)
  81. #else
  82. pack_ck(ptrie, p, s)
  83. NODE PCCRAP *ptrie;
  84. INDEX p;
  85. char *s;
  86. #endif
  87. {
  88. /* Note: node is passed in as a parameter so that it is in a register -
  89.    otherwise it would take an extra instruction every time it was accessed.
  90.    We trust the compiler to allocate register variables most efficiently --
  91.    when people tinker, it might improve one machine but ruin another...
  92.  */
  93.  
  94. #define next_letter(s) \
  95.   p = ptrie[p + *s]; \
  96.   if (((p >> V_LETTER) & M_LETTER) != *s++) return(0!=0); \
  97.   if (*s == '\0') return((p >> V_END_OF_NODE) != 0); \
  98.   if ((p &= M_NODE_POINTER) == 0) return(0!=0)
  99.  
  100.   /* Depending on whether your machine has a cache or not, and whether
  101.      it optimises pipeline fetches, you should decrease or increase the
  102.      number of macro instantiations in the loop below appropriately */
  103.  
  104.   for (;;) {
  105.     next_letter(s);    next_letter(s);    next_letter(s);    next_letter(s);
  106.   }
  107. }
  108.  
  109. int
  110. #ifdef PROTOTYPES
  111. pack_check(NODE PCCRAP *ptrie, char *s)
  112. #else
  113. pack_check(ptrie, s)
  114. NODE PCCRAP *ptrie;
  115. char *s;
  116. #endif
  117. {
  118.   return(pack_ck(ptrie, 1L, s));
  119. }
  120. SHAR_EOF
  121. cat - << \SHAR_EOF > correct.c
  122. /*
  123.  
  124.     File:    correct.c
  125.     Author:  Graham Toal
  126.     Purpose: Correct a word using Soudex and similcmp on DAWG.
  127.     Functions exported:  dawg_correct
  128.     Internal functions:  reccmp, walk_rest_dawg, walk_dawg
  129.  
  130. Description:
  131.    Reduce word to rough phonetic representation.
  132.    Reduce all words in dawg to same form.  Compare.  This
  133.    results in a large list of plausible (HA!) candidates.
  134.  
  135.    Then apply 'similcmp' which returns a distance metric representing
  136.    closeness of two words.  Sort by this metric, and return N best
  137.    matches.  If one stands out above others, return it alone.
  138.  
  139.    I'm working on a *much better* algorithm, but this will do
  140.    for prototyping the interface.
  141.  
  142.    Final version of this will have callbacks to handle corrected
  143.    words as they are produced.
  144.  
  145. */
  146.  
  147. #include "soundex.c"
  148. #include "similcmp.c"
  149.  
  150. typedef struct {
  151.   char *possible;
  152.   int score;
  153. } rec;
  154.  
  155.  
  156. /* Numbers of parameters exploded during process of removing global state :( */
  157.  
  158. static void
  159. #ifdef PROTOTYPES
  160. walk_rest_dawg(NODE PCCRAP *dawg, INDEX node, int len,
  161.   char *word, char *original, char *target,
  162.   rec *ans, int *nextfreep)
  163. #else
  164. walk_rest_dawg(dawg, node, len, word, original, target, ans, nextfreep)
  165.   NODE PCCRAP *dawg;
  166.   INDEX node;
  167.   int len;
  168.   char *word;
  169.   char *original;
  170.   char *target;
  171.   rec *ans;
  172.   int *nextfreep;
  173. #endif
  174. #define nextfree (*nextfreep)
  175. {
  176.   NODE PCCRAP *edge;
  177.   long c;
  178.  
  179.     for (edge = (NODE PCCRAP *)&dawg[node]; ;edge++) {
  180.     c = *edge;            /* Avoid MS C compiler bug :-( */
  181.     c = c >> V_LETTER;
  182.     c = c & M_LETTER;
  183.     word[len] = (char)c;
  184.     if ((*edge & M_END_OF_WORD) != 0) {
  185.       word[len+1] = 0;
  186.       if (strcmp(soundex(word), target) == 0) {
  187.         ans[nextfree].possible = (char *)Malloc(len+1, 1);
  188.         if (ans[nextfree].possible == NULL) {
  189.           fprintf(stderr,"I\'ve no idea - it could be anything...\n");
  190.           exit(0);
  191.         }
  192.         strcpy(ans[nextfree].possible, word);
  193.         ans[nextfree].score = simil(word, original);
  194.         if (nextfree < 511) nextfree++;
  195.       }
  196.     }
  197.     c = *edge & M_NODE_POINTER;
  198.     if (c != 0) {
  199.       walk_rest_dawg(dawg, c, len+1, word, original, target, ans, nextfreep);
  200.     }
  201.     if ((*edge & M_END_OF_NODE) != 0) break; /* End of node */
  202.   }
  203. #undef nextfree
  204. }
  205.  
  206.  
  207. static void
  208. #ifdef PROTOTYPES
  209. walk_dawg(
  210.   NODE PCCRAP *dawg, INDEX node, int len,
  211.   char *original, char *target,
  212.   char targets, char *word,
  213.   rec *ans, int *nextfreep)
  214. #else
  215. walk_dawg(dawg, node, len, original, target, targets, word, ans, nextfreep)
  216.   NODE PCCRAP *dawg;
  217.   INDEX node;
  218.   int len;
  219.   char *original;
  220.   char *target;
  221.   char targets;
  222.   char *word;
  223.   rec *ans;
  224.   int *nextfreep;
  225. #endif
  226. #define nextfree (*nextfreep)
  227. {
  228.   NODE PCCRAP *edge;
  229.   long c;
  230.  
  231.   edge = (NODE PCCRAP *)&dawg[node];
  232.   /* Only search trie starting with initial letter */
  233.   for (;;) {
  234.     c = *edge;            /* Avoid MS C compiler bug :-( */
  235.     c = c >> V_LETTER;
  236.     c = c & M_LETTER;
  237.     word[len] = (char)c;
  238.     if (c == targets) {
  239.       c = *edge & M_NODE_POINTER;
  240.       walk_rest_dawg(dawg, c, len+1, word, original, target, ans, nextfreep);
  241.       return;
  242.     }
  243.     edge++;
  244.   }
  245. #undef nextfree
  246. }
  247.  
  248. static int
  249. #ifdef PROTOTYPES
  250. reccmp(const void *a, const void *b)
  251. #else
  252. reccmp(a, b)
  253.   void *a;
  254.   void *b;
  255. #endif
  256. {
  257.   return(((rec *)b)->score - ((rec *)a)->score);
  258. }
  259.  
  260.  
  261. int
  262. #ifdef PROTOYPES
  263. dawg_correct(NODE PCCRAP *dawg, char *original)
  264. #else
  265. dawg_correct(dawg, original)
  266. NODE PCCRAP *dawg;
  267. char *original;
  268. #endif
  269. {
  270. char word[81];
  271. char target[256];
  272. static rec ans[256];
  273.   /* static because brain-dead MSC can't hack a big stack :-( */
  274. int targets;
  275. int nextfree = 0;
  276. int i, prev=0;
  277.  
  278.   targets = original[0];
  279.   strcpy(target, soundex(original));
  280.   walk_dawg(
  281.     dawg, (INDEX)ROOT_NODE, 0, original, target, targets, word, ans, &nextfree);
  282.   if (nextfree == 0) return(FALSE);
  283.   qsort(ans, (size_t)nextfree, sizeof(rec), /*&*/reccmp);
  284.   for (i = 0; i < nextfree; i++) {
  285.     if (((prev*100) / (ans[i].score)) > 120) break;
  286.     fprintf(stdout, "%s (%d)\n", ans[i].possible, ans[i].score);
  287.     if (ans[i].score >= 100) break;
  288.     if (i == 5) break;
  289.     prev = ans[i].score;
  290.   }
  291.   return(TRUE);
  292. }
  293. SHAR_EOF
  294. cat - << \SHAR_EOF > dyntrie.c
  295. /* The #define is to repair mangling by BITNET mailers */
  296. #define NOT ~
  297.               /* This should be Tilde (twiddle) -- C unary Not   */
  298. /*
  299.  
  300.     File:    dyntrie.c
  301.     Author:  Graham Toal
  302.     Purpose: Check a word using DAWG or TRIE.
  303.     Functions exported:  trie_new, trie_add, trie_dump
  304.     Internal functions:  insert_simple recurse_add
  305.  
  306. Description:
  307.  
  308.    Builds DAWG-compatible trie in store, incrementally; words do not
  309.    have to be presented in order.  (Note it is NOT a 'packed-trie';
  310.    in our scheme it is closer to a dawg - but without the tail-compression
  311.    precomputed dawgs have).
  312.  
  313.    Any tries built using this should be used by check_dawg, print_dawg etc.
  314.  
  315.    Has rather nice property of only claiming enough memory for the
  316.    job; dynamically moves the data structure when it fills!
  317.  
  318. */
  319.  
  320.   /* To avoid global state, I'm putting these useful bits of info
  321.      in the two words before the dawg itself; I *HOPE* that all systems
  322.      allow negative indexing off arrays; I'm not at all sure they do
  323.      though.  However since I moved the base of the dict up by adding
  324.      2 to it, I *should* be able to get the old address by by subtracting
  325.      2 from it, so I'm using the first pair of macros below, not the
  326.      more intuitive second pair.
  327.        I should really do this for ordinary dawgs & tries too.  Indeed
  328.      I should *really* implement the dictlib.h interface, but thats a
  329.      month or two off.  Also I'ld like some feedback first.
  330.    */
  331.  
  332. #define EXTRAS 2
  333. #define MAX_ENTRIES(dawg) (*(dawg-2))          /* Safe way of aliasing */
  334. #define NEXT_FREE(dawg) (*(dawg-1))
  335.  
  336.  
  337.   /* #define MAX_ENTRIES(dawg) dawg[-2] */     /* 'Obvious' alias      */
  338.   /* #define NEXT_FREE(dawg) dawg[-1] */       /* may be buggy         */
  339.  
  340. #define EMPTY 0
  341. #define INIT_MAX_ENTRIES 512
  342.  
  343. /* Slop is so that we don't need to be continually checking nextfree
  344.    as being close to max_entries */
  345. #define SLOP 12
  346.  
  347. /* A debugging macro which rangechecks arrays -- happens when
  348.    utils.c is included with RCHECK defined. Otherwise no overhead. */
  349. #define DICT(idx) dict[RANGECHECK(idx, MAX_ENTRIES(dict))]
  350.  
  351.  
  352.   /*
  353.       This quick hack job has special-case code in each function
  354.       for the root node-set.  Its rather tacky; I could clean it
  355.       up and make the root node like all other nodes, but why
  356.       bother; this is only test code anyway...
  357.    */
  358.  
  359.  
  360.  
  361. static INDEX
  362. #ifdef PROTOTYPES
  363. insert_simple(NODE PCCRAP **dictp, char *word)
  364. #else
  365. insert_simple(dictp, word)
  366. NODE PCCRAP **dictp;
  367. char *word;
  368. #endif
  369. #define dict (*dictp)
  370. {
  371. NODE bugfix;
  372. INDEX i; NODE n; int c;
  373.  
  374.   if (NEXT_FREE(dict) >= MAX_ENTRIES(dict)-SLOP) {
  375.     NODE PCCRAP *moved;
  376.     moved = MALLOC((SIZE_T)MAX_ENTRIES(dict)*2+EXTRAS, sizeof(NODE));
  377.     if (moved != NULL) {
  378.       moved += EXTRAS;
  379.       MAX_ENTRIES(moved) = MAX_ENTRIES(dict);
  380.       NEXT_FREE(moved) = NEXT_FREE(dict);
  381.       /* Should use realloc but appears to be buggy :-( */
  382.       for (i = MAX_ENTRIES(dict); i < MAX_ENTRIES(dict)*2; i++) {
  383.         moved[i] = EMPTY;
  384.       }
  385.       for (i = 0; i < MAX_ENTRIES(dict); i++) moved[i] = DICT(i);
  386.       dict -= EXTRAS;
  387.       FREE(dict);
  388.       dict = moved; MAX_ENTRIES(dict) *= 2;
  389.     } else {
  390.       fprintf(stderr, "Can\'t add any more words again\n");
  391.     }
  392.   }
  393.  
  394.   c = (*word++)&255;
  395.   if (c == '\0') return(TERMINAL_NODE);
  396.   i = NEXT_FREE(dict)++;
  397.   bugfix = insert_simple(&dict, word);
  398.   n = ((NODE)c << (NODE)V_LETTER) | M_END_OF_NODE | bugfix;
  399.   DICT(i) = n; if (*word == '\0') DICT(i) |= M_END_OF_WORD;
  400.   return(i);
  401. #undef dict
  402. }
  403.  
  404. static void
  405. #ifdef PROTOTYPES
  406. recurse_add(NODE PCCRAP **dictp, INDEX base, char *word)
  407. #else
  408. recurse_add(dictp, base, word)
  409. NODE PCCRAP **dictp;
  410. INDEX base;
  411. char *word;
  412. #endif
  413. #define dict (*dictp)
  414. {
  415. NODE bugfix;
  416. INDEX i = base, newbase;
  417. NODE unpicked[MAX_CHARS], n;
  418. int c, ch;
  419. int gap, nextslot = 0, j;
  420.   /* First see if first char is already in trie */
  421.   ch = (*word++)&255;
  422.   for (;;) {
  423.     c = (int)(((dict[i] >> V_LETTER) & M_LETTER)&255);
  424.     if (ch == c) {
  425.       newbase = dict[i]&M_NODE_POINTER;
  426.       if (newbase == 0) {
  427.         /* have abc (this is c), adding (abc)defg */
  428.         dict[i] &= (NOT M_NODE_POINTER);
  429.         bugfix = insert_simple(&dict, word);
  430.         dict[i] |= bugfix;
  431.       } else {
  432.         if (*word == '\0') {
  433.           dict[i] |= M_END_OF_WORD;
  434.         } else {
  435.           recurse_add(dictp, newbase, word);
  436.         }
  437.       }
  438.       return;
  439.     }
  440.     if ((dict[i]&M_END_OF_NODE) != 0) break;
  441.     i++;
  442.   }
  443.  
  444.   /* unpick base */
  445.   for (nextslot = 0; nextslot < MAX_CHARS; nextslot++) {
  446.     unpicked[nextslot] = EMPTY;
  447.   }
  448.   nextslot = 0;
  449.  
  450.   i = base; j = 0;
  451.   for (;;) {
  452.     if ((j == 0) && (((dict[i] >> V_LETTER) & M_LETTER) > ch)) {
  453.       j = 1; newbase = nextslot++;
  454.     }
  455.     n = dict[i]; dict[i] = EMPTY; i++;
  456.     unpicked[nextslot++] = n & (NOT M_END_OF_NODE);
  457.     if ((n & M_END_OF_NODE) != 0) break;
  458.   }
  459.   if (j == 0) newbase = nextslot++; /* Was it last alphabetically? */
  460.   /* add this char to the node */
  461.   if (*word == '\0') {
  462.     unpicked[newbase] =
  463.       ((NODE)ch << (NODE)V_LETTER) | TERMINAL_NODE | M_END_OF_WORD;
  464.   } else {
  465.     /* and insert the rest of the
  466.        string with insert_simple */
  467.     bugfix = insert_simple(&dict, word);
  468.     unpicked[newbase] =
  469.       ((NODE)ch << (NODE)V_LETTER) | bugfix;
  470.       /* The insert_simple call has to come after above loop, because
  471.          of freeing slots... */
  472.   }
  473.   unpicked[nextslot-1] |= M_END_OF_NODE;
  474.  
  475.   /* scan for suitably-sized gap */
  476.   /* MAX_CHARS+1 should be first 'real' node base (0, 1..MAX_CHARS reserved) */
  477.  
  478.   /*
  479.      The particular application this is wanted for doesn't have a large
  480.      number of words to be added dynamically, so the BFI code below which
  481.      finds free holes in the trie space works fine.  However if some bright
  482.      spark cares to keep a freelist *in the holes* then this program
  483.      effectively implements a linear-time sorting algorithm.
  484.  
  485.      (I know it's not *really*, but think about it before jumping
  486.      down my throat; the N^2 case is very statistically unlikely)
  487.    */
  488.  
  489.   for (i = (INDEX)MAX_CHARS+1; i < MAX_ENTRIES(dict)-nextslot-SLOP; i++) {
  490.     /*
  491.         Even without the freelist, the sneaky hack in pack.c for
  492.         noting earliest bunch of free holes might well make a
  493.         significant difference... (It was a lowest_search_start
  494.         variable and used a bit of hysteresis)
  495.      */
  496.     gap = TRUE;
  497.     for (j = 0; j < nextslot; j++) {
  498.       if (dict[i+j] != EMPTY) {
  499.         gap = FALSE;
  500.         break;
  501.       }
  502.     }
  503.     if (gap) break;
  504.   }
  505.   if (!gap) {
  506.     NODE PCCRAP *moved;
  507.     moved = MALLOC((SIZE_T)MAX_ENTRIES(dict)*2+EXTRAS, sizeof(NODE));
  508.     if (moved != NULL) {
  509.       moved += EXTRAS;
  510.       MAX_ENTRIES(moved) = MAX_ENTRIES(dict);
  511.       NEXT_FREE(moved) = NEXT_FREE(dict);
  512.       /* Should use realloc but appears to be buggy :-( */
  513.       for (i = MAX_ENTRIES(dict);
  514.            i < MAX_ENTRIES(dict)*2; i++) moved[i] = EMPTY;
  515.       for (i = 0; i < MAX_ENTRIES(dict); i++) moved[i] = DICT(i);
  516.       dict -= EXTRAS;
  517.       FREE(dict);
  518.       dict = moved; /* If your compiler has aliasing bugs they may hit here. */
  519.       MAX_ENTRIES(dict) *= 2;
  520.       /* scan for suitably-sized gap */
  521.       for (i = ((MAX_ENTRIES(dict)/2)-(MAX_CHARS+1));
  522.            i < MAX_ENTRIES(dict)-nextslot; i++) {
  523.         gap = TRUE;
  524.         for (j = 0; j < nextslot; j++) {
  525.           if (dict[i+j] != EMPTY) {
  526.             gap = FALSE;
  527.             break;
  528.           }
  529.         }
  530.         if (gap) break;
  531.       }
  532.     }
  533.     if (!gap) {
  534.       fprintf(stderr, "Can\'t add any more words\n");
  535.       return;
  536.     }
  537.   }
  538.   newbase = i;
  539.   /* reinsert */
  540.   for (j = 0; j < nextslot; j++) {
  541.     dict[newbase+j] = unpicked[j];
  542.   }
  543.   if (newbase+nextslot-1 >= NEXT_FREE(dict)) NEXT_FREE(dict) = newbase+nextslot;
  544.   /* update pointer to the base of this node */
  545.   for (i = 0; i < MAX_ENTRIES(dict); i++) {
  546.     if ((dict[i] & M_NODE_POINTER) == base) {
  547.       dict[i] &= (NOT M_NODE_POINTER);
  548.       dict[i] |= newbase;
  549.       break;            /* (should only be one since trie, not dawg) */
  550.     }
  551.   }
  552. #undef dict
  553. }
  554.  
  555. void
  556. #ifdef PROTOTYPES
  557. trie_add(NODE PCCRAP **dictp, char *word)
  558. #else
  559. trie_add(dictp, word)
  560. NODE PCCRAP **dictp;
  561. char *word;
  562. #endif
  563. #define dict (*dictp)
  564. {
  565. INDEX next;
  566. INDEX bugfix;
  567. int c;
  568.   /* Root node is pre-reserved MAX_CHARS entries */
  569.   c = (*word++)&255; /* bugfix - remember chars can be signed :-( */
  570.   if (DICT((INDEX)ROOT_NODE+c) == EMPTY) {
  571.     /* I'm allowing the root node to be sparse for speed; it *should*
  572.        be dense like any other node.  May change this later */
  573.     if (*word == '\0') {
  574.       DICT((INDEX)ROOT_NODE+c) =
  575.         ((NODE)c << (NODE)V_LETTER) | M_END_OF_WORD;
  576.     } else {
  577.       bugfix = insert_simple(&dict, word);
  578.       DICT((INDEX)ROOT_NODE+c) =
  579.         ((NODE)c << (NODE)V_LETTER) | bugfix;
  580.     }
  581.   } else {
  582.     if (*word == '\0') {
  583.       DICT((INDEX)ROOT_NODE+c) |= M_END_OF_WORD;
  584.     } else {
  585.       next = DICT((INDEX)ROOT_NODE+c) & M_NODE_POINTER;
  586.       if (next == 0) {
  587.         /* have 'a', adding 'abcd' */
  588.         /* (Should really check the letter for safety...) */
  589.         bugfix = insert_simple(&dict, word);
  590.         DICT((INDEX)ROOT_NODE+c) = ((NODE)c << (NODE)V_LETTER)
  591.           | bugfix | M_END_OF_WORD;
  592.       } else {
  593.         recurse_add(dictp, next, word);
  594.       }
  595.     }
  596.   }
  597. #undef dict
  598. }
  599.  
  600. int
  601. #ifdef PROTOTYPES
  602. trie_new(NODE PCCRAP **dawgp)
  603. #else
  604. trie_new(dawgp)
  605. NODE PCCRAP **dawgp;
  606. #endif
  607. #define dawg (*dawgp)
  608. {
  609. INDEX i;
  610.  
  611.   dawg = MALLOC(INIT_MAX_ENTRIES+EXTRAS, sizeof(NODE));
  612.   dawg += EXTRAS;
  613.  
  614.   MAX_ENTRIES(dawg) = INIT_MAX_ENTRIES; NEXT_FREE(dawg) = MAX_CHARS+1;
  615.  
  616.   dawg[0] = 0;
  617.   for (i = 1; i <= MAX_CHARS; i++) dawg[i] = 0;
  618.   dawg[MAX_CHARS] |= M_END_OF_NODE;
  619.   /* 0 base, MAX_CHARS chars */
  620.  
  621.   return(TRUE);
  622. #undef dawg
  623. }
  624.  
  625. int
  626. #ifdef PROTOTYPES
  627. trie_dump(NODE PCCRAP *dawg, char *filename)
  628. #else
  629. trie_dump(dawg, filename)
  630. NODE PCCRAP *dawg;
  631. char *filename;
  632. #endif
  633. {
  634. INDEX cnt, max;
  635. FILE *dumper;
  636.   max = NEXT_FREE(dawg)*sizeof(NODE);
  637.     /* I *knew* the next_free variable would come in handy :-) */
  638.   dumper = fopen(filename, WRITE_BIN);
  639.   if (dumper == NULL) {
  640.     fprintf(stderr, "Failed to dump trie on file \'%s\'\n", filename);
  641.     return(FALSE);
  642.   }
  643.   putword(max, dumper);
  644.   if ((cnt = putwords(dawg, max, dumper)) != max) {
  645.     fprintf(stderr, "Failed to dump: %ld bytes written instead of %ld\n",
  646.       cnt, max);
  647.     return(FALSE);
  648.   }
  649.   fclose(dumper);
  650.   return(TRUE);
  651. }
  652.  
  653. #undef MAX_ENTRIES
  654. #undef NEXT_FREE
  655. #undef DICT
  656. #undef SLOP
  657. SHAR_EOF
  658. cat - << \SHAR_EOF > init.c
  659. /*
  660.  
  661.     File:    init.c
  662.     Authors: Richard Hooker, Graham Toal
  663.     Purpose: Loading of dictionary for spelling checker.
  664.     Functions exported:  dawg_init, pack_init
  665.     Internal functions:  spell_init
  666.  
  667. Description:
  668.  
  669. The address of a dictionary (either a PACKed dict or a DAWG) is set up by
  670. this procedure.  This gives us the option of connecting the dict in read-only
  671. (or copy-on-write) virtual memory.  On non-VM machines, we simply allocate a
  672. large buffer into which the relevant part of the dictionary is loaded.
  673.  
  674. The magic number is used to check the dict type, *and* the machine byte-sex.
  675. If the sex is reversed, even a VM system has to load the data into writable
  676. memory (so that it can reverse it).
  677.  
  678. */
  679.  
  680. /*######################### INTERNAL FUNCTIONS #########################*/
  681.  
  682.  
  683. static int
  684. #ifdef PROTOTYPES
  685. spell_init(char *filename, NODE PCCRAP **dictp,
  686.   char *DEFAULT_DICT, long magic_number, INDEX *nedges)
  687. #else
  688. spell_init(filename, dictp, DEFAULT_DICT, magic_number, nedges)
  689. char *filename;
  690. NODE PCCRAP **dictp;
  691. char *DEFAULT_DICT;
  692. long magic_number;
  693. INDEX *nedges;
  694. #endif
  695. #define dict (*dictp)
  696. {
  697. FILE *fp; INDEX count;
  698.  
  699.   /*  init_dict("") gets default */
  700.   if (*filename == '\0') filename = DEFAULT_DICT;
  701.  
  702.   /* Open the file and find out the size of the dict -- which
  703.      is stored in the first word.  Later I'll change the dict format
  704.      to have a header, and the header will have to be skipped by
  705.      this module. */
  706.  
  707.   if ((fp = fopen(filename, "rb")) == NULL) {
  708.     fprintf (stderr, "Can\'t open file \"%s\"\n", filename);
  709.     return(FALSE);
  710.   }
  711.   *nedges = getword(fp);
  712. #ifdef DEBUG
  713. fprintf(stderr, "dawg contains %8lx edges\n", *nedges);
  714. #endif
  715.   /* Allocate precisely enough memory for all edges + 0 at root node. */
  716.   if ((dict = MALLOC((SIZE_T)((*nedges)+1), sizeof(NODE PCCRAP *))) == 0) {
  717.     fprintf (stderr, "Can\'t allocate space for dictionary\n");
  718.     return(FALSE);
  719.   }
  720.  
  721.   dict[0] = 0; /* Root node set to 0; terminal nodes point to 0. */
  722.  
  723.   /* Load in the dictionary.  Routine 'getwords' should be efficient */
  724.   count = getwords(&dict[1], (long)(4*(*nedges)), fp);
  725.   if (count != 4*(*nedges)) {
  726.     fprintf(stderr,
  727.       "Failed to read dictionary %s - wanted %ld bytes, got %ld\n",
  728.       filename, 4*(*nedges), count);
  729.     return(FALSE);
  730.   }
  731.   fclose(fp);
  732.  
  733.   return(TRUE);
  734. #undef dict
  735. }
  736.  
  737. /*####################### EXPORTED FUNCTIONS #########################*/
  738.  
  739. int
  740. #ifdef PROTOTYPES
  741. dawg_init(char *filename, NODE PCCRAP **dawgp, INDEX *nedges)
  742. #else
  743. dawg_init(filename, dawgp, nedges)
  744. char *filename;
  745. NODE PCCRAP **dawgp;
  746. INDEX *nedges;
  747. #endif
  748. {
  749.   return(spell_init(filename, dawgp, DEFAULT_DAWG, DAWG_MAGIC, nedges));
  750. }
  751.  
  752. int
  753. #ifdef PROTOTYPES
  754. pack_init(char *filename, NODE PCCRAP **packp, INDEX *nedges)
  755. #else
  756. pack_init(filename, packp, nedges)
  757. char *filename;
  758. NODE PCCRAP **packp;
  759. INDEX *nedges;
  760. #endif
  761. {
  762.   return(spell_init(filename, packp, DEFAULT_PACK, PACK_MAGIC, nedges));
  763. }
  764.  
  765. SHAR_EOF
  766. cat - << \SHAR_EOF > locate.c
  767. /*
  768.  
  769.     File:    locate.c
  770.     Author:  Graham Toal
  771.     Purpose: Find all words beginning with particular prefix.
  772.     Functions exported:  locate_prefix
  773.  
  774. Description:
  775.    Searches as in spell-check for prefix in dict, but doesn't
  776.    fail if word doesn't terminate at that point.  It returns
  777.    an index into the dict which can be used with print_dawg_prefix
  778.    to display all the words found.  However it is more useful
  779.    than that; text-analysis programs can check that a word matches
  780.    "root*", for instance, when doing stylistic analysis etc.
  781.  
  782. */
  783.  
  784. INDEX
  785. #ifdef PROTOTYPES
  786. dawg_locate_prefix(NODE PCCRAP *dawg, char *word, INDEX edge)
  787. #else
  788. dawg_locate_prefix(dawg, word, edge)
  789. NODE PCCRAP *dawg;
  790. char *word;
  791. INDEX edge;
  792. #endif
  793. {
  794.   for (;;) {
  795.     if (*word == (((dawg[edge] >> V_LETTER) & M_LETTER))) {
  796.       if (*++word == '\0') {
  797.         return(dawg[edge]&M_NODE_POINTER);
  798.       } else {
  799.         if ((edge = (dawg[edge] & M_NODE_POINTER)) == ROOT_NODE) break;
  800.         continue;
  801.       }
  802.     }
  803.     if (((dawg[edge++]) & M_END_OF_NODE) != 0) break;
  804.   }
  805.   /* What to do when none found? -- fail-safe, or some error code...? */
  806.   return(ROOT_NODE);
  807. }
  808. SHAR_EOF
  809. cat - << \SHAR_EOF > print.c
  810. /*
  811.  
  812.     File:    print.c
  813.     Author:  Graham Toal
  814.     Purpose: Print a packed trie to stderr.
  815.     Functions exported:  dawg_print, pack_print, dawg_print_prefix
  816.     Internal functions:  pack_pr dawg_pr dawg_pr_prefix
  817.  
  818. Description:
  819.   Pre-order traverse of packed TRIE or DAWG.  Will be modified
  820.   soon to take output file as parameter.  Then sometime after that
  821.   to callback with each string at it is generated.  Meanwhile,
  822.   people requiring custom versions of dawg-walking stuff might
  823.   as well just copy this code and edit it to do what they want.
  824.  
  825.   The special version print_dawg_prefix takes a NODE from somewhere
  826.   in a dict as a parameter, and prints out only those words which
  827.   contain that node.  You have to locate the node seperately with
  828.   'locate_prefix', and pass the prefix string in so it can be printed.
  829.  
  830. */
  831.  
  832. static void
  833. #ifdef PROTOTYPES
  834. dawg_pr(NODE PCCRAP *dawg, INDEX node, int len)
  835. #else
  836. dawg_pr(dawg, node, len)
  837. NODE PCCRAP *dawg;
  838. INDEX node;
  839. int len;
  840. #endif
  841. {
  842.   static char word[MAX_WORD_LEN];
  843.   NODE PCCRAP *edge;
  844.  
  845.   for (edge = (NODE PCCRAP *)&dawg[node]; ; edge++) {
  846.   long c;
  847.     c = *edge;           /* Don't rewrite this - its avoiding a MSC bug */
  848.     c = c >> V_LETTER;
  849.     c = c & M_LETTER;
  850.     word[len] = (char)c;
  851.     if ((*edge & M_END_OF_WORD) != 0) {
  852.       word[len+1] = '\0';
  853.       fprintf(stdout, "%s\n", word);
  854.     }
  855.     c = *edge & M_NODE_POINTER;
  856.     if ((*edge & M_NODE_POINTER) != 0)
  857.       dawg_pr (dawg, c, len + 1);
  858.     if ((*edge & M_END_OF_NODE) != 0) break; /* End of node */
  859.   }
  860. }
  861.  
  862. void
  863. #ifdef PROTOTYPES
  864. dawg_print(NODE PCCRAP *dawg, INDEX node)
  865. #else
  866. dawg_print(dawg, node)
  867. NODE PCCRAP *dawg;
  868. INDEX node;
  869. #endif
  870. {
  871.   dawg_pr(dawg, node, 0);
  872. }
  873.  
  874. static void
  875. #ifdef PROTOTYPES
  876. pack_pr(NODE PCCRAP *ptrie, INDEX i, int pos)
  877. #else
  878. pack_pr(ptrie, i, pos)
  879. NODE PCCRAP *ptrie;
  880. INDEX i;
  881. int pos;
  882. #endif
  883. {
  884. static char s[MAX_WORD_LEN+1];
  885. int b;
  886. INDEX p;
  887.   for (b = BASE_CHAR; b < BASE_CHAR+MAX_CHARS; b++) {
  888.     if (b != 0) {
  889.       p = ptrie[i+b-BASE_CHAR];
  890.       if (((p>>V_LETTER)&M_LETTER) == b) {
  891.           s[pos] = b; s[pos+1] = '\0';
  892.         if ((p & M_END_OF_WORD) != 0) fprintf(stderr, "%s\n", s);
  893.         if ((p &= M_NODE_POINTER) != 0) {
  894.           pack_pr(ptrie, p, pos+1);
  895.         }
  896.       }
  897.     }
  898.   }
  899. }
  900.  
  901.  
  902. void
  903. #ifdef PROTOTYPES
  904. pack_print(NODE PCCRAP *ptrie, INDEX node)
  905. #else
  906. pack_print(ptrie, node)
  907. NODE PCCRAP *ptrie;
  908. INDEX node;
  909. #endif
  910. {
  911.   pack_pr(ptrie, node, 0);
  912. }
  913.  
  914.  
  915. static void
  916. #ifdef PROTOTYPES
  917. dawg_pr_prefix(NODE PCCRAP *dawg, char *prefix, INDEX node, int len)
  918. #else
  919. dawg_pr_prefix(dawg, prefix, node, len)
  920. NODE PCCRAP *dawg;
  921. char *prefix;
  922. INDEX node;
  923. int len;
  924. #endif
  925. {
  926.   NODE PCCRAP *edge;
  927.   static char word[MAX_WORD_LEN];
  928.   long c;
  929.  
  930.   for (edge = (NODE PCCRAP *)&dawg[node]; ; edge++) {
  931.     /* Don't 'fix' - compiler bugaround for microsoft :-( */
  932.     c = *edge; c = c >> V_LETTER; c = c & M_LETTER;
  933.     word[len] = (char)c;
  934.     if ((*edge & M_END_OF_WORD) != 0) {
  935.       word[len+1] = 0;
  936.       fprintf(stdout, "%s%s\n", prefix, word);
  937.     }
  938.     c = *edge & M_NODE_POINTER;
  939.     if (c != 0) dawg_pr_prefix(dawg, prefix, c, len + 1);
  940.     /* End of node - check repair later - I accidentally nobbled it */
  941.     if ((*edge & M_END_OF_NODE) != 0) break;
  942.   }
  943. }
  944.  
  945. void
  946. #ifdef PROTOTYPES
  947. dawg_print_prefix(NODE PCCRAP *dawg, char *prefix, INDEX node)
  948. #else
  949. dawg_print_prefix(dawg, prefix, node)
  950. NODE PCCRAP *dawg;
  951. char *prefix;
  952. INDEX node;
  953. #endif
  954. {
  955.   dawg_pr_prefix(dawg, prefix, node, 0);
  956. }
  957. SHAR_EOF
  958. cat - << \SHAR_EOF > similcmp.c
  959. #ifndef similcmp_c
  960. #define similcmp_c 1
  961.  
  962. #ifdef LIB_STRINGS
  963. #include <strings.h>
  964. #else
  965. #include <string.h>
  966. #endif
  967.  
  968. /*
  969.  
  970.     File:    similcmp.c
  971.     Authors: John Ratcliffe, and an anonymous coder.
  972.     Purpose: Better approximate string equality test.
  973.     Functions exported:  simil
  974.     Internal functions:  GCsubstr
  975.  
  976. Description:
  977.   See below.  I'll replace this one eventually with my own
  978.   algorithm which does sophisticated compound-grapheme analysis
  979.   and returns a degree of phonetic similarity and a probability
  980.   that the transformations made were valid.
  981.  
  982.  
  983.   'ghoti==fish' (Match = 90%, Prob = 1%) ;-)
  984.   lauGH = f       match 100% prob 30%
  985.   wOmen = i       match  90% prob 10%
  986.   staTIon = sh    match 100% prob 5%
  987.  
  988. */
  989.  
  990. /* Ratcliff/Obershelp pattern matching
  991.  *
  992.  *      Approximate word matching: takes two words and returns a
  993.  *      similarity score based on co-occurrence of subpatterns.
  994.  *
  995.  *      This code appeared in a letter to the editor in DDJ, 11/88.
  996.  *      The original article on the pattern matching, "Pattern Matching
  997.  *      by Gestalt" by John Ratcliff, appeared in the July 1988
  998.  *      issue (#181) but the algorithm was presented in assembly.  
  999.  *
  1000.  *      The 11/88 issue also contained another verison in C which was
  1001.  *      a more faithful translation of the original; it has the
  1002.  *      advantage of not being recursive.
  1003.  *
  1004.  *      The algorithm seems to work nicely for a variety of test cases.
  1005.  *      The main drawback of the algorithm is the cost of the pairwise
  1006.  *      comparisons.  It is significantly more expensive than stemming,
  1007.  *      soundex, and the like.  Might consider using this as a second
  1008.  *      phase...
  1009.  */
  1010.  
  1011. int
  1012. #ifdef PROTOTYPES
  1013. GCsubstr(char *st1, char *end1, char *st2, char *end2)
  1014. #else
  1015. GCsubstr(st1, end1, st2, end2)
  1016.   char *st1;
  1017.   char *end1;
  1018.   char *st2;
  1019.   char *end2;
  1020. #endif
  1021. {
  1022. register char *a1, *a2;
  1023. char *b1, *s1, *b2, *s2;
  1024. short max, i;
  1025.  
  1026.   if (end1 <= st1 || end2 <= st2) return(0);
  1027.   if (end1 == st1 + 1 && end2 == st2 + 1) return(0);
  1028.                 
  1029.   max = 0; b1 = end1; b2 = end2;
  1030.         
  1031.   for (a1 = st1; a1 < b1; a1++) {
  1032.     for (a2 = st2; a2 < b2; a2++) {
  1033.       if (*a1 == *a2) {
  1034.         /* determine length of common substring */
  1035.         for (i = 1; a1[i] && (a1[i] == a2[i]); i++) /* do nothing */;
  1036.         if (i > max) {
  1037.           max = i; s1 = a1; s2 = a2;
  1038.           b1 = end1 - max; b2 = end2 - max;
  1039.         }
  1040.       }
  1041.     }
  1042.   }
  1043.   if (!max) return(0);
  1044.   max += GCsubstr(s1 + max, end1, s2 + max, end2);        /* rhs */
  1045.   max += GCsubstr(st1, s1, st2, s2);                      /* lhs */
  1046.   return(max);
  1047. }
  1048.  
  1049. int
  1050. #ifdef PROTOTYPES
  1051. simil(char *s1, char *s2)
  1052. #else
  1053. simil(s1, s2)
  1054.  char *s1;
  1055.  char *s2;
  1056. #endif
  1057. {
  1058. int l1 = strlen(s1), l2 = strlen(s2);
  1059.  if (strcmp(s1, s2) == 0) return(100); /* exact match end-case */
  1060.  return(200 * GCsubstr(s1, s1 + l1, s2, s2 + l2) / (l1 + l2));
  1061. }
  1062. #endif /* similcmp_c */
  1063. SHAR_EOF
  1064. cat - << \SHAR_EOF > soundex.c
  1065. #ifndef soundex_c
  1066. #define soundex_c 1
  1067.  
  1068. #ifdef LIB_STRINGS
  1069. #include <strings.h>
  1070. #else
  1071. #include <string.h>
  1072. #endif
  1073.  
  1074.  
  1075. /* isalpha & toupper; define your own if you don't have ctype.h */
  1076. #include <ctype.h>
  1077.  
  1078. /*
  1079.  
  1080.     File:    soundex.c
  1081.     Authors: Jonathan Leffler
  1082.     Purpose: Approximate string equality test.
  1083.     Functions exported:  soundex
  1084.     Internal functions:  nsoundex
  1085.  
  1086. Description:
  1087.  
  1088.  There are umpteen soundexes around. At least this one is commented...
  1089.  (Actually I'd prefer one which understood ph/f and Mac/Mc as special
  1090.   cases; short of a proper phonetic alg such as I'm currently developing)
  1091.  See below for description:
  1092.  
  1093. */
  1094.  
  1095. /*
  1096. **      SOUNDEX CODING
  1097. **
  1098. **      Rules:
  1099. **      1.      Retain the first letter; ignore non-alphabetic characters.
  1100. **      2.      Replace second and subsequent characters by a group code.
  1101. **              Group   Letters
  1102. **              1               BFPV
  1103. **              2               CGJKSXZ
  1104. **              3               DT
  1105. **              4               L
  1106. **              5               MN
  1107. **              6               R
  1108. **      3.      Do not repeat digits
  1109. **      4.      Truncate or ser-pad to 4-character result.
  1110. **
  1111. **      Originally formatted with tabstops set at 4 spaces -- you were warned!
  1112. **
  1113. **      Code by: Jonathan Leffler (john@sphinx.co.uk)
  1114. **      This code is shareware -- I wrote it; you can have it for free
  1115. **      if you supply it to anyone else who wants it for free.
  1116. **
  1117. **      BUGS: Assumes 7-ASCII; fails on ISO Latin1
  1118. */
  1119.  
  1120. static char lookup[] = {
  1121.         '0',    /* A */        '1',    /* B */        '2',    /* C */
  1122.         '3',    /* D */        '0',    /* E */        '1',    /* F */
  1123.         '2',    /* G */        '0',    /* H */        '0',    /* I */
  1124.         '2',    /* J */        '2',    /* K */        '4',    /* L */
  1125.         '5',    /* M */        '5',    /* N */        '0',    /* O */
  1126.         '1',    /* P */        '0',    /* Q */        '6',    /* R */
  1127.         '2',    /* S */        '3',    /* T */        '0',    /* U */
  1128.         '1',    /* V */        '0',    /* W */        '2',    /* X */
  1129.         '0',    /* Y */        '2'     /* Z */
  1130. };
  1131.  
  1132. /* Soundex for arbitrary number of characters of information */
  1133. #define MAX_SOUNDEX_LEN 10
  1134.  
  1135. static char *
  1136. #ifdef PROTOTYPES
  1137. nsoundex(char *str, int n)
  1138. #else
  1139. nsoundex(str, n)
  1140. char *str;                   /* In: String to be converted */
  1141. int n;                       /* In: Number of characters in result string */
  1142. #endif
  1143. {
  1144.   static char buff[MAX_SOUNDEX_LEN];
  1145.   register char *s;
  1146.   register char *t;
  1147.   char c;
  1148.   char l;
  1149.  
  1150.   if (n <= 0) n = 4;  /* Default */
  1151.   if (n > sizeof(buff) - 1)  n = sizeof(buff) - 1;
  1152.   t = &buff[0];
  1153.  
  1154.   for (s = str; ((c = *s) != '\0') && t < &buff[n]; s++) {
  1155.     if (!isalpha(c)) continue;
  1156.     c = toupper(c);
  1157.     if (t == &buff[0]) {
  1158.       l = *t++ = c;
  1159.       continue;
  1160.     }
  1161.     c = lookup[c-'A'];  /* Fails on any alpha not in 'a'..'z' */
  1162.     if (c != '0' && c != l) l = *t++ = c;
  1163.   }
  1164.   while (t < &buff[n]) *t++ = '0'; *t = '\0';
  1165.   return(&buff[0]);
  1166. }
  1167.  
  1168. /* Normal external interface */
  1169. char *
  1170. #ifdef PROTOTYPES
  1171. soundex(char *str)
  1172. #else
  1173. soundex(str)
  1174. char *str;
  1175. #endif
  1176. {
  1177.   return(nsoundex(str, 4));  /* vary this? - try 5 or 6? */
  1178. }
  1179. #endif /* soundex_c */
  1180.  
  1181. SHAR_EOF
  1182. cat - << \SHAR_EOF > utils.c
  1183. /*
  1184.  
  1185.     File:    utils.c
  1186.     Author:  Graham Toal
  1187.     Purpose: Portability library
  1188.  
  1189. Description:
  1190.  
  1191.    Most of what differs between operating systems is handled here.
  1192.    This module is *incredibly* hacky -- I've just been interested
  1193.    in finding the problems so far, not in making the solutions neat.
  1194.  
  1195.    The final release of this suite will concentrate on cleaning up
  1196.    this file!
  1197. */
  1198.  
  1199.  
  1200.  
  1201. /* PENDING: Generic load dict; meanwhile should also put efficient
  1202.    msdos file loading into getwords().  See spelldawg for best coding. */
  1203.  
  1204. #define SIZE_T size_t
  1205. /* MSDos redefines this for huge allocation */
  1206.  
  1207. #ifdef SYS_RISCOS
  1208. #define DEFAULT_DAWG "run:dict-dwg"
  1209. #define DEFAULT_PACK "run:dict-pck"
  1210. #else
  1211. #ifdef SYS_EMAS
  1212. #define DEFAULT_DAWG "dict#dwg"
  1213. #define DEFAULT_PACK "dict#pck"
  1214. #else
  1215. /* Unix, MessDross, etc... */
  1216. #define DEFAULT_DAWG "dict.dwg"
  1217. #define DEFAULT_PACK "dict.pck"
  1218. #endif
  1219. #endif
  1220.  
  1221.  
  1222. /* Undo any #define's here if they are inappropriate for some system */
  1223.  
  1224. #define EXT_CHAR '.'
  1225.  
  1226. #define READ_TEXT "r"
  1227. #define WRITE_BIN "wb"
  1228. #define READ_BIN "rb"
  1229.  
  1230.  
  1231. /* system configuration */
  1232.  
  1233. #ifdef KNOWS_VOID
  1234. #define VOID void
  1235. #else
  1236. /* As in... void fred(VOID) */
  1237. #define void int
  1238. #define VOID
  1239. #endif
  1240.  
  1241. #ifdef SYS_MSDOS
  1242. #ifdef COMPILER_ZORTECH
  1243. int _stack = 0x3000;
  1244. #define PCCRAP far
  1245. #else
  1246. #ifdef COMPILER_TURBOC
  1247. #define PCCRAP far
  1248. #else
  1249. #define PCCRAP huge
  1250. #endif
  1251. #endif
  1252. #else
  1253. #define PCCRAP
  1254. #endif
  1255.  
  1256. /* Hmph... I don't really want to do realloc too.  Just as well that
  1257.    one implmentation is buggy; saves me having to work out what to do :-) */
  1258.  
  1259.  
  1260. #ifdef SYS_MSDOS
  1261. /* Normally int... */
  1262. #undef SIZE_T
  1263. #define SIZE_T long
  1264. /* (Still to test AZTEC & LATTICE) */
  1265. /* Mallocs of > 64K (maybe even > 32K) have to come off the far/huge heap */
  1266. #ifdef COMPILER_ZORTECH
  1267. #include <dos.h>
  1268. #define MALLOC(x,s) (NODE PCCRAP *)farmalloc((x)*(s)) /* Zortech */
  1269. #define Malloc(x,s) malloc((x)*(s))
  1270. #define FREE(x) farfree(x)
  1271. #define Free(x) free(x)
  1272. #else /* else not microsoft */
  1273. #ifdef COMPILER_TURBOC
  1274. #include <alloc.h>
  1275. #define MALLOC(x,s) (NODE PCCRAP *)farmalloc((x)*(s))  /* Turbo */
  1276. #define Malloc(x,s) malloc((x)*(s))
  1277. #define FREE(x) farfree(x)
  1278. #define Free(x) free(x)
  1279. #else /* else not turbo */
  1280. #include <malloc.h>
  1281. #ifdef NEVER
  1282. #define MALLOC(x,s) (NODE PCCRAP *)my_halloc((long)(x),(size_t)(s))
  1283.  /* Microsoft, Aztec */
  1284. #define Malloc(x,s) my_malloc((x)*(s))
  1285. #define FREE(x) my_hfree((void huge *)(x))  /* For some reason MICROSOFT    */
  1286. #define Free(x) my_free((void *)x)          /* complains of a type mismatch */
  1287.                                          /* without these casts */
  1288. #endif
  1289. #define MALLOC(x,s) (NODE PCCRAP *)halloc((long)(x),(size_t)(s))
  1290.  /* Microsoft, Aztec */
  1291. #define Malloc(x,s) malloc((x)*(s))
  1292. #define FREE(x) hfree((void huge *)(x))  /* For some reason MICROSOFT    */
  1293. #define Free(x) free((void *)x)          /* complains of a type mismatch */
  1294.                                          /* without these casts */
  1295. #endif
  1296. #endif
  1297. #else /* else not SYS_MSDOS */
  1298. #ifdef STDLIBS
  1299. #include <stdlib.h>  /* for malloc, free & exit */
  1300. #define MALLOC(x,s) (NODE PCCRAP *)malloc(((x)*(s)))
  1301. #define Malloc(x,s) malloc((x)*(s))
  1302. #define FREE(x) free(x)
  1303. #define Free(x) free(x)
  1304. #else
  1305. #define MALLOC(x,s) (NODE PCCRAP *)malloc(((x)*(s)))
  1306. #define Malloc(x,s) malloc((x)*(s))
  1307. #define FREE(x) free(x)
  1308. #define Free(x) free(x)
  1309. #ifndef size_t       /* Doesn't work if size_t was typedef'd */
  1310. #define size_t int   /* And if an int isn't big enough we're in trouble! */
  1311. #endif
  1312. #ifdef PROTOTYPES
  1313. extern void *malloc(size_t bytes);
  1314. extern void exit(int rc);
  1315. #else
  1316. extern void *malloc();
  1317. extern void exit();
  1318. #endif
  1319. #endif /* not stdlibs */
  1320. #endif /* Not msdos */
  1321.  
  1322. #ifdef SYS_RISCOS
  1323. #undef EXT_CHAR
  1324. #define EXT_CHAR '-'
  1325. #endif
  1326.  
  1327. #ifdef SYS_EMAS
  1328. #undef EXT_CHAR
  1329. #define EXT_CHAR '#'
  1330. #endif
  1331.  
  1332. #ifdef SYS_MAC
  1333. #ifdef COMPILER_THINK
  1334. #undef WRITE_BIN
  1335. #undef READ_BIN
  1336. #define WRITE_BIN "w"
  1337. #define READ_BIN "r"
  1338. #endif
  1339. #endif
  1340.  
  1341. #ifdef MEMMODELS
  1342. #define SMALL_MEMORY 1
  1343. #endif
  1344.  
  1345. /*
  1346.                      Error handling
  1347.  
  1348.      At the moment we'll just go for OK / NOT OK.  Later we should
  1349.    fix all exit's to use a specific code symbol (eg EXIT_MALLOCFAIL)
  1350.    but this has to be done system by system.  Whenever a new one is
  1351.    added, a default should be set up (as 0?)
  1352.  */
  1353.  
  1354. /*#include <errno.h>*/        /* Only later when we want to be more precise! */
  1355. #define EXIT_OK       (0)     /* Generic success              */
  1356. #define EXIT_ERROR    (1)     /* Generaic failure             */
  1357.  
  1358. /* For each system, replace generic errors with system-dependant ones. */
  1359. #ifdef vms
  1360. /*
  1361.  * VMS-specific error status codes.  Approximate Ultrix equivalents.
  1362.  */
  1363. #include <ssdef.h>
  1364. #include <stsdef.h>
  1365. #undef  EXIT_OK
  1366. #define EXIT_OK     SS$_NORMAL     /* Generic success                  */
  1367. #undef  EXIT_ERROR
  1368. #define EXIT_ERROR  SS$_NORMAL     /* Don't want random error message! */
  1369. #endif
  1370.  
  1371. #define DELETE(filename)
  1372.  
  1373. #ifdef __STDC__
  1374. #undef DELETE
  1375. #define DELETE(filename) remove(filename)
  1376. #else
  1377. #ifdef unix
  1378. #undef DELETE
  1379. #define DELETE(filename) unlink(filename)
  1380. #endif
  1381. #endif
  1382.  
  1383. #ifdef NEVER
  1384.  
  1385. /* these macros caught the fact that on MICROSOFT, the parameters
  1386.    being passed in were ints -- and I hadn't been given a warning
  1387.    because I had explicitly cast the to size-t.  Hence why I've
  1388.    declared SIZE_T as long.  This is all a bit messy. Curse you IBM PCs
  1389.  */
  1390.  
  1391. void PCCRAP *my_halloc(long n,size_t s) {
  1392. char PCCRAP *p;
  1393.   p = halloc(n, s);
  1394.   fprintf(stderr, "halloc(%8lx*%d) -> %8lx\n", n, s, (long)p);
  1395.   return(p);
  1396. }
  1397.  
  1398. void *my_malloc(size_t s) {
  1399. char *p;
  1400.   p = malloc(s);
  1401.   fprintf(stderr, "malloc(%4x) -> %4x\n", s, (int)p);
  1402.   return(p);
  1403. }
  1404.  
  1405. void my_hfree(void PCCRAP *p) {
  1406.   fprintf(stderr, "hfree(%8lx)\n", (long)p);
  1407.   hfree(p);
  1408. }
  1409.  
  1410. void my_free(void *p) {
  1411.   fprintf(stderr, "free(%4x)\n", (int)p);
  1412.   free(p);
  1413. }
  1414. #endif
  1415.  
  1416.  
  1417. #ifdef RCHECK
  1418. #ifndef PROTOTYPES
  1419. long toosmall(idx, max, line)
  1420. long idx;
  1421. long max;
  1422. int line;
  1423. #else
  1424. long toosmall(long idx, long max, int line)
  1425. #endif
  1426. {
  1427.   if (line == 0) {
  1428.     fprintf(stderr,
  1429.       "RANGE CHECK: %ld should not be less than 0 (max %ld)\n", idx, max);
  1430.   } else {
  1431.     fprintf(stderr,
  1432.       "RANGE CHECK AT LINE %d: %ld should not be less than 0 (max %ld)\n",
  1433.       line, idx, max);
  1434.   }
  1435.   return(0L);
  1436. }
  1437. #ifndef PROTOTYPES
  1438. long toobig(idx, max, line)
  1439. long idx;
  1440. long max;
  1441. int line;
  1442. #else
  1443. long toobig(long idx, long max, int line)
  1444. #endif
  1445. {
  1446.   if (line == 0) {
  1447.     fprintf(stderr,
  1448.       "RANGE CHECK: %ld should not be larger than %ld\n", idx, max);
  1449.   } else {
  1450.     fprintf(stderr,
  1451.       "RANGE CHECK AT LINE %d: %ld should not be larger than %ld\n",
  1452.       line, idx, max);
  1453.   }
  1454.   return(max);
  1455. }
  1456.  
  1457. #ifdef KNOWS_LINE
  1458. #define TOOSMALL(idx, max) toosmall((long)idx, (long)max, __LINE__)
  1459. #define TOOBIG(idx, max) toobig((long)idx, (long)max, __LINE__)
  1460. #else
  1461. #define TOOSMALL(idx, max) toosmall((long)idx, (long)max, 0)
  1462. #define TOOBIG(idx, max) toobig((long)idx, (long)max, 0)
  1463. #endif
  1464.  
  1465. #define RANGECHECK(idx,max) \
  1466.   (idx < 0 ? (TOOSMALL(idx,max)) : (idx >= max ? (TOOBIG(idx,max)) : idx))
  1467. #else
  1468. #define RANGECHECK(idx,max) (idx)
  1469. #endif
  1470.  
  1471. #ifdef PROTOTYPES
  1472. long getwords(long PCCRAP *data, long count, FILE *fp)
  1473. #else
  1474. long getwords(data, count, fp)
  1475. long PCCRAP *data;
  1476. long count;
  1477. FILE *fp;
  1478. #endif
  1479. {
  1480. #ifdef SYS_MSDOS
  1481. char PCCRAP *p; int c; long byte_count;
  1482.   p = (char PCCRAP *)(&data[0]);
  1483.   /* Somewhere I have a version which fread()s into a 16K near
  1484.      buffer, then copies it out; use that technique here - *MUCH*
  1485.      faster */
  1486.   for (byte_count = 0; byte_count < count; byte_count++) {
  1487.     c = fgetc(fp);
  1488.     if (c == -1 || ferror(fp)) {
  1489.       printf ("Dictionary read error - %ld wanted - %ld got\n",
  1490.         count, byte_count)/*, exit(0)*/;
  1491.       break;
  1492.     }
  1493.     *p++ = (c & 255);
  1494.   }
  1495.   return(count);
  1496. #else
  1497.   return((long)fread(&data[0], (size_t)1, (size_t)count, fp));
  1498. #endif
  1499. }
  1500.  
  1501. #ifdef PROTOTYPES
  1502. long putwords(long PCCRAP *data, long count, FILE *fp)
  1503. #else
  1504. long putwords(data, count, fp)
  1505. long PCCRAP *data;
  1506. long count;
  1507. FILE *fp;
  1508. #endif
  1509. {
  1510. #ifdef SYS_MSDOS
  1511. extern int _NEAR _CDECL errno;
  1512. long i; char PCCRAP *p;
  1513.   p = (char PCCRAP *)&data[0];
  1514.   if (fp == NULL) {
  1515.     fprintf(stderr, "putwords: no file?\n");
  1516.     exit(0);
  1517.   }
  1518.   for (i = 0L; i < count; i++) {
  1519.   /* Somewhere I have a version which copies to a 16K near
  1520.      buffer, then frwrite()s it out; use that technique here - *MUCH*
  1521.      faster */
  1522.     int rc = fputc(*p++, fp);
  1523.     if (ferror(fp)) {
  1524.       fprintf(stderr, "rc = %d\n", rc);
  1525.       perror("dawg");
  1526.       fprintf (stderr, "Error writing to output file\n");
  1527.       exit(0);
  1528.     }
  1529.   }
  1530.   return(count);
  1531. #else
  1532.   return(fwrite(&data[0], (size_t)1, (size_t)count, fp));
  1533. #endif
  1534. }
  1535.  
  1536. static long PCCRAP *WTMP = NULL;
  1537. /* A bit hacky having this single 4 bytes in heap space, but it makes
  1538.    things a little more consistent.  it'll all go away eventually
  1539.    anyway... */
  1540.  
  1541. #ifdef PROTOTYPES
  1542. void putword(long w, FILE *fp)
  1543. #else
  1544. void putword(w, fp)
  1545. long w;
  1546. FILE *fp;
  1547. #endif
  1548. {
  1549.   if (WTMP == NULL) {
  1550.     WTMP = (long PCCRAP *)MALLOC(1,sizeof(long));
  1551.   }
  1552.   *WTMP = w;
  1553.   if (putwords(WTMP, (long)sizeof(long), fp) != sizeof(long)) {
  1554.     /* (using putwords avoids confusion over bytesex) */
  1555.     fprintf(stderr, "Data write error - putword\n");
  1556.   }
  1557. }
  1558.  
  1559. #ifdef PROTYPES
  1560. long getword(FILE *fp)
  1561. #else
  1562. long getword(fp)
  1563. FILE *fp;
  1564. #endif
  1565. {
  1566.   if (WTMP == NULL) {
  1567.     WTMP = (long PCCRAP *)MALLOC(1,sizeof(long));
  1568.   }
  1569.   if (getwords(WTMP, (long)sizeof(long), fp) != sizeof(long)) {
  1570.     fprintf(stderr, "Data read error - getword\n");
  1571.   }
  1572.   return(*WTMP);
  1573. }
  1574. SHAR_EOF
  1575.