X-Git-Url: http://git.indexdata.com/?p=idzebra-moved-to-github.git;a=blobdiff_plain;f=dfa%2Fset.c;h=d92e54c1852072934c9506dcc4d436a4b933c3a1;hp=f567f29309aa87194e2718f7e49c231b78b28887;hb=89d3a004b7c651fd5673abfc192e1472dc4d4197;hpb=ead74d0c3b9d76204494553c61854812eb69bbc7 diff --git a/dfa/set.c b/dfa/set.c index f567f29..d92e54c 100644 --- a/dfa/set.c +++ b/dfa/set.c @@ -1,36 +1,45 @@ -/* - * Copyright (C) 1994, Index Data I/S - * All rights reserved. - * Sebastian Hammer, Adam Dickmeiss - * - * $Log: set.c,v $ - * Revision 1.1 1994-09-26 10:16:57 adam - * First version of dfa module in alex. This version uses yacc to parse - * regular expressions. This should be hand-made instead. - * - */ +/* $Id: set.c,v 1.13 2007-01-15 15:10:15 adam Exp $ + Copyright (C) 1995-2007 + Index Data ApS + +This file is part of the Zebra server. + +Zebra is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +Zebra is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software +Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + +*/ + + #include #include #include #include -#include -#include +#include #include "imalloc.h" +static DFASet mk_DFASetElement (DFASetType st, int n); -static void rm_SetElement (SetType st, SetElement *p); -static Set mk_SetElement (SetType st, int n); - -SetType mk_SetType (int chunk) +DFASetType mk_DFASetType (int chunk) { - SetType st; + DFASetType st; - assert( chunk > 8 && chunk < 8000 ); + assert (chunk > 8 && chunk < 8000); - st = (SetType) imalloc( sizeof(*st) ); - assert( st ); + st = (DFASetType) imalloc (sizeof(*st)); + assert (st); st->alloclist = st->freelist = NULL; st->used = 0; @@ -38,50 +47,50 @@ SetType mk_SetType (int chunk) return st; } -int inf_SetType (SetType st, long *used, long *allocated) +int inf_DFASetType (DFASetType st, long *used, long *allocated) { - Set s; - assert( st ); + DFASet s; + assert (st); *used = st->used; *allocated = 0; - for( s = st->alloclist; s; s = s->next ) + for (s = st->alloclist; s; s = s->next) *allocated += st->chunk; - return sizeof( SetElement ); + return sizeof (DFASetElement); } -SetType rm_SetType (SetType st) +DFASetType rm_DFASetType (DFASetType st) { - Set s, s1; - for( s = st->alloclist; (s1 = s); ) + DFASet s, s1; + for (s = st->alloclist; (s1 = s);) { s = s->next; - ifree( s1 ); + ifree (s1); } - ifree( st ); + ifree (st); return NULL; } -Set mk_Set (SetType st) +DFASet mk_DFASet (DFASetType st) { - assert( st ); + assert (st); return NULL; } -static Set mk_SetElement (SetType st, int n) +static DFASet mk_DFASetElement (DFASetType st, int n) { - Set s; + DFASet s; int i; - assert( st ); + assert (st); - assert( st->chunk > 8 ); - if( ! st->freelist ) + assert (st->chunk > 8); + if (! st->freelist) { - s = (Set) imalloc( sizeof(*s) * (1+st->chunk) ); - assert( s ); + s = (DFASet) imalloc (sizeof(*s) * (1+st->chunk)); + assert (s); s->next = st->alloclist; st->alloclist = s; st->freelist = ++s; - for( i=st->chunk; --i > 0; s++ ) + for (i=st->chunk; --i > 0; s++) s->next = s+1; s->next = NULL; } @@ -92,23 +101,25 @@ static Set mk_SetElement (SetType st, int n) return s; } -static void rm_SetElement (SetType st, SetElement *p) +#if 0 +static void rm_DFASetElement (DFASetType st, DFASetElement *p) { - assert( st ); - assert( st->used > 0 ); + assert (st); + assert (st->used > 0); p->next = st->freelist; st->freelist = p; st->used--; } +#endif -Set rm_Set (SetType st, Set s) +DFASet rm_DFASet (DFASetType st, DFASet s) { - Set s1 = s; + DFASet s1 = s; int i = 1; - if( s ) + if (s) { - while( s->next ) + while (s->next) { s = s->next; ++i; @@ -116,43 +127,43 @@ Set rm_Set (SetType st, Set s) s->next = st->freelist; st->freelist = s1; st->used -= i; - assert( st->used >= 0 ); + assert (st->used >= 0); } return NULL; } -Set add_Set (SetType st, Set s, int n) +DFASet add_DFASet (DFASetType st, DFASet s, int n) { - SetElement dummy; - Set p = &dummy, new; + DFASetElement dummy; + DFASet p = &dummy, snew; p->next = s; - while( p->next && p->next->value < n ) + while (p->next && p->next->value < n) p = p->next; - assert( p ); - if( !(p->next && p->next->value == n ) ) + assert (p); + if (!(p->next && p->next->value == n)) { - new = mk_SetElement( st, n ); - new->next = p->next; - p->next = new; + snew = mk_DFASetElement (st, n); + snew->next = p->next; + p->next = snew; } return dummy.next; } -Set union_Set (SetType st, Set s1, Set s2) +DFASet union_DFASet (DFASetType st, DFASet s1, DFASet s2) { - SetElement dummy; - Set p; - assert( st ); + DFASetElement dummy; + DFASet p; + assert (st); - for( p = &dummy; s1 && s2; ) - if( s1->value < s2->value ) + for (p = &dummy; s1 && s2;) + if (s1->value < s2->value) { p = p->next = s1; s1 = s1->next; } - else if( s1->value > s2->value ) + else if (s1->value > s2->value) { - p = p->next = mk_SetElement( st, s2->value ); + p = p->next = mk_DFASetElement (st, s2->value); s2 = s2->next; } else @@ -161,13 +172,13 @@ Set union_Set (SetType st, Set s1, Set s2) s1 = s1->next; s2 = s2->next; } - if( s1 ) + if (s1) p->next = s1; else { - while( s2 ) + while (s2) { - p = p->next = mk_SetElement( st, s2->value ); + p = p->next = mk_DFASetElement (st, s2->value); s2 = s2->next; } p->next = NULL; @@ -175,59 +186,59 @@ Set union_Set (SetType st, Set s1, Set s2) return dummy.next; } -Set cp_Set (SetType st, Set s) +DFASet cp_DFASet (DFASetType st, DFASet s) { - return merge_Set( st, s, NULL ); + return merge_DFASet (st, s, NULL); } -Set merge_Set (SetType st, Set s1, Set s2) +DFASet merge_DFASet (DFASetType st, DFASet s1, DFASet s2) { - SetElement dummy; - Set p; - assert( st ); - for( p = &dummy; s1 && s2; p = p->next ) - if( s1->value < s2->value ) + DFASetElement dummy; + DFASet p; + assert (st); + for (p = &dummy; s1 && s2; p = p->next) + if (s1->value < s2->value) { - p->next = mk_SetElement( st, s1->value ); + p->next = mk_DFASetElement (st, s1->value); s1 = s1->next; } - else if( s1->value > s2->value ) + else if (s1->value > s2->value) { - p->next = mk_SetElement( st, s2->value ); + p->next = mk_DFASetElement (st, s2->value); s2 = s2->next; } else { - p->next = mk_SetElement( st, s1->value ); + p->next = mk_DFASetElement (st, s1->value); s1 = s1->next; s2 = s2->next; } - if( !s1 ) + if (!s1) s1 = s2; - while( s1 ) + while (s1) { - p = p->next = mk_SetElement( st, s1->value ); + p = p->next = mk_DFASetElement (st, s1->value); s1 = s1->next; } p->next = NULL; return dummy.next; } -void pr_Set (SetType st, Set s) +void pr_DFASet (DFASetType st, DFASet s) { - assert( st ); - while( s ) + assert (st); + while (s) { - printf( " %d", s->value ); + printf (" %d", s->value); s = s->next; } - putchar( '\n' ); + putchar ('\n'); } -unsigned hash_Set (SetType st, Set s) +unsigned hash_DFASet (DFASetType st, DFASet s) { unsigned n = 0; - while( s ) + while (s) { n += 11*s->value; s = s->next; @@ -235,10 +246,18 @@ unsigned hash_Set (SetType st, Set s) return n; } -int eq_Set (SetType st, Set s1, Set s2) +int eq_DFASet (DFASetType st, DFASet s1, DFASet s2) { - for( ; s1 && s2; s1=s1->next, s2=s2->next ) - if( s1->value != s2->value ) + for (; s1 && s2; s1=s1->next, s2=s2->next) + if (s1->value != s2->value) return 0; return s1 == s2; } +/* + * Local variables: + * c-basic-offset: 4 + * indent-tabs-mode: nil + * End: + * vim: shiftwidth=4 tabstop=8 expandtab + */ +