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