util/LLgen/src/sets.c

   1 /* Copyright (c) 1991 by the Vrije Universiteit, Amsterdam, the Netherlands.
   2  * For full copyright and restrictions on use see the file COPYING in the top
   3  * level of the LLgen tree.
   4  */
   5
   6 /*
   7  *  L L G E N
   8  *
   9  *  An Extended LL(1) Parser Generator
  10  *
  11  *  Author : Ceriel J.H. Jacobs
  12  */
  13
  14 /*
  15  * sets.c
  16  * Set manipulation and allocation routines.
  17  */
  18
  19 # include "types.h"
  20 # include "extern.h"
  21 # include "sets.h"
  22 # include "assert.h"
  23
  24 # ifndef NORCSID
  25 static string rcsid9 = "$Id: sets.c,v 2.8 1997/02/21 11:27:55 ceriel Exp $";
  26 # endif
  27
  28 /* In this file the following routines are defined: */
  29 extern          setinit();
  30 extern p_set    setalloc();
  31 extern p_set    get_set();
  32 extern int      setunion();
  33 extern int      setintersect();
  34 extern          setminus();
  35 extern int      setempty();
  36 extern int      findindex();
  37 extern int      setcount();
  38
  39 int             nbytes;
  40 static int      setsize;
  41 int             tsetsize;
  42 p_set           *setptr, *maxptr;
  43 static t_info   set_info;
  44 p_mem           alloc();
  45
  46 setinit(nt_needed) {
  47         /*
  48          * Initialises some variables needed for setcomputations
  49          */
  50         register int     bitset;
  51
  52         nbytes = NBYTES(ntokens);
  53         bitset = ALIGN(nbytes);
  54         tsetsize = NINTS(bitset);
  55         if (nt_needed) {
  56                 /* nonterminals must be included in the sets */
  57                 bitset += NBYTES(nnonterms);
  58         }
  59         setsize = NINTS(bitset);
  60         set_info.i_esize = sizeof(p_set);
  61         set_info.i_incr = 20;
  62 }
  63
  64 p_set
  65 get_set() {
  66         /*
  67          * Allocate a set that cannot be freed
  68          */
  69         register p_set p, q;
  70         static p_set sets, maxsets;
  71
  72         if ((p = sets) >= maxsets) {
  73                 q = p = (p_set) alloc((unsigned) (50*setsize*sizeof(*sets)));
  74                 maxsets = p + 50 * setsize;
  75                 do {
  76                         *q++ = 0;
  77                 } while (q < maxsets);
  78         }
  79         sets = p + setsize;;
  80         return p;
  81 }
  82
  83 p_set
  84 setalloc() {
  85         /*
  86          * Allocate a set which can later be freed.
  87          */
  88         register p_set  p;
  89         register int    size = setsize;
  90
  91         p = (p_set) alloc((unsigned) (size * sizeof(*p))) + size;
  92         do {
  93                 *--p = 0;
  94         } while (--size);
  95         return p;
  96 }
  97
  98 int
  99 setunion(a,b) register p_set a,b; {
 100         /*
 101          * a = a union b.
 102          * Return 1 if the set a changed
 103          */
 104         register int    i;
 105         register int    j;
 106         register int    nsub = 0;
 107
 108         i = setsize;
 109         do {
 110                 *a = (j = *a) | *b++;
 111                 if (*a++ != j) {
 112                         nsub = 1;
 113                 }
 114         } while (--i);
 115         return nsub;
 116 }
 117
 118 int
 119 setintersect(a,b) register p_set a,b; {
 120         /*
 121          * a = a intersect b.
 122          * return 1 if the result is empty
 123          */
 124         register int    i;
 125         register int    nempty;
 126
 127         nempty = 1;
 128         i =  setsize;
 129         do {
 130                 if (*a++ &= *b++) nempty = 0;
 131         } while (--i);
 132         return nempty;
 133 }
 134
 135 setminus(a,b) register p_set a,b; {
 136         /*
 137          * a = a setminus b
 138          */
 139         register int    i;
 140
 141         i = setsize;
 142         do {
 143                 *a++ &= ~(*b++);
 144         } while (--i);
 145 }
 146
 147 int
 148 setempty(p) register p_set p; {
 149         /*
 150          * Return 1 if the set p is empty
 151          */
 152         register int    i;
 153
 154         i = tsetsize;
 155         do {
 156                 if (*p++) return 0;
 157         } while (--i);
 158         return 1;
 159 }
 160
 161 int
 162 findindex(set) p_set set; {
 163         /*
 164          * The set "set" will serve as a recovery set.
 165          * Search for it in the table. If not present, enter it.
 166          * Here is room for improvement. At the moment, the list of
 167          * sets is examined with linear search.
 168          */
 169         register p_set  *t;
 170         p_mem           new_mem();
 171         register p_set  a;
 172         register p_set  b;
 173         register int    i;
 174         int             saved;
 175
 176         /*
 177          * First search for the set in the table
 178          */
 179         for (t = setptr; t < maxptr; t++) {
 180                 a = *t;
 181                 b = set;
 182                 i = tsetsize;
 183                 do {
 184                         if (*a++ != *b++) break;
 185                 } while (--i);
 186                 if (i) continue;
 187                 /*
 188                  * Here, the sets are equal.
 189                  */
 190                 return nbytes * (t - setptr);
 191         }
 192         /*
 193          * Now check if the set consists of only one element.
 194          * It would be a waste to use a set for that
 195          */
 196         if (setcount(set, &saved) == 1) return -(saved + 1);
 197         /*
 198          * If it does, return its number as a negative number.
 199          */
 200         maxptr = (p_set *) new_mem(&set_info);
 201         setptr = (p_set *) set_info.i_ptr;
 202         *maxptr = setalloc();
 203         setunion(*maxptr, set);
 204         return nbytes * (maxptr++ - setptr);
 205 }
 206
 207 int
 208 setcount(set, saved) register p_set set; int *saved; {
 209         register int i, j;
 210
 211         for (j = 0, i = 0; i < ntokens; i++) {
 212                 if (IN(set,i)) {
 213                         j++;
 214                         *saved = i;
 215                 }
 216         }
 217         return j;
 218 }