maria 1.3.5-4.1 / usr / share / maria / runtime / bushfcn.h

/** @file runtime/bushfcn.h
 * Definitions of low-level tree operations for handling multi-sets
 */

/* Copyright © 2000-2002 Marko Mäkelä (msmakela@tcs.hut.fi).

   This file is part of MARIA, a reachability analyzer and model checker
   for high-level Petri nets.

   MARIA 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.

   MARIA 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.

   The GNU General Public License is often shipped with GNU software, and
   is generally kept in a file called COPYING or LICENSE.  If you do not
   have a copy of the license, write to the Free Software Foundation,
   59 Temple Place, Suite 330, Boston, MA 02111 USA. */

#if !defined CMP3 || !defined EQ || !defined ID
# error "you should not try to use this file directly"
#endif /* !CMP3 || !EQ || !ID */

/** insert an item to the tree
 * @param t	root of the tree
 * @param item	item to be inserted
 * @param count	number of items to insert
 * @return	root of the new tree, or NULL in case of error
 */
struct TREE*
ID(insert) (struct TREE* t, const TYPE* item, card_t count)
{
  if (!t) {
    if (!(t = malloc (sizeof *t)))
      return 0;
    t->up = 0;
  init:
    t->left = t->right = 0;
    t->item = *item;
    t->count = count;
#ifdef RED_BLACK
    balance (t);
#endif /* RED_BLACK */
    ROOT (t);
    return t;
  }
  for (;;) {
    CMP3 ((*item), (t->item), goto less, goto greater);
    /* found */
    if (t->count > CARD_T_MAX - count) { /* cardinality overflow */
    failure:
      ROOT (t); FREE (t); return 0;
    }
    t->count += count;
    ROOT (t); return t;
  less:
    if (t->left) t = t->left;
    else {
      if (!(t->left = malloc (sizeof *t))) goto failure; /* out of memory */
      t->left->up = t, t = t->left;
      goto init;
    }
    continue;
  greater:
    if (t->right) t = t->right;
    else {
      if (!(t->right = malloc (sizeof *t))) goto failure; /* out of memory */
      t->right->up = t, t = t->right;
      goto init;
    }
    continue;
  }
}

/** find an item
 * @param t	root of the tree
 * @param item	item to be sought
 * @return	the corresponding node, or NULL if not found
 */
struct TREE*
ID(find) (struct TREE* t, const TYPE* item)
{
  while (t) {
    CMP3 ((*item), (t->item), goto less, goto greater);
    break;
  less:
    t = t->left; continue;
  greater:
    t = t->right; continue;
  }
  return t;
}

/** multi-set equality comparison
 * @param l	left multi-set to compare
 * @param r	right multi-set to compare
 * @return	whether the two multi-sets are equal
 */
bool_t
ID(equal) (const struct TREE* l,
	   const struct TREE* r)
{
  FIRST (l); FIRST (r);
  while (l && r) {
    while (l && !l->count) NEXT (l);
    while (r && !r->count) NEXT (r);
    if (!(l && r)) break;
    if (l->count != r->count || !(EQ ((l->item), (r->item))))
      return 0;
    NEXT (l); NEXT (r);
  }
  while (l && !l->count) NEXT (l);
  while (r && !r->count) NEXT (r);
  return !l && !r;
}

/** multi-set containment comparison
 * @param l	left multi-set to compare
 * @param r	right multi-set to compare
 * @return	whether the right multi-set contains the left multi-set
 */
bool_t
ID(subset) (const struct TREE* l,
	    const struct TREE* r)
{
  FIRST (l); FIRST (r);
  while (l && r) {
    while (l && !l->count) NEXT (l);
    while (r && !r->count) NEXT (r);
    if (!(l && r)) break;
    CMP3 ((l->item), (r->item), return 0, goto next);
    if (l->count > r->count) return 0;
    NEXT (l);
  next:
    NEXT (r);
  }
  while (l && !l->count) NEXT (l);
  return !l;
}

/** multi-set intersection
 * @param l	multi-set to be intersected
 * @param r	multi-set of items to remove from the left multi-set
 */
void
ID(intersect) (struct TREE* l,
	       const struct TREE* r)
{
  register struct TREE* i = (struct TREE*) r;
  FIRST (i);
  while (i) {
    if (i->count) {
      register struct TREE* t = ID(find) (l, &i->item);
      if (t && t->count > i->count)
	t->count = i->count;
      NEXT (i);
    }
  }
  i = l;
  FIRST (i);
  while (i) {
    if (i->count && !ID(find) ((struct TREE*) r, &i->item))
      i->count = 0;
    NEXT (i);
  }
}

/** multi-set subtraction
 * @param l	multi-set to be subtracted
 * @param r	multi-set of items to remove from the left multi-set
 */
void
ID(subtract) (struct TREE* l,
	      const struct TREE* r)
{
  register const struct TREE* i = r;
  FIRST (i);
  while (i) {
    if (i->count) {
      register struct TREE* t = ID(find) (l, &i->item);
      if (t) {
	if (t->count > i->count)
	  t->count -= i->count;
	else
	  t->count = 0;
      }
    }
    NEXT (i);
  }
}

/** copy constructor
 * @param u	target multi-set
 * @param t	multi-set to be copied to u
 * @return	u augmented with t
 */
struct TREE*
ID(copy) (struct TREE* u,
	  const struct TREE* t)
{
  FIRST (t);
  while (t) {
    if (t->count && !(u = ID(insert) (u, &t->item, t->count)))
      return 0;
    NEXT (t);
  }
  return u;
}

/** multi-copy constructor
 * @param u	target multi-set
 * @param t	multi-set to be copied
 * @param count	number of copies to insert
 * @return	u augmented with count copies of t
 */
struct TREE*
ID(copyc) (struct TREE* u,
	   const struct TREE* t,
	   card_t count)
{
  if (!count)
    return u;
  else if (count == 1)
    return ID(copy) (u, t);
  else {
    card_t maxcount = CARD_T_MAX / count;
    FIRST (t);
    while (t) {
      if (t->count >= maxcount) {
	FREE (u); return 0;
      }
      else if (t->count && !(u = ID(insert) (u, &t->item, t->count * count)))
	return 0;
      NEXT (t);
    }
    return u;
  }
}

#undef ID
#undef CMP3
#undef EQ