path: root/lib/gl_anyavltree_list2.h

/* Sequential list data type implemented by a binary tree.
   Copyright (C) 2006-2007, 2009-2017 Free Software Foundation, Inc.
   Written by Bruno Haible <bruno@clisp.org>, 2006.

   This program 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 3 of the License, or
   (at your option) any later version.

   This program 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, see <http://www.gnu.org/licenses/>.  */

/* Common code of gl_avltree_list.c and gl_avltreehash_list.c.  */

/* -------------------------- gl_list_t Data Type -------------------------- */

/* Create a subtree for count >= 1 elements.
   Its height is h where 2^(h-1) <= count <= 2^h - 1.
   Return NULL upon out-of-memory.  */
static gl_list_node_t
create_subtree_with_contents (size_t count, const void **contents)
{
  size_t half1 = (count - 1) / 2;
  size_t half2 = count / 2;
  /* Note: half1 + half2 = count - 1.  */
  gl_list_node_t node =
    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
  if (node == NULL)
    return NULL;

  if (half1 > 0)
    {
      node->left = create_subtree_with_contents (half1, contents);
      if (node->left == NULL)
        goto fail1;
      node->left->parent = node;
    }
  else
    node->left = NULL;

  node->value = contents[half1];

  if (half2 > 0)
    {
      node->right = create_subtree_with_contents (half2, contents + half1 + 1);
      if (node->right == NULL)
        goto fail2;
      node->right->parent = node;
    }
  else
    node->right = NULL;

  /* balance is 0, except when count is a power of two and > 1.
     Reason: half1 <= half2 <= half1 + 1, and the two branches can have
     different heights only if half1 = 2^h - 1 and half2 = 2^h; in this
     case, count = half1 + half2 + 1 = 2^(h+1).  */
  node->balance = (count > 1 && (count & (count - 1)) == 0 ? 1 : 0);

  node->branch_size = count;

  return node;

 fail2:
  if (node->left != NULL)
    free_subtree (node->left);
 fail1:
  free (node);
  return NULL;
}

static gl_list_t
gl_tree_nx_create (gl_list_implementation_t implementation,
                   gl_listelement_equals_fn equals_fn,
                   gl_listelement_hashcode_fn hashcode_fn,
                   gl_listelement_dispose_fn dispose_fn,
                   bool allow_duplicates,
                   size_t count, const void **contents)
{
  struct gl_list_impl *list =
    (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));

  if (list == NULL)
    return NULL;

  list->base.vtable = implementation;
  list->base.equals_fn = equals_fn;
  list->base.hashcode_fn = hashcode_fn;
  list->base.dispose_fn = dispose_fn;
  list->base.allow_duplicates = allow_duplicates;
#if WITH_HASHTABLE
  {
    size_t estimate = xsum (count, count / 2); /* 1.5 * count */
    if (estimate < 10)
      estimate = 10;
    list->table_size = next_prime (estimate);
    if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t))))
      goto fail1;
    list->table =
      (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
    if (list->table == NULL)
      goto fail1;
  }
#endif
  if (count > 0)
    {
      list->root = create_subtree_with_contents (count, contents);
      if (list->root == NULL)
        goto fail2;
      list->root->parent = NULL;

#if WITH_HASHTABLE
      /* Now that the tree is built, node_position() works.  Now we can
         add the nodes to the hash table.  */
      if (add_nodes_to_buckets (list) < 0)
        goto fail3;
#endif
    }
  else
    list->root = NULL;

  return list;

#if WITH_HASHTABLE
 fail3:
  free_subtree (list->root);
#endif
 fail2:
#if WITH_HASHTABLE
  free (list->table);
 fail1:
#endif
  free (list);
  return NULL;
}

/* Ensure the tree is balanced, after an insertion or deletion operation.
   The height of NODE is incremented by HEIGHT_DIFF (1 or -1).
   PARENT = NODE->parent.  (NODE can also be NULL.  But PARENT is non-NULL.)
   Rotation operations are performed starting at PARENT (not NODE itself!).  */
