2.9BSD - /usr/src/cmd/spell/spell.h

   1: #include <sys/localopts.h>  /* for computer type (NONSEPARATE?) */
   2: #include <stdio.h>
   3: #include <ctype.h>
   4: 
   5: #ifndef unix
   6: #define SHIFT   5
   7: #define TABSIZE (int)(400000/(1<<SHIFT))
   8: int *tab;   /*honeywell loader deficiency*/
   9: #else
  10: #define Tolower(c)  (isupper(c)?tolower(c):c) /* ugh!!! */
  11: #define SHIFT   4
  12:     /* The following modifications cut hash table to 300,000
  13: 	 * bits if NONSEPARATE is defined.
  14: 	 * mjk 9/19/80
  15: 	 * Eight hashing functions are used.
  16: 	 * This will run on non-separate I/D machine.
  17: 	 */
  18: #ifdef NONSEPARATE
  19: #define TABSIZE 18750   /*(int)(300000/(1<<SHIFT)) */
  20: #else
  21: #define TABSIZE 25000   /*(int)(400000/(1<<SHIFT)) */
  22: #endif
  23: short   tab[TABSIZE];
  24: #endif
  25: 
  26: #ifdef NONSEPARATE
  27: long    p[] = {
  28:     299909,
  29:     299933,
  30:     299941,
  31:     299951,
  32:     299969,
  33:     299977,
  34:     299983,
  35:     299993
  36: };
  37: #else
  38: long    p[] = {
  39:     399871,
  40:     399887,
  41:     399899,
  42:     399911,
  43:     399913,
  44:     399937,
  45:     399941,
  46:     399953,
  47:     399979,
  48:     399983,
  49:     399989,
  50: };
  51: #endif
  52: #define NP  (sizeof(p)/sizeof(p[0]))
  53: #define NW  30
  54: 
  55: /*
  56: * Hash table for spelling checker has n bits.
  57: * Each word w is hashed by k different (modular) hash functions, hi.
  58: * The bits hi(w), i=1..k, are set for words in the dictionary.
  59: * Assuming independence, the probability that no word of a d-word
  60: * dictionary sets a particular bit is given by the Poisson formula
  61: * P = exp(-y)*y**0/0!, where y=d*k/n.
  62: * The probability that a random string is recognized as a word is then
  63: * (1-P)**k.  For given n and d this is minimum when y=log(2), P=1/2,
  64: * whence one finds, for example, that a 25000-word dictionary in a
  65: * 400000-bit table works best with k=11.
  66: *	(For 300000-bit table use k=8; mjk.)
  67: */
  68: 
  69: long    pow2[NP][NW];
  70: 
  71: prime(argc, argv) register char **argv;
  72: {
  73:     int i, j;
  74:     long h;
  75:     register long *lp;
  76: 
  77: #ifndef unix
  78:     if ((tab = (int *)calloc(sizeof(*tab), TABSIZE)) == NULL)
  79:         return(0);
  80: #endif
  81:     if (argc > 1) {
  82:         FILE *f;
  83:         if ((f = fopen(argv[1], "ri")) == NULL)
  84:             return(0);
  85:         if (fread((char *)tab, sizeof(*tab), TABSIZE, f) != TABSIZE)
  86:             return(0);
  87:         fclose(f);
  88:     }
  89:     for (i=0; i<NP; i++) {
  90:         h = *(lp = pow2[i]) = 1<<14;
  91:         for (j=1; j<NW; j++)
  92:             h = *++lp = (h<<7) % p[i];
  93:     }
  94:     return(1);
  95: }
  96: 
  97: #define get(h)  (tab[h>>SHIFT]&(1<<((int)h&((1<<SHIFT)-1))))
  98: #define set(h)  tab[h>>SHIFT] |= 1<<((int)h&((1<<SHIFT)-1))

Defined functions

Defined variables

Defined macros

Usage of this include