dfa/bset.c

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