kc3-lang/gnulib/lib/gl_anytree_list2.h

• Show log

  Commit

• Hash : 92877a2d
  Author :
  Date : 2008-02-10T19:35:54
  

  New abstract list operation 'node_set_value'.
  

Download

• lib/gl_anytree_list2.h

• /* Sequential list data type implemented by a binary tree.
     Copyright (C) 2006-2008 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, gl_rbtree_list.c,
                    gl_avltreehash_list.c, gl_rbtreehash_list.c.  */
  
  static gl_list_t
  gl_tree_create_empty (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)
  {
    struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
  
    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
    list->table_size = 11;
    list->table = XCALLOC (list->table_size, gl_hash_entry_t);
  #endif
    list->root = NULL;
  
    return list;
  }
  
  static size_t
  gl_tree_size (gl_list_t list)
  {
    return (list->root != NULL ? list->root->branch_size : 0);
  }
  
  static const void *
  gl_tree_node_value (gl_list_t list, gl_list_node_t node)
  {
    return node->value;
  }
  
  static void
  gl_tree_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
  {
  #if WITH_HASHTABLE
    if (elt != node->value)
      {
        size_t new_hashcode =
  	(list->base.hashcode_fn != NULL
  	 ? list->base.hashcode_fn (elt)
  	 : (size_t)(uintptr_t) elt);
  
        if (new_hashcode != node->h.hashcode)
  	{
  	  remove_from_bucket (list, node);
  	  node->value = elt;
  	  node->h.hashcode = new_hashcode;
  	  add_to_bucket (list, node);
  	}
        else
  	node->value = elt;
      }
  #else
    node->value = elt;
  #endif
  }
  
  static gl_list_node_t
  gl_tree_next_node (gl_list_t list, gl_list_node_t node)
  {
    if (node->right != NULL)
      {
        node = node->right;
        while (node->left != NULL)
  	node = node->left;
      }
    else
      {
        while (node->parent != NULL && node->parent->right == node)
  	node = node->parent;
        node = node->parent;
      }
    return node;
  }
  
  static gl_list_node_t
  gl_tree_previous_node (gl_list_t list, gl_list_node_t node)
  {
    if (node->left != NULL)
      {
        node = node->left;
        while (node->right != NULL)
  	node = node->right;
      }
    else
      {
        while (node->parent != NULL && node->parent->left == node)
  	node = node->parent;
        node = node->parent;
      }
    return node;
  }
  
  /* Return the node at the given position < gl_tree_size (list).  */
  static inline gl_list_node_t
  node_at (gl_list_node_t root, size_t position)
  {
    /* Here we know that root != NULL.  */
    gl_list_node_t node = root;
  
    for (;;)
      {
        if (node->left != NULL)
  	{
  	  if (position < node->left->branch_size)
  	    {
  	      node = node->left;
  	      continue;
  	    }
  	  position -= node->left->branch_size;
  	}
        if (position == 0)
  	break;
        position--;
        node = node->right;
      }
    return node;
  }
  
  static const void *
  gl_tree_get_at (gl_list_t list, size_t position)
  {
    gl_list_node_t node = list->root;
  
    if (!(node != NULL && position < node->branch_size))
      /* Invalid argument.  */
      abort ();
    node = node_at (node, position);
    return node->value;
  }
  
  static gl_list_node_t
  gl_tree_set_at (gl_list_t list, size_t position, const void *elt)
  {
    gl_list_node_t node = list->root;
  
    if (!(node != NULL && position < node->branch_size))
      /* Invalid argument.  */
      abort ();
    node = node_at (node, position);
  #if WITH_HASHTABLE
    if (elt != node->value)
      {
        size_t new_hashcode =
  	(list->base.hashcode_fn != NULL
  	 ? list->base.hashcode_fn (elt)
  	 : (size_t)(uintptr_t) elt);
  
        if (new_hashcode != node->h.hashcode)
  	{
  	  remove_from_bucket (list, node);
  	  node->value = elt;
  	  node->h.hashcode = new_hashcode;
  	  add_to_bucket (list, node);
  	}
        else
  	node->value = elt;
      }
  #else
    node->value = elt;
  #endif
    return node;
  }
  
  #if !WITH_HASHTABLE
  
  static gl_list_node_t
  gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
  			const void *elt)
  {
    if (!(start_index <= end_index
  	&& end_index <= (list->root != NULL ? list->root->branch_size : 0)))
      /* Invalid arguments.  */
      abort ();
    {
      gl_listelement_equals_fn equals = list->base.equals_fn;
      /* Iterate across all elements.  */
      gl_list_node_t node = list->root;
      iterstack_t stack;
      iterstack_item_t *stack_ptr = &stack[0];
      size_t index = 0;
  
      if (start_index == 0)
        {
  	/* Consider all elements.  */
  	for (;;)
  	  {
  	    /* Descend on left branch.  */
  	    for (;;)
  	      {
  		if (node == NULL)
  		  break;
  		stack_ptr->node = node;
  		stack_ptr->rightp = 0;
  		node = node->left;
  		stack_ptr++;
  	      }
  	    /* Climb up again.  */
  	    for (;;)
  	      {
  		if (stack_ptr == &stack[0])
  		  return NULL;
  		stack_ptr--;
  		if (!stack_ptr->rightp)
  		  break;
  	      }
  	    node = stack_ptr->node;
  	    /* Test against current element.  */
  	    if (equals != NULL ? equals (elt, node->value) : elt == node->value)
  	      return node;
  	    index++;
  	    if (index >= end_index)
  	      return NULL;
  	    /* Descend on right branch.  */
  	    stack_ptr->rightp = 1;
  	    node = node->right;
  	    stack_ptr++;
  	  }
        }
      else
        {
  	/* Consider only elements at indices >= start_index.
  	   In this case, rightp contains the difference between the start_index
  	   for the parent node and the one for the child node (0 when the child
  	   node is the parent's left child, > 0 when the child is the parent's
  	   right child).  */
  	for (;;)
  	  {
  	    /* Descend on left branch.  */
  	    for (;;)
  	      {
  		if (node == NULL)
  		  break;
  		if (node->branch_size <= start_index)
  		  break;
  		stack_ptr->node = node;
  		stack_ptr->rightp = 0;
  		node = node->left;
  		stack_ptr++;
  	      }
  	    /* Climb up again.  */
  	    for (;;)
  	      {
  		if (stack_ptr == &stack[0])
  		  return NULL;
  		stack_ptr--;
  		if (!stack_ptr->rightp)
  		  break;
  		start_index += stack_ptr->rightp;
  	      }
  	    node = stack_ptr->node;
  	    {
  	      size_t left_branch_size1 =
  		(node->left != NULL ? node->left->branch_size : 0) + 1;
  	      if (start_index < left_branch_size1)
  		{
  		  /* Test against current element.  */
  		  if (equals != NULL ? equals (elt, node->value) : elt == node->value)
  		    return node;
  		  /* Now that we have considered all indices < left_branch_size1,
  		     we can increment start_index.  */
  		  start_index = left_branch_size1;
  		}
  	      index++;
  	      if (index >= end_index)
  		return NULL;
  	      /* Descend on right branch.  */
  	      start_index -= left_branch_size1;
  	      stack_ptr->rightp = left_branch_size1;
  	    }
  	    node = node->right;
  	    stack_ptr++;
  	  }
        }
    }
  }
  
  static size_t
  gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
  			 const void *elt)
  {
    if (!(start_index <= end_index
  	&& end_index <= (list->root != NULL ? list->root->branch_size : 0)))
      /* Invalid arguments.  */
      abort ();
    {
      gl_listelement_equals_fn equals = list->base.equals_fn;
      /* Iterate across all elements.  */
      gl_list_node_t node = list->root;
      iterstack_t stack;
      iterstack_item_t *stack_ptr = &stack[0];
      size_t index = 0;
  
      if (start_index == 0)
        {
  	/* Consider all elements.  */
  	for (;;)
  	  {
  	    /* Descend on left branch.  */
  	    for (;;)
  	      {
  		if (node == NULL)
  		  break;
  		stack_ptr->node = node;
  		stack_ptr->rightp = 0;
  		node = node->left;
  		stack_ptr++;
  	      }
  	    /* Climb up again.  */
  	    for (;;)
  	      {
  		if (stack_ptr == &stack[0])
  		  return (size_t)(-1);
  		stack_ptr--;
  		if (!stack_ptr->rightp)
  		  break;
  	      }
  	    node = stack_ptr->node;
  	    /* Test against current element.  */
  	    if (equals != NULL ? equals (elt, node->value) : elt == node->value)
  	      return index;
  	    index++;
  	    if (index >= end_index)
  	      return (size_t)(-1);
  	    /* Descend on right branch.  */
  	    stack_ptr->rightp = 1;
  	    node = node->right;
  	    stack_ptr++;
  	  }
        }
      else
        {
  	/* Consider only elements at indices >= start_index.
  	   In this case, rightp contains the difference between the start_index
  	   for the parent node and the one for the child node (0 when the child
  	   node is the parent's left child, > 0 when the child is the parent's
  	   right child).  */
  	for (;;)
  	  {
  	    /* Descend on left branch.  */
  	    for (;;)
  	      {
  		if (node == NULL)
  		  break;
  		if (node->branch_size <= start_index)
  		  break;
  		stack_ptr->node = node;
  		stack_ptr->rightp = 0;
  		node = node->left;
  		stack_ptr++;
  	      }
  	    /* Climb up again.  */
  	    for (;;)
  	      {
  		if (stack_ptr == &stack[0])
  		  return (size_t)(-1);
  		stack_ptr--;
  		if (!stack_ptr->rightp)
  		  break;
  		start_index += stack_ptr->rightp;
  	      }
  	    node = stack_ptr->node;
  	    {
  	      size_t left_branch_size1 =
  		(node->left != NULL ? node->left->branch_size : 0) + 1;
  	      if (start_index < left_branch_size1)
  		{
  		  /* Test against current element.  */
  		  if (equals != NULL ? equals (elt, node->value) : elt == node->value)
  		    return index;
  		  /* Now that we have considered all indices < left_branch_size1,
  		     we can increment start_index.  */
  		  start_index = left_branch_size1;
  		}
  	      index++;
  	      if (index >= end_index)
  		return (size_t)(-1);
  	      /* Descend on right branch.  */
  	      start_index -= left_branch_size1;
  	      stack_ptr->rightp = left_branch_size1;
  	    }
  	    node = node->right;
  	    stack_ptr++;
  	  }
        }
    }
  }
  
  #endif
  
  static gl_list_node_t
  gl_tree_add_at (gl_list_t list, size_t position, const void *elt)
  {
    size_t count = (list->root != NULL ? list->root->branch_size : 0);
  
    if (!(position <= count))
      /* Invalid argument.  */
      abort ();
    if (position == count)
      return gl_tree_add_last (list, elt);
    else
      return gl_tree_add_before (list, node_at (list->root, position), elt);
  }
  
  static bool
  gl_tree_remove_at (gl_list_t list, size_t position)
  {
    gl_list_node_t node = list->root;
  
    if (!(node != NULL && position < node->branch_size))
      /* Invalid argument.  */
      abort ();
    node = node_at (node, position);
    return gl_tree_remove_node (list, node);
  }
  
  static bool
  gl_tree_remove (gl_list_t list, const void *elt)
  {
    if (list->root != NULL)
      {
        gl_list_node_t node =
  	gl_tree_search_from_to (list, 0, list->root->branch_size, elt);
  
        if (node != NULL)
  	return gl_tree_remove_node (list, node);
      }
    return false;
  }
  
  #if !WITH_HASHTABLE
  
  static void
  gl_tree_list_free (gl_list_t list)
  {
    /* Iterate across all elements in post-order.  */
    gl_list_node_t node = list->root;
    iterstack_t stack;
    iterstack_item_t *stack_ptr = &stack[0];
  
    for (;;)
      {
        /* Descend on left branch.  */
        for (;;)
  	{
  	  if (node == NULL)
  	    break;
  	  stack_ptr->node = node;
  	  stack_ptr->rightp = false;
  	  node = node->left;
  	  stack_ptr++;
  	}
        /* Climb up again.  */
        for (;;)
  	{
  	  if (stack_ptr == &stack[0])
  	    goto done_iterate;
  	  stack_ptr--;
  	  node = stack_ptr->node;
  	  if (!stack_ptr->rightp)
  	    break;
  	  /* Free the current node.  */
  	  if (list->base.dispose_fn != NULL)
  	    list->base.dispose_fn (node->value);
  	  free (node);
  	}
        /* Descend on right branch.  */
        stack_ptr->rightp = true;
        node = node->right;
        stack_ptr++;
      }
   done_iterate:
    free (list);
  }
  
  #endif
  
  /* --------------------- gl_list_iterator_t Data Type --------------------- */
  
  static gl_list_iterator_t
  gl_tree_iterator (gl_list_t list)
  {
    gl_list_iterator_t result;
    gl_list_node_t node;
  
    result.vtable = list->base.vtable;
    result.list = list;
    /* Start node is the leftmost node.  */
    node = list->root;
    if (node != NULL)
      while (node->left != NULL)
        node = node->left;
    result.p = node;
    /* End point is past the rightmost node.  */
    result.q = NULL;
  #ifdef lint
    result.i = 0;
    result.j = 0;
    result.count = 0;
  #endif
  
    return result;
  }
  
  static gl_list_iterator_t
  gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
  {
    size_t count = (list->root != NULL ? list->root->branch_size : 0);
    gl_list_iterator_t result;
  
    if (!(start_index <= end_index && end_index <= count))
      /* Invalid arguments.  */
      abort ();
    result.vtable = list->base.vtable;
    result.list = list;
    /* Start node is the node at position start_index.  */
    result.p = (start_index < count ? node_at (list->root, start_index) : NULL);
    /* End point is the node at position end_index.  */
    result.q = (end_index < count ? node_at (list->root, end_index) : NULL);
  #ifdef lint
    result.i = 0;
    result.j = 0;
    result.count = 0;
  #endif
  
    return result;
  }
  
  static bool
  gl_tree_iterator_next (gl_list_iterator_t *iterator,
  		       const void **eltp, gl_list_node_t *nodep)
  {
    if (iterator->p != iterator->q)
      {
        gl_list_node_t node = (gl_list_node_t) iterator->p;
        *eltp = node->value;
        if (nodep != NULL)
  	*nodep = node;
        /* Advance to the next node.  */
        if (node->right != NULL)
  	{
  	  node = node->right;
  	  while (node->left != NULL)
  	    node = node->left;
  	}
        else
  	{
  	  while (node->parent != NULL && node->parent->right == node)
  	    node = node->parent;
  	  node = node->parent;
  	}
        iterator->p = node;
        return true;
      }
    else
      return false;
  }
  
  static void
  gl_tree_iterator_free (gl_list_iterator_t *iterator)
  {
  }
  
  /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
  
  static gl_list_node_t
  gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
  			   const void *elt)
  {
    gl_list_node_t node;
  
    for (node = list->root; node != NULL; )
      {
        int cmp = compar (node->value, elt);
  
        if (cmp < 0)
  	node = node->right;
        else if (cmp > 0)
  	node = node->left;
        else /* cmp == 0 */
  	{
  	  /* We have an element equal to ELT.  But we need the leftmost such
  	     element.  */
  	  gl_list_node_t found = node;
  	  node = node->left;
  	  for (; node != NULL; )
  	    {
  	      int cmp2 = compar (node->value, elt);
  
  	      if (cmp2 < 0)
  		node = node->right;
  	      else if (cmp2 > 0)
  		/* The list was not sorted.  */
  		abort ();
  	      else /* cmp2 == 0 */
  		{
  		  found = node;
  		  node = node->left;
  		}
  	    }
  	  return found;
  	}
      }
    return NULL;
  }
  
  static gl_list_node_t
  gl_tree_sortedlist_search_from_to (gl_list_t list,
  				   gl_listelement_compar_fn compar,
  				   size_t low, size_t high,
  				   const void *elt)
  {
    gl_list_node_t node;
  
    if (!(low <= high
  	&& high <= (list->root != NULL ? list->root->branch_size : 0)))
      /* Invalid arguments.  */
      abort ();
  
    for (node = list->root; node != NULL; )
      {
        size_t left_branch_size =
  	(node->left != NULL ? node->left->branch_size : 0);
  
        if (low > left_branch_size)
  	{
  	  low -= left_branch_size + 1;
  	  high -= left_branch_size + 1;
  	  node = node->right;
  	}
        else if (high <= left_branch_size)
  	node = node->left;
        else
  	{
  	  /* Here low <= left_branch_size < high.  */
  	  int cmp = compar (node->value, elt);
  
  	  if (cmp < 0)
  	    {
  	      low = 0;
  	      high -= left_branch_size + 1;
  	      node = node->right;
  	    }
  	  else if (cmp > 0)
  	    node = node->left;
  	  else /* cmp == 0 */
  	    {
  	      /* We have an element equal to ELT.  But we need the leftmost
  		 such element.  */
  	      gl_list_node_t found = node;
  	      node = node->left;
  	      for (; node != NULL; )
  		{
  		  size_t left_branch_size2 =
  		    (node->left != NULL ? node->left->branch_size : 0);
  
  		  if (low > left_branch_size2)
  		    {
  		      low -= left_branch_size2 + 1;
  		      node = node->right;
  		    }
  		  else
  		    {
  		      /* Here low <= left_branch_size2.  */
  		      int cmp2 = compar (node->value, elt);
  
  		      if (cmp2 < 0)
  			{
  			  low = 0;
  			  node = node->right;
  			}
  		      else if (cmp2 > 0)
  			/* The list was not sorted.  */
  			abort ();
  		      else /* cmp2 == 0 */
  			{
  			  found = node;
  			  node = node->left;
  			}
  		    }
  		}
  	      return found;
  	    }
  	}
      }
    return NULL;
  }
  
  static size_t
  gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
  			    const void *elt)
  {
    gl_list_node_t node;
    size_t position;
  
    for (node = list->root, position = 0; node != NULL; )
      {
        int cmp = compar (node->value, elt);
  
        if (cmp < 0)
  	{
  	  if (node->left != NULL)
  	    position += node->left->branch_size;
  	  position++;
  	  node = node->right;
  	}
        else if (cmp > 0)
  	node = node->left;
        else /* cmp == 0 */
  	{
  	  /* We have an element equal to ELT.  But we need the leftmost such
  	     element.  */
  	  size_t found_position =
  	    position + (node->left != NULL ? node->left->branch_size : 0);
  	  node = node->left;
  	  for (; node != NULL; )
  	    {
  	      int cmp2 = compar (node->value, elt);
  
  	      if (cmp2 < 0)
  		{
  		  if (node->left != NULL)
  		    position += node->left->branch_size;
  		  position++;
  		  node = node->right;
  		}
  	      else if (cmp2 > 0)
  		/* The list was not sorted.  */
  		abort ();
  	      else /* cmp2 == 0 */
  		{
  		  found_position =
  		    position
  		    + (node->left != NULL ? node->left->branch_size : 0);
  		  node = node->left;
  		}
  	    }
  	  return found_position;
  	}
      }
    return (size_t)(-1);
  }
  
  static size_t
  gl_tree_sortedlist_indexof_from_to (gl_list_t list,
  				    gl_listelement_compar_fn compar,
  				    size_t low, size_t high,
  				    const void *elt)
  {
    gl_list_node_t node;
    size_t position;
  
    if (!(low <= high
  	&& high <= (list->root != NULL ? list->root->branch_size : 0)))
      /* Invalid arguments.  */
      abort ();
  
    for (node = list->root, position = 0; node != NULL; )
      {
        size_t left_branch_size =
  	(node->left != NULL ? node->left->branch_size : 0);
  
        if (low > left_branch_size)
  	{
  	  low -= left_branch_size + 1;
  	  high -= left_branch_size + 1;
  	  position += left_branch_size + 1;
  	  node = node->right;
  	}
        else if (high <= left_branch_size)
  	node = node->left;
        else
  	{
  	  /* Here low <= left_branch_size < high.  */
  	  int cmp = compar (node->value, elt);
  
  	  if (cmp < 0)
  	    {
  	      low = 0;
  	      high -= left_branch_size + 1;
  	      position += left_branch_size + 1;
  	      node = node->right;
  	    }
  	  else if (cmp > 0)
  	    node = node->left;
  	  else /* cmp == 0 */
  	    {
  	      /* We have an element equal to ELT.  But we need the leftmost
  		 such element.  */
  	      size_t found_position =
  		position + (node->left != NULL ? node->left->branch_size : 0);
  	      node = node->left;
  	      for (; node != NULL; )
  		{
  		  size_t left_branch_size2 =
  		    (node->left != NULL ? node->left->branch_size : 0);
  
  		  if (low > left_branch_size2)
  		    {
  		      low -= left_branch_size2 + 1;
  		      node = node->right;
  		    }
  		  else
  		    {
  		      /* Here low <= left_branch_size2.  */
  		      int cmp2 = compar (node->value, elt);
  
  		      if (cmp2 < 0)
  			{
  			  position += left_branch_size2 + 1;
  			  node = node->right;
  			}
  		      else if (cmp2 > 0)
  			/* The list was not sorted.  */
  			abort ();
  		      else /* cmp2 == 0 */
  			{
  			  found_position = position + left_branch_size2;
  			  node = node->left;
  			}
  		    }
  		}
  	      return found_position;
  	    }
  	}
      }
    return (size_t)(-1);
  }
  
  static gl_list_node_t
  gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
  			const void *elt)
  {
    gl_list_node_t node = list->root;
  
    if (node == NULL)
      return gl_tree_add_first (list, elt);
  
    for (;;)
      {
        int cmp = compar (node->value, elt);
  
        if (cmp < 0)
  	{
  	  if (node->right == NULL)
  	    return gl_tree_add_after (list, node, elt);
  	  node = node->right;
  	}
        else if (cmp > 0)
  	{
  	  if (node->left == NULL)
  	    return gl_tree_add_before (list, node, elt);
  	  node = node->left;
  	}
        else /* cmp == 0 */
  	return gl_tree_add_before (list, node, elt);
      }
  }
  
  static bool
  gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
  			   const void *elt)
  {
    gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt);
    if (node != NULL)
      return gl_tree_remove_node (list, node);
    else
      return false;
  }
  

Download