kernels/linux-2.4.0/mm/mmap_avl.c
/* Removes a node out of a tree. */
Removes a node out of a tree.
Removes a node out of a tree .
static void avl_remove (struct vm_area_struct * node_to_delete, struct vm_area_struct ** ptree)
{
	vm_avl_key_t key = node_to_delete->vm_avl_key;
	struct vm_area_struct ** nodeplace = ptree;
	struct vm_area_struct ** stack[avl_maxheight];
	int stack_count = 0;
	struct vm_area_struct *** stack_ptr = &stack[0]; 
	struct vm_area_struct ** nodeplace_to_delete;
	for (;;) {
		struct vm_area_struct * node = *nodeplace;
#ifdef DEBUG_AVL
		if (node == vm_avl_empty) {
			printk("avl_remove: node to delete not found in tree\n");
			return;
		}
#endif
		*stack_ptr++ = nodeplace; stack_count++;
		if (key == node->vm_avl_key)
			break;
		if (key < node->vm_avl_key)
			nodeplace = &node->vm_avl_left;
		else
			nodeplace = &node->vm_avl_right;
	}
	nodeplace_to_delete = nodeplace;
	if (node_to_delete->vm_avl_left == vm_avl_empty) {
		*nodeplace_to_delete = node_to_delete->vm_avl_right;
		stack_ptr--; stack_count--;
	} else {
		struct vm_area_struct *** stack_ptr_to_delete = stack_ptr;
		struct vm_area_struct ** nodeplace = &node_to_delete->vm_avl_left;
		struct vm_area_struct * node;
		for (;;) {
			node = *nodeplace;
			if (node->vm_avl_right == vm_avl_empty)
				break;
			*stack_ptr++ = nodeplace; stack_count++;
			nodeplace = &node->vm_avl_right;
		}
		*nodeplace = node->vm_avl_left;
		node->vm_avl_left = node_to_delete->vm_avl_left;
		node->vm_avl_right = node_to_delete->vm_avl_right;
		node->vm_avl_height = node_to_delete->vm_avl_height;
		*nodeplace_to_delete = node; 
		*stack_ptr_to_delete = &node->vm_avl_left; 
	}
	avl_rebalance(stack_ptr,stack_count);
}
static void avl_remove ( struct vm_area_struct * node_to_delete , struct vm_area_struct * * ptree ) { vm_avl_key_t key = node_to_delete -> vm_avl_key ; struct vm_area_struct * * nodeplace = ptree ; struct vm_area_struct * * stack [ avl_maxheight ] ; int stack_count = 0 ; struct vm_area_struct * * * stack_ptr = & stack [ 0 ] ; struct vm_area_struct * * nodeplace_to_delete ; for ( ; ; ) { struct vm_area_struct * node = * nodeplace ; #ifdef DEBUG_AVL if ( node == vm_avl_empty ) { printk ( " \n " ) ; return ; } #endif * stack_ptr ++ = nodeplace ; stack_count ++ ; if ( key == node -> vm_avl_key ) break ; if ( key < node -> vm_avl_key ) nodeplace = & node -> vm_avl_left ; else nodeplace = & node -> vm_avl_right ; } nodeplace_to_delete = nodeplace ; if ( node_to_delete -> vm_avl_left == vm_avl_empty ) { * nodeplace_to_delete = node_to_delete -> vm_avl_right ; stack_ptr -- ; stack_count -- ; } else { struct vm_area_struct * * * stack_ptr_to_delete = stack_ptr ; struct vm_area_struct * * nodeplace = & node_to_delete -> vm_avl_left ; struct vm_area_struct * node ; for ( ; ; ) { node = * nodeplace ; if ( node -> vm_avl_right == vm_avl_empty ) break ; * stack_ptr ++ = nodeplace ; stack_count ++ ; nodeplace = & node -> vm_avl_right ; } * nodeplace = node -> vm_avl_left ; node -> vm_avl_left = node_to_delete -> vm_avl_left ; node -> vm_avl_right = node_to_delete -> vm_avl_right ; node -> vm_avl_height = node_to_delete -> vm_avl_height ; * nodeplace_to_delete = node ; * stack_ptr_to_delete = & node -> vm_avl_left ; } avl_rebalance ( stack_ptr , stack_count ) ; }
Removes a node out of a tree.
Removes a node out of a tree .
/* = &stack[stackcount] */ /* what? node_to_delete not found in tree? */ /* Have to remove node_to_delete = *nodeplace_to_delete. */ /* node replaces node_to_delete */ /* replace node_to_delete */ /* replace &node_to_delete->vm_avl_left */