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