dfa/set.c

   1 /* $Id: set.c,v 1.10 2005-01-15 21:45:42 adam Exp $
   2    Copyright (C) 1995-2005
   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 Zebra; see the file LICENSE.zebra.  If not, write to the
  19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.
  21 */
  22
  23
  24 #include <stdio.h>
  25 #include <assert.h>
  26
  27 #include <stdlib.h>
  28 #include <string.h>
  29
  30 #include <dfaset.h>
  31 #include "imalloc.h"
  32
  33 static DFASet mk_DFASetElement (DFASetType st, int n);
  34
  35 DFASetType mk_DFASetType (int chunk)
  36 {
  37     DFASetType st;
  38
  39     assert (chunk > 8 && chunk < 8000);
  40
  41     st = (DFASetType) imalloc (sizeof(*st));
  42     assert (st);
  43
  44     st->alloclist = st->freelist = NULL;
  45     st->used = 0;
  46     st->chunk = chunk;
  47     return st;
  48 }
  49
  50 int inf_DFASetType (DFASetType st, long *used, long *allocated)
  51 {
  52     DFASet s;
  53     assert (st);
  54     *used = st->used;
  55     *allocated = 0;
  56     for (s = st->alloclist; s; s = s->next)
  57          *allocated += st->chunk;
  58     return sizeof (DFASetElement);
  59 }
  60
  61 DFASetType rm_DFASetType (DFASetType st)
  62 {
  63     DFASet s, s1;
  64     for (s = st->alloclist; (s1 = s);)
  65     {
  66         s = s->next;
  67         ifree (s1);
  68     }
  69     ifree (st);
  70     return NULL;
  71 }
  72
  73 DFASet mk_DFASet (DFASetType st)
  74 {
  75     assert (st);
  76     return NULL;
  77 }
  78
  79 static DFASet mk_DFASetElement (DFASetType st, int n)
  80 {
  81     DFASet s;
  82     int i;
  83     assert (st);
  84
  85     assert (st->chunk > 8);
  86     if (! st->freelist)
  87     {
  88         s = (DFASet) imalloc (sizeof(*s) * (1+st->chunk));
  89         assert (s);
  90         s->next = st->alloclist;
  91         st->alloclist = s;
  92         st->freelist = ++s;
  93         for (i=st->chunk; --i > 0; s++)
  94             s->next = s+1;
  95         s->next = NULL;
  96     }
  97     st->used++;
  98     s = st->freelist;
  99     st->freelist = s->next;
 100     s->value = n;
 101     return s;
 102 }
 103
 104 #if 0
 105 static void rm_DFASetElement (DFASetType st, DFASetElement *p)
 106 {
 107     assert (st);
 108     assert (st->used > 0);
 109     p->next = st->freelist;
 110     st->freelist = p;
 111     st->used--;
 112 }
 113 #endif
 114
 115 DFASet rm_DFASet (DFASetType st, DFASet s)
 116 {
 117     DFASet s1 = s;
 118     int i = 1;
 119
 120     if (s)
 121     {
 122         while (s->next)
 123         {
 124             s = s->next;
 125             ++i;
 126         }
 127         s->next = st->freelist;
 128         st->freelist = s1;
 129         st->used -= i;
 130         assert (st->used >= 0);
 131     }
 132     return NULL;
 133 }
 134
 135 DFASet add_DFASet (DFASetType st, DFASet s, int n)
 136 {
 137     DFASetElement dummy;
 138     DFASet p = &dummy, snew;
 139     p->next = s;
 140     while (p->next && p->next->value < n)
 141         p = p->next;
 142     assert (p);
 143     if (!(p->next && p->next->value == n))
 144     {
 145         snew = mk_DFASetElement (st, n);
 146         snew->next = p->next;
 147         p->next = snew;
 148     }
 149     return dummy.next;
 150 }
 151
 152 DFASet union_DFASet (DFASetType st, DFASet s1, DFASet s2)
 153 {
 154     DFASetElement dummy;
 155     DFASet p;
 156     assert (st);
 157
 158     for (p = &dummy; s1 && s2;)
 159         if (s1->value < s2->value)
 160         {
 161             p = p->next = s1;
 162             s1 = s1->next;
 163         }
 164         else if (s1->value > s2->value)
 165         {
 166             p = p->next = mk_DFASetElement (st, s2->value);
 167             s2 = s2->next;
 168         }
 169         else
 170         {
 171             p = p->next = s1;
 172             s1 = s1->next;
 173             s2 = s2->next;
 174         }
 175     if (s1)
 176         p->next = s1;
 177     else
 178     {
 179         while (s2)
 180         {
 181             p = p->next = mk_DFASetElement (st, s2->value);
 182             s2 = s2->next;
 183         }
 184         p->next = NULL;
 185     }
 186     return dummy.next;
 187 }
 188
 189 DFASet cp_DFASet (DFASetType st, DFASet s)
 190 {
 191     return merge_DFASet (st, s, NULL);
 192 }
 193
 194 DFASet merge_DFASet (DFASetType st, DFASet s1, DFASet s2)
 195 {
 196     DFASetElement dummy;
 197     DFASet p;
 198     assert (st);
 199     for (p = &dummy; s1 && s2; p = p->next)
 200         if (s1->value < s2->value)
 201         {
 202             p->next = mk_DFASetElement (st, s1->value);
 203             s1 = s1->next;
 204         }
 205         else if (s1->value > s2->value)
 206         {
 207             p->next = mk_DFASetElement (st, s2->value);
 208             s2 = s2->next;
 209         }
 210         else
 211         {
 212             p->next = mk_DFASetElement (st, s1->value);
 213             s1 = s1->next;
 214             s2 = s2->next;
 215         }
 216     if (!s1)
 217         s1 = s2;
 218     while (s1)
 219     {
 220         p = p->next = mk_DFASetElement (st, s1->value);
 221         s1 = s1->next;
 222     }
 223     p->next = NULL;
 224     return dummy.next;
 225 }
 226
 227 void pr_DFASet (DFASetType st, DFASet s)
 228 {
 229     assert (st);
 230     while (s)
 231     {
 232         printf (" %d", s->value);
 233         s = s->next;
 234     }
 235     putchar ('\n');
 236 }
 237
 238 unsigned hash_DFASet (DFASetType st, DFASet s)
 239 {
 240     unsigned n = 0;
 241     while (s)
 242     {
 243         n += 11*s->value;
 244         s = s->next;
 245     }
 246     return n;
 247 }
 248
 249 int eq_DFASet (DFASetType st, DFASet s1, DFASet s2)
 250 {
 251     for (; s1 && s2; s1=s1->next, s2=s2->next)
 252         if (s1->value != s2->value)
 253             return 0;
 254     return s1 == s2;
 255 }