Logo Search packages:      
Sourcecode: bazaar version File versions

bitset-tree.c

/* tag: Tom Lord Tue Dec  4 14:41:34 2001 (bitset-tree.c)
 */
/* bitset-tree.c -
 *
 ****************************************************************
 * Copyright (C) 2000 Tom Lord
 * 
 * See the file "COPYING" for further information about
 * the copyright and warranty status of this work.
 */


#include "hackerlab/mem/mem.h"
#include "hackerlab/bitsets/bitset-tree.h"


/************************************************************************
 *(h1 "Bitset Trees"
 *    :includes ("hackerlab/bitsets/bitset-tree.h"))
 * 
 * A "bitset tree" is a sparse representation for a large bitset which
 * is mostly homogenous (i.e., containing large runs which are all 0
 * or all 1).  A bitset tree saves time and memory by compressing the
 * representation of homogenous subsets.
 * 
 * It is important to note that if your bitsets do not contain large,
 * contiguous, homogenous (all 0 or all 1) subsets, then bitset trees
 * are of no help -- they add space and time overhead and offer no
 * advantage.  If your sets do have homogenous subsets, bitset trees
 * can lead to significant space and time savings.
 * 
 * Usually, you will not want to use bitset trees directly.  Instead,
 * you will want to use ``shared bitset trees''.  (See xref:"Shared
 * Bitset Trees".)  Nevertheless, even if you will use shared bitset
 * trees, it is important to understand how bitset trees work.
 */


/************************************************************************
 *(h2 "The Bitset Tree Data Structure")
 * 
 * This section describes the internal representation of bitset trees.
 * The public interface to bitset trees hides most of the details of
 * this representation -- but understanding it will help you predict
 * the performance of programs which use bitset trees, and design
 * bitset tree rules.  (See xref:"Bitset Tree Rules".)
 * 
 * Bitset trees are defined recursively: a bitset tree is an array of
 * (pointers to) bitset trees.  The leaf nodes of a bitset trees are
 * (pointers to) ordinary bitsets.  (See xref:"Flat Bitsets".)
 * 
 * A bitset tree represents a single logical bitset which is the
 * concatenation of its sub-trees.  Each subtree at a given distance
 * from the root has the same number of members and the same depth and
 * branching structure.
 * 
 * As an optimization, if a particular subtree is all 0s, that subtree
 * may be replaced by a null pointer.  If a particular subtree is all
 * 1s, it may be replaced by the pointer `(bits_tree)-1'.  Whenever
 * practical, functions which operate on bitset trees use this
 * optimization automatically.  For example, `bits_fill_range' will
 * store a subtree of all 0s or all 1s efficiently.  In some cases,
 * the optimization is not practical.  For example, `bits_adjoin'
 * does not attempt to optimize the subtrees it modifies.
 * 
 * The function `bits_tree_compact' recursively searches a bitset tree,
 * replacing homogenous sub-trees with 0 or `-1'.
 * 
 */

/*(include-documentation "bitset-tree.h")
 */



/************************************************************************
 *(h2 "Allocating Bitset Trees")
 * 
 * 
 * 
 */

/*(c bits_tree_alloc)
 * bits_tree bits_tree_alloc (alloc_limits lim,
 *                            struct bits_tree_rule * rule);
 * 
 * Allocate a new bitset tree.
 * 
 * `lim' describes allocation limits that apply to this bitset tree.
 * For more information about allocation limits, see xref:"Allocation
 * With Limitations".
 * 
 * `rule' describes the branching structure of the bitset tree.
 * See xref:"Bitset Tree Rules".
 * 
 * The new set is initialized to all `0's.
 * 
 * If allocation fails, 0 is returned.
 */
bits_tree
bits_tree_alloc (alloc_limits lim,
             struct bits_tree_rule * rule)
{
  bits_tree answer;

  if (!rule->fanout)
    return (bits_tree)bitset_alloc (lim, rule->subset_size);

  answer = (bits_tree)lim_malloc (lim, rule->fanout * sizeof (bits_tree));
  if (answer)
    mem_set0 ((t_uchar *)answer, rule->fanout * sizeof (bits_tree));
  return answer;
}


/*(c bits_tree_free)
 * void bits_tree_free (alloc_limits lim,
 *                      struct bits_tree_rule * rule,
 *                      bits_tree b);
 * 
 * Free all storage associated with a bitset tree.
 * 
 * `lim' describes allocation limits that apply to this bitset tree.
 * For more information about allocation limits, see xref:"Allocation
 * With Limitations".
 * 
 * `rule' describes the branching structure of the bitset tree.
 * See xref:"Bitset Tree Rules".
 * 
 */
void
bits_tree_free (alloc_limits lim,
            struct bits_tree_rule * rule,
            bits_tree b)
{
  int x;

  if (!rule->fanout)
    {
      bitset_free (lim, (bitset)b);
      return;
    }

  for (x = 0; x < rule->fanout; ++x)
    {
      if (   (((bits_tree *)b)[x] != bits_tree_full_bitset)
        && (((bits_tree *)b)[x] != bits_tree_empty_bitset))
      bits_tree_free (lim, rule + 1, ((bits_tree *)b)[x]);
    }
  lim_free (lim, (t_uchar *)b);
}


/*(c bits_tree_compact)
 * bit_t bits_tree_compact (alloc_limits lim,
 *                          struct bits_tree_rule * rule,
 *                          bits_tree a);
 * 
 * Optimize a bitset tree by compacting homogenous
 * sub-trees.  See xref:"The Bitset Tree Data Structure".
 * 
 * `lim' describes allocation limits that apply to this bitset tree.
 * For more information about allocation limits, see xref:"Allocation
 * With Limitations".
 * 
 * `rule' describes the branching structure of the bitset tree.
 * See xref:"Bitset Tree Rules".
 * 
 * The population size of the set is returned.
 */
bit_t
bits_tree_compact (alloc_limits lim,
               struct bits_tree_rule * rule,
               bits_tree a)
{
  int x;
  bit_t pop;

  if (!rule->fanout)
    {
      return bits_tree_population (lim, rule, a);
    }

  pop = 0;
  for (x = 0; x < rule->fanout; ++x)
    {
      if (((bits_tree *)a)[x] == bits_tree_full_bitset)
      {
        pop += rule->subset_size;
      }
      else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
      continue;
      else 
      {
        bit_t sub_pop;

        sub_pop = bits_tree_compact (lim, rule + 1, ((bits_tree *)a)[x]);

        if (sub_pop == 0)
          {
            bits_tree_free (lim, rule + 1, ((bits_tree *)a)[x]);
            ((bits_tree *)a)[x] = bits_tree_empty_bitset;
          }
        else if (sub_pop == rule->subset_size)
          {
            bits_tree_free (lim, rule + 1, ((bits_tree *)a)[x]);
            ((bits_tree *)a)[x] = bits_tree_full_bitset;
          }

        pop += sub_pop;
      }
    }
  return pop;
}


