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