dfa/set.c

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