/*(c bits_tree_dup)
 * bits_tree bits_tree_dup (alloc_limits lim,
 *                          struct bits_tree_rule * rule,
 *                          bits_tree a);
 * 
 * Allocate a new copy of bitset tree `a'.
 * 
 * `lim' describes allocation limits that apply to this bitset tree.
 * For more information about allocation limits, see xref:"Allocation
 * With Limitations".
 * 
 * `rule' describes the branching structure of the bitset tree.
 * See xref:"Bitset Tree Rules".
 * 
 * If allocation fails, 0 is returned.
 */
bits_tree
bits_tree_dup (alloc_limits lim,
             struct bits_tree_rule * rule,
             bits_tree a)
{
  bits_tree answer;
  int x;

  if (!rule->fanout)
    {
      return (bits_tree)bitset_dup (lim, rule->subset_size, (bitset)a);
    }

  answer = (bits_tree)lim_malloc (lim, rule->fanout * sizeof (bits_tree));
  if (answer)
    {
      for (x = 0; x < rule->fanout; ++x)
      {
        if (((bits_tree *)a)[x] == bits_tree_full_bitset)
          ((bits_tree *)answer)[x] = bits_tree_full_bitset;
        else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
          ((bits_tree *)answer)[x] = bits_tree_empty_bitset;
        else
          {
            ((bits_tree *)answer)[x] = bits_tree_dup (lim, rule + 1, ((bits_tree *)a)[x]);
            if ((!((bits_tree *)answer)[x]) && ((bits_tree *)a)[x])
            {
              int y;
              for (y = x; y < rule->fanout; ++y)
                ((bits_tree *)answer)[y] = bits_tree_empty_bitset;
              bits_tree_free (lim, rule, answer);
              return 0;
            }
          }
      }
    }
  return answer;
}


/************************************************************************
 *h2 "Accessing Individual Subsets of a Bitset Tree")
 * 
 * 
 * 
 */

/*c bits_tree_get_subset)
 * int bits_tree_get_subset (bitset_subset * answer,
 *                           alloc_limits lim,
 *                           struct bits_tree_rule * rule,
 *                           bits_tree b,
 *                           bit_t n);
 * 
 * Return (in `*answer') the `bitset_subet' containing bit `n' of
 * bitset tree `b'.  See xref:"bitset_subset".
 * 
 * `lim' describes allocation limits that apply to this
 * bitset tree.  For more information about allocation limits, see
 * xref:"Allocation With Limitations".
 * 
 * `rule' describes the branching structure of the bitset tree.
 * See xref:"Bitset Tree Rules".
 * 
 * If the indicated subset does not exist (because it is part of
 * a homogenous subtree whose representation has been optimized)
 * the corresponding subtree is newly allocated.
 * 
 * If allocation fails, -1 is returned.  Otherwise, 0 is returned.
 */
int
bits_tree_get_subset (bitset_subset * answer,
                  alloc_limits lim,
                  struct bits_tree_rule * rule,
                  bits_tree b,
                  bit_t n)
{
  int bs;

  if (!rule->fanout)
    {
      *answer = ((bitset)b)[bitset_which_subset (n)];
      return 0;
    }

  bs = bits_tree_which_bitset (lim, rule, n);

  if (((bits_tree *)b)[bs] == bits_tree_empty_bitset)
    {
      ((bits_tree *)b)[bs] = bits_tree_alloc (lim, rule + 1);
      if (!((bits_tree *)b)[bs])
      {
        ((bits_tree *)b)[bs] = bits_tree_empty_bitset;
        return -1;
      }
    }
  else if (((bits_tree *)b)[bs] == bits_tree_full_bitset)
    {
      ((bits_tree *)b)[bs] = bits_tree_alloc (lim, rule + 1);
      if (!((bits_tree *)b)[bs])
      {
        ((bits_tree *)b)[bs] = bits_tree_full_bitset;
        return -1;
      }
      bits_tree_fill (lim, rule + 1, ((bits_tree *)b)[bs]);
    }

  return bits_tree_get_subset (answer, lim, rule + 1, ((bits_tree *)b)[bs], bits_tree_which_bit(lim, rule, n));
}


