4.3BSD - /usr/src/usr.bin/spell/spell.h

   1: /*	@(#)spell.h	4.1	12/18/82	*/
   2: 
   3: #include <stdio.h>
   4: #include <ctype.h>
   5: 
   6: #ifndef unix
   7: #define SHIFT   5
   8: #define TABSIZE (int)(400000/(1<<SHIFT))
   9: int *tab;   /*honeywell loader deficiency*/
  10: #else
  11: #define Tolower(c)  (isupper(c)?tolower(c):c) /* ugh!!! */
  12: #define SHIFT   4
  13: #define TABSIZE 25000   /*(int)(400000/(1<<shift))--pdp11 compiler deficiency*/
  14: short   tab[TABSIZE];
  15: #endif
  16: long    p[] = {
  17:     399871,
  18:     399887,
  19:     399899,
  20:     399911,
  21:     399913,
  22:     399937,
  23:     399941,
  24:     399953,
  25:     399979,
  26:     399983,
  27:     399989,
  28: };
  29: #define NP  (sizeof(p)/sizeof(p[0]))
  30: #define NW  30
  31: 
  32: /*
  33: * Hash table for spelling checker has n bits.
  34: * Each word w is hashed by k different (modular) hash functions, hi.
  35: * The bits hi(w), i=1..k, are set for words in the dictionary.
  36: * Assuming independence, the probability that no word of a d-word
  37: * dictionary sets a particular bit is given by the Poisson formula
  38: * P = exp(-y)*y**0/0!, where y=d*k/n.
  39: * The probability that a random string is recognized as a word is then
  40: * (1-P)**k.  For given n and d this is minimum when y=log(2), P=1/2,
  41: * whence one finds, for example, that a 25000-word dictionary in a
  42: * 400000-bit table works best with k=11.
  43: */
  44: 
  45: long    pow2[NP][NW];
  46: 
  47: prime(argc, argv) register char **argv;
  48: {
  49:     int i, j;
  50:     long h;
  51:     register long *lp;
  52: 
  53: #ifndef unix
  54:     if ((tab = (int *)calloc(sizeof(*tab), TABSIZE)) == NULL)
  55:         return(0);
  56: #endif
  57:     if (argc > 1) {
  58:         FILE *f;
  59:         if ((f = fopen(argv[1], "ri")) == NULL)
  60:             return(0);
  61:         if (fread((char *)tab, sizeof(*tab), TABSIZE, f) != TABSIZE)
  62:             return(0);
  63:         fclose(f);
  64:     }
  65:     for (i=0; i<NP; i++) {
  66:         h = *(lp = pow2[i]) = 1<<14;
  67:         for (j=1; j<NW; j++)
  68:             h = *++lp = (h<<7) % p[i];
  69:     }
  70:     return(1);
  71: }
  72: 
  73: #define get(h)  (tab[h>>SHIFT]&(1<<((int)h&((1<<SHIFT)-1))))
  74: #define set(h)  tab[h>>SHIFT] |= 1<<((int)h&((1<<SHIFT)-1))

Defined functions

Defined variables

Defined macros

Usage of this include