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