/************************************************************************
 *(h2 "Operations on Bitset Trees")
 * 
 * 
 * Each of the operations defined for flat bitsets has a corresponding
 * operation for bitset trees.  See xref:"Flat Bitsets".
 * 
 * The bitset tree operations are:
 * 
 * 
 * |$bits_tree_is_member| |$bits_tree_is_equal| |$bits_tree_is_subset|
 * |$bits_tree_is_empty| |$bits_tree_is_full| |$bits_tree_is_empty_range|
 * |$bits_tree_is_full_range| |$bits_tree_adjoin| |$bits_tree_remove|
 * |$bits_tree_toggle| |$bits_tree_clear| |$bits_tree_fill| |$bits_tree_clear_range|
 * |$bits_tree_fill_range| |$bits_tree_complement| |$bits_tree_assign|
 * |$bits_tree_union| |$bits_tree_intersection| |$bits_tree_difference|
 * |$bits_tree_revdifference| |$bits_tree_xor| |$bits_tree_population|
 * |$bits_tree_population_range| |$bits_tree_ffs| |$bits_tree_ffc|
 * |$bits_tree_ffs_range| |$bits_tree_ffc_range|
 * 
 *     int bits_tree_is_member (alloc_limits lim,
 *                       struct bits_tree_rule * rule,
 *                       bits_tree b,
 *                       int n);
 *     int bits_tree_is_equal (alloc_limits lim,
 *                      struct bits_tree_rule * rule,
 *                      bits_tree a, bits_tree b);
 *     int bits_tree_is_subset (alloc_limits lim,
 *                       struct bits_tree_rule * rule,
 *                       bits_tree a,
 *                       bits_tree b);
 *     int bits_tree_is_empty (alloc_limits lim,
 *                      struct bits_tree_rule * rule,
 *                      bits_tree a);
 *     int bits_tree_is_full (alloc_limits lim,
 *                       struct bits_tree_rule * rule,
 *                       bits_tree a);
 *     int bits_tree_is_empty_range (alloc_limits lim,
 *                            struct bits_tree_rule * rule,
 *                            bits_tree a,
 *                            int from,
 *                            int to);
 *     int bits_tree_is_full_range (alloc_limits lim,
 *                           struct bits_tree_rule * rule,
 *                           bits_tree a,
 *                           int from,
 *                           int to);
 *     int bits_tree_adjoin (alloc_limits lim,
 *                      struct bits_tree_rule * rule,
 *                      bits_tree b,
 *                      int n);
 *     int bits_tree_remove (alloc_limits lim,
 *                      struct bits_tree_rule * rule,
 *                      bits_tree b, int n);
 *     int bits_tree_toggle (alloc_limits lim,
 *                      struct bits_tree_rule * rule,
 *                      bits_tree b,
 *                      int n);
 *     void bits_tree_clear (alloc_limits lim,
 *                      struct bits_tree_rule * rule,
 *                      bits_tree b);
 *     void bits_tree_fill (alloc_limits lim,
 *                     struct bits_tree_rule * rule,
 *                     bits_tree b);
 *     int bits_tree_clear_range (alloc_limits lim,
 *                         struct bits_tree_rule * rule,
 *                         bits_tree b,
 *                         int from,
 *                         int to);
 *     int bits_tree_fill_range (alloc_limits lim,
 *                        struct bits_tree_rule * rule,
 *                        bits_tree b,
 *                        int from,
 *                        int to);
 *     void bits_tree_complement (alloc_limits lim,
 *                         struct bits_tree_rule * rule,
 *                         bits_tree b);
 *     int bits_tree_assign (alloc_limits lim,
 *                      struct bits_tree_rule * rule,
 *                      bits_tree a,
 *                      bits_tree b);
 *     int bits_tree_union (alloc_limits lim,
 *                     struct bits_tree_rule * rule,
 *                     bits_tree a,
 *                     bits_tree b);
 *     int bits_tree_intersection (alloc_limits lim,
 *                          struct bits_tree_rule * rule,
 *                          bits_tree a,
 *                          bits_tree b);
 *     int bits_tree_difference (alloc_limits lim,
 *                        struct bits_tree_rule * rule,
 *                        bits_tree a,
 *                        bits_tree b);
 *     int bits_tree_revdifference (alloc_limits lim,
 *                           struct bits_tree_rule * rule,
 *                           bits_tree a,
 *                           bits_tree b);
 *     int bits_tree_xor (alloc_limits lim,
 *                   struct bits_tree_rule * rule,
 *                   bits_tree a,
 *                   bits_tree b);
 *     int bits_tree_population (alloc_limits lim,
 *                        struct bits_tree_rule * rule,
 *                        bits_tree a);
 *     int bits_tree_population_range (alloc_limits lim,
 *                            struct bits_tree_rule * rule,
 *                            bits_tree a, int from, int to);
 *     int bits_tree_ffs (alloc_limits lim,
 *                   struct bits_tree_rule * rule,
 *                   bits_tree b);
 *     int bits_tree_ffc (alloc_limits lim,
 *                   struct bits_tree_rule * rule,
 *                   bits_tree b);
 *     int bits_tree_ffs_range (alloc_limits lim,
 *                       struct bits_tree_rule * rule,
 *                       bits_tree b,
 *                       int from,
 *                       int to);
 *     int bits_tree_ffc_range (alloc_limits lim,
 *                       struct bits_tree_rule * rule,
 *                       bits_tree b,
 *                       int from,
 *                       int to);
 *
 * Each function performs the same operation as the corresponding
 * `bitset_' function (replace `bits_tree' with `bitset_'.)
 * For documentation, see xref:"Flat Bitsets".  For that reason,
 * the `bits_tree_' functions are not individually documented.
 * 
 * Each `bits_tree' function takes two initial parameters, `lim' and `rule'.
 * 
 * `lim' describes allocation limits that apply to the bitset tree(s)
 * being operated upon.  For more information about allocation limits,
 * see xref:"Allocation With Limitations".
 * 
 * `rule' describes the branching structure of the bitset trees.
 * See xref:"Bitset Tree Rules".
 * 
 * These functions:
 * 
 *    bits_tree_adjoin
 *    bits_tree_remove
 *    bits_tree_toggle
 *    bits_tree_clear
 *    bits_tree_fill
 *    bits_tree_clear_range
 *    bits_tree_fill_range
 *    bits_tree_complement
 *    bits_tree_assign
 *    bits_tree_union
 *    bits_tree_intersection
 *    bits_tree_difference
 *    bits_tree_revdifference
 *    bits_tree_xor
 * 
 * return a value of type `int'. All of them will sometimes allocate
 * memory. 
 * 
 * If an allocation fails, these functions return -1 and have
 * indeterminate side effect on the set being operated upon.
 * 
 * If all allocations succeed, they return 0 (and have the intended
 * side effect on the set being operated upon).
 */

int
bits_tree_is_member (alloc_limits lim,
                 struct bits_tree_rule * rule,
                 bits_tree b,
                 int n)
{
  int bs;

  if (!rule->fanout)
    {
      return bitset_is_member ((bitset)b, n);
    }

  bs = bits_tree_which_bitset (lim, rule, n);
  if (((bits_tree *)b)[bs] == bits_tree_full_bitset)
    return 1;
  else if (((bits_tree *)b)[bs] == bits_tree_empty_bitset)
    return 0;
  else
    return bits_tree_is_member (lim, rule + 1, ((bits_tree *)b)[bs], bits_tree_which_bit (lim, rule, n));
}


static int
bits_tree_is_full_bitset (alloc_limits lim,
                    struct bits_tree_rule * rule,
                    bits_tree a)
{
  return (   (a == bits_tree_full_bitset)
        || (   (a != bits_tree_empty_bitset)
            && (rule->subset_size == bits_tree_population (lim, rule + 1, a))));
}


static int
bits_tree_is_empty_bitset (alloc_limits lim,
                     struct bits_tree_rule * rule,
                     bits_tree a)
{
  return (   (a == bits_tree_empty_bitset)
        || (   (a != bits_tree_full_bitset)
            && (0 == bits_tree_population (lim, rule + 1, a))));
}



int
bits_tree_is_equal (alloc_limits lim,
                struct bits_tree_rule * rule,
                bits_tree a, bits_tree b)
{
  int x;

  if (!rule->fanout)
    {
      return bitset_is_equal (rule->subset_size, (bitset)a, (bitset)b);
    }

  for (x = 0; x < rule->fanout; ++x)
    {
      if (((bits_tree *)a)[x] == bits_tree_full_bitset)
      {
        if (!bits_tree_is_full_bitset (lim, rule, ((bits_tree *)b)[x]))
          return 0;
      }
      else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
      {
        if (!bits_tree_is_empty_bitset (lim, rule, ((bits_tree *)b)[x]))
          return 0;
      }
      else if (((bits_tree *)b)[x] == bits_tree_full_bitset)
      {
        if (!bits_tree_is_full_bitset (lim, rule, ((bits_tree *)a)[x]))
          return 0;
      }
      else if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
      {
        if (!bits_tree_is_empty_bitset (lim, rule, ((bits_tree *)a)[x]))
          return 0;
      }
      else if (!bits_tree_is_equal (lim, rule + 1, ((bits_tree *)a)[x], ((bits_tree *)b)[x]))
        return 0;
    }
  return 1;
}


int
bits_tree_is_subset (alloc_limits lim,
                 struct bits_tree_rule * rule,
                 bits_tree a,
                 bits_tree b)
{
  int x;

  if (!rule->fanout)
    {
      return bitset_is_subset (rule->subset_size, (bitset)a, (bitset)b);
    }

  for (x = 0; x < rule->fanout; ++x)
    {
      if (((bits_tree *)a)[x] == bits_tree_full_bitset)
      continue;
      else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
      {
        if (!bits_tree_is_empty_bitset (lim, rule, ((bits_tree *)b)[x]))
          return 0;
      }
      else if (((bits_tree *)b)[x] == bits_tree_full_bitset)
      return 0;
      else if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
      continue;
      else
      if (!bits_tree_is_subset (lim, rule + 1, ((bits_tree *)a)[x], ((bits_tree *)b)[x]))
        return 0;
    }
  return 1;
}


