rx/rxnode.c

   1 /* classes: src_files */
   2
   3 /*      Copyright (C) 1995, 1996 Tom Lord
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU Library General Public License as published by
   7  * the Free Software Foundation; either version 2, or (at your option)
   8  * any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public License
  16  * along with this software; see the file COPYING.  If not, write to
  17  * the Free Software Foundation, 59 Temple Place - Suite 330,
  18  * Boston, MA 02111-1307, USA.
  19  */
  20
  21
  22 \f
  23 #include "rxall.h"
  24 #include "rxnode.h"
  25 \f
  26
  27
  28 #define INITSIZE   8
  29 #define EXPANDSIZE 8
  30
  31 #ifdef __STDC__
  32 static int
  33 rx_init_string(struct rx_string *thisone, char first)
  34 #else
  35 static int
  36 rx_init_string(thisone, first)
  37      struct rx_string *thisone;
  38      char first;
  39 #endif
  40 {
  41   char *tmp;
  42
  43   tmp = (char *) malloc (INITSIZE);
  44
  45   if(!tmp)
  46     return -1;
  47
  48   thisone->contents    = tmp;
  49   thisone->contents[0] = first;
  50   thisone->reallen     = INITSIZE;
  51   thisone->len         = 1;
  52   return 0;
  53 }
  54
  55 #ifdef __STDC__
  56 static void
  57 rx_free_string (struct rx_string *junk)
  58 #else
  59 static void
  60 rx_free_string (junk)
  61      struct rx_string *junk;
  62 #endif
  63 {
  64   free (junk->contents);
  65   junk->len = junk->reallen = 0;
  66   junk->contents = 0;
  67 }
  68
  69
  70 #ifdef __STDC__
  71 int
  72 rx_adjoin_string (struct rx_string *str, char c)
  73 #else
  74 int
  75 rx_adjoin_string (str, c)
  76      struct rx_string *str;
  77      char c;
  78 #endif
  79 {
  80   if (!str->contents)
  81     return rx_init_string (str, c);
  82
  83   if (str->len == str->reallen)
  84     {
  85       char *temp;
  86       temp = (char *) realloc (str->contents, str->reallen + EXPANDSIZE);
  87
  88       if(!temp)
  89         return -1;
  90
  91       str->contents = temp;
  92       str->reallen += EXPANDSIZE;
  93     }
  94
  95   str->contents[str->len++] = c;
  96   return 0;
  97 }
  98
  99
 100 #ifdef __STDC__
 101 static int
 102 rx_copy_string (struct rx_string *to, struct rx_string *from)
 103 #else
 104 static int
 105 rx_copy_string (to, from)
 106         struct rx_string *to;
 107         struct rx_string *from;
 108 #endif
 109 {
 110   char *tmp;
 111
 112   if (from->len)
 113     {
 114       tmp = (char *) malloc (from->reallen);
 115
 116       if (!tmp)
 117         return -1;
 118     }
 119
 120   rx_free_string (to);
 121   to->len      = from->len;
 122   to->reallen  = from->reallen;
 123   to->contents = tmp;
 124
 125   memcpy (to->contents, from->contents, from->reallen);
 126
 127   return 0;
 128 }
 129
 130
 131 #ifdef __STDC__
 132 static int
 133 rx_compare_rx_strings (struct rx_string *a, struct rx_string *b)
 134 #else
 135 static int
 136 rx_compare_rx_strings (a, b)
 137      struct rx_string *a;
 138      struct rx_string *b;
 139 #endif
 140 {
 141   if (a->len != b->len)
 142     return 0;
 143
 144   if (a->len)
 145     return !memcmp (a->contents, b->contents, a->len);
 146   else
 147     return 1;                   /* trivial case: "" == "" */
 148 }
 149
 150
 151 #ifdef __STDC__
 152 static unsigned long
 153 rx_string_hash (unsigned long seed, struct rx_string *str)
 154 #else
 155 static unsigned long
 156 rx_string_hash (seed, str)
 157      unsigned long seed;
 158      struct rx_string *str;
 159 #endif
 160 {
 161   /* From Tcl: */
 162   unsigned long result;
 163   int c;
 164   char * string;
 165   int len;
 166
 167   string = str->contents;
 168   len = str->len;
 169   result = seed;
 170
 171   while (len--)
 172     {
 173       c = *string;
 174       string++;
 175       result += (result<<3) + c;
 176     }
 177   return result;
 178 }
 179
 180
 181 \f
 182
 183 #ifdef __STDC__
 184 struct rexp_node *
 185 rexp_node (int type)
 186 #else
 187 struct rexp_node *
 188 rexp_node (type)
 189      int type;
 190 #endif
 191 {
 192   struct rexp_node *n;
 193
 194   n = (struct rexp_node *) malloc (sizeof (*n));
 195   rx_bzero ((char *)n, sizeof (*n));
 196   if (n)
 197     {
 198       n->type = type;
 199       n->id = -1;
 200       n->refs = 1;
 201     }
 202   return n;
 203 }
 204
 205
 206 /* free_rexp_node assumes that the bitset passed to rx_mk_r_cset
 207  * can be freed using rx_free_cset.
 208  */
 209
 210 #ifdef __STDC__
 211 struct rexp_node *
 212 rx_mk_r_cset (int type, int size, rx_Bitset b)
 213 #else
 214 struct rexp_node *
 215 rx_mk_r_cset (type, size, b)
 216      int type;
 217      int size;
 218      rx_Bitset b;
 219 #endif
 220 {
 221   struct rexp_node * n;
 222   n = rexp_node (type);
 223   if (n)
 224     {
 225       n->params.cset = b;
 226       n->params.cset_size = size;
 227     }
 228   return n;
 229 }
 230
 231
 232 #ifdef __STDC__
 233 struct rexp_node *
 234 rx_mk_r_int (int type, int intval)
 235 #else
 236 struct rexp_node *
 237 rx_mk_r_int (type, intval)
 238      int type;
 239      int intval;
 240 #endif
 241 {
 242   struct rexp_node * n;
 243   n = rexp_node (type);
 244   if (n)
 245     n->params.intval = intval;
 246   return n;
 247 }
 248
 249
 250 #ifdef __STDC__
 251 struct rexp_node *
 252 rx_mk_r_str (int type, char c)
 253 #else
 254 struct rexp_node *
 255 rx_mk_r_str (type, c)
 256      int type;
 257      char c;
 258 #endif
 259 {
 260   struct rexp_node *n;
 261   n = rexp_node (type);
 262   if (n)
 263     rx_init_string (&(n->params.cstr), c);
 264   return n;
 265 }
 266
 267
 268 #ifdef __STDC__
 269 struct rexp_node *
 270 rx_mk_r_binop (int type, struct rexp_node * a, struct rexp_node * b)
 271 #else
 272 struct rexp_node *
 273 rx_mk_r_binop (type, a, b)
 274      int type;
 275      struct rexp_node * a;
 276      struct rexp_node * b;
 277 #endif
 278 {
 279   struct rexp_node * n = rexp_node (type);
 280   if (n)
 281     {
 282       n->params.pair.left = a;
 283       n->params.pair.right = b;
 284     }
 285   return n;
 286 }
 287
 288
 289 #ifdef __STDC__
 290 struct rexp_node *
 291 rx_mk_r_monop (int type, struct rexp_node * a)
 292 #else
 293 struct rexp_node *
 294 rx_mk_r_monop (type, a)
 295      int type;
 296      struct rexp_node * a;
 297 #endif
 298 {
 299   return rx_mk_r_binop (type, a, 0);
 300 }
 301
 302
 303 #ifdef __STDC__
 304 void
 305 rx_free_rexp (struct rexp_node * node)
 306 #else
 307 void
 308 rx_free_rexp (node)
 309      struct rexp_node * node;
 310 #endif
 311 {
 312   if (node && !--node->refs)
 313     {
 314       if (node->params.cset)
 315         rx_free_cset (node->params.cset);
 316       if (node->params.cstr.reallen)
 317         rx_free_string (&(node->params.cstr));
 318       rx_free_rexp (node->params.pair.left);
 319       rx_free_rexp (node->params.pair.right);
 320       rx_free_rexp (node->simplified);
 321       free ((char *)node);
 322     }
 323 }
 324
 325 #ifdef __STDC__
 326 void
 327 rx_save_rexp (struct rexp_node * node)
 328 #else
 329 void
 330 rx_save_rexp (node)
 331      struct rexp_node * node;
 332 #endif
 333 {
 334   if (node)
 335     ++node->refs;
 336 }
 337
 338
 339 #ifdef __STDC__
 340 struct rexp_node *
 341 rx_copy_rexp (int cset_size, struct rexp_node *node)
 342 #else
 343 struct rexp_node *
 344 rx_copy_rexp (cset_size, node)
 345      int cset_size;
 346      struct rexp_node *node;
 347 #endif
 348 {
 349   if (!node)
 350     return 0;
 351   else
 352     {
 353       struct rexp_node *n;
 354       n = rexp_node (node->type);
 355       if (!n)
 356         return 0;
 357
 358       if (node->params.cset)
 359         {
 360           n->params.cset = rx_copy_cset (cset_size,
 361                                          node->params.cset);
 362           if (!n->params.cset)
 363             {
 364               rx_free_rexp (n);
 365               return 0;
 366             }
 367         }
 368
 369       if (node->params.cstr.reallen)
 370         if (rx_copy_string (&(n->params.cstr), &(node->params.cstr)))
 371           {
 372             rx_free_rexp(n);
 373             return 0;
 374           }
 375
 376       n->params.intval = node->params.intval;
 377       n->params.intval2 = node->params.intval2;
 378       n->params.pair.left = rx_copy_rexp (cset_size, node->params.pair.left);
 379       n->params.pair.right = rx_copy_rexp (cset_size, node->params.pair.right);
 380       if (   (node->params.pair.left && !n->params.pair.left)
 381           || (node->params.pair.right && !n->params.pair.right))
 382         {
 383           rx_free_rexp  (n);
 384           return 0;
 385         }
 386       n->id = node->id;
 387       n->len = node->len;
 388       n->observed = node->observed;
 389       return n;
 390     }
 391 }
 392
 393 \f
 394
 395 #ifdef __STDC__
 396 struct rexp_node *
 397 rx_shallow_copy_rexp (int cset_size, struct rexp_node *node)
 398 #else
 399 struct rexp_node *
 400 rx_shallow_copy_rexp (cset_size, node)
 401      int cset_size;
 402      struct rexp_node *node;
 403 #endif
 404 {
 405   if (!node)
 406     return 0;
 407   else
 408     {
 409       struct rexp_node *n;
 410       n = rexp_node (node->type);
 411       if (!n)
 412         return 0;
 413
 414       if (node->params.cset)
 415         {
 416           n->params.cset = rx_copy_cset (cset_size,
 417                                          node->params.cset);
 418           if (!n->params.cset)
 419             {
 420               rx_free_rexp (n);
 421               return 0;
 422             }
 423         }
 424
 425       if (node->params.cstr.reallen)
 426         if (rx_copy_string (&(n->params.cstr), &(node->params.cstr)))
 427           {
 428             rx_free_rexp(n);
 429             return 0;
 430           }
 431
 432       n->params.intval = node->params.intval;
 433       n->params.intval2 = node->params.intval2;
 434       n->params.pair.left = node->params.pair.left;
 435       rx_save_rexp (node->params.pair.left);
 436       n->params.pair.right = node->params.pair.right;
 437       rx_save_rexp (node->params.pair.right);
 438       n->id = node->id;
 439       n->len = node->len;
 440       n->observed = node->observed;
 441       return n;
 442     }
 443 }
 444
 445 \f
 446
 447
 448 #ifdef __STDC__
 449 int
 450 rx_rexp_equal (struct rexp_node * a, struct rexp_node * b)
 451 #else
 452 int
 453 rx_rexp_equal (a, b)
 454      struct rexp_node * a;
 455      struct rexp_node * b;
 456 #endif
 457 {
 458   int ret;
 459
 460   if (a == b)
 461     return 1;
 462
 463   if ((a == 0) || (b == 0))
 464     return 0;
 465
 466   if (a->type != b->type)
 467     return 0;
 468
 469   switch (a->type)
 470     {
 471     case r_cset:
 472       ret = (   (a->params.cset_size == b->params.cset_size)
 473              && rx_bitset_is_equal (a->params.cset_size,
 474                                     a->params.cset,
 475                                     b->params.cset));
 476       break;
 477
 478     case r_string:
 479       ret = rx_compare_rx_strings (&(a->params.cstr), &(b->params.cstr));
 480       break;
 481
 482     case r_cut:
 483       ret = (a->params.intval == b->params.intval);
 484       break;
 485
 486     case r_concat:
 487     case r_alternate:
 488       ret = (   rx_rexp_equal (a->params.pair.left, b->params.pair.left)
 489              && rx_rexp_equal (a->params.pair.right, b->params.pair.right));
 490       break;
 491     case r_opt:
 492     case r_star:
 493     case r_plus:
 494       ret = rx_rexp_equal (a->params.pair.left, b->params.pair.left);
 495       break;
 496     case r_interval:
 497       ret = (   (a->params.intval == b->params.intval)
 498              && (a->params.intval2 == b->params.intval2)
 499              && rx_rexp_equal (a->params.pair.left, b->params.pair.left));
 500       break;
 501     case r_parens:
 502       ret = (   (a->params.intval == b->params.intval)
 503              && rx_rexp_equal (a->params.pair.left, b->params.pair.left));
 504       break;
 505
 506     case r_context:
 507       ret = (a->params.intval == b->params.intval);
 508       break;
 509     default:
 510       return 0;
 511     }
 512   return ret;
 513 }
 514
 515
 516 \f
 517
 518
 519 #ifdef __STDC__
 520 unsigned long
 521 rx_rexp_hash (struct rexp_node * node, unsigned long seed)
 522 #else
 523      unsigned long
 524      rx_rexp_hash (node, seed)
 525      struct rexp_node * node;
 526      unsigned long seed;
 527 #endif
 528 {
 529   if (!node)
 530     return seed;
 531
 532   seed = rx_rexp_hash (node->params.pair.left, seed);
 533   seed = rx_rexp_hash (node->params.pair.right, seed);
 534   seed = rx_bitset_hash (node->params.cset_size, node->params.cset);
 535   seed = rx_string_hash (seed, &(node->params.cstr));
 536   seed += (seed << 3) + node->params.intval;
 537   seed += (seed << 3) + node->params.intval2;
 538   seed += (seed << 3) + node->type;
 539   seed += (seed << 3) + node->id;
 540 #if 0
 541   seed += (seed << 3) + node->len;
 542   seed += (seed << 3) + node->observed;
 543 #endif
 544   return seed;
 545 }