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