int
bits_tree_is_empty (alloc_limits lim,
                struct bits_tree_rule * rule,
                bits_tree a)
{
  int x;

  if (!rule->fanout)
    {
      return bitset_is_empty (rule->subset_size, (bitset)a);
    }

  for (x = 0; x < rule->fanout; ++x)
    {
      if (!bits_tree_is_empty_bitset (lim, rule, ((bits_tree *)a)[x]))
      return 0;
    }
  return 1;
}


int
bits_tree_is_full (alloc_limits lim,
               struct bits_tree_rule * rule,
               bits_tree a)
{
  int x;

  if (!rule->fanout)
    {
      return bitset_is_full (rule->subset_size, (bitset)a);
    }

  for (x = 0; x < rule->fanout; ++x)
    {
      if (!bits_tree_is_full_bitset (lim, rule, ((bits_tree *)a)[x]))
      return 0;
    }
  return 1;
}


int
bits_tree_is_empty_range (alloc_limits lim,
                    struct bits_tree_rule * rule,
                    bits_tree a,
                    int from,
                    int to)
{
  int first_bs;
  int first_bit;
  int last_bs;
  int last_bit;

  if (!rule->fanout)
    {
      return bitset_is_empty_range ((bitset)a, from, to);
    }

  if (to <= from)
    return 1;

  first_bs = bits_tree_which_bitset (lim, rule, from);
  first_bit = bits_tree_which_bit (lim, rule, from);

  last_bs = bits_tree_which_bitset (lim, rule, to);
  last_bit = bits_tree_which_bit (lim, rule, to);

  if (first_bs == last_bs)
    {
      if (((bits_tree *)a)[first_bs] == bits_tree_full_bitset)
      return 0;
      if (((bits_tree *)a)[first_bs] == bits_tree_empty_bitset)
      return 1;
      return bits_tree_is_empty_range (lim, rule + 1, ((bits_tree *)a)[first_bs], first_bit, last_bit);
    }
  else
    {
      int x;

      if (   (((bits_tree *)a)[first_bs] == bits_tree_full_bitset)
        || (   (((bits_tree *)a)[first_bs] != bits_tree_empty_bitset)
            && !bits_tree_is_empty_range (lim, rule + 1, ((bits_tree *)a)[first_bs], first_bit, rule->subset_size)))
      return 0;

      if (   last_bit
        && ((((bits_tree *)a)[last_bs] == bits_tree_full_bitset)
            || (   (((bits_tree *)a)[last_bs] != bits_tree_empty_bitset)
              && !bits_tree_is_empty_range (lim, rule + 1, ((bits_tree *)a)[last_bs], 0, last_bit))))
      return 0;

      for (x = first_bs + 1; x < last_bs; ++x)
      {
        if (!bits_tree_is_empty_bitset (lim, rule, ((bits_tree *)a)[x]))
          return 0;
      }
      return 1;
    }
}

int
bits_tree_is_full_range (alloc_limits lim,
                   struct bits_tree_rule * rule,
                   bits_tree a,
                   int from,
                   int to)
{
  int first_bs;
  int first_bit;
  int last_bs;
  int last_bit;

  if (!rule->fanout)
    {
      return bitset_is_full_range ((bitset)a, from, to);
    }

  if (to <= from)
    return 1;

  first_bs = bits_tree_which_bitset (lim, rule, from);
  first_bit = bits_tree_which_bit (lim, rule, from);

  last_bs = bits_tree_which_bitset (lim, rule, to);
  last_bit = bits_tree_which_bit (lim, rule, to);

  if (first_bs == last_bs)
    {
      if (((bits_tree *)a)[first_bs] == bits_tree_full_bitset)
      return 1;
      if (((bits_tree *)a)[first_bs] == bits_tree_empty_bitset)
      return 0;
      return bits_tree_is_full_range (lim, rule + 1, ((bits_tree *)a)[first_bs], first_bit, last_bit);
    }
  else
    {
      int x;

      if (   (((bits_tree *)a)[first_bs] == bits_tree_empty_bitset)
        || (   (((bits_tree *)a)[first_bs] != bits_tree_full_bitset)
            && !bits_tree_is_full_range (lim, rule + 1, ((bits_tree *)a)[first_bs], first_bit, rule->subset_size)))
      return 0;

      if (   last_bit
        && ((((bits_tree *)a)[last_bs] == bits_tree_empty_bitset)
            || (   (((bits_tree *)a)[last_bs] != bits_tree_full_bitset)
              && !bits_tree_is_full_range (lim, rule + 1, ((bits_tree *)a)[last_bs], 0, last_bit))))
      return 0;

      for (x = first_bs + 1; x < last_bs; ++x)
      {
        if (!bits_tree_is_full_bitset (lim, rule, ((bits_tree *)a)[x]))
          return 0;
      }
      return 1;
    }
}

int
bits_tree_adjoin (alloc_limits lim,
              struct bits_tree_rule * rule,
              bits_tree b,
              int n)
{
  int bs;

  if (!rule->fanout)
    {
      bitset_adjoin ((bitset)b, n);
      return 0;
    }

  bs = bits_tree_which_bitset (lim, rule, n);
  if (((bits_tree *)b)[bs] == bits_tree_full_bitset)
    return 0;

  if (((bits_tree *)b)[bs] == bits_tree_empty_bitset)
    {
      ((bits_tree *)b)[bs] = bits_tree_alloc (lim, rule + 1);
      if (!((bits_tree *)b)[bs])
      {
        ((bits_tree *)b)[bs] = bits_tree_empty_bitset;
        return -1;
      }
    }

  return bits_tree_adjoin (lim, rule + 1, ((bits_tree *)b)[bs], bits_tree_which_bit (lim, rule, n));
}


int
bits_tree_remove (alloc_limits lim,
              struct bits_tree_rule * rule,
              bits_tree b, int n)
{
  int bs;

  if (!rule->fanout)
    {
      bitset_remove ((bitset)b, n);
      return 0;
    }

  bs = bits_tree_which_bitset (lim, rule, n);

  if (((bits_tree *)b)[bs] == bits_tree_empty_bitset)
    return 0;

  if (((bits_tree *)b)[bs] == bits_tree_full_bitset)
    {
      ((bits_tree *)b)[bs] = bits_tree_alloc (lim, rule + 1);
      if (!((bits_tree *)b)[bs])
      {
        ((bits_tree *)b)[bs] = bits_tree_full_bitset;
        return -1;
      }
      bits_tree_fill (lim, rule + 1, ((bits_tree *)b)[bs]);
    }
  return bits_tree_remove (lim, rule + 1, ((bits_tree *)b)[bs], bits_tree_which_bit (lim, rule, n));
}


