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