static void
rebalance (gl_list_t list,
           gl_list_node_t node, int height_diff, gl_list_node_t parent)
{
  for (;;)
    {
      gl_list_node_t child;
      int previous_balance;
      int balance_diff;
      gl_list_node_t nodeleft;
      gl_list_node_t noderight;

      child = node;
      node = parent;

      previous_balance = node->balance;

      /* The balance of NODE is incremented by BALANCE_DIFF: +1 if the right
         branch's height has increased by 1 or the left branch's height has
         decreased by 1, -1 if the right branch's height has decreased by 1 or
         the left branch's height has increased by 1, 0 if no height change.  */
      if (node->left != NULL || node->right != NULL)
        balance_diff = (child == node->right ? height_diff : -height_diff);
      else
        /* Special case where above formula doesn't work, because the caller
           didn't tell whether node's left or right branch shrunk from height 1
           to NULL.  */
        balance_diff = - previous_balance;

      node->balance += balance_diff;
      if (balance_diff == previous_balance)
        {
          /* node->balance is outside the range [-1,1].  Must rotate.  */
          gl_list_node_t *nodep;

          if (node->parent == NULL)
            /* node == list->root */
            nodep = &list->root;
          else if (node->parent->left == node)
            nodep = &node->parent->left;
          else if (node->parent->right == node)
            nodep = &node->parent->right;
          else
            abort ();

          nodeleft = node->left;
          noderight = node->right;

          if (balance_diff < 0)
            {
              /* node->balance = -2.  The subtree is heavier on the left side.
                 Rotate from left to right:

                                  *
                                /   \
                             h+2      h
               */
              gl_list_node_t nodeleftleft = nodeleft->left;
              gl_list_node_t nodeleftright = nodeleft->right;
              if (nodeleft->balance <= 0)
                {
                  /*
                              *                    h+2|h+3
                            /   \                  /    \
                         h+2      h      -->      /   h+1|h+2
                         / \                      |    /    \
                       h+1 h|h+1                 h+1  h|h+1  h
                   */
                  node->left = nodeleftright;
                  nodeleft->right = node;

                  nodeleft->parent = node->parent;
                  node->parent = nodeleft;
                  if (nodeleftright != NULL)
                    nodeleftright->parent = node;

                  nodeleft->balance += 1;
                  node->balance = - nodeleft->balance;

                  node->branch_size =
                    (nodeleftright != NULL ? nodeleftright->branch_size : 0)
                    + 1 + (noderight != NULL ? noderight->branch_size : 0);
                  nodeleft->branch_size =
                    nodeleftleft->branch_size + 1 + node->branch_size;

                  *nodep = nodeleft;
                  height_diff = (height_diff < 0
                                 ? /* noderight's height had been decremented from
                                      h+1 to h.  The subtree's height changes from
                                      h+3 to h+2|h+3.  */
                                   nodeleft->balance - 1
                                 : /* nodeleft's height had been incremented from
                                      h+1 to h+2.  The subtree's height changes from
                                      h+2 to h+2|h+3.  */
                                   nodeleft->balance);
                }
              else
                {
                  /*
                            *                     h+2
                          /   \                 /     \
                       h+2      h      -->    h+1     h+1
                       / \                    / \     / \
                      h  h+1                 h   L   R   h
                         / \
                        L   R

                   */
                  gl_list_node_t L = nodeleft->right = nodeleftright->left;
                  gl_list_node_t R = node->left = nodeleftright->right;
                  nodeleftright->left = nodeleft;
                  nodeleftright->right = node;

                  nodeleftright->parent = node->parent;
                  if (L != NULL)
                    L->parent = nodeleft;
                  if (R != NULL)
                    R->parent = node;
                  nodeleft->parent = nodeleftright;
                  node->parent = nodeleftright;

                  nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0);
                  node->balance = (nodeleftright->balance < 0 ? 1 : 0);
                  nodeleftright->balance = 0;

                  nodeleft->branch_size =
                    (nodeleft->left != NULL ? nodeleft->left->branch_size : 0)
                    + 1 + (nodeleft->right != NULL ? nodeleft->right->branch_size : 0);
                  node->branch_size =
                    (node->left != NULL ? node->left->branch_size : 0)
                    + 1 + (node->right != NULL ? node->right->branch_size : 0);
                  nodeleftright->branch_size =
                    nodeleft->branch_size + 1 + node->branch_size;

                  *nodep = nodeleftright;
                  height_diff = (height_diff < 0
                                 ? /* noderight's height had been decremented from
                                      h+1 to h.  The subtree's height changes from
                                      h+3 to h+2.  */
                                   -1
                                 : /* nodeleft's height had been incremented from
                                      h+1 to h+2.  The subtree's height changes from
                                      h+2 to h+2.  */
                                   0);
                }
            }
          else
            {
              /* node->balance = 2.  The subtree is heavier on the right side.
                 Rotate from right to left:

                                  *
                                /   \
                              h      h+2
               */
              gl_list_node_t noderightleft = noderight->left;
              gl_list_node_t noderightright = noderight->right;
              if (noderight->balance >= 0)
                {
                  /*
                              *                    h+2|h+3
                            /   \                   /    \
                          h      h+2     -->    h+1|h+2   \
                                 / \            /    \    |
                             h|h+1 h+1         h   h|h+1 h+1
                   */
                  node->right = noderightleft;
                  noderight->left = node;

                  noderight->parent = node->parent;
                  node->parent = noderight;
                  if (noderightleft != NULL)
                    noderightleft->parent = node;

                  noderight->balance -= 1;
                  node->balance = - noderight->balance;

                  node->branch_size =
                    (nodeleft != NULL ? nodeleft->branch_size : 0)
                    + 1 + (noderightleft != NULL ? noderightleft->branch_size : 0);
                  noderight->branch_size =
                    node->branch_size + 1 + noderightright->branch_size;

                  *nodep = noderight;
                  height_diff = (height_diff < 0
                                 ? /* nodeleft's height had been decremented from
                                      h+1 to h.  The subtree's height changes from
                                      h+3 to h+2|h+3.  */
                                   - noderight->balance - 1
                                 : /* noderight's height had been incremented from
                                      h+1 to h+2.  The subtree's height changes from
                                      h+2 to h+2|h+3.  */
                                   - noderight->balance);
                }
              else
                {
                  /*
                            *                    h+2
                          /   \                /     \
                        h      h+2    -->    h+1     h+1
                               / \           / \     / \
                             h+1  h         h   L   R   h
                             / \
                            L   R

                   */
                  gl_list_node_t L = node->right = noderightleft->left;
                  gl_list_node_t R = noderight->left = noderightleft->right;
                  noderightleft->left = node;
                  noderightleft->right = noderight;

                  noderightleft->parent = node->parent;
                  if (L != NULL)
                    L->parent = node;
                  if (R != NULL)
                    R->parent = noderight;
                  node->parent = noderightleft;
                  noderight->parent = noderightleft;

                  node->balance = (noderightleft->balance > 0 ? -1 : 0);
                  noderight->balance = (noderightleft->balance < 0 ? 1 : 0);
                  noderightleft->balance = 0;

                  node->branch_size =
                    (node->left != NULL ? node->left->branch_size : 0)
                    + 1 + (node->right != NULL ? node->right->branch_size : 0);
                  noderight->branch_size =
                    (noderight->left != NULL ? noderight->left->branch_size : 0)
                    + 1 + (noderight->right != NULL ? noderight->right->branch_size : 0);
                  noderightleft->branch_size =
                    node->branch_size + 1 + noderight->branch_size;

                  *nodep = noderightleft;
                  height_diff = (height_diff < 0
                                 ? /* nodeleft's height had been decremented from
                                      h+1 to h.  The subtree's height changes from
                                      h+3 to h+2.  */
                                   -1
                                 : /* noderight's height had been incremented from
                                      h+1 to h+2.  The subtree's height changes from
                                      h+2 to h+2.  */
                                   0);
                }
            }
          node = *nodep;
        }
      else
        {
          /* No rotation needed.  Only propagation of the height change to the
             next higher level.  */
          if (height_diff < 0)
            height_diff = (previous_balance == 0 ? 0 : -1);
          else
            height_diff = (node->balance == 0 ? 0 : 1);
        }

      if (height_diff == 0)
        break;

      parent = node->parent;
      if (parent == NULL)
        break;
    }
}