int
bits_tree_toggle (alloc_limits lim,
              struct bits_tree_rule * rule,
              bits_tree b,
              int n)
{
  int bs;

  if (!rule->fanout)
    {
      bitset_toggle ((bitset)b, n);
      return 0;
    }

  bs = bits_tree_which_bitset (lim, rule, n);

  if (((bits_tree *)b)[bs] == bits_tree_empty_bitset)
    {
      ((bits_tree *)b)[bs] = bits_tree_alloc (lim, rule + 1);
      if (!((bits_tree *)b)[bs])
      {
        ((bits_tree *)b)[bs] = bits_tree_empty_bitset;
        return -1;
      }
    }
  else if (((bits_tree *)b)[bs] == bits_tree_full_bitset)
    {
      ((bits_tree *)b)[bs] = bits_tree_alloc (lim, rule + 1);
      if (!((bits_tree *)b)[bs])
      {
        ((bits_tree *)b)[bs] = bits_tree_full_bitset;
        return -1;
      }
      bits_tree_fill (lim, rule + 1, ((bits_tree *)b)[bs]);
    }
  return bits_tree_toggle (lim, rule + 1, ((bits_tree *)b)[bs], bits_tree_which_bit (lim, rule, n));
}


void
bits_tree_clear (alloc_limits lim,
             struct bits_tree_rule * rule,
             bits_tree b)
{
  int x;

  if (!rule->fanout)
    {
      bitset_clear (rule->subset_size, (bitset)b);
      return;
    }

  for (x = 0; x < rule->fanout; ++x)
    {
      if (((bits_tree *)b)[x] == bits_tree_full_bitset)
      ((bits_tree *)b)[x] = bits_tree_empty_bitset;
      else if (((bits_tree *)b)[x] != bits_tree_empty_bitset)
      {
        bits_tree_free (lim, rule + 1, ((bits_tree *)b)[x]);
        ((bits_tree *)b)[x] = bits_tree_empty_bitset;
      }
    }
}


void
bits_tree_fill (alloc_limits lim,
            struct bits_tree_rule * rule,
            bits_tree b)
{
  int x;

  if (!rule->fanout)
    {
      bitset_fill (rule->subset_size, (bitset)b);
      return;
    }

  for (x = 0; x < rule->fanout; ++x)
    {
      if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
      ((bits_tree *)b)[x] = bits_tree_full_bitset;
      else if (((bits_tree *)b)[x] != bits_tree_full_bitset)
      {
        bits_tree_free (lim, rule + 1, ((bits_tree *)b)[x]);
        ((bits_tree *)b)[x] = bits_tree_full_bitset;
      }
    }
}


int
bits_tree_clear_range (alloc_limits lim,
                   struct bits_tree_rule * rule,
                   bits_tree b,
                   int from,
                   int to)
{
  int first_bs;
  int first_bit;
  int last_bs;
  int last_bit;

  if (!rule->fanout)
    {
      bitset_clear_range ((bitset)b, from, to);
      return 0;
    }

  if (to <= from)
    return 0;

  first_bs = bits_tree_which_bitset (lim, rule, from);
  first_bit = bits_tree_which_bit (lim, rule, from);

  last_bs = bits_tree_which_bitset (lim, rule, to);
  last_bit = bits_tree_which_bit (lim, rule, to);

  if (first_bs == last_bs)
    {
      if (((bits_tree *)b)[first_bs] == bits_tree_empty_bitset)
      return 0;

      if (((bits_tree *)b)[first_bs] == bits_tree_full_bitset)
      {
        ((bits_tree *)b)[first_bs] = bits_tree_alloc (lim, rule + 1);
        if (!((bits_tree *)b)[first_bs])
          {
            ((bits_tree *)b)[first_bs] = bits_tree_full_bitset;
            return -1;
          }
        bits_tree_fill (lim, rule + 1, ((bits_tree *)b)[first_bs]);
      }

      return bits_tree_clear_range (lim, rule + 1, ((bits_tree *)b)[first_bs], first_bit, last_bit);
    }
  else
    {
      int x;

      if (((bits_tree *)b)[first_bs] != bits_tree_empty_bitset)
      {
        if (((bits_tree *)b)[first_bs] == bits_tree_full_bitset)
          {
            ((bits_tree *)b)[first_bs] = bits_tree_alloc (lim, rule + 1);
            if (!((bits_tree *)b)[first_bs])
            {
              ((bits_tree *)b)[first_bs] = bits_tree_full_bitset;
              return -1;
            }
            bits_tree_fill (lim, rule + 1, ((bits_tree *)b)[first_bs]);
          }
        if (bits_tree_clear_range (lim, rule + 1, ((bits_tree *)b)[first_bs], first_bit, rule->subset_size))
          return -1;
      }

      if (last_bit)
      {
        if (((bits_tree *)b)[last_bs] != bits_tree_empty_bitset)
          {
            if (((bits_tree *)b)[last_bs] == bits_tree_full_bitset)
            {
              ((bits_tree *)b)[last_bs] = bits_tree_alloc (lim, rule + 1);
              if (!((bits_tree *)b)[last_bs])
                {
                  ((bits_tree *)b)[last_bs] = bits_tree_full_bitset;
                  return -1;
                }
              bits_tree_fill (lim, rule + 1, ((bits_tree *)b)[last_bs]);
            }
            if (bits_tree_clear_range (lim, rule + 1, ((bits_tree *)b)[last_bs], 0, last_bit))
            return -1;
          }
      }

      for (x = first_bs + 1; x < last_bs; ++x)
      {
        if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
          continue;
        if (((bits_tree *)b)[x] != bits_tree_full_bitset)
          bits_tree_free (lim, rule + 1, ((bits_tree *)b)[x]);
        ((bits_tree *)b)[x] = bits_tree_empty_bitset;
      }
      return 0;
    }
}


