dfa/bset.c

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