static void
gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node)
{
  gl_list_node_t parent = node->parent;

  if (node->left == NULL)
    {
      /* Replace node with node->right.  */
      gl_list_node_t child = node->right;

      if (child != NULL)
        child->parent = parent;
      if (parent == NULL)
        list->root = child;
      else
        {
          if (parent->left == node)
            parent->left = child;
          else /* parent->right == node */
            parent->right = child;

          /* Update branch_size fields of the parent nodes.  */
          {
            gl_list_node_t p;

            for (p = parent; p != NULL; p = p->parent)
              p->branch_size--;
          }

          rebalance (list, child, -1, parent);
        }
    }
  else if (node->right == NULL)
    {
      /* It is not absolutely necessary to treat this case.  But the more
         general case below is more complicated, hence slower.  */
      /* Replace node with node->left.  */
      gl_list_node_t child = node->left;

      child->parent = parent;
      if (parent == NULL)
        list->root = child;
      else
        {
          if (parent->left == node)
            parent->left = child;
          else /* parent->right == node */
            parent->right = child;

          /* Update branch_size fields of the parent nodes.  */
          {
            gl_list_node_t p;

            for (p = parent; p != NULL; p = p->parent)
              p->branch_size--;
          }

          rebalance (list, child, -1, parent);
        }
    }
  else
    {
      /* Replace node with the rightmost element of the node->left subtree.  */
      gl_list_node_t subst;
      gl_list_node_t subst_parent;
      gl_list_node_t child;

      for (subst = node->left; subst->right != NULL; )
        subst = subst->right;

      subst_parent = subst->parent;

      child = subst->left;

      /* The case subst_parent == node is special:  If we do nothing special,
         we get confusion about node->left, subst->left and child->parent.
           subst_parent == node
           <==> The 'for' loop above terminated immediately.
           <==> subst == subst_parent->left
                [otherwise subst == subst_parent->right]
         In this case, we would need to first set
           child->parent = node; node->left = child;
         and later - when we copy subst into node's position - again
           child->parent = subst; subst->left = child;
         Altogether a no-op.  */
      if (subst_parent != node)
        {
          if (child != NULL)
            child->parent = subst_parent;
          subst_parent->right = child;
        }

      /* Update branch_size fields of the parent nodes.  */
      {
        gl_list_node_t p;

        for (p = subst_parent; p != NULL; p = p->parent)
          p->branch_size--;
      }

      /* Copy subst into node's position.
         (This is safer than to copy subst's value into node, keep node in
         place, and free subst.)  */
      if (subst_parent != node)
        {
          subst->left = node->left;
          subst->left->parent = subst;
        }
      subst->right = node->right;
      subst->right->parent = subst;
      subst->balance = node->balance;
      subst->branch_size = node->branch_size;
      subst->parent = parent;
      if (parent == NULL)
        list->root = subst;
      else if (parent->left == node)
        parent->left = subst;
      else /* parent->right == node */
        parent->right = subst;

      /* Rebalancing starts at child's parent, that is subst_parent -
         except when subst_parent == node.  In this case, we need to use
         its replacement, subst.  */
      rebalance (list, child, -1, subst_parent != node ? subst_parent : subst);
    }
}