int
bits_tree_fill_range (alloc_limits lim,
                  struct bits_tree_rule * rule,
                  bits_tree b,
                  int from,
                  int to)
{
  int first_bs;
  int first_bit;
  int last_bs;
  int last_bit;

  if (!rule->fanout)
    {
      bitset_fill_range ((bitset)b, from, to);
      return 0;
    }

  if (to <= from)
    return 0;

  first_bs = bits_tree_which_bitset (lim, rule, from);
  first_bit = bits_tree_which_bit (lim, rule, from);

  last_bs = bits_tree_which_bitset (lim, rule, to);
  last_bit = bits_tree_which_bit (lim, rule, to);

  if (first_bs == last_bs)
    {
      if (((bits_tree *)b)[first_bs] == bits_tree_full_bitset)
      return 0;

      if (((bits_tree *)b)[first_bs] == bits_tree_empty_bitset)
      {
        ((bits_tree *)b)[first_bs] = bits_tree_alloc (lim, rule + 1);
        if (!((bits_tree *)b)[first_bs])
          {
            ((bits_tree *)b)[first_bs] = bits_tree_empty_bitset;
            return -1;
          }
      }

      return bits_tree_fill_range (lim, rule + 1, ((bits_tree *)b)[first_bs], first_bit, last_bit);
    }
  else
    {
      int x;

      if (((bits_tree *)b)[first_bs] != bits_tree_full_bitset)
      {
        if (((bits_tree *)b)[first_bs] == bits_tree_empty_bitset)
          {
            ((bits_tree *)b)[first_bs] = bits_tree_alloc (lim, rule + 1);
            if (!((bits_tree *)b)[first_bs])
            {
              ((bits_tree *)b)[first_bs] = bits_tree_full_bitset;
              return -1;
            }
          }
        if (bits_tree_fill_range (lim, rule + 1, ((bits_tree *)b)[first_bs], first_bit, rule->subset_size))
          return -1;
      }

      if (last_bit)
      {
        if (((bits_tree *)b)[last_bs] != bits_tree_full_bitset)
          {
            if (((bits_tree *)b)[last_bs] == bits_tree_empty_bitset)
            {
              ((bits_tree *)b)[last_bs] = bits_tree_alloc (lim, rule + 1);
              if (!((bits_tree *)b)[last_bs])
                {
                  ((bits_tree *)b)[last_bs] = bits_tree_empty_bitset;
                  return -1;
                }
            }
            if (bits_tree_fill_range (lim, rule + 1, ((bits_tree *)b)[last_bs], 0, last_bit))
            return -1;
          }
      }

      for (x = first_bs + 1; x < last_bs; ++x)
      {
        if (((bits_tree *)b)[x] == bits_tree_full_bitset)
          continue;
        if (((bits_tree *)b)[x] != bits_tree_empty_bitset)
          bits_tree_free (lim, rule + 1, ((bits_tree *)b)[x]);
        ((bits_tree *)b)[x] = bits_tree_full_bitset;
      }
      return 0;
    }
}


void
bits_tree_complement (alloc_limits lim,
                  struct bits_tree_rule * rule,
                  bits_tree b)
{
  int x;

  if (!rule->fanout)
    {
      bitset_complement (rule->subset_size, (bitset)b);
      return;
    }

  for (x = 0; x < rule->fanout; ++x)
    {
      if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
      ((bits_tree *)b)[x] = bits_tree_full_bitset;
      else if (((bits_tree *)b)[x] == bits_tree_full_bitset)
      ((bits_tree *)b)[x] = bits_tree_empty_bitset;
      else
      bits_tree_complement (lim, rule + 1, ((bits_tree *)b)[x]);
    }
}


int
bits_tree_assign (alloc_limits lim,
              struct bits_tree_rule * rule,
              bits_tree a,
              bits_tree b)
{
  int x;

  if (!rule->fanout)
    {
      bitset_assign (rule->subset_size, (bitset)a, (bitset)b);
      return 0;
    }

  for (x = 0; x < rule->fanout; ++x)
    {
      if (   (((bits_tree *)b)[x] == bits_tree_empty_bitset)
        || (((bits_tree *)b)[x] == bits_tree_full_bitset))
      {
        if (   (((bits_tree *)a)[x] != bits_tree_empty_bitset)
             && (((bits_tree *)a)[x] != bits_tree_full_bitset))
          bits_tree_free (lim, rule + 1, ((bits_tree *)a)[x]);
        ((bits_tree *)a)[x] = ((bits_tree *)b)[x];
      }
      else
      {
        if (   (((bits_tree *)a)[x] == bits_tree_empty_bitset)
            || (((bits_tree *)a)[x] == bits_tree_full_bitset))
          {
            ((bits_tree *)a)[x] = bits_tree_alloc (lim, rule + 1);
            if (!((bits_tree *)a)[x])
            {
              ((bits_tree *)a)[x] = bits_tree_empty_bitset;
              return -1;
            }
          }
        if (bits_tree_assign (lim, rule + 1, ((bits_tree *)a)[x], ((bits_tree *)b)[x]))
          return -1;
      }
    }
  return 0;
}


int
bits_tree_union (alloc_limits lim,
             struct bits_tree_rule * rule,
             bits_tree a,
             bits_tree b)
{
  int x;

  if (!rule->fanout)
    {
      bitset_union (rule->subset_size, (bitset)a, (bitset)b);
      return 0;
    }

  for (x = 0; x < rule->fanout; ++x)
    {
      if (((bits_tree *)b)[x] == bits_tree_full_bitset)
      {
        if (   (((bits_tree *)a)[x] != bits_tree_empty_bitset)
            && (((bits_tree *)a)[x] != bits_tree_full_bitset))
          bits_tree_free (lim, rule + 1, ((bits_tree *)a)[x]);
        ((bits_tree *)a)[x] = bits_tree_full_bitset;
      }
      else if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
      continue;
      else if (((bits_tree *)a)[x] == bits_tree_full_bitset)
      continue;
      else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
      {
        ((bits_tree *)a)[x] = bits_tree_dup (lim, rule + 1, ((bits_tree *)b)[x]);
        if (!((bits_tree *)a)[x])
          {
            ((bits_tree *)a)[x] = bits_tree_empty_bitset;
            return -1;
          }
      }
      else
      if (bits_tree_union (lim, rule + 1, ((bits_tree *)a)[x], ((bits_tree *)b)[x]))
        return -1;
    }
  return 0;
}


int
bits_tree_intersection (alloc_limits lim,
                  struct bits_tree_rule * rule,
                  bits_tree a,
                  bits_tree b)
{
  int x;

  if (!rule->fanout)
    {
      bitset_intersection (rule->subset_size, (bitset)a, (bitset)b);
      return 0;
    }

  for (x = 0; x < rule->fanout; ++x)
    {
      if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
      {
        if (   (((bits_tree *)a)[x] != bits_tree_empty_bitset)
            && (((bits_tree *)a)[x] != bits_tree_full_bitset))
          bits_tree_free (lim, rule + 1, ((bits_tree *)a)[x]);
        ((bits_tree *)a)[x] = bits_tree_empty_bitset;
      }
      else if (((bits_tree *)b)[x] == bits_tree_full_bitset)
      continue;
      else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
      continue;
      else if (((bits_tree *)a)[x] == bits_tree_full_bitset)
      {
        ((bits_tree *)a)[x] = bits_tree_dup (lim, rule + 1, ((bits_tree *)b)[x]);
        if (!((bits_tree *)a)[x])
          {
            ((bits_tree *)a)[x] = bits_tree_full_bitset;
            return -1;
          }
      }
      else
      if (bits_tree_intersection (lim, rule + 1, ((bits_tree *)a)[x], ((bits_tree *)b)[x]))
        return -1;
    }
  return 0;
}


