dfa/set.c

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: set.c,v $
   7  * Revision 1.3  1995-02-06 10:12:55  adam
   8  * Unused static function rm_SetElement was removed.
   9  *
  10  * Revision 1.2  1995/01/24  16:00:22  adam
  11  * Added -ansi to CFLAGS.
  12  * Some changes to the dfa module.
  13  *
  14  * Revision 1.1  1994/09/26  10:16:57  adam
  15  * First version of dfa module in alex. This version uses yacc to parse
  16  * regular expressions. This should be hand-made instead.
  17  *
  18  */
  19 #include <stdio.h>
  20 #include <assert.h>
  21
  22 #include <stdlib.h>
  23 #include <string.h>
  24
  25 #include <util.h>
  26 #include <set.h>
  27 #include "imalloc.h"
  28
  29
  30 static Set mk_SetElement (SetType st, int n);
  31
  32 SetType mk_SetType (int chunk)
  33 {
  34     SetType st;
  35
  36     assert (chunk > 8 && chunk < 8000);
  37
  38     st = (SetType) 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_SetType (SetType st, long *used, long *allocated)
  48 {
  49     Set 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 (SetElement);
  56 }
  57
  58 SetType rm_SetType (SetType st)
  59 {
  60     Set 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 Set mk_Set (SetType st)
  71 {
  72     assert (st);
  73     return NULL;
  74 }
  75
  76 static Set mk_SetElement (SetType st, int n)
  77 {
  78     Set s;
  79     int i;
  80     assert (st);
  81
  82     assert (st->chunk > 8);
  83     if (! st->freelist)
  84     {
  85         s = (Set) 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_SetElement (SetType st, SetElement *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 Set rm_Set (SetType st, Set s)
 113 {
 114     Set 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 Set add_Set (SetType st, Set s, int n)
 133 {
 134     SetElement dummy;
 135     Set p = &dummy, new;
 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         new = mk_SetElement (st, n);
 143         new->next = p->next;
 144         p->next = new;
 145     }
 146     return dummy.next;
 147 }
 148
 149 Set union_Set (SetType st, Set s1, Set s2)
 150 {
 151     SetElement dummy;
 152     Set 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_SetElement (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_SetElement (st, s2->value);
 179             s2 = s2->next;
 180         }
 181         p->next = NULL;
 182     }
 183     return dummy.next;
 184 }
 185
 186 Set cp_Set (SetType st, Set s)
 187 {
 188     return merge_Set (st, s, NULL);
 189 }
 190
 191 Set merge_Set (SetType st, Set s1, Set s2)
 192 {
 193     SetElement dummy;
 194     Set p;
 195     assert (st);
 196     for (p = &dummy; s1 && s2; p = p->next)
 197         if (s1->value < s2->value)
 198         {
 199             p->next = mk_SetElement (st, s1->value);
 200             s1 = s1->next;
 201         }
 202         else if (s1->value > s2->value)
 203         {
 204             p->next = mk_SetElement (st, s2->value);
 205             s2 = s2->next;
 206         }
 207         else
 208         {
 209             p->next = mk_SetElement (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_SetElement (st, s1->value);
 218         s1 = s1->next;
 219     }
 220     p->next = NULL;
 221     return dummy.next;
 222 }
 223
 224 void pr_Set (SetType st, Set 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_Set (SetType st, Set 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_Set (SetType st, Set s1, Set 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 }