dfa/bset.c

   1 /* This file is part of the Zebra server.
   2    Copyright (C) 1994-2010 Index Data
   3
   4 Zebra is free software; you can redistribute it and/or modify it under
   5 the terms of the GNU General Public License as published by the Free
   6 Software Foundation; either version 2, or (at your option) any later
   7 version.
   8
   9 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  10 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12 for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with this program; if not, write to the Free Software
  16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17
  18 */
  19
  20
  21 #include <stdio.h>
  22 #include <assert.h>
  23
  24 #include <stdlib.h>
  25 #include <string.h>
  26
  27 #include <idzebra/util.h>
  28 #include <bset.h>
  29 #include "imalloc.h"
  30
  31 #define GET_BIT(s,m) (s[(m)/(sizeof(BSetWord)*8)]&(1<<(m&(sizeof(BSetWord)*8-1))))
  32 #define SET_BIT(s,m) (s[(m)/(sizeof(BSetWord)*8)]|=(1<<(m&(sizeof(BSetWord)*8-1))))
  33
  34 BSetHandle *mk_BSetHandle (int size, int chunk)
  35 {
  36     int wsize = 1+size/(sizeof(BSetWord)*8);
  37     BSetHandle *sh;
  38
  39     if (chunk <= 1)
  40         chunk = 32;
  41     sh = (BSetHandle *) imalloc (sizeof(BSetHandle) +
  42                                 chunk*sizeof(BSetWord)*wsize);
  43
  44     sh->size = size;
  45     sh->wsize = wsize;
  46     sh->chunk = chunk * wsize;
  47     sh->offset = 0;
  48     sh->setchain = NULL;
  49     return sh;
  50 }
  51
  52 void rm_BSetHandle (BSetHandle **shp)
  53 {
  54     BSetHandle *sh, *sh1;
  55
  56     assert (shp);
  57     sh = *shp;
  58     assert (sh);
  59     while (sh)
  60     {
  61         sh1 = sh->setchain;
  62         ifree (sh);
  63         sh = sh1;
  64     }
  65 }
  66
  67 int inf_BSetHandle (BSetHandle *sh, long *used, long *allocated)
  68 {
  69     int wsize;
  70
  71     assert (sh);
  72     *used = 0;
  73     *allocated = 0;
  74     wsize = sh->wsize;
  75     do
  76     {
  77         *used += sh->offset;
  78         *allocated += sh->chunk;
  79     } while ((sh = sh->setchain));
  80     return wsize;
  81 }
  82
  83 BSet mk_BSet (BSetHandle **shp)
  84 {
  85     BSetHandle *sh, *sh1;
  86     unsigned off;
  87     assert (shp);
  88     sh = *shp;
  89     assert (sh);
  90
  91     off = sh->offset;
  92     if ((off + sh->wsize) > sh->chunk)
  93     {
  94         sh1 = (BSetHandle *) imalloc (sizeof(BSetHandle) +
  95                                      sh->chunk*sizeof(BSetWord));
  96         sh1->size = sh->size;
  97         sh1->wsize = sh->wsize;
  98         sh1->chunk = sh->chunk;
  99         off = sh1->offset = 0;
 100         sh1->setchain = sh;
 101         sh = *shp = sh1;
 102     }
 103     sh->offset = off + sh->wsize;
 104     return sh->setarray + off;
 105 }
 106
 107 void add_BSet (BSetHandle *sh, BSet dst, unsigned member)
 108 {
 109     assert (dst);
 110     assert (sh);
 111     assert (member <= sh->size);
 112     SET_BIT(dst, member);
 113 }
 114
 115 unsigned test_BSet (BSetHandle *sh, BSet src, unsigned member)
 116 {
 117     assert (src);
 118     assert (sh);
 119     assert (member <= sh->size);
 120     return GET_BIT (src , member) != 0;
 121 }
 122
 123 BSet cp_BSet (BSetHandle *sh, BSet dst, BSet src)
 124 {
 125     assert (sh);
 126     assert (dst);
 127     assert (src);
 128     memcpy (dst, src, sh->wsize * sizeof(BSetWord));
 129     return dst;
 130 }
 131
 132 void res_BSet (BSetHandle *sh, BSet dst)
 133 {
 134     assert (dst);
 135     memset (dst, 0, sh->wsize * sizeof(BSetWord));
 136 }
 137
 138 void union_BSet (BSetHandle *sh, BSet dst, BSet src)
 139 {
 140     int i;
 141     assert (sh);
 142     assert (dst);
 143     assert (src);
 144     for (i=sh->wsize; --i >= 0;)
 145         *dst++ |= *src++;
 146 }
 147
 148 unsigned hash_BSet (BSetHandle *sh, BSet src)
 149 {
 150     int i;
 151     unsigned s = 0;
 152     assert (sh);
 153     assert (src);
 154     for (i=sh->wsize; --i >= 0;)
 155         s += *src++;
 156     return s;
 157 }
 158
 159 void com_BSet (BSetHandle *sh, BSet dst)
 160 {
 161     int i;
 162     assert (sh);
 163     assert (dst);
 164     for (i=sh->wsize; --i >= 0; dst++)
 165         *dst = ~*dst;
 166 }
 167
 168 int eq_BSet (BSetHandle *sh, BSet dst, BSet src)
 169 {
 170     int i;
 171     assert (sh);
 172     assert (dst);
 173     assert (src);
 174     for (i=sh->wsize; --i >= 0;)
 175         if (*dst++ != *src++)
 176             return 0;
 177     return 1;
 178 }
 179
 180 int trav_BSet (BSetHandle *sh, BSet src, unsigned member)
 181 {
 182     int i = sh->size - member;
 183     BSetWord *sw = src+member/(sizeof(BSetWord)*8);
 184     unsigned b = member & (sizeof(BSetWord)*8-1);
 185     while(i >= 0)
 186         if (b == 0 && *sw == 0)
 187         {
 188             member += sizeof(BSetWord)*8;
 189             ++sw;
 190             i -= sizeof(BSetWord)*8;
 191         }
 192         else if (*sw & (1<<b))
 193             return member;
 194         else
 195         {
 196             ++member;
 197             --i;
 198             if (++b == sizeof(BSetWord)*8)
 199             {
 200                 b = 0;
 201                 ++sw;
 202             }
 203         }
 204     return -1;
 205 }
 206
 207 int travi_BSet (BSetHandle *sh, BSet src, unsigned member)
 208 {
 209     int i = sh->size - member;
 210     BSetWord *sw = src+member/(sizeof(BSetWord)*8);
 211     unsigned b = member & (sizeof(BSetWord)*8-1);
 212     while(i >= 0)
 213         if (b == 0 && *sw == (BSetWord) ~ 0)
 214         {
 215             member += sizeof(BSetWord)*8;
 216             ++sw;
 217             i -= sizeof(BSetWord)*8;
 218         }
 219         else if ((*sw & (1<<b)) == 0)
 220             return member;
 221         else
 222         {
 223             ++member;
 224             --i;
 225             if (++b == sizeof(BSetWord)*8)
 226             {
 227                 b = 0;
 228                 ++sw;
 229             }
 230         }
 231     return -1;
 232 }
 233
 234
 235 void pr_BSet (BSetHandle *sh, BSet src)
 236 {
 237     int i;
 238     assert (sh);
 239     assert (src);
 240     for (i=0; (i=trav_BSet(sh,src,i)) != -1; i++)
 241         printf (" %d", i);
 242     putchar ('\n');
 243 }
 244
 245 void pr_charBSet (BSetHandle *sh, BSet src, void (*f) (int))
 246 {
 247     int i0, i1, i;
 248
 249     assert (sh);
 250     assert (src);
 251     i = trav_BSet (sh, src, 0);
 252     while (i != -1)
 253     {
 254         i0 = i;
 255         if (i == '-')
 256             f ('\\');
 257         f(i);
 258         i1 = trav_BSet (sh, src, ++i);
 259         if (i1 == i)
 260         {
 261             do
 262                 ++i;
 263             while ((i1=trav_BSet (sh, src, i)) == i);
 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
 275 /*
 276  * Local variables:
 277  * c-basic-offset: 4
 278  * c-file-style: "Stroustrup"
 279  * indent-tabs-mode: nil
 280  * End:
 281  * vim: shiftwidth=4 tabstop=8 expandtab
 282  */
 283