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