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