dfa/set.c

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