static gl_list_node_t
gl_tree_nx_add_first (gl_list_t list, const void *elt)
{
  /* Create new node.  */
  gl_list_node_t new_node =
    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));

  if (new_node == NULL)
    return NULL;

  new_node->left = NULL;
  new_node->right = NULL;
  new_node->balance = 0;
  new_node->branch_size = 1;
  new_node->value = elt;
#if WITH_HASHTABLE
  new_node->h.hashcode =
    (list->base.hashcode_fn != NULL
     ? list->base.hashcode_fn (new_node->value)
     : (size_t)(uintptr_t) new_node->value);
#endif

  /* Add it to the tree.  */
  if (list->root == NULL)
    {
      list->root = new_node;
      new_node->parent = NULL;
    }
  else
    {
      gl_list_node_t node;

      for (node = list->root; node->left != NULL; )
        node = node->left;

      node->left = new_node;
      new_node->parent = node;
      node->balance--;

      /* Update branch_size fields of the parent nodes.  */
      {
        gl_list_node_t p;

        for (p = node; p != NULL; p = p->parent)
          p->branch_size++;
      }

      /* Rebalance.  */
      if (node->right == NULL && node->parent != NULL)
        rebalance (list, node, 1, node->parent);
    }

#if WITH_HASHTABLE
  /* Add node to the hash table.
     Note that this is only possible _after_ the node has been added to the
     tree structure, because add_to_bucket() uses node_position().  */
  if (add_to_bucket (list, new_node) < 0)
    {
      gl_tree_remove_node_from_tree (list, new_node);
      free (new_node);
      return NULL;
    }
  hash_resize_after_add (list);
#endif

  return new_node;
}

static gl_list_node_t
gl_tree_nx_add_last (gl_list_t list, const void *elt)
{
  /* Create new node.  */
  gl_list_node_t new_node =
    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));

  if (new_node == NULL)
    return NULL;

  new_node->left = NULL;
  new_node->right = NULL;
  new_node->balance = 0;
  new_node->branch_size = 1;
  new_node->value = elt;
#if WITH_HASHTABLE
  new_node->h.hashcode =
    (list->base.hashcode_fn != NULL
     ? list->base.hashcode_fn (new_node->value)
     : (size_t)(uintptr_t) new_node->value);
