dfa/bset.c

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: bset.c,v $
   7  * Revision 1.2  1995-01-24 16:00:21  adam
   8  * Added -ansi to CFLAGS.
   9  * Some changes to the dfa module.
  10  *
  11  * Revision 1.1  1994/09/26  10:16:53  adam
  12  * First version of dfa module in alex. This version uses yacc to parse
  13  * regular expressions. This should be hand-made instead.
  14  *
  15  */
  16 #include <stdio.h>
  17 #include <assert.h>
  18
  19 #include <stdlib.h>
  20 #include <string.h>
  21
  22 #include <util.h>
  23 #include <bset.h>
  24 #include "imalloc.h"
  25
  26 #define GET_BIT(s,m) (s[(m)/(sizeof(BSetWord)*8)]&(1<<(m&(sizeof(BSetWord)*8-1))))
  27 #define SET_BIT(s,m) (s[(m)/(sizeof(BSetWord)*8)]|=(1<<(m&(sizeof(BSetWord)*8-1))))
  28
  29 BSetHandle *mk_BSetHandle (int size, int chunk)
  30 {
  31     int wsize = 1+size/(sizeof(BSetWord)*8);
  32     BSetHandle *sh;
  33
  34     if (chunk <= 1)
  35         chunk = 32;
  36     sh = (BSetHandle *) imalloc (sizeof(BSetHandle) +
  37                                 chunk*sizeof(BSetWord)*wsize);
  38
  39     sh->size = size;
  40     sh->wsize = wsize;
  41     sh->chunk = chunk * wsize;
  42     sh->offset = 0;
  43     sh->setchain = NULL;
  44     return sh;
  45 }
  46
  47 void rm_BSetHandle (BSetHandle **shp)
  48 {
  49     BSetHandle *sh, *sh1;
  50
  51     assert (shp);
  52     sh = *shp;
  53     assert (sh);
  54     while (sh)
  55     {
  56         sh1 = sh->setchain;
  57         ifree (sh);
  58         sh = sh1;
  59     }
  60 }
  61
  62 int inf_BSetHandle (BSetHandle *sh, long *used, long *allocated)
  63 {
  64     int wsize;
  65
  66     assert (sh);
  67     *used = 0;
  68     *allocated = 0;
  69     wsize = sh->wsize;
  70     do
  71     {
  72         *used += sh->offset;
  73         *allocated += sh->chunk;
  74     } while ((sh = sh->setchain));
  75     return wsize;
  76 }
  77
  78 BSet mk_BSet (BSetHandle **shp)
  79 {
  80     BSetHandle *sh, *sh1;
  81     unsigned off;
  82     assert (shp);
  83     sh = *shp;
  84     assert (sh);
  85
  86     off = sh->offset;
  87     if ((off + sh->wsize) > sh->chunk)
  88     {
  89         sh1 = (BSetHandle *) imalloc (sizeof(BSetHandle) +
  90                                      sh->chunk*sizeof(BSetWord));
  91         sh1->size = sh->size;
  92         sh1->wsize = sh->wsize;
  93         sh1->chunk = sh->chunk;
  94         off = sh1->offset = 0;
  95         sh1->setchain = sh;
  96         sh = *shp = sh1;
  97     }
  98     sh->offset = off + sh->wsize;
  99     return sh->setarray + off;
 100 }
 101
 102 void add_BSet (BSetHandle *sh, BSet dst, unsigned member)
 103 {
 104     assert (dst);
 105     assert (sh);
 106     assert (member <= sh->size);
 107     SET_BIT(dst, member);
 108 }
 109
 110 unsigned test_BSet (BSetHandle *sh, BSet src, unsigned member)
 111 {
 112     assert (src);
 113     assert (sh);
 114     assert (member <= sh->size);
 115     return GET_BIT (src , member) != 0;
 116 }
 117
 118 BSet cp_BSet (BSetHandle *sh, BSet dst, BSet src)
 119 {
 120     assert (sh);
 121     assert (dst);
 122     assert (src);
 123     memcpy (dst, src, sh->wsize * sizeof(BSetWord));
 124     return dst;
 125 }
 126
 127 void res_BSet (BSetHandle *sh, BSet dst)
 128 {
 129     assert (dst);
 130     memset (dst, 0, sh->wsize * sizeof(BSetWord));
 131 }
 132
 133 void union_BSet (BSetHandle *sh, BSet dst, BSet src)
 134 {
 135     int i;
 136     assert (sh);
 137     assert (dst);
 138     assert (src);
 139     for (i=sh->wsize; --i >= 0;)
 140         *dst++ |= *src++;
 141 }
 142
 143 unsigned hash_BSet (BSetHandle *sh, BSet src)
 144 {
 145     int i;
 146     unsigned s = 0;
 147     assert (sh);
 148     assert (src);
 149     for (i=sh->wsize; --i >= 0;)
 150         s += *src++;
 151     return s;
 152 }
 153
 154 void com_BSet (BSetHandle *sh, BSet dst)
 155 {
 156     int i;
 157     assert (sh);
 158     assert (dst);
 159     for (i=sh->wsize; --i >= 0; dst++)
 160         *dst = ~*dst;
 161 }
 162
 163 int eq_BSet (BSetHandle *sh, BSet dst, BSet src)
 164 {
 165     int i;
 166     assert (sh);
 167     assert (dst);
 168     assert (src);
 169     for (i=sh->wsize; --i >= 0;)
 170         if (*dst++ != *src++)
 171             return 0;
 172     return 1;
 173 }
 174
 175 int trav_BSet (BSetHandle *sh, BSet src, unsigned member)
 176 {
 177     int i = sh->size - member;
 178     BSetWord *sw = src+member/(sizeof(BSetWord)*8);
 179     unsigned b = member & (sizeof(BSetWord)*8-1);
 180     while(i >= 0)
 181         if (b == 0 && *sw == 0)
 182         {
 183             member += sizeof(BSetWord)*8;
 184             ++sw;
 185             i -= sizeof(BSetWord)*8;
 186         }
 187         else if (*sw & (1<<b))
 188             return member;
 189         else
 190         {
 191             ++member;
 192             --i;
 193             if (++b == sizeof(BSetWord)*8)
 194             {
 195                 b = 0;
 196                 ++sw;
 197             }
 198         }
 199     return -1;
 200 }
 201
 202 int travi_BSet (BSetHandle *sh, BSet src, unsigned member)
 203 {
 204     int i = sh->size - member;
 205     BSetWord *sw = src+member/(sizeof(BSetWord)*8);
 206     unsigned b = member & (sizeof(BSetWord)*8-1);
 207     while(i >= 0)
 208         if (b == 0 && *sw == (BSetWord) ~ 0)
 209         {
 210             member += sizeof(BSetWord)*8;
 211             ++sw;
 212             i -= sizeof(BSetWord)*8;
 213         }
 214         else if ((*sw & (1<<b)) == 0)
 215             return member;
 216         else
 217         {
 218             ++member;
 219             --i;
 220             if (++b == sizeof(BSetWord)*8)
 221             {
 222                 b = 0;
 223                 ++sw;
 224             }
 225         }
 226     return -1;
 227 }
 228
 229
 230 void pr_BSet (BSetHandle *sh, BSet src)
 231 {
 232     int i;
 233     assert (sh);
 234     assert (src);
 235     for (i=0; (i=trav_BSet(sh,src,i)) != -1; i++)
 236         printf (" %d", i);
 237     putchar ('\n');
 238 }
 239
 240 void pr_charBSet (BSetHandle *sh, BSet src, void (*f) (int))
 241 {
 242     int i0, i1, i;
 243
 244     assert (sh);
 245     assert (src);
 246     i = trav_BSet (sh, src, 0);
 247     while (i != -1)
 248     {
 249         i0 = i;
 250         if (i == '-')
 251             f ('\\');
 252         f(i);
 253         i1 = trav_BSet (sh, src, ++i);
 254         if (i1 == i)
 255         {
 256             while ((i1=trav_BSet (sh, src, ++i)) == i)
 257                 ;
 258             if (i != i0+2)
 259                 f ('-');
 260             if (i-1 == '-')
 261                 f ('\\');
 262             f(i-1);
 263         }
 264         i = i1;
 265     }
 266 }
 267
 268