int
bits_tree_difference (alloc_limits lim,
                  struct bits_tree_rule * rule,
                  bits_tree a,
                  bits_tree b)
{
  int x;

  if (!rule->fanout)
    {
      bitset_difference (rule->subset_size, (bitset)a, (bitset)b);
      return 0;
    }

  for (x = 0; x < rule->fanout; ++x)
    {
      if (((bits_tree *)b)[x] == bits_tree_full_bitset)
      {
        if (   (((bits_tree *)a)[x] != bits_tree_empty_bitset)
            && (((bits_tree *)a)[x] != bits_tree_full_bitset))
          bits_tree_free (lim, rule + 1, ((bits_tree *)a)[x]);
        ((bits_tree *)a)[x] = bits_tree_empty_bitset;
      }
      else if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
      continue;
      else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
      continue;
      else if (((bits_tree *)a)[x] == bits_tree_full_bitset)
      {
        ((bits_tree *)a)[x] = bits_tree_dup (lim, rule + 1, ((bits_tree *)b)[x]);
        if (!((bits_tree *)a)[x])
          {
            ((bits_tree *)a)[x] = bits_tree_full_bitset;
            return -1;
          }
        bits_tree_complement (lim, rule + 1, ((bits_tree *)a)[x]);
      }
      else
      if (bits_tree_difference (lim, rule + 1, ((bits_tree *)a)[x], ((bits_tree *)b)[x]))
        return -1;
    }
  return 0;
}


int
bits_tree_revdifference (alloc_limits lim,
                   struct bits_tree_rule * rule,
                   bits_tree a,
                   bits_tree b)
{
  int x;

  if (!rule->fanout)
    {
      bitset_revdifference (rule->subset_size, (bitset)a, (bitset)b);
      return 0;
    }

  for (x = 0; x < rule->fanout; ++x)
    {
      if (((bits_tree *)a)[x] == bits_tree_full_bitset)
      ((bits_tree *)a)[x] = bits_tree_empty_bitset;
      else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
      {
        if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
          continue;
        else if (((bits_tree *)b)[x] == bits_tree_full_bitset)
          ((bits_tree *)a)[x] = ((bits_tree *)b)[x];
        else
          {
            ((bits_tree *)a)[x] = bits_tree_dup (lim, rule + 1, ((bits_tree *)b)[x]);
            if (!((bits_tree *)a)[x])
            {
              ((bits_tree *)a)[x] = bits_tree_full_bitset;
              return -1;
            }
          }
      }
      else if (((bits_tree *)b)[x] == bits_tree_full_bitset)
      bits_tree_complement (lim, rule + 1, ((bits_tree *)a)[x]);
      else if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
      {
        if (   (((bits_tree *)a)[x] != bits_tree_empty_bitset)
            && (((bits_tree *)a)[x] != bits_tree_full_bitset))
          bits_tree_free (lim, rule + 1, ((bits_tree *)a)[x]);
        ((bits_tree *)a)[x] = bits_tree_empty_bitset;
      }
      else
      {
        if (bits_tree_revdifference (lim, rule + 1, ((bits_tree *)a)[x], ((bits_tree *)b)[x]))
          return -1;
      }
    }
  return 0;
}


int
bits_tree_xor (alloc_limits lim,
             struct bits_tree_rule * rule,
             bits_tree a,
             bits_tree b)
{
  int x;

  if (!rule->fanout)
    {
      bitset_xor (rule->subset_size, (bitset)a, (bitset)b);
      return 0;
    }

  for (x = 0; x < rule->fanout; ++x)
    {
      if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
      continue;
      else if (((bits_tree *)b)[x] == bits_tree_full_bitset)
      {
        if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
          ((bits_tree *)a)[x] = bits_tree_full_bitset;
        else if (((bits_tree *)a)[x] == bits_tree_full_bitset)
          ((bits_tree *)a)[x] = bits_tree_empty_bitset;
        else
          bits_tree_complement (lim, rule + 1, ((bits_tree *)a)[x]);
      }
      else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
      {
        if (   (((bits_tree *)b)[x] == bits_tree_empty_bitset)
            || (((bits_tree *)b)[x] == bits_tree_full_bitset))
          ((bits_tree *)a)[x] = ((bits_tree *)b)[x];
        else
          {
            ((bits_tree *)a)[x] = bits_tree_dup (lim, rule + 1, ((bits_tree *)b)[x]);
            if (!((bits_tree *)a)[x])
            {
              ((bits_tree *)a)[x] = bits_tree_empty_bitset;
              return -1;
            }
          }
      }
      else if (((bits_tree *)a)[x] == bits_tree_full_bitset)
      {
        ((bits_tree *)a)[x] = bits_tree_dup (lim, rule + 1, ((bits_tree *)b)[x]);
        if (!((bits_tree *)a)[x])
          {
            ((bits_tree *)a)[x] = bits_tree_full_bitset;
            return -1;
          }
        bits_tree_complement (lim, rule + 1, ((bits_tree *)a)[x]);
      }
      else
      {
        if (bits_tree_xor (lim, rule + 1, ((bits_tree *)a)[x], ((bits_tree *)b)[x]))
          return -1;
      }
    }
  return 0;
}


int
bits_tree_population (alloc_limits lim,
                  struct bits_tree_rule * rule,
                  bits_tree a)
{
  int x;
  int pop;

  if (!rule->fanout)
    {
      return bitset_population (rule->subset_size, (bitset)a);
    }

  pop = 0;
  for (x = 0; x < rule->fanout; ++x)
    {
      if (((bits_tree *)a)[x] == bits_tree_full_bitset)
      pop += rule->subset_size;
      else if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
      continue;
      else
      pop += bits_tree_population (lim, rule + 1, ((bits_tree *)a)[x]);
    }
  return pop;
}


int
bits_tree_population_range (alloc_limits lim,
                      struct bits_tree_rule * rule,
                      bits_tree a, int from, int to)
{
  int first_bs;
  int first_bit;
  int last_bs;
  int last_bit;

  if (!rule->fanout)
    {
      return bitset_population_range ((bitset)a, from, to);
    }

  if (to <= from)
    return 0;

  first_bs = bits_tree_which_bitset (lim, rule, from);
  first_bit = bits_tree_which_bit (lim, rule, from);

  last_bs = bits_tree_which_bitset (lim, rule, to);
  last_bit = bits_tree_which_bit (lim, rule, to);

  if (first_bs == last_bs)
    {
      if (((bits_tree *)a)[first_bs] == bits_tree_full_bitset)
      return last_bit - first_bit;
      if (((bits_tree *)a)[first_bs] == bits_tree_empty_bitset)
      return 0;
      return bits_tree_population_range (lim, rule + 1, ((bits_tree *)a)[first_bs], first_bit, last_bit);
    }
  else
    {
      int pop;
      int x;

      if (bits_tree_is_empty_bitset (lim, rule, ((bits_tree *)a)[first_bs]))
      pop = 0;
      else if (bits_tree_is_full_bitset (lim, rule, ((bits_tree *)a)[first_bs]))
      pop = rule->subset_size - first_bit;
      else
      pop = bits_tree_population_range (lim, rule + 1, ((bits_tree *)a)[first_bs], first_bit, rule->subset_size);

      if (last_bit)
      {
        if (bits_tree_is_empty_bitset (lim, rule, ((bits_tree *)a)[last_bs]))
          pop += 0;
        else if (bits_tree_is_full_bitset (lim, rule, ((bits_tree *)a)[last_bs]))
          pop += last_bit;
        else
          pop += bits_tree_population_range (lim, rule + 1, ((bits_tree *)a)[last_bs], 0, last_bit);
      }

      for (x = first_bs + 1; x < last_bs; ++x)
      {
        if (((bits_tree *)a)[x] == bits_tree_empty_bitset)
          pop += 0;
        else if (((bits_tree *)a)[x] == bits_tree_full_bitset)
          pop += rule->subset_size;
        else
          pop += bits_tree_population (lim, rule + 1, ((bits_tree *)a)[x]);
      }
      return pop;
    }
}


