home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pccts.zip / pccts / support / set / set.c next >
C/C++ Source or Header  |  1994-03-31  |  15KB  |  786 lines
  1. /*    set.c
  2.  
  3.     The following is a general-purpose set library originally developed
  4.     by Hank Dietz and enhanced by Terence Parr to allow dynamic sets.
  5.     
  6.     Sets are now structs containing the #words in the set and
  7.     a pointer to the actual set words.
  8.     
  9.     Generally, sets need not be explicitly allocated.  They are
  10.     created/extended/shrunk when appropriate (e.g. in set_of()).
  11.     HOWEVER, sets need to be destroyed (free()ed) when they go out of scope
  12.     or are otherwise no longer needed.  A routine is provided to
  13.     free a set.
  14.     
  15.     Sets can be explicitly created with set_new(s, max_elem).
  16.     
  17.     Sets can be declared to have minimum size to reduce realloc traffic.
  18.     Default minimum size = 1.
  19.     
  20.     Sets can be explicitly initialized to have no elements (set.n == 0)
  21.     by using the 'empty' initializer:
  22.     
  23.     Examples:
  24.         set a = empty;    -- set_deg(a) == 0
  25.         
  26.         return( empty );
  27.     
  28.     Example set creation and destruction:
  29.     
  30.     set
  31.     set_of2(e,g)
  32.     unsigned e,g;
  33.     {
  34.         set a,b,c;
  35.         
  36.         b = set_of(e);        -- Creates space for b and sticks in e
  37.         set_new(c, g);        -- set_new(); set_orel() ==> set_of()
  38.         set_orel(g, &c);
  39.         a = set_or(b, c);
  40.         .
  41.         .
  42.         .
  43.         set_free(b);
  44.         set_free(c);
  45.         return( a );
  46.     }
  47.  
  48.     1987 by Hank Dietz
  49.     
  50.     Modified by:
  51.         Terence Parr
  52.         Purdue University
  53.         October 1989
  54.  
  55.     Made it smell less bad to C++ 7/31/93 -- TJP
  56. */
  57.  
  58. #include <stdio.h>
  59. #ifdef __cplusplus
  60. #ifndef __STDC__
  61. #define __STDC__
  62. #endif
  63. #endif
  64. #ifdef __STDC__
  65. #include <stdlib.h>
  66. #else
  67. #include <malloc.h>
  68. #endif
  69. #include <string.h>
  70.  
  71. #include "set.h"
  72.  
  73. /* elems can be a maximum of 32 bits */
  74. static unsigned bitmask[] = {
  75.     0x00000001, 0x00000002, 0x00000004, 0x00000008,
  76.     0x00000010, 0x00000020, 0x00000040, 0x00000080,
  77.     0x00000100, 0x00000200, 0x00000400, 0x00000800,
  78.     0x00001000, 0x00002000, 0x00004000, 0x00008000,
  79. #ifndef PC
  80.     0x00010000, 0x00020000, 0x00040000, 0x00080000,
  81.     0x00100000, 0x00200000, 0x00400000, 0x00800000,
  82.     0x01000000, 0x02000000, 0x04000000, 0x08000000,
  83.     0x10000000, 0x20000000, 0x40000000, 0x80000000
  84. #endif
  85. };
  86.  
  87. set empty = set_init;
  88. static unsigned min=1;
  89.  
  90. #define StrSize        200
  91.  
  92. #ifdef MEMCHK
  93. #define CHK(a)                    \
  94.     if ( a.setword != NULL )    \
  95.       if ( !valid(a.setword) )    \
  96.         {fprintf(stderr, "%s(%d): invalid set\n",__FILE__,__LINE__); exit(-1);}
  97. #else
  98. #define CHK(a)
  99. #endif
  100.  
  101. /*
  102.  * Set the minimum size (in words) of a set to reduce realloc calls
  103.  */
  104. void
  105. #ifdef __STDC__
  106. set_size( unsigned n )
  107. #else
  108. set_size( n )
  109. unsigned n;
  110. #endif
  111. {
  112.     min = n;
  113. }
  114.  
  115. unsigned int
  116. #ifdef __STDC__
  117. set_deg( set a )
  118. #else
  119. set_deg( a )
  120. set a;
  121. #endif
  122. {
  123.     /* Fast compute degree of a set... the number
  124.        of elements present in the set.  Assumes
  125.        that all word bits are used in the set
  126.        and that SETSIZE(a) is a multiple of WORDSIZE.
  127.     */
  128.     register unsigned *p = &(a.setword[0]);
  129.     register unsigned *endp = &(a.setword[a.n]);
  130.     register unsigned degree = 0;
  131.  
  132.     CHK(a);
  133.     if ( a.n == 0 ) return(0);
  134.     while ( p < endp )
  135.     {
  136.         register unsigned t = *p;
  137.         register unsigned *b = &(bitmask[0]);
  138.         do {
  139.             if (t & *b) ++degree;
  140.         } while (++b < &(bitmask[WORDSIZE]));
  141.         p++;
  142.     }
  143.  
  144.     return(degree);
  145. }
  146.  
  147. set
  148. #ifdef __STDC__
  149. set_or( set b, set c )
  150. #else
  151. set_or( b, c )
  152. set b;
  153. set c;
  154. #endif
  155. {
  156.     /* Fast set union operation */
  157.     /* resultant set size is max(b, c); */
  158.     set *big;
  159.     set t;
  160.     unsigned int m,n;
  161.     register unsigned *r, *p, *q, *endp;
  162.  
  163.     CHK(b); CHK(c);
  164.     t = empty;
  165.     if (b.n > c.n) {big= &b; m=b.n; n=c.n;} else {big= &c; m=c.n; n=b.n;}
  166.     set_ext(&t, m);
  167.     r = t.setword;
  168.  
  169.     /* Or b,c until max of smaller set */
  170.     q = c.setword;
  171.     p = b.setword;
  172.     endp = &(b.setword[n]);
  173.     while ( p < endp ) *r++ = *p++ | *q++;    
  174.  
  175.     /* Copy rest of bigger set into result */
  176.     p = &(big->setword[n]);
  177.     endp = &(big->setword[m]);
  178.     while ( p < endp ) *r++ = *p++;
  179.  
  180.     return(t);
  181. }
  182.  
  183. set
  184. #ifdef __STDC__
  185. set_and( set b, set c )
  186. #else
  187. set_and( b, c )
  188. set b;
  189. set c;
  190. #endif
  191. {
  192.     /* Fast set intersection operation */
  193.     /* resultant set size is min(b, c); */
  194.     set t;
  195.     unsigned int n;
  196.     register unsigned *r, *p, *q, *endp;
  197.  
  198.     CHK(b); CHK(c);
  199.     t = empty;
  200.     n = (b.n > c.n) ? c.n : b.n;
  201.     if ( n == 0 ) return t;        /* TJP 4-27-92 fixed for empty set */
  202.     set_ext(&t, n);
  203.     r = t.setword;
  204.  
  205.     /* & b,c until max of smaller set */
  206.     q = c.setword;
  207.     p = b.setword;
  208.     endp = &(b.setword[n]);
  209.     while ( p < endp ) *r++ = *p++ & *q++;    
  210.  
  211.     return(t);
  212. }
  213.  
  214. set
  215. #ifdef __STDC__
  216. set_dif( set b, set c )
  217. #else
  218. set_dif( b, c )
  219. set b;
  220. set c;
  221. #endif
  222. {
  223.     /* Fast set difference operation b - c */
  224.     /* resultant set size is size(b) */
  225.     set t;
  226.     unsigned int n;
  227.     register unsigned *r, *p, *q, *endp;
  228.  
  229.     CHK(b); CHK(c);
  230.     t = empty;
  231.     n = (b.n <= c.n) ? b.n : c.n ;
  232.     if ( b.n == 0 ) return t;        /* TJP 4-27-92 fixed for empty set */
  233.                                     /* WEC 12-1-92 fixed for c.n = 0 */
  234.     set_ext(&t, b.n);
  235.     r = t.setword;
  236.  
  237.     /* Dif b,c until smaller set size */
  238.     q = c.setword;
  239.     p = b.setword;
  240.     endp = &(b.setword[n]);
  241.     while ( p < endp ) *r++ = *p++ & (~ *q++);    
  242.  
  243.     /* Copy rest of b into result if size(b) > c */
  244.     if ( b.n > n )
  245.     {
  246.         p = &(b.setword[n]);
  247.         endp = &(b.setword[b.n]);
  248.         while ( p < endp ) *r++ = *p++;
  249.     }
  250.  
  251.     return(t);
  252. }
  253.  
  254. set
  255. #ifdef __STDC__
  256. set_of( unsigned b )
  257. #else
  258. set_of( b )
  259. unsigned b;
  260. #endif
  261. {
  262.     /* Fast singleton set constructor operation */
  263.     static set a;
  264.  
  265.     if ( b == nil ) return( empty );
  266.     set_new(a, b);
  267.     a.setword[DIVWORD(b)] = bitmask[MODWORD(b)];
  268.  
  269.     return(a);
  270. }
  271.  
  272. /*
  273.  * Extend (or shrink) the set passed in to have n words.
  274.  *
  275.  * if n is smaller than the minimum, boost n to have the minimum.
  276.  * if the new set size is the same as the old one, do nothing.
  277.  *
  278.  * TJP 4-27-92 Fixed so won't try to alloc 0 bytes
  279.  */
  280. void
  281. #ifdef __STDC__
  282. set_ext( set *a, unsigned int n )
  283. #else
  284. set_ext( a, n )
  285. set *a;
  286. unsigned int n;
  287. #endif
  288. {
  289.     register unsigned *p;
  290.     register unsigned *endp;
  291.     unsigned int size;
  292.     
  293.     CHK((*a));
  294.     if ( a->n == 0 )
  295.     {
  296.         if ( n == 0 ) return;
  297.         a->setword = (unsigned *) calloc(n, BytesPerWord);
  298.         if ( a->setword == NULL )
  299.         {
  300.             fprintf(stderr, "set_ext(%d words): cannot allocate set\n", n);
  301.             exit(-1);
  302.         }
  303.         a->n = n;
  304.         return;
  305.     }
  306.     if ( n < min ) n = min;
  307.     if ( a->n == n || n == 0 ) return;
  308.     size = a->n;
  309.     a->n = n;
  310.     a->setword = (unsigned *) realloc( a->setword, (n*BytesPerWord) );
  311.     if ( a->setword == NULL )
  312.     {
  313.         fprintf(stderr, "set_ext(%d words): cannot allocate set\n", n);
  314.         exit(-1);
  315.     }
  316.  
  317.     p    = &(a->setword[size]);        /* clear from old size to new size */
  318.     endp = &(a->setword[a->n]);
  319.     do {
  320.         *p++ = 0;
  321.     } while ( p < endp );
  322. }
  323.  
  324. set
  325. #ifdef __STDC__
  326. set_not( set a )
  327. #else
  328. set_not( a )
  329. set a;
  330. #endif
  331. {
  332.     /* Fast not of set a (assumes all bits used) */
  333.     /* size of resultant set is size(a) */
  334.     /* ~empty = empty cause we don't know how bit to make set */
  335.     set t;
  336.     register unsigned *r;
  337.     register unsigned *p = a.setword;
  338.     register unsigned *endp = &(a.setword[a.n]);
  339.  
  340.     CHK(a);
  341.     t = empty;
  342.     if ( a.n == 0 ) return( empty );
  343.     set_ext(&t, a.n);
  344.     r = t.setword;
  345.     
  346.     do {
  347.         *r++ = (~ *p++);
  348.     } while ( p < endp );
  349.  
  350.     return(t);
  351. }
  352.  
  353. int
  354. #ifdef __STDC__
  355. set_equ( set a, set b )
  356. #else
  357. set_equ( a, b )
  358. set a;
  359. set b;
  360. #endif
  361. {
  362.     /* Fast set equality comparison operation */
  363.     register unsigned *p = a.setword;
  364.     register unsigned *q = b.setword;
  365.     register unsigned *endp = &(a.setword[a.n]);
  366.  
  367.     CHK(a); CHK(b);
  368.     if ( a.n != b.n ) return(0);
  369.     else if ( a.n==0 ) return(1);    /* empty == empty */
  370.     
  371.     do {
  372.         if (*p != *q) return(0);
  373.         ++q;
  374.     } while ( ++p < endp );
  375.  
  376.     return(1);
  377. }
  378.  
  379. int
  380. #ifdef __STDC__
  381. set_sub( set a, set b )
  382. #else
  383. set_sub( a, b )
  384. set a;
  385. set b;
  386. #endif
  387. {
  388.     /* Fast check for a is a proper subset of b (alias a < b) */
  389.     register unsigned *p = a.setword;
  390.     register unsigned *q = b.setword;
  391.     register unsigned *endp = &(a.setword[a.n]);
  392.     register int asubset = 0;
  393.  
  394.     CHK(a); CHK(b);
  395.     if ( a.n > b.n ) return(0);
  396.     if (a.n==0 && b.n==0) return(1);/* empty prop sub of empty */
  397.     if ( a.n == 0 ) return(1);        /* empty is sub of everything */
  398.  
  399.     do {
  400.         /* Prune tests based on guess that most set words
  401.            will match, particularly if a is a subset of b.
  402.         */
  403.         if (*p != *q) {
  404.             if (*p & ~(*q)) {
  405.                 /* Fail -- a contains something b does not */
  406.                 return(0);
  407.             }
  408.             /* At least this word was a proper subset, hence
  409.                even if all other words are equal, a is a
  410.                proper subset of b.
  411.             */
  412.             asubset = 1;
  413.         }
  414.         ++q;
  415.     } while (++p < endp);
  416.  
  417.     /* at this point, a,b are equ or a subset */
  418.     if ( asubset || b.n == a.n ) return(asubset);
  419.     
  420.     /* if !asubset, size(b) > size(a), then a=b and must check rest of b */
  421.     p = q;
  422.     endp = &(a.setword[b.n]);
  423.     do
  424.     {
  425.         if ( *p++ ) return(1);
  426.     } while ( p < endp );
  427.  
  428.     return(0);
  429. }
  430.  
  431. unsigned
  432. #ifdef __STDC__
  433. set_int( set b )
  434. #else
  435. set_int( b )
  436. set b;
  437. #endif
  438. {
  439.     /* Fast pick any element of the set b */
  440.     register unsigned *p = b.setword;
  441.     register unsigned *endp = &(b.setword[b.n]);
  442.  
  443.     CHK(b);
  444.     if ( b.n == 0 ) return( nil );
  445.  
  446.     do {
  447.         if (*p) {
  448.             /* Found a non-empty word of the set */
  449.             register unsigned i = ((p - b.setword) << LogWordSize);
  450.             register unsigned t = *p;
  451.             p = &(bitmask[0]);
  452.             while (!(*p & t)) {
  453.                 ++i; ++p;
  454.             }
  455.             return(i);
  456.         }
  457.     } while (++p < endp);
  458.  
  459.     /* Empty -- only element it contains is nil */
  460.     return(nil);
  461. }
  462.  
  463. int
  464. #ifdef __STDC__
  465. set_el( unsigned b, set a )
  466. #else
  467. set_el( b, a )
  468. unsigned b;
  469. set a;
  470. #endif
  471. {
  472.     CHK(a);
  473.     /* nil is an element of every set */
  474.     if (b == nil) return(1);
  475.     if ( a.n == 0 || NumWords(b) > a.n ) return(0);
  476.     
  477.     /* Otherwise, we have to check */
  478.     return( a.setword[DIVWORD(b)] & bitmask[MODWORD(b)] );
  479. }
  480.  
  481. int
  482. #ifdef __STDC__
  483. set_nil( set a )
  484. #else
  485. set_nil( a )
  486. set a;
  487. #endif
  488. {
  489.     /* Fast check for nil set */
  490.     register unsigned *p = a.setword;
  491.     register unsigned *endp = &(a.setword[a.n]);
  492.  
  493.     CHK(a);
  494.     if ( a.n == 0 ) return(1);
  495.     /* The set is not empty if any word used to store
  496.        the set is non-zero.  This means one must be a
  497.        bit careful about doing things like negation.
  498.     */
  499.     do {
  500.         if (*p) return(0);
  501.     } while (++p < endp);
  502.     
  503.     return(1);
  504. }
  505.  
  506. char *
  507. #ifdef __STDC__
  508. set_str( set a )
  509. #else
  510. set_str( a )
  511. set a;
  512. #endif
  513. {
  514.     /* Fast convert set a into ASCII char string...
  515.        assumes that all word bits are used in the set
  516.        and that SETSIZE is a multiple of WORDSIZE.
  517.        Trailing 0 bits are removed from the string.
  518.        if no bits are on or set is empty, "" is returned.
  519.     */
  520.     register unsigned *p = a.setword;
  521.     register unsigned *endp = &(a.setword[a.n]);
  522.     static char str_tmp[StrSize+1];
  523.     register char *q = &(str_tmp[0]);
  524.  
  525.     CHK(a);
  526.     if ( a.n==0 ) {*q=0; return( &(str_tmp[0]) );}
  527.     do {
  528.         register unsigned t = *p;
  529.         register unsigned *b = &(bitmask[0]);
  530.         do {
  531.             *(q++) = (char) ((t & *b) ? '1' : '0');
  532.         } while (++b < &(bitmask[WORDSIZE]));
  533.     } while (++p < endp);
  534.  
  535.     /* Trim trailing 0s & NULL terminate the string */
  536.     while ((q > &(str_tmp[0])) && (*(q-1) != '1')) --q;
  537.     *q = 0;
  538.  
  539.     return(&(str_tmp[0]));
  540. }
  541.  
  542. set
  543. #ifdef __STDC__
  544. set_val( register char *s )
  545. #else
  546. set_val( s )
  547. register char *s;
  548. #endif
  549. {
  550.     /* Fast convert set ASCII char string into a set.
  551.        If the string ends early, the remaining set bits
  552.        are all made zero.
  553.        The resulting set size is just big enough to hold all elements.
  554.     */
  555.     static set a;
  556.     register unsigned *p, *endp;
  557.  
  558.     set_new(a, strlen(s));
  559.     p = a.setword;
  560.     endp = &(a.setword[a.n]);
  561.     do {
  562.         register unsigned *b = &(bitmask[0]);
  563.         /* Start with a word with no bits on */
  564.         *p = 0;
  565.         do {
  566.             if (*s) {
  567.                 if (*s == '1') {
  568.                     /* Turn-on this bit */
  569.                     *p |= *b;
  570.                 }
  571.                 ++s;
  572.             }
  573.         } while (++b < &(bitmask[WORDSIZE]));
  574.     } while (++p < endp);
  575.  
  576.     return(a);
  577. }
  578.  
  579. /*
  580.  * Or element e into set a.  a can be empty.
  581.  */
  582. void
  583. #ifdef __STDC__
  584. set_orel( unsigned e, set *a )
  585. #else
  586. set_orel( e, a )
  587. unsigned e;
  588. set *a;
  589. #endif
  590. {
  591.     CHK((*a));
  592.     if ( e == nil ) return;
  593.     if ( NumWords(e) > a->n ) set_ext(a, NumWords(e));
  594.     a->setword[DIVWORD(e)] |= bitmask[MODWORD(e)];
  595. }
  596.  
  597. /*
  598.  * Or set b into set a.  a can be empty. does nothing if b empty.
  599.  */
  600. void
  601. #ifdef __STDC__
  602. set_orin( set *a, set b )
  603. #else
  604. set_orin( a, b )
  605. set *a;
  606. set b;
  607. #endif
  608. {
  609.     /* Fast set union operation */
  610.     /* size(a) is max(a, b); */
  611.     unsigned int m;
  612.     register unsigned *p,
  613.                       *q    = b.setword,
  614.                       *endq = &(b.setword[b.n]);
  615.  
  616.     CHK((*a)); CHK(b);
  617.     if ( b.n == 0 ) return;
  618.     m = (a->n > b.n) ? a->n : b.n;
  619.     set_ext(a, m);
  620.     p = a->setword;
  621.     do {
  622.         *p++ |= *q++;
  623.     } while ( q < endq );
  624. }
  625.  
  626. void
  627. #ifdef __STDC__
  628. set_rm( unsigned e, set a )
  629. #else
  630. set_rm( e, a )
  631. unsigned e;
  632. set a;
  633. #endif
  634. {
  635.     /* Does not effect size of set */
  636.     CHK(a);
  637.     if ( (e == nil) || (NumWords(e) > a.n) ) return;
  638.     a.setword[DIVWORD(e)] ^= (a.setword[DIVWORD(e)]&bitmask[MODWORD(e)]);
  639. }
  640.  
  641. void
  642. #ifdef __STDC__
  643. set_clr( set a )
  644. #else
  645. set_clr( a )
  646. set a;
  647. #endif
  648. {
  649.     /* Does not effect size of set */
  650.     register unsigned *p = a.setword;
  651.     register unsigned *endp = &(a.setword[a.n]);
  652.     
  653.     CHK(a);
  654.     if ( a.n == 0 ) return;
  655.     do {
  656.         *p++ = 0;
  657.     } while ( p < endp );
  658. }
  659.  
  660. set
  661. #ifdef __STDC__
  662. set_dup( set a )
  663. #else
  664. set_dup( a )
  665. set a;
  666. #endif
  667. {
  668.     set b;
  669.     register unsigned *p,
  670.                       *q    = a.setword,
  671.                       *endq = &(a.setword[a.n]);
  672.     
  673.     CHK(a);
  674.     b = empty;
  675.     if ( a.n == 0 ) return( empty );
  676.     set_ext(&b, a.n);
  677.     p = b.setword;
  678.     do {
  679.         *p++ = *q++;
  680.     } while ( q < endq );
  681.     
  682.     return(b);
  683. }
  684.  
  685. /*
  686.  * Return a nil terminated list of unsigned ints that represents all
  687.  * "on" bits in the bit set.
  688.  *
  689.  * e.g. {011011} --> {1, 2, 4, 5, nil}
  690.  *
  691.  * _set_pdq and set_pdq are useful when an operation is required on each element
  692.  * of a set.  Normally, the sequence is:
  693.  *
  694.  *        while ( set_deg(a) > 0 ) {
  695.  *            e = set_int(a);
  696.  *            set_rm(e, a);
  697.  *            ...process e...
  698.  *        }
  699.  * Now,
  700.  *
  701.  *        t = e = set_pdq(a);
  702.  *        while ( *e != nil ) {
  703.  *            ...process *e...
  704.  *            e++;
  705.  *        }
  706.  *        free( t );
  707.  *
  708.  * We have saved many set calls and have not destroyed set a.
  709.  */
  710. void
  711. #ifdef __STDC__
  712. _set_pdq( set a, register unsigned *q )
  713. #else
  714. _set_pdq( a, q )
  715. set a;
  716. register unsigned *q;
  717. #endif
  718. {
  719.     register unsigned *p = a.setword,
  720.                       *endp = &(a.setword[a.n]);
  721.     register unsigned e=0;
  722.  
  723.     CHK(a);
  724.     /* are there any space (possibility of elements)? */
  725.     if ( a.n == 0 ) return;
  726.     do {
  727.         register unsigned t = *p;
  728.         register unsigned *b = &(bitmask[0]);
  729.         do {
  730.             if ( t & *b ) *q++ = e;
  731.             ++e;
  732.         } while (++b < &(bitmask[WORDSIZE]));
  733.     } while (++p < endp);
  734.     *q = nil;
  735. }
  736.  
  737. /*
  738.  * Same as _set_pdq except allocate memory.  set_pdq is the natural function
  739.  * to use.
  740.  */
  741. unsigned *
  742. #ifdef __STDC__
  743. set_pdq( set a )
  744. #else
  745. set_pdq( a )
  746. set a;
  747. #endif
  748. {
  749.     unsigned *q;
  750.     int max_deg;
  751.     
  752.     CHK(a);
  753.     max_deg = WORDSIZE*a.n;
  754.     /* assume a.n!=0 & no elements is rare, but still ok */
  755.     if ( a.n == 0 ) return(NULL);
  756.     q = (unsigned *) malloc((max_deg+1)*BytesPerWord);
  757.     if ( q == NULL ) return( NULL );
  758.     _set_pdq(a, q);
  759.     return( q );
  760. }
  761.  
  762. /* a function that produces a hash number for the set
  763.  */
  764. unsigned int
  765. #ifdef __STDC__
  766. set_hash( set a, register unsigned int mod )
  767. #else
  768. set_hash( a, mod )
  769. set a;
  770. register unsigned int mod;
  771. #endif
  772. {
  773.     /* Fast hash of set a (assumes all bits used) */
  774.     register unsigned *p = &(a.setword[0]);
  775.     register unsigned *endp = &(a.setword[a.n]);
  776.     register unsigned i = 0;
  777.  
  778.     CHK(a);
  779.     while (p<endp){
  780.         i += (*p);
  781.         ++p;
  782.     }
  783.  
  784.     return(i % mod);
  785. }
  786.