#endif

  /* Add it to the tree.  */
  if (list->root == NULL)
    {
      list->root = new_node;
      new_node->parent = NULL;
    }
  else
    {
      gl_list_node_t node;

      for (node = list->root; node->right != NULL; )
        node = node->right;

      node->right = new_node;
      new_node->parent = node;
      node->balance++;

      /* Update branch_size fields of the parent nodes.  */
      {
        gl_list_node_t p;

        for (p = node; p != NULL; p = p->parent)
          p->branch_size++;
      }

      /* Rebalance.  */
      if (node->left == NULL && node->parent != NULL)
        rebalance (list, node, 1, node->parent);
    }

#if WITH_HASHTABLE
  /* Add node to the hash table.
     Note that this is only possible _after_ the node has been added to the
     tree structure, because add_to_bucket() uses node_position().  */
  if (add_to_bucket (list, new_node) < 0)
    {
      gl_tree_remove_node_from_tree (list, new_node);
      free (new_node);
      return NULL;
    }
  hash_resize_after_add (list);
#endif

  return new_node;
}

static gl_list_node_t
gl_tree_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
{
  /* Create new node.  */
  gl_list_node_t new_node;
  bool height_inc;

  new_node =
    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
  if (new_node == NULL)
    return NULL;

  new_node->left = NULL;
  new_node->right = NULL;
  new_node->balance = 0;
  new_node->branch_size = 1;
  new_node->value = elt;
#if WITH_HASHTABLE
  new_node->h.hashcode =
    (list->base.hashcode_fn != NULL
     ? list->base.hashcode_fn (new_node->value)
     : (size_t)(uintptr_t) new_node->value);
#endif

  /* Add it to the tree.  */
  if (node->left == NULL)
    {
      node->left = new_node;
      node->balance--;
      height_inc = (node->right == NULL);
    }
  else
    {
      for (node = node->left; node->right != NULL; )
        node = node->right;
      node->right = new_node;
      node->balance++;
      height_inc = (node->left == NULL);
    }
  new_node->parent = node;

  /* Update branch_size fields of the parent nodes.  */
  {
    gl_list_node_t p;

    for (p = node; p != NULL; p = p->parent)
      p->branch_size++;
  }

  /* Rebalance.  */
  if (height_inc && node->parent != NULL)
    rebalance (list, node, 1, node->parent);

#if WITH_HASHTABLE
  /* Add node to the hash table.
     Note that this is only possible _after_ the node has been added to the
     tree structure, because add_to_bucket() uses node_position().  */
  if (add_to_bucket (list, new_node) < 0)
    {
      gl_tree_remove_node_from_tree (list, new_node);
      free (new_node);
      return NULL;
    }
  hash_resize_after_add (list);
#endif

  return new_node;
}

static gl_list_node_t
gl_tree_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
{
  /* Create new node.  */
  gl_list_node_t new_node;
  bool height_inc;

  new_node =
    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
  if (new_node == NULL)
    return NULL;

  new_node->left = NULL;
  new_node->right = NULL;
  new_node->balance = 0;
  new_node->branch_size = 1;
  new_node->value = elt;
#if WITH_HASHTABLE
  new_node->h.hashcode =
    (list->base.hashcode_fn != NULL
     ? list->base.hashcode_fn (new_node->value)
     : (size_t)(uintptr_t) new_node->value);
#endif

  /* Add it to the tree.  */
  if (node->right == NULL)
    {
      node->right = new_node;
      node->balance++;
      height_inc = (node->left == NULL);
    }
  else
    {
      for (node = node->right; node->left != NULL; )
        node = node->left;
      node->left = new_node;
      node->balance--;
      height_inc = (node->right == NULL);
    }
  new_node->parent = node;

  /* Update branch_size fields of the parent nodes.  */
  {
    gl_list_node_t p;

    for (p = node; p != NULL; p = p->parent)
      p->branch_size++;
  }

  /* Rebalance.  */
  if (height_inc && node->parent != NULL)
    rebalance (list, node, 1, node->parent);

#if WITH_HASHTABLE
  /* Add node to the hash table.
     Note that this is only possible _after_ the node has been added to the
     tree structure, because add_to_bucket() uses node_position().  */
  if (add_to_bucket (list, new_node) < 0)
    {
      gl_tree_remove_node_from_tree (list, new_node);
      free (new_node);
      return NULL;
    }
  hash_resize_after_add (list);
#endif

  return new_node;
}