int
bits_tree_ffs (alloc_limits lim,
             struct bits_tree_rule * rule,
             bits_tree b)
{
  int x;
  int offset;

  if (!rule->fanout)
    {
      return bitset_ffs (rule->subset_size, (bitset)b);
    }

  for (x = 0, offset = 0; x < rule->fanout; ++x, offset += rule->subset_size)
    {
      int fs;

      if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
      continue;
      else if (((bits_tree *)b)[x] == bits_tree_full_bitset)
      return offset;
      else
      {
        fs = bits_tree_ffs (lim, rule + 1, ((bits_tree *)b)[x]);
        if (fs >= 0)
          return fs + offset;
      }
    }
  return -1;
}


int
bits_tree_ffc (alloc_limits lim, struct bits_tree_rule * rule, bits_tree b)
{
  int x;
  int offset;

  if (!rule->fanout)
    {
      return bitset_ffc (rule->subset_size, (bitset)b);
    }

  for (x = 0, offset = 0; x < rule->fanout; ++x, offset += rule->subset_size)
    {
      int fc;

      if (((bits_tree *)b)[x] == bits_tree_full_bitset)
      continue;
      else if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
      return offset;
      else
      {
        fc = bits_tree_ffc (lim, rule + 1, ((bits_tree *)b)[x]);
        if (fc >= 0)
          return fc + offset;
      }
    }
  return -1;
}


int
bits_tree_ffs_range (alloc_limits lim,
                 struct bits_tree_rule * rule,
                 bits_tree b,
                 int from,
                 int to)
{
  int first_bs;
  int first_bit;
  int last_bs;
  int last_bit;

  if (!rule->fanout)
    {
      return bitset_ffs_range ((bitset)b, from, to);
    }

  if (to <= from)
    return -1;

  first_bs = bits_tree_which_bitset (lim, rule, from);
  first_bit = bits_tree_which_bit (lim, rule, from);

  last_bs = bits_tree_which_bitset (lim, rule, to);
  last_bit = bits_tree_which_bit (lim, rule, to);

  if (first_bs == last_bs)
    {
      int fs;

      if (((bits_tree *)b)[first_bs] == bits_tree_empty_bitset)
      return -1;

      if (((bits_tree *)b)[first_bs] == bits_tree_full_bitset)
      return from;

      fs = bits_tree_ffs_range (lim, rule + 1, ((bits_tree *)b)[first_bs], first_bit, last_bit);

      if (fs < 0)
      return -1;
      else
      return (first_bs * rule->subset_size) + fs;
    }
  else
    {
      int x;
      
      if (((bits_tree *)b)[first_bs] != bits_tree_empty_bitset)
      {
        int fs;
        if (((bits_tree *)b)[first_bs] == bits_tree_full_bitset)
          return from;

        fs = bits_tree_ffs_range (lim, rule + 1, ((bits_tree *)b)[first_bs], first_bit, rule->subset_size);
        if (fs >= 0)
          return (first_bs * rule->subset_size) + fs;
      }

      for (x = first_bs + 1; x < last_bs; ++x)
      {
        int fs;
        if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
          continue;
        if (((bits_tree *)b)[x] == bits_tree_full_bitset)
          return (x * rule->subset_size);
        fs = bits_tree_ffs (lim, rule + 1, ((bits_tree *)b)[x]);
        if (fs >= 0)
          return (x * rule->subset_size) + fs;
      }

      if (last_bit)
      {
        if (((bits_tree *)b)[last_bs] != bits_tree_empty_bitset)
          {
            if (((bits_tree *)b)[last_bs] == bits_tree_full_bitset)
            return (last_bs * rule->subset_size);
            else
            {
              int fs;

              fs = bits_tree_ffs_range (lim, rule + 1, ((bits_tree *)b)[last_bs], 0, last_bit);
              if (fs >= 0)
                return (last_bs * rule->subset_size) + fs;
            }
          }
      }

      return -1;
    }
}


int
bits_tree_ffc_range (alloc_limits lim,
                 struct bits_tree_rule * rule,
                 bits_tree b,
                 int from,
                 int to)
{
  int first_bs;
  int first_bit;
  int last_bs;
  int last_bit;

  if (!rule->fanout)
    {
      return bitset_ffc_range ((bitset)b, from, to);
    }

  if (to <= from)
    return -1;

  first_bs = bits_tree_which_bitset (lim, rule, from);
  first_bit = bits_tree_which_bit (lim, rule, from);

  last_bs = bits_tree_which_bitset (lim, rule, to);
  last_bit = bits_tree_which_bit (lim, rule, to);

  if (first_bs == last_bs)
    {
      int fs;

      if (((bits_tree *)b)[first_bs] == bits_tree_full_bitset)
      return -1;

      if (((bits_tree *)b)[first_bs] == bits_tree_empty_bitset)
      return from;

      fs = bits_tree_ffc_range (lim, rule + 1, ((bits_tree *)b)[first_bs], first_bit, last_bit);

      if (fs < 0)
      return -1;
      else
      return (first_bs * rule->subset_size) + fs;
    }
  else
    {
      int x;
      
      if (((bits_tree *)b)[first_bs] != bits_tree_full_bitset)
      {
        int fs;
        if (((bits_tree *)b)[first_bs] == bits_tree_empty_bitset)
          return from;

        fs = bits_tree_ffc_range (lim, rule + 1, ((bits_tree *)b)[first_bs], first_bit, rule->subset_size);
        if (fs >= 0)
          return (first_bs * rule->subset_size) + fs;
      }

      for (x = first_bs + 1; x < last_bs; ++x)
      {
        int fs;
        if (((bits_tree *)b)[x] == bits_tree_full_bitset)
          continue;
        if (((bits_tree *)b)[x] == bits_tree_empty_bitset)
          return (x * rule->subset_size);
        fs = bits_tree_ffc (lim, rule + 1, ((bits_tree *)b)[x]);
        if (fs >= 0)
          return (x * rule->subset_size) + fs;
      }

      if (last_bit)
      {
        if (((bits_tree *)b)[last_bs] != bits_tree_full_bitset)
          {
            if (((bits_tree *)b)[last_bs] == bits_tree_empty_bitset)
            return (last_bs * rule->subset_size);
            else
            {
              int fs;

              fs = bits_tree_ffc_range (lim, rule + 1, ((bits_tree *)b)[last_bs], 0, last_bit);
              if (fs >= 0)
                return (last_bs * rule->subset_size) + fs;
            }
          }
      }

      return -1;
    }
}



Generated by  Doxygen 1.6.0   Back to index