www.delorie.com/gnu/docs/avl/libavl_109.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

6.7 Copying

Copying an AVL tree is similar to copying a BST. The only important difference is that we have to copy the AVL balance factor between nodes as well as node data. We don't check our stack height here, either.

 
&#60;@xref{\NODE\, , BST copy error helper function; bst =>.&#62; avl,82}
struct avl_table *
avl_copy (const struct avl_table *org, avl_copy_func *copy, avl_item_func *destroy, struct libavl_allocator *allocator)
{ struct avl_node *stack[2 * (AVL_MAX_HEIGHT + 1)]; int height = 0; struct avl_table *new; const struct avl_node *x; struct avl_node *y; assert (org != NULL); new = avl_create (org-&#62;avl_compare, org-&#62;avl_param, allocator != NULL ? allocator : org-&#62;avl_alloc); if (new == NULL) return NULL; new-&#62;avl_count = org-&#62;avl_count; if (new-&#62;avl_count == 0) return new; x = (const struct avl_node *) &org-&#62;avl_root; y = (struct avl_node *) &new-&#62;avl_root; for (;;)
{ while (x-&#62;avl_link[0] != NULL)
{ assert (height < 2 * (AVL_MAX_HEIGHT + 1)); y-&#62;avl_link[0] =
new-&#62;avl_alloc-&#62;libavl_malloc (new-&#62;avl_alloc, sizeof *y-&#62;avl_link[0]); if (y-&#62;avl_link[0] == NULL)
{ if (y != (struct avl_node *) &new-&#62;avl_root)
{ y-&#62;avl_data = NULL; y-&#62;avl_link[1] = NULL; } copy_error_recovery (stack, height, new, destroy); return NULL; } stack[height++] = (struct avl_node *) x; stack[height++] = y; x = x-&#62;avl_link[0]; y = y-&#62;avl_link[0]; } y-&#62;avl_link[0] = NULL; for (;;)
{ y-&#62;avl_balance = x-&#62;avl_balance; if (copy == NULL) y-&#62;avl_data = x-&#62;avl_data; else
{ y-&#62;avl_data = copy (x-&#62;avl_data, org-&#62;avl_param); if (y-&#62;avl_data == NULL)
{ y-&#62;avl_link[1] = NULL; copy_error_recovery (stack, height, new, destroy); return NULL; } } if (x-&#62;avl_link[1] != NULL)
{ y-&#62;avl_link[1] =
new-&#62;avl_alloc-&#62;libavl_malloc (new-&#62;avl_alloc, sizeof *y-&#62;avl_link[1]); if (y-&#62;avl_link[1] == NULL)
{ copy_error_recovery (stack, height, new, destroy); return NULL; } x = x-&#62;avl_link[1]; y = y-&#62;avl_link[1]; break; } else
y-&#62;avl_link[1] = NULL; if (height <= 2) return new; y = stack[--height]; x = stack[--height]; } } }
This code is included in @refalso{145


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003