dfa/set.c

   1 /* $Id: set.c,v 1.9 2005-01-15 19:38:19 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 <set.h>
  31 #include "imalloc.h"
  32
  33
  34 static Set mk_SetElement (SetType st, int n);
  35
  36 SetType mk_SetType (int chunk)
  37 {
  38     SetType st;
  39
  40     assert (chunk > 8 && chunk < 8000);
  41
  42     st = (SetType) imalloc (sizeof(*st));
  43     assert (st);
  44
  45     st->alloclist = st->freelist = NULL;
  46     st->used = 0;
  47     st->chunk = chunk;
  48     return st;
  49 }
  50
  51 int inf_SetType (SetType st, long *used, long *allocated)
  52 {
  53     Set s;
  54     assert (st);
  55     *used = st->used;
  56     *allocated = 0;
  57     for (s = st->alloclist; s; s = s->next)
  58          *allocated += st->chunk;
  59     return sizeof (SetElement);
  60 }
  61
  62 SetType rm_SetType (SetType st)
  63 {
  64     Set s, s1;
  65     for (s = st->alloclist; (s1 = s);)
  66     {
  67         s = s->next;
  68         ifree (s1);
  69     }
  70     ifree (st);
  71     return NULL;
  72 }
  73
  74 Set mk_Set (SetType st)
  75 {
  76     assert (st);
  77     return NULL;
  78 }
  79
  80 static Set mk_SetElement (SetType st, int n)
  81 {
  82     Set s;
  83     int i;
  84     assert (st);
  85
  86     assert (st->chunk > 8);
  87     if (! st->freelist)
  88     {
  89         s = (Set) imalloc (sizeof(*s) * (1+st->chunk));
  90         assert (s);
  91         s->next = st->alloclist;
  92         st->alloclist = s;
  93         st->freelist = ++s;
  94         for (i=st->chunk; --i > 0; s++)
  95             s->next = s+1;
  96         s->next = NULL;
  97     }
  98     st->used++;
  99     s = st->freelist;
 100     st->freelist = s->next;
 101     s->value = n;
 102     return s;
 103 }
 104
 105 #if 0
 106 static void rm_SetElement (SetType st, SetElement *p)
 107 {
 108     assert (st);
 109     assert (st->used > 0);
 110     p->next = st->freelist;
 111     st->freelist = p;
 112     st->used--;
 113 }
 114 #endif
 115
 116 Set rm_Set (SetType st, Set s)
 117 {
 118     Set s1 = s;
 119     int i = 1;
 120
 121     if (s)
 122     {
 123         while (s->next)
 124         {
 125             s = s->next;
 126             ++i;
 127         }
 128         s->next = st->freelist;
 129         st->freelist = s1;
 130         st->used -= i;
 131         assert (st->used >= 0);
 132     }
 133     return NULL;
 134 }
 135
 136 Set add_Set (SetType st, Set s, int n)
 137 {
 138     SetElement dummy;
 139     Set p = &dummy, snew;
 140     p->next = s;
 141     while (p->next && p->next->value < n)
 142         p = p->next;
 143     assert (p);
 144     if (!(p->next && p->next->value == n))
 145     {
 146         snew = mk_SetElement (st, n);
 147         snew->next = p->next;
 148         p->next = snew;
 149     }
 150     return dummy.next;
 151 }
 152
 153 Set union_Set (SetType st, Set s1, Set s2)
 154 {
 155     SetElement dummy;
 156     Set p;
 157     assert (st);
 158
 159     for (p = &dummy; s1 && s2;)
 160         if (s1->value < s2->value)
 161         {
 162             p = p->next = s1;
 163             s1 = s1->next;
 164         }
 165         else if (s1->value > s2->value)
 166         {
 167             p = p->next = mk_SetElement (st, s2->value);
 168             s2 = s2->next;
 169         }
 170         else
 171         {
 172             p = p->next = s1;
 173             s1 = s1->next;
 174             s2 = s2->next;
 175         }
 176     if (s1)
 177         p->next = s1;
 178     else
 179     {
 180         while (s2)
 181         {
 182             p = p->next = mk_SetElement (st, s2->value);
 183             s2 = s2->next;
 184         }
 185         p->next = NULL;
 186     }
 187     return dummy.next;
 188 }
 189
 190 Set cp_Set (SetType st, Set s)
 191 {
 192     return merge_Set (st, s, NULL);
 193 }
 194
 195 Set merge_Set (SetType st, Set s1, Set s2)
 196 {
 197     SetElement dummy;
 198     Set p;
 199     assert (st);
 200     for (p = &dummy; s1 && s2; p = p->next)
 201         if (s1->value < s2->value)
 202         {
 203             p->next = mk_SetElement (st, s1->value);
 204             s1 = s1->next;
 205         }
 206         else if (s1->value > s2->value)
 207         {
 208             p->next = mk_SetElement (st, s2->value);
 209             s2 = s2->next;
 210         }
 211         else
 212         {
 213             p->next = mk_SetElement (st, s1->value);
 214             s1 = s1->next;
 215             s2 = s2->next;
 216         }
 217     if (!s1)
 218         s1 = s2;
 219     while (s1)
 220     {
 221         p = p->next = mk_SetElement (st, s1->value);
 222         s1 = s1->next;
 223     }
 224     p->next = NULL;
 225     return dummy.next;
 226 }
 227
 228 void pr_Set (SetType st, Set s)
 229 {
 230     assert (st);
 231     while (s)
 232     {
 233         printf (" %d", s->value);
 234         s = s->next;
 235     }
 236     putchar ('\n');
 237 }
 238
 239 unsigned hash_Set (SetType st, Set s)
 240 {
 241     unsigned n = 0;
 242     while (s)
 243     {
 244         n += 11*s->value;
 245         s = s->next;
 246     }
 247     return n;
 248 }
 249
 250 int eq_Set (SetType st, Set s1, Set s2)
 251 {
 252     for (; s1 && s2; s1=s1->next, s2=s2->next)
 253         if (s1->value != s2->value)
 254             return 0;
 255     return s1 == s2;
 256 }