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